首页 > 编程语言 >层次聚类算法原理及Python实现

层次聚类算法原理及Python实现

时间:2024-08-19 21:24:38浏览次数:13  
标签:层次 树状 Python 算法 scipy fcluster 聚类 ward

层次聚类算法(Hierarchical Clustering Method)是一种基于簇间相似度在不同层次上分析数据,从而形成树形聚类结构的算法。它主要分为两种形式:凝聚层次聚类(自下而上)和分裂层次聚类(自上而下)。以下将详细介绍凝聚层次聚类的原理与步骤:

一、原理

凝聚层次聚类算法的基本思想是将每个样本点视为一个单独的簇,然后在算法运行的每一次迭代中找出相似度最高的两个簇进行合并,这个过程不断重复,直到达到预设的簇类个数K或只剩下一个簇。

在层次聚类中,簇间的相似度通常通过距离来度量,距离越小表示相似度越高。常用的距离度量方法包括欧氏距离、曼哈顿距离、切比雪夫距离等。

二、步骤

  1. 初始化:将每个样本点视为一个独立的簇。

  2. 计算相似度:计算所有簇之间的相似度(或距离)。这一步通常生成一个相似度矩阵(或距离矩阵),其中矩阵的元素表示对应簇之间的相似度(或距离)。

  3. 合并簇:找出相似度最高(或距离最小)的两个簇,将它们合并为一个新的簇。同时,更新相似度矩阵,以反映新簇与其他簇之间的相似度(或距离)。

  4. 重复合并:重复步骤2和步骤3,直到达到预设的簇类个数K或只剩下一个簇。在每一步中,都需要重新计算并更新相似度矩阵。

  5. 生成聚类结果:根据最终的簇结构,将样本点分配到相应的簇中,形成聚类结果。

三、优缺点

优点

  • 不需要预先指定簇的数量,可以通过观察聚类树状图来决定簇的数量。
  • 可以发现不同层次上的簇结构,有助于更深入地理解数据。

缺点

  • 计算复杂度较高,特别是当样本点数量较多时。
  • 合并或拆分的决策一旦作出,就不能撤销,这可能导致聚类结果对初始条件敏感。

四、优化方法

为了降低层次聚类算法的计算复杂度,可以采用一些优化方法,如:

  • 使用连通性约束来减少需要计算相似度的簇对数量。
  • 利用并行计算技术来加速算法的执行。

总的来说,层次聚类算法是一种灵活且强大的聚类方法,适用于探索性数据分析和复杂数据集的聚类任务。

五、Python实现

在Python中,实现层次聚类算法通常可以使用scipy库中的linkage函数和fcluster函数,它们提供了层次聚类的核心功能。不过,需要注意的是,scipy直接提供的是层次聚类的计算部分,而聚类结果的可视化(如树状图或称为树状结构图,dendrogram)则可能需要借助matplotlibscipy.cluster.hierarchy模块的其他函数。

以下是一个使用scipy进行层次聚类的基础示例,包括计算层次聚类的结果并绘制树状图:

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist

# 示例数据
X = np.array([[1, 2], [1, 4], [1, 0],
              [4, 2], [4, 0], [4, 4],
              [4, 5], [0, 1], [2, 2],
              [3, 3], [5, 5]])

# 计算所有点之间的欧氏距离
Y = pdist(X, 'euclidean')

# 使用linkage函数进行层次聚类,method='ward'表示最小方差法
Z = linkage(Y, 'ward')

# 绘制树状图
plt.figure(figsize=(10, 7))
dendrogram(Z, labels=range(1, len(X) + 1))
plt.xlabel('Sample index')
plt.ylabel('Distance')
plt.title('Dendrogram')
plt.show()

# 如果需要按照一定的簇数量进行切割,可以使用fcluster
from scipy.cluster.hierarchy import fcluster

# 假设我们想要得到3个簇
max_d = 3  

# 这里的max_d并不是直接的簇数量,而是用于fcluster的一个阈值参数
# 对于'ward'方法,通常使用'maxclust'参数来指定簇的数量,但这里为了演示fcluster的用法,我们仍然使用阈值
# 注意:对于'ward'方法,使用fcluster的'maxclust'参数可能更直接
clusters = fcluster(Z, max_d, criterion='distance')

# 打印聚类结果
print("Cluster memberships:", clusters)

# 注意:由于我们是用阈值来划分簇的,这可能导致簇的数量不等于max_d
# 如果想要精确控制簇的数量,应该使用'maxclust'参数(但'ward'方法可能不直接支持)
# 或者,可以先观察树状图,然后选择一个合适的阈值

