使用LSA降維的改進(jìn)ART2神經(jīng)網(wǎng)絡(luò)文本聚類

徐晨凱，高茂庭

上海海事大學(xué) 信息工程學(xué)院，上海 201306

使用LSA降維的改進(jìn)ART2神經(jīng)網(wǎng)絡(luò)文本聚類

徐晨凱，高茂庭

上海海事大學(xué) 信息工程學(xué)院，上海 201306

1 引言

隨著網(wǎng)絡(luò)信息的快速增長(zhǎng)，每天發(fā)布的文本數(shù)量呈指數(shù)級(jí)增長(zhǎng)，提供一種有效的文本組織方式顯得日趨重要，而文本聚類可以對(duì)文本數(shù)據(jù)進(jìn)行較為科學(xué)合理的聚類分析和處理，能夠有效地幫助人們?nèi)カ@取想要的各種信息。

一方面，文本通常采用G.Salton等人提出的向量空間模型[1]（Vector Space Model，VSM）來表示，并通過如TD-IDF算法[2]來提取特征詞的權(quán)重，從而形成文本集的矩陣表示。由于文本中出現(xiàn)的單詞眾多，文本特征矩陣往往表現(xiàn)出巨大的維數(shù)，從而導(dǎo)致維數(shù)災(zāi)難，文本聚類計(jì)算復(fù)雜，一些經(jīng)典統(tǒng)計(jì)算法無法適用等。解決這些問題的一種有效辦法就是先對(duì)數(shù)據(jù)進(jìn)行降維處理。目前，人們已經(jīng)提出了許多降維方法，如：主成分分析PCA、獨(dú)立成分分析ICA、隱含語(yǔ)義分析LSA[3]，其中隱含語(yǔ)義分析LSA根據(jù)矩陣奇異值分解理論達(dá)到快速降維，是一種較為有效的降維方法。

另一方面，為了對(duì)文本數(shù)據(jù)進(jìn)行有效的聚類處理，人們已經(jīng)使用了許多有效的聚類方法，如經(jīng)典的k-means聚類算法[4]、基于SOM神經(jīng)網(wǎng)絡(luò)[5]的文本聚類算法等。但這些方法往往需要大量的先驗(yàn)知識(shí)來確定聚類簇?cái)?shù)目，無法動(dòng)態(tài)學(xué)習(xí)，對(duì)于新向量的學(xué)習(xí)會(huì)影響到已經(jīng)學(xué)習(xí)的向量等問題。而根據(jù)自適應(yīng)共振理論提出的ART2神經(jīng)網(wǎng)絡(luò)[6-8]（簡(jiǎn)稱ART2網(wǎng)絡(luò)）可以有效地動(dòng)態(tài)學(xué)習(xí)，并且實(shí)現(xiàn)記憶和學(xué)習(xí)的平衡，還能自適應(yīng)地確定聚類的數(shù)目。但ART2網(wǎng)絡(luò)依然存在值得改進(jìn)的地方，如對(duì)數(shù)據(jù)的輸入敏感將會(huì)極大影響ART2網(wǎng)絡(luò)的聚類結(jié)果[9-14]。

針對(duì)以上問題，本文提出一種基于最近鄰關(guān)系重組數(shù)據(jù)的改進(jìn)ART2網(wǎng)絡(luò)，在不失動(dòng)態(tài)性的同時(shí)，有效地降低了ART2網(wǎng)絡(luò)對(duì)數(shù)據(jù)輸入的敏感性，并將LSA理論[3]與這種改進(jìn)的ART2網(wǎng)絡(luò)[7-8]相結(jié)合實(shí)現(xiàn)文本聚類。先運(yùn)用LSA理論對(duì)文本特征矩陣進(jìn)行降維處理，再運(yùn)用改進(jìn)后的ART2網(wǎng)絡(luò)進(jìn)行文本聚類。實(shí)驗(yàn)表明，該方法不僅能夠快速對(duì)文本進(jìn)行聚類，準(zhǔn)確度較高，自動(dòng)地確定文本聚類簇?cái)?shù)目，同時(shí)還有效地降低了ART2網(wǎng)絡(luò)對(duì)樣本輸入順序的敏感性。由于常用的聚類距離有歐氏距離和余弦距離等，而在文本聚類中余弦距離往往比歐氏距離有更好的聚類效果[15]，所以本文所使用的距離是余弦距離，并用距離簡(jiǎn)稱。

2 ART2型神經(jīng)網(wǎng)絡(luò)基本原理

2.1 ART2神經(jīng)網(wǎng)絡(luò)模型

本文使用的ART2網(wǎng)絡(luò)結(jié)構(gòu)是文獻(xiàn)[8]中使用的網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。

圖1 ART2神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

