基于高維聚類的文本大數(shù)據(jù)挖掘算法仿真

郭紅建,陳一飛,梅軼群

(南京審計大學(xué)信息工程學(xué)院,江蘇 南京 211815)

1 引言

當(dāng)前數(shù)據(jù)挖掘領(lǐng)域發(fā)展迅速,其面臨的問題與挑戰(zhàn)也越來越多。多媒體時代的到來,全球各地的用戶通過多種載體模式交流和獲取信息,但是在數(shù)據(jù)挖掘時經(jīng)常會碰見高維數(shù)據(jù)[1],這些高維數(shù)據(jù)中包含冗余、空間維度復(fù)雜的信息,挖掘其中并獲取自己想要的信息較為困難[2],導(dǎo)致時間、資金和精力的巨大損失。因此,如何有效地從高維數(shù)據(jù)中提取到想要的信息成為研究的重點。

目前相關(guān)學(xué)著已經(jīng)提出了很多經(jīng)典的文本挖掘方法,例如:黃文秀等人[3]提出一種基于改進的k最鄰近算法的海量數(shù)據(jù)挖掘方法。以文本大數(shù)據(jù)集合為樣本集,確定密集樣本的分布區(qū)域,并對其精準劃分,使文本數(shù)據(jù)分布更加均衡。基于此,利用改進的k最鄰近算法對處理后的文本大數(shù)據(jù)分類,完成文本的挖掘。但是該方法在挖掘文本前,會將數(shù)據(jù)對象進行相似編碼,數(shù)據(jù)對象需要迭代幾百次,步驟復(fù)雜,運行效率低。牛奉高等人[4]提出一種基于加權(quán)網(wǎng)絡(luò)改進的短文本相似性挖掘方法。首先,在語義網(wǎng)范圍內(nèi)對文本共現(xiàn)頻次實現(xiàn)加權(quán),針對短文本的權(quán)重識別效率偏低的問題,計算短文本中每個詞語的加權(quán)復(fù)雜網(wǎng)絡(luò)綜合特征值,并通過聚類處理最終得到文本挖掘結(jié)果。但此方法對初始數(shù)據(jù)點較為敏感,易出現(xiàn)劇烈合并錯亂的現(xiàn)象,風(fēng)險較大,其次,在處理高維數(shù)據(jù)時,目標函數(shù)運算過程中會發(fā)生收斂的狀況,導(dǎo)致算法結(jié)果不精準。

為此,提出一種基于高維聚類算法的文本大數(shù)據(jù)挖掘方法。通過等距離特征映射算法[5]將多維數(shù)據(jù)轉(zhuǎn)換到低維空間中,得到全局最小值,降低了空間的維數(shù)。并在傳統(tǒng)的模糊聚類方法上作出改進,為減少獨立數(shù)據(jù)對聚類中心的影響,從數(shù)據(jù)類型的隸屬性上提高權(quán)值系數(shù)[6];以信息熵作為衡量聚類項目的標準;通過密度函數(shù)提取原始聚類中心[7],當(dāng)平均信息熵達到做小數(shù)值時,此時的聚類中心為最佳聚類數(shù),聚類技術(shù)的操作有效,精度準確。

2 大數(shù)據(jù)降維

等距離特征映射算法能夠在保證多維數(shù)據(jù)的幾何特征不變條件下,將多維數(shù)據(jù)轉(zhuǎn)換到低維空間中。通過計算數(shù)據(jù)節(jié)點間距離,保證在最小損失原始信息的同時降低數(shù)據(jù)維數(shù)。構(gòu)建鄰居圖、嵌入維層得到全局距離最小值,對于距離相近的兩個點,用空間最短距離表示;對于距離較遠的兩個點,用相鄰的空間最長距離表示。

第一步建立鄰居圖G,Y表示輸入空間,I,J表示輸入空間內(nèi)的任意兩個點,M表示距離的流形,通過一個獨立的點連接所有相鄰的點。

