常見的六大聚類算法

Version:1.0StartHTML:000000223EndHTML:000150033StartFragment:000104048EndFragment:000149960StartSelection:000104048EndSelection:000149956SourceURL:https://blog.csdn.net/Katherine_hsr/article/details/79382249

1. K-Means(K均值)聚類

算法步驟:

(1) 首先我們選擇一些類/組舆声,并隨機(jī)初始化它們各自的中心點(diǎn)混移。中心點(diǎn)是與每個(gè)數(shù)據(jù)點(diǎn)向量長(zhǎng)度相同的位置从诲。這需要我們提前預(yù)知類的數(shù)量(即中心點(diǎn)的數(shù)量)。

(2) 計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到中心點(diǎn)的距離再菊,數(shù)據(jù)點(diǎn)距離哪個(gè)中心點(diǎn)最近就劃分到哪一類中族奢。

(3) 計(jì)算每一類中中心點(diǎn)作為新的中心點(diǎn)懈玻。

(4) 重復(fù)以上步驟女轿,直到每一類中心在每次迭代后變化不大為止箭启。也可以多次隨機(jī)初始化中心點(diǎn),然后選擇運(yùn)行結(jié)果最好的一個(gè)蛉迹。

下圖演示了K-Means進(jìn)行分類的過(guò)程:

優(yōu)點(diǎn):

速度快傅寡,計(jì)算簡(jiǎn)便

缺點(diǎn):

我們必須提前知道數(shù)據(jù)有多少類/組。

K-Medians是K-Means的一種變體北救,是用數(shù)據(jù)集的中位數(shù)而不是均值來(lái)計(jì)算數(shù)據(jù)的中心點(diǎn)荐操。

K-Medians的優(yōu)勢(shì)是使用中位數(shù)來(lái)計(jì)算中心點(diǎn)不受異常值的影響;缺點(diǎn)是計(jì)算中位數(shù)時(shí)需要對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行排序珍策,速度相對(duì)于K-Means較慢托启。

2. 均值漂移聚類

均值漂移聚類是基于滑動(dòng)窗口的算法,來(lái)找到數(shù)據(jù)點(diǎn)的密集區(qū)域攘宙。這是一個(gè)基于質(zhì)心的算法屯耸,通過(guò)將中心點(diǎn)的候選點(diǎn)更新為滑動(dòng)窗口內(nèi)點(diǎn)的均值來(lái)完成,來(lái)定位每個(gè)組/類的中心點(diǎn)蹭劈。然后對(duì)這些候選窗口進(jìn)行相似窗口進(jìn)行去除疗绣,最終形成中心點(diǎn)集及相應(yīng)的分組。

具體步驟:

1. 確定滑動(dòng)窗口半徑r铺韧,以隨機(jī)選取的中心點(diǎn)C半徑為r的圓形滑動(dòng)窗口開始滑動(dòng)多矮。均值漂移類似一種爬山算法,在每一次迭代中向密度更高的區(qū)域移動(dòng)哈打,直到收斂塔逃。

2. 每一次滑動(dòng)到新的區(qū)域,計(jì)算滑動(dòng)窗口內(nèi)的均值來(lái)作為中心點(diǎn)料仗,滑動(dòng)窗口內(nèi)的點(diǎn)的數(shù)量為窗口內(nèi)的密度湾盗。在每一次移動(dòng)中,窗口會(huì)想密度更高的區(qū)域移動(dòng)罢维。

3. 移動(dòng)窗口淹仑,計(jì)算窗口內(nèi)的中心點(diǎn)以及窗口內(nèi)的密度丙挽,知道沒有方向在窗口內(nèi)可以容納更多的點(diǎn)肺孵,即一直移動(dòng)到圓內(nèi)密度不再增加為止。

4. 步驟一到三會(huì)產(chǎn)生很多個(gè)滑動(dòng)窗口颜阐,當(dāng)多個(gè)滑動(dòng)窗口重疊時(shí)平窘,保留包含最多點(diǎn)的窗口,然后根據(jù)數(shù)據(jù)點(diǎn)所在的滑動(dòng)窗口進(jìn)行聚類凳怨。

