聚類算法：

聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統計分析方法，同時也是數據挖掘的一個重要算法。

聚類（Cluster）分析是由若干模式（Pattern）組成的，通常，模式是一個度量（Measurement）的向量，或者是多維空間中的一個點。

聚類分析以相似性為基礎，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。

俗話說：“物以類聚，人以群分”，在自然科學和社會科學中，存在著大量的分類問題。所謂類，通俗地說，就是指相似元素的集合。

聚類分析起源于分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行定量的分類。隨著人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切地進行分類，于是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之后又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

常見聚類算法：

????????? 1.原型聚類：K-means , KNN , LVQ

?????????? 2.密度聚類：DBSCAN

?????????? 3.層次聚類： AGNES

?????????? 4.模糊聚類：高斯混合模型

?????????? 5.譜聚類

1 K-means聚類算法（K均值算法）

定義： 通過把樣本分離成 n 個具有相同方差的類的方式來聚集數據，最小化稱為 慣量(inertia) 或 簇內平方和(within-cluster sum-of-squares)的標準（criterion）。該算法需要指定簇的數量K。

算法：采用貪心策略通過迭代優化來近似求解?

? ? ? ? ? ?

優點：速度快，簡單

缺點：1.適合聚類球狀類簇，不能發現一些混合度較高，非球狀類簇

2.需指定簇個數

3.算法結果不穩定，最終結果跟初始點選擇相關，容易陷入局部最優

4.對噪聲或離群點比較敏感：無法區分出哪些是噪聲或者離群點，只能給每個數據點都判斷出一個類別來，這樣會導致樣本質心偏移，導致誤判或者聚類緊密程度降低。

kmeans算法結果易受初始點影響

由于kmeans算法結果易受初始點影響，得到的結果是局部最優，為次，我們可以運行n次kmeans算法，每次運行的初始點均為隨機生成。然后在n次運行結果中，選取目標函數(代價函數)最小的聚類結果。

聚類數量k如何確定?

? ? ? ?通常在數據集有多少個聚類是不清楚的。對于低維的數據，對其可視化，我們可以通過肉眼觀察到有多少個聚類，但這樣并不準確，而且大部分數據也無法可視化顯示。方法1：我們可以通過構建一個代價函數與聚類數量k的關系圖，如下圖所示，橫坐標是聚類數量，每個聚類數量對應的代價函數J均是n次運行的最優結果。觀察下圖，代價函數隨聚類數量增大而減小，但并不是說聚類數量越多越好，比如：對于m個樣本，m個聚類的代價函數自然是0，但這樣根本不合理。觀察下圖，代價函數在沒有到拐點之前下降很快，拐點之后下降變緩，我們就可以考慮選擇這個拐點對應的數量作為聚類數量，這是一種較為合理的方法，但受限于能否得到一個清晰的拐點，如右下圖所示，

?

2 KNN聚類算法

算距離：給定待分類樣本，計算它與已分類樣本中的每個樣本的距離；

找鄰居：圈定與待分類樣本距離最近的K個已分類樣本，作為待分類樣本的近鄰；

做分類：根據這K個近鄰中的大部分樣本所屬的類別來決定待分類樣本該屬于哪個分類；

? ? ? ? ? ? ??

?

3 DBSCAN

?聚類原則：聚類距離簇邊界最近的點

算法流程：

核心點：核心點的半徑范圍內的樣本個數≥最少點數

邊界點：邊界點的半徑范圍內的樣本個數小于最少點數大于0

噪聲點：噪聲 點的半徑范圍的樣本個數為0

DBSCAN 算法有兩個參數：半徑 eps 和密度閾值 MinPts，具體步驟為：

1、以每一個數據點 xi 為圓心，以 eps 為半徑畫一個圓圈。這個圓圈被稱為 xi 的 eps 鄰域

2、對這個圓圈內包含的點進行計數。如果一個圓圈里面的點的數目超過了密度閾值 MinPts，那么將該圓圈的圓心記為核心點，又稱核心對象。如果某個點的 eps 鄰域內點的個數小于密度閾值但是落在核心點的鄰域內，則稱該點為邊界點。既不是核心點也不是邊界點的點，就是噪聲點。

?3、核心點 xi 的 eps 鄰域內的所有的點，都是 xi 的直接密度直達。如果 xj 由 xi 密度直達，xk 由 xj 密度直達。。。xn 由 xk 密度直達，那么，xn 由 xi 密度可達。這個性質說明了由密度直達的傳遞性，可以推導出密度可達。

