層次聚類和DBSCAN

1.層次聚類

下面這樣的結構應該比較常見，這就是一種層次聚類的樹結構，層次聚類是通過計算不同類別點的相似度創建一顆有層次的樹結構，在這顆樹中，樹的底層是原始數據點，頂層是一個聚類的根節點。

創建這樣一棵樹的方法有自底向上和自頂向下兩種方式。

下面介紹一下如何利用自底向上的方式的構造這樣一棵樹：

為了便于說明，假設我們有5條數據，對這5條數據構造一棵這樣的樹，如下是5條數據：

第一步，計算兩兩樣本之間相似度，然后找到最相似兩條數據（假設1、2兩個最相似），然后將其merge起來，成為1條數據：

現在數據還剩4條，然后同樣計算兩兩之間的相似度，找出最相似的兩條數據（假設前兩條最相似），然后再merge起來：

現在還剩余3條數據，然后繼續重復上面的步驟，假設后面兩條數據最相似，那么：

然后還剩余兩條數據，再把這兩條數據merge起來，最終完成一個樹的構建：

上述就是自底向上聚類樹的構建過程，自頂向下的過程與之相似，只不過初始數據是一個類別，不斷分裂出距離最遠的那個點，知道所有的點都成為葉子結點。

那么我們如何根據這棵樹進行聚類呢？

我們從樹的中間部分切一刀，像下面這樣：

然后葉子節點被分成兩個類別，也可以像下面這樣切：

那么樣本集就被分成3個類別。?這個切割的線是由一個閾值“threshold”來決定切在什么位置，而這個閾值是需要預先給定的?。

但在實做過程中，往往不需要先構建一棵樹，再去進行切分，注意看上面切分，切完后，所剩余的節點數量就是類別個數。

那么在?建樹的過程中，當達到所指定的類別后，則就可以停止樹的建立了?。

下面看一下HAC（自底向上）的實現過程：

import math import numpy as npdef euler_distance(point1, point2):distance = 0.0for a, b in zip(point1, point2):distance += math.pow(a-b, 2)return math.sqrt(distance)# 定義聚類樹的節點 class ClusterNode:def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):"""vec: 保存兩個數據merge后新的中心left: 左節點right: 右節點distance: 兩個節點的距離id: 保存哪個節點是計算過的count: 這個節點的葉子節點個數"""self.vec = vecself.left = leftself.right = rightself.distance = distanceself.id = idself.count = count# 層次聚類的類 # 不同于文中所說的先構建樹，再進行切分，而是直接根據所需類別數目，聚到滿足條件的節點數量即停止 # 和k-means一樣，也需要指定類別數量 class Hierarchical:def __init__(self, k=1):assert k > 0self.k = kself.labels = Nonedef fit(self, x):# 初始化節點各位等于數據的個數nodes = [ClusterNode(vec=v, id=i) for i, v in enumerate(x)]distance = {}point_num, feature_num = np.shape(x)self.labels = [-1] * point_numcurrentclustid = -1while len(nodes) > self.k:min_dist = np.inf# 當前節點的個數nodes_len = len(nodes)# 最相似的兩個類別closest_part = None# 當前節點中兩兩距離計算，找出最近的兩個節點for i in range(nodes_len-1):for j in range(i+1, nodes_len):# 避免重復計算d_key = (nodes[i].id, nodes[j].id)if d_key not in distance:distance[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)d = distance[d_key]if d < min_dist:min_dist = dclosest_part = (i, j)part1, part2 = closest_partnode1, node2 = nodes[part1], nodes[part2]# 將兩個節點進行合并,即兩個節點所包含的所有數據的平均值new_vec = [(node1.vec[i] * node1.count + node2.vec[i] * node2.count) / (node1.count + node2.count)for i in range(feature_num)]new_node = ClusterNode(vec=new_vec, left=node1, right=node2, distance=min_dist, id=currentclustid,count=node1.count + node2.count)currentclustid -= 1# 刪掉這最近的兩個節點del nodes[part2], nodes[part1]# 把新的節點添加進去nodes.append(new_node)# 樹建立完成，這里要注意，在示例中是最終凝聚為1個節點，而這里到達所要指定的類別數目即停止，一個node屬于一個類別self.nodes = nodes# 給每個node以及node包含的數據打上標簽self.calc_label()def calc_label(self):# 調取聚類結果for i, node in enumerate(self.nodes):self.leaf_traversal(node, i)def leaf_traversal(self, node: ClusterNode, label):# 遞歸遍歷葉子結點if node.left is None and node.right is None:self.labels[node.id] = labelif node.left:self.leaf_traversal(node.left, label)if node.right:self.leaf_traversal(node.right, label)

