X-means：一種針對(duì)聚類個(gè)數(shù)的K-means算法改進(jìn)

1、精品好資料學(xué)習(xí)推薦X-means：一種針對(duì)聚類個(gè)數(shù)的K-means算法改進(jìn)摘要盡管K-means很受歡迎，但是他有不可避免的三個(gè)缺點(diǎn)：1、它的計(jì)算規(guī)模是受限的。2、它的聚類個(gè)數(shù)K必須是由用戶手動(dòng)指定的。3、它的搜索是基于局部極小值的。在本文中，我們引入了前兩種問題的解決辦法，而針對(duì)最后一個(gè)問題，我們提出了一種局部補(bǔ)救的措施。根據(jù)先前有關(guān)算法改進(jìn)的工作，我們引入了一種根據(jù)BIC（Bayesian Information Criterion）或者AIC（Akaike information criterion）得分機(jī)制而確定聚類個(gè)數(shù)的算法，本文的創(chuàng)新點(diǎn)包括：兩種新的利用充分統(tǒng)計(jì)量的方式，還有一種有

2、效地測(cè)試方法，這種方法在K-means算法中可以用來篩選最優(yōu)的子集。通過這樣的方式可以得到一種快速的、基于統(tǒng)計(jì)學(xué)的算法，這種算法可以實(shí)現(xiàn)輸出聚類個(gè)數(shù)以及他們的參量值。實(shí)驗(yàn)表明，這種技術(shù)可以更科學(xué)的找出聚類個(gè)數(shù)K值，比利用不同的K值而重復(fù)使用K-means算法更快速。1、 介紹K-means算法在處理量化數(shù)據(jù)中已經(jīng)用了很長(zhǎng)時(shí)間了，它的吸引力主要在于它很簡(jiǎn)單，并且算法是局部最小化收斂的。但是它有三點(diǎn)不可避免的缺點(diǎn)：首先，它在完成每次迭代的過程中要耗費(fèi)大量的時(shí)間，并且它所能處理的數(shù)據(jù)量也是很少的。第二，聚類個(gè)數(shù)K值必須由用戶自身來定義。第三，當(dāng)限定了一個(gè)確定的K值時(shí)，K-means算法往往比一個(gè)動(dòng)態(tài)

3、K值的算法表現(xiàn)的更差。我們要提供針對(duì)這些問題的解決辦法，通過嵌入樹型的數(shù)據(jù)集以及將節(jié)點(diǎn)存儲(chǔ)為充分統(tǒng)計(jì)變量的方式來大幅度提高算法的計(jì)算速度。確定中心的分析算法要考慮到泰森多邊形邊界的幾何中心，并且在估計(jì)過程的任何地方都不能存在近似的方法。另外還有一種估計(jì)方法，“黑名單”，這個(gè)列表中將會(huì)包含那些需要在指定的區(qū)域內(nèi)被考慮的圖心。這種方法不僅在準(zhǔn)確度上以及處理數(shù)據(jù)的規(guī)模上都表現(xiàn)的非常好，而這個(gè)快速算法在X-means聚類算法當(dāng)中充當(dāng)了結(jié)構(gòu)算法的作用，通過它可以很快的估計(jì)K值。這個(gè)算法在每次使用K-means算法之后進(jìn)行，來決定一個(gè)簇是否應(yīng)該為了更好的適應(yīng)這個(gè)數(shù)據(jù)集而被分開。決定的依據(jù)是BIC得分。在本

4、文中，我們闡述了“黑名單”方法如何對(duì)現(xiàn)有的幾何中心計(jì)算BIC得分，并且這些幾何中心所產(chǎn)生的子類花費(fèi)不能比一個(gè)單純的K-means聚類算法更高。更進(jìn)一步的，我們還通過緩存狀態(tài)信息以及估計(jì)是否需要重新計(jì)算的方法來改善估計(jì)方法。我們已經(jīng)用X-means算法進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了它的確比猜K值更加科學(xué)有效。X-means算法可以在人造的或者是真實(shí)數(shù)據(jù)中表現(xiàn)的更好，通過BIC得分機(jī)制。它的運(yùn)行速度也是比K-means更快的。2、 定義我們首先描述簡(jiǎn)單的K-means算法應(yīng)該考慮哪些因素。通過K-means可以把一定量的數(shù)據(jù)集分為K個(gè)數(shù)據(jù)子集，這K個(gè)數(shù)據(jù)子集分別圍繞著K個(gè)聚類中心。這種算法保持著K個(gè)聚類中心不

