一種改進的K—medoids知識聚類算法研究

譚黔林+覃運初+盧艷蘭

摘 要：根據(jù)文本信息在聚類過程中的特點構建了一種基于K-medoids的文檔聚類方法，并結合文本特征提取KNN算法對訓練文本進行測試，該方法首先利用K-medoids在聚類過程中實現(xiàn)簡單、收斂速度快的特性，再利用KNN算法在文檔特征提取過程中簡單、高效的特點，對訓練進行聚類劃分。實驗結果表明，利用該方法在對文檔進行聚類時，F(xiàn)1值、耗時及分割數(shù)等方面與KNN及CLKNN算法相比都有較大提高。

關鍵詞關鍵詞：K-medoids；知識聚類；聚類分析技術

DOIDOI：10.11907/rjdk.161475

中圖分類號：TP312

文獻標識碼：A ：1672-7800（2016）008-0013-03

0 引言

聚類分析技術已廣泛應用于各大領域，并已在原有基礎上針對不同的應用領域進行了改進，提出了相應的算法及模型，大體上可分為網(wǎng)格、層次、密度、層次及劃分方法。大數(shù)據(jù)時代，各類結構化、半結構化的數(shù)據(jù)資源在快速增長，用戶在檢索信息過程中的搜索范圍也越來越廣，聚類分析技術的引入可以有效提高相似信息的分類，使同一類的信息個體具有高度的同質性，使不同類之間的個體具有高度的異質性[1]，從而有效提高了用戶信息獲準率。

知識搜索，實際上是將信息按照學科性質、從屬關系及層次關系進行組織，根據(jù)關鍵詞、關鍵字及其屬性進行分類匯總的過程，通過聚類規(guī)則將同屬性、高相似度的信息進行分類，有效解決當前大數(shù)據(jù)集下信息的獲準率問題，從而提高知識獲取的速度與準確度。K-means聚類方法由于實現(xiàn)簡單、收斂速度快而被廣泛應用，但由于K值難以估算從而給具體分類帶來了困難。大數(shù)據(jù)集中，為了有效實現(xiàn)數(shù)據(jù)分類，阮光冊在文獻[2]中將集對分析同異反系統(tǒng)和文本向量空間模式相結合，提出了一種基于流形結構的聚類分析算法；楊欣欣、黃少濱在文獻[3]中通過相關性度量指標Goodman-kruskalτ對特征變量和對象變量的相關性進行衡量，提出了一種高階層次聯(lián)合聚類算法；文獻[4]中利用二分圖聚類算法構造了基于Web數(shù)據(jù)挖掘的搜索引擎。因此，通過聚類方法將同質性的信息進行聚合，解決知識搜索中的泛在性，對大數(shù)據(jù)集下的知識搜索相關研究具有重要意義。

1 K-medoids聚類算法

聚類是數(shù)據(jù)挖掘中的一種常用方法，通過聚類將相同特質和具有共同屬性的個體歸為一簇，在不同的簇中，同質性的個體具有較高的相似度，表現(xiàn)為個體之間的距離較短，異質類個體之間的距離則表現(xiàn)為距離越大，相似度越低。K-medoids聚類算法是一種基于劃分的聚類方法[5]，相比K-means算法而言，K-medoids算法更容易實現(xiàn)，具有較好的收斂性和時間復雜度，在全局搜索時所得到的效果更好。

1.1 算法描述

K-medoids算法廣泛應用于大數(shù)據(jù)集下的文本分類，算法過程是將N個數(shù)據(jù)對象劃分為K個類作為聚類參照中心，對未劃分到類中的數(shù)據(jù)對象按照距離優(yōu)先原則劃分到鄰近的簇中，得到初始聚類后，將剩余的對象按距離長短進行重新劃分，反復執(zhí)行這一過程，直到簇收斂。K-medoids聚類算法是基于聚類準則函數(shù)的最優(yōu)原則，使用最接近聚類中心的對象作為類中心，增強了算法的魯棒性，對小的數(shù)據(jù)集非常有效[6]。

1.2 K-medoids算法過程

輸入：K個簇，包含n個數(shù)據(jù)集。

輸出：符合條件的K個聚類。

在輸出的符合條件的K個聚類中，聚類效果通常使用絕對誤差標準函數(shù)來進行衡量，定義為：

式（1）中，x為簇si中的一個對象，si是聚類中心的第i個簇，k表示簇的數(shù)量，C值的大小取決于簇內各對象與中心點的距離，C值越大說明簇內各對象的相似類越低，反之亦然。

①從n個數(shù)據(jù)集中，選k個對象作為聚類的初始中心點；②對離中心點距離較遠的對象進行劃分，將其分配到附近的簇中；③對每個簇的均值進行重新計算，為每一簇賦予新的值給；④重復②、③步驟，直到類收斂。