通過讀取sklearn自帶的鳶尾花的數據庫，測試一下：

from sklearn.datasets import load_iris import matplotlib.pyplot as plt iris = load_iris()my = Hierarchical(4) my.fit(iris.data) data = iris.data data_0 = data[np.nonzero(np.array(my.labels) == 0)] data_1 = data[np.nonzero(np.array(my.labels) == 1)] data_2 = data[np.nonzero(np.array(my.labels) == 2)] data_3 = data[np.nonzero(np.array(my.labels) == 3)] plt.scatter(data_0[:, 0], data_0[:, 1]) plt.scatter(data_1[:, 0], data_1[:, 1]) plt.scatter(data_2[:, 0], data_2[:, 1]) plt.scatter(data_3[:, 0], data_3[:, 1])print(np.array(my.labels))from sklearn.cluster import KMeans km = KMeans(4) km.fit(iris.data) print(km.labels_)data_0_ = data[np.nonzero(np.array(km.labels_) == 0)] data_1_ = data[np.nonzero(np.array(km.labels_) == 1)] data_2_ = data[np.nonzero(np.array(km.labels_) == 2)] data_3_ = data[np.nonzero(np.array(km.labels_) == 3)] plt.figure() plt.scatter(data_0_[:, 0], data_0_[:, 1]) plt.scatter(data_1_[:, 0], data_1_[:, 1]) plt.scatter(data_2_[:, 0], data_2_[:, 1]) plt.scatter(data_3_[:, 0], data_3_[:, 1])

可以看到，兩種結果差不多，但是也有些不同。

其實sklearn中也有層次聚類算法，上面是為了更好理解層次聚類的算法過程，下面利用sklearn庫實現層次聚類算法：

from sklearn.cluster import AgglomerativeClustering from sklearn.preprocessing import MinMaxScaler model = AgglomerativeClustering(n_clusters=4, affinity='euclidean', memory=None, connectivity=None,compute_full_tree='auto', linkage='ward', pooling_func='deprecated') """ 參數：n_cluster: 聚類數目affinity: 計算距離的方法，'euclidean'為歐氏距離, 'manhattan'曼哈頓距離, 'cosine'余弦距離, 'precompute'預先計算的affinity matrix;memory: None, 給定一個地址，層次聚類的樹緩存在相應的地址中；linkage: 層次聚類判斷相似度的方法，有三種：'ward': 即single-linkage'average': 即average-linkage'complete': 即complete-linkage """ """ 屬性：labels_： 每個數據的分類標簽n_leaves_：分層樹的葉節點數量n_components：連接圖中連通分量的估計值children：一個數組，給出了每個非節點數量 """data_array = np.array(load_iris().data[:50, :]) min_max_scalar = MinMaxScaler() data_scalar = min_max_scalar.fit_transform(data_array) model.fit(min_max_scalar)from scipy.cluster.hierarchy import linkage, dendrogram plt.figure(figsize=(20, 6)) Z = linkage(data_scalar, method='ward', metric='euclidean') p = dendrogram(Z, 0) plt.show()

有關參數已在上面進行注釋，關于類別間的距離計算，有三種：single-linkage、complete-linkage和average-linkage，一個是以最近距離作為類別間的距離，一個是以最遠距離作為類間距離，還有是以各個樣本距離總的平均值為類間距離。