5、變，并且通過迭代不斷調(diào)整這K個(gè)聚類中心。在第一次迭代開始之前，K個(gè)聚類中心都是隨機(jī)選取的，算法當(dāng)聚類中心不再變化的時(shí)候返回最佳的結(jié)果，在每一次迭代中，算法都要進(jìn)行如下的動(dòng)作：1、 對(duì)于每一個(gè)節(jié)點(diǎn)向量，找到距離它最近的聚類中心，歸入此類。2、 重新評(píng)估每一個(gè)圖心的位置，對(duì)于每一個(gè)圖心，必須是簇的質(zhì)心。K-means聚類算法通過局部最小化每個(gè)向量到對(duì)應(yīng)圖心的距離來實(shí)現(xiàn)聚類。同時(shí)，它處理真實(shí)數(shù)據(jù)時(shí)是非常慢的。許多情況下，真實(shí)的數(shù)據(jù)不能直接用K-means進(jìn)行聚類，而要經(jīng)過二次抽樣篩選之后再進(jìn)行聚類。Ester曾經(jīng)提出了一種可以從樹形數(shù)據(jù)中獲得平衡的抽樣數(shù)據(jù)的方法。Ng和Han曾經(jīng)提出了一種可以指導(dǎo)概

6、率空間對(duì)輸入向量的檢索模擬模型。Zhang則提出了一種基于充分統(tǒng)計(jì)學(xué)的樹形模型?？梢员挥脕懋惓ＷR(shí)別以及快速計(jì)算。然而，這種聚類器是近似的，并且要依靠許多的近似值。要注意雖然剛開始聚類的聚類中心是隨便選取的，但是對(duì)于K-means算法來說，這K個(gè)聚類中心是實(shí)實(shí)在在確定了的。如果你選取了不科學(xué)的聚類中心，就有可能影響到最后的聚類結(jié)果以及算法的效率。Bradley和Fayyad討論了通過二次抽樣和平滑數(shù)據(jù)的方法來更加科學(xué)的選取聚類中心。在本文的剩余部分，我們將會(huì)用uj來表示第J個(gè)質(zhì)心，用i表示距離向量i最近的聚類質(zhì)心，例如說，ui表示在迭代中距離i最近的聚類質(zhì)心。D表示輸入的數(shù)據(jù)節(jié)點(diǎn)，而Di表示所有

7、距離ui最近的節(jié)點(diǎn)集。R為D中節(jié)點(diǎn)的個(gè)數(shù)，Ri為Di中節(jié)點(diǎn)的個(gè)數(shù)。分布數(shù)量是M，高斯協(xié)方差矩陣為=diag(*)3、 K值的估計(jì)到目前為止，我們所描述的算法是K-means聚類算法的相關(guān)步驟，K值是由用戶確定的，我們現(xiàn)在要描述X-means算法如何確定K值，通過BIC得分的優(yōu)劣，通過聚類算法我們不僅僅要得到一些比較合理的聚類中心還要得到一個(gè)合理的K值。首先，我們描述整個(gè)確定K值的過程，不要太在意算法的細(xì)節(jié)。接下來，我們推導(dǎo)出適用于不同統(tǒng)計(jì)模型的測(cè)試集。再然后，我們回到高層的算法描述，顯示算法是如何利用黑名單的思想將大量的數(shù)據(jù)存儲(chǔ)在樹形的數(shù)據(jù)集中。3.1模型檢索本質(zhì)上，算法的運(yùn)行過程主要是先給定

