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

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

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

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

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

今天拿出最常見(jiàn)的 10 種聚類算法和大家聊聊~

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

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

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

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

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

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

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

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

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

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

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

2、基于密度的聚類算法

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

3、K均值聚類

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

4、凝聚層次聚類

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

5、均值漂移算法

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

聚類算法

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

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

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

1、KNN

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

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

計(jì)算訓(xùn)練樣本和測(cè)試樣本中每個(gè)樣本點(diǎn)的距離(常見(jiàn)的距離度量有歐式距離，馬氏距離等);

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

選前k 個(gè)最小距離的樣本;

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

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

(1)一般k 會(huì)取一個(gè)較小的值，然后用過(guò)交叉驗(yàn)證來(lái)確定;

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

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

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

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

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

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

2、K-Means

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

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

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

時(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)點(diǎn)：原理比較簡(jiǎn)單，實(shí)現(xiàn)也是很容易，收斂速度快;聚類效果較優(yōu);算法的可解釋度比較強(qiáng);主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k。

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

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

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

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

5、對(duì)噪音和異常點(diǎn)比較的敏感。

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

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

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

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

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

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

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

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

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

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

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

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

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

二分k均值不太受初始化的困擾，因?yàn)樗鼒?zhí)行了多次二分試驗(yàn)并選取具有最小誤差的試驗(yàn)結(jié)果，還因?yàn)槊坎街挥袃蓚€(gè)質(zhì)心。

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

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

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

3、 層次聚類

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

優(yōu)點(diǎn)：無(wú)需目標(biāo)函數(shù)，沒(méi)有局部極小問(wèn)題或是選擇初始點(diǎn)的問(wèn)題。缺點(diǎn)：計(jì)算代價(jià)大。

4、密度聚類

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

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

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

優(yōu)點(diǎn)：不需要確定要?jiǎng)澐值木垲悅€(gè)數(shù)，聚類結(jié)果沒(méi)有偏倚;抗噪聲，在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感;處理任意形狀和大小的簇，相對(duì)的，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。

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

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

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

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

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

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

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

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

重要術(shù)語(yǔ)

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

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

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

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

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

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