K-Means

算法流程（密度聚類）

1）隨機(jī)初始化k個(gè)組，求其中心點(diǎn)作為初始簇的中心點(diǎn)晾腔。

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è)。）

優(yōu)點(diǎn)：收斂速度快靖榕；計(jì)算簡便标锄；可解釋性強(qiáng)。

缺點(diǎn)：如何設(shè)k值茁计；對于非凸數(shù)據(jù)集難以準(zhǔn)確收斂料皇；類別不平衡結(jié)果不佳；局部最優(yōu)星压；噪聲敏感践剂。

優(yōu)化：K-Medians，用中位數(shù)代替均值娜膘，減少異常值的影響逊脯；但是數(shù)據(jù)排序求中位數(shù)的過程使速度變慢。

DBSCAN

算法流程

1）確定密度閾值和鄰域半徑竣贪。從一個(gè)沒有被訪問過的任意數(shù)據(jù)點(diǎn)開始军洼，以這個(gè)點(diǎn)為中心巩螃，r為半徑的圓內(nèi)包含的點(diǎn)的數(shù)量是否大于或等于minPoints，如果大于或等于minPoints則改點(diǎn)被標(biāo)記為中心點(diǎn)匕争，反之標(biāo)記為噪聲點(diǎn)避乏。?

2）重復(fù)1的步驟，如果一個(gè)噪聲點(diǎn)存在于某個(gè)中心點(diǎn)為半徑的圓內(nèi)甘桑，則這個(gè)點(diǎn)被標(biāo)記為邊緣點(diǎn)拍皮，反之仍為噪聲點(diǎn)。

3）重復(fù)步驟1跑杭，直至所有的點(diǎn)都被訪問過铆帽。

優(yōu)點(diǎn)：不需要知道簇的數(shù)量；可檢測任意形狀簇德谅；噪聲不敏感爹橱。

缺點(diǎn)：需要確定距離r和minPoints；收斂時(shí)間長女阀；不平衡數(shù)據(jù)結(jié)果不好。

Mean-Shift

算法流程（基于滑動(dòng)窗口）

1）在未被標(biāo)記的數(shù)據(jù)點(diǎn)中隨機(jī)選擇一個(gè)點(diǎn)作為起始中心點(diǎn)center屑迂；

2）找出以center為中心半徑為R的區(qū)域中出現(xiàn)的所有數(shù)據(jù)點(diǎn)浸策，認(rèn)為這些點(diǎn)同屬于一個(gè)簇。同時(shí)在該聚類中記錄數(shù)據(jù)點(diǎn)出現(xiàn)的次數(shù)加1惹盼。

3）以center為中心點(diǎn)庸汗，落在窗口圓中的所有點(diǎn)和圓心都會(huì)對應(yīng)的一個(gè)向量，把所有這些向量相加手报，最終我們只得到一個(gè)向量蚯舱，就是meanshift向量。

4）移動(dòng)窗口（以meanshift向量的終點(diǎn)為新的圓心）掩蛤，計(jì)算窗口內(nèi)的中心點(diǎn)以及窗口內(nèi)的密度枉昏，直到?jīng)]有方向在窗口內(nèi)可以容納更多的點(diǎn)，即一直移動(dòng)到圓內(nèi)密度不再增加為止揍鸟。

5）重復(fù)4）直至shift的很小兄裂，此時(shí)的中心點(diǎn)就是該簇的中心，這個(gè)迭代過程中的所有窗口內(nèi)的點(diǎn)都屬于該簇阳藻。

6）如果收斂時(shí)當(dāng)前簇C的center與其它已經(jīng)存在的簇C2中心的距離小于閾值晰奖，那么把簇合并，數(shù)據(jù)點(diǎn)出現(xiàn)次數(shù)也對應(yīng)合并腥泥。

7）重復(fù)匾南，直到所有的點(diǎn)都被標(biāo)記為已訪問。

優(yōu)點(diǎn)：不需要提前知道簇的數(shù)量蛔外；相比K-Means來說受均值影響較小

缺點(diǎn)：需要確定R（R的選擇可能不重要）

GMM

算法流程

1）選擇簇的數(shù)量蛆楞，隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)（均值和方差）溯乒。（也可以先觀察數(shù)據(jù)給出一個(gè)相對精確的均值和方差。 ）

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)來計(jì)算這些新的參數(shù)，權(quán)重就是數(shù)據(jù)點(diǎn)屬于該簇的概率逻住。

4）重復(fù)迭代2和3直到在迭代中的變化不大钟哥。

優(yōu)點(diǎn)：簇可以呈現(xiàn)出橢圓形而不是僅僅限制于圓形。（K-Means是GMMs的一個(gè)特殊情況瞎访，是方差在所有維度上都接近于0時(shí)簇就會(huì)呈現(xiàn)出圓形腻贰。）；使用概率扒秸，所以一個(gè)數(shù)據(jù)點(diǎn)可以屬于多個(gè)簇播演，也就是說GMMs可以支持混合資格。

缺點(diǎn)：形狀不是任意的伴奥；需要提前確定簇?cái)?shù)写烤。

優(yōu)化：常先用K-Means初步計(jì)算，再輸入至GMM拾徙。

凝聚層次聚類

算法流程

1）將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇洲炊，選擇一個(gè)測量兩個(gè)簇之間距離的度量標(biāo)準(zhǔn)。

2）每次迭代尼啡，將兩個(gè)具有最小距離的簇合并成為一個(gè)簇暂衡。

3）重復(fù)2），直至所有數(shù)據(jù)點(diǎn)合并成一個(gè)簇崖瞭，然后選擇需要的簇狂巢。

優(yōu)點(diǎn)：不需要知道有多少個(gè)簇 ；對距離度量標(biāo)準(zhǔn)的選擇不敏感书聚。

缺點(diǎn)：效率低隧膘。