肖洋，李平，王鵬，邱寧佳

（長春理工大學　計算機科學技術(shù)學院，長春　130022）

基于最小方差的自適應K-均值初始化方法

肖洋，李平，王鵬，邱寧佳

（長春理工大學計算機科學技術(shù)學院，長春130022）

K-均值算法對初始聚類中心敏感，聚類結(jié)果隨不同初始聚類中心波動。針對以上問題，提出一種基于最小方差的自適應K-均值初始化方法，使初始聚類中心分布在K個不同樣本密集區(qū)域，聚類結(jié)果收斂到全局最優(yōu)。首先，根據(jù)樣本空間分布信息，計算樣本方差得到樣本緊密度信息，并基于樣本緊密度選出滿足條件的候選初始聚類中心；然后，對候選初始聚類中心進行處理，篩選出K個初始聚類中心。實驗證明，算法具有較高的聚類性能，對噪聲和孤立點具有較好的魯棒性，且適合對大規(guī)模數(shù)據(jù)集聚類。

聚類；K-均值；方差；初始聚類中心

數(shù)據(jù)挖掘（Data Mining）就是從大量數(shù)據(jù)中獲取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過程。數(shù)據(jù)挖掘的主要方法有分類、聚類、關(guān)聯(lián)分析、回歸分析等。其中聚類分析［1-3］在數(shù)據(jù)挖掘領(lǐng)域的應用最為廣泛。聚類是一種無監(jiān)督的機器學習算法，通過獲取數(shù)據(jù)的內(nèi)在屬性，實現(xiàn)對數(shù)據(jù)的分類或壓縮，使得同一類中的對象之間具有較高的相似性，不同類中的對象之間具有較高的相異性。聚類分析廣泛應用于許多研究領(lǐng)域，如模式識別、數(shù)據(jù)挖掘、圖像處理、市場研究、數(shù)據(jù)分析等。對于不同的問題和用戶，國內(nèi)外學者研究出許多具有代表性的聚類算法，大致分為基于層次的方法、基于劃分的方法、基于網(wǎng)格的方法、基于密度的方法等。

K-均值是基于劃分方法的代表算法，算法思想簡單，易于實現(xiàn)，其實現(xiàn)版本廣泛應用于數(shù)據(jù)挖掘工具包中，應用范圍廣泛?？梢酝ㄟ^修改初始化、相似性度量、算法終止條件等部分適應新的應用環(huán)境。算法使用歐式距離度量數(shù)據(jù)對象間的相似性，對噪聲和孤立點比較敏感，使得K-均值算法中需要添加去除噪聲的步驟，增加了算法的復雜性。算法對初始聚類中心特別敏感，選取不同的初始聚類中心，會使算法很大程度上收斂到不同的聚類結(jié)果。如果選取較好的初始聚類中心，按照Forgy方法進行初始劃分，即根據(jù)最近鄰方法把樣本分配到相應的初始聚類中心代表的聚簇中，將會得到全局最優(yōu)的聚類結(jié)果。因此，怎樣確定有效的初始聚類中心，成為研究K-均值聚類算法的重要內(nèi)容。

本文在分析K-均值算法優(yōu)化初始聚類中心研究的基礎上，提出一種基于最小方差的自適應K-均值初始化方法。根據(jù)方差的定義可知，數(shù)據(jù)集中方差最小的樣本通常位于數(shù)據(jù)分布較為密集的區(qū)域，而數(shù)據(jù)較密集的區(qū)域常常是聚類中心的潛在區(qū)域。本文通過兩個步驟選取初始聚類中心。首先，根據(jù)樣本方差判斷樣本是否處于數(shù)據(jù)密集區(qū)域，若是，則把該樣本作為候選初始聚類中心，因此，可以得到一些處于數(shù)據(jù)密集區(qū)域的候選初始聚類中心；然后，對候選初始聚類中心進行篩選，選取K個聚類中心作為最終K-均值算法的初始聚類中心。在數(shù)據(jù)密集區(qū)域選取初始聚類中心，可以避免選擇噪聲或孤立點作為初始聚類中心，增強算法的抗噪性能，且該算法適合于大數(shù)據(jù)集聚類。

