數(shù)據(jù)科學(xué)家必須要掌握的5種聚類算法
聚類是一種將數(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)具有差異很大的屬性或特征。
聚類屬于無監(jiān)督學(xué)習(xí)中的一種方法,也是一種在許多領(lǐng)域中用于統(tǒng)計(jì)數(shù)據(jù)分析的常用技術(shù)。在數(shù)據(jù)科學(xué)中,我們可以使用聚類分析,來獲得一些有價(jià)值的信息。其手段是在應(yīng)用聚類算法時(shí),查看數(shù)據(jù)點(diǎn)會(huì)落入哪些類。
現(xiàn)在,我們來看看數(shù)據(jù)科學(xué)家們需要掌握的5種常見聚類算法以及它們的優(yōu)缺點(diǎn)! ▌K-均值聚類 K-Means可能是最知名的聚類算法,沒有之一。在很多介紹性的數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)課程中,都有講授該算法。并且該算法的代碼很容易理解和實(shí)現(xiàn)!你可以通過看下面的插圖來理解它。
K均值聚類
1、首先,我們選擇一些要使用的類/組,并隨機(jī)初始化他們各自的中心點(diǎn)(質(zhì)心)。要計(jì)算出簇(類)的使用數(shù)量,最好的方法是快速查看一下數(shù)據(jù)并嘗試鑒別有多少不同的分組。中心點(diǎn)是一個(gè)矢量,它到每個(gè)數(shù)據(jù)點(diǎn)的矢量長度相同,在上圖中用“X”來表示。 2、每個(gè)數(shù)據(jù)點(diǎn)通過計(jì)算該點(diǎn)與每個(gè)簇中心之間的距離來進(jìn)行分類,根據(jù)最小距離,將該點(diǎn)分類到對應(yīng)中心點(diǎn)的簇中。 3、根據(jù)這些已分類的點(diǎn),我們重新計(jì)算簇中所有向量的均值,來確定新的中心點(diǎn)。 4、重復(fù)以上步驟來進(jìn)行一定數(shù)量的迭代,或者直到簇中心點(diǎn)在迭代之間變化不大。你也可以選擇多次隨機(jī)初始化簇中心點(diǎn),然后選擇看起來像是最佳結(jié)果的數(shù)據(jù),再來重復(fù)以上步驟。 K-Means算法的優(yōu)勢在于它的速度非常快,因?yàn)槲覀兯龅闹皇怯?jì)算點(diǎn)和簇中心之間的距離; 這已經(jīng)是非常少的計(jì)算了!因此它具有線性的復(fù)雜度O(n)。 但是,K-Means算法也是有一些缺點(diǎn)。首先,你必須手動(dòng)選擇有多少簇。
這是一個(gè)很大的弊端,理想情況下,我們是希望能使用一個(gè)聚類算法來幫助我們找出有多少簇,因?yàn)榫垲愃惴ǖ哪康木褪菑臄?shù)據(jù)中來獲得一些有用信息。
K-means算法的另一個(gè)缺點(diǎn)是從隨機(jī)選擇的簇中心點(diǎn)開始運(yùn)行,這導(dǎo)致每一次運(yùn)行該算法可能產(chǎn)生不同的聚類結(jié)果。
因此,該算法結(jié)果可能具有不可重復(fù),缺乏一致性等性質(zhì)。而其他聚類算法的結(jié)果則會(huì)顯得更一致一些。 K-Medians是與K-Means類似的另一種聚類算法,它是通過計(jì)算類中所有向量的中值,而不是平均值,來確定簇的中心點(diǎn)。
這種方法的優(yōu)點(diǎn)是對數(shù)據(jù)中的異常值不太敏感,但是在較大的數(shù)據(jù)集時(shí)進(jìn)行聚類時(shí),速度要慢得多,造成這種現(xiàn)象的原因是這種方法每次迭代時(shí),都需要對數(shù)據(jù)進(jìn)行排序。 ▌Mean-Shift聚類算法 Mean-Shift是一種基于滑動(dòng)窗口的聚類算法。也可以說它是一種基于質(zhì)心的算法,這意思是它是通過計(jì)算滑動(dòng)窗口中的均值來更新中心點(diǎn)的候選框,以此達(dá)到找到每個(gè)簇中心點(diǎn)的目的。然后在剩下的處理階段中,對這些候選窗口進(jìn)行濾波以消除近似或重復(fù)的窗口,找到最終的中心點(diǎn)及其對應(yīng)的簇。看看下面的圖解。
用于單個(gè)滑動(dòng)窗口的Mean-Shift聚類算法
1、為了闡釋Mean-shift算法,我們可以考慮二維空間中的一組點(diǎn),如上圖所示。我們從一個(gè)以C點(diǎn)(隨機(jī)選擇)為中心,以半徑r為核心的圓滑動(dòng)窗口開始。Mean-shift可以看作是一種等高線算法,在每次迭代中,它能將核函數(shù)(圓滑動(dòng)窗口)移動(dòng)到每個(gè)迭代中較高密度的區(qū)域,直至收斂。 2、在每次迭代中,通過將中心點(diǎn)移動(dòng)到窗口內(nèi)點(diǎn)的平均值處(因此得名),來使滑動(dòng)窗口移向更高密度的區(qū)域。滑動(dòng)窗口內(nèi)的數(shù)據(jù)密度與其內(nèi)部點(diǎn)的數(shù)目成正比。當(dāng)然,通過移動(dòng)窗口中點(diǎn)的平均值,它(滑動(dòng)窗口)就會(huì)逐漸移向點(diǎn)密度更高的區(qū)域。 3、我們繼續(xù)根據(jù)平均值來移動(dòng)滑動(dòng)窗口,直到不能找到一個(gè)移動(dòng)方向,使滑動(dòng)窗口可以容納更多的點(diǎn)。看看上面圖片的動(dòng)畫效果;直到滑動(dòng)窗口內(nèi)不再增加密度(即窗口中的點(diǎn)數(shù)),我們才停止移動(dòng)這個(gè)圓圈。 4、步驟1至步驟3的過程是由許多滑動(dòng)窗口來完成的,直到所有的點(diǎn)都能位于對應(yīng)窗口內(nèi)時(shí)才停止。當(dāng)多個(gè)滑動(dòng)窗口重疊時(shí),該算法就保留包含最多點(diǎn)的窗口。最終所有數(shù)據(jù)點(diǎn)根據(jù)它們所在的滑動(dòng)窗口來確定分到哪一類。 下圖顯示了所有滑動(dòng)窗口從頭到尾的整個(gè)移動(dòng)過程。每個(gè)黑點(diǎn)代表滑動(dòng)窗口的質(zhì)心,每個(gè)灰點(diǎn)代表一個(gè)數(shù)據(jù)點(diǎn)。
Mean-Shift聚類的整個(gè)過程
與K-means聚類算法相比,Mean-shift算法是不需要選擇簇的數(shù)量,因?yàn)樗亲詣?dòng)找尋有幾類。這是一個(gè)相比其他算法巨大的優(yōu)點(diǎn)。而且該算法的聚類效果也是非常理想的,在自然數(shù)據(jù)驅(qū)動(dòng)的情況下,它能非常直觀的展現(xiàn)和符合其意義。算法的缺點(diǎn)是固定了窗口大小/半徑“r”。 ▌基于密度的噪聲應(yīng)用空間聚類(DBSCAN) DBSCAN是一種基于密度的聚類算法,類似于Mean-shift算法,但具有一些顯著的優(yōu)點(diǎn)。我們從看下面這個(gè)奇特的圖形開始了解該算法。
DBSCAN笑臉人臉聚類
1、DBSCAN算法從一個(gè)未被訪問的任意的數(shù)據(jù)點(diǎn)開始。這個(gè)點(diǎn)的鄰域是用距離epsilon來定義(即該點(diǎn)ε距離范圍內(nèi)的所有點(diǎn)都是鄰域點(diǎn))。 2、如果在該鄰域內(nèi)有足夠數(shù)量的點(diǎn)(根據(jù)minPoints的值),則聚類過程開始,并且當(dāng)前數(shù)據(jù)點(diǎn)成為新簇中的第一個(gè)點(diǎn)。否則,該點(diǎn)將被標(biāo)記為噪聲(稍后,這個(gè)噪聲點(diǎn)可能成為聚類中的一部分)。在這兩種情況下,該點(diǎn)都會(huì)被標(biāo)記為“已訪問”。 3、對于新簇中的第一個(gè)點(diǎn),它的ε距離鄰域內(nèi)的點(diǎn)也會(huì)成為同簇的一部分。這個(gè)過程使ε鄰域內(nèi)的所有點(diǎn)都屬于同一個(gè)簇,然后對才添加到簇中的所有新點(diǎn)重復(fù)上述過程。 4、重復(fù)步驟2和3兩個(gè)過程直到確定了聚類中的所有點(diǎn)才停止,即訪問和標(biāo)記了聚類的ε鄰域內(nèi)的所有點(diǎn)。 5、一旦我們完成了當(dāng)前的聚類,就檢索和處理新的未訪問的點(diǎn),就能進(jìn)一步發(fā)現(xiàn)新的簇或者是噪聲。重復(fù)上述過程,直到所有點(diǎn)被標(biāo)記為已訪問才停止。由于所有點(diǎn)已經(jīng)被訪問完畢,每個(gè)點(diǎn)都被標(biāo)記為屬于一個(gè)簇或是噪聲。 與其他聚類算法相比,DBSCAN具有很多優(yōu)點(diǎn)。首先,它根本不需要確定簇的數(shù)量。不同于Mean-shift算法,當(dāng)數(shù)據(jù)點(diǎn)非常不同時(shí),會(huì)將它們單純地引入簇中,DBSCAN能將異常值識(shí)別為噪聲。另外,它能夠很好地找到任意大小和任意形狀的簇。 DBSCAN算法的主要缺點(diǎn)是,當(dāng)數(shù)據(jù)簇密度不均勻時(shí),它的效果不如其他算法好。這是因?yàn)楫?dāng)密度變化時(shí),用于識(shí)別鄰近點(diǎn)的距離閾值ε和minPoints的設(shè)置將隨著簇而變化。在處理高維數(shù)據(jù)時(shí)也會(huì)出現(xiàn)這種缺點(diǎn),因?yàn)殡y以估計(jì)距離閾值ε。 ▌使用高斯混合模型(GMM)的期望最大化(EM)聚類 K-Means算法的主要缺點(diǎn)之一就是它對于聚類中心平均值的使用太單一。
通過查看下面的圖例,我們可以明白為什么它不是使用均值最佳的方式。
在左側(cè),人眼看起來非常明顯的是,具有相同均值的數(shù)據(jù)中心點(diǎn),卻是不同半徑長度的兩個(gè)圓形簇。
而K-Means算法不能解決這樣的數(shù)據(jù)問題,因?yàn)檫@些簇的均值是非常接近的。
K-Means算法在簇不是圓形的情況下也一樣無效,也是由于使用均值作為集群中心。
K-Means算法兩個(gè)失敗的案例
相較于K-means算法,高斯混合模型(GMMs)能處理更多的情況。對于GMM,我們假設(shè)數(shù)據(jù)點(diǎn)是高斯分布的; 這是一個(gè)限制較少的假設(shè),而不是用均值來表示它們是圓形的。這樣,我們有兩個(gè)參數(shù)來描述簇的形狀:即均值和標(biāo)準(zhǔn)差!以二維為例,這意味著這些簇可以是任何類型的橢圓形(因?yàn)镚MM在x和y方向上都有標(biāo)準(zhǔn)偏差)。因此,每個(gè)高斯分布都被單個(gè)簇所指定。 為了找到每個(gè)簇的高斯參數(shù)(例如平均值和標(biāo)準(zhǔn)差),我們將使用期望最大化(EM)的優(yōu)化算法。請看下面的圖表,可以作為匹配簇的高斯圖的闡釋。然后我們來完成使用GMM的期望最大化聚類過程。
使用GMM的EM聚類
1、我們首先選擇簇的數(shù)量(如K-Means),然后隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)。可以通過快速查看數(shù)據(jù)的方式,來嘗試為初始參數(shù)提供一個(gè)較好的猜測。不過請注意,從上圖可以看出,這不是100%必要的,因?yàn)榧词故菑囊粋€(gè)很差的高斯分布開始,算法也能很快的優(yōu)化它。 2、給定每個(gè)簇的高斯分布,計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于特定簇的概率。一個(gè)點(diǎn)越靠近高斯的中心,它越可能屬于該簇。在使用高斯分布時(shí)這應(yīng)該是非常直觀的,因?yàn)槲覀兗僭O(shè)大部分?jǐn)?shù)據(jù)更靠近簇的中心。 3、基于這些概率,我們?yōu)楦咚狗植加?jì)算一組新的參數(shù),使得我們能最大化簇內(nèi)數(shù)據(jù)點(diǎn)的概率。我們使用數(shù)據(jù)點(diǎn)位置的加權(quán)和來計(jì)算這些新參數(shù),其中權(quán)重是數(shù)據(jù)點(diǎn)屬于該特定簇的概率。為了更直觀的解釋這個(gè),我們可以看看上面的圖片,特別是黃色的簇。第一次迭代時(shí),分布是隨機(jī)開始,但是我們可以看到大部分黃點(diǎn)都在分布的右側(cè)。當(dāng)我們計(jì)算按概率加權(quán)的和時(shí),即使中心附近的點(diǎn)大部分都在右邊,通過分配的均值自然就會(huì)接近這些點(diǎn)。我們也可以看到,大部分?jǐn)?shù)據(jù)點(diǎn)都是“從右上到左下”。因此,改變標(biāo)準(zhǔn)差的值,可以找到一個(gè)更適合這些點(diǎn)的橢圓,以最大化概率加權(quán)的總和。 4、重復(fù)迭步驟2和3,直到收斂,也就是分布在迭代中基本再無變化。 使用GMM方法有兩個(gè)很重要的優(yōu)點(diǎn)。 首先,GMM方法在聚類協(xié)方差上比K-Means靈活得多; 由于使用了標(biāo)準(zhǔn)偏差參數(shù),簇可以呈現(xiàn)任何橢圓形狀,而不是被限制為圓形。 K-mean算法實(shí)際上是GMM的一個(gè)特殊情況,即每個(gè)簇的協(xié)方差在所有維度上都接近0。其次,由于GMM使用了概率,每個(gè)數(shù)據(jù)點(diǎn)可以有多個(gè)簇。因此,如果一個(gè)數(shù)據(jù)點(diǎn)位于兩個(gè)重疊的簇的中間,我們可以簡單地定義它的類,即屬于類1的概率是百分之X,屬于類2的概率是百分之Y。即,GMM支持混合類這種情況。 ▌凝聚層次聚類 分層聚類算法實(shí)際上分為兩類:自上而下或自下而上。
自下而上的算法首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇,然后連續(xù)地合并(或聚合)成對的簇,直到所有的簇都合并成一個(gè)包含所有數(shù)據(jù)點(diǎn)的簇。
因此,自下而上的分層聚類被稱為合成聚類或HAC。
這個(gè)簇的層次可以用樹(或樹狀圖)表示。樹的根是收集所有樣本的唯一簇,葉是僅具有一個(gè)樣本的簇。
在進(jìn)入算法步驟之前,請查看下面的圖解。
合成聚類
1、我們首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇,即如果我們的數(shù)據(jù)集中有X個(gè)數(shù)據(jù)點(diǎn),那么我們就有X個(gè)簇。然后,我們選擇一個(gè)距離度量,來度量兩個(gè)簇之間距離。作為一個(gè)例子,我們將使用平均關(guān)聯(lián)度量,它將兩個(gè)簇之間的距離定義為第一個(gè)簇中的數(shù)據(jù)點(diǎn)與第二個(gè)簇中的數(shù)據(jù)點(diǎn)之間的平均距離。 2、在每次迭代中,我們將兩個(gè)簇合并成一個(gè)簇。選擇平均關(guān)聯(lián)值最小的兩個(gè)簇進(jìn)行合并。根據(jù)我們選擇的距離度量,這兩個(gè)簇之間的距離最小,因此是最相似的,所有應(yīng)該合并。 3、重復(fù)步驟2直到我們到達(dá)樹的根,即我們只有一個(gè)包含所有數(shù)據(jù)點(diǎn)的簇。通過這種方式,我們可以選擇最終需要多少個(gè)簇。方法就是選擇何時(shí)停止合并簇,即停止構(gòu)建樹時(shí)! 分層次聚類不需要我們指定簇的數(shù)量,我們甚至可以在構(gòu)建樹的同時(shí),選擇一個(gè)看起來效果最好的簇的數(shù)量。
另外,該算法對距離度量的選擇并不敏感;
與其他距離度量選擇很重要的聚類算法相比,該算法下的所有距離度量方法都表現(xiàn)得很好。
當(dāng)基礎(chǔ)數(shù)據(jù)具有層次結(jié)構(gòu),并且想要恢復(fù)層次結(jié)構(gòu)時(shí),層次聚類算法能實(shí)現(xiàn)這一目標(biāo);
而其他聚類算法則不能做到這一點(diǎn)。
與K-Means和GMM的線性復(fù)雜性不同,層次聚類的這些優(yōu)點(diǎn)是以較低的效率為代價(jià),即它具有O(n3)的時(shí)間復(fù)雜度。