代碼后半部分是生成一個開篇說的那種圖的可視化方式，限于顯示需要，只取前50個數據，生成的樹的結果如圖所示（這里并沒有分類，而是一種可視化的形式）：

層次聚類的優缺點：

優點：

1、距離的定義比較容易，而且比較自由；

2、有時可以不用指定所需類別個數，就像前面說的，我們可以通過閾值來進行類的劃分；

3、可以生成非球形的簇，發現層次間的關系。

缺點：

1、在建樹過程中要計算每個樣本間的距離，計算復雜度較高；

2、算法對于異常值比較敏感，影響聚類效果；

3、容易形成鏈狀的簇。

2.DBSCAN

前面說了層次聚類算法，其實原理比較簡單，但對于噪聲（異常值）比較敏感，且基于距離的算法只能發現“類圓形”的簇。

另一種聚類算法?DBSCAN算法是一種基于密度的聚類算法，它能夠克服前面說到的基于距離聚類的缺點，且對噪聲不敏感，它可以發現任意形狀的簇?。

DBSCAN的主旨思想是?只要一個區域中的點的密度大于一定的閾值，就把它加到與之相近的類別當中去?。

那么究竟是如何做呢，我們首先需要了解與DBSCAN有關的幾個概念：

先看下面一張圖，結合圖來理解下面幾個概念：

（1）?ε-鄰域：?一個對象在半徑為ε內的區域，簡單來說就是在給定一個數據為圓心畫一個半徑為ε的圈；

（2）?核心對象：?對于給定的一個數值m，在某個對象的鄰域內，至少包含m個點，則稱之為核心，簡單來說就是某個對象的圈內的數據大于m個，則這個對象就是核心；

（3）?直接密度可達：?結合上圖，給定一個對象q，如果這個對象的鄰域內有大于m個點，而另一個對象p又在這個鄰域內，則稱之為p是q的直接密度可達；

（4）?間接密度可達：?如下一張圖，p1是q的直接密度可達，而p是p1的直接密度可達，那么p則是q的密度可達；

（5）?密度相連?：?假設一個對象O，是對象p的密度可達，而q是O的密度可達，那么p和q則是密度相連的。

（6）?簇?：基于密度聚類的簇就是最大的密度相連的所有對象的集合；

（7）?噪聲?：不屬于任何簇中的對象稱之為噪聲；

其實上面的概念看似復雜，這里也進行了簡化，原先的定義更加比較難理解，但?結合當前疫情感染情況?，我們可以試著對上面概念進行一個類比和解釋：

假設某個區域突然發現1例感染者，那么防疫人員就要對這個人軌跡進行溯源，就假設這個人的活動區域就是一個圓，那么這個圓就稱為這個確診者的?鄰域?；

然后來過該區域內的所有人員進行核酸篩查，假設發現有3個以上的確診者，就算中高風險地區了，通過篩查發現第一個人的鄰域內有5個確診者，那么第1個病例這里稱之為A，就是?核心?；

由于這5個人都到過這個區域，那么這5個人的任意一個人都是A的?直接密度可達?。

這里注意，?直接密度可達是一個不對稱的?，可以說這5個其中一個是A的直接密度可達，但不能說第1個病例是這5個的直接密度可達，因為這5個人的活動范圍只是與A有交集，但在其各自的活動范圍內，并不一定都有超過3個確診病例；

在又篩查出來5個以后，防疫人員又要進一步擴大核酸范圍，那么需要分別對這另外5個人的活動范圍進行排查；

經排查發現其中一個確診者，這里稱之為B，B的活動范圍內有3個陽性，那么這里B就也是一個?核心?，其中一個稱之為C，不在A的鄰域內，那么?C是B的直接密度可達?，?C是A的間接密度可達?；

這里注意，間接密度可達同樣也是不對稱的，同樣的道理，可以說C是A的間接密度可達，不能說A是C的間接密度可達；

接下來，防疫人員又要對C的鄰域進行排查，發現C的活動范圍內也有3個確診者，那么C也是一個?核心，?而這3個確診者當中，有一個沒有來過B的活動范圍?，稱之為D；