ART2神經(jīng)網(wǎng)絡(luò)一般都由注意子系統(tǒng)[7]（Attentional Subsystem）和定向子系統(tǒng)[7]（Orienting Subsystem）兩大部分組成，而注意子系統(tǒng)又包括F0、F1和F2三層。對(duì)于一個(gè)未被歸類的輸入信號(hào)向量I0，通過F0層的放大增益信號(hào)，抑制噪聲，得到處理后的信號(hào)I作為F1層和定向子系統(tǒng)的輸入向量。F1層得到F0層的輸入向量之后，將F0層的輸入向量存儲(chǔ)在F1層的STM中，通過非線性變化函數(shù)抑制噪聲，放大有用信號(hào)，經(jīng)過多次迭代達(dá)到穩(wěn)定后，將所得向量通過F1→F2的LTM，激活F2層的神經(jīng)元并得到勝利神經(jīng)元，勝利神經(jīng)元通過F2→F1的LTM將反饋信息返回給F1層。F1層得到反饋向量后，再次通過非線性變化函數(shù)得到穩(wěn)定的F1層輸出向量輸出到定向子系統(tǒng)。定向子系統(tǒng)得到F0和F1層的輸出向量后，通過距離計(jì)算公式和警戒閾值 ρ，決定是抑制勝利神經(jīng)元，發(fā)出reset信號(hào)，重新進(jìn)行搜索還是讓勝利神經(jīng)元進(jìn)入學(xué)習(xí)階段。

2.2 ART2學(xué)習(xí)方法討論

對(duì)于ART2網(wǎng)絡(luò)，傳統(tǒng)的學(xué)習(xí)方法主要有快速學(xué)習(xí)方法，慢速學(xué)習(xí)方法以及折中學(xué)習(xí)方法。由于在一般常見學(xué)習(xí)方法中，F(xiàn)2→F1的LTM權(quán)值學(xué)習(xí)方法和對(duì)F1→F2的LTM權(quán)值學(xué)習(xí)方法一樣，所以這里只寫出F2→F1的LTM權(quán)值的學(xué)習(xí)方法。

快速學(xué)習(xí)方法公式[7]如下：

其中，J代表勝利神經(jīng)元的編號(hào)，i代表該神經(jīng)元LTM的第i個(gè)分量，k為學(xué)習(xí)次數(shù)，下同。由式（1）可以得出，勝利神經(jīng)元學(xué)習(xí)后的權(quán)值完全只與新輸入的輸入信號(hào)向量相關(guān)，而與之前所學(xué)習(xí)的輸入信號(hào)向量無關(guān)。雖然這種方法可以快速使勝利神經(jīng)元的LTM權(quán)值達(dá)到收斂，但是也導(dǎo)致該勝利神經(jīng)元的LTM在一定程度上受到噪聲的影響[8]。

慢速學(xué)習(xí)方法公式[7]如下：

由式（10）可以得出，慢速學(xué)習(xí)方法是一個(gè)有權(quán)重的學(xué)習(xí)方法，而由于0＜d＜1[7]，所以神經(jīng)元的LTM更偏向于最近學(xué)習(xí)的信號(hào)向量。又由式（10）可得：

因?yàn)閁1向量在 F0層已經(jīng)進(jìn)行了歸一化操作，所以||U1||的值為1，又因?yàn)?＜d＜1[7]，則0＜1-d+d2＜1，隨著k→ +∞，(1-d+d2)k→0，即||ZJ(k)||≤1/(1-d)，由于在F1層凡是小于θ的分量都被去除，而θ≥0，所以往往都有輸入向量距離在0到1之間，則此時(shí)有||ZJ(k)||→1/(1-d)。

折中學(xué)習(xí)方法公式[8]如下：

其中ψ為歸一化運(yùn)算，β為0到1之間的一個(gè)參數(shù)。

由式（1）（10）（11），可以總結(jié)出傳統(tǒng)ART2網(wǎng)絡(luò)的學(xué)習(xí)算法都是非等權(quán)重的學(xué)習(xí)方法。

在許多研究中都使用了一種較為常用的等權(quán)重學(xué)習(xí)方法來減緩向量偏移的問題[10-11]：

其中k為學(xué)習(xí)次數(shù)。由上述可知||ZJ(k)||＜1/(1-d)，但是顯然||ZJ(k)||的值并非是個(gè)定值而是隨著U1，U2，…，Uk之間的夾角變化。該學(xué)習(xí)方法可以算是一種慢速學(xué)習(xí)方法，而文獻(xiàn)[8]中的方法要求每次學(xué)習(xí)完||ZJ(k)||為一個(gè)定值，所以無法利用文獻(xiàn)[8]的原理進(jìn)行步驟上的優(yōu)化。

本文使用的是一種折中學(xué)習(xí)方法：

