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

李金廣 劉家磊 安陽工學(xué)院

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

李金廣 劉家磊 安陽工學(xué)院

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

數(shù)據(jù)挖掘；聚類；K-均值。

1 當(dāng)前主要的聚類算法

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

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

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

3）基于密度的方法，如DBSCAN文獻(xiàn)[8]；

4）基于網(wǎng)格的方法，如STING；

5）基于模型的方法。

全文內(nèi)容安排如下：第二節(jié)介紹傳統(tǒng)K-均值算法的基本思想，并進(jìn)行特性分析；第三節(jié)介紹改進(jìn)的K-均值算法；第四節(jié)實(shí)驗(yàn)；第五節(jié)結(jié)束語。

2 傳統(tǒng)的K-均值算法

2.1 基本思想

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

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

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

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

輸出：K 個簇。

處理流程：

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

（2）循環(huán)下述流程（3）到（4）直到每聚類不再發(fā)生變化。

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

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

2.3 K-均值算法的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：K-均值算法實(shí)現(xiàn)起來比較簡單其計算復(fù)雜度為(nkt),其中,n為對象個數(shù),k為聚類個數(shù),t為循環(huán)次數(shù),它具有可擴(kuò)展性。

缺點(diǎn)：K-均值算法有以下四個缺點(diǎn)：

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

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

（3）K-均值算法還不適合發(fā)現(xiàn)非凸?fàn)畹木垲悺?/p>

（4）K-均值算法對噪聲和異常數(shù)據(jù)非常敏感。因?yàn)檫@類數(shù)據(jù)可能會影響到各聚類的均值。

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

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

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

3.1 基本思想

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

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

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

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

3.2 基本過程

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

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

處理流程：

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

（2）循環(huán)下述流程（3）（4）直到每個聚類不再發(fā)生變化。

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

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

3.3 時間復(fù)雜度分析

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

4 實(shí)驗(yàn)

我們將本算法應(yīng)用到學(xué)生成績信息分析中，學(xué)生成績信息分析的目的是研究學(xué)生成績的分布情況，找出異常信息，為教務(wù)部門進(jìn)行教學(xué)督查提供決策信息。

1）實(shí)驗(yàn)環(huán)境

計算機(jī)配置：CPU Athlon 64 3000+，1GHz內(nèi)存，160GB 硬盤

操作系統(tǒng)：Microsoft Windows XP

開發(fā)平臺：Microsoft Visual Studio 2005

開發(fā)語言：C#

數(shù)據(jù)庫：Microsoft SQL Server 2005

2）數(shù)據(jù)集

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

實(shí)驗(yàn)比較了改進(jìn)后的K-均值算法與傳統(tǒng)K-均值算法。實(shí)驗(yàn)前首先將指定數(shù)據(jù)全部讀入內(nèi)存，并完成相應(yīng)的預(yù)處理工作。

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

通過實(shí)驗(yàn)表明改進(jìn)后的K-均值算法和傳統(tǒng)的K-均值算法用時基本相當(dāng)，并沒有顯著增加用時，但聚類效果卻明顯改善。

5 結(jié)束語

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

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

[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-），男，碩士，河南息縣人，主要研究方向?yàn)閿?shù)據(jù)挖掘、智能信息處理等。