算法介绍
层次聚类(Hierarchical Clustering)是聚类算法的一种，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法。
在社会学领域，一般通过给定网络的拓扑结构定义网络节点间的相似性或距离，然后采用单连接层次聚类或全连接层次聚类将网络节点组成一个树状图层次结构。其中，树的叶节点表示网络节点，非叶节点一般由相似或距离接近的子节点合并而得到。
层次聚类方法的基本思想是：通过某种相似性测度计算节点之间的相似性，并按相似度由高到低排序，逐步重新连接个节点。该方法的优点是可随时停止划分，主要步骤如下：
移除网络中的所有边，得到有n个孤立节点的初始状态；
计算网络中每对节点的相似度；
根据相似度从强到弱连接相应节点对，形成树状图；
根据实际需求横切树状图，获得社区结构。
自底向上的合并算法：
层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。
示意图如下图所示：
算法优势
优点：
距离和规则的相似度容易定义，限制少；
不需要预先制定聚类数；
可以发现类的层次关系；
可以聚类成其它形状；
缺点：
计算复杂度太高；
奇异值也能产生很大影响；
算法很可能聚类成链状；
参数介绍
sklearn.cluster.AgglomerativeClustering(n_clusters=2,*,affinity='euclidean',memory=None,connectivity=None,compute_full_tree='auto',linkage='ward',distance_threshold=None)
参数：
n_clusters：一个整数，指定分类簇的数量。
connectivity：一个数组或者可调用对象或者None，用于指定连接矩阵。
affinity：一个字符串或者可调用对象，用于计算距离。可以为：'euclidean'、'l1'、'l2'、'mantattan'、'cosine'、'precomputed'，如果linkage='ward'，则affinity必须为'euclidean'。
memory：用于缓存输出的结果，默认为不缓存。
n_components：在v-0.18中移除。
compute_full_tree：通常当训练了n_clusters后，训练过程就会停止，但是如果compute_full_tree=True，则会继续训练从而生成一颗完整的树。
linkage：一个字符串，用于指定链接算法。
(1).'ward'：单链接single-linkage，采用dmindmin；
(2).'complete'：全链接complete-linkage算法，采用dmaxdmax；
(3).'average'：均连接average-linkage算法，采用davgdavg；
pooling_func：一个可调用对象，它的输入是一组特征的值，输出是一个数。
属性：
labels：每个样本的簇标记。
n_leaves_：分层树的叶节点数量。
n_components：连接图中连通分量的估计值。
children：一个数组，给出了每个非节点数量。
方法：
fit(X[,y])：训练样本。
fit_predict(X[,y])：训练模型并预测每个样本的簇标记。
调优方法
BIRCH算法(常用)：
适合大规模数据集，线性效率；
只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数。
CURE算法：
能够处理非球形分布的应用场景；
采用随机抽样和分区的方式可以提高算法的执行效率。
适用场景
适合包含大量聚类，可能是连通性约束的，非欧几里得距离。
如果是按变量(或标题)聚类，此类聚类的代表是层次聚类，层次聚类会生成聚类树状图，可以直观看到聚类结果，可结合专业知识综合判定分析。
由于K-means聚类需要自己设定聚类个数，设置的太多或太少都可能影响聚类效果，而层次聚类可以自动聚类类别数量，不需要事先设定聚类个数，因此有时也会将K-means聚类和层次聚类结合起来使用。
demo示例
from sklearn.cluster import AgglomerativeClusteringimport numpy as npX = np.array([[1, 2], [1, 4], [1, 0], [4, 2], [4, 4], [4, 0]])clustering = AgglomerativeClustering().fit(X)clustering# AgglomerativeClustering()clustering.labels_# array([1, 1, 1, 0, 0, 0])

ML之HierarchicalClustering：自定义HierarchicalClustering层次聚类算法
目录
输出结果
实现代码
输出结果
更新……
实现代码
# -*- encoding=utf-8 -*-

from numpy import *

class cluster_node:  #定义cluster_node类，类似Java中的构造函数
    def __init__(self,vec,left=None,right=None,distance=0.0,id=None,count=1):
        self.left=left  
        self.right=right
        self.vec=vec
        self.id=id
        self.distance=distance
        self.count=count #only used for weighted average 

def L2dist(v1,v2):  
    return sqrt(sum((v1-v2)**2))
    
def L1dist(v1,v2):  
    return sum(abs(v1-v2))

