Giải thuật k hàng xóm gần nhất

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Khi dữ liệu được biểu diễn dưới dạng các phần tử trong không gian nhiều chiều thì sẽ hình thành nên khái niệm láng giềng. Giả sử chúng ta muốn dự báo hành vi của một tập khách hàng với một cơ sở dữ liệu mô tả về các khách hàng đó. Một giả định quan trọng đòi hỏi đặt ra là khách hàng cùng một kiểu sẽ có cùng một hành động. Trong không gian dữ liệu, một kiểu khách hàng không gì hơn là một vùng dữ liệu mà các bộ có cùng kiểu. Nói khác đi, các bộ có cùng kiểu sẽ phân bố gần nhau vào chúng sẽ là “láng giềng” của nhau. Dựa trên ý tưởng này, chúng ta có thể phát triển một thuật toán học rất đơn giản nhưng hiệu quả “k - láng giềng gần nhất”. Phương châm của phương pháp k - láng giềng gần nhất là “làm như láng giềng làm”. Nếu như chúng ta muốn dự báo hành vi của một cá nhân nào đó, chúng ta bắt đầu bằng cách nhìn vào các hành vi của chẳng hạn 10 cá nhân gần nhất với anh ta. Và giá trị trung bình của các hành vi của các láng giềng này sẽ dự báo cho hành vi của anh ta. Số k trong phương pháp k - láng giềng gần nhất dùng để chỉ số láng giềng được xem xét. Phương pháp k - láng giềng gần nhất đơn giản chưa phải là một kỹ thuật học mà gần như một phương pháp tìm kiếm. Nếu ta muốn phương pháp này dự báo hành vi cho từng phần tử trong một tập dữ liệu có n bộ thì ta phải so sánh từng bộ với tất cả các bộ còn lại và như vậy, độ phức tạp sẽ là O(n2). Điều đó có nghĩa là không thể áp dụng phương pháp này cho dữ liệu lớn. Một vấn đề của phương pháp k - láng giềng gần nhất là độ đo, tức là xác định khoảng cách của hai phần tử trong không gian. Do các thuộc tính có nhiều khuôn dạng dữ liệu khác nhau, có thể là các giá trị liên tục, rời rạc hoặc mờ nên việc tìm một độ đo hiệu quả là rất khó. Các thuộc tính quan trọng có thể có một trọng số cao hơn trong công thức tính độ đo. Việc áp dụng thuật toán k - láng giềng gần nhất chỉ là dự báo hiệu quả trong một số trường hợp nhất định. Chẳng hạn, với tập dữ liệu phân bố tương đối đều trong cả không gian, k - láng giềng gần nhất sẽ không tìm ra được các thông tin nhiều ý nghĩa. Nhưng nếu trong một không gian khách hàng có thu nhập khác nhau lớn, chắc chắn hành vi mua sắm cũng khác nhau và như vậy phương pháp k - láng giềng gần nhất có thể hữu ích.