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

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

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

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

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

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

數(shù)據(jù)聚類是數(shù)據(jù)挖掘的一個(gè)非常活躍的研究方向。聚類在文獻(xiàn)[1]中定義為：將數(shù)據(jù)對(duì)象進(jìn)行分組，成為多個(gè)類或簇。在聚類過(guò)程中無(wú)須用戶提供先驗(yàn)的分類知識(shí)，而是根據(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é)束語(yǔ)。

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

2.1 基本思想

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

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

2.2 K-均值算法的基本過(guò)程

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

輸出：K 個(gè)簇。

處理流程：

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

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

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

（4）重新計(jì)算每個(gè)有變化聚類的均值（中心對(duì)象）。

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

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

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

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

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

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

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

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

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

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

3.1 基本思想

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

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

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

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

3.2 基本過(guò)程

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

輸出：K個(gè)或小于K個(gè)簇。

處理流程：

（1）任意選擇K個(gè)對(duì)象作為初始的簇中心。

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

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

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

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

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

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

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

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

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

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

開(kāi)發(fā)平臺(tái)：Microsoft Visual Studio 2005

開(kāi)發(fā)語(yǔ)言：C#

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

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

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

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

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

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

5 結(jié)束語(yǔ)

在本文中，我們提出了一種基于最近鄰思想的K-均值算法，該算法在計(jì)算聚類中心點(diǎn)時(shí)，采用了一種最近鄰思想有效克服了‘噪聲’對(duì)平均值的影響，從而使聚類結(jié)果更加合理，并通過(guò)實(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ù)挖掘、智能信息處理等。