基于特征聚類的文本信息檢索算法研究

楊宇環， 張開生

(1.陜西科技大學 圖書館信息部， 陜西 西安 710021； 2.陜西科技大學 電氣與控制工程學院， 陜西 西安 710021)

0 引言

隨著網絡通訊、物聯網技術和云計算技術等現代通信和網絡技術的廣泛應用，各種結構化和非結構化數據資源呈現爆發式增長，標志著大數據時代[1]進入一個全新階段.并且文本數據在所有形式的信息資源中占主導地位[2].大量的數據信息是以文本的形式呈現，海量的文本信息作為互聯網信息中的主要表現形式[3]，成為計算機領域和情報領域的重點研究對象.文本信息的查詢、獲取以及有效利用是文本信息檢索、文本數據挖掘、自然語言處理等文本處理技術的最終目標，是其經濟價值和社會價值的重要體現.因此文本處理技術是大數據時代信息利用的關鍵途徑，其中文本信息檢索是文本處理技術的重要基礎和前提，如何在海量文本信息中準確、全面的檢索到讀者需要的信息是文本信息檢索技術發展的關鍵問題和研究熱點.

從文本信息出現起，文本信息的檢索技術就應運而生，成為學者的研究對象.起先是圖書情報領域的專家運用傳統、手工檢索工具進行圖書、期刊等文獻的題錄分類和檢索[4]；隨著計算機技術的產生，出現利用計算機實現聯機檢索技術對文本進行查詢[5-6]；近期隨著人工智能技術的發展，機器學習、深度學習等技術在自然語言處理領域應用，使得文本信息檢索在計算機學科和圖書情報學科協同助力下獲得飛速發展.目前主流的文本信息檢索方法分為三種文本信息挖掘方法，即基于關聯規則挖掘算法、基于語義關系挖掘算法、基于模糊聚類算法[7]，以及基于文本特征提取的文本信息檢索方法[8].隨著人工智能領域機器學習相關技術的發展，基于文本特征提取的文本分類、信息檢索和文本信息挖掘成為自然語言處理技術在文本主題識別和信息挖掘的重要研究方向.其中基于潛在狄利克雷分配LDA模型的文本信息檢索和文本主題識別成為近期研究熱點.LDA模型被用于發掘文獻中蘊含的潛在主題，是挖掘文本潛在語義的一種統計模型[9].研究表明，LDA模型的運用克服了采用特征抽取方法帶來的分類性能受損問題，避免了使用特征濾取方法存在的未考慮詞與詞之間語義聯系的問題[10].但是LDA是一種有監督學習算法，且其可能出現數據過擬合.

針對LDA模型的局限，本文提出一種基于特征聚類的文本信息檢索算法.首先采用主成分分析PCA技術對高維文本信息進行降維，去除文本信息中的冗余數據和噪聲，保留文本信息的主要特征；其次利用K-Means++算法對降維后的文本特征信息進行聚類，實現文本信息的快速檢索.

1 文本特征降維處理

文本信息特征提取是海量數據下文本信息檢索的關鍵步驟.文本數據特征維度高，數據量大，冗余數據多，呈現高維稀疏的特征[11].因此在對文本信息數據進行分詞、停用詞過濾和TFIDF算法構建向量矩陣等預處理后，需要進行文本向量數據的降維處理，實現保留文本分類特征的主要信息，去除掉冗余信息，提高檢索效率.提高信息檢索的速度和準確率的關鍵是文本分類，而文本特征集的降維又是影響文本分類準確率和效率的關鍵步驟.特征選擇和特征抽取是目前主流的特征降維方法.特征選擇是按照既定的規則從原始的特征集合中選擇出一組少量的特征，使用這些特征來有效的表征原始數據[12].特征選擇的統計工具主要有特征頻度(TF)，文檔頻度(DF)，特征熵(Term Entropy)，互信息(MI)，信息增益(IG)，X2統計(CHI).特征選擇的降維效果除依賴訓練數據集合本身的特點，分類器的選擇也會影響分類結果，不同的分類器的降維效果也不盡相同[13].