第二步計算鄰居圖G中最短直徑空間距離dG(I,J),推導(dǎo)出流形M里所有相對兩點之間的測量距離dM(I,J)。當(dāng)I,J兩點相連時,可以描述為dY(I,J);當(dāng)I,J兩點不相連時,則dG(I,J)=∞。對于K=(1,2,…,N)的任意數(shù)值,使用min{dG(I,J),dG(I,K)+dG(K,J)}來替換輸入dG(I,J)。最后用DG=dG(I,J)數(shù)值矩陣描述鄰居圖G中點對之間的最短距離。

第三步嵌入d維,憑借圖距離矩陣[8]DG=dG(I,J),在d維度的空間Y內(nèi),空間Y可以最大限度的保證數(shù)據(jù)流形的幾何特征。

在Y的坐標向量yi內(nèi),通過誤差函數(shù)[9]降低兩點之間測量距離的錯誤率。

(1)

式中,L2代表矩陣模式,將距離轉(zhuǎn)換為內(nèi)積,DY代表{dy(I,J)}的矩陣,DG代表{dG(I,J)}的矩陣,基于上述在保證原本數(shù)據(jù)的幾何特性前提下,得到了全局的最小數(shù)值,降低了原始高維大數(shù)據(jù)空間的維數(shù)。

3 關(guān)鍵特征提取

編程模型[10]是一種并行計算模型,由于降維后數(shù)據(jù)內(nèi)會包含一部分用戶隱私信息,這部分信息被加密了,很難提取其特征和文本數(shù)據(jù)挖掘,難以保證挖掘結(jié)果的F1值,為此,憑借編程模型中的匯編程序與再生產(chǎn)兩個過程,實現(xiàn)對加密大數(shù)據(jù)關(guān)鍵特征映射估計。

匯編程序函數(shù)將(密鑰中心,估計值)作為輸入,通過一系列的處理,將新的(密鑰中心,估計值)作為輸出,具體操作過程如圖1所示:

圖1 映射任務(wù)執(zhí)行過程

在生產(chǎn)函數(shù)將密鑰中心作為輸入,經(jīng)處理后,輸出結(jié)果最終形成最佳估計值,具體操作過程如圖2所示:

圖2 導(dǎo)出任務(wù)執(zhí)行過程

為更好地提取大數(shù)據(jù)內(nèi)關(guān)鍵特征,以便獲得最佳文本聚類中心,對其相空間重建[11],避免在特征提取時破壞降維后的數(shù)據(jù)特征。

設(shè)定{q1,q2,…,qN}為一維空間序列,重建的相空間為:

(2)

r≥2a+1

(3)

其中,r代表嵌入維數(shù),a代表奇異吸引子的維度,ε代表時延,當(dāng)發(fā)生r≥2a+1的情況,就會破壞數(shù)據(jù)內(nèi)的幾何結(jié)構(gòu)特征。

關(guān)聯(lián)維[12]可以描述數(shù)據(jù)在多維空間中稀疏濃密程度。在大數(shù)據(jù)相空間重新構(gòu)造的基礎(chǔ)上,使用關(guān)聯(lián)維提取相空間矢量,通過兩個矢量[13]的最高限度分量差計算兩個矢量之間的距離,建立公式如下

|QI-QJ|=max1≤δ≤r|QIδ-QJδ|

(4)

其中,δ表示常數(shù)。將I,J兩點間隔低于正數(shù)l的矢量作為關(guān)聯(lián)矢量,在重建空間中發(fā)現(xiàn)h點,那么在h2組內(nèi)的占比為關(guān)聯(lián)積分,H表示海維賽德函數(shù),計算出矢量對數(shù)。

(5)

(6)

關(guān)聯(lián)積分Sh(l)在發(fā)生l=0的狀態(tài)下與l有關(guān)聯(lián),描述公式如下

(7)