責(zé)任編輯:售電衡衡
-
權(quán)威發(fā)布 | 新能源汽車產(chǎn)業(yè)頂層設(shè)計(jì)落地:鼓勵(lì)“光儲(chǔ)充放”,有序推進(jìn)氫燃料供給體系建設(shè)
2020-11-03新能源,汽車,產(chǎn)業(yè),設(shè)計(jì) -
中國自主研制的“人造太陽”重力支撐設(shè)備正式啟運(yùn)
2020-09-14核聚變,ITER,核電 -
探索 | 既耗能又可供能的數(shù)據(jù)中心 打造融合型綜合能源系統(tǒng)
2020-06-16綜合能源服務(wù),新能源消納,能源互聯(lián)網(wǎng)
-
新基建助推 數(shù)據(jù)中心建設(shè)將迎爆發(fā)期
2020-06-16數(shù)據(jù)中心,能源互聯(lián)網(wǎng),電力新基建 -
泛在電力物聯(lián)網(wǎng)建設(shè)下看電網(wǎng)企業(yè)數(shù)據(jù)變現(xiàn)之路
2019-11-12泛在電力物聯(lián)網(wǎng) -
泛在電力物聯(lián)網(wǎng)建設(shè)典型實(shí)踐案例
2019-10-15泛在電力物聯(lián)網(wǎng)案例
-
新基建之充電樁“火”了 想進(jìn)這個(gè)行業(yè)要“心里有底”
2020-06-16充電樁,充電基礎(chǔ)設(shè)施,電力新基建 -
燃料電池汽車駛?cè)雽こ0傩占疫€要多久?
-
備戰(zhàn)全面電動(dòng)化 多部委及央企“定調(diào)”充電樁配套節(jié)奏
-
權(quán)威發(fā)布 | 新能源汽車產(chǎn)業(yè)頂層設(shè)計(jì)落地:鼓勵(lì)“光儲(chǔ)充放”,有序推進(jìn)氫燃料供給體系建設(shè)
2020-11-03新能源,汽車,產(chǎn)業(yè),設(shè)計(jì) -
中國自主研制的“人造太陽”重力支撐設(shè)備正式啟運(yùn)
2020-09-14核聚變,ITER,核電 -
能源革命和電改政策紅利將長期助力儲(chǔ)能行業(yè)發(fā)展
-
探索 | 既耗能又可供能的數(shù)據(jù)中心 打造融合型綜合能源系統(tǒng)
2020-06-16綜合能源服務(wù),新能源消納,能源互聯(lián)網(wǎng) -
5G新基建助力智能電網(wǎng)發(fā)展
2020-06-125G,智能電網(wǎng),配電網(wǎng) -
從智能電網(wǎng)到智能城市
-
山西省首座電力與通信共享電力鐵塔試點(diǎn)成功
-
中國電建公司公共資源交易服務(wù)平臺(tái)摘得電力創(chuàng)新大獎(jiǎng)
-
電力系統(tǒng)對UPS的技術(shù)要求