1　基于最小方差的自適應K-均值初始化方法

1.1相關(guān)研究

本文僅討論K-均值算法初始聚類中心選擇的方法。選擇初始聚類中心的方法隨著K-均值算法的產(chǎn)生而開始，最早的研究是1965年的Forgy方法。把數(shù)據(jù)集X中的每個樣本隨機分配給K個聚類，每個聚類的中心作為K個初始聚類中心，該方法缺少理論上的依據(jù)。Mac Queen提出兩種初始聚類中心選取方法。一種是把數(shù)據(jù)集X中前K個樣本作為K個初始聚類中心，該方法現(xiàn)應用在IBM SPSS統(tǒng)計軟件快速聚類的過程中，但選擇的初始聚類中心對數(shù)據(jù)輸入順序較敏感。另一種是K-均值算法廣泛使用的選取初始聚類中心的方法，即隨機選取數(shù)據(jù)集中K個樣本作為K個初始聚類中心，該方法可能會選擇噪聲或孤立點作為初始聚類中心，因此需要多次運行算法才能得到較好的聚類結(jié)果。Onoda等人［4］通過計算數(shù)據(jù)集的K個獨立成分，選擇到第i個獨立成分的余弦距離最小的樣本作為第i個初始聚類中心。文獻［5］把數(shù)據(jù)集平均分成若干等份，在每一等份上運行K-均值算法，在求出的所有聚類中心中選出相距較遠的聚類中心作為整個數(shù)據(jù)集的初始聚類中心。該方法在一定程度上克服了K-均值算法對初始聚類中心敏感的問題，但時間復雜度大，不適用大數(shù)據(jù)集聚類。文獻［6-8］根據(jù)樣本分布密度確定初始聚類中心。文獻［9］使用密度函數(shù)求出數(shù)據(jù)集的多個聚類中心，結(jié)合小類合并運算，避免算法收斂到局部最優(yōu)值。對于K-均值初始聚類中心選取方法的研究已有大量的研究成果，但是沒有出現(xiàn)公認最好的初始聚類中心選取的方法。當數(shù)據(jù)集中存在噪聲或孤立點時，已有的方法很難選出正確的初始聚類中心。

1.2K-均值聚類算法

K-均值聚類算法的基本思想是：首先在數(shù)據(jù)集中隨機選取k個樣本作為K個初始聚類中心，根據(jù)最小距離原則，把剩余樣本分配到與其距離最近的聚類中心所代表的聚簇中，計算每個聚簇的質(zhì)心作為新的聚類中心，反復迭代直到誤差平方準則函數(shù)SSE收斂。K-均值聚類算法的具體過程如下：

輸入：數(shù)據(jù)集X=｛x1，x2，...，xn｝，聚類個數(shù)K，誤差平方準則函數(shù)優(yōu)化精度ξ，使用歐式距離度量樣本間的相似性。

輸出：聚類中心V，每個樣本對應的類標簽T。

（1）在數(shù)據(jù)集X中隨機選取K個樣本作為初始聚類中心V=｛v1，v2，...，vk｝。

（2）把樣本xi分配到與其距離最小的聚類中心所代表的聚簇中，設置類別標簽為：

（3）計算每個聚簇的質(zhì)心作為新的聚類中心；

（4）計算誤差平方準則函數(shù)：

其中t是迭代次數(shù)，||vi是簇i中樣本個數(shù)。

（5）若|SSEt-1-SSEt|＜ξ，算法結(jié)束，輸出V 和T，否則，設置t=t+1，轉(zhuǎn)到（2）。

1.3基于最小方差的K-均值初始化方法

