機器學(xué)習(xí)聚類算法有哪幾種

聚類是一種將數(shù)據(jù)點按一定規(guī)則分群的機器學(xué)習(xí)技術(shù)。

給定一組數(shù)據(jù)點，我們可以使用聚類算法將每個數(shù)據(jù)點分類到一個特定的簇中。

理論上，屬于同一類的數(shù)據(jù)點應(yīng)具有相似的屬性或特征，而不同類中的數(shù)據(jù)點應(yīng)具有差異很大的屬性或特征。

聚類屬于無監(jiān)督學(xué)習(xí)中的一種方法，也是一種在許多領(lǐng)域中用于統(tǒng)計數(shù)據(jù)分析的常用技術(shù)。

聚類算法在初學(xué)者，工作崗位，都是很常見的算法之一。 聚類算法的重要性不言而喻，

今天拿出最常見的 10 種聚類算法和大家聊聊~

K-means：這是最常見的聚類算法之一，用于將數(shù)據(jù)分成預(yù)定義數(shù)量的簇。

層次聚類：通過構(gòu)建數(shù)據(jù)點之間的層次結(jié)構(gòu)來進(jìn)行聚類，可以是自底向上的凝聚方法或自頂向下的分裂方法。

DBSCAN：一種基于密度的聚類算法，能夠識別任意形狀的簇，同時對噪聲和離群點具有較好的魯棒性。

譜聚類：使用數(shù)據(jù)的相似性矩陣來進(jìn)行聚類，特別適用于復(fù)雜形狀的數(shù)據(jù)集。

高斯混合模型：是一種基于概率模型的聚類方法，適用于估計子群體的分布。

模糊C-means：與K-means相似，但允許一個數(shù)據(jù)點屬于多個簇，每個簇都有一定的隸屬度或概率。

K-medoids：與K-means類似，但使用數(shù)據(jù)點(medoids)而不是均值作為簇的中心。

Mean Shift：通過迭代地更新候選簇中心點來尋找數(shù)據(jù)點密度最高的區(qū)域。

OPTICS：一種基于密度的聚類算法，類似于DBSCAN，但對不同密度的數(shù)據(jù)集表現(xiàn)更好。

BIRCH：專為大型數(shù)據(jù)集設(shè)計的一種層次聚類方法。

這些聚類算法各有優(yōu)缺點，適用于不同類型的數(shù)據(jù)和不同的應(yīng)用場景。選擇合適的聚類算法通常取決于具體的需求、數(shù)據(jù)的特性和計算資源。

2、基于密度的聚類算法

基于密度的聚類算法最大的優(yōu)點在于無需定義類的數(shù)量，其次可以識別出局外點和噪聲點、并且可以對任意形狀的數(shù)據(jù)進(jìn)行聚類。DBSCAN同樣是基于密度的聚類算法，但其原理卻與均值漂移大不相同：首先從沒有被遍歷的任一點開始，利用鄰域距離epsilon來獲取周圍點;如果鄰域內(nèi)點的數(shù)量滿足閾值則此點成為核心點并以此開始新一類的聚類;其鄰域內(nèi)的所有點也屬于同一類，將所有的鄰域內(nèi)點以epsilon為半徑進(jìn)行步驟二的計算;重復(fù)步驟二、三直到變量完所有核心點的鄰域點;此類聚類完成，同時又以任意未遍歷點開始步驟一到四直到所有數(shù)據(jù)點都被處理;最終每個數(shù)據(jù)點都有自己的歸屬類別或者屬于噪聲。

3、K均值聚類

這一最著名的聚類算法主要基于數(shù)據(jù)點之間的均值和與聚類中心的聚類迭代而成。它主要的優(yōu)點是十分的高效，由于只需要計算數(shù)據(jù)點與劇類中心的距離，其計算復(fù)雜度只有O(n)。其工作原理主要分為以下四步：首先我們需要預(yù)先給定聚類的數(shù)目同時隨機初始化聚類中心。我們可以初略的觀察數(shù)據(jù)并給出較為準(zhǔn)確的聚類數(shù)目;每一個數(shù)據(jù)點通過計算與聚類中心的距離了來分類到最鄰近的一類中;根據(jù)分類結(jié)果，利用分類后的數(shù)據(jù)點重新計算聚類中心;重復(fù)步驟二三直到聚類中心不再變化。

4、凝聚層次聚類

層次聚類法主要有自頂向下和自底向上兩種方式。其中自底向上的方式，最初將每個點看做是獨立的類別，隨后通過一步步的凝聚最后形成獨立的一大類，并包含所有的數(shù)據(jù)點。這會形成一個樹形結(jié)構(gòu)，并在這一過程中形成聚類。