其中，e→0主要防止除0錯(cuò)誤所以往往取非常小的數(shù)值，在計(jì)算中可以忽略，WJ(k)為額外的一個(gè)向量，由于存放所有歸類在該神經(jīng)元下的向量和。由式（15）可得，由于e→0，則||WJ(k)||可近似看成是1，為一個(gè)恒定值，這就滿足了文獻(xiàn)[8]提出的快速收斂，隨著學(xué)習(xí)又可以調(diào)整的要求。則根據(jù)文獻(xiàn)[8]的方法，由于原距離計(jì)算函數(shù)的主要變量為F2→F1的LTM權(quán)值以及兩個(gè)向量之間的余弦距離，而由式（15）可得，F(xiàn)2→F1的LTM權(quán)值為一個(gè)定值，所以可以將原距離計(jì)算函數(shù)更改為計(jì)算余弦距離，又因?yàn)樵谟?jì)算勝利神經(jīng)元時(shí)，此時(shí)輸入向量U以及F1→F2的LTM權(quán)值都是經(jīng)過歸一化處理之后的向量，所以兩個(gè)向量的內(nèi)積即為其余弦距離，故當(dāng)?shù)谝粋€(gè)勝利神經(jīng)元未滿足閾值ρ，其余神經(jīng)元也定無法滿足閾值 ρ，故可直接建立新神經(jīng)元，從而避免了重新搜索階段，加快了向量的歸類過程并去除了參數(shù)c和d[8]，而ART2網(wǎng)絡(luò)具體運(yùn)算步驟與文獻(xiàn)[8]的一致。

3 基于LSA降維方法

隱含語(yǔ)義分析是一種用于知識(shí)獲取和展示的計(jì)算理論和方法[3]。它主要通過奇異值分解來實(shí)現(xiàn)降維，并因此能夠凸顯出文本特征矩陣向量間隱含的語(yǔ)義特征。

設(shè)W為m×n的詞條-文本矩陣，其中，m為詞條個(gè)數(shù)，n為文本個(gè)數(shù)，則對(duì)于矩陣W，可以進(jìn)行奇異值分解，得到：

其中，U和V矩陣被稱為W的左、右奇異矩陣，Σ為一個(gè)對(duì)角矩陣，對(duì)角線上的每個(gè)元素為W的奇異值，并且按遞減順序排列。通過取前r個(gè)大的奇異值，并將U與V所對(duì)應(yīng)的r個(gè)奇異向量，構(gòu)建W的r-秩近似矩陣Wr：

其中，Ur矩陣中的行向量對(duì)應(yīng)原矩陣W的r個(gè)主要的詞向量，Vr矩陣中的行向量對(duì)應(yīng)原矩陣W的文本向量。

這樣，當(dāng)使用W 文本矩陣進(jìn)行聚類時(shí)，通過計(jì)算WT在Ur矩陣中r個(gè)行向量上的投影從而達(dá)到降維目的，具體變換方法如下：

其中，W*表示的是降維后的文本-詞條矩陣，W表示原詞條-文本矩陣。

4 基于LSA的ART2神經(jīng)網(wǎng)絡(luò)文本聚類

4.1 ART2神經(jīng)網(wǎng)絡(luò)的不足

由于ART2網(wǎng)絡(luò)的神經(jīng)元LTM的初始權(quán)值實(shí)際上是由樣本輸入順序決定的，而初始LTM的權(quán)值又影響神經(jīng)元之間的競(jìng)爭(zhēng)，從而導(dǎo)致ART2網(wǎng)絡(luò)的穩(wěn)定性降低，產(chǎn)生對(duì)輸入樣本順序敏感的現(xiàn)象。

設(shè)有一組平面上的數(shù)據(jù)點(diǎn)，類1的數(shù)據(jù)結(jié)點(diǎn)集為{（cos16°，sin16°），（cos20°，sin20°），（cos24°，sin24°），（cos28°，sin28°），（cos32°，sin32°）}，類2的數(shù)據(jù)結(jié)點(diǎn)集為{（cos45°，sin45°），（cos55，sin55°），（cos65°，sin65°），（cos70°，sin70°）}，如圖2所示，采用k-means算法[4]對(duì)該數(shù)據(jù)進(jìn)行聚類分析可以得到較為理想的聚類結(jié)果。

采用ART2網(wǎng)絡(luò)進(jìn)行聚類，由于數(shù)據(jù)（cos45°，sin45°）和（cos70°，sin70°）的距離為cos25°，若期望ART2網(wǎng)絡(luò)分出同樣聚類效果，則需取到合適的ρ使得數(shù)據(jù)（cos45°，sin45°）和（cos70°，sin70°）能被放入到同一個(gè)類簇，通過計(jì)算可以得到 ρ至少為cos16°，而數(shù)據(jù)（cos45°，sin45°）和（cos32°，sin32°）的余弦距離為cos13°，所以無論如何選取 ρ，只要數(shù)據(jù)（cos45°，sin45°）和（cos70°，sin70°）能歸為同一類簇，那么數(shù)據(jù)（cos45°，sin45°）和（cos32°，sin32°）也顯然可以通過改變順序歸為同一類簇。若此時(shí)數(shù)據(jù)輸入順序?yàn)閧（cos45°，sin45°），（cos32°，sin32°），（cos65°，sin65°），（cos55°，sin55°），（cos70°，sin70°），（cos16°，sin16°），（cos20°，sin20°），（cos24°，sin24°），（cos28°，sin28°）}，則會(huì)出現(xiàn)當(dāng)（cos45°，sin45°）輸入時(shí)，由于學(xué)習(xí)的向量為（cos32°，sin32°），則兩者之間的距離滿足閾值ρ，則此時(shí)出現(xiàn)如圖3情況。