聚類中心應該位于數(shù)據(jù)集的密集區(qū)域，所以能夠代表相應的類簇。但是數(shù)據(jù)的密集性并沒有一個數(shù)學上的定義，而只是一個直觀的概念。本文引入樣本方差的概念，得到樣本緊密度信息，進而發(fā)現(xiàn)位于數(shù)據(jù)密集區(qū)域的樣本，然后對數(shù)據(jù)密集區(qū)域的樣本進行處理，選出K個樣本，作為K個初始聚類中心。

定義1：設數(shù)據(jù)集 X=｛xi|i=1，2，...，n｝，其中xi∈Rd，樣本xi的方差定義為：

其中d（xi，xj）是xi和xj之間的距離，計算公式為：

由上述定義可知，如果樣本xi的方差越小，說明xi周圍分布的數(shù)據(jù)越密集。反之，則說明xi周圍分布的數(shù)據(jù)越稀疏。這與直觀的數(shù)據(jù)密度相符。設定一個閾值?，如果樣本xi的方差小于?，則認為樣本xi處于某種程度的數(shù)據(jù)密集區(qū)域，因此，可以把樣本xi作為候選初始聚類中心。這是本文提出基于最小方差的自適應K-均值初始化方法的思想來源。本文提出的選取初始聚類中心的方法分為兩個過程：首先，依據(jù)樣本方差的定義，將方差小于閾值?的樣本作為候選初始聚類中心，使用自適應方法，設置合適的閾值，使得候選初始聚類中心Vh的個數(shù)M多于給定的聚類個數(shù)K；然后，從候選初始聚類中心集Vh中選擇方差最小的樣本作為第一個判斷中心，選擇距離已有判斷中心最遠的樣本作為下一個判斷中心，直到選出K個判斷中心，K個判斷中心代表K個聚簇，按照最小距離原則，把候選初始聚類中心內(nèi)其余樣本分配到距離最近的K個聚簇中，更新每個簇的質(zhì)心，重復該過程，直到聚簇中心不再變化，此時的K個聚簇中心就是本文算法得到的K個初始聚類中心。

圖1　算法流程圖

算法流程圖如圖1所示。根據(jù)方差的定義可知，計算n個樣本方差的時間復雜度為O（n2），本文算法應用到大數(shù)據(jù)集時，通過對大數(shù)據(jù)集進行采樣和降維操作，依然可以選擇合理的初始聚類中心，進而降低時間復雜度。實驗證明本文算法適合于大數(shù)據(jù)集聚類。數(shù)據(jù)集中噪聲或孤立點的方差較大，且遠遠大于閾值，引入樣本方差的概念選取候選初始聚類中心，使算法對噪聲和孤立點具有較強的魯棒性。測試數(shù)據(jù)集如表1所示。

表1　測試數(shù)據(jù)集

2　實驗結(jié)果與分析

硬件運行環(huán)境是Intel CPU，2.99G內(nèi)存，931G硬盤；軟件運行環(huán)境是WindowsXP操作系統(tǒng)，Visual Studio 2013開發(fā)平臺，算法使用C++作為編程語言。使用UCI中的標準數(shù)據(jù)作為測試數(shù)據(jù)，如表1所示。在測試數(shù)據(jù)上分別100次運行本文算法（A1），傳統(tǒng)K-均值算法（A2），K-Means++算法（A3），比較各個評價指標的均值。使用五個性能評價指標，驗證本文算法的有效性，五個指標分別為：

（1）起始誤差平方和（First SSE）：度量選擇的初始聚類中心的有效性，其值等于選出的初始聚類中心對應的誤差平方和，值越小，說明選出的初始聚類中心越接近正確值。

（2）終止誤差平方和（Last SSE）：度量選擇的初始聚類中心對整個聚類過程的有效性，其值等于聚類終止時對應的誤差平方和，值越小，說明本文算法有效性越高。如表2所示。

（3）運行時間（Time）：度量整個聚類過程所用的時間。

（4）Jaccard系數(shù)，使用正確聚類的樣本占屬于同一類簇的樣本的比例評價聚類結(jié)果。

