聚類(lèi)中心初始值選擇方法綜述

鄧旭冉，超木日力格，郭 靜

(1.中國(guó)科學(xué)技術(shù)大學(xué),安徽 230000；2.中國(guó)電子科學(xué)研究院，北京 100041)

0 引 言

隨著網(wǎng)絡(luò)和多媒體的蓬勃發(fā)展，人們可以收集的數(shù)據(jù)越來(lái)越多，例如視頻信息、音頻信息、文本信息、圖像信息等等。為了提高數(shù)據(jù)分析效率，人們更加傾向于通過(guò)機(jī)器學(xué)習(xí)的方式對(duì)海量的數(shù)據(jù)進(jìn)行處理。聚類(lèi)是模式識(shí)別和數(shù)據(jù)挖掘中廣為使用的數(shù)據(jù)分析手段。是無(wú)監(jiān)督學(xué)習(xí)領(lǐng)域近年來(lái)的研究熱點(diǎn)之一[1-2]。聚類(lèi)分析適用于很多不同類(lèi)型的數(shù)據(jù)集合，很多研究領(lǐng)域，如生物、醫(yī)藥、工程、語(yǔ)言、人類(lèi)學(xué)、心理學(xué)和市場(chǎng)學(xué)等[3]。

把單個(gè)樣本對(duì)象的集合以相似程度劃分為樣本組成的類(lèi)或簇的過(guò)程，稱(chēng)之為聚類(lèi)[4]。聚類(lèi)過(guò)程將樣本空間中的數(shù)據(jù)點(diǎn)劃分到不同的類(lèi)中，使得同一類(lèi)中的樣本間相似程度高，不同類(lèi)中的樣本間相似程度低，這就是聚類(lèi)的本質(zhì)。經(jīng)典的聚類(lèi)方法有基于劃分的方法、基于層次的方法、基于密度的方法，還有基于網(wǎng)格的方法及基于模型的方法。劃分聚類(lèi)算法是最常用的聚類(lèi)算法之一，經(jīng)典的K均值(K-means)聚類(lèi)算法[5-6,8]以及模糊C均值(FCM)聚類(lèi)算法[9]都屬于劃分聚類(lèi)算法。

在劃分聚類(lèi)問(wèn)題中，如何選擇初始聚類(lèi)中心一直是聚類(lèi)算法研究的關(guān)鍵論題之一。劃分聚類(lèi)算法需要事先給定初始聚類(lèi)中心，通過(guò)聚類(lèi)中心和隸屬度的迭代更新以得到對(duì)樣本集合的劃分。眾所周知,聚類(lèi)算法的結(jié)果和聚類(lèi)中心初始化密切相關(guān)，合理的初始化可以使得聚類(lèi)算法很快收斂，并得到較好的聚類(lèi)結(jié)果。但不合理的初始聚類(lèi)中心會(huì)導(dǎo)致算法的效率低下，甚至得到不好的聚類(lèi)結(jié)果。因此，如何選擇好的初始聚類(lèi)中心，對(duì)聚類(lèi)算法來(lái)說(shuō)是非常重要的。

選取初始類(lèi)中心的一種常用方法是：多次使用聚類(lèi)算法，每次選擇一組不同的隨機(jī)初始類(lèi)中心，然后從聚類(lèi)結(jié)果集中選取最優(yōu)聚類(lèi)結(jié)果，聚類(lèi)結(jié)果對(duì)應(yīng)的初始類(lèi)中心被認(rèn)為是最佳初始類(lèi)中心。這種策略簡(jiǎn)單，但計(jì)算量大且效果可能不好，這取決于數(shù)據(jù)集的大小和類(lèi)的個(gè)數(shù)。

第二種有效的選擇初始類(lèi)中心的方法是，隨機(jī)地選擇一個(gè)點(diǎn)，或者取樣本集的質(zhì)心作為第一個(gè)初始類(lèi)中心點(diǎn)。第二個(gè)初始類(lèi)中心點(diǎn)選擇離第一個(gè)點(diǎn)最遠(yuǎn)的點(diǎn)，選擇后續(xù)類(lèi)中心的方法是，選擇離已經(jīng)選取過(guò)的類(lèi)中心距離和最大的點(diǎn)。使用這種方法，確保了選擇的初始類(lèi)中心不僅是隨機(jī)的，而且是散開(kāi)的。但是這種方法運(yùn)算量較大，且容易選中離群點(diǎn)。

