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

楊宇環(huán)， 張開生

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

0 引言

隨著網(wǎng)絡(luò)通訊、物聯(lián)網(wǎng)技術(shù)和云計(jì)算技術(shù)等現(xiàn)代通信和網(wǎng)絡(luò)技術(shù)的廣泛應(yīng)用，各種結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)資源呈現(xiàn)爆發(fā)式增長，標(biāo)志著大數(shù)據(jù)時(shí)代[1]進(jìn)入一個(gè)全新階段.并且文本數(shù)據(jù)在所有形式的信息資源中占主導(dǎo)地位[2].大量的數(shù)據(jù)信息是以文本的形式呈現(xiàn)，海量的文本信息作為互聯(lián)網(wǎng)信息中的主要表現(xiàn)形式[3]，成為計(jì)算機(jī)領(lǐng)域和情報(bào)領(lǐng)域的重點(diǎn)研究對象.文本信息的查詢、獲取以及有效利用是文本信息檢索、文本數(shù)據(jù)挖掘、自然語言處理等文本處理技術(shù)的最終目標(biāo)，是其經(jīng)濟(jì)價(jià)值和社會價(jià)值的重要體現(xiàn).因此文本處理技術(shù)是大數(shù)據(jù)時(shí)代信息利用的關(guān)鍵途徑，其中文本信息檢索是文本處理技術(shù)的重要基礎(chǔ)和前提，如何在海量文本信息中準(zhǔn)確、全面的檢索到讀者需要的信息是文本信息檢索技術(shù)發(fā)展的關(guān)鍵問題和研究熱點(diǎn).

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

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

1 文本特征降維處理

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

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

(1)

(2)

PCA算法實(shí)現(xiàn)降維的仿真如圖1所示.

圖1 PCA降維仿真圖

2 文本特征聚類算法

文本特征聚類屬于數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要應(yīng)用，它的實(shí)現(xiàn)原理是依據(jù)文本的相似性，將相似性高的文本劃分為一個(gè)簇，各個(gè)簇之間關(guān)聯(lián)程度較小，因此可實(shí)現(xiàn)文本的快速檢索，從而幫助讀者快速有效地檢索出感興趣的文本信息.

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

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

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

圖2 K-Means算法特征聚類仿真結(jié)果圖

但是傳統(tǒng)的K-Means算法依靠隨機(jī)選擇確定質(zhì)心位置，勢必影響聚類結(jié)果和運(yùn)行時(shí)間.因此本文參考俞皓芳提出的改進(jìn)K-Means++算法進(jìn)行文本聚類[25].

K-Means算法的結(jié)果依賴于由初始聚類中心出發(fā)所遇到的第一個(gè)局部極值點(diǎn)，不同的初始聚類中心很可能導(dǎo)致截然不同的聚類結(jié)果.改進(jìn)K-Means++算法是在K-Means算法的基礎(chǔ)上進(jìn)行的優(yōu)化，其步驟為：

Step1首先隨機(jī)選擇輸入數(shù)據(jù)中的一個(gè)點(diǎn)作為第一個(gè)聚類中心.

Step2計(jì)算出數(shù)據(jù)中所有的點(diǎn)到step1中選取的點(diǎn)的距離.

Step3找出step2中所有距離最小的一個(gè).

Step4依據(jù)較大的點(diǎn)被作為聚類中心概率最大的原則，選擇一個(gè)新的聚類中心.

Step5不斷重復(fù)step2～step4，一直得到K個(gè)聚類質(zhì)心.

Step6利用得到的K個(gè)質(zhì)心執(zhí)行K-Means算法.

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

(3)

式(3)中：n表示文本數(shù)據(jù)當(dāng)中總共包含的文本特征數(shù)，vi為第i個(gè)特征的權(quán)重.由此計(jì)算文本信息檢索的目標(biāo)函數(shù)記為：

(4)

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

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)數(shù)據(jù)集來源于UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中下載的flame數(shù)據(jù)集.UCI數(shù)據(jù)庫是加州大學(xué)歐文分校提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫，這個(gè)數(shù)據(jù)庫共有559個(gè)數(shù)據(jù)，實(shí)驗(yàn)采用UCI數(shù)據(jù)庫下的flame數(shù)據(jù)集，其中記錄數(shù)為240，維度為2，聚類數(shù)為2.

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

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

為了進(jìn)一步驗(yàn)證本文算法在文本信息檢索中的有效性，本文統(tǒng)計(jì)了三種不同算法檢索時(shí)間，結(jié)果如表1所示.

表1 不同算法檢索時(shí)間

根據(jù)表1中的結(jié)果可知，本文算法的檢索時(shí)間，相較于傳統(tǒng)K-Means算法，時(shí)間降低13.3個(gè)百分點(diǎn)，相較于合并聚類算法，時(shí)間降低25.7個(gè)百分點(diǎn)，充分體現(xiàn)本文算法在文本數(shù)據(jù)檢索方面的優(yōu)越性.

4 結(jié)論

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