王安瑾

(東華大學 計算機科學與技術(shù)學院，上海 200000)

0 引 言

隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)新聞中文本數(shù)量日益增多，每天用戶面臨的各個網(wǎng)站的新聞可以用數(shù)以萬計來形容。出于用戶對不同新聞的需求，近似新聞文本聚類已經(jīng)是目前數(shù)據(jù)處理的一個重要研究課題。傳統(tǒng)的文本聚類比如向量空間模型(vector space model，VSM[1])，一般是使用TF-IDF(term frequency-inverse document frequency)[2]提取出文本中的特征詞，然后通過對特征詞進行加權(quán)處理，用一個權(quán)重向量表示文本[3]，構(gòu)建特征詞文本矩陣來進行聚類。但由于特征詞權(quán)重向量維度高，且數(shù)據(jù)較為稀疏，因此利用向量空間模型進行文本聚類經(jīng)常會占用很大內(nèi)存且聚類速度慢。由Blei等[4]于2003年提出的基于貝葉斯模型的潛在狄利克雷分配(latent Dirichlet allocation，LDA)以概率分布的形式給出文檔集中每篇文檔的主題，通過分析文檔的主題來進行主題聚類，這種聚類適用于大規(guī)模文本聚類，但是缺點也很明顯，降維后維度太低，容易破壞文檔的完整性[5]。因此，文中提出一種基于MinHash[6]的文本聚類方法。

現(xiàn)有的聚類方法主要有以下幾類：

基于劃分的聚類算法，如K-means[7]算法，一般通過給定K值，將N個待聚類樣本構(gòu)造成K個分組，每個分組就是一個聚類。算法通過反復迭代的方法使得同一分組中的記錄盡可能近，而不同分組中的記錄盡可能遠。

基于密度的聚類算法，如DBSCAN[8]算法，該類算法中各個類別是通過樣本分布的緊密程度決定的，同屬于一個類別的樣本之間緊密度較大，而與不同類別的樣本之間聯(lián)系較為疏松。只要某個區(qū)域中存在距離小于某個閾值的點，且該點周圍的密度大過某個值，便能形成一個簇，從而實現(xiàn)聚類。

基于層次的聚類算法，如BIRCH[9]算法，顧名思義，該類算法對給定的數(shù)據(jù)集一層一層進行聚類，通過迭代的方法創(chuàng)建一棵分層的聚類樹。層次聚類可分為自底向上的凝聚聚類和自頂向下的分裂聚類。

文中采用的是基于密度的聚類算法DBSCAN，相比其他聚類算法，該算法優(yōu)點為無需給定最終聚類的個數(shù)，可以發(fā)現(xiàn)任意形狀的簇且處理噪聲能力強。

1 MinHash

1.1 Jaccard系數(shù)

Jaccard系數(shù)[10]是衡量兩個文本之間相似度的系數(shù)。Jaccard系數(shù)的定義為：給定集合A和集合B，A、B中共有的元素個數(shù)占A、B總元素個數(shù)的比重即為A與B的Jaccard相似系數(shù)。即

Jaccard(A,B)=|A∩B|/|A∪B|

該系數(shù)的值域為0至1，系數(shù)越接近1，兩個文本之間的相似度越高。

1.2 MinHash算法

MinHash(最小哈希)是局部敏感哈希算法(locality-sensitive hashing，LSH)[11]的一種，局部敏感哈希是適用于大規(guī)模高維度數(shù)據(jù)的一種快速最近鄰查找(nearest neighbor search)[12]算法，其實質(zhì)是基于一種假設(shè)，相似度很高的兩個數(shù)據(jù)映射成同一個hash值的概率較大，而相似度很低的兩個數(shù)據(jù)則很難映射成同一個hash值。

MinHash的原理[13]為，假設(shè)存在集合A、B，將集合A、B中的元素經(jīng)過哈希函數(shù)哈希之后，如果其中具有最小哈希值的元素既在A∪B中也在A∩B中，那么hmin(A)=hmin(B)，集合A和B的相似度就可以表示為集合A、B的最小哈希值相等的概率，即：

J(A,B)=Pr[hmin(A)=hmin(B)]

MinHash算法用于文本聚類的一般流程是，先將提取到的特征值向量和文檔組成矩陣，通過多個哈希函數(shù)將特征值向量矩陣哈希成“簽名矩陣(signature matrix)”，簽名矩陣中的數(shù)據(jù)都是降維后的結(jié)果，然后將該矩陣中的行號進行隨機變換并排列，取出某一文檔對應的列中排在最前面的1，“1”對應的單詞可以代表該文檔，經(jīng)過多次哈希隨機變換就可以選取出多個特征值來代表這個文檔。從而對文檔實現(xiàn)了降維，高維度的文檔被壓縮為n個整數(shù)表示。然后計算兩兩文檔之間的Jaccard系數(shù)即可算出文檔之間的相似度。