（5）Adjusted Rand Index參數(shù)，用來衡量聚類結(jié)果與數(shù)據(jù)的外部標準類之間的一致程度。

算法在測試數(shù)據(jù)集上的起始誤差平方和（First SSE）和終止誤差平方和（Last SSE）比較結(jié)果如表2所示。運行總時間如表3所示。圖2是算法聚類結(jié)果的Jaccard系數(shù)比較。圖3是算法聚類結(jié)果的Adjusted Rand Index參數(shù)比較。

表2　起始誤差平方和終止誤差平方

表3　運行時間

圖2　Adjusted Rand Index參數(shù)比較

圖3　Jaccard系數(shù)比較

從表2可以看出，本文算法在所有數(shù)據(jù)集上的起始誤差平方和與終止誤差平方和的值最小，選擇的初始聚類中心與K-均值算法聚類之后的聚類中心間的距離最小。由圖2和圖3可知，在所有數(shù)據(jù)集上，本文算法聚類結(jié)果的各評價指標最大，在數(shù)據(jù)集Ecoli和Letter Recognition上三種算法聚類結(jié)果的評價指標比較接近，在數(shù)據(jù)集Olivetti和Segmentation上，本文算法與K-均值算法聚類結(jié)果的評價指標相差最大。其中在數(shù)據(jù)集Segmentation上，本文算法的聚類誤差平方和高于K-Means++算法，但聚類評價指標均低于K-Means++算法，說明數(shù)據(jù)集Segmentation的真實分布情況是類內(nèi)數(shù)據(jù)間的緊密性較弱。以上對比結(jié)果可知，本文算法優(yōu)于其它兩種算法，對K-均值算法的初始化具有很好的指導意義，提高了K-均值算法的聚類性能。本文算法引入樣本方差的概念選取初始聚類中心，而計算樣本方差是一個O（n2）時間復雜度的過程，由表3可知，本文算法的時間消耗高于其它算法，對大數(shù)據(jù)集聚類時，通過采樣和降維操作，可以降低本文算法的時間復雜度且不影響算法聚類性能。

本文算法使用歐式距離度量樣本間的相似度，若兩個樣本對應屬性的取值差異較大，則這兩個樣本間的距離較大。即屬性取值差異的大小，直接影響樣本間距離的大小?；谝陨纤枷耄瑢Υ髷?shù)據(jù)集聚類時，首先對大數(shù)據(jù)集進行采樣操作，然后排除數(shù)據(jù)集中取值范圍較小的屬性（降維操作），最后使用本文算法進行初始聚類中心的選取。為了證明對大數(shù)據(jù)集進行采樣和降維操作，不影響本文算法的有效性。使用不同的采樣率對數(shù)據(jù)集Olivetti和Letter Recognition進行采樣，采樣之后本文算法的聚類結(jié)果如表4所示。其中采樣率為1/2表示隨機選取原數(shù)據(jù)集的1/2進行初始聚類中心的選取。把數(shù)據(jù)集Olivetti和Letter Recognition中的屬性按照取值范圍由大到小降序排列，使用不同比例值進行降維。降維之后本文算法的聚類結(jié)果如表5所示。其中比例值1/2表示降序排列后選擇前1/2部分屬性進行初始聚類中心的選取。

由表4可知，使用不同采樣率，起始誤差平方和與終止誤差平方和的變化量非常小，但是運行時間卻大幅度減少。由表5可知，數(shù)據(jù)集3的維數(shù)較大，比例值低于1/9時，起始和終止誤差平方和出現(xiàn)略微變化，數(shù)據(jù)集5的維數(shù)較小，比例值低于1/2時，起始和終止誤差平方和出現(xiàn)略微變化。為了減小本文算法對大數(shù)據(jù)集聚類的時間復雜度，且不影響聚類效果，使用不同的采樣率對數(shù)據(jù)進行采樣，設置比例值為1/2對數(shù)據(jù)進行降維，然后使用本文算法選取初始聚類中心，聚類結(jié)果如表6所示。由表6可知，同時對大數(shù)據(jù)集進行采樣和降維，加大了聚類時間減小幅度，且不影響聚類效果。比例值為1/2對數(shù)據(jù)進行降維，適合數(shù)據(jù)集3的采樣率為1/5～1/10，適合數(shù)據(jù)集6的采樣率為1/6～1/2。實驗證明本文算法適合對大數(shù)據(jù)集聚類。

