-
2021-10-27 16:19:09
层次聚类
1. 基本介绍
层次聚类有聚合(自下而上)和分裂(自上而下)两种方式。
聚合聚类开始将每个样本各自分到 个类:之后将相距最近的两类合井,建立一个新的类,重复此操作直到满足停止条件
分裂聚类开始将所有样本分到一个类之后将己有类中相距最远的样本分到两个新的类,重复此操作直到满足停止条件
2. 聚合聚类
对于给定的样本集合,开始将每个样本分到一个类,然后按照一定规则,例如类间距离最小,将最满足规则条件的两个类进行合并 如此反复进行,每次减少一个类,直到满足停止条件
聚合聚类需要预先确定下面三个要素:
- 距离或相似度:欧氏距离、曼哈顿距离、夹角余弦等
- 合并规则:最短距离,最长距离,中心距离,平均距离等
- 停止条件:类的个数达到阈值、类的直径超过阈值等
3. 聚合聚类算法流程
如果采用欧氏距离作为样本间的距离,类间距离最小作为合并规则,类的个数为1作为停止条件,那么聚合聚类算法流程如下:
输 入 : n 个 样 本 组 成 的 样 本 集 合 及 样 本 之 间 的 距 离 输入: n 个样本组成的样本集合及样本之间的距离 输入:n个样本组成的样本集合及样本之间的距离
输 出 : 对 样 本 集 合 的 个 层 次 化 聚 类 输出:对样本集合的 个层次化聚类 输出:对样本集合的个层次化聚类
- 计算 n n n个样本两两之间的欧氏距离 d i j d_{ij} dij
- 构造 n n n个类,每个类只包含一个样本
- 合井类间距离最小的两个类,其中最短距离为类间距离,构建一个新类。
- 计算新类与当前各类的距离。若类的个数为1,终止计算,否则回到步骤3
4.
Scipy
中的层次聚类from scipy.cluster.hierarchy import dendrogram, linkage from matplotlib import pyplot as plt X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]] Z = linkage(X, 'average') fig = plt.figure(figsize=(5, 3)) dn = dendrogram(Z) plt.show()
scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)
y
:是距离矩阵,可以是1维压缩向量(距离向量),也可以是2维观测向量(坐标矩阵)。若y
是1维压缩向量,则y
必须是n个初始观测值的组合,n是坐标矩阵中成对的观测值。method
:是指计算类间距离的方法single
:
d ( u , v ) = m i n ( d i s t ( u [ i ] , v [ j ] ) ) d(u,v)=min(dist(u[i],v[j])) d(u,v)=min(dist(u[i],v[j]))complete
:
d ( u , v ) = m a x ( d i s t ( u [ i ] , v [ j ] ) ) d(u,v)=max(dist(u[i],v[j])) d(u,v)=max(dist(u[i],v[j]))average
:
d ( u , v ) = ∑ i j d i s t ( u [ i ] , u [ j ] ) ( ∣ u ∣ ⋅ ∣ v ∣ ) d(u,v)=\sum_{ij}\frac {dist(u[i],u[j])} {(|u| \cdot |v|)} d(u,v)=ij∑(∣u∣⋅∣v∣)dist(u[i],u[j])ward
:
d ( u , v ) = ∣ v ∣ + ∣ s ∣ N d i s t ( v , s ) 2 + ∣ v ∣ + ∣ t ∣ N d i s t ( v , t ) 2 − ∣ v ∣ N d i s t ( s , t ) 2 d(u,v)=\sqrt {\frac {|v|+|s|}{N}dist(v,s)^2+\frac {|v|+|t|}{N}dist(v,t)^2-\frac {|v|} {N}dist(s,t)^2} d(u,v)=N∣v∣+∣s∣dist(v,s)2+N∣v∣+∣t∣dist(v,t)2−N∣v∣dist(s,t)2
其中, u u u是 s 和 t s和t s和t组成的新类, v v v初始时的类。 N = ∣ v ∣ + ∣ s ∣ + ∣ t ∣ N=|v|+|s|+|t| N=∣v∣+∣s∣+∣t∣
返回值: ( n − 1 , 4 ) (n-1,4) (n−1,4)的矩阵 Z Z Z
5.
Sklearn
中的层次聚类from sklearn.cluster import AgglomerativeClustering from scipy.cluster.hierarchy import dendrogram from matplotlib import pyplot as plt import numpy as np X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]] def plot_dendrogram(model, **kwargs): counts = np.zeros(model.children_.shape[0]) n_samples = len(model.labels_) for i, merge in enumerate(model.children_): current_count = 0 for child_idx in merge: if child_idx < n_samples: current_count += 1 else: current_count += counts[child_idx - n_samples] counts[i] = current_count linkage_matrix = np.column_stack( [model.children_, model.distances_, counts] ).astype(float) dendrogram(linkage_matrix, **kwargs) model = AgglomerativeClustering(n_clusters=None, distance_threshold=0, linkage='average') model.fit(X) plot_dendrogram(model) plt.show()
sklearn.cluster.AgglomerativeClustering
n_clusters
:聚类数目linkage
: 计算类间距离的方法
返回值的属性
-
labels_
: 每一点的聚类标签 -
children_
:每个非叶节点的子节点。小于n_samples
的值对应于原始样本树的叶子。大于或等于n_samples
的节点i
是一个非叶节点,具有子节点children_[i - n_samples]
。或者,在第i
次迭代时,将children[i][0]
和children[i][1]
合并成节点n_samples + i
。
-
数据
X
一共有8个样本,那么在进行层次聚类是,这8个样本各自一类,类别名称是0、1、2、3、4、5、6、7 -
第一行:[5, 6]意思是类别5和类别6距离最近,首先聚成一类,并自动定义类别为8(=8-1+1)
-
第二行:[2, 7]意思是类别2和类别7距离最近,聚成一类,类别为9(=8-1+2)
-
依次类推
6. 实例演示
import numpy as np import matplotlib.pyplot as plt from sklearn import cluster, datasets from sklearn.preprocessing import StandardScaler np.random.seed(0) # 构建数据 n_samples = 1500 noisy_circles = datasets.make_circles(n_samples=n_samples, factor=0.5, noise=0.05) noisy_moons = datasets.make_moons(n_samples=n_samples, noise=0.05) blobs = datasets.make_blobs(n_samples=n_samples, random_state=8) data_sets = [ ( noisy_circles, { "n_clusters": 2 } ), ( noisy_moons, { "n_clusters": 2 } ), ( blobs, { "n_clusters": 3 } ) ] colors = ["#377eb8", "#ff7f00", "#4daf4a"] linkage_list = ['single', 'average', 'complete', 'ward'] plt.figure(figsize=(20, 15)) for i_dataset, (dataset, algo_params) in enumerate(data_sets): # 模型参数 params = algo_params # 数据 X, y = dataset X = StandardScaler().fit_transform(X) for i_linkage, linkage_strategy in enumerate(linkage_list): # 创建AgglomerativeCluster ac = cluster.AgglomerativeClustering(n_clusters=params['n_clusters'], linkage=linkage_strategy) # 训练 ac.fit(X) # 预测 y_pred = ac.labels_.astype(int) y_pred_colors = [] for i in y_pred: y_pred_colors.append(colors[i]) plt.subplot(3, 4, 4*i_dataset+i_linkage+1) plt.title(linkage_strategy) plt.scatter(X[:, 0], X[:, 1], color=y_pred_colors) plt.show()
7. 层次聚类小结
优点:
- 距离和规则的相似度容易定义,限制少
- 不需要预先制定聚类数
- 可以发现类的层次关系
- 可以聚类成其它形状
缺点:
-
计算复杂度太高,的复杂度是 O ( n 3 m ) O(n^3m) O(n3m)其中 m m m是样本的维数, n n n是样本个数。
-
奇异值也能产生很大影响
-
算法很可能聚类成链状
更多相关内容 -
层次聚类算法的实现
2022-04-12 16:00:32层次聚类算法介绍2.1 层次聚类算法原理2.2 层次聚类算法步骤2.3 层次聚类算法分类3.层次聚类算法实现(代码如下)3.1 相关包导入3.2 生成测试数据集3.3 层次聚类实现&画出树状图3.4 获取聚类结果3.5 对比不同方法...目录
1.作者介绍
杨金花,女,西安工程大学电子信息学院,21级硕士研究生
研究方向:基于学习方法的运动目标检测
电子邮件:2902551510@qq.com孟莉苹,女,西安工程大学电子信息学院,2021级硕士研究生,张宏伟人工智能课题组
研究方向:机器视觉与人工智能
电子邮件:2425613875@qq.com2.层次聚类算法介绍
2.1 层次聚类算法原理
聚类就是对大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小。 层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。算法流程展示如图所示。
2.2 层次聚类算法步骤
假设有6个样本点{A,B,C,D,E,F},对于层次聚类来说,步骤如下:
(1)假设每个样本点都为一个簇类,计算每个簇类间的相似度,得到相似矩阵;
(2)寻找各个类之间最近的两个类,即若B和C的相似度最高,合并簇类B和C为一个簇类。现在我们还有五个簇类,分别为A,BC,D,E,F;
(3)更新簇类间的相似矩阵,若簇类BC和D的相似度最高,合并簇类BC和D为一个簇类。现在我们还有四个簇类,分别为A,BCD,E,F;
(4)更新簇类间的相似矩阵,若簇类E和F的相似度最高,合并簇类E和F为一个簇类。现在我们还有3个簇类,分别为A,BCD,EF。
(5)重复第四步,簇类BCD和簇类EF的相似度最高,合并该两个簇类,现在我们还有2个簇类,分别为A,BCDEF。
(6)最后合并簇类A和BCDEF为一个簇类,层次聚类算法结束。
层次聚类实现过程如图2所示。2.3 层次聚类算法分类
自顶向下的层次聚类算法(Divisive):
Divisive 层次聚类:又称自顶向下(top-down)的层次聚类,最开始所有的对象均属于一个cluster,每次按一定的准则将某个cluster 划分为多个cluster,如此往复,直至每个对象均属于某一个cluster。实现过程示意图如下。自底向上的层次聚类算法(Agglomerative):
Agglomerative 层次聚类:又称自底向上(bottom-up)的层次聚类,每一个对象最开始都是一个cluster,每次按一定的准则将最相近的两个cluster合并生成一个新的cluster,如此往复,直至最终所有的对象都属于一个cluster。3.层次聚类算法实现(代码如下)
3.1 相关包导入
from scipy.cluster.hierarchy import linkage #导入linage函数用于层次聚类 from scipy.cluster.hierarchy import dendrogram #dendrogram函数用于将聚类结果绘制成树状图 from scipy.cluster.hierarchy import fcluster #fcluster函数用于提取出聚类的结果 from sklearn.datasets import make_blobs #make_blobs用于生成聚类算法的测试数据 from sklearn.cluster import AgglomerativeClustering #自底向上层次聚类算法 import matplotlib.pyplot as plt #导入matplotlib绘图工具包
3.2 生成测试数据集
#生成测试数据 centers = [[1, 1], [-1, -1], [1, -1]] X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0) plt.figure(figsize=(10, 8)) plt.scatter(X[:, 0], X[:, 1], c='b') plt.show() #from scipy.cluster.hierarchy import linkage
3.3 层次聚类实现&画出树状图
#层次聚类实现 #from scipy.cluster.hierarchy import dendrogram Z = linkage(X, method='ward', metric='euclidean') print(Z.shape) print(Z[: 5]) #画出树状图 #from scipy.cluster.hierarchy import fcluster plt.figure(figsize=(10, 8)) dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15, show_contracted=True) plt.show()
3.4 获取聚类结果
#根据临界距离返回聚类结果 d = 15 labels_1 = fcluster(Z, t=d, criterion='distance') print(labels_1[: 100]) # 打印聚类结果 print(len(set(labels_1))) # 看看在该临界距离下有几个 cluster #根据聚类数目返回聚类结果 k = 3 labels_2 = fcluster(Z, t=k, criterion='maxclust') print(labels_2[: 100]) list(labels_1) == list(labels_2) # 看看两种不同维度下得到的聚类结果是否一致 #聚类的结果可视化,相同的类的样本点用同一种颜色表示 plt.figure(figsize=(10, 8)) plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism') plt.show()
3.5完整代码
from scipy.cluster.hierarchy import linkage #导入linage函数用于层次聚类 from scipy.cluster.hierarchy import dendrogram #dendrogram函数用于将聚类结果绘制成树状图 from scipy.cluster.hierarchy import fcluster #fcluster函数用于提取出聚类的结果 from sklearn.datasets import make_blobs #make_blobs用于生成聚类算法的测试数据 from sklearn.cluster import AgglomerativeClustering #自底向上层次聚类算法 import matplotlib.pyplot as plt #导入matplotlib绘图工具包 #生成测试数据 centers = [[1, 1], [-1, -1], [1, -1]] X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0) plt.figure(figsize=(10, 8)) plt.scatter(X[:, 0], X[:, 1], c='b') plt.show() #from scipy.cluster.hierarchy import linkage #层次聚类实现 #from scipy.cluster.hierarchy import dendrogram Z = linkage(X, method='ward', metric='euclidean') print(Z.shape) print(Z[: 5]) #画出树状图 #from scipy.cluster.hierarchy import fcluster plt.figure(figsize=(10, 8)) dendrogram(Z, truncate_mode='lastp', p=20, show_leaf_counts=False, leaf_rotation=90, leaf_font_size=15, show_contracted=True) plt.show() # 根据临界距离返回聚类结果 d = 15 labels_1 = fcluster(Z, t=d, criterion='distance') print(labels_1[: 100]) # 打印聚类结果 print(len(set(labels_1))) # 看看在该临界距离下有几个 cluster # 根据聚类数目返回聚类结果 k = 3 labels_2 = fcluster(Z, t=k, criterion='maxclust') print(labels_2[: 100]) list(labels_1) == list(labels_2) # 看看两种不同维度下得到的聚类结果是否一致 # 聚类的结果可视化,相同的类的样本点用同一种颜色表示 plt.figure(figsize=(10, 8)) plt.scatter(X[:, 0], X[:, 1], c=labels_2, cmap='prism') plt.show()
3.6 对比不同方法聚类效果
from time import time import numpy as np from sklearn.datasets import make_blobs from scipy.cluster.hierarchy import linkage, fcluster from sklearn.metrics.cluster import adjusted_mutual_info_score import matplotlib.pyplot as plt #生成样本点 centers = [[1, 1], [-1, -1], [1, -1]] X, labels = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0) #可视化聚类结果 def plot_clustering(X, labels, title=None): plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='prism') if title is not None: plt.title(title, size=17) plt.axis('off') plt.tight_layout() #进行 Agglomerative 层次聚类 linkage_method_list = ['single', 'complete', 'average', 'ward'] plt.figure(figsize=(10, 8)) ncols, nrows = 2, int(np.ceil(len(linkage_method_list) / 2)) plt.subplots(nrows=nrows, ncols=ncols) for i, linkage_method in enumerate(linkage_method_list): print('method %s:' % linkage_method) start_time = time() Z = linkage(X, method=linkage_method) labels_pred = fcluster(Z, t=3, criterion='maxclust') print('Adjust mutual information: %.3f' % adjusted_mutual_info_score(labels, labels_pred)) print('time used: %.3f seconds' % (time() - start_time)) plt.subplot(nrows, ncols, i + 1) plot_clustering(X, labels_pred, '%s linkage' % linkage_method) plt.show()
AMI评估结果:
该量越接近于 1 则说明聚类算法产生的类越接近于真实情况。从右图的AMI量的表现来看,Single-link 方法下的层次聚类结果最差,它几乎将所有的点都聚为一个 cluster,而其他两个 cluster 则都仅包含个别稍微有点偏离中心的样本点,而另外三种聚类方法效果都还可以。结果如下图4.参考链接
-
层次聚类算法介绍
2020-07-15 00:23:38层次聚类算法介绍1层次聚类的定义思考示例问题:2距离与相似性2.1常用的计算距离的方法2.2计算指标相似性的方法1)余弦计算公式:2)相关计算公式:3合并...层次聚类算法介绍
1.本博客是观看清风数学建数学建模课程后有所感想记录的笔记,有想要深入学习的朋友可以购买观看课程:https://weidian.com/?userid=1372657210
2.感兴趣的推荐看B站数学建模试看课程:
https://www.bilibili.com/video/av202387041层次聚类的定义
聚类就是对大量未知标注的数据集,按照数据内部存在的数据特征将数据集划分为多个不同的类别,使类别内的数据比较相似,类别之间的数据相似度比较小,属于无监督学习。
层次聚类的合并算法通过计算两类数据点间的距离,对最为接近的两类数据点进行组合,并反复迭代这一过程,直到将所有数据点合成一类,并生成聚类谱系图。
思考示例问题:
2距离与相似性
2.1常用的计算距离的方法
Ps:其中绝对值距离一般应用于网状道路距离,一般采用欧氏距离。2.2计算指标相似性的方法
1)余弦计算公式:
2)相关计算公式:
3合并算法思想
思想:将两个簇合成为一个簇,计算这个簇与其他簇之间的距离,再进行合并。
簇与簇之间的常用距离:重心法,最短距离法,最长距离法,组间平均连接法,组内平均链接法(下图顺序一致)1)重心法
2)最短距离法
3)最长距离法
4)组间平均连接法
5)组内平均链接法
4算法流程
程序执行过程:
系统(层次)聚类的算法流程: 1.将每个对象看作一类,计算两两之间的最小距离; 2.将距离最小的两个类合并成一个新类; 3.新计算新类与所有类之间的距离; 4.重复2、3两步,直到所有类最后合并成一类; 5.结束。
5 示例与分析
根据所给的图,以及距离矩阵,求解聚类结果:
5.1基于最小值的层次聚类
计算结果如下:
优缺点
优点:可以处理非椭圆形状
缺点:对噪声点和异常值敏感5.2 基于最大值的层次聚类
计算结果如下:
优缺点
优点:不容易受噪声点和异常值影响
缺点:1.往往打破大聚类 2.偏向球状星团
5.3基于组平均
计算结果如下:
优缺点 (MIN和MAX之间的折中)
优点:不易受噪声和异常值影响
缺点:偏向球状星团6需注意的问题
1.对于一个实际问题要根据分类的目的来选取指标,指标选取的不同分类结果一般也不同。 2.样品间距离定义方式的不同,聚类结果一般也不同。 3.聚类方法的不同,聚类结果一般也不同 (尤其是样品特别多的时候)。最好能通过各种方法找出其中的共性。 4.要注意指标的量纲,量纲差别太大会导致聚类结果不合理。 5.聚类分析的结果可能不令人满意,因为我们所做的是一个数学的处理,对于结果我们要找到一个合理的解释。
对比Kmean算法
k均值需要定义聚类簇数k,而层次聚类不需要,层次聚类可以根据聚类谱系图选择聚类的簇个数。
-
层次聚类算法原理总结
2022-01-16 01:19:58点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构...点击上方“小白学视觉”,选择加"星标"或“置顶”
重磅干货,第一时间送达
层次聚类(hierarchical clustering)基于簇间的相似度在不同层次上分析数据,从而形成树形的聚类结构,层次聚类一般有两种划分策略:自底向上的聚合(agglomerative)策略和自顶向下的分拆(divisive)策略,本文对层次聚类算法原理进行了详细总结。
目录
1. 层次聚类算法原理
2. 簇间相似度的计算方法
3. 层次聚类算法的复杂度计算
4. 层次聚类算法的优化方法
5. 层次聚类算法的优缺点
1.层次据类算法原理
层次聚类根据划分策略包括聚合层次聚类和拆分层次聚类,由于前者较后者有更广泛的应用且算法思想一致,因此本节重点介绍聚合层次聚类算法。
聚合层次聚类算法假设每个样本点都是单独的簇类,然后在算法运行的每一次迭代中找出相似度较高的簇类进行合并,该过程不断重复,直到达到预设的簇类个数K或只有一个簇类。
聚合层次聚类的基本思想:
1)计算数据集的相似矩阵;
2)假设每个样本点为一个簇类;
3)循环:合并相似度最高的两个簇类,然后更新相似矩阵;
4)当簇类个数为1时,循环终止;
为了更好的理解,我们对算法进行图示说明,假设我们有6个样本点{A,B,C,D,E,F}。
第一步:我们假设每个样本点都为一个簇类(如下图),计算每个簇类间的相似度,得到相似矩阵;
第二步:若B和C的相似度最高,合并簇类B和C为一个簇类。现在我们还有五个簇类,分别为A,BC,D,E,F。
第三步:更新簇类间的相似矩阵,相似矩阵的大小为5行5列;若簇类BC和D的相似度最高,合并簇类BC和D为一个簇类。现在我们还有四个簇类,分别为A,BCD,E,F。
第四步:更新簇类间的相似矩阵,相似矩阵的大小为4行4列;若簇类E和F的相似度最高,合并簇类E和F为一个簇类。现在我们还有3个簇类,分别为A,BCD,EF。
第五步:重复第四步,簇类BCD和簇类EF的相似度最高,合并该两个簇类;现在我们还有2个簇类,分别为A,BCDEF。
第六步:最后合并簇类A和BCDEF为一个簇类,层次聚类算法结束。
树状图是类似树(tree-like)的图表,记录了簇类聚合和拆分的顺序。我们根据上面的步骤,使用树状图对聚合层次聚类算法进行可视化:
也可用下面的图记录簇类聚合和拆分的顺序:
拆分层次聚类算法假设所有数据集归为一类,然后在算法运行的每一次迭代中拆分相似度最低的样本,该过程不断重复,最终每个样本对应一个簇类。简单点说,拆分层次聚类是聚合层次聚类的反向算法,读者可通过树状图去加强理解,一个是自底向上的划分,一个是自顶向下的划分。
2.簇间相似度的计算方法
由上节知道,合并或拆分层次聚类算法都是基于簇间相似度进行的,每个簇类包含了一个或多个样本点,通常用距离评价簇间或样本间的相似度,即距离越小相似度越高,距离越大相似度越低。因此我们首先假设样本间的距离为:dist(Pi,Pj),其中Pi,Pj为任意两个样本,下面介绍常用的簇间相似度计算方法:
最小距离
最大距离
平均距离
中心距离
最小方差法
最小距离:也称为单链接算法(single linkage algorithm),含义为簇类C1和C2的距离由该两个簇的最近样本决定,数学表达式写为:
算法也可用下图表示,其中红色线表示簇类C1和C2的距离。
优点:
只要两个簇类的间隔不是很小,单链接算法可以很好的分离非椭圆形状的样本分布。
如下图的两个聚类例子,其中不同颜色表示不同的簇类:
例1
例2
缺点:
单链接算法不能很好的分离簇类间含有噪声的数据集,如下图:
最大距离:也称为全链接算法(complete linkage algorithm),含义为簇类C1和C2的距离由该两个簇的最远样本决定,与单链接算法的含义相反,数学表达式写为:
算法也可用如下图表示,其中红色线表示簇类C1和C2的距离。
优点:
全链接算法可以很好的分离簇类间含有噪声的数据集,如下图:
缺点:
全链接算法对球形数据集的分离会产生偏差,如下图:
平均距离:也称为均链接算法(average-linkage algorithm),含义为簇类C1和C2的距离等于两个簇类所有样本对的距离平均,数学表达式为:
其中|C1|,|C2|分别表示簇类的样本个数。
均链接算法也可用如下图表示:
所有连线的距离求和平均即为簇类C1和C2的距离。
优点:
均链接算法可以很好的分离簇类间有噪声的数据集。
缺点:
均链接算法对球形数据集的分离会产生偏差。
中心距离:簇类C1和C2的距离等于该两个簇类中心间的距离,如下图:
其中红色点表示簇类的中心,红色线表示簇类C1和C2的距离。这种计算簇间距离的方法非常少用,个人不建议使用这一算法。
离差平方和:簇类C1和C2的距离等于两个簇类所有样本对距离平方和的平均,与均链接算法很相似,数学表达式为:
优点:
离差平方和可以很好的分离簇间有噪声的数据集。
缺点:
离差平方和对球形数据集的分离会产生偏差。
我们已经知道了如何通过样本间的距离来评估簇间的距离,本节只剩下最后一个问题了,如何计算样本间的距离,假设样本是n维,常用的距离计算方法有:
1)欧拉距离(Euclidean distance):
2)平方欧式距离(Squared Euclidean distance):
3)曼哈顿距离(Manhattan distance):
4)切比雪夫距离(Chebyshev distance):
5)马氏距离(Mahalanobis distance):
其中S为协方差矩阵。
对于文本或非数值型的数据,我们常用汉明距离(Hamming distance)和编辑距离(Levenshtein distance)表示样本间的距离。
不同的距离度量会影响簇类的形状,因为样本距离因距离度量的不同而不同,如点(1.1)和(0,0)的曼哈顿距离是2,欧式距离是sqrt(2),切比雪夫距离是1。
3.层次据类算法的复杂度计算
空间复杂度:当样本点数目很大时,层次聚类需要较大的空间存储相似矩阵,相似矩阵的大小是样本个数的平方,因此空间复杂度是n的平方阶次,即空间复杂度=O(n^2)。
时间复杂度:层次聚类算法需要进行n次迭代,每次迭代都需要更新并存储相似矩阵,所以时间复杂度是样本个数n的立方阶次,即时间复杂度=O(n^3)。
4.层次聚类算法的优化方法
上节介绍数据量较大时,层次聚类算法的空间复杂度和时间复杂度较高,我们可以通过连通性约束(connectivity constraint)降低算法复杂度,甚至提高聚类结果。
连通性约束是通过连通性矩阵(connectivity matrix)实现的,连通性矩阵的元素只有1和0两种结果,1表示两个样本是连通的,0表示两个样本不连通,我们只对连通性的样本进行距离计算并融合,这一过程大大降低了计算量,常采用sklearn.neighbors.kneighbors_graph来构建连接矩阵。
我们构建了容量为15000的瑞士卷(swiss roll dataset)数据集:
# 生成瑞士卷数据集,容量为15000 n_samples = 15000 noise = 0.05 X, _ = make_swiss_roll(n_samples, noise) # 减小瑞士卷的厚度 X[:, 1] *= .5
用离差平方和的层次聚类算法建模,可视化聚类结果并输出算法运行时间。
print("Compute unstructured hierarchical clustering...") st = time.time() ward = AgglomerativeClustering(n_clusters=6, linkage='ward').fit(X) elapsed_time = time.time() - st label = ward.labels_ # 运行时间 print("Elapsed time: %.2fs" % elapsed_time) print("Number of points: %i" % label.size) # ############################################################################# # 可视化结果 fig = plt.figure() ax = p3.Axes3D(fig) ax.view_init(7, -80) for l in np.unique(label): ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2], color=plt.cm.jet(np.float(l) / np.max(label + 1)), s=20, edgecolor='k') plt.title('Without connectivity constraints (time %.2fs)' % elapsed_time)
结果:
我们在构建层次聚类算法模型前,先定义数据集的连通矩阵:
# 定义不包含样本点在内的10个最近邻的连通样本点 from sklearn.neighbors import kneighbors_graph connectivity = kneighbors_graph(X, n_neighbors=10, include_self=False)
用离差平方和的层次聚类算法建模,可视化聚类结果并输出算法运行时间:
print("Compute structured hierarchical clustering...") st = time.time() ward = AgglomerativeClustering(n_clusters=6, connectivity=connectivity, linkage='ward').fit(X) elapsed_time = time.time() - st label = ward.labels_ print("Elapsed time: %.2fs" % elapsed_time) print("Number of points: %i" % label.size) # ############################################################################# # Plot result fig = plt.figure() ax = p3.Axes3D(fig) ax.view_init(7, -80) for l in np.unique(label): ax.scatter(X[label == l, 0], X[label == l, 1], X[label == l, 2], color=plt.cm.jet(float(l) / np.max(label + 1)), s=20, edgecolor='k') plt.title('With connectivity constraints (time %.2fs)' % elapsed_time) plt.show()
结果:
由上面例子可知:大数据量的情况下,增加连通性约束矩阵可以降低算法的运行时间,若只关注数据集的局部信息,连通性约束也能提高算法性能。
6.层次聚类算法的优点
优点:
算法简单,易于理解
树状图包含了整个算法过程的信息;
缺点:
选择合适的距离度量与簇类的链接准则较难;
高的时间复杂度和空间复杂度;
参考:
https://towardsdatascience.com
https://scikit-learn.org/stable/
下载1:OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复:扩展模块中文教程,即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
下载2:Python视觉实战项目52讲
在「小白学视觉」公众号后台回复:Python视觉实战项目,即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。
下载3:OpenCV实战项目20讲
在「小白学视觉」公众号后台回复:OpenCV实战项目20讲,即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~
-
层次聚类算法
2018-09-04 15:08:58首先介绍聚类中的层次聚类算法。层次法又分为凝聚的层次聚类和分裂的层次聚类。 凝聚的方法:也称自底向上的方法,首先将每个对象作为单独的一个聚类,然后根据性质和规则相继地合并相近的类,直到所有的对象都... -
matlab层次聚类算法
2016-12-26 21:32:15%生成20个随机样本 %屏幕输出Q型聚类结果 %屏幕输出R型聚类结果 包含具体聚类步骤和算法,自写函数体 -
【聚类算法】层次聚类算法
2019-11-19 21:37:25层次聚类有两种聚类的方式: Agglomerative - 从下至上的聚类 将每一个数据样本作为一个独立的簇。在每一次迭代中将相似的簇合并起来,知道整份数据集结成成一个簇或多个簇 Divsive - 从上... -
基本凝聚层次聚类算法
2017-01-13 15:02:14一、基本凝聚层次聚类算法 1:如果需要,计算近邻度矩阵 2:repeat 2.1:合并最接近的两个簇 2.2:更新近邻性矩阵,以反映新的簇与原来的簇之间的近邻性 3:until 仅剩下一个簇 存储近邻度个数... -
聚类算法——层次聚类算法
2018-02-11 15:51:25每篇一句: You must strive to find your own voice. Because the longer you wait to begin, the less likely you are to find it at all. –你必须努力去寻找自己的声音,... 层次聚类算法 (Hierarchical Clu -
关于层次聚类算法的python实现
2021-03-17 02:50:48from scipy.cluster import hierarchy0.层次聚类的概念层次聚类和k-means一样都是很常用的聚类方法。...层次聚类又分为自底而上的聚合层次聚类和自顶而下的分裂层次聚类。0.1 聚合层次聚类每一个点初始为1类,得到N(... -
层次聚类算法 算法_聚类算法简介
2020-08-06 13:33:09层次聚类算法 算法Take a look at the image below. It’s a collection of bugs and creepy-crawlies of different shapes and sizes. Take a moment to categorize them by similarity into a number of groups. ... -
聚类算法之层次聚类(Python实现)
2021-02-05 13:38:57层次聚类算法介绍假设有 n 个待聚类的样本,对于层次聚类算法,它的步骤是:步骤一:(初始化)将每个样本都视为一个聚类;步骤二:计算各个聚类之间的相似度;步骤三:寻找最近的两个聚类,将他们归为一类;步骤四:... -
层次聚类算法解析
2018-03-04 17:45:05上篇博客我们粗略讲解了一下kmeans聚类算法,其中牵涉到了新的聚类算法:层次聚类算法,本篇博客我们着重讲一下这种聚类算法。 kmeans聚类算法可以看做top-down结构,而层次聚类算法则可以视为bottom-up结构,而且... -
【算法推荐】层次聚类算法BIRCH及其实现
2020-04-17 15:17:39利用层次结构的平衡迭代归约和聚类(Balanced Iterative Reducing and Clustering usingHierarchies, BIRCH)是为大量数值数据聚类设计的,它将层次聚类(在初始微聚类阶段)与诸如迭代地划分这样的其他聚类算法(在其后... -
层次聚类算法及通过python的scipy进行计算
2022-07-21 09:46:15层次聚类算法及通过sklearn调用方式 -
聚类算法之层次聚类和密度聚类(图文并茂)
2021-07-17 23:14:50凝聚的层次聚类——AGNES算法 采用自底向上的策略,首先将每个对象作为一个簇,然后这些簇根据某些准则被一步步合并,两个簇之间的距离由这两个的不同簇中距离最近的数据点的相似度来确定;聚类的过程直到所有对象... -
聚类——基于层次的聚类算法
2021-12-23 17:41:40基于层次的聚类算法(Hierarchical Clustering) 当不知道应该分为几类时,使用层次聚类比较适合。层次聚类会构建一个多层嵌套的分类,类似一个树状结构。可以选择一个聚类数量,根据需求对树状图中画一条水平线,... -
聚类算法及python实现——层次聚类
2022-04-03 17:46:50聚类算法及python实现——层次聚类 构建二叉树 步骤 step1:将每个样品都看作一类 step2:计算每个样品两两之间的距离 step3:合并距离最近的两类变成一个新的类 step4:计算各个类之间的距离,合并,直至只有一类 ... -
聚类算法之层次聚类算法和应用举例
2017-05-09 17:47:19聚类算法之层次聚类算法和应用举例 1.假设有N个待聚类的样本,对于层次聚类来说,步骤: 1、(初始化)把每个样本归为一类,计算每两个类之间的距离,也就是样本与样本之间的相似度; 2、寻找各个类之间最近的两... -
聚类算法(2):系统聚类/层次聚类算法
2019-06-20 15:23:30聚类算法(4)--Hierarchical clustering层次聚类 系统聚类:相当于自下而上法,也就是层次聚类 目录 一、系统聚类 1. 系统聚类实现的一般步骤 2. 常用的距离 3. 类间距离 二、手动实现过程 三、代码实现 1.... -
12.聚类算法之层次聚类
2018-11-08 14:42:50假设有n个待聚类的样本,对于层次聚类算法,它的步骤是: 步骤一:(初始化)将每个样本都视为一个聚类; 步骤二:计算各个聚类之间的相似度; 步骤三:寻找最近的两个聚类,将他们归为一类; 步骤四:重复步... -
机器学习:基于层次的聚类算法
2020-12-02 13:44:18尽管基于划分的聚类算法能够实现把数据集划分成指定数量的簇,但是在某些情况下,需要把数据集划分成不同层上的簇:比如,作为一家公司的人力资源部经理,你可以把所有的雇员组织成较大的簇,如主管、经理和职员;... -
python实现AGNES(凝聚层次聚类)算法
2021-04-30 22:56:31#AGNES(凝聚层次聚类)算法 import numpy as np import pandas as pd import matplotlib.pyplot as plt from sklearn.cluster import AgglomerativeClustering from sklearn import datasets from sklearn.metrics ... -
层次聚类算法总结
2017-02-25 22:59:54上述的几篇博文已经大致将基本的层次聚类算法讲了一下,现在做个简单总结,将这几个算法串联起来。 AGNES和DIANA这两个层次聚类算法尽管比较简单,但是存在缺点,因此需要改进,针对不同的缺点,引入了不同的算法。... -
[层次聚类算法matlab]初识聚类算法:K均值、凝聚层次聚类和DBSCAN
2021-04-26 18:03:55篇一 : 初识聚类算法:K均值、凝聚层次聚类和DBSCAN聚类分析就仅根据在数据中发现的描述对象及其关系的信息,将数据对象分组(簇)。其目标是,组内的对象相互之间是相似的,而不同组中的对象是不同的。组内相似性越大... -
初识聚类算法:K均值、凝聚层次聚类和DBSCAN
2020-12-20 03:00:32先介绍下聚类的不同类型,通常有以下几种:(1)层次的与划分的:如果允许簇具有子簇,则我们得到一个层次聚类。层次聚类是嵌套簇的集族,组织成一棵树。划分聚类简单地将数据对象划分成不重叠的子集(簇),使得每个... -
聚类算法(k_means与层次聚类)
2020-06-11 17:02:45K-means聚类 算法思路如下: 首先输入 k 的值,即我们指定希望通过聚类得到 k 个分组; 从数据集中随机选取 k 个数据点作为初始质心; 对集合中每一个样本点,计算与每一个初始质心的距离,离哪个初始质心距离近...