重要说明

  1. 在上面的代码中,linkage函数的method参数设置为'ward',它代表Ward最小方差法,这是一种常用的层次聚类方法。但是,fcluster函数中的criterion='distance'并不是与'ward'方法直接对应的最佳方式,因为'ward'方法更适合使用criterion='maxclust'(尽管scipy的当前版本中fcluster可能不直接支持'ward''maxclust'的组合)。然而,为了演示fcluster的用法,我们还是使用了'distance'作为示例。

  2. 在实际应用中,你可能需要根据树状图的形状和你对数据的理解来选择一个合适的阈值或簇的数量。

  3. 如果你确实需要按照簇的数量来切割树状图,并且你的scipy版本不支持criterion='maxclust''ward'方法的组合,你可能需要手动选择一个阈值,或者寻找其他支持这种功能的库(如scikit-learn中的层次聚类实现,尽管它可能不完全相同)。但是,请注意,scikit-learn的层次聚类实现可能更注重于凝聚层次聚类,并且可能不提供与scipy相同的所有功能。

运行结果:

Cluster memberships: [4 4 3 2 2 1 1 3 4 2 1]

标签:层次,树状,Python,算法,scipy,fcluster,聚类,ward
From: https://blog.csdn.net/u013571432/article/details/141334670

相关文章

  • 谱聚类算法原理及Python实现
    谱聚类算法(SpectralClustering)是一种基于图论的聚类算法,其原理与步骤可以详细阐述如下:一、原理谱聚类算法建立在谱图理论基础上,它将聚类问题转化为图的最优划分问题。具体来说,算法将数据集中的每个对象看作是图的顶点V,将顶点间的相似度量化作为相应顶点连接边E的权值,从而得......
  • python基础(06控制语句)
    python系列文章目录python基础(01变量&数据类型&运算符)python基础(02序列共性)python基础(03列表和元组)python基础(04字符串&字典)python基础(05集合set)文章目录python系列文章目录前言一、语句块二、bool类型:Ture、False三、条件判断(if、else、elif)四、循环语句五、推......
  • 高校爬虫可视化系统-基于python|Django|flask的高校爬虫可视化系统|大学数据抓取与展
    博主介绍:✌十余年IT大项目实战经验、在某机构培训学员上千名、专注于本行业领域✌技术范围:Java实战项目、Python实战项目、微信小程序/安卓实战项目、爬虫+大数据实战项目、Nodejs实战项目、PHP实战项目、.NET实战项目、Golang实战项目。主要内容:系统功能设计、开题报告......
  • 算法备案流程中的痛点攻克指南
    主体信息填报的难点主要包括以下几个方面:1.《落实算法安全主体责任基本情况》的填写:需要详细描述企业在算法安全方面的组织架构、专职机构设置、以及相关责任人的职责分配。2.算法安全责任人工作证明:必须提供算法安全责任人的身份证明和工作职责证明,这可能需要企业内部的详......
  • TCPIP路由技术第一卷第七章第三部分Eigrp邻居发现以及DUAL算法
    普通情况下eigrp每5秒发一次hello.在多点的x.25、帧中继和atm接口上,由于他们介入链路速率通常是t1或更低的速率,他们的hello数据包是以单播方式每60s发送一次的.hello包5秒一次常见接口ethernet,point-to-point,point-to-point子接口帧中继.hello包60秒一次常见接口nbmafra......
  • TCPIP路由技术第一卷第七章第四部分DUAL算法
    eigrp三张表neighbortoplogy目的网络的可行距离所有的可行后续路由器每一个可行后续路由器所通告的到达目的网络的通告距离.本地路由器所计算的经过每一个可行后续路由器到达目的网络的距离,也就是基于可行后续路由器所通告的到达目的子网的距离和本地路由器与该可行后续路......
  • python随笔day4
    python实战面试题目1、列出你知道的http协议的状态码,说出表示什么意思?1xx临时响应2xx成功3xx重定向4xx请求错误5xx服务器错误我经常遇到的:200成功、404未找到网页文件、403服务器拒绝请求(禁止)、304未修改(自从上次请求后该网页就未修改过)、500服务器内部错误、503服务器......
  • OpenCV-Python系列之对极几何
    点击查看代码importnumpyasnpimportcv2ascvimg1=cv.imread("data1/1.png",0)#queryimageleftimageimg2=cv.imread("data1/2.png",0)#trainimagerightimagesift=cv.SIFT_create()#sift1=cv.xfeatures2d.SIFT_create()kp1,des1=sift.dete......
  • 【OpenCV_python】凸包检测 轮廓特征 直方图均衡化 模板匹配 霍夫变换
    凸包特征检测凸包就是图像的最小外接多边形,通过图像的轮廓点,找到距离最远的两个点的直线,根据直线找到距离最远的下一个点,直到所有的点被包围在多边形内读取图像二值化找图像的轮廓获取凸包点的坐标绘制凸包点convexHull获得图像的凸包点cv2.convexHull(points,hu......
  • yolov8双目测距(包含有前端的源码和无前端的源码Sgbm双目测距算法)-内含测距代码,视差图
    YOLOv8:YOLOv8是一个目标检测模型,它是YOLO(YouOnlyLookOnce)系列的一部分,用于实时物体检测。YOLOv8能够快速准确地检测视频或图像中的对象。双目测距:双目测距是指使用两个摄像头(或一个立体相机)从不同角度拍摄同一场景,通过比较两个摄像头捕捉到的图像差异来计算物体的距......