10.HanLP實作k均值--文本聚類

筆記轉載于GitHub專案：https://github.com/NLP-LOVE/Introduction-NLP

10. 文本聚類

正所謂物以類聚，人以群分，人們在獲取資料時需要整理，將相似的資料歸檔到一起，自動發現大量樣本之間的相似性，這種根據相似性歸檔的任務稱為聚類，

10.1 概述

1. 聚類

   聚類(cluster analysis )指的是將給定物件的集合劃分為不同子集的程序，目標是使得每個子集內部的元素盡量相似，不同子集間的元素盡量不相似，這些子集又被稱為簇(cluster),一般沒有交集，

   

   一般將聚類時簇的數量視作由使用者指定的超引數，雖然存在許多自動判斷的演算法，但它們往往需要人工指定其他超引數，

   根據聚類結果的結構，聚類演算法也可以分為劃分式(partitional )和層次化(hierarchieal兩種，劃分聚類的結果是一系列不相交的子集，而層次聚類的結果是一棵樹， 葉子節點是元素，父節點是簇，本章主要介紹劃分聚類，

2. 文本聚類

   文本聚類指的是對檔案進行聚類分析，被廣泛用于文本挖掘和資訊檢索領域，

   文本聚類的基本流程分為特征提取和向量聚類兩步， 如果能將檔案表示為向量，就可以對其應用聚類演算法，這種表示程序稱為特征提取，而一旦將檔案表示為向量，剩下的演算法就與檔案無關了，這種抽象思維無論是從軟體工程的角度，還是從數學應用的角度都十分簡潔有效，

10.2 檔案的特征提取

1. 詞袋模型

   詞袋(bag-of-words )是資訊檢索與自然語言處理中最常用的檔案表示模型，它將檔案想象為一個裝有詞語的袋子， 通過袋子中每種詞語的計數等統計量將檔案表示為向量，比如下面的例子:

   人 吃 魚，
   美味 好 吃！
   

   統計詞頻后如下:

   人=1
   吃=2
   魚=1
   美味=1
   好=1
   

   檔案經過該詞袋模型得到的向量表示為[1,2,1,1,1]，這 5 個維度分別表示這 5 種詞語的詞頻，

   一般選取訓練集檔案的所有詞語構成一個詞表，詞表之外的詞語稱為 oov，不予考慮，一旦詞表固定下來，假設大小為 N，則任何一個檔案都可以通過這種方法轉換為一個N維向量，詞袋模型不考慮詞序，也正因為這個原因，詞袋模型損失了詞序中蘊含的語意，比如，對于詞袋模型來講，“人吃魚”和“魚吃人”是一樣的，這就不對了，

   不過目前工業界已經發展出很好的詞向量表示方法了: word2vec/bert 模型等，

2. 詞袋中的統計指標

   詞袋模型并非只是選取詞頻作為統計指標，而是存在許多選項，常見的統計指標如下:

   • 布爾詞頻: 詞頻非零的話截取為1，否則為0，適合長度較短的資料集
   • TF-IDF: 適合主題較少的資料集
   • 詞向量: 如果詞語本身也是某種向量的話，則可以將所有詞語的詞向量求和作為檔案向量，適合處理 OOV 問題嚴重的資料集，
   • 詞頻向量: 適合主題較多的資料集

   定義由 n 個檔案組成的集合為 S，定義其中第 i 個檔案 di 的特征向量為 di，其公式如下:

   \[d_{i}=\left(\operatorname{TF}\left(t_{1}, d_{i}\right), \operatorname{TF}\left(t_{2}, d_{i}\right), \cdots, \operatorname{TF}\left(t_{j}, d_{i}\right), \cdots, \operatorname{TF}\left(t_{m}, d_{i}\right)\right) \]

   其中 tj表示詞表中第 j 種單詞，m 為詞表大小， TF(tj, di) 表示單詞 tj 在檔案 di 中的出現次數，為了處理長度不同的檔案，通常將檔案向量處理為單位向量，即縮放向量使得 ||d||=1，

10.3 k均值演算法

一種簡單實用的聚類演算法是k均值演算法(k-means),由Stuart Lloyd于1957年提出，該演算法雖然無法保證一定能夠得到最優聚類結果，但實踐效果非常好，基于k均值演算法衍生出許多改進演算法，先介紹 k均值演算法，然后推導它的一個變種，

1. 基本原理

   形式化啊定義 k均值演算法所解決的問題，給定 n 個向量 d1 到 dn，以及一個整數 k，要求找出 k 個簇 S1 到 Sk 以及各自的質心 C1 到 Ck，使得下式最小:

   \[\text { minimize } \mathcal{I}_{\text {Euclidean }}=\sum_{r=1}^{k} \sum_{d_{i} \in S_{r}}\left\|\boldsymbol{d}_{i}-\boldsymbol{c}_{r}\right\|^{2} \]

   其中 ||di - Cr|| 是向量與質心的歐拉距離，I(Euclidean) 稱作聚類的準則函式，也就是說，k均值以最小化每個向量到質心的歐拉距離的平方和為準則進行聚類，所以該準則函式有時也稱作平方誤差和函式，而質心的計算就是簇內資料點的幾何平均:

   \[\begin{array}{l}{s_{i}=\sum_{d_{j} \in S_{i}} d_{j}} \\ {c_{i}=\frac{s_{i}}{\left|S_{i}\right|}}\end{array} \]

   其中，si 是簇 Si 內所有向量之和，稱作合成向量，

   生成 k 個簇的 k均值演算法是一種迭代式演算法，每次迭代都在上一步的基礎上優化聚類結果，步驟如下:

   • 選取 k 個點作為 k 個簇的初始質心，
   • 將所有點分別分配給最近的質心所在的簇，
   • 重新計算每個簇的質心，
   • 重復步驟 2 和步驟 3 直到質心不再發生變化，

   k均值演算法雖然無法保證收斂到全域最優，但能夠有效地收斂到一個區域最優點，對于該演算法，初級讀者重點需要關注兩個問題，即初始質心的選取和兩點距離的度量，

2. 初始質心的選取

   由于 k均值不保證收敏到全域最優，所以初始質心的選取對k均值的運行結果影響非常大，如果選取不當，則可能收斂到一個較差的區域最優點，

   一種更高效的方法是， 將質心的選取也視作準則函式進行迭代式優化的程序，其具體做法是，先隨機選擇第一個資料點作為質心，視作只有一個簇計算準則函式，同時維護每個點到最近質心的距離的平方，作為一個映射陣列 M，接著，隨機取準則函式值的一部分記作，遍歷剩下的所有資料點，若該點到最近質心的距離的平方小于0,則選取該點添加到質心串列，同時更新準則函式與 M，如此回圈多次，直至湊足 k 個初始質心，這種方法可行的原理在于，每新增一個質心，都保證了準則函式的值下降一個隨機比率， 而樸素實作相當于每次新增的質心都是完全隨機的，準則函式的增減無法控制，孰優孰劣，一目了然，

   考慮到 k均值是一種迭代式的演算法， 需要反復計算質心與兩點距離，這部分計算通常是效瓶頸，為了改進樸素 k均值演算法的運行效率，HanLP利用種更快的準則函式實作了k均值的變種，

3. 更快的準則函式

   除了歐拉準則函式，還存在一種基于余弦距離的準則函式:

   \[\text { maximize } \mathcal{I}_{\mathrm{cos}}=\sum_{r=1}^{k} \sum_{d_{i} \in S_{r}} \cos \left(\boldsymbol{d}_{i}, \boldsymbol{c}_{r}\right) \]

   該函式使用余弦函式衡量點與質心的相似度，目標是最大化同簇內點與質心的相似度，將向量夾角計算公式代人，該準則函式變換為:

   \[\mathcal{I}_{\mathrm{cos}}=\sum_{r=1}^{k} \sum_{d_{i} \in S_{r}} \frac{d_{i} \cdot c_{r}}{\left\|c_{r}\right\|} \]

   代入后變換為:

   \[\mathcal{I}_{\cos }=\sum_{r=1}^{k} \frac{S_{r} \cdot c_{r}}{\left\|c_{r}\right\|}=\sum_{r=1}^{k} \frac{\left|S_{r}\right| c_{r} \cdot c_{r}}{\left\|c_{r}\right\|}=\sum_{r=1}^{k}\left|S_{r}\right|\left\|c_{r}\right\|=\sum_{r=1}^{k}\left\|s_{r}\right\| \]

   也就是說，余弦準則函式等于 k 個簇各自合成向量的長度之和，比較之前的準則函式會發現在資料點從原簇移動到新簇時，I(Euclidean) 需要重新計算質心，以及兩個簇內所有點到新質心的距離，而對于I(cos)，由于發生改變的只有原簇和新簇兩個合成向量，只需求兩者的長度即可，計算量一下子減小不少，

   基于新準則函式 I(cos)，k均值變種演算法流程如下:

   • 選取 k 個點作為 k 個簇的初始質心，
   • 將所有點分別分配給最近的質心所在的簇，
   • 對每個點，計算將其移入另一個簇時 I(cos) 的增大量，找出最大增大量，并完成移動，
   • 重復步驟 3 直到達到最大迭代次數，或簇的劃分不再變化，

4. 實作

   在 HanLP 中，聚類演算法實作為 ClusterAnalyzer，用戶可以將其想象為一個檔案 id 到檔案向量的映射容器，

   此處以某音樂網站中的用戶聚類為案例講解聚類模塊的用法，假設該音樂網站將 6 位用戶點播的歌曲的流派記錄下來，并且分別拼接為 6 段文本，給定用戶名稱與這 6 段播放歷史，要求將這 6 位用戶劃分為 3 個簇，實作代碼如下:

   from pyhanlp import *
   
   ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
   
   if __name__ == '__main__':
       analyzer = ClusterAnalyzer()
       analyzer.addDocument("趙一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 藍調, 藍調, 藍調, 藍調, 藍調, 藍調, 搖滾, 搖滾, 搖滾, 搖滾")
       analyzer.addDocument("錢二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
       analyzer.addDocument("張三", "古典, 古典, 古典, 古典, 民謠, 民謠, 民謠, 民謠")
       analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金屬, 金屬, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
       analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 搖滾, 搖滾, 搖滾, 嘻哈, 嘻哈, 嘻哈")
       analyzer.addDocument("馬六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 搖滾")
       print(analyzer.kmeans(3))
   

   結果如下:

   [[李四, 錢二], [王五, 趙一], [張三, 馬六]]
   

   通過 k均值聚類演算法，我們成功的將用戶按興趣分組，獲得了“人以群分”的效果，

   聚類結果中簇的順序是隨機的，每個簇中的元素也是無序的，由于 k均值是個隨機演算法，有小概率得到不同的結果，

   該聚類模塊可以接受任意文本作為檔案，而不需要用特殊分隔符隔開單詞，

10.4 重復二分聚類演算法

1. 基本原理

   重復二分聚類(repeated bisection clustering) 是 k均值演算法的效率加強版，其名稱中的bisection是“二分”的意思，指的是反復對子集進行二分，該演算法的步驟如下:

   • 挑選一個簇進行劃分，
   • 利用 k均值演算法將該簇劃分為 2 個子集，
   • 重復步驟 1 和步驟 2，直到產生足夠舒朗的簇，

   每次產生的簇由上到下形成了一顆二叉樹結構，

   

   正是由于這個性質，重復二分聚類算得上一種基于劃分的層次聚類演算法，如果我們把演算法運行的中間結果存盤起來，就能輸出一棵具有層級關系的樹，樹上每個節點都是一個簇，父子節點對應的簇滿足包含關系，雖然每次劃分都基于 k均值，由于每次二分都僅僅在一個子集上進行，輸人資料少，演算法自然更快，

   在步驟1中，HanLP采用二分后準則函式的增幅最大為策略，每產生一個新簇，都試著將其二分并計算準則函式的增幅，然后對增幅最大的簇執行二分，重復多次直到滿足演算法停止條件，

2. 自動判斷聚類個數k

   讀者可能覺得聚類個數 k 這個超引數很難準確估計，在重復二分聚類演算法中，有一種變通的方法，那就是通過給準則函式的增幅設定閾值 β 來自動判斷 k，此時演算法的停止條件為，當一個簇的二分增幅小于 β 時不再對該簇進行劃分，即認為這個簇已經達到最終狀態，不可再分，當所有簇都不可再分時，演算法終止，最終產生的聚類數量就不再需要人工指定了，

3. 實作

   from pyhanlp import *
   
   ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
   
   if __name__ == '__main__':
       analyzer = ClusterAnalyzer()
       analyzer.addDocument("趙一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 藍調, 藍調, 藍調, 藍調, 藍調, 藍調, 搖滾, 搖滾, 搖滾, 搖滾")
       analyzer.addDocument("錢二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
       analyzer.addDocument("張三", "古典, 古典, 古典, 古典, 民謠, 民謠, 民謠, 民謠")
       analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金屬, 金屬, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
       analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 搖滾, 搖滾, 搖滾, 嘻哈, 嘻哈, 嘻哈")
       analyzer.addDocument("馬六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 搖滾")
   
       print(analyzer.repeatedBisection(3))    # 重復二分聚類
       print(analyzer.repeatedBisection(1.0))  # 自動判斷聚類數量k
   

   運行結果如下:

   [[李四, 錢二], [王五, 趙一], [張三, 馬六]]
   [[李四, 錢二], [王五, 趙一], [張三, 馬六]]
   

   與上面音樂案例得出的結果一致，但運行速度要快不少，

10.5 標準化評測

本次評測選擇搜狗實驗室提供的文本分類語料的一個子集，我稱它為“搜狗文本分類語料庫迷你版”，該迷你版語料庫分為5個類目，每個類目下1000 篇文章，共計5000篇文章，運行代碼如下:

from pyhanlp import *

import zipfile
import os
from pyhanlp.static import download, remove_file, HANLP_DATA_PATH

def test_data_path():
    """
    獲取測驗資料路徑，位于$root/data/test，根目錄由組態檔指定，
    :return:
    """
    data_path = os.path.join(HANLP_DATA_PATH, 'test')
    if not os.path.isdir(data_path):
        os.mkdir(data_path)
    return data_path



## 驗證是否存在 MSR語料庫，如果沒有自動下載
def ensure_data(data_name, data_url):
    root_path = test_data_path()
    dest_path = os.path.join(root_path, data_name)
    if os.path.exists(dest_path):
        return dest_path
    
    if data_url.endswith('.zip'):
        dest_path += '.zip'
    download(data_url, dest_path)
    if data_url.endswith('.zip'):
        with zipfile.ZipFile(dest_path, "r") as archive:
            archive.extractall(root_path)
        remove_file(dest_path)
        dest_path = dest_path[:-len('.zip')]
    return dest_path


sogou_corpus_path = ensure_data('搜狗文本分類語料庫迷你版', 'http://file.hankcs.com/corpus/sogou-text-classification-corpus-mini.zip')


## ===============================================
## 以下開始聚類

ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')

if __name__ == '__main__':
    for algorithm in "kmeans", "repeated bisection":
        print("%s F1=%.2f\n" % (algorithm, ClusterAnalyzer.evaluate(sogou_corpus_path, algorithm) * 100))

運行結果如下:

kmeans F1=83.74

repeated bisection F1=85.58

評測結果如下表:

對比兩種演算法，重復二分聚類不僅準確率比 k均值更高，而且速度是 k均值的 3 倍，然而重復二分聚類成績波動較大，需要多運行幾次才可能得出這樣的結果，

無監督聚類演算法無法學習人類的偏好對檔案進行劃分，也無法學習每個簇在人類那里究竟叫什么，

10.6 GitHub

HanLP何晗--《自然語言處理入門》筆記：

https://github.com/NLP-LOVE/Introduction-NLP

專案持續更新中......

目錄

標籤：其他

上一篇：機器學習演算法總覽

下一篇：OpenCL中讀取image時的坐標