特征抽取是通過特定的映射函數將高維的原始特征空間變換成一個新的低維特征空間，新的特征能更好的表征原始數據[14].潛在語義標引(LSI)、主成分分析(PCA)是常用的特征抽取方法.潛在語義索引中的奇異值分解方法在用于大規模數據集時通常分解非常困難，同時存在對數據變化敏感、運算速度慢以及左、右奇異矩陣對存儲要求高等缺點[15].主成分分析相對于文本頻度、基于分類頻率的文本頻度和TFIDF降維效果最好[16].同時相對于LDA模型等的有監督算法，主成分分析(Principal Component Analysis，PCA)屬于無監督的機器學習算法，在特征提取過程中不需要分類樣本數據.主成分分析最早是由美國統計學家皮爾遜(Pearson)在研究對空間中的一些點進行最佳擬合直線和平面時，提出了主成分分析的方法[17].PCA的基本思想是將原始的、數量較多的彼此相關的指標用較少數量的彼此無關的綜合指標來代替，同時盡可能的使較少的綜合指標更多的反映原始指標包含的信息[18].通過PCA降維能將原始的高維文本特征矩陣轉換為較低維的正交特征矩陣，此矩陣由原始文本特征矩陣的主成分組成，并盡可能多的保留原始特征矩陣的特征信息[19].PCA可以有效緩解維度災難問題還能夠在降維的同時，使有效信息損失最小化.高維數據降維的核心點在于坐標系的合理建立，假設數據X和前K個主成分如下：

(1)

(2)

PCA算法實現降維的仿真如圖1所示.

圖1 PCA降維仿真圖

2 文本特征聚類算法

文本特征聚類屬于數據挖掘領域的一個重要應用，它的實現原理是依據文本的相似性，將相似性高的文本劃分為一個簇，各個簇之間關聯程度較小，因此可實現文本的快速檢索，從而幫助讀者快速有效地檢索出感興趣的文本信息.

文本聚類方法主要有層次凝聚法、平面劃分法、簡單貝葉斯聚類法、K-最近鄰聚類法、分級聚類法以及基于概念的文本聚類法等[20].聚類算法可以分為兩大類：層次聚類算法和劃分聚類算法[21].層次聚類算法根據給定的距離定義，計算出每兩個對象之間、對象和分組之間以及分組和分組之間的距離，然后按照距離的大小構建一個聚類層次圈.層次聚類法主要分為自底向上和自頂向下兩種聚類算法.層次聚類的主要優點是處理速度快，不需要事先指定聚類個數，但是具有o(n3)的時間復雜度[22].

K-Means算法是一種無監督學習，同時也是基于劃分的聚類算法，K-Means聚類算法是一個不斷迭代的過程[23].K-Means算法的基本思想是，根據參數k，隨機選取k個點作為初始聚類中心，根據每個點與初始聚類中心的距離將所有點劃分為k個簇，以每個簇的質心作為新的聚類中心，不斷地迭代以上的步驟，對簇進行調整，使簇內對象之間的距離盡可能小，而簇間對象之間的距離盡可能大，直至目標函數收斂[24].較好的聚類結果表現為簇內密集，但簇與簇之間具有較為明顯的區分.

綜合分析，本文選擇K-Means算法作為基礎聚類算法，K-Means聚類效果如圖2(a)～(b)所示.

圖2 K-Means算法特征聚類仿真結果圖

但是傳統的K-Means算法依靠隨機選擇確定質心位置，勢必影響聚類結果和運行時間.因此本文參考俞皓芳提出的改進K-Means++算法進行文本聚類[25].

K-Means算法的結果依賴于由初始聚類中心出發所遇到的第一個局部極值點，不同的初始聚類中心很可能導致截然不同的聚類結果.改進K-Means++算法是在K-Means算法的基礎上進行的優化，其步驟為：

