基于最近鄰思想的K-均值算法

李金廣 劉家磊 安陽工學院

基于最近鄰思想的K-均值算法

李金廣 劉家磊 安陽工學院

K-均值聚類算法是一種基于劃分方法的聚類算法，本文通過對傳統的K-均值聚類算法的分析，提出了一種改進的K-均值算法，并對該算法的時間復雜度和空間復雜度進行了分析。該算法在計算聚類中心點時采用了一種最近鄰的思想，可以有效地去除“噪聲”和“孤立點”對簇中平均值（聚類中心）的影響，從而使聚類結果更加合理。最后通過實驗表明該算法的有效性和正確性。

數據挖掘；聚類；K-均值。

1 當前主要的聚類算法

數據聚類是數據挖掘的一個非常活躍的研究方向。聚類在文獻[1]中定義為：將數據對象進行分組，成為多個類或簇。在聚類過程中無須用戶提供先驗的分類知識，而是根據數據實際的分布情況得到自然的聚集結果。當前主要的聚類算法可以劃分為如下幾類：

1）基于劃分的方法，如k-means(K-均值)文獻[2]，k-medoids(K-中心點)文獻[3]；

2）基于層次的方法，如BIRCH文獻[4]，CURE文獻[5], ROCK文獻[6]，Chameleon文獻[7]；

3）基于密度的方法，如DBSCAN文獻[8]；

4）基于網格的方法，如STING；

5）基于模型的方法。

全文內容安排如下：第二節介紹傳統K-均值算法的基本思想，并進行特性分析；第三節介紹改進的K-均值算法；第四節實驗；第五節結束語。

2 傳統的K-均值算法

2.1 基本思想

K-均值算法是一種重要的聚類算法，它是目前應用最廣的基于劃分的聚類算法，K-均值算法以K為參數，把N個對象分為K個簇，使簇內具有較高的相似度，而簇間的相似度較低。相似度的計算根據一個簇中的對象的平均值來進行。

K-均值算法的處理流程如下：首先從N個數據對象任意選擇K個對象作為初始聚類中心，而對于所剩下的其他對象則根據它們與這些聚類中心的相似度量（距離）分別將它們分配給與其最相似的（聚類中心所代表的）聚類。然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）。不斷重復這一過程直到標準函數開始收斂為止。

2.2 K-均值算法的基本過程

輸入：聚類個數K,以及包含N個數據對象的數據庫。

輸出：K 個簇。

處理流程：

（1）從N個數據對象任意選擇K個對象作為初始聚類中心。

（2）循環下述流程（3）到（4）直到每聚類不再發生變化。

（3）根據每個聚類對象的均值（聚類中心對象），計算與這些中心對象的距離，并根據最小距離重新對相應對象進行劃分。

（4）重新計算每個有變化聚類的均值（中心對象）。

2.3 K-均值算法的優缺點

優點：K-均值算法實現起來比較簡單其計算復雜度為(nkt),其中,n為對象個數,k為聚類個數,t為循環次數,它具有可擴展性。

缺點：K-均值算法有以下四個缺點：

（1）K-均值算法只適用于聚類均值有意義的情況。

（2）用戶必須事先指定聚類個數K。

（3）K-均值算法還不適合發現非凸狀的聚類。

（4）K-均值算法對噪聲和異常數據非常敏感。因為這類數據可能會影響到各聚類的均值。

要想使一種聚類算法能克服以上所有缺點幾乎不可能。針對K-均值算法對異常點和噪聲敏感的這一缺點，Kaufman和Rousseeuw在文獻中提出了一種K-中心點算法,K-中心點算法不采用簇中對象的平均值作為參照點,而是選用簇中位置最中心的點（中心點）作為聚類的中心點。剩余的對象根據其與代表點的距離分配給最近的一個簇。然后反復地用非代表對象代替代表對象，以改進聚類的質量。

K-中心點聚類算法雖然比K-均值算法更健壯，但K-中心點聚類算法的執行代價要比K-均值算法要高得多。

3 基于最近鄰思想的K-均值算法

3.1 基本思想

在傳統K-均值算法中存在的一個主要缺點是對噪聲和異常點敏感，其原因是在K-均值算法的每一次迭代中，簇中的所有對象都參與計算平均值，再將新的平均值作為新的聚類中心進行計算，這樣噪聲和異常點都會參與平均值的計算。因而對平均值（聚類中心）有較大的影響。為了避免該情況發生，我們可以選擇參與平均值（聚類中心）計算的對象，不是全部的對象都參與計算平均值，而是選擇與上次聚類中心最近鄰的i（i

下面分析聚類初始點對該算法的影響。如果所選初始點為正常對象（不是異常）點，則其近鄰數一般都會大于i這種情況該中心點形成的簇不會被刪除。如果某一初始點選中了異常點，由于異常點與正常對象之間的距離較遠，則其近鄰對象一般都會小于i，這樣就可以將該中心點所形成的簇刪除，從而使聚類結果更加合理。不會受到異常點的影響。

