Version:1.0StartHTML:000000223EndHTML:000150033StartFragment:000104048EndFragment:000149960StartSelection:000104048EndSelection:000149956SourceURL:https://blog.csdn.net/Katherine_hsr/article/details/79382249
算法步驟:
(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較慢托启。
均值漂移聚類是基于滑動(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的選擇可能是不重要的芒率。
與均值漂移聚類類似囤耳,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
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可以支持混合資格衍菱。
層次聚類算法分為兩類:自上而下和自下而上赶么。凝聚層級(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。