Step1首先隨機選擇輸入數據中的一個點作為第一個聚類中心.

Step2計算出數據中所有的點到step1中選取的點的距離.

Step3找出step2中所有距離最小的一個.

Step4依據較大的點被作為聚類中心概率最大的原則，選擇一個新的聚類中心.

Step5不斷重復step2～step4，一直得到K個聚類質心.

Step6利用得到的K個質心執行K-Means算法.

利用改進K-Means++算法得到的每個聚類中心表示一個文本信息的主要特征，將該特征作為聚類樣本，假設將樣本信息記為w，則對w進行聚類后，兩個樣本特征之間的相似度可以表示為：

(3)

式(3)中：n表示文本數據當中總共包含的文本特征數，vi為第i個特征的權重.由此計算文本信息檢索的目標函數記為：

(4)

式(4)中：c為特征類別，將文本信息聚類結果的最小值轉換為求目標函數的最小值.根據拉格朗日法，得到目標函數所要滿足的約束條件，從而求得其最小值.

3 實驗結果與分析

本文在Intel(R) Core(TM)i5-6200U CPU，主頻為2.30 GHz，GPU顯卡為AMD Radeon R5 M315以及4 GB內存配置的Windows7計算機上進行測試.

實驗數據集來源于UCI標準數據庫中下載的flame數據集.UCI數據庫是加州大學歐文分校提出的用于機器學習的數據庫，這個數據庫共有559個數據，實驗采用UCI數據庫下的flame數據集，其中記錄數為240，維度為2，聚類數為2.

檢索準確率和檢索時間是信息檢索、分類、識別、翻譯等領域的重要評價指標.準確率指的是簇劃分正確點的個數與樣本點總個數的比值，用來反映算法的準確程度.檢索時間體現了算法的有效性，在同一個數據集下，檢索時間的縮短能夠減少迭代和加快收斂速度，從而有效提高算法的計算性能.因此本文采用檢索準確率和檢索時間作為本文算法的評價指標，分別與合并聚類和傳統K-Means聚類算法進行對比.其中，合并聚類是屬于層次法，屬于聚類算法的其中一種，主要是對給定的數據集進行層次分解，也是文本聚類當中一種常見的算法.三種算法的檢索準確率對比圖如圖3所示.

由圖3可以看出，本文算法相較于傳統K-Means算法和合并聚類算法檢測準確率得到大幅度提高.可以看出不同算法整體上呈現出檢索準確率隨著文本信息量增大而增大的趨勢.傳統K-Means算法與合并聚類算法整體檢測準確率相當，其中合并聚類算法的檢索準確率略勝一籌.經過改進之后的算法在文本檢索效率方面表現出了良好的效果，準確率基本符合需求.

為了進一步驗證本文算法在文本信息檢索中的有效性，本文統計了三種不同算法檢索時間，結果如表1所示.

表1 不同算法檢索時間

根據表1中的結果可知，本文算法的檢索時間，相較于傳統K-Means算法，時間降低13.3個百分點，相較于合并聚類算法，時間降低25.7個百分點，充分體現本文算法在文本數據檢索方面的優越性.

4 結論

基于文本信息的高維稀疏特征，導致在特征聚類時的信息量過于龐大，使得數據維數過高.本文首先采用主成分分析(PCA)技術對高維文本信息進行降維，去除掉冗余的特征信息，盡可能保留文本的原有特征信息.對K-Means++算法進行了相關分析，K-Means++算法具有較高的運算速率，并且對于數據量較大的情況下，能表現出良好的伸縮性，且K-Means++算法的時間復雜度接近于線性，適合大規模文本數據集挖掘的優點.因此本文將PCA降維和K-Means++算法相結合用于文本信息的檢索，選用檢索準確率和檢索時間兩種算法評價指標進行算法效率評價，將本文算法與傳統K-Means算法與合并聚類算法進行比較，其性能均優于傳統K-Means算法和合并聚類算法，為基于特征提取和特征聚類的文本信息的檢索提供了一種新方法.