福建省知識產(chǎn)權(quán)信息公共服務(wù)中心 林 俊 黃雄杰 陳 平

?

中文專利文本聚類方法研究*

福建省知識產(chǎn)權(quán)信息公共服務(wù)中心 林 俊 黃雄杰 陳 平

該文提出了一種針對中文專利文本的聚類方法。使用自組織特征映射算法獲得初始的聚類中心，并以此作為K-means算法的初始輸入，從而得到最終的聚類結(jié)果。這樣的組合可以在提高聚類準(zhǔn)確率的同時，降低運行時間。在聚類之前還對文本進(jìn)行LSI降維操作，降低了特征向量的維數(shù)，使得SOM和K-means兩個對維數(shù)敏感的算法可以更加有效和快捷。

K-means SOM LSI 文本聚類 中文專利

0 引言

信息聚類是基于聚類假設(shè)的, 相關(guān)文本之間的相似性比無關(guān)文本之間的相似性更大, 它把一個信息集分成若干稱為簇(cluster) 的子集,每個簇中的文本之間具有較大的相似性, 而簇之間的文本具有較小的相似性。信息聚類是一個非常熱門的問題，它大致分為劃分聚類算法、層次聚類算法、基于密度的聚類算法、基于模型的聚類算法和基于網(wǎng)格的聚類算法以及其他算法等幾大類。但是, 現(xiàn)有的算法中大多數(shù)并不能很好地適應(yīng)于處理專利信息數(shù)據(jù)。只有少部分能被應(yīng)用于處理專利信息。因此需要對現(xiàn)有算法進(jìn)行一定的改進(jìn)才能使之更好地適應(yīng)于專利文本聚類的工作。

1 算法分析

1.1 SOM算法

自組織特征映射（self-organizing feature map, SOM）是最流行的神經(jīng)網(wǎng)絡(luò)聚類分析方法之一，它是由芬蘭神經(jīng)網(wǎng)絡(luò)專家Kohonen 教授1981 年提出的[1]。它是一種無指導(dǎo)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)，自組織的過程實際上就是一種無指導(dǎo)的學(xué)習(xí)。它通過自身訓(xùn)練，自動對輸入模式進(jìn)行聚類。SOM 網(wǎng)絡(luò)中，某個輸出結(jié)點能對某一類模式做出特別的反應(yīng)以代表該模式類。輸出層上相鄰的結(jié)點能對實際模式分布中相近的模式類做出特別的反映，當(dāng)某類數(shù)據(jù)模式輸入時，對某一輸出結(jié)點產(chǎn)生最大刺激(獲勝結(jié)點)，同時對獲勝結(jié)點周圍的一些結(jié)點產(chǎn)生較大刺激。在訓(xùn)練的過程中，不斷對獲勝結(jié)點的連接權(quán)值作調(diào)整，同時對獲勝結(jié)點的鄰域結(jié)點的連接權(quán)值作調(diào)整。隨著訓(xùn)練的進(jìn)行，這個鄰域范圍不斷縮小，直到收斂。SOM算法簡單,不包含復(fù)雜的數(shù)學(xué)運算, 可以很好地用于孤立點問題，但存在收斂時間過長的缺點。

SOM可以看作是k均值聚類的約束版本，其中簇的中心往往處于特征或?qū)傩钥臻g的一個低維流形中。使用SOM，聚類通過若干單元競爭當(dāng)前對象來進(jìn)行。權(quán)重向量最接近當(dāng)前對象的單元成為贏家或活動單元。為了更接近輸入對象，調(diào)整獲勝單元及其最近鄰的權(quán)重，SOM假設(shè)在輸入對象中存在某種拓?fù)浣Y(jié)構(gòu)或序，并且單元將最終呈現(xiàn)空間的這種結(jié)構(gòu)。單元的組織形成一個特征映射。

SOM網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，SOM網(wǎng)絡(luò)由輸入層和輸出層構(gòu)成。網(wǎng)絡(luò)是全連接的，因此每個輸入結(jié)點均與所有的輸出結(jié)點相連接。

圖1 SOM網(wǎng)絡(luò)結(jié)構(gòu)圖

1.2 K-Means算法

K-means算法是硬聚類算法, 是典型的基于原型的目標(biāo)函數(shù)聚類方法的代表, 它是數(shù)據(jù)點到原型(類別中心)的某種距離和作為優(yōu)化的目標(biāo)函數(shù), 利用函數(shù)求極值的方法得到迭代運算的調(diào)整規(guī)則。K-means算法以歐式距離作為相似性測度, 它是求對應(yīng)某一初始聚類中心向量的最優(yōu)分類, 使得評價指標(biāo)值最小。算法常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。但K-means算法存在著固有的缺點:如初始值對聚類結(jié)果影響較大、容易陷入局部最優(yōu)、依賴經(jīng)驗判斷最優(yōu)類的個數(shù)以及對噪音和孤立點數(shù)據(jù)比較敏感, 這些缺陷大大限制了它的應(yīng)用范圍和效果[2]。

1.3 K-means和SOM兩階段聚類算法