8、一個(gè)聚類個(gè)數(shù)的下限，然后不停的用K-means算法進(jìn)行迭代，直到達(dá)到最好的BIC得分的結(jié)果，然后返回聚類結(jié)果。迭代算法中主要包括以下動(dòng)作：X-means：1、 改變參數(shù)2、 改變結(jié)構(gòu)3、 如果K大于最高限定的K值則返回結(jié)果，否則回到第一步對(duì)參數(shù)的改變過程很簡(jiǎn)單，就是傳統(tǒng)的K-means收斂的過程。第二步中改變結(jié)構(gòu)式算法的核心步驟，通過將一個(gè)大的聚類一分為二，然后決定新的質(zhì)心應(yīng)該出現(xiàn)的地方，我們要通過BIC得分來決定是否對(duì)聚類進(jìn)行分割。分裂觀點(diǎn)1：第一個(gè)想法是先選擇一個(gè)重心，然后再它附近再產(chǎn)生一個(gè)重心，然后評(píng)價(jià)是否兩個(gè)重心的情況下聚類表現(xiàn)的更好，如果是則分割聚類，如果不是則返回上一步。這個(gè)過程需

9、要在X-means算法聚類的整個(gè)過程中反復(fù)出現(xiàn)，直到返回最佳的聚類結(jié)果，算法的時(shí)間復(fù)雜度為O(Kmax)。但是如果沒有得到BIC得分的提高應(yīng)該怎么辦呢，我們就必須對(duì)每一個(gè)聚類中心都采取這種方式進(jìn)行處理，所以每一次都需要調(diào)用一次K-means算法，也就是說我們?cè)诩右粋€(gè)聚類中心的時(shí)候需要運(yùn)行很多次K-means，耗費(fèi)了太多時(shí)間。分裂觀點(diǎn)2：將一個(gè)完整的簇分為兩個(gè)部分，第二個(gè)想法用于SPLITLOOP系統(tǒng)，實(shí)現(xiàn)高斯混合模型識(shí)別。通過一些啟發(fā)式的標(biāo)準(zhǔn)來簡(jiǎn)單的分割完整簇。分割他們時(shí)要調(diào)用K-means算法并且計(jì)算分割后的成績(jī)是否比分割之前更好，如果更好的話就返回分割之后的結(jié)果，這是一個(gè)比較大的改善，因?yàn)?/p>

10、通過這種方法進(jìn)行聚類的時(shí)間復(fù)雜度只有O(Logk)。不斷的改善數(shù)據(jù)結(jié)構(gòu)，直到X-means算法結(jié)束，但是這種思想的問題在于：什么樣的啟發(fā)機(jī)制用來分割聚類呢？還有圖心應(yīng)該擁有多大的規(guī)模呢？是圖心決定了圖結(jié)構(gòu)的變化嗎？如果只有一個(gè)或者是兩個(gè)簇需要被分割，其他都不需要的話這種算法仍然是科學(xué)的嗎？我們的解決辦法同時(shí)考慮了想法一和想法二的優(yōu)點(diǎn)，同時(shí)還避免了他們的缺點(diǎn)，并且我們的解決辦法可以在很短時(shí)間內(nèi)實(shí)現(xiàn)。我們將通過一個(gè)例子來解釋。圖1展示了擁有三個(gè)圖心的一個(gè)穩(wěn)定的K-means聚類。每一個(gè)圖心所擁有的區(qū)域邊界也在圖中展示出來了，對(duì)這個(gè)圖的結(jié)構(gòu)改進(jìn)的過程如下：首先將每一個(gè)簇分為兩個(gè)孩子簇（圖2）。他們是