圖2 k-means聚類結(jié)果

圖3 學(xué)習(xí)向量（cos32°，sin32°）后

隨后，對(duì)向量（cos65°，sin65°）進(jìn)行聚類，由于其與由（cos45°，sin45°），（cos32°，sin32°）所組成的類的中心向量的余弦距離均不滿足閾值 ρ，所以將在F2層生成一個(gè)新的神經(jīng)元如圖4情況。

之后，（cos55°，sin55°），（cos70°，sin70°）分布在向量（cos65°，sin65°）兩側(cè)，且距離類2的神經(jīng)元更近且其距離值滿足閾值 ρ，則都分別歸類到類2中。最終當(dāng)所有結(jié)果學(xué)習(xí)完成之后，所得結(jié)果最終聚類結(jié)果如圖5。根據(jù)圖5所示，可以發(fā)現(xiàn)，雖然ART2網(wǎng)絡(luò)最終獲得的聚類簇個(gè)數(shù)比預(yù)期的要多，但是聚類準(zhǔn)確率卻并未提高。而事實(shí)上，若原始數(shù)據(jù)按{（cos45°，sin45°），（cos55°，sin55°），（cos65°，sin65°），（cos70°，sin70°），（cos16°，sin16°），（cos20°，sin20°），（cos24°，sin24°），（cos28°，sin28°），（cos32°，sin32°）}的順序輸入之后，也能得到與k-means聚類結(jié)果一致的聚類結(jié)果。

圖4 學(xué)習(xí)向量（cos65°，sin65°）后

圖5 最終聚類結(jié)果

4.2 原因分析

之所以k-means聚類算法具有比ART2網(wǎng)絡(luò)有更好的聚類結(jié)果，一方面，k-means聚類算法初始中心向量往往是通過一些方法獲取的，而不是簡(jiǎn)單的由順序來決定初始中心向量，從而減弱了對(duì)數(shù)據(jù)輸入順序的依賴；而ART2網(wǎng)絡(luò)的神經(jīng)元初始LTM權(quán)值從本質(zhì)上直接依賴于數(shù)據(jù)的輸入順序，改變數(shù)據(jù)的輸入順序就可能完全改變了ART2網(wǎng)絡(luò)的神經(jīng)元初始LTM權(quán)值，若初始的LTM權(quán)值介于類與類之間，從而導(dǎo)致一些不同類的邊緣元素在競(jìng)爭(zhēng)中以該錯(cuò)誤的神經(jīng)元為勝利神經(jīng)元，又由于是不同類的元素，所以該神經(jīng)元的LTM權(quán)值未必能向某個(gè)類的特征方向收斂，從而導(dǎo)致聚類結(jié)果不佳。另一方面，k-means聚類算法都是初始中心向量個(gè)數(shù)固定，由于真實(shí)的實(shí)際數(shù)據(jù)當(dāng)具有一定數(shù)量之后，不同類的數(shù)據(jù)確實(shí)有不同特征趨勢(shì)的統(tǒng)計(jì)特征，從而使得k-means聚類算法的中心向量向某個(gè)類的特征方向收斂，通過不斷地迭代，從而使中心向量逐漸收斂從而獲得較好的聚類結(jié)果；相反，在ART2網(wǎng)絡(luò)中，若恰好原本具有漂移趨勢(shì)的中心向量由于新的中心向量產(chǎn)生而被取代，從而使得新的中心向量向某個(gè)類的特征中心收斂，而原本的中心向量保持不變，而ART2不會(huì)刪除神經(jīng)元，這樣就導(dǎo)致ART2網(wǎng)絡(luò)無論如何迭代，都無法優(yōu)化聚類結(jié)果，同時(shí)又增加了聚類類別的個(gè)數(shù)。

4.3 改進(jìn)思路

本文根據(jù)實(shí)體對(duì)象往往與其最近鄰實(shí)體對(duì)象更可能是同一類別這一假設(shè)，通過最近鄰關(guān)系來動(dòng)態(tài)地調(diào)整輸入到ART2網(wǎng)絡(luò)中信號(hào)向量的所屬神經(jīng)元，使最終聚類結(jié)果更加穩(wěn)定準(zhǔn)確。

4.4 最近鄰重組步驟

本文為ART2網(wǎng)絡(luò)額外添加一個(gè)最近鄰關(guān)系表，其表內(nèi)每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)輸入信號(hào)量，其中存放當(dāng)前所有輸入信號(hào)向量之間的最近鄰關(guān)系，并且隨著后續(xù)信號(hào)向量輸入動(dòng)態(tài)維護(hù)該表。其主要包含當(dāng)前結(jié)點(diǎn)的最近鄰結(jié)點(diǎn)在表中的位置，與該最近鄰的距離值以及一張鏈表，該鏈表主要存放以當(dāng)前結(jié)點(diǎn)為最近鄰的結(jié)點(diǎn)所在表中位置信息。而維護(hù)過程中需要使用一個(gè)棧和一張表來記錄所要處理的結(jié)點(diǎn)，該表稱為待處理表，棧稱為遍歷棧。具體步驟如下：