下圖演示了均值漂移聚類的計(jì)算步驟:

下面顯示了所有滑動(dòng)窗口從頭到尾的整個(gè)過(guò)程瑰艘。每個(gè)黑點(diǎn)代表滑動(dòng)窗口的質(zhì)心是鬼,每個(gè)灰點(diǎn)代表一個(gè)數(shù)據(jù)點(diǎn)。

優(yōu)點(diǎn):(1)不同于K-Means算法紫新,均值漂移聚類算法不需要我們知道有多少類/組均蜜。

(2)基于密度的算法相比于K-Means受均值影響較小。

缺點(diǎn):(1)窗口半徑r的選擇可能是不重要的芒率。

3. 基于密度的聚類方法(DBSCAN)

與均值漂移聚類類似囤耳,DBSCAN也是基于密度的聚類算法肿嘲。

具體步驟:

1. 首先確定半徑r和minPoints. 從一個(gè)沒有被訪問(wèn)過(guò)的任意數(shù)據(jù)點(diǎn)開始亿蒸,以這個(gè)點(diǎn)為中心,r為半徑的圓內(nèi)包含的點(diǎn)的數(shù)量是否大于或等于minPoints展哭,如果大于或等于minPoints則改點(diǎn)被標(biāo)記為central point,反之則會(huì)被標(biāo)記為noise point匪蟀。

2. 重復(fù)1的步驟椎麦,如果一個(gè)noise point存在于某個(gè)central point為半徑的圓內(nèi),則這個(gè)點(diǎn)被標(biāo)記為邊緣點(diǎn)材彪,反之仍為noise point观挎。重復(fù)步驟1,知道所有的點(diǎn)都被訪問(wèn)過(guò)段化。

優(yōu)點(diǎn):不需要知道簇的數(shù)量

缺點(diǎn):需要確定距離r和minPoints

4. 用高斯混合模型(GMM)的最大期望(EM)聚類

K-Means的缺點(diǎn)在于對(duì)聚類中心均值的簡(jiǎn)單使用键兜。下面的圖中的兩個(gè)圓如果使用K-Means則不能作出正確的類的判斷。同樣的穗泵,如果數(shù)據(jù)集中的點(diǎn)類似下圖中曲線的情況也是不能正確分類的普气。

使用高斯混合模型(GMM)做聚類首先假設(shè)數(shù)據(jù)點(diǎn)是呈高斯分布的,相對(duì)應(yīng)K-Means假設(shè)數(shù)據(jù)點(diǎn)是圓形的佃延,高斯分布(橢圓形)給出了更多的可能性现诀。我們有兩個(gè)參數(shù)來(lái)描述簇的形狀:均值和標(biāo)準(zhǔn)差。所以這些簇可以采取任何形狀的橢圓形履肃,因?yàn)樵趚仔沿,y方向上都有標(biāo)準(zhǔn)差。因此尺棋,每個(gè)高斯分布被分配給單個(gè)簇封锉。

所以要做聚類首先應(yīng)該找到數(shù)據(jù)集的均值和標(biāo)準(zhǔn)差,我們將采用一個(gè)叫做最大期望(EM)的優(yōu)化算法膘螟。下圖演示了使用GMMs進(jìn)行最大期望的聚類過(guò)程成福。

具體步驟:

1. 選擇簇的數(shù)量(與K-Means類似)并隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)(均值和方差)。也可以先觀察數(shù)據(jù)給出一個(gè)相對(duì)精確的均值和方差荆残。

2. 給定每個(gè)簇的高斯分布奴艾,計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于每個(gè)簇的概率。一個(gè)點(diǎn)越靠近高斯分布的中心就越可能屬于該簇内斯。