牛養(yǎng)殖業(yè)尚處于發(fā)展階段，但為人們的生活帶來較大的改變，逐漸使人們奔向小康社會。但養(yǎng)殖中常會出現(xiàn)各種疾病，尤其是結(jié)核病，該病屬于人畜共患的疾病，不僅要密切關(guān)注牛的身體狀況還要對工作人員的身體狀況進行觀察，一旦發(fā)現(xiàn)結(jié)核病，應該立即隔離治療，減少病菌的感染。同時，對病牛的飼養(yǎng)環(huán)境、糞便等進行有效的消毒以及處理，徹底消滅病菌，促進牛養(yǎng)殖業(yè)的健康發(fā)展。養(yǎng)殖戶在飼養(yǎng)中需要明確結(jié)核病的臨床癥狀、診斷方式、處理方法以及向有關(guān)部門報告，做到及時發(fā)現(xiàn)、及時隔離處理，減少對健康?；蛘呷说膫魅?，減少經(jīng)濟損失。

2 DBSCAN

DBSCAN(density-based spatial clustering of application with noise)是一種基于密度的聚類算法。該算法中各個類別是通過樣本分布的緊密程度決定的，同屬于一個類別的樣本之間緊密度較大，而與不同類別的樣本之間聯(lián)系較為疏松。通過選取核心點，將與其聯(lián)系緊密的樣本歸為一類，就形成了樣本的其中一個聚類，通過對多個核心點的劃分，形成圍繞這些核心點的多個聚類類別就完成了一次數(shù)據(jù)聚類。該算法的特點是聚類速度快，不需人為設(shè)定聚類后簇的個數(shù)且可以發(fā)現(xiàn)空間中任意形狀的簇。

在DBSCAN中樣本集的緊密程度是通過鄰域反映的。該算法有兩個重要的參數(shù)，即鄰域半徑Eps以及形成一個簇所需要的最小點數(shù)MinPts[14]。

假設(shè)輸入數(shù)據(jù)集是D=(x1,x2,…,xm),則得知：

(1)半徑鄰域：對于數(shù)據(jù)集D中的任意一個樣本數(shù)據(jù)，假設(shè)xi∈D，如果存在另一個樣本數(shù)據(jù)xj∈D，可以使得其與xi之間的距離小于等于半徑Eps，即Nε(xi)={xj∈D|distance(xi,xj)≤Eps}，則稱其為xi的半徑鄰域，或ε鄰域。所有在xi的半徑鄰域中的點構(gòu)成了一個子樣本集，該樣本集中的個數(shù)為xi的密度，記為ρ(xi)=|Nε(xi)|。

(2)核心點：若存在某一樣本xi∈D，且在其鄰域半徑Eps內(nèi)至少包含MinPts個樣本，即ρ(xi)≥MinPts，則xi是一個核心點。

(3)邊界點：若存在某一樣本xi∈D，且在其鄰域半徑Eps內(nèi)點的數(shù)量小于MinPts，即ρ(xi)

(4)噪音點：數(shù)據(jù)集D中既不是核心點也不是邊界點的點則為噪音點。

(5)密度直達：假設(shè)xi為核心點，如果xj位于xi鄰域內(nèi)，即xj∈Nε(xi)，則稱xj由xi直接密度可達。

(7)密度相連：對于xi∈D和xj∈D,如果xi，xj均是由核心點xk密度可達的，則稱xi和xj密度相連。密度相連滿足對稱性。

其算法具體過程如下：

初始化核心點集和結(jié)果集，標記所有樣本為未訪問。遍歷樣本，確定每個樣本鄰域Nε(xi)并判斷該樣本鄰域密度ρ(xi)是否大于等于MinPts，若是，將該樣本加入核心點集合。選取任意一個核心點q，將其標記為已訪問，如果該點ε鄰域內(nèi)至少有MinPts個樣本，則新建一個簇C，并將q加入C中。對于核心點q鄰域Nε(q)內(nèi)樣本集合中的任意一個點qi，如果該點未訪問，則標記為已訪問，判斷其鄰域內(nèi)點的數(shù)量是否大于等于MinPts，若是，則將這些樣本添加到Nε(q)中。如果qi還不是任何簇的成員，則將其加入到C中。重復上述步驟，直到所有核心點均被訪問過。

3 基于MinHash的改進DBSCAN聚類算法

