摘  要： 文本聚類在很多領域都有廣泛應用，而聚類算法作為文本聚類的核心直接決定了聚類的效果和效率。結合基于劃分的聚類算法和基于密度的聚類算法的優點，提出了基于密度的聚類算法DBCKNN。算法利用了k近鄰和離群度等概念，能夠迅速確定數據集中每類的中心及其類半徑，在保證聚類效果的基礎上提高了聚類效率。
關鍵詞： 文本聚類；基于密度；k近鄰；離群度

    文本聚類是指將n篇文章聚集成k類，使得每類內的樣本相似度較大，每類間的樣本相似度較小。文本聚類是一種特殊的數據聚類，有著自身的特點。文本的聚類對象維數較高，決定了聚類算法需要快速收斂，注重效率。國內外也圍繞著文本聚類提出了很多理論和算法，采用的核心聚類算法一般分為兩類，一類是基于劃分的聚類算法，如K-means算法、CLARANS算法等；另一類是基于密度的聚類算法，如KNNCLUST算法、DBSCAN算法等。
1 基于密度聚類算法的研究與改進
1.1現有算法的缺陷
    K-means算法與DBSCAN算法分別作為基于劃分和基于密度的聚類算法的代表，被廣泛應用于文本聚類中。其中K-means算法有實現簡單、時間復雜度低等優點，但算法需要指定種類數，且對初始點依賴性過強，導致聚類效果不理想；DBSCAN算法則有抗噪音性強、聚類準確性高等優點，但算法的主要閾值參數很難確定，且時間復雜度過高，導致聚類效果不理想。
    本文將K-means算法的特性，融入到利用k近鄰概念的基于密度的聚類算法中，提出了DBCKNN算法(Density-Based Clustering using K-Nearest Neighbor)，在保證算法準確性的前提下，提高了算法效率。


點的絕對離群度域值為(0，+∞)，且值越小，表示點越有可能為類中點，反之，表示點越有可能為噪音點。θ一般取不大于3的正整數，θ越大，不同對象的絕對離群度分布越離散。如圖1(a)中類近似為高斯分布，圖1(b)中z軸為點的絕對離群度值，其θ取1。可以看出，越是類中心的點，其絕對離群度越小，而類邊緣和噪音點都有相對高的絕對離群度值。

    定義6 邊緣點集的k平均近鄰距離的均值

1.3 算法改進
1.3.1 確定類初始中心核心子算法FINDCENTER(ε)
    現有的基于密度的聚類算法中，通常會對全體點進行一次密度值掃描，導致算法復雜性和空間復雜性過高。改進后的算法，利用劃分算法中迭代并更新中心點的思想，可以對定半徑的超球體的移動具有指導性，使得落入超球體內部的點相對更多，即超球體的密度相對更大。
    算法1 FINDCENTER(ε)
    算法輸入：p，ε；算法輸出：p
    (1)以ε為鄰域半徑，求|Neighbors(p，ε)|和absdegree(p，k)。
   
    算法中的λ取值一般為0~1。λ取值越小，半徑變化越小，迭代次數越多，但最終得到類半徑的值越準確。算法中的(α，β)域越寬，聚類粒度越大。算法中的n是不大于k的正整數，一般取值和k相同。n取值越大，則時間復雜度越高，但最終得到類半徑的值越準確。
1.3.3 DBSCAN算法思想
    在數據對象集中找到absdegree(p，k)大于閾值的對象p后，通過反復迭代FINDCENTER(ε)和ADJUSTRADIUS(p，ε)，找出初始類Ci，并將Ci排除出數據對象集。重復上述過程，生成初始類集。通過初始類集中各類間的包含關系和評價函數，將噪音點集從初始類集中提取出。最后將噪音點集中的對象按與類集中各類中心點的距離分配給各個類。
2 實驗
    通過實驗對DBCKNN算法的聚類效果和時間效率進行對比和分析。數據集采用兩個著名的數據集Iris和KDDCUP1000。測試數據集信息如表1。這兩個數據集每一類的數據映射到高維空間中近似為正凸型的超球體，符合文本聚類中所提取的文本特征向量的分布情況，其中Iris為3類，KDDCUP1000為5類。實驗用VC6.0編寫，在配置PentiumⅣ 2.4 GB CPU、內存1 GB、80 GB硬盤的計算機上運行。

    本文對聚類效果的評判標準采用參考文獻[4]中提出的聚類質量判定式：S-Dbw(c)=Scat(c)+Dens-bw(c)，其中c為類集，Dens-bw(c)評價的是各類間的平均密度，值越小表示類間區分度越好；Scat(c)評價的是類內元素的相似性，值越小表示類越內聚。
    對經典算法K-means、DBSCAN和本文提出的DBCKNN算法在聚類效果和效率上做對比。其中K-means算法的k分別取3和5，并對初始點集做預處理，盡量使初始點集分散且局部密度相對大，DBSCAN算法的minpts、eps取2.5，DBCKNN算法的λ取0.5，k、n取20，θ取2，(α，β)取(0.9，1.1)。
    圖2為預處理后的K-means算法、DBSCAN算法和DBCKNN算法對測試數據集的聚類效果比較。
    從圖2可以看出，雖然已經對初始點集做了預處理，而且對k取了正確的值，但是K-means算法效果仍然不理想。由于DBSCAN算法在數據對象密度的處理上更精確，在數據對象維數較低時，效果略好于DBCKNN算法；而當數據對象維數較高時，高維空間中數據分布稀疏，DBSCAN算法會誤將部分數據對象視為噪音點，從而對聚類效果產生負面影響，而由于DBCKNN算法采用k近鄰距離作為密度探測半徑，對噪音點的處理更加合理，所以在數據對象維數較高時效果要略好于DBSCAN算法。

    圖3為K-means算法、DBSCAN算法和DBCKNN算法對測試數據集的聚類效率。

    從圖3可以看出，K-means算法的效率非常高，在常數次迭代就得到聚類結果，數據規模對聚類效率的影響有限；DBSCAN算法要對所有數據對象的密度進行一次以上的處理，聚類效率依賴于數據規模，導致效率相對低下；本文的DBCKNN算法會根據數據對象局部區域的密度信息來評價這個局部區域所有數據對象的密度信息，所以聚類效率比K-means算法低，但遠高于DBSCAN算法。
    本文結合了基于劃分的聚類算法和基于密度的聚類算法各自的優點，提出了一種能夠快速找到類中心并自適應類半徑的聚類算法DBCKNN算法。DBCKNN算法能在對高維空間下每類形似正凸形超球體的數據對象集進行相對準確的聚類情況下，提高算法效率。另外，本文通過分析及實驗數據對比，從聚類效果和聚類效率兩方面驗證了這種改進方法的正確性和高效性。進一步將這種方法和基于語義的聚類方法相結合，應用于聚類搜索引擎等數據挖掘領域，是下一步研究的重點。
參考文獻
[1] 孫吉貴．聚類算法研究[J]．軟件學報，2008，19(1)：48-61．
[2] KANUNGO T， MOUNT D M， NETANYAHU N， et al． A local search approximation algorithm for K-means clustering[J]．Computational Geometry， 2004(28)： 89-112．
[3] 汪中．一種優化初始中心點的K-means算法[J]．模式識別與人工智能，2009，22(2)：300-304．
[4] HALKIDI M， VAZIRGIANNIS M． Clustering validity assessment： finding the optimal partitioning of a data set[C]． In： Proc．of the 1st IEEE Int’I Conf．on Data Mining．187-194．
[5] 談恒貴．數據挖掘中的聚類算法[J]．微型機與應用，2005(1)．