今天，和大家分享一下機(jī)器學(xué)習(xí)之無(wú)監(jiān)督學(xué)習(xí)中的常見(jiàn)的聚類方法。

在無(wú)監(jiān)督學(xué)習(xí)中，我們的數(shù)據(jù)并不帶有任何標(biāo)簽，因此在無(wú)監(jiān)督學(xué)習(xí)中要做的就是將這一系列無(wú)標(biāo)簽的數(shù)據(jù)輸入到算法中，然后讓算法找到一些隱含在數(shù)據(jù)中的結(jié)構(gòu)，通過(guò)下圖中的數(shù)據(jù)，可以找到的一個(gè)結(jié)構(gòu)就是數(shù)據(jù)集中的點(diǎn)可以分成兩組分開(kāi)的點(diǎn)集（簇），能夠圈出這些簇（cluster）的算法，就叫做聚類算法（clustering algorithm）。

聚類算法的應(yīng)用

市場(chǎng)分割：將數(shù)據(jù)庫(kù)中客戶的信息根據(jù)市場(chǎng)進(jìn)行不同的分組，從而實(shí)現(xiàn)對(duì)其分別銷售或者根據(jù)不同的市場(chǎng)進(jìn)行服務(wù)改進(jìn)。

社交網(wǎng)絡(luò)分析：通過(guò)郵件最頻繁聯(lián)系的人及其最頻繁聯(lián)系的人來(lái)找到一個(gè)關(guān)系密切的群體。

組織計(jì)算機(jī)集群：在數(shù)據(jù)中心里，計(jì)算機(jī)集群經(jīng)常一起協(xié)同工作，可以用它來(lái)重新組織資源、重新布局網(wǎng)絡(luò)、優(yōu)化數(shù)據(jù)中心以及通信數(shù)據(jù)。

了解銀河系的構(gòu)成：利用這些信息來(lái)了解一些天文學(xué)的知識(shí)。

聚類分析的目標(biāo)是將觀測(cè)值劃分為組（“簇”），以便分配到同一簇的觀測(cè)值之間的成對(duì)差異往往小于不同簇中的觀測(cè)值之間的差異。聚類算法分為三種不同的類型：組合算法、混合建模和模式搜索。

常見(jiàn)的幾種聚類算法有：

K-Means Clustering

Hierarchical Clustering

Agglomerative Clustering

Affinity Propagation

Mean Shift Clustering

Bisecting K-Means

DBSCAN

OPTICS

BIRCH

K-means

K-means 算法是目前最流行的聚類方法之一。

K-means 是由貝爾實(shí)驗(yàn)室的 Stuart Lloyd 在 1957 年提出來(lái)的，最開(kāi)始是用于脈沖編碼調(diào)制，直到 1982 年才將該算法對(duì)外公布。1965 年，Edward W.Forgy 發(fā)布了相同的算法，因此 K-Means 有時(shí)被稱為 Lloyd-Forgy。

在聚類問(wèn)題中，我們會(huì)給定一組未加標(biāo)簽的數(shù)據(jù)集，同時(shí)希望有一個(gè)算法能夠自動(dòng)地將這些數(shù)據(jù)分成有緊密關(guān)系的的（coherent）子集（subsets） 或是簇（clusters）。K 均值（K-means）算法是現(xiàn)在最熱門最為廣泛運(yùn)用的聚類算法。

直觀理解 K 均值算法：

假如有一個(gè)無(wú)標(biāo)簽的數(shù)據(jù)集（上圖左），并且我們想要將其分為兩個(gè)簇，現(xiàn)在執(zhí)行 K 均值算法，具體操作如下：

第一步，隨機(jī)生成兩個(gè)點(diǎn)（因?yàn)橄胍獙?shù)據(jù)聚成兩類）（上圖右），這兩個(gè)點(diǎn)叫做聚類中心（cluster centroids）。

第二步，進(jìn)行 K 均值算法的內(nèi)循環(huán)。K 均值算法是一個(gè)迭代算法，它會(huì)做兩件事情，第一個(gè)是簇分配（cluster assignment），第二個(gè)是移動(dòng)聚類中心（move centroid）。

內(nèi)循環(huán)的第一步是要進(jìn)行簇分配，也就是說(shuō)，遍歷每一個(gè)樣本，再根據(jù)每一個(gè)點(diǎn)到聚類中心距離的遠(yuǎn)近將其分配給不同的聚類中心（離誰(shuí)近分配給誰(shuí)），對(duì)于本例而言，就是遍歷數(shù)據(jù)集，將每個(gè)點(diǎn)染成紅色或藍(lán)色。