第三種，通過(guò)使用其他的聚類(lèi)方法，例如山峰聚類(lèi)[17]，聚類(lèi)結(jié)果作為其他聚類(lèi)算法的初始類(lèi)中心。顯然，這樣的聚類(lèi)中心初始化方法效果較好，因?yàn)橥ㄟ^(guò)使用前序聚類(lèi)算法已經(jīng)得到了數(shù)據(jù)集粗略的數(shù)據(jù)結(jié)構(gòu)，因此使用算法的結(jié)果作為后續(xù)聚類(lèi)算法的初始類(lèi)中心是合理的。

本文對(duì)目前常用的幾種聚類(lèi)中心初始化方法進(jìn)行總結(jié)。本文的章節(jié)安排如下：第一節(jié)中，重點(diǎn)介紹劃分聚類(lèi)算法的框架；第二節(jié)中，重點(diǎn)介紹幾類(lèi)聚類(lèi)中心初始化方法；第三節(jié)中，分析本文介紹的幾種聚類(lèi)中心初始化方法，對(duì)其性能以及適用的問(wèn)題進(jìn)行了對(duì)比；第四節(jié)中，對(duì)本文的內(nèi)容進(jìn)行總結(jié)，并展望未來(lái)的工作。

1 劃分聚類(lèi)算法

劃分聚類(lèi)算法的原理，簡(jiǎn)單來(lái)說(shuō)就是按照“類(lèi)內(nèi)間距小，類(lèi)間間距大”的原則對(duì)樣本集合進(jìn)行劃分。首先需要確定樣本最后要聚成幾類(lèi)，然后挑選幾個(gè)樣本點(diǎn)作為初始中心點(diǎn)，再然后依據(jù)隸屬度和聚類(lèi)中心的迭代更新公式給數(shù)據(jù)點(diǎn)做劃分，直到最后達(dá)到“類(lèi)內(nèi)的點(diǎn)都足夠近，類(lèi)間的點(diǎn)都足夠遠(yuǎn)”的聚類(lèi)效果[7]。

假設(shè)X={x1,x2,...,xn}是一S維數(shù)據(jù)集，X∈RS,數(shù)據(jù)集中的每個(gè)樣本xk∈X,k=1,2,...,n,均由一個(gè)S維特征向量表示。聚類(lèi)的目標(biāo)是將這n個(gè)數(shù)據(jù)點(diǎn)分為c類(lèi),V={vi},i=1,2,...,c表示各個(gè)聚類(lèi)中心。算法中用uik表示數(shù)據(jù)集X中的第k個(gè)樣本xk對(duì)第i類(lèi)的隸屬程度。劃分聚類(lèi)算法通過(guò)使非相似性指數(shù)的價(jià)值函數(shù)達(dá)到最小，從而得到數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的劃分。

劃分聚類(lèi)算法的迭代過(guò)程，具體的實(shí)現(xiàn)框架如下：

表1 劃分聚類(lèi)算法框架

上述迭代更新過(guò)程，對(duì)不同的劃分聚類(lèi)算法來(lái)說(shuō)，有不同的迭代更新公式。例如，K-means聚類(lèi)算法的迭代更新過(guò)程可以總結(jié)為[5]：

(1)

(2)

對(duì)于FCM算法，聚類(lèi)中心和隸屬度的迭代更新公式為[9]：

(3)

(4)

選擇合適的初始類(lèi)中心是劃分聚類(lèi)算法的關(guān)鍵步驟。常見(jiàn)的方法是隨機(jī)的選取初始質(zhì)類(lèi)中心，但是這樣的聚類(lèi)結(jié)果質(zhì)量往往很差。下節(jié)，我們主要介紹幾種劃分聚類(lèi)算法的初始聚類(lèi)中心選取方法。

2 聚類(lèi)中心初始化方法