def hcluster(features,distance=L2dist): 
    #cluster the rows of the "features" matrix
    distances={}     
    currentclustid=-1 

    # clusters are initially just the individual rows
    clust=[cluster_node(array(features[i]),id=i) for i in range(len(features))]


    while len(clust)>1:  
        lowestpair=(0,1) 
        closest=distance(clust[0].vec,clust[1].vec)
    
        for i in range(len(clust)):
            for j in range(i+1,len(clust)):
                # distances is the cache of distance calculations
                if (clust[i].id,clust[j].id) not in distances: 
                    distances[(clust[i].id,clust[j].id)]=distance(clust[i].vec,clust[j].vec)
        
                d=distances[(clust[i].id,clust[j].id)]  
        
                if d<closest:  
                    closest=d
                    lowestpair=(i,j) 
        
        mergevec=[(clust[lowestpair[0]].vec[i]+clust[lowestpair[1]].vec[i])/2.0 
            for i in range(len(clust[0].vec))]
        
        newcluster=cluster_node(array(mergevec),left=clust[lowestpair[0]],
                             right=clust[lowestpair[1]],
                             distance=closest,id=currentclustid)
        
        currentclustid-=1  
        del clust[lowestpair[1]]
        del clust[lowestpair[0]]
        clust.append(newcluster)

    return clust[0]

def extract_clusters(clust,dist):  #(clust上边的树形结构，dist阈值)
    # extract list of sub-tree clusters from hcluster tree with distance<dist
    clusters = {}
    if clust.distance<dist:
        # we have found a cluster subtree
        return [clust] 
    else:
        # check the right and left branches
        cl = []   
        cr = []
        if clust.left!=None:  
            cl = extract_clusters(clust.left,dist=dist)
        if clust.right!=None: 
            cr = extract_clusters(clust.right,dist=dist)
        return cl+cr  
        
def get_cluster_elements(clust):  #用于取出算好聚类的元素
    # return ids for elements in a cluster sub-tree
    if clust.id>=0:  
        # positive id means that this is a leaf
        return [clust.id]
    else:
        # check the right and left branches
        cl = []
        cr = []
        if clust.left!=None: 
            cl = get_cluster_elements(clust.left)
        if clust.right!=None: 
            cr = get_cluster_elements(clust.right)
        return cl+cr


def printclust(clust,labels=None,n=0):  #将值打印出来
    # indent to make a hierarchy layout
    for i in range(n): print (' '),
    if clust.id<0: 
        # negative id means that this is branch
        print ('-')
    else:           
        # positive id means that this is an endpoint
        if labels==None: print (clust.id)
        else: print (labels[clust.id])
    
    if clust.left!=None: printclust(clust.left,labels=labels,n=n+1)
    if clust.right!=None: printclust(clust.right,labels=labels,n=n+1)



def getheight(clust):  #树的高度，递归方法
    # Is this an endpoint? Then the height is just 1
    if clust.left==None and clust.right==None: return 1
    
    # Otherwise the height is the same of the heights of
    # each branch
    return getheight(clust.left)+getheight(clust.right)

def getdepth(clust):   #树的深度，递归方法
    if clust.left==None and clust.right==None: return 0
    
    return max(getdepth(clust.left),getdepth(clust.right))+clust.distance
      
      
相关文章
ML之H-clustering：自定义HierarchicalClustering层次聚类算法

每篇一句：


  
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 Clustering Method）又称为系统聚类法、分级聚类法。


层次聚类算法又分为两种形式：

凝聚层次聚类：

首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
分裂层次聚类：

首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。
凝聚层次聚类：

本文介绍的为第一种形式，即凝聚层次聚类：


  
思路：每个样本先自成一类，然后按距离准则逐步合并，减少类数。


算法描述：

1）N个初始模式样本自成一类，即建立N类：

G1(0)，G2(0)，…，Gn(0)     (G_Group)


计算  各类之间（即各样本间）的距离（相似性、相关性），得一N*N维距离矩阵。“0”表示初始状态。

2）假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：

G1(n+1)，G2(n+1)，…


3）计算合并后新类别之间的距离，得D(n+1)。

4）跳至第二步，重复计算及合并。

结束条件：

取距离阈值T，当D(n)的最小分量超过给定值T时，算法停止。所得即为聚类结果。
或不设阈值T，一直将全部样本聚成一类为止，输出聚类的分级树。

问题讨论：——类间距离计算准则

在算法描述第一步中提到要计算每个聚类之间的距离，在层次聚类算法中，计算聚类距离间距的计算方法主要有以下五种：

1）最短距离法：  （常用）

如H、K是两个聚类，则两类间的最短距离定义为：

 Dhk = min{D(Xh，Xk)} Xh∈H，Xk∈K


Dhk: H类中所有样本与K类中所有样本之间的最小距离。

D(Xh，Xk)： H类中的某个样本Xh和K类中的某个样本Xk之间的欧式距离。



如果K类由I和J两类合并而成，则：

 Dhi = min{D(Xh, Xi)} Xh∈H,Xi∈I 
 Dhj = min{D(Xh, Xj)}   Xh∈H,Xj∈J


得到递推公式：

 Dhk = min{Dhi, Dhj}





2) 最长距离法：

 



3）中间距离法： 