步驟1對(duì)新輸入的信號(hào)向量，依次計(jì)算其與之前的信號(hào)向量的距離，若某個(gè)舊信號(hào)向量的最近鄰距離大于新信號(hào)量與該信號(hào)量的距離，則將該信號(hào)量的最近鄰位置更改為新信號(hào)量的位置，其最近鄰值改為與新信號(hào)量的距離值，并將該信號(hào)量位置信息插入到新信號(hào)量的鏈表中。

步驟2通過依次計(jì)算之前所有信號(hào)向量的距離，將所得到新信號(hào)量的最近鄰位置信息及其距離值寫入到新信號(hào)向量的結(jié)點(diǎn)最近鄰關(guān)系表中。

步驟3將新信號(hào)向量的結(jié)點(diǎn)添加到待處理表中，并將該結(jié)點(diǎn)壓入遍歷棧中。

步驟4若棧不空，取出棧頂結(jié)點(diǎn)元素，執(zhí)行步驟6，否則執(zhí)行步驟5。

步驟5依次遍歷所得結(jié)點(diǎn)元素內(nèi)鏈表中的所有結(jié)點(diǎn)，查看鏈表內(nèi)結(jié)點(diǎn)所對(duì)應(yīng)的最近鄰關(guān)系表中的結(jié)點(diǎn)的最近鄰是否為當(dāng)前所得結(jié)點(diǎn)，若是，則將當(dāng)前訪問的鏈表元素放入到待處理表中并將其放入棧中，將其所在的ART2網(wǎng)絡(luò)對(duì)應(yīng)神經(jīng)元的LTM權(quán)重減去其所對(duì)應(yīng)的信號(hào)向量權(quán)重，若不是則將其從該鏈表中刪除，直至訪問完鏈表元素后執(zhí)行步驟4。

步驟6將所得待處理表內(nèi)結(jié)點(diǎn)所對(duì)應(yīng)信號(hào)向量權(quán)值相加，歸一化后作為新的輸入，輸入到ART2網(wǎng)絡(luò)中，將待處理表內(nèi)結(jié)點(diǎn)所對(duì)應(yīng)信號(hào)向量歸到最終滿足閾值ρ的獲勝神經(jīng)元中。

步驟7將新信號(hào)向量所對(duì)應(yīng)結(jié)點(diǎn)插入到其最近鄰所對(duì)應(yīng)結(jié)點(diǎn)的鏈表中，將待處理表清空。

如上例中，當(dāng)向量（cos65°，sin65°）進(jìn)入ART2學(xué)習(xí)之后，雖然此時(shí)的情況如之前未修改的ART2網(wǎng)絡(luò)結(jié)果相同，但是當(dāng)之后的向量（cos55°，sin55°）進(jìn)入學(xué)習(xí)之后，由于向量（cos45°，sin45°）距離（cos55°，sin55°）更近，從而改變了（cos45°，sin45°）的最近鄰，而（cos32°，sin32°）的最近鄰依然是（cos45°，sin45°），所以將（cos32°，sin32°）和（cos45°，sin45°）同時(shí)從原神經(jīng)元中移除，此時(shí)該神經(jīng)元的LTM權(quán)值降為0相當(dāng)于被刪除。而（cos32°，sin32°）和（cos45°，sin45°）與向量（cos55°，sin55°）合并計(jì)算出中心向量作為ART2神經(jīng)網(wǎng)絡(luò)的新輸入進(jìn)行學(xué)習(xí)，顯然此時(shí)網(wǎng)絡(luò)只剩下向量（cos65°，sin65°）所在的神經(jīng)元，并且其距離滿足閾值 ρ。雖然此時(shí)，向量（cos32°，sin32°）被誤分，但是隨著后續(xù)向量的進(jìn)一步學(xué)習(xí)，當(dāng)向量（cos28°，sin28°）進(jìn)入時(shí)，由于此時(shí)（cos32°，sin32°）的最近鄰變成（cos28°，sin28°），從而在原神經(jīng)元中被移除，而（cos45°，sin45°）的最近鄰依然保持不變，故只有（cos32°，sin32°）和（cos28°，sin28°）合并成為新的輸入，輸入到ART2網(wǎng)絡(luò)中，并最終歸到正確的神經(jīng)元中，經(jīng)過改進(jìn)后的ART2網(wǎng)絡(luò)所得聚類結(jié)果與k-means結(jié)果一致，比起未改進(jìn)的ART2網(wǎng)絡(luò)所得聚類結(jié)果更加正確及穩(wěn)定。

4.5 基于LSA的改進(jìn)ART2神經(jīng)網(wǎng)絡(luò)文本聚類步驟

步驟1將所要聚類的文本向量通過投影矩陣，投影到降維后的向量空間中。

