Thuật toán k-láng giềng gần nhất

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.

Comments