机器学习-入门

【算法】一篇入门之-层次聚类算法

作者 : 老饼 发表日期 : 2022-06-26 23:25:16 更新日期 : 2024-10-05 19:22:14
本站原创文章,转载请说明来自《老饼讲解-机器学习》www.bbbdata.com



层次聚类法(Agglomerative)分为凝聚法和分裂法,它将每个样本点逐层聚为一类

本文讲解层次聚类算法的算法步骤,聚类过程,所用的距离计算公式,以及代码实现

通过本文,可以快速知道什么了层次聚类算法,如何使用层次聚类算法对样本进行聚类




    01. 什么是层次聚类算法      



本节讲解什么是层次聚类算法,以及层次聚类算法的流程




      什么是层次聚类算法      


层次聚类算法(Hierarchical)是一种最基本的聚类算法,用于对样本进行聚类
层次聚类算法分为凝聚法和分裂法,但层次聚类法一般默认都是指凝聚法,很少用分裂法
 层次聚类算法(凝聚法Agglomerative)算法流程如下:
1. 将每个样本初始化为一类,有多少个样本就有多少个类别               
2. 计算类别两两之间的距离                                                              
3. 将距离最近的两个类别合并为一类                                                
4. 计算新类别与其它类别的距离                                                       
重复3,4,直到只剩1个类别(或k个类别)
层次聚类的过程解说
 层次聚类算法的聚类过程如下:
  层次聚类算法的聚类过程 
 层次聚类算法(凝聚法)是一种自下而上的算法,上图从最底部往上看
 
从图中可以看到,一共有12个样本,最开始时,它们各自代表着一个类别
根据合并线的高度可以看到,刚开始是2、5合并为一类,然后1、3合并
之后是0、11合并......如此逐层向上,直到最后所有的样本都合并为一类






      层次聚类算法-分裂法的流程      


分裂法是一种自上而下的算法,很少使用,这里仅作简单介绍
层次聚类算法(分裂法)的算法流程如下:

 一、初始化                                                                                
 将所有样本作为一个类别                                         
 二、分裂                                                                                    
            对每个样本>2的类别进行下述分裂,直到每个类别只有一个样本
每个类别分裂的流程如下:                                           
 1. 计算样本两两之间的距离                         
2. 将距离最远的两个样本作为两个类别中心          
3. 将其余样本划分到离它最近的类别中心            
4. 以两个类别上的样本均值作为两个类别的位置      







    02. 层次聚类算法中的距离计算      



本节计算层次聚类算法中常用的的各种距离计算公式




    层次聚类法的类别距离     


层次聚类法在计算两个类别距离时,一般有如下方法:
1. single:最近邻算法,NPA(Nearest Point Algorithm)                                    
 ,其中                       
 解释:u的样本与v的样本两两计算距离 ,取最小距离             
 
                        
 2. complete:最远邻算法,FPA(Farthest Point Algorithm)                                
 ,其中                      
 解释:u的样本与v的样本两两计算距离 ,取最大距离             
 
                 
                     3. average:等权均值法,UPGMA(Unweighted Pair-Group Methodusing the Average approach)
      ,其中                       
 解释:u的样本与v的样本两两计算距离 ,取平均距离             
 

                         4. centroid:等权质心法,UPGMC(Unweighted Paire-Group Method using Centroid approach)
                                           
   解释:类别u的质心(样本均值)与类别v的质心的距离               
 
 
                    5. median: WPGMC,加权质心法(Weighted Pair-Group Method using Centroid approach)
  距离的计算与centroid相同                              
只是将u,v合并时,新类别的位置为u,v质心均值                  

  
    6. weighted: 加权均值法(Weighted Pair Group Method with Arithmetic mean)
 u是刚由s、t两个类别组成的新类别,则u与v的距离计算如下:     
                                          
 解释:两个旧类别s,t与v的距离的平均值                         
 

7. ward :ward方差法                                                                                      
            ward方差中的距离d指的是:如果u类别与v类别合并时,类内方差SSE的增加量
           即 SSE((u,v))-SSE(u)-SSE(v),类内方差SSE是指该类的样本与该类中心的方差之和
  如果每次按上述定义计算,计算量会较大,所以一般使用如下迭代公式:

 
                  其中,u由s、t两个类别合并而成,代表的样本个数, 
其中,ward一般是默认使用方法,其次是single、complete、average等







    03. 层次聚类算法的实现    



本节展示如何实现一个层次聚类算法




    层次聚类代码实现     


在python中虽然用sklearn也能实现层次聚类算法,但它底层调用的其实是scipy
因此,我们这里直接使用scipy来实现层次聚类算法,下面是一个具体的实现例子
 层次聚类算法具体代码如下:
import matplotlib.pyplot as plt
from scipy.cluster import hierarchy
import numpy as np

X = np.array([[1 ,2],[3 ,4],[5 ,6],[1 ,8],[2 ,2]])           # 生成数据X
Z = hierarchy.linkage(X,method='ward', metric='euclidean')   # 使用层次聚类进行聚类
print('\n聚类过程Z:\n',Z)                                    # 打印聚类结果 
plt.figure(figsize=(8, 6))                                   # 初始化画布
hierarchy.dendrogram(Z)                                      # 绘制聚类过程
运行结果如下:
 层次聚类算法的聚类结果
 层次聚类法代码运行结果  
其中,Z记录了合并过程,各列为:类别1,类别2,距离,合并后的样本数
 以Z的第一行为例,它的意思是:类别0与类别4的距离为1,合并后样本个数为2











  End  






联系老饼