表4　采樣數(shù)據(jù)的聚類結(jié)果

表5　降維數(shù)據(jù)的聚類結(jié)果

表6　采樣和1/2降維數(shù)據(jù)的聚類結(jié)果

3　結(jié)論

本文提出基于最小方差的自適應K-均值初始化方法，可以發(fā)現(xiàn)數(shù)據(jù)集中較密集的區(qū)域，使選擇的初始聚類中心均分布在數(shù)據(jù)密集區(qū)域，進而保證初始聚類中心的準確性；算法可以避免選取噪聲或孤立點作為初始聚類中心，提升聚類性能；算法思想簡單，容易實現(xiàn)，且適合于大數(shù)據(jù)集聚類。

［1］ Yu H，Li Z，Yao N.Research on optimization method for K-Means clustering algorithm［J］.Journal of Chinese Computer Systems，2012，33（10）：2273-2277.

［2］ 倪巍偉，陳耿，崇志宏，等.面向聚類的數(shù)據(jù)隱藏發(fā)布研究［J］.計算機研究與發(fā)展，2012，49（5）：1095-1104.

［3］ 韓忠明，陳妮，張慧，等.一種非對稱距離下的層次聚類算法［J］.模式識別與人工智能，2014，27（5）：410-416.

［4］OnodaT，SakaiM，YamadaS.CarefulSeeding Method based on Independent Components AnalysisforK-meansClustering［J］.JournalofEmerging Technologies in Web Intelligence，2012，4（1）：51-59.

［5］ 韓曉紅，胡彧.K-means聚類算法研究［J］.太原理工大學學報，2009，40（3）：236-239.

［6］Lai Yuxia，Liu Jianping.Optimization study on initial centerofK-meansalgorithm［J］.ComputerEngineering and Applications，2008，44（10）：147-149.

［7］ Han Lingbo，Wang Qiang，Jiang Zhengfeng.Improved K-means initial clustering center selection algorithm［J］.Computer Engineering and Applications，2010，46 （17）：150-152.

［8］汪中，劉貴全，陳恩紅.一種優(yōu)化初始中心點的K-Means算法［J］.模式識別與人工智能，2009，22（2）：299-304.

［9］ Mao Shaoyang，Li Kenli.Research of optimal K-means initialclusteringcenter［J］.ComputerEngineering and Applications，2007，43（22）：179-181.

An Adaptive K-means Initialization Method Based on Minimum Deviation

XIAO Yang，LI Ping，WANG Peng，QIU Ningjia
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

K-means algorithm is sensitive to the initial cluster center；fluctuation of clustering results are following with different initial cluster centers.To solve these problems，in this paper，an adaptive K-means initialization method is proposed based on minimum variance；the initial clustering center is distributed in the K different sample density regions，clustering results of convergence to the global optimum.Firstly，according to the information of the space distribution of samples，the information of samples close degree is got by calculation of sample variance.In addition，based on samples close degree the qualified candidate initial cluster centers is selected；Then，the candidate initial cluster centers are dealt with and k initial cluster centers are filtered.The experiment proved that this algorithm has high clustering performance and good robustness for processing of the noise and the isolated point；it is suitable for clustering the large-scale data set.

clustering；K-means；deviation；initialized clustering centers

TP391

A

1672-9870（2015）05-0140-05

2015-03-30

肖洋（1989-），男，碩士研究生，E-mail：978996354@qq.com

李平（1958-），女，教授，E-mail：liping@cust.edu.cn