11、被距離質(zhì)心相反方向的兩個(gè)向量的連線分割開來的。然后對(duì)于每一個(gè)父親簇都運(yùn)行一次K=2的K-means聚類算法，兩個(gè)孩子類都要與對(duì)方爭(zhēng)奪父親類的聚類區(qū)域。圖3表示了三個(gè)簇分別的分為兩個(gè)孩子類的過程。圖4表示所有的簇都已經(jīng)分為了兩個(gè)孩子類。在這個(gè)時(shí)候，模型的測(cè)試機(jī)制會(huì)對(duì)每一對(duì)子類進(jìn)行測(cè)試，測(cè)試內(nèi)容包括：兩個(gè)子類的建模過程是否有證據(jù)支撐？還有兩個(gè)子類是否是由父類平均分配的。下一節(jié)我們會(huì)涉及如何用這樣的測(cè)試集來測(cè)試K-means。根據(jù)測(cè)試出的結(jié)果，刪除不符合標(biāo)準(zhǔn)的父親類以及他們的后代，只有通過了這個(gè)過程的父親類以及他們的孩子類才能留存下來。另外一方面，沒有被現(xiàn)有的圖心描述好到的空間將會(huì)在增加圖心的過程中

12、獲得更多的關(guān)注。圖5顯示了圖4經(jīng)過這種處理之后的情況。因此我們的搜索空間覆蓋了所有的2k種可能的分割設(shè)置，并且每個(gè)區(qū)域的分割是由BIC得分來確定的。與上述的想法1以及想法2比較，這種思路可以使得我們自動(dòng)選擇我們的聚類個(gè)數(shù)的增加量時(shí)非常少還是非常多。通過實(shí)際操作我們發(fā)現(xiàn)，K-means聚類運(yùn)行兩個(gè)聚類個(gè)數(shù)的時(shí)候是對(duì)局部最小化準(zhǔn)則最不敏感的。我們?cè)谧罡呦拗芀值下面將會(huì)不斷的進(jìn)行參數(shù)改善以及框架改善來得到一個(gè)更加科學(xué)的K值。3.2 BIC得分假設(shè)我們已經(jīng)有了一個(gè)數(shù)據(jù)集D以及一些可供選擇的模型Mj，不同的模型對(duì)應(yīng)了不同的K值。我們?nèi)绾尾拍苓x擇最好的K值呢？我們將要用到后驗(yàn)概率來給模型進(jìn)行打分。我們的所

13、有模型都被K-means算法設(shè)定。為了按照統(tǒng)一的標(biāo)準(zhǔn)來設(shè)定后驗(yàn)概率，我們使用了以下公式：在這個(gè)公式當(dāng)中l(wèi)j(D)表示數(shù)據(jù)針對(duì)于第j個(gè)模型的對(duì)數(shù)似然函數(shù)，并且取極大似然函數(shù)值，pj是模型Mj中的參數(shù)數(shù)量，這個(gè)也被叫做Schwarz標(biāo)準(zhǔn)。這些變化之后的極大似然函數(shù)估計(jì)要在同一個(gè)高斯假設(shè)下：節(jié)點(diǎn)概率為：節(jié)點(diǎn)的對(duì)數(shù)似然函數(shù)為對(duì)于n屬于1到K中間的數(shù)值時(shí)，只關(guān)注Dn數(shù)據(jù)集中屬于n個(gè)圖心的點(diǎn)，并且插入最大似然函數(shù)的估計(jì)值。參數(shù)Pj就是就是簡(jiǎn)單的的鞥與K-1個(gè)類別的概率、M.K個(gè)累心的坐標(biāo)以及方差的估計(jì)值。為了把這一個(gè)圖心的公式延伸到所有圖心上，我們?cè)O(shè)定節(jié)點(diǎn)的似然函數(shù)為節(jié)點(diǎn)對(duì)于所有圖心的相對(duì)似然函數(shù)值，并且

14、將R替代為所有列入考慮的節(jié)點(diǎn)向量。我們?cè)赬-means確定最好的模型時(shí)全局的使用BIC公式，而局部的使用圖心分割測(cè)試。3.3加速到目前為止，X-means可以用在之前的小型數(shù)據(jù)上，但是我們都忽略了X-means聚類算法的主要特點(diǎn)，那就是它可以使用在大型數(shù)據(jù)的分析當(dāng)中。對(duì)K-means算法的加速：我們以一個(gè)簡(jiǎn)單的K-means算法迭代開始，任務(wù)是最終確定哪一個(gè)節(jié)點(diǎn)屬于哪一個(gè)質(zhì)心，通過這種迭代，我們可以計(jì)算出所有的質(zhì)心，并且確定屬于節(jié)點(diǎn)都是屬于哪一個(gè)給定的質(zhì)心，同時(shí)確定質(zhì)心的確定位置。得出結(jié)果之后，我們立刻就會(huì)發(fā)現(xiàn)，對(duì)于一個(gè)節(jié)點(diǎn)數(shù)據(jù)集的質(zhì)心分配與對(duì)于一個(gè)單獨(dú)的節(jié)點(diǎn)的中心分配過程是一樣的，因?yàn)槲覀冇?/p>