內(nèi)循環(huán)的第二步是移動(dòng)聚類中心，將紅色和藍(lán)色的聚類中心移動(dòng)到各自點(diǎn)的均值處（每組點(diǎn)的平均位置）。

接著就是將所有的點(diǎn)根據(jù)與新的聚類中心距離的遠(yuǎn)近進(jìn)行新的簇分配，如此循環(huán)，直至聚類中心的位置不再隨著迭代而改變，并且點(diǎn)的顏色也不再發(fā)生改變，此時(shí)可以說(shuō) K 均值已經(jīng)聚合了。該算法在找出數(shù)據(jù)中兩個(gè)簇的方面做的相當(dāng)好。

K-Means算法的優(yōu)點(diǎn)：

簡(jiǎn)單易懂，計(jì)算速度較快，適用于大規(guī)模數(shù)據(jù)集。

缺點(diǎn)：

例如對(duì)于非球形簇的處理能力較差，容易受到初始簇心的選擇影響，需要預(yù)先指定簇的數(shù)量K等。

此外，當(dāng)數(shù)據(jù)點(diǎn)之間存在噪聲或者離群點(diǎn)時(shí)，K-Means算法可能會(huì)將它們分配到錯(cuò)誤的簇中。

Hierarchical Clustering

層次聚類（Hierarchical Clustering）顧名思義就是按照某個(gè)層次對(duì)樣本集進(jìn)行聚類操作，這里的層次實(shí)際上指的就是某種距離定義。

層次聚類最終的目的是消減類別的數(shù)量，所以在行為上類似于樹(shù)狀圖由葉節(jié)點(diǎn)逐步向根節(jié)點(diǎn)靠近的過(guò)程，這種行為過(guò)程又被稱為“自底向上”。

更通俗的，層次聚類是將初始化的多個(gè)類簇看做樹(shù)節(jié)點(diǎn)，每一步迭代，都是將兩兩相近的類簇合并成一個(gè)新的大類簇，如此反復(fù)，直至最終只剩一個(gè)類簇（根節(jié)點(diǎn)）。

層次聚類策略分為兩種基本范式：聚集型(自下而上)和分裂型(自上而下)。

與層次聚類相反的是分裂聚類（divisive clustering），又名 DIANA(Divise Analysis)，它的行為過(guò)程為“自頂向下”。

應(yīng)用 K-means 的結(jié)果取決于要搜索的聚類數(shù)量的選擇和起始配置分配。相反，層次聚類方法不需要這樣的規(guī)范。相反，它們要求用戶根據(jù)兩組觀察值之間的成對(duì)差異性，指定（不相交）觀察組之間的差異性度量。顧名思義，它們產(chǎn)生層次結(jié)構(gòu)表示，其中層次結(jié)構(gòu)每個(gè)級(jí)別的集群都是通過(guò)合并下一個(gè)較低級(jí)別的集群來(lái)創(chuàng)建的。在最低級(jí)別，每個(gè)集群包含一個(gè)觀察值。在最高級(jí)別，只有一個(gè)集群包含所有數(shù)據(jù)。

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

距離和規(guī)則的相似度容易定義，限制少；

不需要預(yù)先制定聚類數(shù)；

可以發(fā)現(xiàn)類的層次關(guān)系；

可以聚類成其它形狀。

缺點(diǎn)：

計(jì)算復(fù)雜度太高；

奇異值也能產(chǎn)生很大影響；

算法很可能聚類成鏈狀。

Agglomerative Clustering

凝聚層次聚類（Agglomerative Clustering）是一種自底向上的聚類算法，它將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)初始簇，并將它們逐步合并成更大的簇，直到達(dá)到停止條件為止。在該算法中，每個(gè)數(shù)據(jù)點(diǎn)最初被視為一個(gè)單獨(dú)的簇，然后逐步合并簇，直到所有數(shù)據(jù)點(diǎn)被合并為一個(gè)大簇。

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

適用于不同形狀和大小的簇，且不需要事先指定聚類數(shù)目。

該算法也可以輸出聚類層次結(jié)構(gòu)，便于分析和可視化。

缺點(diǎn)：

計(jì)算復(fù)雜度較高，尤其是在處理大規(guī)模數(shù)據(jù)集時(shí)，需要消耗大量的計(jì)算資源和存儲(chǔ)空間。

