-
层次聚类算法
2012-01-13 19:18:39一些常见的聚类算法,层次聚类算法,是非常常用的聚类算法,同时也是被广泛研究的聚类算法。层次聚类本身分为合并和分裂两种实现,在合并算法中,又分基于矩阵理 论的合并和基于图论的合并。 -
层次聚类算法_层次聚类算法介绍及其参数讲解
2020-12-08 15:20:48算法介绍层次聚类(Hierarchical Clustering)是聚类算法的一种,通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中,不同类别的原始数据点是树的最低层,树的顶层是一个聚类的根节点。创建...算法介绍
层次聚类(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:自定义Hierarchical层次聚类算法
2020-12-13 17:54:55ML之HierarchicalClustering:自定义HierarchicalClustering层次聚类算法目录输出结果实现代码输出结果更新……实现代码# -*- encoding=utf-8 -*- from numpy import * class cluster_node: #定义cluster_node类...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层次聚类算法 -
聚类算法——层次聚类算法
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每篇一句:
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_Python实现简单层次聚类算法以及可视化
2020-12-07 17:45:56本文实例为大家分享了Python实现简单层次聚类算法,以及可视化,供大家参考,具体内容如下基本的算法思路就是:把当前组间距离最小的两组合并成一组。算法的差异在算法如何确定组件的距离,一般有最大距离,最小距离...本文实例为大家分享了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次
运行的效果就是迭代一次,组数就会少一次,调用画图方法,同一组的数据被显示为一个颜色。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。
-
层次聚类算法_【R语言】层次聚类算法及可视化
2020-11-27 10:25:57点击上方蓝字关注我们关于层次聚类层次聚类(Hierarchical Clustering)是一种和 K- 均值聚类类似的聚类算法。和 K-均值聚类不同的是,层次聚类不需要预先确定一个层次值;除此之外 ,层次聚类比 K-均值聚类更有优势的... -
Kmeans聚类算法,PCA降维,层次聚类算法,用Python实现
2019-07-05 10:26:54中科大2019春AI 实验二,包括Kmeans算法,PCA算法和层次聚类算法 -
R聚类算法-层次聚类算法
2017-07-24 16:00:48层次聚类算法又称为树聚类算法,它根据数据之间的距离,透过一种层次架构方式,反复将数据进行聚合,创建一个层次以分解给定的数据集。 常用于一维数据的自动分组层次聚类方法 hclust(dist) dist 样本的距离矩阵 ... -
层次聚类算法_聚类算法 Hierarchical Clustering算法
2020-11-26 10:29:09Hierarchical Clustering算法概述HC算法,又称层次聚类算法,就是按照某种方法进行层次分类,直到满足某种条件为止。简单说它是将数据集中的每个样本初始化为一个簇,然后找到距离最近的两个簇,将他们合并,不断... -
【机器学习】【层次聚类算法-2】层次聚类算法(Hierarchical Clustering Alg)的Python实现
2018-06-01 17:56:58别看层次聚类算法简单,但是实现起来在数据结构方面还需要思考一番,不是那么轻而易举的确定数据结构,实现过的人应该知道的。1.Code# -*- coding: utf-8 -*- """ @author: 蔚蓝的天空Tom Talk is ... -
犹豫模糊团聚层次聚类算法
2021-03-04 01:46:28犹豫模糊团聚层次聚类算法 -
python层次聚类_【挖掘模型】:Python-层次聚类算法
2020-11-28 14:38:44层次聚类算法层次聚类算法又称为树聚类算法,它根据数据之间的距离,透过一种层次架构方式,反复将数据进行聚合,创建一个层次以分解给定的数据集# 使用层次聚类将1,3,5,6,9,10,13聚类# 计算出每个点之间的距离# 找... -
层次聚类算法C++
2016-06-22 11:33:59层次聚类算法C++ VS2010 调试运行成功 -
聚类算法之层次聚类算法和应用举例
2017-05-09 17:47:19聚类算法之层次聚类算法和应用举例 1.假设有N个待聚类的样本,对于层次聚类来说,步骤: 1、(初始化)把每个样本归为一类,计算每两个类之间的距离,也就是样本与样本之间的相似度; 2、寻找各个类之间最近的两... -
层次聚类算法_R 无监督聚类算法(1)K-means和层次聚类
2020-11-30 11:43:57首先我们要解决几个问题聚类算法主要包括哪些算法?主要包括:K-means、DBSCAN、Density Peaks聚类(局部密度聚类)、层次聚类、谱聚类。什么是无监督学习?• 无监督学习也是相对于有监督学习来说的,因为现实中... -
聚类算法(2):系统聚类/层次聚类算法
2019-06-20 15:23:30聚类算法(4)--Hierarchical clustering层次聚类 系统聚类:相当于自下而上法,也就是层次聚类 目录 一、系统聚类 1. 系统聚类实现的一般步骤 2. 常用的距离 3. 类间距离 二、手动实现过程 三、代码实现 1.... -
层次聚类算法解析
2018-03-04 17:45:05上篇博客我们粗略讲解了一下kmeans聚类算法,其中牵涉到了新的聚类算法:层次聚类算法,本篇博客我们着重讲一下这种聚类算法。 kmeans聚类算法可以看做top-down结构,而层次聚类算法则可以视为bottom-up结构,而且...