介于最长与最短的距离之间。如果 K 类由 I 类和 J 类合并而成，则 H 和 K 类之间的距离为： 
 



4）重心法：

将每类中包含的样本数考虑进去。若 I 类中有 n I 个样本， J 类中有 n J 个样本，则类与类之间的距离递推式为：

 



5）类平均距离法：




  
定义类间距离的方法不同，分类结果会不太一致。实际问题中常用几种不同的方法，比较分类结果，从而选择一个比较切合实际的分类。

Python 实现：

解释说明见代码中注释
# coding=utf-8

from max_min_cluster import get_distance


def hierarchical_cluster(data, t):
    # N个模式样本自成一类
    result = [[aData] for aData in data]
    step2(result, t)
    return result


def step2(result, t):

    # 记录类间最小距离
    min_dis = min_distance(result[0], result[1])  # 初始为1,2类之间的距离

    # 即将合并的类
    index1 = 0
    index2 = 1

    # 遍历，寻找最小类间距离
    for i in range(len(result)):
        for j in range(i+1, len(result)):
            dis_temp = min_distance(result[i], result[j])
            if dis_temp < min_dis:
                min_dis = dis_temp
                # 记录即将合并的聚类位置下标
                index1 = i
                index2 = j

    # 阈值判断
    if min_dis <= t:
        # 合并聚类index1, index2
        result[index1].extend(result[index2])
        result.pop(index2)
        # 迭代计算，直至min_dis>t为止
        step2(result, t)


def min_distance(list1, list2):

    # 计算两个聚类之间的最小距离：
    # 遍历两个聚类的所有元素，计算距离（方法较为笨拙，有待改进）

    min_dis = get_distance(list1[0], list2[0])
    for i in range(len(list1)):
        for j in range(len(list2)):
            dis_temp = get_distance(list1[i], list2[j]) # get_distance()函数见另一篇博文《聚类算法——最大最小距离算法》
            if dis_temp < min_dis:
                min_dis = dis_temp
    return min_dis

# 测试hierarchical_cluster
# data = [[0, 3, 1, 2, 0], [1, 3, 0, 1, 0], [3, 3, 0, 0, 1], [1, 1, 0, 2, 0],[3, 2, 1, 2, 1], [4, 1, 1, 1, 0]]
# t = math.sqrt(5.5)
# result = hierarchical_cluster(data, t)

# for i in range(len(result)):
#     print "----------第" + str(i+1) + "个聚类----------"
#     print result[i]

# 结果为：
# ----------第1个聚类----------
# [[0, 3, 1, 2, 0], [1, 3, 0, 1, 0], [1, 1, 0, 2, 0]]
# ----------第2个聚类----------
# [[3, 3, 0, 0, 1]]
# ----------第3个聚类----------
# [[3, 2, 1, 2, 1], [4, 1, 1, 1, 0]]


注： 

本次代码实现中采取的类间距离计算准则为最短距离法，但并未采取文中介绍的递推公式，而是采取的较为简单的遍历方式，数据量较大时，算法效率较低，读者有时间的话可以思考尝试所介绍的递推方式。
最后：

本文简单的介绍了 聚类算法——层次聚类算法 中 凝聚层次聚类 的相关内容，以及相应的代码实现，如果有错误的或者可以改进的地方，欢迎大家指出。

代码地址：聚类算法——层次聚类算法（码云）

本文实例为大家分享了Python实现简单层次聚类算法，以及可视化，供大家参考，具体内容如下
基本的算法思路就是：把当前组间距离最小的两组合并成一组。
算法的差异在算法如何确定组件的距离，一般有最大距离，最小距离，平均距离，马氏距离等等。
代码如下：
import numpy as np
import data_helper
np.random.seed(1)
def get_raw_data(n):
_data=np.random.rand(n,2)
#生成数据的格式是n个(x,y)
_groups={idx:[[x,y]] for idx,(x,y) in enumerate(_data)}
return _groups
def cal_distance(cluster1,cluster2):
#采用最小距离作为聚类标准
_min_distance=10000
for x1,y1 in cluster1:
for x2,y2 in cluster2:
_distance=(x1-x2)**2+(y1-y2)**2
if _distance<_min_distance:>
_min_distance=_distance
return _distance
groups=get_raw_data(10)
count=0
while len(groups)!=1:#判断是不是所有的数据是不是归为了同一类
min_distance=10000
len_groups=len(groups)
for i in groups.keys():
for j in groups.keys():
if i>=j:
continue
distance=cal_distance(groups[i],groups[j])
if distance
min_distance=distance
min_i=i
min_j=j#这里的j>i
groups[min_i].extend(groups.pop(min_j))
data_helper.draw_data(groups)
#一共n个簇，共迭代n-1次
运行的效果就是迭代一次，组数就会少一次，调用画图方法，同一组的数据被显示为一个颜色。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。