频道栏目
首页 > 网络 > 云计算 > 正文

聚类算法 层次聚类算法

2018-02-12 13:43:56      个评论    来源:L_Bo  
收藏   我要投稿

层次聚类算法:

层次聚类算法 (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]]

注:

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

最后:

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

 

上一篇:kafk分布式解析
下一篇:Hbase踩坑
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站