式中,C表示為關(guān)聯(lián)維數(shù),基于此可選取合理正數(shù)l,近似值為

(8)

在空間內(nèi)數(shù)據(jù)樣本相對應(yīng)的關(guān)聯(lián)度低、分布散亂、不集中,不同數(shù)據(jù)樣本點數(shù)值與實際數(shù)值之間存在大幅度偏差,σI表示點I序列分解的標準差,z表示倍頻因子,重新組建的空間分布XI關(guān)系

(9)

在提取的特征樣本中,若XI數(shù)值較大,說明數(shù)據(jù)特征樣本分布稀疏,關(guān)聯(lián)性低;若XI數(shù)值較小,說明數(shù)據(jù)特征樣本分布密集,關(guān)聯(lián)性高。通過重建空間分布關(guān)系能夠識別不同信息類型特征集合。

4 文本大數(shù)據(jù)挖掘

4.1 聚類中心密度函數(shù)的計算

(10)

得到樣本點密集程度后,提取樣本中均方根測量距離的二分之一,計算公式如下

(11)

其中,樣本點xi的分布越密集,說明Fi數(shù)值越大,使Fi=max(Fi,i=1,2,…,N),計算改進后的初始數(shù)據(jù)聚類中心的密度函數(shù)描述為:

(12)

聚類的分類越完善,任意數(shù)據(jù)點在其聚類上的歸屬感越高,所提方法使用信息熵為衡量聚類數(shù)目,迭代中轉(zhuǎn)換聚類中心,更改聚類數(shù),當(dāng)平均信息熵轉(zhuǎn)換到最小數(shù)值,其相對的聚類項目為最有效。uij代表在i空間類別的j數(shù)據(jù)樣本的聚類程度,B代表聚類中心數(shù)量,最小值的平均信息熵?所對應(yīng)的聚類數(shù)量為最優(yōu)。平均信息熵的計算公式如下:

(13)

4.2 改進隸屬度

為了實現(xiàn)最佳聚類結(jié)果,基于數(shù)據(jù)類型隸屬度提高權(quán)值系數(shù),改進隸屬度[15]可以將聚類中心范圍變大,計算公式如下

(14)

當(dāng)y等于1時,表示Nij=uij;當(dāng)uij等于0時,表示Nij=0;當(dāng)uij等于1時,表示Nij=1。在聚類算法迭代中,隸屬度數(shù)值降低導(dǎo)致數(shù)據(jù)對象對聚類中心的影響范圍變小。當(dāng)y數(shù)值越大,隸屬度的上下浮動越低,聚類結(jié)果精準清晰;相反,當(dāng)y數(shù)值越小,隸屬度的上下浮動越高,聚類結(jié)果收斂且不精準。

4.3 文本挖掘

為實現(xiàn)文本的最終挖掘,需優(yōu)化聚類數(shù)目以及模糊加權(quán)系數(shù)的不足,在數(shù)據(jù)對象本身增加一個隸屬權(quán)值Nij,使相應(yīng)數(shù)據(jù)中,隸屬度高的特征可以提升對聚類挖掘中心的影響程度,隸屬度低的特征可以減少對聚類中心的影響程度,算法步驟如下:

1)初始化聚類數(shù)c=2,對其迭代,當(dāng)?shù)螖?shù)為b=0,提取指數(shù)權(quán)重數(shù)值m。

2)計算數(shù)據(jù)的隸屬度:

(15)

3)通過對隸屬度的改進,降低對聚類中心的影響。

4)更新聚類中心:

(16)

5 研究方法性能驗證

5.1 實驗環(huán)境

文本聚類算法的性能受多因素影響,為證明提出聚類算法的文本挖掘有效性。使用自建源代碼文件夾檢驗,此文件夾含有視頻數(shù)據(jù)、聲音數(shù)據(jù)、圖像數(shù)據(jù)、代碼模式數(shù)據(jù)、文本數(shù)據(jù)。分析每個源程序數(shù)據(jù)信息,完成大數(shù)據(jù)問卷的總列表,建立實驗軟件環(huán)境如圖3所示。

