信息檢索の扁平聚類：Flat Clustering

04-18

前言：

聚類的概念(扁平演算法)
聚類在IR中的應用及扁平聚類介紹
K-均值(K-Means)聚類演算法
聚類評價
簇(cluster)個數(即聚類的結果類別個數)確定

啥是聚類（Clustering）：

1. 定義

聚類是將一系列文檔按照相似性聚團成子集或者簇(cluster)的過程
簇內文檔之間應該彼此相似
簇間文檔（不同簇之間）之間相似度不大
聚類是一種最常見的無監督學習(unsupervised learning)方法
無監督意味著沒有已標註好的數據集

2. 對數據集的要求

具有清晰簇結構的數據集
提出一個演算法來尋找該例中的簇結構

3. 分類與聚類的比較

分類：有監督的學習
聚類：無監督的學習
分類：類別事先人工定義好，並且是學習演算法輸入的一部分
聚類：簇在沒有人工輸入的情況下從數據中推理而得（但是，很多因素會影響聚類的輸出結果：簇的個數、相似度計算方法、文檔的表示方式，等等）

4. 扁平演算法

將N篇文檔劃分成K個簇
給定一個文檔集合及聚類結果簇的個數K
尋找一個劃分將這個文檔集合分成K個簇，該結果滿足某個最優劃分準則
全局優化：窮舉所有的劃分結果，從中選擇最優的那個劃分結果
（PS：如果扁平演算法無法處理時，可用高效的啟發式方法: K-均值聚類演算法）

聚類在IR的應用：

1. 聚類假設

在考慮文檔和信息需求之間的相關性時，同一簇中的文檔表現互相類似（Closely associated documents tend to be relevant to the same requests）
聚類在IR中的應用所有應用都直接或間接基於上述聚類假設

2. 聚類在IR中的應用

$egin{array}{||c|} hline extbf{應用} & extbf{聚類對象} & extbf{優點}\ hline 搜索結果聚類 & 搜索結果 & 提供面向用戶的更有效的展示\ hline 「分散-集中」界面 & 文檔集和文檔子集 & 提供另一種用戶界面（不需人工輸入關鍵詞）\ hline 文檔集聚類 & 文檔集 & 提供一種面向探索式瀏覽的信息展示方法\ hline 基於語言建模的IR檔集 & 文檔集 & 提高了正確率/召回率\ hline 基於聚類的檢索 & 文檔集 & 加快了搜索的速度\ hline end{array}$

3. 文檔聚類如何提高搜索召回率

可以實現將文檔集中的文檔進行聚類
當文檔d和查詢匹配時，也返回包含d的簇所包含的其它文檔
我們希望通過上述做法，在輸入查詢「car「時，也能夠返回包含「automobile」的文檔
由於聚類演算法會把包含：「car」的文檔和包含，「automobile」的文檔聚在一起
兩種文檔都包含諸如：「parts」、「dealer」、「mercedes」和「road trip」之類的詞語

4. 扁平聚類與層次聚類比較

扁平演算法

通過一開始將全部或部分文檔隨機劃分為不同的組
通過迭代方式不斷修正
代表演算法：K-均值聚類演算法

層次演算法

構建具有層次結構的簇
自底向上(Bottom-up)的演算法稱為凝聚式(agglomerative)演算法
自頂向下(Top-down)的演算法稱為分裂式(divisive)演算法

5. 硬聚類與軟聚類比較

硬聚類(Hard clustering): 每篇文檔僅僅屬於一個簇

相對容易實現

軟聚類(Soft clustering): 一篇文檔可以屬於多個簇

K-均值（K-Means）聚類演算法演算法：

1. 聚類中的文檔表示

向量空間模型(Vector Space Model)
同基於向量空間的分類一樣，這裡我們也採用歐氏距離的方法來計算向量之間的相關性
歐氏距離與餘弦相似度(consine similarity)差不多等價
如果兩個向量都基於長度歸一化，那麼歐氏距離和餘弦相似度是等價的
然而，質心向量（centroid vector）通常都沒有基於長度進行歸一化

2. K-均值聚類演算法思想

演算法中的每個簇都定義為其質心向量
劃分準則：使得所有文檔到其所在簇的質心向量的平方和最小
質心向量的定義： $vec{mu}（omega）= frac{1}{|omega|}sum_{vec{x}in omega}{vec{x}}$ ，其中 $omega$ 代表一個簇
通過下列兩步來實現目標優化

重分配（reassignment）：將每篇文檔分配給離它最近的簇
重計算（recomputation）：重新計算每個簇的質心向量

偽代碼如下：

3. K-均值聚類的例子

1、文檔的向量表示