步驟2將所得投影后的降維向量輸入到改進(jìn)后的ART2神經(jīng)網(wǎng)絡(luò)中，進(jìn)行歸類與學(xué)習(xí)。

步驟3將在同一個(gè)輸出神經(jīng)元上獲勝的所有輸入文本向量歸為一類，并將此結(jié)果作為最終聚類結(jié)果輸出。

4.6 算法復(fù)雜度分析

在預(yù)處理過程中，將會(huì)使用LSA來獲取用來投影的投影矩陣，其中SVD分解需要花費(fèi)一定時(shí)間，但SVD算法已經(jīng)較為成熟，一般需要O(n3)的時(shí)間復(fù)雜度，但由于該操作只在預(yù)處理過程中進(jìn)行，所以只需要一次獲取投影矩陣即可，故時(shí)間開銷可忽略。

在ART2神經(jīng)網(wǎng)絡(luò)聚類過程中，由于先要維護(hù)最近鄰表，所以需要O(n)的計(jì)算時(shí)間，之后需要抽取出相應(yīng)的最近鄰關(guān)系，這里使用鄰接表數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化，將最近鄰表變成了最近鄰樹從而只需要沿指針遍歷即可，所以問題即為遍歷一棵樹，其時(shí)間復(fù)雜度為O(n)，而對(duì)于一個(gè)新輸入的信號(hào)向量，由于本文無需重新搜索，大大加快了聚類速度，故只需要常數(shù)步定可將一個(gè)信號(hào)向量歸類到一個(gè)神經(jīng)元中，而計(jì)算勝利神經(jīng)元的時(shí)間復(fù)雜度至多為n次，所以最終復(fù)雜度為O(n)，而上述每個(gè)步驟都是順序執(zhí)行，所以對(duì)于一組n個(gè)文本向量的聚類時(shí)間復(fù)雜度為O(n2)。

在空間復(fù)雜度上，由于使用了鄰接表來優(yōu)化時(shí)間并且保存最近鄰關(guān)系，所以其空間復(fù)雜度為O(n2)，而由于最近鄰重組時(shí)需要使用之前輸入的信號(hào)向量，所以需要保存之前的信號(hào)向量，其復(fù)雜度為O(nm)。

5 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的改進(jìn)算法對(duì)于文本聚類的有效性以及對(duì)順序敏感性的減弱，設(shè)計(jì)了3組對(duì)照實(shí)驗(yàn)，實(shí)驗(yàn)文本采用海量公司中文智能分詞產(chǎn)品[17]進(jìn)行預(yù)處理，共5類486篇。實(shí)驗(yàn)1中數(shù)據(jù)按類順序輸入，實(shí)驗(yàn)2改變了樣本的輸入順序，按隨機(jī)順序。實(shí)驗(yàn)3將文本數(shù)據(jù)分兩次輸入，第一次輸入先抽取出286篇文本，并通過LSA計(jì)算得到投影矩陣，降維并進(jìn)行聚類，之后將剩余200篇通過之前得到的投影矩陣降維后，作為第二次輸入進(jìn)行聚類。實(shí)驗(yàn)1主要驗(yàn)證本文算法能夠準(zhǔn)確有效地進(jìn)行聚類分析，通過LSA降維之后，能夠凸顯出語(yǔ)義關(guān)系，減少噪聲，突出最近鄰關(guān)系的準(zhǔn)確性，從而能夠提高聚類結(jié)果的準(zhǔn)確性；實(shí)驗(yàn)2驗(yàn)證本文算法能夠有效地減弱聚類結(jié)果對(duì)樣本輸入順序的敏感；實(shí)驗(yàn)3驗(yàn)證各聚類算法的動(dòng)態(tài)性。

為了衡量算法最終所得聚類結(jié)果的準(zhǔn)確性，本文采用準(zhǔn)確度衡量方法，該方法較為直觀，比較容易理解，計(jì)算方法如下：

p=聚類簇正確數(shù)據(jù)點(diǎn)數(shù)/實(shí)際該類數(shù)據(jù)點(diǎn)總數(shù)

本文采用基于余弦距離的k-means算法[4]、ART2網(wǎng)絡(luò)[8]與本文改進(jìn)算法進(jìn)行對(duì)比，所得實(shí)驗(yàn)結(jié)果如表1所示。本文所使用的ART2網(wǎng)絡(luò)的參數(shù)設(shè)置[12]為a=100，b=100，θ=0.001。

表1 實(shí)驗(yàn)結(jié)果

（1）通過比較聚類算法在未降維和經(jīng)過LSA降維之后的聚類結(jié)果可得，LSA降維之后可以突出潛在文本隱含語(yǔ)義，加強(qiáng)相同聚類簇實(shí)體的相似性及不同聚類簇實(shí)體間的差異，使得聚類分析結(jié)果更加準(zhǔn)確，并且數(shù)據(jù)降維能有效地降低計(jì)算復(fù)雜度，從而加快聚類算法的處理速度。

