各種聚類算法（原理+代碼+對比分析）最全總結

一、聚類的目標

使同一類對象的相似度儘可能地大；不同類對象之間的相似度儘可能地小。

二、聚類算法分類

1.基於劃分

給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K

特點：計算量大。很適合發現中小規模的數據庫中小規模的數據庫中的球狀簇。

算法：K-MEANS算法、K-MEDOIDS算法、CLARANS算法

2.基於層次

對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。

特點：較小的計算開銷。然而這種技術不能更正錯誤的決定。

算法：BIRCH算法、CURE算法、CHAMELEON算法

3.基於密度

只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。

特點：能克服基於距離的算法只能發現“類圓形”的聚類的缺點。

算法：DBSCAN算法、OPTICS算法、DENCLUE算法

4.基於網格

將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。

特點：處理速度很快，通常這是與目標數據庫中記錄的個數無關的，只與把數據空間分為多少個單元有關。

算法：STING算法、CLIQUE算法、WAVE-CLUSTER算法

三、DBscan聚類

1.算法原理

DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一種典型的基於密度的聚類算法，在DBSCAN算法中將數據點分為一下三類：

核心點：在半徑Eps內含有超過MinPts數目的點

邊界點：在半徑Eps內點的數量小於MinPts，但是落在核心點的鄰域內

噪音點：既不是核心點也不是邊界點的點

在這裡有兩個量，一個是半徑Eps，另一個是指定的數目MinPts

2.代碼

<code>#  encoding=utf-8
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
class DBScan (object):
    """
    the class inherits from object, encapsulate the  DBscan algorithm
    """
    def __init__(self, p, l_stauts):
        
        self.point = p
        self.labels_stats = l_stauts
        self.db = DBSCAN(eps=0.2, min_samples=10).fit(self.point)
    def draw(self):
     
        coreSamplesMask = np.zeros_like(self.db.labels_, dtype=bool)
        coreSamplesMask[self.db.core_sample_indices_] = True
        labels = self.db.labels_
        nclusters = jiangzao(labels)
        # 輸出模型評估參數，包括估計的集群數量、均勻度、完整性、V度量、
        # 調整後的蘭德指數、調整後的互信息量、輪廓係數
        print('Estimated number of clusters: %d' % nclusters)
        print("Homogeneity: %0.3f" % metrics.homogeneity_score(self.labels_stats, labels))
        print("Completeness: %0.3f" % metrics.completeness_score(self.labels_stats, labels))
        print("V-measure: %0.3f" % metrics.v_measure_score(self.labels_stats, labels))
        print("Adjusted Rand Index: %0.3f"
              % metrics.adjusted_rand_score(self.labels_stats, labels))
        print("Adjusted Mutual Information: %0.3f"
              % metrics.adjusted_mutual_info_score(self.labels_stats, labels))
        print("Silhouette Coefficient: %0.3f"
              % metrics.silhouette_score(self.point, labels))
        # 繪製結果
        # 黑色被移除，並被標記為噪音。
        unique_labels = set(labels)
        colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
        for k, col in zip(unique_labels, colors): 

            if k == -1:
                # 黑色用於噪聲
                col = 'k'
            classMemberMask = (labels == k)
            # 畫出分類點集
            xy = self.point[classMemberMask & coreSamplesMask]
            plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                     markeredgecolor='k', markersize=6)
            # 畫出噪聲點集
            xy = self.point[classMemberMask & ~coreSamplesMask]
            plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
                     markeredgecolor='k', markersize=3)
        # 加標題，顯示分類數
        plt.title('Estimated number of clusters: %d' % nclusters)
        plt.show()
def jiangzao (labels):
    
    # 標籤中的簇數，忽略噪聲（如果存在）
    clusters = len(set(labels)) - (1 if -1 in labels else 0)
    return clusters
def standar_scaler(points):
    
    p = StandardScaler().fit_transform(points)
    return p
if __name__ == "__main__":
     """
     test class dbScan
     """
     centers = [[1, 1], [-1, -1], [-1, 1], [1, -1]]
     point, labelsTrue = make_blobs(n_samples=2000, centers=centers, cluster_std=0.4,
                                    random_state=0)
     point = standar_scaler(point)
     db = DBScan(point, labelsTrue)
     db.draw()/<code>

3.圖形輸出

如圖算法自動將數據集分成了4簇，用四種顏色代表。每一簇內較大的點代表核心對象，較小的點代表邊界點（與簇內其他點密度相連，但是自身不是核心對象）。黑色的點代表離群點或者叫噪聲點。