新聞文本有一個鮮明特征，不同題材新聞之間的關(guān)鍵詞基本不相同,而同類新聞關(guān)鍵詞相似度較大。這個特點決定了利用Jaccard系數(shù)來判斷兩個新聞文本之間的相似度是個不錯的選擇。因此，文中提出了基于MinHash的DBSCAN新聞文本聚類算法。MinHash是基于Jaccard相似系數(shù)的局部哈希算法，適用于文本聚類，該算法結(jié)合了MinHash算法和DBSCAN算法的優(yōu)點，實現(xiàn)了將高維文檔轉(zhuǎn)化為低維數(shù)據(jù)并將相似文檔進行聚類的功能。

3.1 文本處理

對于給定的文本集D={d1,d2,…,dn}，對集合中所有文檔依次進行讀取并分詞。去除“你”、“我”、“日”、“的”等常用停用詞并按照所得分詞的權(quán)重大小提取該文檔的關(guān)鍵詞集合K={k1,k2,…,km},其中m≥10,即只有由10個以上的關(guān)鍵詞組成的新聞文本才認為是有效的文本。

3.2 對關(guān)鍵詞組進行降維

得到文本關(guān)鍵詞之后構(gòu)建一個文本-關(guān)鍵詞矩陣，矩陣的行代表關(guān)鍵詞，列代表文檔，若關(guān)鍵詞i在文檔中j出現(xiàn)，則將該矩陣中i行j列標記為1，否則為0，這樣就可以得到一個稀疏的特征矩陣。通過多個hash函數(shù)將特征矩陣的所有行進行映射，如果該行當前值為0，跳過，如果為1，取哈希值與原始值之間的最小值來構(gòu)造一個簽名矩陣，從而實現(xiàn)對特征矩陣的壓縮。

3.3 DBSCAN文本聚類

將降維之后的矩陣作為DBSCAN聚類算法的輸入集，對于矩陣中的每一列，即文本的特征哈希集合分別兩兩計算它們的Jaccard系數(shù)，并與給定的閾值Eps進行比較，并判斷該點周圍所有與其距離大于閾值的點的個數(shù)是否大于MinPts。如果某一點與其他任一點的Jaccard系數(shù)大于Eps且其周圍與它的Jaccard系數(shù)大于Eps的點的個數(shù)大于或等于MinPts，則該點為核心點，與核心點密度可達的所有點均為一類，否則，為另一類別或噪音點。算法流程如圖1所示。

圖1 算法流程

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)

所用的實驗數(shù)據(jù)是來自復旦大學計算機信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組的中文文本語料庫，共包含350篇新聞，分為藝術(shù)、體育、經(jīng)濟、計算機、環(huán)境五個大類，各個類別的新聞篇數(shù)為70篇，如表1所示。

表1 復旦大學中文文本語料庫

4.2 結(jié)果分析

由于鄰域半徑Eps對聚類效果有一定的影響，于是經(jīng)過多次實驗對聚類結(jié)果進行比較觀察最佳Eps參數(shù)。最后確定了在周圍最小點數(shù)MinPts取15時，文中算法能得到較好的聚類效果。當MinPts=15時，不同鄰域半徑下聚類的準確率如圖2所示。

在文本聚類算法中，經(jīng)常使用以下評估方法對算法進行評估。

準確率=正確識別出的文本數(shù)目/識別出的文本總數(shù)

召回率=正確識別出的文本總數(shù)/語料庫中的文本總數(shù)

F值(F-Measure)=(2×正確率×召回率)/(正確率+召回率)

圖2 不同鄰域半徑下聚類的準確率

通過文中算法，對上述350個近似新聞文本進行聚類后得到如下結(jié)果，見表2。

表2 聚類結(jié)果

從表2可以得知，基于MinHash的DBSCAN聚類算法對于新聞文本有著不錯的聚類效果，準確率和召回率分別為0.93、0.81，平均F值達到0.86。圖3為文中聚類算法與其他傳統(tǒng)文本聚類算法(VSM、LDA)的評價指標比對情況，可見，相比于傳統(tǒng)的新聞文本聚類算法，文中算法具有更高的準確率和召回率。

圖3 不同算法的評價指標對比

5 結(jié)束語

文中提出的基于MinHash的文本聚類算法是基于不同類型新聞文本特征詞不同的特點提出的，利用MinHash算法對表示新聞文本的特征詞進行降維，從而減少內(nèi)存的消耗以及加快聚類速度，而利用DBSCAN算法不需事先指定簇的個數(shù)，可以發(fā)現(xiàn)任意形狀的類別，兩種算法結(jié)合對于新聞文本聚類有著很好的效果。由于實驗所使用的文本集數(shù)量不多，所以在今后的實驗中將進行大數(shù)據(jù)新聞文本的聚類研究，并結(jié)合Shingling[15]算法提升聚類的效果。