本節(jié)主要介紹幾個(gè)聚類(lèi)中心初始化方法，并分析其優(yōu)缺點(diǎn)。包括：

2.1 基于k-means++算法的聚類(lèi)中心初始化

David等人于2007年提出的k-means++算法[10]，就屬于這類(lèi)聚類(lèi)中心初始化方法。k-means++算法隨機(jī)地選擇第一個(gè)類(lèi)中心，然后，選擇離最遠(yuǎn)的點(diǎn)作為第二個(gè)類(lèi)中心。以此類(lèi)推，直至獲得c個(gè)類(lèi)中心，則初始化結(jié)束。

圖1 k-means++算法聚類(lèi)中心選擇流程

選擇后續(xù)聚類(lèi)中心時(shí)需要計(jì)算該聚類(lèi)中心與前面幾個(gè)聚類(lèi)中心間的距離，計(jì)算方法如下[10]：

(5)

表2 k-means++算法

該方法主要考慮聚類(lèi)中心初始化時(shí)需要覆蓋整個(gè)數(shù)據(jù)集，使得聚類(lèi)中心在數(shù)據(jù)集中均勻的分布，從而保證初始的類(lèi)中心具有良好的代表性。通過(guò)該種聚類(lèi)中心的初始化方法，可能可能選中離群點(diǎn)。

2.2 基于子空間的k-means++算法

為了克服k-means++算法的缺點(diǎn)，Murat等人于2011年提出了一種改進(jìn)的聚類(lèi)中心初始化方法[11]。該方法與k-means++算法的聚類(lèi)中心初始化方法類(lèi)似，都是通過(guò)選擇分布于整個(gè)數(shù)據(jù)集的樣本點(diǎn)作為初始類(lèi)中心，從而提高類(lèi)中心對(duì)樣本的代表程度。

從樣本的s個(gè)維度中選擇兩個(gè)具有代表性的維度，建立選擇初始聚類(lèi)中心的子空間。首先，選擇樣本的主維度，也就是對(duì)樣本的區(qū)分程度最高的維度。計(jì)算方法如下[11]：

(6)

然后，通過(guò)計(jì)算主維度與其他維度間的相關(guān)系數(shù)，選擇第二個(gè)特征維度。計(jì)算方法如下[11]：

(7)

選擇CCll′最小的特征維度作為第二個(gè)維度，構(gòu)建樣本的子空間。在子空間中計(jì)算各個(gè)維度的均值[11]：

(8)

表3 基于子空間的k-means++算法

上述方法雖然在k-means++算法的基礎(chǔ)上進(jìn)行了改進(jìn)，從而使得聚類(lèi)中心初始化方法對(duì)異常點(diǎn)更魯棒，但對(duì)噪聲敏感。

2.3 基于mean-shift算法的聚類(lèi)中心初始化

為了使得聚類(lèi)中心初始化方法可以對(duì)抗噪聲點(diǎn)的影響，Jiangang Qiao等人[12]于2013年提出了一種基于mean-shift算法的聚類(lèi)中心初始化方法。

mean-shif算法[18,20]是一種無(wú)參數(shù)密度估計(jì)算法。該算法最先是以一種概率密度梯度函數(shù)的估計(jì)算法提出的。后引入了核函數(shù)和權(quán)重系數(shù)，慢慢發(fā)展為現(xiàn)今的迭代算法。mean-shift算法的核心思想為：先計(jì)算出當(dāng)前像素點(diǎn)的偏移均值，將該點(diǎn)移動(dòng)到其偏移均值，并以此為起點(diǎn)繼續(xù)移動(dòng)直至滿足一定條件后停止迭代。計(jì)算聚類(lèi)中心候選點(diǎn)和候選區(qū)域樣本間的相似性，用相似性函數(shù)的最大值求目標(biāo)的Mean Shift向量，將聚類(lèi)中心候選點(diǎn)移動(dòng)到偏移均值，一直迭代運(yùn)算直至聚類(lèi)中心候選點(diǎn)不發(fā)生偏移[19]。