5、均值漂移算法

這是一種基于滑動窗口的均值算法，用于尋找數(shù)據(jù)點中密度最大的區(qū)域。其目標(biāo)是找出每一個類的中心點，并通過計算滑窗內(nèi)點的均值更新滑窗的中心點。最終消除臨近重復(fù)值的影響并形成中心點，找到其對應(yīng)的類別。其工作原理主要是以下幾點：首先以隨機選取的點為圓心r為半徑做一個圓形的滑窗。其目標(biāo)是找出數(shù)據(jù)點中密度最高點并作為中心;在每個迭代后滑動窗口的中心將為想著較高密度的方向移動;連續(xù)移動，直到任何方向的移動都不能增加滑窗中點的數(shù)量，此時滑窗收斂;將上述步驟在多個滑窗上進(jìn)行以覆蓋所有的點。當(dāng)過個滑窗收斂重疊時，其經(jīng)過的點將會通過其滑窗聚類為一個類。

聚類算法

任務(wù)：將數(shù)據(jù)集中的樣本劃分成若干個通常不相交的子集，對特征空間的一種劃分。

性能度量：類內(nèi)相似度高，類間相似度低。兩大類：1.有參考標(biāo)簽，外部指標(biāo);2.無參照，內(nèi)部指標(biāo)。

距離計算：非負(fù)性，同一性(與自身距離為0)，對稱性，直遞性(三角不等式)。包括歐式距離(二范數(shù))，曼哈頓距離(一范數(shù))等等。

1、KNN

k近鄰(KNN)是一種基本分類與回歸方法。

其思路如下：給一個訓(xùn)練數(shù)據(jù)集和一個新的實例，在訓(xùn)練數(shù)據(jù)集中找出與這個新實例最近的k 個訓(xùn)練實例，然后統(tǒng)計最近的k 個訓(xùn)練實例中所屬類別計數(shù)最多的那個類，就是新實例的類。其流程如下所示：

計算訓(xùn)練樣本和測試樣本中每個樣本點的距離(常見的距離度量有歐式距離，馬氏距離等);

對上面所有的距離值進(jìn)行排序;

選前k 個最小距離的樣本;

根據(jù)這k 個樣本的標(biāo)簽進(jìn)行投票，得到最后的分類類別;

KNN的特殊情況是k =1 的情況，稱為最近鄰算法。對輸入的實例點(特征向量)x ，最近鄰法將訓(xùn)練數(shù)據(jù)集中與x 最近鄰點的類作為其類別。

(1)一般k 會取一個較小的值，然后用過交叉驗證來確定;

(2)距離度量：一般是歐式距離(二范數(shù))，或者曼哈頓距離(一范數(shù))

(3)回歸問題：取K個最近樣本的平均，或者使用加權(quán)平均。

算法的優(yōu)點：(1)思想簡單，理論成熟，既可以用來做分類也可以用來做回歸;(2)可用于非線性分類;(3)訓(xùn)練時間復(fù)雜度為O(n);(4)準(zhǔn)確度高，對數(shù)據(jù)沒有假設(shè)，對outlier不敏感。

缺點：計算量大;樣本不平衡問題(即有些類別的樣本數(shù)量很多，而其它樣本的數(shù)量很少);需要大量的內(nèi)存;

需要考慮問題：(1)KNN的計算成本很高;(2)所有特征應(yīng)該標(biāo)準(zhǔn)化數(shù)量級，否則數(shù)量級大的特征在計算距離上會有偏移;(3)在進(jìn)行KNN前預(yù)處理數(shù)據(jù)，例如去除異常值，噪音等。

KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進(jìn)行快速檢索(那KNN計算的時候不需要對全樣本進(jìn)行距離的計算了)。KD樹更加適用于實例數(shù)量遠(yuǎn)大于空間維度的KNN搜索，如果實例的空間維度與實例個數(shù)差不多時，它的效率基于等于線性掃描。

2、K-Means

K-Means算法是無監(jiān)督的聚類算法，它實現(xiàn)起來比較簡單，聚類效果也不錯，因此應(yīng)用很廣泛。

基本思想：對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

算法步驟：1.隨機選擇k個樣本作為初始均值向量;2.計算樣本到各均值向量的距離，把它劃到距離最小的簇;3.計算新的均值向量;4.迭代，直至均值向量未更新或到達(dá)最大次數(shù)。