3. 基于這些概率我們計(jì)算高斯分布參數(shù)使得數(shù)據(jù)點(diǎn)的概率最大化蕴潦,可以使用數(shù)據(jù)點(diǎn)概率的加權(quán)來(lái)計(jì)算這些新的參數(shù)像啼,權(quán)重就是數(shù)據(jù)點(diǎn)屬于該簇的概率。

4. 重復(fù)迭代2和3直到在迭代中的變化不大潭苞。

GMMs的優(yōu)點(diǎn):(1)GMMs使用均值和標(biāo)準(zhǔn)差忽冻,簇可以呈現(xiàn)出橢圓形而不是僅僅限制于圓形。K-Means是GMMs的一個(gè)特殊情況此疹,是方差在所有維度上都接近于0時(shí)簇就會(huì)呈現(xiàn)出圓形甚颂。

(2)GMMs是使用概率,所有一個(gè)數(shù)據(jù)點(diǎn)可以屬于多個(gè)簇秀菱。例如數(shù)據(jù)點(diǎn)X可以有百分之20的概率屬于A簇振诬,百分之80的概率屬于B簇。也就是說(shuō)GMMs可以支持混合資格衍菱。

5. 凝聚層次聚類

層次聚類算法分為兩類:自上而下和自下而上赶么。凝聚層級(jí)聚類(HAC)是自下而上的一種聚類算法。HAC首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇脊串,然后計(jì)算所有簇之間的距離來(lái)合并簇辫呻,知道所有的簇聚合成為一個(gè)簇為止。

下圖為凝聚層級(jí)聚類的一個(gè)實(shí)例:

具體步驟:

1. 首先我們將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇琼锋,然后選擇一個(gè)測(cè)量?jī)蓚€(gè)簇之間距離的度量標(biāo)準(zhǔn)放闺。例如我們使用average linkage作為標(biāo)準(zhǔn),它將兩個(gè)簇之間的距離定義為第一個(gè)簇中的數(shù)據(jù)點(diǎn)與第二個(gè)簇中的數(shù)據(jù)點(diǎn)之間的平均距離缕坎。

2. 在每次迭代中怖侦,我們將兩個(gè)具有最小average linkage的簇合并成為一個(gè)簇。

3. 重復(fù)步驟2知道所有的數(shù)據(jù)點(diǎn)合并成一個(gè)簇谜叹,然后選擇我們需要多少個(gè)簇匾寝。

層次聚類優(yōu)點(diǎn):(1)不需要知道有多少個(gè)簇

(2)對(duì)于距離度量標(biāo)準(zhǔn)的選擇并不敏感

缺點(diǎn):效率低

6. 圖團(tuán)體檢測(cè)(Graph Community Detection)

當(dāng)我們的數(shù)據(jù)可以被表示為網(wǎng)絡(luò)或圖是,可以使用圖團(tuán)體檢測(cè)方法完成聚類荷腊。在這個(gè)算法中圖團(tuán)體(graph community)通常被定義為一種頂點(diǎn)(vertice)的子集艳悔,其中的頂點(diǎn)相對(duì)于網(wǎng)絡(luò)的其他部分要連接的更加緊密。下圖展示了一個(gè)簡(jiǎn)單的圖女仰,展示了最近瀏覽過(guò)的8個(gè)網(wǎng)站猜年,根據(jù)他們的維基百科頁(yè)面中的鏈接進(jìn)行了連接。

模塊性可以使用以下公式進(jìn)行計(jì)算:

M=12L∑Ni,j=1(Aij?kiKj2L)δCi,CjM=12L∑i,j=1N(Aij?kiKj2L)δCi,CjM=\frac{1}{2L}\sum_{i,j=1}^{N}(A_{ij}-\frac{k_iK_j}{2L})\delta_{C_{i},C{j}}

