改進的GHSOM算法在文本聚類中的應用

陳 林

(福建中醫藥大學人文與管理學院，福建 福州 350108）

改進的GHSOM算法在文本聚類中的應用

陳 林

(福建中醫藥大學人文與管理學院，福建 福州 350108）

信息時代，文本信息極其巨大。本文運用一種改進GHSOM算法進行文本聚類，該算法具有顯著的文本聚類能力，能夠將文本的相似性用多種手段表現。實驗結果表明改進GHSOM算法整體上是優于SOM算法，它的先進性主要體現在更短的計算時間，并提供更豐富的有序性表達能力。

文本聚類；成長型分級自組織映射；SOM

1 引言

信息時代信息量極大，可以用“信息爆炸”來形容，對信息的查詢、存取、處理都要前期對信息進行分類處理。在浩如煙海的信息中，文本信息占據的比重較大，同時很多其他的信息也可以轉換成文本或者以文本的某種形式體現，而這些信息的處理可以歸結為文本分類問題。如何從這些繁多的文本信息中找到滿足用戶的文本信息是文本挖掘的重要研究內容。利用文本聚類將文本進行自動分類是解決這類問題的重要手段。眾多學者對文本聚類算法進行了研究，取得了很多成果[1～8]。文本聚類的基本思想就是通過計算文本間的相似度，將文本劃分成若干個子類，使得同一子類中文本盡可能相似，而不同子類中的文本盡可能不同。文本聚類已得到廣泛的應用，比如數據挖掘、信息檢索等方面[4]。

本文針對文本聚類問題，提出一種改進的成長型分級自組織映射(Growing Hierarchical Self-organizing Map,GHSOM)算法處理[9～11]。實驗顯示改進的GHSOM算法具有明顯的文本聚類能力，能夠將文本的相似性用多種手段表現。將最相似的文本映射到同一神經元，同一映射相鄰神經元、不同映射間由全局導向作用導致的相鄰也都體現著一定程度的相似性。改進GHSOM算法整體上是優于SOM算法[12～15]，它的先進性主要體現在更短的計算時間，并提供更豐富的有序性表達能力。

2 改進的成長型分級自組織映射(GHSOM)的原理及算法實現

2.1 GHSOM原理

GHSOM是多層分級結構，每一層包含數個獨立的成長型SOM，通過增長規模來在一定詳細程度上描述數據集。表示過分復雜數據的神經元被擴展，在下層形成一個小的成長型SOM，而表示一個相似數據集的單元將不需要進一步擴展。因此，通過它特有的結構與數據固有的分級結構，GHSOM的結果更加反映出它的適應性。

在圖1中給出了GHSOM的典型結構。第一層映射提供輸入數據中主要聚類的粗略組織。在第二層中的六個單獨的SOM提供數據的更詳細的表示。值得注意的是，由于數據結構的不同，映射的規模也不同。第0層為虛擬映射，為成長過程提供服務。

圖1 GHSOM的典型結構

2.2 GHSOM核心算法流程

根據GHSOM的原理，設計了算法的主要步驟如下：

(1)計算第0層單元的量化誤差qe，計算式如下：

其中，C0為映射到第0層單元上的輸入向量集，即為全部向量集；m0代表輸入向量的平均值。

(2)構建第1層映射為2*2個單元的SOM，采用K-means方法對向量權值進行初始化，并設置此網絡為活動網絡，活動網絡層級數為1，訓練數據集為全部數據集[11]。

(3)使用SOM訓練算法訓練活動網絡。

(4)計算活動網絡內所有神經元的量化誤差qei，并根據平均量化誤差MQE定義式：

計算當前網絡的MQEm值。其中，m為活動網絡所在層級數，qei出自數據投射到的映射單元的子集μ。

(5)驗證級內終止條件：MQEm＜τ1·qeu，其中，qeu是相應的上層單元的量化誤差。條件成立時，轉第7步。

(6)選取活動網絡中qe值最大的單元，標記為錯誤單元e。然后按下式得到最相異的鄰居d：d=argmax(‖ ‖me-mi), mi∈Ne，其中Νe是e的鄰居集。在e和d之間插入一行新的單元，重置SOM參數，轉第3步。

(7)對活動網絡單元逐個驗證全局終止條件：qei＜τ2·qe0。發現不滿足條件的單元時，計算該單元四個鄰居的模型向量值，然后構建以此四個向量值為初始值的2*2新映射網絡，并設置新建網絡為活動網絡，層級數加1。將映射在該單元上的數據作為訓練數據，轉第3步。

(8)完成一個活動網絡的驗證時，將此網絡父親單元所在網絡設置為活動網絡，層級數為1時結束。否則，層級數減1，轉第7步。

上述算法步驟僅僅列出了GHSOM網絡的構建和訓練過程，不包含對數據的預處理以及輸入輸出操作。

2.3 GHSOM算法實現的改進

為了完善和改進GHSOM算法，以得到更好的性能，本文提出了以下改進方法：

(1)使用自定義的映射結構和相應的訓練函數。本文中算法實現時GHSOM結構中每一個映射都是由一個SOM網絡結構和其它相關信息組成的結構體表示的，這其中SOM網絡結構包含了在GHSOM算法中并無用處的數據項和函數，使用自定義的映射結構，可以更貼近GHSOM算法中各個函數的需要，這樣不但可以明確映射結構包含的數據項內容，有效防止計算中意外情況的發生(如未使用數據默認值對計算的影響)，而且可以提供以下所有改進意見中對數據結構支持的要求。此處訓練函數指的是一層映射的訓練函數，即是用自定義的函數代替原算法實現中SOM的標準訓練函數。采用自定義的函數的最大好處就是可以充分利用GHSOM的特點，加快訓練時的計算速度。

(2)從算法流程的角度改進，可以將本文中采用的深度優先的結構構建過程改為廣度優先的構建過程。這樣處理需要對訓練過程中的數據保存和內存使用進行合理的安排，否則算法將出現邏輯錯誤。改為廣度優先的構建方法的一個最大優勢在于提供繼續計算功能，即首先設定全局成長參數為比較大的數值，使GHSOM成長過程在聚類精度較粗時暫時停止計算，經過人工檢驗不滿意時，再將全局成長參數設置得更小一些，并以先前計算得到的GHSOM網絡結構為初始繼續進行計算。

(3)根據耗散結構論理論，系統有序結構形成過程中，“負熵流”起到的作用至關重要，而信息即可以看作一種典型的“負熵流”。如在上述GHSOM結構形成過程中，僅僅依靠了程序設置參數的信息和映射中每個神經元權值向量的量化誤差信息。由此可以想到，只要在有序結構的形成過程中提供更多的信息，就可以得到有序程度更高的結構。舉例來說，在上述GHSOM算法中，上層映射向下層映射轉移的過程中，數據樣本向量要進行刪減，在算法中刪減掉的特征值未發揮作用。仔細分析發現，這些刪減掉的特征值實際是對上層映射起到重要作用的特征值，即具有這些特征的數據樣本很可能屬于刪減這些特征的上層映射。如果將刪減信息傳遞給上層映射，并利用此信息對以后的聚類提供導向性信息，則可以加快訓練的速度。

3 輸入文本數據及處理

程序訓練使用的數據集為NSF(The National Science Foundation國家科學基金會)在基礎研究領域授獎情況(1990-2013)的摘要描述文集。每一篇摘要保存為一個文件，這些文件以NSF標準的摘要格式存儲。這些摘要文件集經過名為NSFAbst的文本自動分析器處理，輸出四個文本文件。程序訓練所采用的數據集為docwords.txt文件，其內容與格式如下：

docwords.txt=docid wordid freq (e.g.,1 9792 1)

其中，docid表示摘要文件的被處理時的編號；wordid表示關鍵詞編號，編號從文件word.txt中獲得；freq表示關鍵詞在相應摘要中出現的次數。

算法中，程序用docid代表文本，在聚類效果檢查時，使用idnsfid.txt文件查找得到文本的NSF編號，進行人工聚類效果檢查。

GHSOM算法實現程序要求輸入數據為一個二維數組，其中列向量表示一個個數據樣本。原始的輸入數據樣本集不是滿足這一要求的，因此要對輸入數據進行處理以便滿足程序要求，同時，應該盡量保證更好的訓練效果。

本次實驗所用的數據集文件docwords.txt剛好符合稀疏數組的形式；另外，本數據集每一文本中只包含數百單詞，而作為關鍵詞出現的單詞數目高達數千并接近一萬，最終以向量表示文本時，存在固有的稀疏特性。因此可以使用標準的稀疏數組生成函數來處理輸入數據集文件，得到程序輸入要求的fulldata.mat數據文件。

此時輸入數據的向量表示包含了大量的特征值，即向量長度都很長。數據向量包含的特征值過多時，一方面會增大計算量，也就降低了計算速度；另一方面，由于在算法中每個特征值的權重是相同的，大量對聚類效果不大的特征值的存在，可能會干擾正常的聚類計算。因此，在輸入數據作為訓練數據對網絡進行訓練之前，應該先對輸入數據的特征值進行選擇。

在特征值的選擇上，我們刪減出現概率過高和過低的特征，因為這些特征對聚類的貢獻相對比較小(從信息量角度)。

4 聚類效果及分析

4.1 文本聚類結果

在本文實驗時，訓練數據樣本數目采用100個。由于數據樣本中前14個存在噪音，因此修改程序，取編號101-200的樣本。

刪減樣本向量長度時，采用的特征值概率上下限分別為：0.5和0.03，即僅僅保留在3篇摘要以上、50篇摘要以下出現的特征。經過刪減后，輸入數據樣本轉換為594*100的二維數組。成長參數采用默認值：層內成長參數τ2＝0.15，全局成長參數τ1=0.03，訓練后得到如圖2的分級結構。整個計算過程用時大約為100秒至110秒。

圖2 GHSOM算法得到的文本分級結構

計算得到的GHSOM結構共有三級，第一級為2*4映射，第二級多數為2*3映射，只有2個為2*2映射，第三級只在個別位置出現，絕大多數為2*2映射。整個GHSOM結構中共有70個葉神經元節點(即不再擴展子映射的節點)，其中有10個節點為沒有文本映射在上面的死節點。

為了能夠與普通的SOM算法進行對比，在本次實驗中，還編寫了使用SOM標準算法解決此文本聚類問題的程序。

在使用SOM算法時，將SOM網絡規模定義為7*10(根據GHSOM結果)，并采用與GHSOM相同的迭代次數。SOM整個算法實現就是一系列的命令調用，本文將其全部保存于imsom.m文件。利用與GHSOM中函數visualmap()類似的方法，編寫了SOM聚類結果的圖表輸出函數visualsom()，得到如圖3的聚類結果圖表。

圖3 SOM算法得到的文本聚類

使用SOM算法進行訓練時，使用與上面GHSOM算法時相同的訓練數據，最終計算時間大約為160秒至170秒。

4.2 聚類效果分析

由于是進行的文本聚類計算，沒有期望的分類對計算的結果進行定量的檢驗。本次實驗在檢驗聚類結果時，將程序運行所用數據調出，由人工定性檢查GHSOM網絡的聚類效果。

在檢驗聚類結果之前，先規定每一映射中神經元的編號。由于分級結構的存在，低層級中神經元的編號中包含其父親神經元的編號，不同層級間用→隔開。同一映射中，神經元的編號自左下向右上依次編號為1、2、……，如圖4。

圖4 神經元編號

按此編號方法，GHSOM分級結構中，左下角包含61的神經元編號為[1→1]，包含52的神經元編號為[1→3→4]，右上角包含99的神經元編號為[8→6→4]。

觀察分級映射的左上角[7→4]，有三個文本(14 15 21)聚類為一類，為2級映射神經元，這三篇摘要實際上是針對同一個獎項的摘要。此映射下面有四個3級映射神經元(由神經元[7→2]擴展得到)，代表的四篇摘要均是關于大學內的計算機相關系統，但是具體內容有所差別。由此看來，盡管[7→4]、[7→2]兩個神經元相鄰，它們代表的摘要內容相似性卻很差，造成這種情況的原因主要是因為[7→4]代表的內容過于特別，而沒有與之相似的文本。

神經元[1→4]內容為北太平洋新生代板塊模型和馬爾代夫周圍環境和沉積物研究，均屬于地殼研究內容；它的右邊神經元[1→5]內容為東太平洋的地震攝影術研究，也涉及地殼研究內容；它的上面神經元[3→1]則是關于大氣層熱量與紫外線研究，與地殼研究相關性不大。由此可以看出，同一映射下相鄰關系鄰近度要高于全局導向的鄰近度。神經元[1→1]內容為海洋生態系統中捕食者間的相互作用研究，它的右側[1→2]內容為海洋漂流物研究和海洋表面水域的研究，這兩個神經元間內容相似性較強，但是與神經元[1→4]的相似性僅僅體現在研究領域中均出現了太平洋。由此可以看出，GHSOM算法也可能導致專斷的劃分，即將兩個相似程度不高的兩類強行聚類成相鄰關系。

神經元[4]擴展成的映射包含密度最大的文本，神經元[4→1]包括的內容有DNA變異研究、幾何變形容忍、機械加工容忍、機器人動作計劃，這四篇文章雖然研究領域各異，但主要內容均是從幾何學出發，說明聚類算法是一種按內容分類的方法。向右方，神經元[4→2→1]為機器人任務分派算法，神經元[4→2→3]為隨機網絡產量優化算法，這都是數學問題。向上方，神經元[4→3]是關于物理學中表面現象的研究，再向上，神經元[4→5]都是幾何學在特殊領域中的應用。而它們的右邊，有的文本聚類的結果并不理想，文本37、78都涉及了地殼的內容，即與主要研究地殼的左下角神經元相距較遠。因此，GHSOM算法依然存在相似聚類間聯系丟失的問題。

綜上所述，GHSOM算法具有明顯的文本聚類能力，能夠將文本的相似性用多種手段表現。將最相似的文本映射到同一神經元，同一映射相鄰神經元、不同映射間由全局導向作用導致的相鄰也都體現著一定程度的相似性。不同級別的映射也體現了不同程度的相似性，低級別的相鄰神經元體現了更高的相似性，如3級神經元相鄰的相似性要高于2級相鄰。GHSOM算法也存在問題，首先是對于獨特的文本，算法會專斷地將其與某類文本相鄰。這個問題更可能出現在少量文本聚類問題中，因為在海量文本中不會出現“獨特”的文本。其次，GHSOM表現相似性能力只能以樹型方式，比起網絡狀還有一定差距，因此會造成部分子聚類間聯系無法體現。

與SOM算法對比，SOM算法在已經知道合適的網絡(70)的情況下，它的計算時間也要長于GHSOM算法，并且產生了更多的死節點(17)，因此在計算性能上，GHSOM算法要優于SOM。

聚類效果方面，SOM表現相似性的手段比GHSOM少，只有一種相鄰性來體現。SOM算法中，文本35、40、41、50的分別比較接近的神經元中，并且也與文本23、53、66映射的神經元相鄰，體現了GHSOM中神經元[7→1]、[7→2]對相似性的體現，但是，SOM算法中相似級別只有一種，而GHSOM中在此處的相似級別有兩種。

關于地殼相關文本，SOM算法將原來GHSOM算法中[1→4]和[3→1]映射到了右下角，而對于GHSOM中海洋相關的研究[1→1]和[1→2]的文本也專斷的進行了映射。對于GHSOM算法中密度最大的文本映射，SOM算法將這些文本映射在了網絡的中部偏右的位置，特別注意的是，在GHSOM算法中未能體現出來的文本37、78與地殼研究相關性，在SOM中得到了一定的體現，這兩個文本映射在了接近右下角(地殼研究內容)的位置。出現這種情況，并不能說明SOM有更好的有序性表達能力，只是算法中隨機性的一種體現。

因此，GHSOM算法整體上是優于SOM算法的，它的先進性主要體現在更短的計算時間，并提供更豐富的有序性表達能力。

5 結束語

實現的改進GHSOM算法在文本聚類領域中的應用體現了自組織性：在毫無教師信號的前提下，自動將文本分成了不同的類別，并用不同映射神經元的相鄰關系顯示了文本的相似性。文本的相似性表現手段也是多樣的：映射到同一神經元的文本具有最高的相似性，同一映射神經元的相鄰、不同映射間由全局導向作用導致的相鄰也都體現了一定程度的相似性；不同級別映射神經元相鄰也體現了不同程度的相似性，低級別的相鄰神經元體現了更高的相似性，如3級神經元相鄰的相似性要高于2級相鄰。改進GHSOM算法整體上是優于SOM算法，它的先進性主要體現在更短的計算時間，并提供更豐富的有序性表達能力。

[1]MAHDAVI M，ABOLHASSANI H．Harmony K-means algorithm for document clustering[J]．Data Mining and Knowledge Discovery，2009，18(3)：370-391．

[2]徐森，盧志茂，顧國昌．解決文本聚類集成問題的兩個譜算法[J]．自動化學報，2009，35(7)：997-1002．

[3]ZHENG Hai-tao，KANG B Y，KIM H G．Exploiting noun phrases and semantic relationships for text document clustering[J]．Information Sciences，2009，179(13)：2249-2262．

[4]趙衛中，馬慧芳，李志清，等．一種結合主動學習的半監督文檔聚類算法[J]．軟件學報，2012，23(6)：1486-1499．

[5]BASAVAＲAJU M，PＲABHAKAＲ Ｒ．A novel method of spam mail detection using text based clustering approach[J]．International Journal of Computer Applications，2010，5(4)：15-25．

[6]卜東波，白碩，李國杰．文本聚類中權重計算的對偶性策略[J]．軟件學報，2002，13(11)：2083-2090．

[7]趙軍，金千里，徐波．面向文本檢索的語義計算[J]．計算機學報，2005，28(12)：2068-2078．

[8]管仁初，裴志利，時小虎，等．權吸引子傳播算法及其在文本聚類中的應用[J]．計算機研究與發展，2010，47(10)：1733－1740．

[9]Rauber A，Merkl D，Dittenbach M．The Growing Hierarchical Self-organizing Map：Exploratory Analysis of High-dimensional Data[J]．IEEE Transactions on Neural Networks，2002，13(6)：1331-1341．

[10]Yen G G，Wu Zheng．Ranked centroid projection：A data visualization approach with self-organizing maps[J]．IEEE Transactions on Neural Networks，2008，19(2)：245-259．

[11]Alahakoon D，Halgarmuge S K，Srinivasan B．Dynamic self-organizing maps with controlled growth for knowledge discovery[J]．IEEE Transactions on Neural Network，2000，11(3)：601-614．

[12]譚長貴，動態平衡態勢論研究——一種自組織系統有序演化新范式，電子科技大學出版社，2004．

[13]Kohonen T．Self-organizing Maps[M]．Berlin：Springer，2001．

[14]Kohonen T，Ritter H．Self-organizing semantic maps[J]．Biological Cybernetics，1989，61(4)：241-254．

[15]Yen G G，Wu Zheng．Ranked centroid projection：A data visualization approach with self-organizing maps[J]．IEEE Transactions on Neural Networks，2008，19(2)：245-259．

An Improved GHSOM Algorithm for Text Clustering

Chen Lin
(Fujian University of Traditional Chinese Medicine,Fuzhou 350108,Fujian)

In the information era,the text information is very great.An improved GHSOM algorithm for text clustering is presented in this paper.This algorithm which has obvious text clustering ability can use a variety of means to show the similarity of text.The experimental results show that the improved GHSOM algorithm is better than SOM algorithm on the whole,and its advanced nature is mainly reflected in the shorter computation time and more expression.

text clustering;growing hierarchical self-organizing map;SOM

TP181

A

1008-6609(2016)05-0057-05

陳林，男，福建福州人，碩士，助教，研究方向：計算機應用與軟件，信息管理。