15、足夠的數(shù)據(jù)量作為支撐。顯然，這樣做可以節(jié)省很多的計(jì)算資源，所需要占用的資源往往不比證明一個(gè)點(diǎn)的歸屬問題多多少。既然kd-tree結(jié)構(gòu)強(qiáng)加了一個(gè)分層的數(shù)據(jù)結(jié)構(gòu)給數(shù)據(jù)，那么我們就可以很容易的計(jì)算它的節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)在建立他們的時(shí)候，對(duì)這些節(jié)點(diǎn)做一個(gè)局部的自然選擇。每一個(gè)kd-tree代表一個(gè)點(diǎn)集。這個(gè)樹形結(jié)構(gòu)同樣也有邊界，即一個(gè)可以包括數(shù)據(jù)集中所有點(diǎn)的矩形。另外，這種樹形結(jié)構(gòu)有兩個(gè)指針向量，向量表示每一個(gè)父親節(jié)點(diǎn)都被分為了兩個(gè)子節(jié)點(diǎn)。設(shè)置一個(gè)計(jì)數(shù)器來存儲(chǔ)每一個(gè)質(zhì)心擁有多少個(gè)節(jié)點(diǎn)，現(xiàn)在我們來展示這種計(jì)數(shù)器如何只掃描一遍樹形結(jié)構(gòu)就能夠統(tǒng)計(jì)到所有的圖心的數(shù)據(jù)。統(tǒng)計(jì)的過程是一個(gè)遞歸的過程，把每個(gè)圖心所擁有的

16、點(diǎn)視作參數(shù)。它的任務(wù)就是更新節(jié)點(diǎn)計(jì)數(shù)器中點(diǎn)的值都到達(dá)一個(gè)適當(dāng)?shù)拇笮?。在它遞歸返回之后，可能會(huì)由計(jì)數(shù)器產(chǎn)生新的位置信息。這個(gè)過程也包括根據(jù)之前提到的邊界框?qū)⒉豢赡軗碛腥魏吸c(diǎn)的圖心剔除出去，也就是在“黑名單”中出現(xiàn)的節(jié)點(diǎn)。這個(gè)過程的完整描述在Pelleg和Moore的論文中有體現(xiàn)。有一點(diǎn)要特別注意：在收縮了黑名單之后，這個(gè)過程要重新考慮現(xiàn)有節(jié)點(diǎn)的孩子節(jié)點(diǎn)。圖心的計(jì)數(shù)器通過這樣的方式增長(zhǎng)。這種工作通常在較高級(jí)的樹形結(jié)構(gòu)中實(shí)現(xiàn)，但是清除工作往往在整個(gè)樹形結(jié)構(gòu)中實(shí)現(xiàn)。加速結(jié)構(gòu)改善過程：這個(gè)過程就是在K-means迭代過程中改變圖心位置的過程。我們現(xiàn)在運(yùn)用同樣的過程來實(shí)現(xiàn)結(jié)構(gòu)改善的過程。之前的方法是，我們