其中L代表網(wǎng)絡(luò)中邊的數(shù)量疾忍,AijAijA_{ij}代表真實(shí)的頂點(diǎn)i和j之間的邊數(shù),ki,kjki,kjk_i, k_j代表每個(gè)頂點(diǎn)的degree乔外,可以通過(guò)將每一行每一列的項(xiàng)相加起來(lái)而得到。兩者相乘再除以2L表示該網(wǎng)絡(luò)是隨機(jī)分配的時(shí)候頂點(diǎn)i和j之間的預(yù)期邊數(shù)锭碳。所以Aij?kikj2LAij?kikj2LA_{ij}-\frac{k_ik_j}{2L}代表了該網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)和隨機(jī)組合時(shí)的預(yù)期結(jié)構(gòu)之間的差袁稽。當(dāng)AijAijA_{ij}為1時(shí)勿璃,且kikj2Lkikj2L\frac{k_ik_j}{2L}很小的時(shí)候擒抛,其返回值最高推汽。也就是說(shuō),當(dāng)在定點(diǎn)i和j之間存在一個(gè)非預(yù)期邊是得到的值更高歧沪。

δCi,CjδCi,Cj\delta_{C_i, C_j}是克羅內(nèi)克δδ\delta函數(shù)(Kronecker-delta function). 下面是其Python解釋:

def ? Kronecker_Delta(ci,cj):

if ? ci==cj:? return1 ??

else: ? return0

通過(guò)上述公式可以計(jì)算圖的模塊性歹撒,且模塊性越高,該網(wǎng)絡(luò)聚類成不同團(tuán)體的程度越好诊胞,因此通過(guò)最優(yōu)化方法尋找最大模塊性就能發(fā)現(xiàn)聚類該網(wǎng)絡(luò)的最佳方法暖夭。

組合學(xué)告訴我們對(duì)于一個(gè)僅有8個(gè)頂點(diǎn)的網(wǎng)絡(luò),就存在4140種不同的聚類方式撵孤,16個(gè)頂點(diǎn)的網(wǎng)絡(luò)的聚類方式將超過(guò)100億種迈着。32個(gè)頂點(diǎn)的網(wǎng)絡(luò)的可能聚類方式更是將超過(guò)10^21種。因此邪码,我們必須尋找一種啟發(fā)式的方法使其不需要嘗試每一種可能性裕菠。這種方法叫做Fast-Greedy Modularity-Maximization(快速貪婪模塊性最大化)的算法,這種算法在一定程度上類似于上面描述的集聚層次聚類算法闭专。只是這種算法不根據(jù)距離來(lái)融合團(tuán)體奴潘,而是根據(jù)模塊性的改變來(lái)對(duì)團(tuán)體進(jìn)行融合。

具體步驟:

1. 首先初始分配每個(gè)頂點(diǎn)到其自己的團(tuán)體影钉,然后計(jì)算整個(gè)網(wǎng)絡(luò)的模塊性 M画髓。

2. 第 1 步要求每個(gè)團(tuán)體對(duì)(community pair)至少被一條單邊鏈接,如果有兩個(gè)團(tuán)體融合到了一起平委,該算法就計(jì)算由此造成的模塊性改變 ΔM奈虾。

3. 第 2 步是取 ΔM 出現(xiàn)了最大增長(zhǎng)的團(tuán)體對(duì),然后融合廉赔。然后為這個(gè)聚類計(jì)算新的模塊性 M愚墓,并記錄下來(lái)。

4. 重復(fù)第 1 步和 第 2 步——每一次都融合團(tuán)體對(duì)昂勉,這樣最后得到 ΔM 的最大增益浪册,然后記錄新的聚類模式及其相應(yīng)的模塊性分?jǐn)?shù) M。