（2）通過實(shí)驗(yàn)1和實(shí)驗(yàn)2可得，改進(jìn)后的ART2網(wǎng)絡(luò)能大大提高傳統(tǒng)ART2網(wǎng)絡(luò)的穩(wěn)定性及準(zhǔn)確性，并且其準(zhǔn)確性比k-means算法高而穩(wěn)定性與k-means算法相近。由于k-means算法通過全局迭代并以最小二乘方作為評(píng)價(jià)函數(shù)，聚類結(jié)果對(duì)順序的依賴非常小，而由上分析可得數(shù)據(jù)輸入順序直接決定了ART2網(wǎng)絡(luò)的LTM初始值，故其對(duì)數(shù)據(jù)輸入順序的依賴較大，而在引入最近鄰重組后，改進(jìn)的ART2網(wǎng)絡(luò)有效地減弱了對(duì)于輸入順序的依賴。

（3）由實(shí)驗(yàn)3可得，只要在同一個(gè)向量空間的數(shù)據(jù)ART2網(wǎng)絡(luò)以及改進(jìn)后的ART2網(wǎng)絡(luò)都可以在原有基礎(chǔ)上進(jìn)行聚類，而k-means算法無法實(shí)現(xiàn)。由于ART2網(wǎng)絡(luò)及改進(jìn)后的ART2網(wǎng)絡(luò)的聚類分析實(shí)際上是由數(shù)據(jù)與神經(jīng)元之間關(guān)系確定，從而可在原有聚類基礎(chǔ)上進(jìn)行再次聚類，而k-means算法對(duì)新的數(shù)據(jù)需要采用全局迭代過程才能最終確定聚類結(jié)果。

從實(shí)驗(yàn)結(jié)果可以得出，改進(jìn)后的ART2網(wǎng)絡(luò)在聚類結(jié)果的準(zhǔn)確性和穩(wěn)定性均優(yōu)于傳統(tǒng)ART2網(wǎng)絡(luò)的聚類結(jié)果。

6 結(jié)束語(yǔ)

本文研究表明，使用ART2網(wǎng)絡(luò)進(jìn)行文本聚類，能夠有效和動(dòng)態(tài)地對(duì)文本數(shù)據(jù)進(jìn)行聚類分析。但一方面由于文本數(shù)據(jù)的高維性，所以結(jié)合LSA合理地進(jìn)行降維能夠更好地得出聚類結(jié)果，另一方面ART2網(wǎng)絡(luò)為了實(shí)現(xiàn)動(dòng)態(tài)性，在一定程度上犧牲了穩(wěn)定性，所以在低閾值的情況下，表現(xiàn)出對(duì)輸入順序的敏感。本文通過最近鄰關(guān)系重組，在一定程度上改善了這個(gè)問題并且保留了ART2網(wǎng)絡(luò)的高動(dòng)態(tài)性，但仍然有較多的問題遺留等待研究：

（1）由于ART2網(wǎng)絡(luò)能夠自動(dòng)生成聚類個(gè)數(shù)，所以實(shí)現(xiàn)無需估計(jì)聚類個(gè)數(shù)。而ART2網(wǎng)絡(luò)的聚類個(gè)數(shù)主要是由警戒閾值 ρ決定，而如何確定警戒閾值目前還只能通過統(tǒng)計(jì)，或者多次測(cè)試等手段獲取，如何更方便地獲取有效的警戒閾值ρ是一個(gè)值得研究的方向。

（2）由于最近鄰關(guān)系是一種全局關(guān)系，所以能夠在一定程度上確定實(shí)體之間的關(guān)系，而不依賴輸入順序的改變，但是最近鄰關(guān)系并不是一種嚴(yán)格的全局關(guān)系，當(dāng)存在“平局”現(xiàn)象時(shí)，則此時(shí)即使是最近鄰關(guān)系依然依賴輸入順序，所以如何更好地解決這種“平局”現(xiàn)象使實(shí)體之間的關(guān)系更加確定也是一個(gè)需要研究的問題。

（3）LSA理論是一種有效的降維方法，不僅能夠有效減弱原文本-詞條矩陣中包含的“噪聲”因素，使文本和詞條之間的語(yǔ)義關(guān)系更加凸現(xiàn)出來；而且降維后使文本-詞條向量空間大大縮減，減少了數(shù)據(jù)計(jì)算量，從而提高文本聚類的處理效率。但是由于文本間的相互關(guān)聯(lián)性較為復(fù)雜，文本特征的高維性，如何合理地選取文本特征、確定降維規(guī)模、有效地處理文本的多個(gè)主題仍然是一個(gè)值得研究的問題。

[1]Salton G，Wong A，Yang C S.A vector space model for automatic indexing[J].Communications of the ACM，1975，18（11）：613-620.

[2]Salton G，Buckley C.Term-weighting approaches in automatic text retrieval[J].Information Processing and Management，1988，24（5）：513-523.

[3]Landauer T K，F(xiàn)oltz P W，Laham D.An introduction to latent semantic analysis[J].Discourse Processes，1998，25（2/3）：259-284.

[4]Han Jiawei，Kamber M.Data mining：concepts and techniques[M].USA：Morgan Kaufmann，2001.