首先，該方法的第一步與基于子空間的k-means++算法相同，需要通過(guò)計(jì)算得到樣本的兩個(gè)具有代表性的維度，建立只有這兩個(gè)維度的樣本集X′。

其次，選擇任意一點(diǎn)，最為初始類(lèi)中心候選。對(duì)該樣本使用以R為半徑的mean-shift算法，以使得初始類(lèi)中心在樣本密度較高的區(qū)域，這樣就可以避免噪聲點(diǎn)的影響。mean-shift算法半徑R的計(jì)算方法為：

(1)從X′隨機(jī)選取100個(gè)樣本點(diǎn)；

(2)計(jì)算這100個(gè)樣本點(diǎn)與其最近鄰樣本間的距離；

(3)mean-shift算法半徑R等于最大距離的4倍。

最后，與基于子空間的k-means++算法相似，根據(jù)樣本點(diǎn)與已有類(lèi)中心間的距離選擇初始類(lèi)中心。但每次選擇類(lèi)中心時(shí)均通過(guò)mean-shift算法對(duì)其進(jìn)行修正。

圖2 基于mean-shift算法的聚類(lèi)中心初始化方法流程

該方法對(duì)噪聲點(diǎn)不敏感，通過(guò)使用mean-shift算法，使得得到的初始類(lèi)中心在樣本點(diǎn)密度較高的區(qū)域，因此初始聚類(lèi)中心對(duì)樣本點(diǎn)的代表程度較高。

2.4 基于山峰聚類(lèi)的聚類(lèi)中心初始化

一些聚類(lèi)算法的聚類(lèi)結(jié)果，也可以用于其他聚類(lèi)算法的初始化。例如，山峰聚類(lèi)算法因?yàn)槠湫矢?、聚?lèi)結(jié)果可靠等性能，一般可用于其他復(fù)雜聚類(lèi)算法的聚類(lèi)中心初始化。

Yager和Filev在1994年提出的一種聚類(lèi)方法，可以有效快速的估計(jì)聚類(lèi)中心[17]。它的基本思想是通過(guò)構(gòu)造密度函數(shù)，尋找樣本密度較高的點(diǎn)作為聚類(lèi)中心，再通過(guò)計(jì)算樣本與聚類(lèi)中心間的距離，實(shí)現(xiàn)樣本的聚類(lèi)。

第一步：在數(shù)據(jù)空間上構(gòu)造網(wǎng)格，如圖3所示，網(wǎng)格的交叉部分構(gòu)成了聚類(lèi)中心的候選集，記為V。一般情況下，取網(wǎng)格間隔均勻，也可以根據(jù)數(shù)據(jù)分布的先驗(yàn)信息使用非均勻的網(wǎng)格。網(wǎng)格的密度與聚類(lèi)的精度以及聚類(lèi)的速率有著密切的關(guān)系。網(wǎng)格劃分越細(xì)，聚類(lèi)中心候選集越大，增大了所需的計(jì)算量，聚類(lèi)就越慢。

圖3 網(wǎng)格示意圖

第二步：構(gòu)造山峰函數(shù)(密度函數(shù))，該步是山峰聚類(lèi)算法的核心。通過(guò)山峰函數(shù)，計(jì)算數(shù)據(jù)空間中密度較大的點(diǎn)。一般，使用高斯密度函數(shù)作為山峰函數(shù)。點(diǎn)vi山峰函數(shù)的高度為[17]：

(9)

其中，δ是一個(gè)固定常數(shù)。式(9)表明，點(diǎn)vi處的山峰高度由數(shù)據(jù)集中的所有樣本點(diǎn)進(jìn)行計(jì)算。顯然，數(shù)據(jù)點(diǎn)與vi間的距離越大，對(duì)山峰函數(shù)的貢獻(xiàn)越小。因此，當(dāng)聚類(lèi)候選中心vi周?chē)臄?shù)據(jù)增加時(shí)，該點(diǎn)的山峰高度更高，該點(diǎn)被選取為聚類(lèi)中心的概率越大。通過(guò)計(jì)算山峰函數(shù)，可以得到山峰函數(shù)分布圖。

