hanlp 词频统计_10.HanLP实现k均值--文本聚类
AI
人工智能
10.HanLP實(shí)現(xiàn)k均值--文本聚類
10. 文本聚類
正所謂物以類聚，人以群分。人們?cè)讷@取數(shù)據(jù)時(shí)需要整理，將相似的數(shù)據(jù)歸檔到一起，自動(dòng)發(fā)現(xiàn)大量樣本之間的相似性，這種根據(jù)相似性歸檔的任務(wù)稱為聚類。
10.1 概述
聚類
聚類(cluster analysis )指的是將給定對(duì)象的集合劃分為不同子集的過(guò)程，目標(biāo)是使得每個(gè)子集內(nèi)部的元素盡量相似，不同子集間的元素盡量不相似。這些子集又被稱為簇(cluster),一般沒有交集。
一般將聚類時(shí)簇的數(shù)量視作由使用者指定的超參數(shù)，雖然存在許多自動(dòng)判斷的算法，但它們往往需要人工指定其他超參數(shù)。
根據(jù)聚類結(jié)果的結(jié)構(gòu)，聚類算法也可以分為劃分式(partitional )和層次化(hierarchieal兩種。劃分聚類的結(jié)果是一系列不相交的子集，而層次聚類的結(jié)果是一棵樹， 葉子節(jié)點(diǎn)是元素，父節(jié)點(diǎn)是簇。本章主要介紹劃分聚類。
文本聚類
文本聚類指的是對(duì)文檔進(jìn)行聚類分析，被廣泛用于文本挖掘和信息檢索領(lǐng)域。
文本聚類的基本流程分為特征提取和向量聚類兩步， 如果能將文檔表示為向量，就可以對(duì)其應(yīng)用聚類算法。這種表示過(guò)程稱為特征提取，而一旦將文檔表示為向量，剩下的算法就與文檔無(wú)關(guān)了。這種抽象思維無(wú)論是從軟件工程的角度，還是從數(shù)學(xué)應(yīng)用的角度都十分簡(jiǎn)潔有效。
10.2 文檔的特征提取
詞袋模型
詞袋(bag-of-words )是信息檢索與自然語(yǔ)言處理中最常用的文檔表示模型，它將文檔想象為一個(gè)裝有詞語(yǔ)的袋子， 通過(guò)袋子中每種詞語(yǔ)的計(jì)數(shù)等統(tǒng)計(jì)量將文檔表示為向量。比如下面的例子:
人 吃 魚。
美味 好 吃！
統(tǒng)計(jì)詞頻后如下:
人=1
吃=2
魚=1
美味=1
好=1
文檔經(jīng)過(guò)該詞袋模型得到的向量表示為[1,2,1,1,1]，這 5 個(gè)維度分別表示這 5 種詞語(yǔ)的詞頻。
一般選取訓(xùn)練集文檔的所有詞語(yǔ)構(gòu)成一個(gè)詞表，詞表之外的詞語(yǔ)稱為 oov，不予考慮。一旦詞表固定下來(lái)，假設(shè)大小為 N。則任何一個(gè)文檔都可以通過(guò)這種方法轉(zhuǎn)換為一個(gè)N維向量。詞袋模型不考慮詞序，也正因?yàn)檫@個(gè)原因，詞袋模型損失了詞序中蘊(yùn)含的語(yǔ)義，比如，對(duì)于詞袋模型來(lái)講，“人吃魚”和“魚吃人”是一樣的，這就不對(duì)了。
不過(guò)目前工業(yè)界已經(jīng)發(fā)展出很好的詞向量表示方法了: word2vec/bert 模型等。
詞袋中的統(tǒng)計(jì)指標(biāo)
詞袋模型并非只是選取詞頻作為統(tǒng)計(jì)指標(biāo)，而是存在許多選項(xiàng)。常見的統(tǒng)計(jì)指標(biāo)如下:
布爾詞頻: 詞頻非零的話截取為1，否則為0，適合長(zhǎng)度較短的數(shù)據(jù)集
TF-IDF: 適合主題較少的數(shù)據(jù)集
詞向量: 如果詞語(yǔ)本身也是某種向量的話，則可以將所有詞語(yǔ)的詞向量求和作為文檔向量。適合處理 OOV 問題嚴(yán)重的數(shù)據(jù)集。
詞頻向量: 適合主題較多的數(shù)據(jù)集
定義由 n 個(gè)文檔組成的集合為 S，定義其中第 i 個(gè)文檔 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 中的出現(xiàn)次數(shù)。為了處理長(zhǎng)度不同的文檔，通常將文檔向量處理為單位向量，即縮放向量使得 ||d||=1。
10.3 k均值算法
一種簡(jiǎn)單實(shí)用的聚類算法是k均值算法(k-means),由Stuart Lloyd于1957年提出。該算法雖然無(wú)法保證一定能夠得到最優(yōu)聚類結(jié)果，但實(shí)踐效果非常好。基于k均值算法衍生出許多改進(jìn)算法，先介紹 k均值算法，然后推導(dǎo)它的一個(gè)變種。
基本原理
形式化啊定義 k均值算法所解決的問題，給定 n 個(gè)向量 d1 到 dn，以及一個(gè)整數(shù) k，要求找出 k 個(gè)簇 S1 到 Sk 以及各自的質(zhì)心 C1 到 Ck，使得下式最小:
[
text { minimize } mathcal{I}_{text {Euclidean }}=sum_{r=1}^{k} sum_{d_{i} in S_{r}}left|boldsymbolze8trgl8bvbq_{i}-boldsymbol{c}_{r}right|^{2}
]
其中 ||di - Cr|| 是向量與質(zhì)心的歐拉距離，I(Euclidean) 稱作聚類的準(zhǔn)則函數(shù)。也就是說(shuō)，k均值以最小化每個(gè)向量到質(zhì)心的歐拉距離的平方和為準(zhǔn)則進(jìn)行聚類，所以該準(zhǔn)則函數(shù)有時(shí)也稱作平方誤差和函數(shù)。而質(zhì)心的計(jì)算就是簇內(nèi)數(shù)據(jù)點(diǎn)的幾何平均:
[
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 內(nèi)所有向量之和，稱作合成向量。
生成 k 個(gè)簇的 k均值算法是一種迭代式算法，每次迭代都在上一步的基礎(chǔ)上優(yōu)化聚類結(jié)果，步驟如下:
選取 k 個(gè)點(diǎn)作為 k 個(gè)簇的初始質(zhì)心。
將所有點(diǎn)分別分配給最近的質(zhì)心所在的簇。
重新計(jì)算每個(gè)簇的質(zhì)心。
重復(fù)步驟 2 和步驟 3 直到質(zhì)心不再發(fā)生變化。
k均值算法雖然無(wú)法保證收斂到全局最優(yōu)，但能夠有效地收斂到一個(gè)局部最優(yōu)點(diǎn)。對(duì)于該算法，初級(jí)讀者重點(diǎn)需要關(guān)注兩個(gè)問題，即初始質(zhì)心的選取和兩點(diǎn)距離的度量。
初始質(zhì)心的選取
由于 k均值不保證收敏到全局最優(yōu)，所以初始質(zhì)心的選取對(duì)k均值的運(yùn)行結(jié)果影響非常大，如果選取不當(dāng)，則可能收斂到一個(gè)較差的局部最優(yōu)點(diǎn)。
一種更高效的方法是， 將質(zhì)心的選取也視作準(zhǔn)則函數(shù)進(jìn)行迭代式優(yōu)化的過(guò)程。其具體做法是，先隨機(jī)選擇第一個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心，視作只有一個(gè)簇計(jì)算準(zhǔn)則函數(shù)。同時(shí)維護(hù)每個(gè)點(diǎn)到最近質(zhì)心的距離的平方，作為一個(gè)映射數(shù)組 M。接著，隨機(jī)取準(zhǔn)則函數(shù)值的一部分記作。遍歷剩下的所有數(shù)據(jù)點(diǎn)，若該點(diǎn)到最近質(zhì)心的距離的平方小于0,則選取該點(diǎn)添加到質(zhì)心列表，同時(shí)更新準(zhǔn)則函數(shù)與 M。如此循環(huán)多次，直至湊足 k 個(gè)初始質(zhì)心。這種方法可行的原理在于，每新增一個(gè)質(zhì)心，都保證了準(zhǔn)則函數(shù)的值下降一個(gè)隨機(jī)比率。 而樸素實(shí)現(xiàn)相當(dāng)于每次新增的質(zhì)心都是完全隨機(jī)的，準(zhǔn)則函數(shù)的增減無(wú)法控制。孰優(yōu)孰劣，一目了然。
考慮到 k均值是一種迭代式的算法， 需要反復(fù)計(jì)算質(zhì)心與兩點(diǎn)距離，這部分計(jì)算通常是效瓶頸。為了改進(jìn)樸素 k均值算法的運(yùn)行效率，HanLP利用種更快的準(zhǔn)則函數(shù)實(shí)現(xiàn)了k均值的變種。
更快的準(zhǔn)則函數(shù)
除了歐拉準(zhǔn)則函數(shù)，還存在一種基于余弦距離的準(zhǔn)則函數(shù):
[
text { maximize } mathcal{I}_{mathrm{cos}}=sum_{r=1}^{k} sum_{d_{i} in S_{r}} cos left(boldsymbolze8trgl8bvbq_{i}, boldsymbol{c}_{r}right)
]
該函數(shù)使用余弦函數(shù)衡量點(diǎn)與質(zhì)心的相似度，目標(biāo)是最大化同簇內(nèi)點(diǎn)與質(zhì)心的相似度。將向量夾角計(jì)算公式代人，該準(zhǔn)則函數(shù)變換為:
[
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|
]
也就是說(shuō)，余弦準(zhǔn)則函數(shù)等于 k 個(gè)簇各自合成向量的長(zhǎng)度之和。比較之前的準(zhǔn)則函數(shù)會(huì)發(fā)現(xiàn)在數(shù)據(jù)點(diǎn)從原簇移動(dòng)到新簇時(shí)，I(Euclidean) 需要重新計(jì)算質(zhì)心，以及兩個(gè)簇內(nèi)所有點(diǎn)到新質(zhì)心的距離。而對(duì)于I(cos)，由于發(fā)生改變的只有原簇和新簇兩個(gè)合成向量，只需求兩者的長(zhǎng)度即可，計(jì)算量一下子減小不少。
基于新準(zhǔn)則函數(shù) I(cos)，k均值變種算法流程如下:
選取 k 個(gè)點(diǎn)作為 k 個(gè)簇的初始質(zhì)心。
將所有點(diǎn)分別分配給最近的質(zhì)心所在的簇。
對(duì)每個(gè)點(diǎn)，計(jì)算將其移入另一個(gè)簇時(shí) I(cos) 的增大量，找出最大增大量，并完成移動(dòng)。
重復(fù)步驟 3 直到達(dá)到最大迭代次數(shù)，或簇的劃分不再變化。
實(shí)現(xiàn)
在 HanLP 中，聚類算法實(shí)現(xiàn)為 ClusterAnalyzer，用戶可以將其想象為一個(gè)文檔 id 到文檔向量的映射容器。
此處以某音樂網(wǎng)站中的用戶聚類為案例講解聚類模塊的用法。假設(shè)該音樂網(wǎng)站將 6 位用戶點(diǎn)播的歌曲的流派記錄下來(lái)，并且分別拼接為 6 段文本。給定用戶名稱與這 6 段播放歷史，要求將這 6 位用戶劃分為 3 個(gè)簇。實(shí)現(xiàn)代碼如下:
from pyhanlp import *
ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
if __name__ == '__main__':
analyzer = ClusterAnalyzer()
analyzer.addDocument("趙一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 搖滾, 搖滾, 搖滾, 搖滾")
analyzer.addDocument("錢二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
analyzer.addDocument("張三", "古典, 古典, 古典, 古典, 民謠, 民謠, 民謠, 民謠")
analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金屬, 金屬, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 搖滾, 搖滾, 搖滾, 嘻哈, 嘻哈, 嘻哈")
analyzer.addDocument("馬六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 搖滾")
print(analyzer.kmeans(3))
結(jié)果如下:
[[李四, 錢二], [王五, 趙一], [張三, 馬六]]
通過(guò) k均值聚類算法，我們成功的將用戶按興趣分組，獲得了“人以群分”的效果。
聚類結(jié)果中簇的順序是隨機(jī)的，每個(gè)簇中的元素也是無(wú)序的，由于 k均值是個(gè)隨機(jī)算法，有小概率得到不同的結(jié)果。
該聚類模塊可以接受任意文本作為文檔，而不需要用特殊分隔符隔開單詞。
10.4 重復(fù)二分聚類算法
基本原理
重復(fù)二分聚類(repeated bisection clustering) 是 k均值算法的效率加強(qiáng)版，其名稱中的bisection是“二分”的意思，指的是反復(fù)對(duì)子集進(jìn)行二分。該算法的步驟如下:
挑選一個(gè)簇進(jìn)行劃分。
利用 k均值算法將該簇劃分為 2 個(gè)子集。
重復(fù)步驟 1 和步驟 2，直到產(chǎn)生足夠舒朗的簇。
每次產(chǎn)生的簇由上到下形成了一顆二叉樹結(jié)構(gòu)。
正是由于這個(gè)性質(zhì)，重復(fù)二分聚類算得上一種基于劃分的層次聚類算法。如果我們把算法運(yùn)行的中間結(jié)果存儲(chǔ)起來(lái)，就能輸出一棵具有層級(jí)關(guān)系的樹。樹上每個(gè)節(jié)點(diǎn)都是一個(gè)簇，父子節(jié)點(diǎn)對(duì)應(yīng)的簇滿足包含關(guān)系。雖然每次劃分都基于 k均值，由于每次二分都僅僅在一個(gè)子集上進(jìn)行，輸人數(shù)據(jù)少，算法自然更快。
在步驟1中，HanLP采用二分后準(zhǔn)則函數(shù)的增幅最大為策略，每產(chǎn)生一個(gè)新簇，都試著將其二分并計(jì)算準(zhǔn)則函數(shù)的增幅。然后對(duì)增幅最大的簇執(zhí)行二分，重復(fù)多次直到滿足算法停止條件。
自動(dòng)判斷聚類個(gè)數(shù)k
讀者可能覺得聚類個(gè)數(shù) k 這個(gè)超參數(shù)很難準(zhǔn)確估計(jì)。在重復(fù)二分聚類算法中，有一種變通的方法，那就是通過(guò)給準(zhǔn)則函數(shù)的增幅設(shè)定閾值 β 來(lái)自動(dòng)判斷 k。此時(shí)算法的停止條件為，當(dāng)一個(gè)簇的二分增幅小于 β 時(shí)不再對(duì)該簇進(jìn)行劃分，即認(rèn)為這個(gè)簇已經(jīng)達(dá)到最終狀態(tài)，不可再分。當(dāng)所有簇都不可再分時(shí)，算法終止，最終產(chǎn)生的聚類數(shù)量就不再需要人工指定了。
實(shí)現(xiàn)
from pyhanlp import *
ClusterAnalyzer = JClass('com.hankcs.hanlp.mining.cluster.ClusterAnalyzer')
if __name__ == '__main__':
analyzer = ClusterAnalyzer()
analyzer.addDocument("趙一", "流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 流行, 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 藍(lán)調(diào), 搖滾, 搖滾, 搖滾, 搖滾")
analyzer.addDocument("錢二", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
analyzer.addDocument("張三", "古典, 古典, 古典, 古典, 民謠, 民謠, 民謠, 民謠")
analyzer.addDocument("李四", "爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 爵士, 金屬, 金屬, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲, 舞曲")
analyzer.addDocument("王五", "流行, 流行, 流行, 流行, 搖滾, 搖滾, 搖滾, 嘻哈, 嘻哈, 嘻哈")
analyzer.addDocument("馬六", "古典, 古典, 古典, 古典, 古典, 古典, 古典, 古典, 搖滾")
print(analyzer.repeatedBisection(3)) # 重復(fù)二分聚類
print(analyzer.repeatedBisection(1.0)) # 自動(dòng)判斷聚類數(shù)量k
運(yùn)行結(jié)果如下:
[[李四, 錢二], [王五, 趙一], [張三, 馬六]]
[[李四, 錢二], [王五, 趙一], [張三, 馬六]]
與上面音樂案例得出的結(jié)果一致，但運(yùn)行速度要快不少。
10.5 標(biāo)準(zhǔn)化評(píng)測(cè)
本次評(píng)測(cè)選擇搜狗實(shí)驗(yàn)室提供的文本分類語(yǔ)料的一個(gè)子集，我稱它為“搜狗文本分類語(yǔ)料庫(kù)迷你版”。該迷你版語(yǔ)料庫(kù)分為5個(gè)類目，每個(gè)類目下1000 篇文章，共計(jì)5000篇文章。運(yùn)行代碼如下:
from pyhanlp import *
import zipfile
import os
from pyhanlp.static import download, remove_file, HANLP_DATA_PATH
def test_data_path():
"""
獲取測(cè)試數(shù)據(jù)路徑，位于$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
## 驗(yàn)證是否存在 MSR語(yǔ)料庫(kù)，如果沒有自動(dòng)下載
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('搜狗文本分類語(yǔ)料庫(kù)迷你版', '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=%.2fn" % (algorithm, ClusterAnalyzer.evaluate(sogou_corpus_path, algorithm) * 100))
運(yùn)行結(jié)果如下:
kmeans F1=83.74
repeated bisection F1=85.58
評(píng)測(cè)結(jié)果如下表:
算法
F1
耗時(shí)k均值
83.74
67秒
重復(fù)二分聚類
85.58
24秒
對(duì)比兩種算法，重復(fù)二分聚類不僅準(zhǔn)確率比 k均值更高，而且速度是 k均值的 3 倍。然而重復(fù)二分聚類成績(jī)波動(dòng)較大，需要多運(yùn)行幾次才可能得出這樣的結(jié)果。
無(wú)監(jiān)督聚類算法無(wú)法學(xué)習(xí)人類的偏好對(duì)文檔進(jìn)行劃分，也無(wú)法學(xué)習(xí)每個(gè)簇在人類那里究竟叫什么。
10.6 GitHub
HanLP何晗--《自然語(yǔ)言處理入門》筆記：
項(xiàng)目持續(xù)更新中......
目錄
內(nèi)容來(lái)源于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系客服刪除
總結(jié)
以上是生活随笔為你收集整理的hanlp 词频统计_10.HanLP实现k均值--文本聚类的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： react 更新input 默认值set
- 下一篇： java中p.name_spring如何