該算法對(duì)初始簇的選擇也比較敏感，可能會(huì)導(dǎo)致不同的聚類結(jié)果。

Affinity Propagation

Affinity Propagation（AP）算法，通常被翻譯為近鄰傳播算法或者親和力傳播算法,

Affinity Propagation 是一種基于圖論的聚類算法，旨在識(shí)別數(shù)據(jù)中的"exemplars"(代表點(diǎn))和"clusters"(簇)。與 K-Means 等傳統(tǒng)聚類算法不同，Affinity Propagation 不需要事先指定聚類數(shù)目，也不需要隨機(jī)初始化簇心，而是通過(guò)計(jì)算數(shù)據(jù)點(diǎn)之間的相似性得出最終的聚類結(jié)果。

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

不需要制定最終聚類族的個(gè)數(shù)

已有的數(shù)據(jù)點(diǎn)作為最終的聚類中心，而不是新生成一個(gè)簇中心。

模型對(duì)數(shù)據(jù)的初始值不敏感。

對(duì)初始相似度矩陣數(shù)據(jù)的對(duì)稱性沒(méi)有要求。

相比與 k-centers 聚類方法，其結(jié)果的平方差誤差較小。

缺點(diǎn)：

該算法的計(jì)算復(fù)雜度較高，需要大量的存儲(chǔ)空間和計(jì)算資源；

對(duì)于噪聲點(diǎn)和離群點(diǎn)的處理能力較弱。

Mean Shift Clustering

Mean Shift Clustering 是一種基于密度的非參數(shù)聚類算法，其基本思想是通過(guò)尋找數(shù)據(jù)點(diǎn)密度最大的位置（稱為"局部最大值"或"高峰"），來(lái)識(shí)別數(shù)據(jù)中的簇。算法的核心是通過(guò)對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行局部密度估計(jì)，并將密度估計(jì)的結(jié)果用于計(jì)算數(shù)據(jù)點(diǎn)移動(dòng)的方向和距離。算法的核心是通過(guò)對(duì)每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行局部密度估計(jì)，并將密度估計(jì)的結(jié)果用于計(jì)算數(shù)據(jù)點(diǎn)移動(dòng)的方向和距離。

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

不需要指定簇的數(shù)目，且對(duì)于形狀復(fù)雜的簇也有很好的效果。

算法還能夠有效地處理噪聲數(shù)據(jù)。

缺點(diǎn)：

計(jì)算復(fù)雜度較高，尤其是在處理大規(guī)模數(shù)據(jù)集時(shí)，需要消耗大量的計(jì)算資源和存儲(chǔ)空間；

該算法還對(duì)初始參數(shù)的選擇比較敏感，需要進(jìn)行參數(shù)調(diào)整和優(yōu)化。

Bisecting K-Means

Bisecting K-Means 是一種基于 K-Means 算法的層次聚類算法，其基本思想是將所有數(shù)據(jù)點(diǎn)劃分為一個(gè)簇，然后將該簇分成兩個(gè)子簇，并對(duì)每個(gè)子簇分別應(yīng)用 K-Means 算法，重復(fù)執(zhí)行這個(gè)過(guò)程，直到達(dá)到預(yù)定的聚類數(shù)目為止。

算法首先將所有數(shù)據(jù)點(diǎn)視為一個(gè)初始簇，然后對(duì)該簇應(yīng)用K-Means算法，將該簇分成兩個(gè)子簇，并計(jì)算每個(gè)子簇的誤差平方和（SSE）。然后，選擇誤差平方和最大的子簇，并將其再次分成兩個(gè)子簇，重復(fù)執(zhí)行這個(gè)過(guò)程，直到達(dá)到預(yù)定的聚類數(shù)目為止。

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

具有較高的準(zhǔn)確性和穩(wěn)定性，能夠有效地處理大規(guī)模數(shù)據(jù)集，并且不需要指定初始聚類數(shù)目。

該算法還能夠輸出聚類層次結(jié)構(gòu)，便于分析和可視化。

缺點(diǎn)：

計(jì)算復(fù)雜度較高，尤其是在處理大規(guī)模數(shù)據(jù)集時(shí)，需要消耗大量的計(jì)算資源和存儲(chǔ)空間。

此外該算法對(duì)初始簇的選擇也比較敏感，可能會(huì)導(dǎo)致不同的聚類結(jié)果。

DBSCAN