第三步：得到聚類(lèi)中心。首先，在聚類(lèi)中心候選集V中選取山峰函數(shù)最大的點(diǎn)作為第一個(gè)聚類(lèi)中心，而后通過(guò)順序地削去山峰函數(shù)大的點(diǎn)及該點(diǎn)周?chē)狞c(diǎn)，尋找下個(gè)聚類(lèi)中心。

從山峰聚類(lèi)的過(guò)程可以看出，山峰聚類(lèi)結(jié)果中的聚類(lèi)中心分布在樣本密度較高的區(qū)域，并且聚類(lèi)的個(gè)數(shù)是不需要事先指定的。

2.5 基于高密度區(qū)域快速搜索聚類(lèi)算法

有的聚類(lèi)算法將聚類(lèi)中心的選擇與聚類(lèi)過(guò)程結(jié)合起來(lái)，避免對(duì)聚類(lèi)中心的初始化。山峰聚類(lèi)算法在尋找聚類(lèi)中心時(shí)是通過(guò)順序的削去山峰來(lái)實(shí)現(xiàn)的，而在實(shí)際中，當(dāng)類(lèi)個(gè)數(shù)非常大時(shí)，通過(guò)山峰聚類(lèi)算法進(jìn)行聚類(lèi)中心的發(fā)現(xiàn)其時(shí)空代價(jià)過(guò)大。Alex Rodriguez和 Alessandro Laio[21]于2014年在《自然》雜志上提出了一種很簡(jiǎn)潔優(yōu)美的聚類(lèi)算法, 可以識(shí)別各種形狀的類(lèi)簇, 并且其參數(shù)很容易確定。

該算法的假設(shè)是, 類(lèi)簇的中心由一些局部密度比較低的點(diǎn)圍繞, 并且這些點(diǎn)距離其他高局部密度點(diǎn)的距離都比較大。首先定義兩個(gè)值: 局部密度ρi以及到高局部密度點(diǎn)的距離δi[21]:

(10)

(11)

其中：如果x<0，χ(x)=1，否則χ(x)=0。dc是一個(gè)截?cái)嗑嚯x, 是一個(gè)超參數(shù)。所以ρi相當(dāng)于距離點(diǎn)i的距離小于dc的點(diǎn)的個(gè)數(shù)。由于該算法只對(duì)ρi的相對(duì)值敏感, 所以對(duì)dc的選擇比較魯棒, 一種推薦做法是選擇dc使得平均每個(gè)點(diǎn)的近鄰數(shù)為所有點(diǎn)的1%～2%。對(duì)于密度最大的點(diǎn)，設(shè)置δi=maxj(dij)。

那些有著比較大的局部密度ρi和很大的δi的點(diǎn)被認(rèn)為是類(lèi)簇的中心。局部密度較小但是δi較大的點(diǎn)是異常點(diǎn).在確定了類(lèi)簇中心之后, 所有其他點(diǎn)屬于距離其最近的類(lèi)簇中心所代表的類(lèi)簇。

圖4(A)中為樣本點(diǎn)，圖4(B)中通過(guò)式(10)和式(11)計(jì)算局部密度ρi和δi后構(gòu)建的決策圖。從圖4可以看出，可以看到, 點(diǎn)1和點(diǎn)10兩個(gè)點(diǎn)的ρi和δi都比較大, 可以作為聚類(lèi)中心點(diǎn)，而 點(diǎn)26、點(diǎn) 27和點(diǎn) 28的δi也比較大, 但是ρi較小, 所以屬于異常點(diǎn)。

圖4 基于高密度區(qū)域快速搜索聚類(lèi)算法

通過(guò)該聚類(lèi)方法，可以避免對(duì)聚類(lèi)中心的初始化，也可以得到較好的聚類(lèi)結(jié)果。顯然，該聚類(lèi)方法也可用于尋找聚類(lèi)中心，并作為其他聚類(lèi)算法的類(lèi)中心初始值。

3 聚類(lèi)中心初始化方法分析

本文介紹的幾種聚類(lèi)方法，存在優(yōu)缺點(diǎn)，且適用的聚類(lèi)場(chǎng)景也不一樣。本節(jié)中，主要對(duì)這幾種聚類(lèi)方法進(jìn)行分析比對(duì)。