時間復(fù)雜度：O(tkmn)，其中，t為迭代次數(shù)，k為簇的數(shù)目，m為記錄數(shù)，n為維數(shù);

空間復(fù)雜度：O((m+k)n)，其中，k為簇的數(shù)目，m為記錄數(shù)，n為維數(shù)。

優(yōu)點：原理比較簡單，實現(xiàn)也是很容易，收斂速度快;聚類效果較優(yōu);算法的可解釋度比較強;主要需要調(diào)參的參數(shù)僅僅是簇數(shù)k。

缺點： 1、聚類中心的個數(shù)K 需要事先給定，這個 K 值的選定是非常難以估計的。很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適;一般通過交叉驗證確定;

2、不同的初始聚類中心可能導(dǎo)致完全不同的聚類結(jié)果。算法速度依賴于初始化的好壞，初始質(zhì)點距離不能太近;

3、如果各隱含類別的數(shù)據(jù)不平衡，比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡，或者各隱含類別的方差不同，則聚類效果不佳;

4、該方法不適于發(fā)現(xiàn)非凸面形狀的簇或大小差別很大的簇，對于不是凸的數(shù)據(jù)集比較難收斂;

5、對噪音和異常點比較的敏感。

6、需樣本存在均值(限定數(shù)據(jù)種類)。

7、采用迭代方法，得到的結(jié)果只是局部最優(yōu)。

K-Means算法改進(jìn)：

1、K-Means++算法就是對K-Means隨機初始化質(zhì)心的方法的優(yōu)化。

K-Means++的對于初始化質(zhì)心的優(yōu)化策略也很簡單，如下：

a) 從輸入的數(shù)據(jù)點集合中隨機選擇一個點作為第一個聚類中心

b) 對于數(shù)據(jù)集中的每一個點，計算它與已選擇的聚類中心中最近聚類中心的距離

c) 選擇一個新的數(shù)據(jù)點作為新的聚類中心，選擇的原則是：距離較大的點，被選取作為聚類中心的概率較大

d) 重復(fù)b和c直到選擇出k個聚類質(zhì)心

e) 利用這k個質(zhì)心來作為初始化質(zhì)心去運行標(biāo)準(zhǔn)的K-Means算法。

2、二分-K均值是為了解決k-均值的用戶自定義輸入簇值k所延伸出來的自己判斷k數(shù)目，針對初始聚類中心選擇問題，其基本思路是：

為了得到k個簇，將所有點的集合分裂成兩個簇，從這些簇中選取一個繼續(xù)分裂，如此下去，直到產(chǎn)生k個簇。

具體描述：比如要分成5個組，第一次分裂產(chǎn)生2個組，然后從這2個組中選一個目標(biāo)函數(shù)產(chǎn)生的誤差比較大的，分裂這個組產(chǎn)生2個，這樣加上開始那1個就有3個組了，然后再從這3個組里選一個分裂，產(chǎn)生4個組，重復(fù)此過程，產(chǎn)生5個組。這算是一中基本求精的思想。

二分k均值不太受初始化的困擾，因為它執(zhí)行了多次二分試驗并選取具有最小誤差的試驗結(jié)果，還因為每步只有兩個質(zhì)心。

3、大樣本優(yōu)化Mini Batch K-Means

也就是用樣本集中的一部分的樣本來做傳統(tǒng)的K-Means，這樣可以避免樣本量太大時的計算難題，算法收斂速度大大加快。當(dāng)然此時的代價就是我們的聚類的精確度也會有一些降低。一般來說這個降低的幅度在可以接受的范圍之內(nèi)。

在Mini Batch K-Means中，我們會選擇一個合適的批樣本大小batch size，我們僅僅用batch size個樣本來做K-Means聚類。那么這batch size個樣本怎么來的?一般是通過無放回的隨機采樣得到的。為了增加算法的準(zhǔn)確性，我們一般會多跑幾次Mini Batch K-Means算法，用得到不同的隨機采樣集來得到聚類簇，選擇其中最優(yōu)的聚類簇。

3、 層次聚類

步驟：1.先將數(shù)據(jù)集中的每個樣本看作一個初始聚類簇;2.找到距離最近的兩個聚類簇進(jìn)行合并。

優(yōu)點：無需目標(biāo)函數(shù)，沒有局部極小問題或是選擇初始點的問題。缺點：計算代價大。

4、密度聚類

DBSCAN既可以適用于凸樣本集，也可以適用于非凸樣本集。找到幾個由密度可達(dá)關(guān)系導(dǎo)出的最大的密度相連樣本集合。即為我們最終聚類的一個類別，或者說一個簇。