具有噪聲的基于密度的聚類方法（Density-Based Spatial Clustering of Applications with Noise，DBSCAN）是一種典型的基于密度的空間聚類算法。

基于密度的方法的特點(diǎn)是不依賴于距離，而是依賴于密度，從而克服基于距離的算法只能發(fā)現(xiàn)“球形”聚簇的缺點(diǎn)。

DBSCAN算法的核心思想是：對(duì)于一個(gè)給定的數(shù)據(jù)點(diǎn)，如果它的密度達(dá)到一定的閾值，則它屬于一個(gè)簇中；否則，它被視為噪聲點(diǎn)。

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

這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”(凸)的聚類的缺點(diǎn)；

可發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感；

不需要指定類的數(shù)目 cluster；

算法中只有兩個(gè)參數(shù)，掃描半徑 (eps)和最小包含點(diǎn)數(shù)(min_samples)。

缺點(diǎn)：

計(jì)算復(fù)雜度，不進(jìn)行任何優(yōu)化時(shí)，算法的時(shí)間復(fù)雜度是O(N^{2})，通?？衫肦-tree，k-d tree, ball；

tree索引來(lái)加速計(jì)算，將算法的時(shí)間復(fù)雜度降為O(Nlog(N))；

受eps影響較大。在類中的數(shù)據(jù)分布密度不均勻時(shí)，eps較小時(shí)，密度小的cluster會(huì)被劃分成多個(gè)性質(zhì)相似的cluster；eps較大時(shí)，會(huì)使得距離較近且密度較大的cluster被合并成一個(gè)cluster。在高維數(shù)據(jù)時(shí)，因?yàn)榫S數(shù)災(zāi)難問(wèn)題，eps的選取比較困難；

依賴距離公式的選取，由于維度災(zāi)害，距離的度量標(biāo)準(zhǔn)不重要；

不適合數(shù)據(jù)集集中密度差異很大的，因?yàn)閑ps和metric選取很困難。

OPTICS

OPTICS（Ordering Points To Identify the Clustering Structure）是一種基于密度的聚類算法，其能夠自動(dòng)確定簇的數(shù)量，同時(shí)也可以發(fā)現(xiàn)任意形狀的簇，并能夠處理噪聲數(shù)據(jù)。

OPTICS 算法的核心思想是：對(duì)于一個(gè)給定的數(shù)據(jù)點(diǎn)，通過(guò)計(jì)算它到其它點(diǎn)的距離，確定其在密度上的可達(dá)性，從而構(gòu)建一個(gè)基于密度的距離圖。然后，通過(guò)掃描該距離圖，自動(dòng)確定簇的數(shù)量，并對(duì)每個(gè)簇進(jìn)行劃分。

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

能夠自動(dòng)確定簇的數(shù)量，并能夠處理任意形狀的簇，并能夠有效地處理噪聲數(shù)據(jù)。

該算法還能夠輸出聚類層次結(jié)構(gòu)，便于分析和可視化。

缺點(diǎn)：

計(jì)算復(fù)雜度較高，尤其是在處理大規(guī)模數(shù)據(jù)集時(shí)，需要消耗大量的計(jì)算資源和存儲(chǔ)空間。

該算法對(duì)于密度差異較大的數(shù)據(jù)集，可能會(huì)導(dǎo)致聚類效果不佳。

BIRCH

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）是一種基于層次聚類的聚類算法，其可以快速地處理大規(guī)模數(shù)據(jù)集，并且對(duì)于任意形狀的簇都有較好的效果。

BIRCH算法的核心思想是：通過(guò)對(duì)數(shù)據(jù)集進(jìn)行分級(jí)聚類，逐步減小數(shù)據(jù)規(guī)模，最終得到簇結(jié)構(gòu)。BIRCH算法采用一種類似于B樹(shù)的結(jié)構(gòu)，稱為CF樹(shù)，它可以快速地插入和刪除子簇，并且可以自動(dòng)平衡，從而確保簇的質(zhì)量和效率。

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

能夠快速處理大規(guī)模數(shù)據(jù)集，并且對(duì)于任意形狀的簇都有較好的效果。

該算法對(duì)于噪聲數(shù)據(jù)和離群點(diǎn)也有較好的容錯(cuò)性。

缺點(diǎn)：

對(duì)于密度差異較大的數(shù)據(jù)集，可能會(huì)導(dǎo)致聚類效果不佳；

對(duì)于高維數(shù)據(jù)集的效果也不如其他算法。