5. 重復(fù)第 1 步和 第 2 步——每一次都融合團(tuán)體對(duì)岗照,這樣最后得到 ΔM 的最大增益村象,然后記錄新的聚類模式及其相應(yīng)的模塊性分?jǐn)?shù) M。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末攒至,一起剝皮案震驚了整個(gè)濱河市厚者,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌迫吐,老刑警劉巖库菲,帶你破解...
    沈念sama閱讀 210,978評(píng)論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異志膀,居然都是意外死亡熙宇,警方通過(guò)查閱死者的電腦和手機(jī)鳖擒,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,954評(píng)論 2 384
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)烫止,“玉大人蒋荚,你說(shuō)我怎么就攤上這事」萑洌” “怎么了期升?”我有些...
    開封第一講書人閱讀 156,623評(píng)論 0 345
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)互躬。 經(jīng)常有香客問(wèn)我播赁,道長(zhǎng),這世上最難降的妖魔是什么吼渡? 我笑而不...
    開封第一講書人閱讀 56,324評(píng)論 1 282
  • 正文 為了忘掉前任行拢,我火速辦了婚禮,結(jié)果婚禮上诞吱,老公的妹妹穿的比我還像新娘舟奠。我一直安慰自己,他們只是感情好房维,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,390評(píng)論 5 384
  • 文/花漫 我一把揭開白布沼瘫。 她就那樣靜靜地躺著,像睡著了一般咙俩。 火紅的嫁衣襯著肌膚如雪耿戚。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,741評(píng)論 1 289
  • 那天阿趁,我揣著相機(jī)與錄音膜蛔,去河邊找鬼。 笑死脖阵,一個(gè)胖子當(dāng)著我的面吹牛皂股,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播命黔,決...
    沈念sama閱讀 38,892評(píng)論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼呜呐,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了悍募?” 一聲冷哼從身側(cè)響起蘑辑,我...
    開封第一講書人閱讀 37,655評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎坠宴,沒想到半個(gè)月后洋魂,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,104評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,451評(píng)論 2 325
  • 正文 我和宋清朗相戀三年副砍,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了衔肢。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,569評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡址晕,死狀恐怖膀懈,靈堂內(nèi)的尸體忽然破棺而出顿锰,到底是詐尸還是另有隱情谨垃,我是刑警寧澤,帶...
    沈念sama閱讀 34,254評(píng)論 4 328
  • 正文 年R本政府宣布硼控,位于F島的核電站刘陶,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏牢撼。R本人自食惡果不足惜匙隔,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,834評(píng)論 3 312
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望熏版。 院中可真熱鬧纷责,春花似錦、人聲如沸撼短。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,725評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)曲横。三九已至喂柒,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間禾嫉,已是汗流浹背灾杰。 一陣腳步聲響...
    開封第一講書人閱讀 31,950評(píng)論 1 264
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留熙参,地道東北人艳吠。 一個(gè)月前我還...
    沈念sama閱讀 46,260評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像孽椰,于是被迫代替她去往敵國(guó)和親讲竿。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,446評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容

  • 聚類算法 前面介紹的集中算法都是屬于有監(jiān)督機(jī)器學(xué)習(xí)方法弄屡,這章和前面不同题禀,介紹無(wú)監(jiān)督學(xué)習(xí)算法,也就是聚類算法膀捷。在無(wú)監(jiān)...
    飄涯閱讀 41,277評(píng)論 3 52
  • 前兩天我們經(jīng)理說(shuō)她兒子這段時(shí)間學(xué)習(xí)特別懶散,不知道是不是和暑假在家懶習(xí)慣了有關(guān)系秀仲,晚上和周末都宅在家融痛,不肯出去,拉...
    紅豬豬閱讀 443評(píng)論 0 0
  • 尋到洞口神僵,我系好繩索雁刷,把背包交給老陳就要一人下去,老陳不愿意了:王司令保礼,你可不能這樣沛励,脫離組織獨(dú)自行動(dòng)可是要受...
    潦草的楷書閱讀 251評(píng)論 0 0
  • 雷鳴震我耳,斜雨濕我衣炮障。 弱傘不足用目派,薄履不足惜。 一生何所命胁赢,高冠或蓑披企蹭。 破浪歸帆后,莫笑老田迂智末。
    帝司閱讀 236評(píng)論 0 0
  • JAVA環(huán)境 : 1.下載jdk jdk鏈接 2.配置系統(tǒng)變量: 我的電腦》右鍵》屬性》高級(jí)系統(tǒng)設(shè)置》環(huán)境變量》...
    0安閱讀 527評(píng)論 0 0