圖3 實驗的軟件環(huán)境

由圖3可以得出,此實驗軟件環(huán)境的主體界面含有菜單欄、頁面顯示、查詢列表、關(guān)鍵詞語提取。通過輸入關(guān)鍵字,可清晰查詢到文本聚類算法相對應(yīng)的功能函數(shù)。

5.2 指標量化測試結(jié)果與分析

在文本挖掘過程中,選定指標來驗證所提方法的挖掘性能。評價挖掘可描述為混淆矩陣,TP表示被挖掘出的文本數(shù)據(jù),FP表示被挖掘的非文本數(shù)據(jù),FN表示未被挖掘的文本數(shù)據(jù),TN表示未被挖掘的非文本數(shù)據(jù)。

1)查準率為文本被正確挖掘出的數(shù)量與預(yù)測文本數(shù)據(jù)數(shù)量的比值,準確率計算公式為

(17)

2)查全率為文本被正確挖掘出的數(shù)量與實際文本數(shù)據(jù)數(shù)量的比值,查全率計算公式為:

(18)

3)F1值表示查準率與查全率之間的調(diào)和平均值,因為二者里面存在非線性關(guān)系,會存在查準率高但查全率低的情況。通過計算得到的F1值越大,代表查準率與查全率之間不一致結(jié)果越小,計算過程為

(19)

實驗選取文獻[3]提出的基于改進的k最鄰近算法的海量數(shù)據(jù)挖掘方法和文獻[4]提出的基于加權(quán)網(wǎng)絡(luò)改進的短文本相似性挖掘方法作為實驗對照組,與所提方法的指標測試結(jié)果相比較,三種方法挖掘結(jié)果的調(diào)和平均指標F1值如圖4所示。

圖4 不同方法挖掘結(jié)果準確率對比

圖4中能夠看出,基于改進的k最鄰近算法的海量數(shù)據(jù)挖掘方法的F1值在0.90到0.94之間;基于加權(quán)網(wǎng)絡(luò)改進的短文本相似性挖掘方法的F1值雖然波動更為平穩(wěn),但是F1值總體較低;所提方法F1值隨著實驗次數(shù)增加出現(xiàn)小幅度的波動,但是可穩(wěn)定在0.96到1之間,證明所提方法的數(shù)據(jù)挖掘精準。

5.3 聚類可視化效果評價

將采集的5組實驗數(shù)據(jù)放置在降維后的空間內(nèi),深度數(shù)據(jù)聚類。不同方法的文本聚類結(jié)果如圖5所示。

圖5 不同方法的文本數(shù)據(jù)聚類結(jié)果

分析圖5可知,由于視頻數(shù)據(jù)集與圖像數(shù)據(jù)集相似度高,文獻方法在聚類過程中會出現(xiàn)錯分的問題,且使代碼模式數(shù)據(jù)、文本數(shù)據(jù)聚類中心過近,難以明確挖掘各類數(shù)據(jù)信息。應(yīng)用所提方法完成本文聚類處理時,不僅聚類邊界清晰,而且相似點的聚類中心距離最遠,最大程度避免了后期發(fā)生數(shù)據(jù)挖掘錯誤的情況。

6 結(jié)論

本文將多維數(shù)據(jù)轉(zhuǎn)換到低維空間后提取數(shù)據(jù)的關(guān)鍵特征信息,利用改進模糊聚類方法對大數(shù)據(jù)環(huán)境下文本信息挖掘,得到文本數(shù)據(jù)的特征向量,使用密度函數(shù)得到聚類中心,輸出最終挖掘結(jié)果。通過實驗證明了本次研究對文本數(shù)據(jù)挖掘?qū)嶋H應(yīng)用具有重要意義。