4.控制檯輸出

<code>Estimated number of clusters: 4
Homogeneity: 0.928
Completeness: 0.862
V-measure: 0.894
Adjusted Rand Index: 0.928
Adjusted Mutual Information: 0.862
Silhouette Coefficient: 0.584/<code>

四、K-means聚類

1.算法原理

2.代碼

<code>#coding=utf-8
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
#從磁盤讀取城市經緯度數據
X = []
f = open('city.txt')
for v in f:
    X.append([float(v.split(',')[1]), float(v.split(',')[2])])
#轉換成numpy array
X = np.array(X)
#類簇的數量
n_clusters = 5
#現在把數據和對應的分類書放入聚類函數中進行聚類
cls = KMeans(n_clusters).fit(X)
#X中每項所屬分類的一個列表
cls.labels_
#畫圖
markers = ['^', 'x', 'o', '*', '+']
for i in range(n_clusters):
  members = cls.labels_ == i
  plt.scatter(X[members, 0], X[members, 1], s=60, marker=markers[i], c='b', alpha=0.5)
plt.title(' ')
plt.show()/<code>

3.圖像輸出

五、層次聚類

1.算法簡介

凝聚層次聚類：所謂凝聚的，指的是該算法初始時，將每個點作為一個簇，每一步合併兩個最接近的簇。另外即使到最後，對於噪音點或是離群點也往往還是各佔一簇的，除非過度合併。對於這裡的“最接近”，有下面三種定義。我在實現是使用了MIN，該方法在合併時，只要依次取當前最近的點對，如果這個點對當前不在一個簇中，將所在的兩個簇合並就行：

單鏈(MIN):定義簇的鄰近度為不同兩個簇的兩個最近的點之間的距離。

全鏈(MAX):定義簇的鄰近度為不同兩個簇的兩個最遠的點之間的距離。

組平均：定義簇的鄰近度為取自兩個不同簇的所有點對鄰近度的平均值。

2.代碼

<code># scoding=utf-8
# Agglomerative Hierarchical Clustering(AHC)
import pylab as pl
from operator import itemgetter
from collections import OrderedDict,Counter
points = [[int(eachpoint.split('#')[0]), int(eachpoint.split('#')[1])] for eachpoint in open("points","r")]
# 初始時每個點指派為單獨一簇 

groups = [idx for idx in range(len(points))]
# 計算每個點對之間的距離
disP2P = {}
for idx1,point1 in enumerate(points):
  for idx2,point2 in enumerate(points):
    if (idx1 < idx2):
      distance = pow(abs(point1[0]-point2[0]),2) + pow(abs(point1[1]-point2[1]),2)
      disP2P[str(idx1)+"#"+str(idx2)] = distance
# 按距離降序將各個點對排序
disP2P = OrderedDict(sorted(disP2P.iteritems(), key=itemgetter(1), reverse=True))
# 當前有的簇個數
groupNum = len(groups)
# 過分合並會帶入噪音點的影響，當簇數減為finalGroupNum時，停止合併
finalGroupNum = int(groupNum*0.1)
while groupNum > finalGroupNum:
  # 選取下一個距離最近的點對
  twopoins,distance = disP2P.popitem()
  pointA = int(twopoins.split('#')[0])
  pointB = int(twopoins.split('#')[1])
  pointAGroup = groups[pointA]
  pointBGroup = groups[pointB]
  # 當前距離最近兩點若不在同一簇中，將點B所在的簇中的所有點合併到點A所在的簇中，此時當前簇數減1
  if(pointAGroup != pointBGroup):
    for idx in range(len(groups)):
      if groups[idx] == pointBGroup:
        groups[idx] = pointAGroup
    groupNum -= 1
# 選取規模最大的3個簇，其他簇歸為噪音點
wantGroupNum = 3
finalGroup = Counter(groups).most_common(wantGroupNum)
finalGroup = [onecount[0] for onecount in finalGroup]
dropPoints = [points[idx] for idx in range(len(points)) if groups[idx] not in finalGroup]
# 打印規模最大的3個簇中的點
group1 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[0]]
group2 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[1]]
group3 = [points[idx] for idx in range(len(points)) if groups[idx]==finalGroup[2]] 

pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or')
pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy')
pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og')
# 打印噪音點，黑色
pl.plot([eachpoint[0] for eachpoint in dropPoints], [eachpoint[1] for eachpoint in dropPoints], 'ok')
pl.show()/<code>

3.圖像輸出

閱讀更多 風信子編程 的文章

關鍵字: 技術 算法 最全