[Natural Language Processing] Đánh giá chất lượng của Clustering bằng Rand Index

Trong phương pháp này, ta sẽ đánh giá dựa trên decision với hai tiêu chí như sau. Giả sử ta có N documents:
- Ta so sánh similarity giữa từng cặp documents trong số N docs này với nhau.
- Hai docs giống nhau sẽ thuộc về cùng một cluster
- Số quyết định là tổ hợp chập 2 của N. N(N-1)/2

Khi đưa ra một quyết định, ta sẽ có 4 trường hợp sau đây:

- True Positive (TP): Hai docs giống nhau thuộc về cùng 1 cluster
- True Negative (TN): Hai docs khác nhau khác cluster
- False Postive (FP): Hai docs khác nhau thuộc về cùng 1 cluster (error)
- False Negative (FN): Hai docs giống nhau khác cluster (error)

Khi đó, chỉ số RI (Rand Index) được định nghĩa như sau:

Giả sử ta có observation như hình dưới đây:

Khi đó, ta có thể tính được TP với 3 class là:

TP = tổ hợp chập 2 của 5 + tổ hợp chập 2 của 4 + tổ hợp chập 2 của 3 và tổ hợp chập 2 của 2(có thành phần này vì ta cần quan tâm đến 2 objects đỏ trong cluster 3, RI quan tâm đến 2 docs giống nhau cùng 1 cluster) = 5*4/2 + 4*3/2 + 3*2/2 + 2*1/2 = 10 + 6 + 3 + 1 = 20. (1)

TP + FP được tính là tổng của các quyết định liên quan tới hai docs giống nhau cùng 1 cluster và hai docs khác nhau cùng 1 cluster.
Ta có: TP + FP = tổ hợp chập 2 của 6 + tổ hợp chập 2 của 6 + tổ hợp chập 2 của 5 = 6*5/2 + 6*5/2 + 5*4/2 = 40 (2)

Từ (1) và (2) ta có FP = 20. (3)

Ta có tổng TP + FN là số cặp document giống nhau (có thể chung 1 cluster hoặc khác cluster).

TP + FN = Tổ hợp chập 2 của 8 (vì có 8 chấm đỏ) + tổ hợp chập 2 của 5 (5 chấm xanh) + tổ hợp chập 2 của 4 (4 chấm xanh lá) = 8*7/2 + 5*4/2 + 4*3/2 = 44 (4)

Từ (3) và (4) ta có FN = 24. (5)

Số quyết định trên cả tập là : FN + FP + TN + TP = tổ hợp chập 2 của (8 + 5 + 4) = 136 (6)

Từ (1) (3) (5) và (6) ta có TN = 136 - 24 - 20 - 20 = 72

Từ đó chỉ số RI = (TP+TN)/(TP+TN+FP+FN) = 92/136 ~ 0.68