层次聚类.doc层次聚类方法
栗爽真
层次聚类方法概述
■层次聚类方法对给定的数据集进行层次的分解,直 到某种条件满足为止。具体又可分为:
凝聚的层次聚类:一种自底向上的策略,首先将每个对象 作为一个簇,然后合并这些原子簇为越來越大的簇,直到某个 终结条件被满足。
分裂的层次聚类:采用自顶向下的策略,它首先将所有对 象置于一个簇中,然后逐渐细分为越來越小的簇,直到达到了 某个终结条件。
层次凝聚的代表是AGNES算法。层次分裂的代表是 DIANA算法。
AGNES算法
■ AGNES(Agglomerative NESting)算法最初将每个对象作为
一个簇,然后这些簇根据某些准则被一步步地合并。两个簇 间的相似度由这两个不同簇中距离最近的数据点对的相似度 来确定。聚类的合并过程反复进行直到所有的对象最终满足 簇数目。
自底向上凝聚算法(AGNES):
输入:包含n个对象的数据库,终止条件簇的数目k。
输出:k个簇,达到终止条件规定簇数目。
将每个对象当成一个初始簇;
REPEAT
根据两个簇中最近的数据点找到最近的两个簇;
合并两个簇,生成新的簇的集合;
UNTIL达到定义的簇的数目;
序号
属性1
属性2
1
1
1
2
1
2
3
2
1
4
2
2
5
3
4
6
3
5
7
4
4
8
4
5
AGNES算法例题
第1步:根据初始簇计算每个簇之间的距离,随机找出距离最小的两 个簇,进行合并,最小距离为1,合并后1,2两个点合并为一个簇。
第2步:对上一次合并后的簇计算簇间距离,找出距离最近的两个簇 进行合并,合并后3,4点成为一簇。
第3步:重复第2步的工作,5,6点成为一簇。
第4步:重复第2步的工作,7,8点成为一簇。
第5步:合并{1,2}, {3,4}成为一个包含四个点的簇。
第6步:合并{5,6}, {7,8},由于合并后的簇的数目己经达到了用户输 入的终止条件,程序终止。
步骤
最近的簇距离
6
最近的两个簇
⑴,{2}
{3},{4}
{5}, {6}
⑺,{8}
{1,2},{3,4}
{5,6}, {7,8}
合并后的新簇
{1,2}, {3}, {4}, {5}, {6}, {7}, {8}
{1,2},
{1,2},
{1,2},
{3,4},
{3,4},
{3,4},
{5},{6}, {7}, {8}
{5,6}, {7}, {8}
{5,6}, {7,8}
{1,2,3,4}, {5,6}, {7,8}
{1,2,3,4}, {5,6,7,8}结束
融2
R 3
层次聚类 来自淘豆网www.taodocs.com转载请标明出处.