在聚類過程中，如果某一聚類中心所形成的簇中包含有異常點，如果該簇中包含的對象個數小于i個，則該簇被刪除；如果該簇中對象的個數大于i個則在計算新的聚類中心時，異常點必定不會參與計算；如果該簇中對象的個數剛好是i個，則異常點參與計算。但經過數次迭代之后，該情況出現的概率很小。

綜上所述，該算法可以有效地去除噪聲（異常點）對傳統K-均值算法中平均值（聚類中心點）的影響，從而使聚類結果更加合理。

3.2 基本過程

輸入：簇的數K，包含n個對象的數據庫，i簇中參與計算平均值的對象數目。

輸出：K個或小于K個簇。

處理流程：

（1）任意選擇K個對象作為初始的簇中心。

（2）循環下述流程（3）（4）直到每個聚類不再發生變化。

（3）根據簇中前i個對象的平均值，將每個對象重新賦給最類似的簇。

（4）更新簇中聚類中心的值。（計算每個簇中與前一次聚類中心最鄰近的前i個對象平均值。）

3.3 時間復雜度分析

改進后的K-均值算法與傳統K-均值算法的最大區別就是取每個簇中與聚類中心最鄰近的i個對象作為計算平均值（下一次聚類中心）的對象。而不是計算簇中所有對象的平均值作為下一次聚類的中心。這樣就需要在計算平均值之前進行一次排序。排序的時間復雜度為km2(其中k為簇的個數，m為最大簇中對象的個數)。因此改進后的K均值算法的時間復雜度為k(m2+n)t（其中k為簇的數目，m為最大簇中對象的個數，n為全體數對象個數，t為迭代次數。影響m值的因素很多，如果則改進后的K均值算法與傳統的K_均值算法時間復雜性相同，但通常m2>n所以改進后的K平均算法要比傳統的K_均值算法時間復雜度要高。

4 實驗

我們將本算法應用到學生成績信息分析中，學生成績信息分析的目的是研究學生成績的分布情況，找出異常信息，為教務部門進行教學督查提供決策信息。

1）實驗環境

計算機配置：CPU Athlon 64 3000+，1GHz內存，160GB 硬盤

操作系統：Microsoft Windows XP

開發平臺：Microsoft Visual Studio 2005

開發語言：C#

數據庫：Microsoft SQL Server 2005

2）數據集

近兩年來收集的學生公修課學生成績信息，數據中含學生學號、姓名、高等數學成績、大學英語成績。

實驗比較了改進后的K-均值算法與傳統K-均值算法。實驗前首先將指定數據全部讀入內存，并完成相應的預處理工作。

3）實驗結果分析

通過實驗表明改進后的K-均值算法和傳統的K-均值算法用時基本相當，并沒有顯著增加用時，但聚類效果卻明顯改善。

5 結束語

在本文中，我們提出了一種基于最近鄰思想的K-均值算法，該算法在計算聚類中心點時，采用了一種最近鄰思想有效克服了‘噪聲’對平均值的影響，從而使聚類結果更加合理，并通過實際數據的實驗驗證明這種算法是有效的。如何將該算法應用到更多的實際數據的聚類是下一步的研究。

[1] Jiawei Han，Micheline Kamber 著；范明，孟小峰，等譯.數據挖掘概念與技術.機械工業出版社

[2] J.MacQueen. Some methods for classification and analysis of multivariate observations.Journal of the American Statistical Association, 83:715----728, 1967

[3] L.Kaufman and P.J.Rousseeuw. Finding Groups in Data:An Introduction to Cluster Analysis. New York:John Wiley&Sons,1990

[4] T.Zhang,R.Ramakrishnan, and M.Livny. BIRCH:An efficient data clustering method for very large databases.In Proc.1996 ACMSIGMOD Int.Conf.Management of data (SIGMOD’96),oages 103----114, Mibtreak,Cabada,June 1996

[5] S.Guha,R.Rastogi,and K.Shim. Cure:An efficient clustering algorithm for large databases.In Proc.1998 ACM-SIGMOD Int. Conf.Management of Data(SIGMOD’98), pages73—84, seattle,WA,June 1998

[6] S.Guha,R.Rastogi,and K.Shim. Rock:An Robust clustering algorithm for categorical attributes.In Proc.1999 Int.Conf.Data Engineering(ICDE’99), page512—521, Stdebet,Australia,Mar.1999

[7] G..Karypis,E.-H.Han, and V.Ku- mar. CHANELEON:A hierarchical clustering algorithm using dynamic modeling.COMPUTER,32:68—75,1999

[8] M.Ester,H.-P.Kriegel,J.sander, a nd X. Xu. Adensity-based algorithm for dircorvering clusters in large spatial databases. In Proc. 1996 Int.Conf. Knowledge Discovery and Data Mining (KDD’97),pages226—231,Portland, OR, Aug. 1996

10.3969/j.issn.1001-8972.2011.17.012

李金廣（1980-），男，碩士，河南息縣人，主要研究方向為數據挖掘、智能信息處理等。