基于k-means++算法的聚類(lèi)中心初始化算法和基于子空間的k-means++算法都是需要制定類(lèi)中心個(gè)數(shù)的聚類(lèi)中心初始化方法。顯然，在對(duì)數(shù)據(jù)集的結(jié)構(gòu)不了解的情況下指定聚類(lèi)個(gè)數(shù)是比較困難的。同時(shí)，這兩類(lèi)方法都是在得到第一個(gè)聚類(lèi)中心后，通過(guò)一定的方式尋找后續(xù)的聚類(lèi)中心，因此該方法對(duì)噪聲敏感，如果第一個(gè)聚類(lèi)中心偏離較大時(shí)，得到的聚類(lèi)中心初始化結(jié)果也會(huì)較差。

雖然基于mean-shift的聚類(lèi)中心初始化算法也是通過(guò)獲得第一個(gè)聚類(lèi)中心，然后根據(jù)一定規(guī)律尋找后續(xù)的聚類(lèi)中心的方法，但是因?yàn)閙ean-shift方法的性質(zhì)，使得得到的初始類(lèi)中心在樣本點(diǎn)密度較高的區(qū)域，對(duì)樣本點(diǎn)的代表程度較高，因此該方法對(duì)噪聲魯棒。上述三種方法都是對(duì)聚類(lèi)中心的初始化方法，后續(xù)對(duì)數(shù)據(jù)的聚類(lèi)需要使用其他的聚類(lèi)算法，例如k-means聚類(lèi)算法等，對(duì)數(shù)據(jù)集進(jìn)行劃分。

山峰聚類(lèi)是一種常用聚類(lèi)中心初始化方法，該方法與基于mean-shift的聚類(lèi)中心初始化算法一樣，都是基于類(lèi)中心應(yīng)選在數(shù)據(jù)點(diǎn)密度較高的區(qū)域的假設(shè)。根據(jù)山峰函數(shù)計(jì)算數(shù)據(jù)點(diǎn)的密度，不斷選擇山峰作為聚類(lèi)中心候選點(diǎn)，從而得到數(shù)據(jù)的類(lèi)中心。顯然，該方法也存在需要指定類(lèi)中心個(gè)數(shù)的問(wèn)題，但該方法計(jì)算簡(jiǎn)單，且得到聚類(lèi)中心的同時(shí)，也可以得到數(shù)據(jù)的劃分。

基于高密度區(qū)域快速搜索聚類(lèi)算法，在山峰聚類(lèi)的基礎(chǔ)上，通過(guò)引入新的函數(shù)，可以一次性得到數(shù)據(jù)的聚類(lèi)中心以及數(shù)據(jù)的劃分，因此該算法提出后得到了廣泛的應(yīng)用。

綜上所述，這幾類(lèi)聚類(lèi)算法各有其優(yōu)缺點(diǎn)，也有其適用的聚類(lèi)場(chǎng)景。

4 結(jié) 語(yǔ)

聚類(lèi)算法在許多科學(xué)領(lǐng)域均得到了非常廣泛的應(yīng)用，同時(shí)，怎樣提升聚類(lèi)結(jié)果的精確度，也成為了機(jī)器學(xué)習(xí)研究的熱點(diǎn)。聚類(lèi)算法初始化的好壞決定著聚類(lèi)算法結(jié)果的優(yōu)劣，近年來(lái)，專(zhuān)家學(xué)者們對(duì)如何合理的對(duì)聚類(lèi)中心進(jìn)行初始化做了大量的研究，為得到更好地聚類(lèi)結(jié)果做出了顯著地貢獻(xiàn)。本文旨在介紹近年來(lái)提出的聚類(lèi)中心初始化方法，分析其優(yōu)劣性質(zhì)，為選擇聚類(lèi)中心初始化方法提供參考。當(dāng)然，本文短短的篇幅不足以概括所有的聚類(lèi)中心初始化方法，作者只是將最新的成果羅列出來(lái)，因此收集更多地聚類(lèi)中心初始化方法并分析其優(yōu)缺點(diǎn)也是下一步工作的重點(diǎn)。