1.3 K-medoids算法擴展

K-medoids聚類算法在聚類過程中，通過對簇中心點周圍的對象進行反復均值計算更新，能夠得到較為理想的分類結果。在知識搜索過程中，利用這一思想，通過類別、關鍵詞、關鍵字、同一性等方式對不同信息資源進行分類匯總，產(chǎn)生初始的類，再利用K-medoids聚類算法對知識的特征碼進行聚類分析，直到類收斂，可以有效提高信息知識的分類效果。

2 基于K-medoids的聚類構建

2.1 特征提取

在進行聚類前，所有知識信息都是相對獨立的，利用KNN算法進行特征提取時根據(jù)這一特點進行假設判定：①假設所有的知識信息都是相對獨立的，知識信息內容出現(xiàn)的頻率和位置無關；②將收集到的知識信息進行抽取映射分組，分成U1，T1；U2，T2；…；UN，TN個組別；③假設信息知識分組的訓練集有C，C中有N個不同的類別V1，V2，V3，…，VN，其總數(shù)有M；④最后將特征對數(shù)進行降維處理，表示為Wi={a1，a2，a3，…，an}T，其中i的取值范圍為0～M（含M）。

在特征提取階段，按照知識信息的特征向量，將訓練過程中分類尚未確定的知識信息W表示為：W={a1，a2，a3，…，an}T；再次從C訓練集中提取出W中相似度較高的訓練集知識信息Wi={a1，a2，a3，…，an}T，得到知識信息的高相似性分類，最后W歸屬分類知識信息。待分類知識信息和訓練集的分類根據(jù)向量夾角余弦公式計算，如下：

根據(jù)K鄰近值，對分類信息W在各分類中的所屬關系進行計算，如下：

最后得到Vm，其中包含了等分類的信息文本W(wǎng)。

在分類算法中，KNN算法具有簡單、高效的特點，在文本信息分類過程中經(jīng)常用到此方法。

2.2 聚類構建

在大數(shù)據(jù)集中，對一些復雜的信息進行分類，單獨采用K-medoids或KNN算法都具有一定的局限性或不足，K-medoids在大數(shù)據(jù)集聚類過程中存在收斂度低、產(chǎn)生的類目較多等缺點，而KNN在聚類過程中也存在耗時大、誤差也較大等不足，基于以上考慮，在聚類過程中同時采用K-medoids和KNN算法對大數(shù)據(jù)集下的信息知識進行二次聚類處理，以解決在大數(shù)據(jù)集下對信息知識聚類過程中存在的中足，提高聚類的效果和效率，聚類過程如下：輸入：訓練集W，包含n個數(shù)據(jù)集。輸出：m個聚類。①從數(shù)據(jù)集中隨機對數(shù)據(jù)進行抽取，找到若干個樣本集W1，W2，W3，…，Wm作為原始的聚類中心點；②通過K-medoids算法，用公式（1）對樣本集進行聚類處理，并將每個聚類標記為C1，C2，C3，…，Cm；③反復從訓練集W中對樣本的相似類進行計算，得出最大相似度的文本；④在計算出初始聚類后，利用KNN算法對類進行收縮計算，去除因增長較慢而未形成的類，調整聚類中心；⑤重復步驟①-④，直到所有數(shù)據(jù)被劃分出m個類，且無獨立的文本數(shù)據(jù)。

3 實驗分析

實驗之前，考慮到計算過程中文本相似度較大，所產(chǎn)生的維度也較高，為確保計算效果，在進行聚類時，對文本類別、標題、關鍵字、關鍵詞進行分析，以降低計算時文本產(chǎn)生的維度。同時利用本文所提出的方法進行了實驗，實驗環(huán)境如下：實驗時所采用的系統(tǒng)環(huán)境為Windows 8 64位，處理器為Inter i5 5200 2.2G，內存為6G，實驗工具為Eclipse和Matlab。數(shù)據(jù)集源自復旦大學計算機信息與技術系國際數(shù)據(jù)庫中心自然語言處理小組提供的文本分類語類庫，文檔總量為19 637篇，共20個類別，選取其中農(nóng)業(yè)、藝術、軍事、計算機、經(jīng)濟、教育、環(huán)境、醫(yī)學8個類別，共2 627個文本，其中用于訓練的文本總量為1 839個，余下788個文檔用于測試，實驗數(shù)據(jù)如表1所示。

對文檔聚類效果進行評價，常用的指標參數(shù)為文檔的查準率P（precision）、查全率R（recall）及F1值（與準確率、查全率有相關性）[7]。查準率由文檔正確分類數(shù)T1和用于測試的總文檔數(shù)T2之間的比值構成，計算公式如下：