將K-Means和SOM結(jié)合起來可以有效解決K-Means對于初始聚類中心選擇困難的問題，同時也能避免SOM收斂時間過長的缺點。K-Means的初始聚類中心將由SOM計算得出。因此SOM不需要迭代至收斂才結(jié)束，而K-Means算法則可以獲得一個很好的初始聚類中心。這樣既保證了一定的聚類準(zhǔn)確率，同時也縮短了算法的運行時間，使得算法可以運用于企業(yè)專利文本的聚類工作[3-4]。

K-means+SOM聚類方法分為兩個階段。第一階段，把待聚類文本輸入SOM中進(jìn)行聚類，這個過程不需要讓SOM完全結(jié)束，只需運行若干代數(shù)，獲得一個初步的聚類結(jié)果即可。在第二階段，把SOM聚類的結(jié)果作為K-means算法的初始聚類中心，進(jìn)行再聚類，并獲得最終的聚類結(jié)果。該聚類組合方法既保持了SOM網(wǎng)絡(luò)自組織的優(yōu)點，又吸收了K-means算法高效率的特點，同時還避免了SOM收斂過慢以及K-means初始聚類中心選擇不佳造成聚類結(jié)果不佳的缺點。

其算法流程如下：

第一步

（1）時間t=0，k=1，迭代次數(shù)iter=1。取第k個樣本。

（2）計算當(dāng)前模式與所有神經(jīng)元的距離

（4）更新每個神經(jīng)元

（5）令t=t+1。如果k

（6）iter=iter+1,如果iter=ITER轉(zhuǎn)至（10）

（8）更新近鄰函數(shù)

（9）轉(zhuǎn)到第三步

（10）把SOM算法獲得的初步聚類結(jié)果作為K-means的初始聚類中心。

（11）遍歷樣本集，將每個樣本指派到距離最近的簇中。

（12）更新聚類中心，即計算每個簇中對象的均值，并把它作為新的聚類中心。

（13）如果準(zhǔn)則函數(shù)還沒有收斂，則轉(zhuǎn)至第二步。

（14）獲得聚類結(jié)果。

衡量樣本之間距離的方法有很多，本文使用的是經(jīng)典的歐氏距離：

準(zhǔn)則函數(shù)采用平方誤差準(zhǔn)則，其定義如下：

2 LSI降維

2.1 潛在語義空間的構(gòu)建

潛在語義索引（Latent Semantic Indexing, LSI）是T.K.Landauer和S.T.Dumais等人提出的一種將文獻(xiàn)信息組織成語義空間結(jié)構(gòu)的方法[4-5]。LSI可以看作是一個特征向量模型的映射，它假設(shè)在文本中有潛在語義結(jié)構(gòu)，它隱藏在文本中詞語的上下文使用模式中。其核心思想是通過對原始文本的文檔—向量矩陣的奇異值分解將文檔向量和詞向量投影到一個低維空間。這樣相互之間有關(guān)系的文本即使沒有相同的詞也可以獲得相同的向量表示。

構(gòu)建詞頻—文檔矩陣：

2.2 潛在語義空間的更新

在已經(jīng)存在的LSI空間中增加新的文檔或者特征項的最直接的方法就是重新計算新的詞頻—文檔矩陣，然后再進(jìn)行SVD。但是實際情況中，這種方法需要消耗大量的時間和內(nèi)存，不適合應(yīng)用到具體的項目中，此必須考慮其他的方法。

3 結(jié)論

本文提出了一種針對專利文本的K-Means+SOM的兩階段聚類方法。首先使用SOM方法迭代若干次（不必獲得最后結(jié)果）得到一個初步的聚類結(jié)果，并在下一階段，將獲得的結(jié)果作為K-Means方法的初始聚類中心。這樣的結(jié)合既克服了SOM收斂過慢的缺點，同時也彌補了K-Means方法獲得聚類結(jié)果對于初始節(jié)點選取依賴大的不足。這樣一種結(jié)合方式不僅提高了聚類的準(zhǔn)確率，同時也提高了算法的運行時間。在聚類之前，使用潛在語義索引進(jìn)行降維，這樣提高了K-means和SOM的兩個對維數(shù)敏感算法的工作效率，進(jìn)一步縮短了算法的運行時間。

[1] Kohonen T. The self-organizing map[J]. Proceedings of the IEEE, 1990, 78(9): 1464-1480.

[2]Han J, Kamber M, Pei J. Data mining: concepts and techniques[M]. Morgan kaufmann, 2006.

[3] Ba??o F, Lobo V, Painho M. Self-organizing maps as substitutes for k-means clustering[M]//Computational Science–ICCS 2005. Springer Berlin Heidelberg, 2005: 476-483.

[4] 楊占華, 楊燕. 一種基于SOM和K-means的文檔聚類算法[J]. 計算機應(yīng)用研究, 2006, 23(5): 73-74.

[5] Deerwester, S., et al, Improving Information Retrieval with Latent Semantic Indexing, Proceedings of the 51st Annual Meeting of the American Society for Information Science 25, 1988：36-40.

[6] 蓋杰，王怡，武港山. 基于潛在語義分析的信息檢索[J].計算機工程,2004,30(2): 58-60.

[7] 居斌. 潛在語義標(biāo)引在中文信息檢索中的研究與實現(xiàn)[J]. 計算機工程，2007(5):193-196

* 福建省科技計劃項目《企業(yè)專利預(yù)警應(yīng)用的混合聚類關(guān)鍵技術(shù)研究》（項目編號：2012H0016）資助。