Scikit Learn - K-Nearest Neighbors (KNN)
Chương này sẽ giúp bạn hiểu các phương thức lân cận gần nhất trong Sklearn.
Phương pháp học tập dựa trên láng giềng có cả hai loại cụ thể là supervised và unsupervised. Học tập dựa trên hàng xóm có giám sát có thể được sử dụng cho cả phân loại cũng như các bài toán dự đoán hồi quy, nhưng nó chủ yếu được sử dụng cho các bài toán dự đoán phân loại trong ngành.
Phương pháp học tập dựa trên láng giềng không có giai đoạn đào tạo chuyên biệt và sử dụng tất cả dữ liệu để đào tạo trong khi phân loại. Nó cũng không giả định bất cứ điều gì về dữ liệu cơ bản. Đó là lý do họ lười biếng và không có tham số.
Nguyên tắc chính đằng sau các phương pháp láng giềng gần nhất là:
Để tìm một số lượng xác định trước tủ mẫu đào tạo trong khoảng cách đến điểm dữ liệu mới
Dự đoán nhãn từ số lượng mẫu đào tạo này.
Ở đây, số lượng mẫu có thể là một hằng số do người dùng xác định như trong K-gần nhất học hàng xóm hoặc thay đổi dựa trên mật độ cục bộ của điểm như trong học hàng xóm dựa trên bán kính.
Mô-đun sklearn.neighbors
Scikit-learning có sklearn.neighborsmô-đun cung cấp chức năng cho cả phương pháp học tập dựa trên hàng xóm không giám sát và có giám sát. Là đầu vào, các lớp trong mô-đun này có thể xử lý mảng NumPy hoặcscipy.sparse ma trận.
Các loại thuật toán
Các loại thuật toán khác nhau có thể được sử dụng trong việc triển khai các phương pháp dựa trên hàng xóm như sau:
Lực lượng vũ phu
Tính toán bạo lực của khoảng cách giữa tất cả các cặp điểm trong tập dữ liệu cung cấp triển khai tìm kiếm hàng xóm ngây thơ nhất. Về mặt toán học, đối với N mẫu ở kích thước D, phương pháp tiếp cận brute-force sẽ cân bằng0[DN2]
Đối với các mẫu dữ liệu nhỏ, thuật toán này có thể rất hữu ích, nhưng nó trở nên không khả thi khi số lượng mẫu tăng lên. Tìm kiếm hàng xóm bạo lực có thể được kích hoạt bằng cách viết từ khóaalgorithm=’brute’.
Cây KD
Một trong những cấu trúc dữ liệu dựa trên cây đã được phát minh để giải quyết sự thiếu hiệu quả trong tính toán của phương pháp tiếp cận brute-force, là cấu trúc dữ liệu cây KD. Về cơ bản, cây KD là một cấu trúc cây nhị phân được gọi là cây K chiều. Nó phân vùng một cách đệ quy không gian tham số dọc theo các trục dữ liệu bằng cách chia nó thành các vùng trực giao lồng nhau mà các điểm dữ liệu được lấp đầy.
Ưu điểm
Sau đây là một số ưu điểm của thuật toán cây KD:
Construction is fast - Vì việc phân vùng chỉ được thực hiện dọc theo các trục dữ liệu nên việc xây dựng cây KD diễn ra rất nhanh.
Less distance computations- Thuật toán này cần rất ít tính toán khoảng cách để xác định láng giềng gần nhất của điểm truy vấn. Nó chỉ mất[ ()] tính toán khoảng cách.
Nhược điểm
Fast for only low-dimensional neighbor searches- Tìm kiếm hàng xóm có chiều thấp (D <20) rất nhanh nhưng khi D lớn lên thì nó trở nên không hiệu quả. Vì phân vùng chỉ được thực hiện dọc theo các trục dữ liệu,
Tìm kiếm hàng xóm trên cây KD có thể được kích hoạt bằng cách viết từ khóa algorithm=’kd_tree’.
Cây bóng
Như chúng ta biết rằng KD Tree không hiệu quả ở các chiều cao hơn, do đó, để giải quyết sự kém hiệu quả này của KD Tree, cấu trúc dữ liệu Ball tree đã được phát triển. Về mặt toán học, nó chia dữ liệu một cách đệ quy, thành các nút được xác định bởi tâm C và bán kính r, theo cách mà mỗi điểm trong nút nằm trong siêu hình cầu được xác định bởi tâmC và bán kính r. Nó sử dụng bất đẳng thức tam giác, được đưa ra bên dưới, làm giảm số điểm ứng viên cho tìm kiếm hàng xóm
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$Ưu điểm
Sau đây là một số ưu điểm của thuật toán Cây bóng -
Efficient on highly structured data - Khi cây bóng phân vùng dữ liệu trong một loạt các siêu quả cầu lồng vào nhau, nó hiệu quả trên dữ liệu có cấu trúc cao.
Out-performs KD-tree - Cây bóng thực hiện được cây KĐ ở chiều cao vì nó có dạng hình cầu của các nút cây bóng.
Nhược điểm
Costly - Phân vùng dữ liệu trong một loạt các siêu quả cầu lồng nhau làm cho việc xây dựng nó rất tốn kém.
Tìm kiếm hàng xóm cây bóng có thể được kích hoạt bằng cách viết từ khóa algorithm=’ball_tree’.
Chọn thuật toán láng giềng gần nhất
Việc lựa chọn một thuật toán tối ưu cho một tập dữ liệu nhất định phụ thuộc vào các yếu tố sau:
Số lượng mẫu (N) và Kích thước (D)
Đây là những yếu tố quan trọng nhất cần được xem xét khi lựa chọn thuật toán Nearest Neighbor. Đó là vì những lý do được đưa ra dưới đây -
Thời gian truy vấn của thuật toán Brute Force tăng lên là O [DN].
Thời gian truy vấn của thuật toán cây bóng phát triển là O [D log (N)].
Thời gian truy vấn của thuật toán cây KD thay đổi theo D một cách kỳ lạ mà rất khó mô tả. Khi D <20, chi phí là O [D log (N)] và thuật toán này rất hiệu quả. Mặt khác, nó không hiệu quả trong trường hợp D> 20 do chi phí tăng lên gần O [DN].
Cấu trúc dữ liệu
Một yếu tố khác ảnh hưởng đến hiệu suất của các thuật toán này là kích thước nội tại của dữ liệu hoặc độ thưa thớt của dữ liệu. Đó là vì thời gian truy vấn của các thuật toán cây bóng và cây KD có thể bị ảnh hưởng rất nhiều bởi nó. Trong khi đó, thời gian truy vấn của thuật toán Brute Force không thay đổi theo cấu trúc dữ liệu. Nói chung, các thuật toán cây bóng và cây KD tạo ra thời gian truy vấn nhanh hơn khi được cấy trên dữ liệu thưa thớt hơn với kích thước nội tại nhỏ hơn.
Số hàng xóm (k)
Số lượng hàng xóm (k) được yêu cầu cho một điểm truy vấn ảnh hưởng đến thời gian truy vấn của các thuật toán cây bóng và cây KD. Thời gian truy vấn của họ trở nên chậm hơn khi số lượng hàng xóm (k) tăng lên. Trong khi thời gian truy vấn của Brute Force sẽ không bị ảnh hưởng bởi giá trị của k.
Số điểm truy vấn
Bởi vì, chúng cần giai đoạn xây dựng, cả thuật toán cây KD và cây bóng sẽ hiệu quả nếu có số lượng điểm truy vấn lớn. Mặt khác, nếu có số lượng điểm truy vấn nhỏ hơn, thuật toán Brute Force hoạt động tốt hơn so với thuật toán cây KD và cây bóng.