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

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

基于最小方差的自適應(yīng)K-均值初始化方法

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

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

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

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

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

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

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

1　基于最小方差的自適應(yīng)K-均值初始化方法

1.1相關(guān)研究

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

1.2K-均值聚類算法

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

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

輸出：聚類中心V，每個(gè)樣本對(duì)應(yīng)的類標(biāo)簽T。

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

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

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

（4）計(jì)算誤差平方準(zhǔn)則函數(shù)：

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

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

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

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

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

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

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

圖1　算法流程圖

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

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

2　實(shí)驗(yàn)結(jié)果與分析

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

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

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

（3）運(yùn)行時(shí)間（Time）：度量整個(gè)聚類過程所用的時(shí)間。

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

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

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

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

表3　運(yùn)行時(shí)間

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

圖3　Jaccard系數(shù)比較

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

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

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

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

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

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

3　結(jié)論

本文提出基于最小方差的自適應(yīng)K-均值初始化方法，可以發(fā)現(xiàn)數(shù)據(jù)集中較密集的區(qū)域，使選擇的初始聚類中心均分布在數(shù)據(jù)密集區(qū)域，進(jìn)而保證初始聚類中心的準(zhǔn)確性；算法可以避免選取噪聲或孤立點(diǎn)作為初始聚類中心，提升聚類性能；算法思想簡單，容易實(shí)現(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］.計(jì)算機(jī)研究與發(fā)展，2012，49（5）：1095-1104.

［3］ 韓忠明，陳妮，張慧，等.一種非對(duì)稱距離下的層次聚類算法［J］.模式識(shí)別與人工智能，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］.太原理工大學(xué)學(xué)報(bào)，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)化初始中心點(diǎn)的K-Means算法［J］.模式識(shí)別與人工智能，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