[5]Kohonen T，Somervuo P.Self-organizing maps of symbol strings[J].Neuro Computing，1998，26（5）：19-30.

[6]Carpenter G A，Grossberg S.A massively parallel architecture for a self-organizing neural pattern recognition machine[J].Computer Vision，Graphics and Image Processing，1987，37（1）：54-115.

[7]Carpenter G A，Grossberg S.ART-2：self-organization of stable category recognition codes for analog input pattern[J].Applied Optics，1987，26（23）：4919-4930.

[8]Carpenter G A，Grossberg S，Rosen D B.ART2-A：an adaptive resonance algorithm for rapid category learning and recognition system[J].Neural Network，1991，4：493-504.

[9]葉曉明，林小竹.慢速權(quán)值更新的ART2神經(jīng)網(wǎng)絡(luò)研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（24）：146-150.

[10]韓小云，劉瑞巖.ART-2網(wǎng)絡(luò)學(xué)習(xí)算法的改進(jìn)[J].數(shù)據(jù)采集與處理，1996，11（4）：241-245.

[11]劉力，胡博，史立峰.ART2神經(jīng)網(wǎng)絡(luò)綜述[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，38（1）：21-26.

[12]諶海霞.ART2網(wǎng)絡(luò)的學(xué)習(xí)速率調(diào)整及其影響[J].微電子學(xué)與計(jì)算機(jī)，2008，25（9）：147-150.

[13]呂秀江，王鵬翔，王德元.基于ART2神經(jīng)網(wǎng)絡(luò)算法改進(jìn)的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（5）：137-139.

[14]顧民，葛良全.一種ART2神經(jīng)網(wǎng)絡(luò)的改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用，2007，27（4）：945-947.

[15]高茂庭，王正歐.基于LSA降維的RPCL文本聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（23）：138-140.

[16]林鴻飛.基于實(shí)例的文本標(biāo)題分類機(jī)制[J].計(jì)算機(jī)研究與發(fā)展，2001，38（9）：1132-1136.

[17]海量公司.中文智能分詞[EB/OL].[2012-12-20].http：//www. hylanda.com/dowmload/segment/.

XU Chenkai,GAO Maoting

College of Information Engineering,Shanghai Maritime University,Shanghai 201306,China

In order to realize dynamic clustering for high-dimensional text data,an improved ART2 neural network text clustering algorithm based on Latent Semantic Analysis（LSA）is proposed,which emerges the semantic relations between texts and terms and reduces the noises,the dimensionality and the computation complexity by LSA.The new algorithm uses an improved intermediate learning method to simplify calculating procedures and accelerate the computation of the ART2 network,and uses the nearest neighbor reformation to improve the stability and weaken the dependence of samples order for the ART2 network clustering.Experiments demonstrate that this improved algorithm can realize dynamic text clustering effectively.

ART2 neural network;nearest neighbor;Latent Semantic Analysis（LSA）;dimensionality reduction;text clustering;clustering analysis

針對(duì)文本數(shù)據(jù)高維度的特點(diǎn)和聚類的動(dòng)態(tài)性要求，結(jié)合隱含語(yǔ)義分析（LSA）降維，提出一種改進(jìn)的ART2神經(jīng)網(wǎng)絡(luò)文本聚類算法，通過LSA凸顯文本和詞條之間的語(yǔ)義關(guān)系，減少無用噪聲，降低數(shù)據(jù)維度和計(jì)算復(fù)雜性；采用改進(jìn)的折中學(xué)習(xí)方法，減少計(jì)算步驟，加快ART2神經(jīng)網(wǎng)絡(luò)計(jì)算速度，并利用最近鄰動(dòng)態(tài)重組方法提高ART2網(wǎng)絡(luò)聚類的穩(wěn)定性，減弱算法對(duì)樣本輸入順序的依賴。實(shí)驗(yàn)表明，改進(jìn)的文本聚類算法能有效地實(shí)現(xiàn)動(dòng)態(tài)文本聚類。

ART2神經(jīng)網(wǎng)絡(luò)；最近鄰；隱含語(yǔ)義分析（LSA）；降維；文本聚類；聚類分析

A

TP183

10.3778/j.issn.1002-8331.1302-0109

XU Chenkai,GAO Maoting.Improved ART2 neural network for text clustering based on LSA.Computer Engineering and Applications,2014,50（24）：133-138.

上海市科委科技創(chuàng)新項(xiàng)目（No.12595810200）；上海海事大學(xué)科研項(xiàng)目（No.201100051）。

徐晨凱（1989—），男，碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域：數(shù)據(jù)挖掘；高茂庭（1963—），男，博士，教授，系統(tǒng)分析員，CCF高級(jí)會(huì)員，主要研究領(lǐng)域：數(shù)據(jù)挖掘，數(shù)據(jù)庫(kù)與信息系統(tǒng)。E-mail：kk9265w@gmail.com

2013-02-20

2013-04-11

1002-8331（2014）24-0133-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-05-13，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130513.1601.002.html