那么，D是C的直接密度可達，D是B的間接密度可達，D是A的密度相連。密度相連是一個對稱的概念，因為二者都與C有關；

然后，上面的這些人的活動區域連接起來，則就構成了整個中高風險地區，也就是一個?簇；

假設在另一個區域又突然發現一名確診者，經排查后，如果這個確診者也作為核心向周圍擴散發現很多確診者，那么這就形成了一個?新的簇?；

如果其所在區除了他自己，沒有別的確診病例了，因此，這個就是屬于?噪聲點。

通過上面的舉例，應該可以很好理解有關密度聚類的幾個概念了，而且能夠為后面算法的理解更容易。

那么根據上面簇的概念和所舉的例子，有關DBSCAN的算法過程就比較簡單理解了：

下面再舉一個實際的例子，來看一下DNSCAN的算法處理過程，例子來源于水印。

假設有一組數據，設定MinPts=3，ε=3，數據如圖所示：

第一步：

首先掃描點p1(1,2)，以p1為中心：

（1）p1的鄰域內有點{p1,p2,p3,p13}，因此p1是核心點；

（2）以p1為核心點，建立簇C1；找出所有與p1的密度可達的點；

（3）p2的鄰域內為{p1,p2,p3,p4,p13}，因此p4屬于p1的密度可達，p4屬于簇C1；

（4）p3的鄰域內為{p1,p2,p3,p4,p13}，這些點都已屬于簇C1，繼續；

（5）p4的鄰域內為{?p3,p4,p13?}，這些點也都屬于簇C1，繼續；

（6）p13的鄰域內為{p2,p3,p4,p13}，也都處理過了

至此，以p1為核心的密度可達的數據點搜索完畢，得到簇C1，包含{?p1,p2,p3,p13,p4?}

第二步：

繼續掃描點，到p5，以p5為中心：

（1）計算p5鄰域內的點{?p5,p6,p7,p8?}，因此p5也是核心點；

（2）以p5為核心點 ，建立簇C2，找出所有與p5的密度可達的點；

（3）同第一步中一樣，依次掃描p6、p7、p8;

得到以p5為核心點的簇C2，包含的點為{?p5,p6,p7,p8?}。

第三步：

繼續掃描點，到點p9，以p9為中心：

（1）p9的鄰域內的點為{p9}，所以p9b不是核心點，進行下一步

第四步：

繼續掃描點，到點p10，以p10為中心：

（1）p10的領域內的點為{?p10,p11?}，所以p10不是核心點，進行下一步。

第五步：

繼續掃描到點p11，以p11為中心：

（1）計算p11鄰域內的點為{?p11,p10,p12?}，所以p11是核心點；

（2）以p11為核心點建立簇C3，找出所有的密度可達點；

（3）p10已被處理處理過，繼續掃描；

（4）掃描p12，p12鄰域內{?p12,p11?}；

至此，p11的密度可達點都搜索完畢，形成簇C3，包含的點為{?p11,p10,p12?}

第六步：

繼續掃描點，p12，p13都已被處理過，至此所有點都被處理過，算法結束。

下面對DBSCAN進行算法的實現，首先是算法的步驟實現，然后再用sklearn進行實現：