查全率是衡量檢索性能的一項重要評價指標，是計算結果中所得到的正確的分類文檔數(shù)T1與實際應得到的文檔數(shù)T0之間的比值，計算公式如下：

F1值是為了平衡查準率和查全率之間的關系而提出，當查準過高時，查全率相應就會降低，反之亦然，F(xiàn)1值的計算公式如下：F1=P×RP+R×2×100%（6）

實驗過程主要分為兩個階段，實驗中將文本提出的方法與傳統(tǒng)的KNN算法和文獻[8]中所提出的CLKNN算法進行對比實驗，第一階段主要確定3種不同算法的最佳分類點，在初始分類值的基礎上依次遞增，根據(jù)P、R及F1值確定最佳分類值。3種不同算法最佳分類的比對情況如表2所示。

從表2中的實驗數(shù)據(jù)可得出，KNN算法在進行聚類劃分過程中，當取值為19時，P、R及F1值達到最大值，此時聚類效果最佳；CLKNN算法在取值為14時，各項指標達到最大值；本文中的算法取值為17時P、R及F1值為最大，聚類效果達到最優(yōu)。在得到最優(yōu)取值的前提下，進行第二階段的實驗，對比3種不同算法在實驗過程中的優(yōu)越性，實驗數(shù)據(jù)如圖1和表3所示。

考慮到文本聚類的綜合評價指標不由查準率和查全率單獨確定，因而省略了P、R值的對比。從圖1和表3兩組數(shù)據(jù)中可看出KNN算法和改進的CLKNN算法與本文提出的方法在對數(shù)據(jù)集進行聚類后的F1值、耗時及分割個數(shù)的對比情況，圖1中，CLKNN算法相對于KNN所得到的F1值有了明顯提高，平均提高了3.8%，而本文中的算法在前兩種算法基礎之上有了進一步提升，比CLKNN算法平均提高了1.2%。表3中，KNN算法在聚類時耗時最長，由于CLKNN算法在對訓練集進行聚類時分割的文數(shù)較多，所花費的時間相對于本文提出的算法多了18s，而本文算法在分割上較CLKNN少，因而在訓練過程中所耗費的時間也較CLKNN少，通過兩組數(shù)據(jù)的分析證明，本文所提出的方法在對文本的分類性能上較前兩種算法均有所提高。

4 結語

本文利用K-medoids聚類方法并結合KNN算法在文本聚類中的優(yōu)勢，提出了一種基于K-medoids的改進的知識聚類算法，在實驗過程中經(jīng)過大量的訓練及測試，并與原有KNN算法及經(jīng)過改進后的CLKNN進行了性能測試、比較，結果表明，本文所提出的方法不管是在聚類效果還是在測試耗時及分割方面都有明顯提高，進一步解決了KNN算法在聚類過程中耗時長、文本丟失較大的缺點。本文算法在性能方面較KNN和CLKNN算法有明顯提高，但本方法是在對測試集進行降維處理前提下所進行的實驗，在測試過程中減少了對本文算法的部分開銷，此外大數(shù)據(jù)集下本算法的峰值及性能評測、維度處理也需重點研究。

參考文獻：

[1] 唐然，龍騰銳，龍向宇.基于模糊聚類的改進遺傳算法[J].重慶大學學報，2008（2）：165-169.

[2] 阮光冊.基于知識關聯(lián)的檢索結果聚類分析研究[J].情報科學，2015（2）：63-66.

[3] 楊欣欣，黃少濱.高階異構數(shù)據(jù)層次聯(lián)合聚類算法[J].計算機研究與發(fā)展，2015，521（1）：200-210.

[4] SHARIFI，ABOOSALEH M，AMIRGHOLIPOUR.Intrusion detection based on joint of k-means and knn[J].Journal of Convergence Information Technology，2014（5）：45-52.

[5] SHASHIDHAR HV，SUBRAMANIAN VARADARAJAN.Customer segmentation of bank based on data mining security value based heuristic approach as a replacement to kmeans segmentation[J].International Journal of Computer Applications，2011（5）：66-72.

[6] S VIMALA.Convergence analysis of codebook generation techniques for vector quantization using K-Means clustering technique[J].International Journal of Computer Applications，2011（3）：85-92.

[7] NALINI SINGH，AMBARISH G MOHAPATRA.Breast cancer mass detection in mammograms using kmeans and fuzzy cmeans clustering[J].International Journal of Computer Applications，2014（3）：34-40.

[8] 路永和，何新宇.文檔相似矩陣在提高KNN分類效率中的應用[J].情報理論與實踐，2014（1）：141-144.

[9] HEJIN YUAN，CUIRU WANG.A human action recognition algorithm based on semi-supervised kmeans clustering[J].Transactions on Edutainment，2014（6）：47-52.

（責任編輯：孫 娟）