Bộ phân lớp dựa trên thuật toán K người láng giềng gần nhất là một bộ phân lớp dựa trên bộ nhớ, đơn giản vì nó được xây dựng bằng cách lưu trữ tất cả các đối tượng trong tập huấn luyện. Để phân lớp cho một điểm dữ liệu mới x, trước hết bộ phân lớp sẽ tính khoảng cách từ điểm dữ liệu trong tập huấn luyện. Qua đó tìm được tập N(x, D, k) gồm k điểm dữ liệu mẫu có khoảng cách đến x là gần nhất. Ví dụ nếu các dữ liệu mẫu được biểu diễn bởi không gian vector thì chúng ta có thể sử dụng khoảng cách Euclian để tính khoảng cách giữa các điểm dữ liệu với nhau. Sau khi xác định được tập N(x, D, k), bộ phân lớp sẽ gán nhãn cho điểm dữ liệu x bằng lớp chiếm đại đa số trong tập N(x, D, k). Mặc dù rất đơn giản, nhưng thuật toán K người láng giềng gần nhất đã cho kết quả tốt trong nhiều ứng dụng thực tế. Để áp dụng thuật toán K người láng giềng vào tài liệu văn bản, chúng ta sử dụng hàm tính trọng số cho mỗi lớp theo biểu thức : score(c|x) = Σ cos(x,x') với mọi x' thuộc tập Nc(x, D, k). Trong đó Nc(x, D, k) là tập con chỉ chứa các đối tượng thuộc lớp c của tập N(x, D, k). Khi đó tài liệu x sẽ được phân vào lớp c0 nếu: score(c0 | x) = Max {score(c | x), c∈C} Phương pháp K người láng giềng gần nhất là một phương pháp đươn giản. Tuy nhiên, thuật toán này ổn định và sai sót thấp khi số văn bản trong tập văn bản láng giềng phải lớn. Trong ứng dụng phân loại văn bản với số lượng văn bản rất lớn, thuật toán này không thực sự tốt khi phải sử dụng quá nhiều bộ nhớ. Có vài cách để giảm không gian bộ nhớ (như chỉ lưu trữ N văn bản tiêu biểu cho mỗi lớp) nhưng lại làm ảnh hưởng tới kết quả của thuật toán. |
 | |
|
|