17、對(duì)于每一個(gè)泰森多邊形下的區(qū)域分為兩塊相同大小的區(qū)域。并首先列出父親圖心的列表，然后將其作為這個(gè)過程的輸入變量。與全局迭代過程不同的地方在于當(dāng)圖心減少為只有一個(gè)單一圖心的時(shí)候，算法所進(jìn)行的動(dòng)作。如果出現(xiàn)了這種情況，那就表明數(shù)據(jù)集中的所有的點(diǎn)都是可以被歸納為一個(gè)圖心所包括的點(diǎn)。這個(gè)時(shí)候我們只要在它的孩子圖心之間進(jìn)行分割就可以了。為了達(dá)到這一目標(biāo)，我們將這個(gè)圖心分為兩個(gè)孩子圖心，然后評(píng)價(jià)是否應(yīng)當(dāng)對(duì)之前的結(jié)構(gòu)進(jìn)行分割。在對(duì)整個(gè)的樹形結(jié)構(gòu)進(jìn)行掃描之后，（有可能刪掉了很多的節(jié)點(diǎn)），子圖心的計(jì)數(shù)器已經(jīng)得到了一個(gè)最終的統(tǒng)計(jì)值，而且新的圖心的位置也已經(jīng)確定了，繼而我們可以進(jìn)行下一次迭代，直到所有的圖心已經(jīng)被處理

18、完成。額外的加速：在我哦們進(jìn)行上述迭代的過程中，那些沒有被考慮的空間區(qū)域往往為定義為活動(dòng)的，那些已經(jīng)被圖心包括的區(qū)域被標(biāo)記為靜止的。我們可以將這種分析模式通過將它的先前迭代的統(tǒng)計(jì)狀態(tài)作為緩存數(shù)據(jù)的方式來準(zhǔn)換為一種更進(jìn)一步的改進(jìn)加速，考慮到兩個(gè)圖心的邊界（這兩個(gè)圖心對(duì)數(shù)據(jù)集中的所有節(jié)點(diǎn)都有可能包括）。雖然我們必須遍歷屬性結(jié)構(gòu)來更新我們計(jì)數(shù)器中的數(shù)值，但是我們沒有理由在下一次迭代中再進(jìn)行一遍這個(gè)動(dòng)作，因?yàn)閳D心根本就沒有移動(dòng)過，也沒有任何新加入的圖心占用任何一個(gè)已經(jīng)分配給圖心的節(jié)點(diǎn)。因此我們可以記錄下圖心節(jié)點(diǎn)的數(shù)量然后進(jìn)行連續(xù)迭代，而不用每次都對(duì)數(shù)據(jù)的樹形結(jié)構(gòu)進(jìn)行一次遍歷。為了能夠快速比較兩個(gè)圖心位

19、置的優(yōu)劣，我們使用一個(gè)寫操作來實(shí)現(xiàn)：一旦數(shù)據(jù)結(jié)構(gòu)不允許在數(shù)據(jù)形成之后改變圖心的位置，一旦圖心的位置改變了，那么一個(gè)新的元素就必須插入進(jìn)來，并且這個(gè)插入的元素有特別的識(shí)別標(biāo)識(shí)。這個(gè)方法僅僅在兩個(gè)圖心進(jìn)行比較的時(shí)候會(huì)用到。顯然，因?yàn)榕f的圖心再也不會(huì)用到了，所以也沒有什么繼續(xù)存儲(chǔ)他們的必要了。這就涉及到我們要建立一個(gè)原始的M.K存儲(chǔ)器配上一個(gè)哈希表來快速尋找響應(yīng)的標(biāo)簽。這個(gè)想法的更進(jìn)一步的擴(kuò)展可以把這種存儲(chǔ)方式利用在圖心的孩子節(jié)點(diǎn)上。這些節(jié)點(diǎn)將會(huì)變?yōu)榻┦瑺顟B(tài)而不是被刪除。又由于他們的標(biāo)識(shí)符是不會(huì)變的，所以說緩沖區(qū)存儲(chǔ)的數(shù)據(jù)就是最后一次迭代完成之后的數(shù)據(jù)。5、結(jié)論本文中展現(xiàn)了一種新型的K-means算法來選擇更加科學(xué)的數(shù)據(jù)分類模型。通過適應(yīng)和擴(kuò)展來提高K-means，用這個(gè)算法可以免除用戶用不同的K值來測(cè)試哪個(gè)結(jié)果更加科學(xué)，X-means算法只需要運(yùn)行一