機(jī)器學(xué)習(xí)之無監(jiān)督學(xué)習(xí)：九大聚類算法

作者：佚名 2023-12-01 16:27:05

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

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

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

市場分割：將數(shù)據(jù)庫中客戶的信息根據(jù)市場進(jìn)行不同的分組，從而實(shí)現(xiàn)對其分別銷售或者根據(jù)不同的市場進(jìn)行服務(wù)改進(jìn)。
社交網(wǎng)絡(luò)分析：通過郵件最頻繁聯(lián)系的人及其最頻繁聯(lián)系的人來找到一個(gè)關(guān)系密切的群體。
組織計(jì)算機(jī)集群：在數(shù)據(jù)中心里，計(jì)算機(jī)集群經(jīng)常一起協(xié)同工作，可以用它來重新組織資源、重新布局網(wǎng)絡(luò)、優(yōu)化數(shù)據(jù)中心以及通信數(shù)據(jù)。
了解銀河系的構(gòu)成：利用這些信息來了解一些天文學(xué)的知識(shí)。

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

常見的幾種聚類算法有：

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 年提出來的，最開始是用于脈沖編碼調(diào)制，直到 1982 年才將該算法對外公布。1965 年，Edward W.Forgy 發(fā)布了相同的算法，因此 K-Means 有時(shí)被稱為 Lloyd-Forgy。

在聚類問題中，我們會(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è)無標(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)行簇分配，也就是說，遍歷每一個(gè)樣本，再根據(jù)每一個(gè)點(diǎn)到聚類中心距離的遠(yuǎn)近將其分配給不同的聚類中心（離誰近分配給誰），對于本例而言，就是遍歷數(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í)可以說 K 均值已經(jīng)聚合了。該算法在找出數(shù)據(jù)中兩個(gè)簇的方面做的相當(dāng)好。

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

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

缺點(diǎn)：

例如對于非球形簇的處理能力較差，容易受到初始簇心的選擇影響，需要預(yù)先指定簇的數(shù)量K等。
此外，當(dāng)數(shù)據(jù)點(diǎn)之間存在噪聲或者離群點(diǎn)時(shí)，K-Means算法可能會(huì)將它們分配到錯(cuò)誤的簇中。

Hierarchical Clustering

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

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

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

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

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

應(yīng)用 K-means 的結(jié)果取決于要搜索的聚類數(shù)量的選擇和起始配置分配。相反，層次聚類方法不需要這樣的規(guī)范。相反，它們要求用戶根據(jù)兩組觀察值之間的成對差異性，指定（不相交）觀察組之間的差異性度量。顧名思義，它們產(chǎn)生層次結(jié)構(gòu)表示，其中層次結(jié)構(gòu)每個(gè)級別的集群都是通過合并下一個(gè)較低級別的集群來創(chuàng)建的。在最低級別，每個(gè)集群包含一個(gè)觀察值。在最高級別，只有一個(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ǔ)空間。
該算法對初始簇的選擇也比較敏感，可能會(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ī)初始化簇心，而是通過計(jì)算數(shù)據(jù)點(diǎn)之間的相似性得出最終的聚類結(jié)果。

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

不需要制定最終聚類族的個(gè)數(shù)
已有的數(shù)據(jù)點(diǎn)作為最終的聚類中心，而不是新生成一個(gè)簇中心。
模型對數(shù)據(jù)的初始值不敏感。
對初始相似度矩陣數(shù)據(jù)的對稱性沒有要求。
相比與 k-centers 聚類方法，其結(jié)果的平方差誤差較小。

缺點(diǎn)：

該算法的計(jì)算復(fù)雜度較高，需要大量的存儲(chǔ)空間和計(jì)算資源；
對于噪聲點(diǎn)和離群點(diǎn)的處理能力較弱。

Mean Shift Clustering

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

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

不需要指定簇的數(shù)目，且對于形狀復(fù)雜的簇也有很好的效果。
算法還能夠有效地處理噪聲數(shù)據(jù)。

缺點(diǎn)：

計(jì)算復(fù)雜度較高，尤其是在處理大規(guī)模數(shù)據(jù)集時(shí)，需要消耗大量的計(jì)算資源和存儲(chǔ)空間；
該算法還對初始參數(shù)的選擇比較敏感，需要進(jìn)行參數(shù)調(diào)整和優(yōu)化。

Bisecting K-Means

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

算法首先將所有數(shù)據(jù)點(diǎn)視為一個(gè)初始簇，然后對該簇應(yīng)用K-Means算法，將該簇分成兩個(gè)子簇，并計(jì)算每個(gè)子簇的誤差平方和（SSE）。然后，選擇誤差平方和最大的子簇，并將其再次分成兩個(gè)子簇，重復(fù)執(zhí)行這個(gè)過程，直到達(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ǔ)空間。
此外該算法對初始簇的選擇也比較敏感，可能會(huì)導(dǎo)致不同的聚類結(jié)果。

DBSCAN

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

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

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

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

這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”(凸)的聚類的缺點(diǎn)；
可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(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})，通常可利用R-tree，k-d tree, ball；
tree索引來加速計(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)難問題，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 算法的核心思想是：對于一個(gè)給定的數(shù)據(jù)點(diǎn)，通過計(jì)算它到其它點(diǎn)的距離，確定其在密度上的可達(dá)性，從而構(gòu)建一個(gè)基于密度的距離圖。然后，通過掃描該距離圖，自動(dòng)確定簇的數(shù)量，并對每個(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ǔ)空間。
該算法對于密度差異較大的數(shù)據(jù)集，可能會(huì)導(dǎo)致聚類效果不佳。

BIRCH

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

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