4、如果對于 xk，使 xi 和 xj 都可以由 xk 密度可達，那么，就稱 xi 和 xj 密度相連。將密度相連的點連接在一起，就形成了我們的聚類簇。

?

?4 AGNES

算法流程：
(1) 將每個對象看作一類，計算兩兩之間的最小距離；

(2) 將距離最小的兩個類合并成一個新類；

(3) 重新計算新類與所有類之間的距離；

(4) 重復(2)、(3)，直到所有類最后合并成一類

?

5 譜聚類算法

譜聚類是基于譜圖理論基礎上的一種聚類方法，與傳統的聚類方法相比:

1. 具有在任意形狀的樣本空間上聚類并且收斂于全局最優解的優點。
2. 通過對樣本數據的拉普拉斯矩陣的特征向量進行聚類，從而達到對樣本數據進行聚類的目的;

其本質是將聚類問題轉換為圖的最優劃分問題，是一種點對聚類算法。
譜聚類算法將數據集中的每個對象看做圖的頂點V,將頂點間的相似度量化為相應頂點連接邊E的權值w，這樣就構成了一-個基于相似度的無向加權圖G(V,E)，于是聚類問題就轉換為圖的劃分問題。
基于圖的最優劃分規則就是子圖內的相似度最大，子圖間的相似度最小。其中，V代表所有樣本的集

?

?

?

?

?

?

6 模糊聚類算法

模糊c均值聚類原理

模糊c-均值聚類算法 fuzzy c-means algorithm （ FCM）在眾多模糊聚類算法中，模糊C-均值（ FCM） 算法應用最廣泛且較成功，它通過優化目標函數得到每個樣本點對所有類中心的隸屬度，從而決定樣本點的類屬以達到自動對樣本數據進行分類的目的。給每個樣本賦予屬于每個簇的隸屬度函數，通過隸屬度值大小來將樣本歸類。

模糊c均值聚類主要有三個關鍵參數，固定數量的集群、每個群集一個質心、每個數據點屬于最接近質心對應的簇。

（1）目標函數

模糊c均值聚類通過最小化目標函數來得到聚類中心。目標函數本質上是各個點到各個類的歐式距離的和(誤差的平方和）。聚類的過程就是最小化目標函數的過程，通過反復的迭代運算，逐步降低目標函數的誤差值，當目標函數收斂時，可得到最終的聚類結果。
下面是目標函數：

? ? ? ? ? ? ? ?

其中，m為聚類的簇數（類數），N 為樣本數，C 為聚類中心數。cj 表示第 j 個聚類中心，和樣本特征維數相同，xi 表示第 i 個樣本，uij 表示樣本 xi 對聚類中心 cj 的隸屬度(即 xi 屬于 cj 的概率)。||?|| 可以是任意表示數據相似性(距離)的度量，最常見的就是歐幾里得范數（又稱歐氏范數，L2范數，歐氏距離）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（2）隸屬度矩陣Uij和簇中心Cij

隸屬度矩陣應當是 N?C 的矩陣,隸屬度矩陣表示的是每個樣本點屬于每個類的程度。對于單個樣本xi，它對于每個簇的隸屬度之和為1。對于每個樣本點在哪個類的隸屬度最大歸為哪個類。越接近于1表示隸屬度越高，反之越低。

求每組的聚類中心ci，使得目標函數最小（因為目標函數與歐幾里德距離有關，目標函數達到最小時，歐式距離最短，相似度最高），這保證了組內相似度最高，組間相似度最低的聚類原則。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

（3）終止條件

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

上圖為終止條件，其中 t 是迭代步數，ε 是一個很小的常數表示誤差閾值。也就是說迭代地更新 uij 和 cj 直到前后兩次隸屬度最大變化值不超過誤差閾值。即繼續迭代下去，隸屬程度也不會發生較大的變化，認為隸屬度不變了，已經達到比較優（局部最優或全局最優）狀態了。這個過程最終收斂于 Jm 的局部極小值點或鞍點。

模糊c均值聚類算法步驟

（1）選擇聚類中心數C，選擇合適的聚類簇數m，初始化由隸屬度函數確定的矩陣U0（隨機值[0，1]之間初始化）；

（2）計算聚類的中心值Cj；

（3）計算新的隸屬度矩陣Uj

（4）比較Uj和U(j+1)，如果兩者的變化小于某個閾值，則停止算法，否則轉向（2）。

總結

以上是生活随笔為你收集整理的机器学习-常见聚类算法K-means，模糊c-均值，谱聚类 DBSCAN算法等的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。