import numpy as np import random import matplotlib.pyplot as plt import copy from sklearn import datasets# 搜索鄰域內的點 def find_neighbor(j, x, eps):""":param j: 核心點的索引:param x: 數據集:param eps:鄰域半徑:return:"""temp = np.sum((x - x[j]) ** 2, axis=1) ** 0.5N = np.argwhere(temp <= eps).flatten().tolist()return Ndef DBSCAN(X, eps, MinPts):k = -1# 保存每個數據的鄰域neighbor_list = []# 核心對象的集合omega_list = []# 初始化，所有的點記為未處理gama = set([x for x in range(len(X))])cluster = [-1 for _ in range(len(X))]for i in range(len(X)):neighbor_list.append(find_neighbor(i, X, eps))if len(neighbor_list[-1]) >= MinPts:omega_list.append(i)omega_list = set(omega_list)while len(omega_list) > 0:gama_old = copy.deepcopy(gama)# 隨機選取一個核心點j = random.choice(list(omega_list))# 以該核心點建立簇Ckk = k + 1Q = list()# 選取的核心點放入Q中處理，Q中只有一個對象Q.append(j)# 選取核心點后，將核心點從核心點列表中刪除gama.remove(j)# 處理核心點，找出核心點所有密度可達點while len(Q) > 0:q = Q[0]# 將核心點移出，并開始處理該核心點Q.remove(q)# 第一次判定為True，后面如果這個核心點密度可達的點還有核心點的話if len(neighbor_list[q]) >= MinPts:# 核心點鄰域內的未被處理的點delta = set(neighbor_list[q]) & gamadelta_list = list(delta)# 開始處理未被處理的點for i in range(len(delta)):# 放入待處理列表中Q.append(delta_list[i])# 將已處理的點移出標記列表gama = gama - delta# 本輪中被移除的點就是屬于Ck的點Ck = gama_old - gamaCklist = list(Ck)# 依次按照索引放入cluster結果中for i in range(len(Ck)):cluster[Cklist[i]] = komega_list = omega_list - Ckreturn clusterX1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.02) X2, y2 = datasets.make_blobs(n_samples=400, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]], random_state=9) X = np.concatenate((X1, X2)) eps = 0.08 min_Pts = 10 C = DBSCAN(X, eps, min_Pts) plt.figure() plt.scatter(X[:, 0], X[:, 1], c=C) plt.show()

運行結果如圖所示：

然后就是利用sklearn中的DBSCAN類進行實現：

from sklearn.cluster import DBSCANmodel = DBSCAN(eps=0.08, min_samples=10, metric='euclidean', algorithm='auto') """ eps: 鄰域半徑 min_samples：對應MinPts metrics: 鄰域內距離計算方法，之前在層次聚類中已經說過，可選有： 歐式距離：“euclidean”曼哈頓距離：“manhattan”切比雪夫距離：“chebyshev” 閔可夫斯基距離：“minkowski”帶權重的閔可夫斯基距離：“wminkowski”標準化歐式距離： “seuclidean”馬氏距離：“mahalanobis” algorithm：最近鄰搜索算法參數，算法一共有三種，第一種是蠻力實現‘brute’，第二種是KD樹實現‘kd_tree’，第三種是球樹實現‘ball_tree’， ‘auto’則會在上面三種算法中做權衡 leaf_size：最近鄰搜索算法參數，為使用KD樹或者球樹時， 停止建子樹的葉子節點數量的閾值 p: 最近鄰距離度量參數。只用于閔可夫斯基距離和帶權重閔可夫斯基距離中p值的選擇，p=1為曼哈頓距離， p=2為歐式距離。""" model.fit(X) plt.figure() plt.scatter(X[:, 0], X[:, 1], c=model.labels_) plt.show()

上面一些參數是需要調的，如eps和MinPts，基于?密度聚類對這兩個參數敏感。

關于DBSCAN的優缺點：

優點

1、不必指定聚類的類別數量；

2、可以形成任意形狀的簇，而K-means只適用于凸數據集；

3、對于異常值不敏感；

缺點：

1、計算量較大，對于樣本數量和維度巨大的樣本，計算速度慢，收斂時間長，這時可以采用KD樹進行改進；

2、對于eps和MinPts敏感，調參復雜，需要聯合調參；

3、?樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用 DBSCAN 算法一般不適合；

4、樣本同采用一組參數聚類，有時不同的簇的密度不一樣，有人提出OPTICS聚類算法（有空會把這一算法補上）；

5、由于對噪聲不敏感，在一些領域，如異常檢測不適用。

總結

以上是生活随笔為你收集整理的【Python机器学习实战】聚类算法——层次聚类(HAC)和DBSCAN的全部內容，希望文章能夠幫你解決所遇到的問題。

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