基本思想：它任意選擇一個沒有類別的核心對象作為種子，然后找到所有這個核心對象能夠密度可達(dá)的樣本集合，即為一個聚類簇。接著繼續(xù)選擇另一個沒有類別的核心對象去尋找密度可達(dá)的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。

步驟：1、找到任意一個核心點，對該核心點進(jìn)行擴充;2、擴充方法是尋找從該核心點出發(fā)的所有密度相連的數(shù)據(jù)點;3、遍歷該核心的鄰域內(nèi)所有核心點，尋找與這些數(shù)據(jù)點密度相連的點。

優(yōu)點：不需要確定要劃分的聚類個數(shù)，聚類結(jié)果沒有偏倚;抗噪聲，在聚類的同時發(fā)現(xiàn)異常點，對數(shù)據(jù)集中的異常點不敏感;處理任意形狀和大小的簇，相對的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。

缺點：數(shù)據(jù)量大時內(nèi)存消耗大，相比K-Means參數(shù)多一些;樣本集的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量較差，這時用DBSCAN聚類一般不適合;

那么我們什么時候需要用DBSCAN來聚類呢?一般來說，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的，那么用DBSCAN會比K-Means聚類效果好很多。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來聚類。

無監(jiān)督學(xué)習(xí)是機器學(xué)習(xí)技術(shù)中的一類，用于發(fā)現(xiàn)數(shù)據(jù)中的模式。本文介紹用Python進(jìn)行無監(jiān)督學(xué)習(xí)的幾種聚類算法，包括 K-Means 聚類、分層聚類、 t-SNE聚類、 DBSCAN聚類等。

無監(jiān)督學(xué)習(xí)是機器學(xué)習(xí)技術(shù)中的一類，用于發(fā)現(xiàn)數(shù)據(jù)中的模式。無監(jiān)督算法的數(shù)據(jù)沒有標(biāo)注，這意味著只提供輸入變量(X)，沒有相應(yīng)的輸出變量。在無監(jiān)督學(xué)習(xí)中，算法自己去發(fā)現(xiàn)數(shù)據(jù)中有意義的結(jié)構(gòu)。

Facebook首席AI科學(xué)家Yan Lecun解釋說，無監(jiān)督學(xué)習(xí)——即教機器自己學(xué)習(xí)，不需要明確地告訴它們所做的每一件事情是對還是錯，是“真正的”AI的關(guān)鍵。

監(jiān)督學(xué)習(xí) VS 無監(jiān)督學(xué)習(xí)

在監(jiān)督學(xué)習(xí)中，系統(tǒng)試圖從之前給出的例子中學(xué)習(xí)。反之，在無監(jiān)督學(xué)習(xí)中，系統(tǒng)試圖從給出的例子中直接找到模式。因此，如果數(shù)據(jù)集有標(biāo)記，那么它是有監(jiān)督問題，如果數(shù)據(jù)集無標(biāo)記，那么它是一個無監(jiān)督問題。

如上圖，左邊是監(jiān)督學(xué)習(xí)的例子; 我們使用回歸技術(shù)來尋找特征之間的最佳擬合線。而在無監(jiān)督學(xué)習(xí)中，輸入是基于特征分離的，預(yù)測則取決于它屬于哪個聚類(cluster)。

重要術(shù)語

特征(Feature) ：用于進(jìn)行預(yù)測的輸入變量。

預(yù)測(Predictions) ：當(dāng)提供一個輸入示例時，模型的輸出。

示例(Example) ：數(shù)據(jù)集的一行。一個示例包含一個或多個特征，可能有標(biāo)簽。

標(biāo)簽(Label) ：特征的結(jié)果。

為無監(jiān)督學(xué)習(xí)做準(zhǔn)備

在本文中，我們使用 Iris數(shù)據(jù)集(鳶尾花卉數(shù)據(jù)集) 來進(jìn)行我們的第一次預(yù)測。該數(shù)據(jù)集包含150條記錄的一組數(shù)據(jù)，有5個屬性——花瓣長度，花瓣寬度，萼片長度，萼片寬度和類別。三個類別分別是Iris Setosa(山鳶尾)，Iris Virginica(維吉尼亞鳶尾)和Iris Versicolor(變色鳶尾)。對于我們的無監(jiān)督算法，我們給出鳶尾花的這四個特征，并預(yù)測它屬于哪一類。我們在Python中使用sklearn Library來加載Iris數(shù)據(jù)集，并使用matplotlib來進(jìn)行數(shù)據(jù)可視化。以下是代碼片段。