2、隨便選擇兩個種子（K=2）

3、將文檔分配給離它最近的質心向量

4、分配後的簇（第一次）

5、重新計算質心向量

6、將文檔分配給離它最近的質心向量（第二次）

7、重新分配的結果

省略第四到第六次的計算和分配，不然占的空間太多了/(ㄒoㄒ)/~~

8、重新計算質心向量

9、重新分配（第七次）

10、分配結果

11、重新計算質心向量

12、質心向量和分配結果最終收斂

4. K-均值聚類演算法的初始化

種子的隨機選擇只是K-均值聚類演算法的一種初始化方法之一
隨機選擇不太魯棒(Robutness)：可能會獲得一個次優的聚類結果
一些確定初始質心向量的更好辦法：

非隨機地採用某些啟發式方法來選擇種子(比如，過濾掉一些離群點，或者尋找具有較好文檔空間覆蓋度的種子集合)
採用層級聚類演算法尋找好的種子
選擇 i (比如 i = 10) 次不同的隨機種子集合，對每次產生的隨機種子集合運行K-均值聚類演算法，最後選擇具有最小RSS值的聚類結果

5. K-均值聚類演算法一定會收斂：證明

RSS（Residual Sum of Squares，殘差平方和）：所有簇上的文檔向量到(最近的)質心向量的距離平方和的總和

$RSS_{k} = sum_{x in omega_k}|vec{x} - vec{mu}(omega_k)|^{2}$
$RSS = sum{^{K}_{k=1}}RSS_{k}$

每次分配和重計算後RSS都會下降，因為每個向量都被移到離它最近的質心所代表的簇

$RSS_{k}(vec{v}) = sum_{vec{x}in omega_k}|vec{v} - vec{x}|^{2} = sum_{vec{x}in omega_{k}}sum_{m=1}^{M}(V_m - X_m)^2$
$frac{partial RSS_{k}(vec{v})}{partial V_m} = sum_{vec{x}in omega_k}2(v_m - x_m) = 0$
$v_m = frac{1}{|omega_k|}sum_{vec{x in omega_k}}{x_m}$

可能的聚類結果是有窮的，因此一定會有一個固定點,但是不知道到達收斂所需多少時間

6. 缺點

收斂並不意味著會達到全局最優的聚類結果，這是最大的缺點之一
如果開始的種子沒選好，那麼最終的聚類結果可能會很糟糕

7. 時間複雜度

整體複雜度： $O(IKNM)$ ~ 線性
I ：是迭代次數的上界
$O（M）$ ：計算兩個向量距離的事件複雜度

聚類演算法評估：

1. 判斷聚類結果的好壞

內部準則（Internal criteria）

如：K-均值聚類演算法的RSS值

外部準則（External criteria）

對一個分好類的數據集進行聚類，將聚類結果和事先的類別情況進行比照，得到最後的評價結果

2. 外部準則：純度（purity）

$purity(Omega, C) = frac{1}{N}sum_{k}max_{j} |omega_k cap c_j|$
$Ω={ {ω_1, ω_2, . . . , ω_k} }$ 是簇的集合
$C ={ {c_1, c_2, . . . , c_j} }$ 是類別的集合
對每個簇 $ω_k$ : 找到一個類別 $c_j$ ，該類別包含 $omega_k$ 中的元素最多，為 $n_{kj}$ 個，也就是說 $omega_k$ 的元素最多分布在 $c_j$ 中
將所有 $n_kj$ 求和，然後除以所有的文檔數目
例子：

為計算純度：

maxj |ω1 ∩ cj | = 5 (class x, cluster 1)
maxj |ω2 ∩ cj | = 4 (class o, cluster 2)
maxj |ω3 ∩ cj | = 3 (class $diamond$ , cluster 3)
純度為 (1/17) × (5 + 4 + 3) ≈ 0.71.

3. 其他準則：

蘭迪指數（Rand Index）： $RI = frac{TP+TN}{TP+FP+FN+TN}$
歸一化互信息（Normalised mutual information）
F值：正確率和召回率的加權平均

聚類評估結果比較

所有簇指標都是從0（非常差的聚類結果）到1（完美聚類）

簇（Cluster）個數確定：

1. 簇個數確定

在很多應用中，簇個數 K 是事先給定的

比如，可能存在對K的外部限制
例子：在「分散-集中」應用中，在顯示器上(上世紀90年代)很難顯示超過10-20個簇

如果沒有外部的限制會怎樣？是否存在正確的簇個數？

一種辦法：定義一個優化準則
給定文檔，找到達到最優情況的K 值

參考文獻：

Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze, Introduction to Information Retrieval
機器學習演算法比較