機器學(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ù)可視化。以下是代碼片段。