参考文章

DIANA算法思想

DIANA算法属于分裂的层次聚类,与凝聚的层次算法(也就是AGNES),它采用一种自顶向下的策略,它首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一个簇,或者达到某个终结点,比如达到了某个希望的簇数目,或者两个最近簇之间的距离超过了某个阈值。

在DIANA方法的处理过程中,所有的对象初始值都放在一个簇中,根据某一些原则,将该簇进行分裂,簇的分类过程反复进行,直到最终每个新的簇只包含一个对象。

举例

对于所给的数据进行DIANA算法,(设n=8,用户输入的终止条件为两个簇), 初始簇{1,2,3,4,5}。
DIANA算法步骤如下:

输入簇数据

第一步, 找到具有最大直径的簇,对簇中的每个点计算平均相异度。

就是一个点与一个簇中的所有其他点的平均距离,用来衡量该点与簇的离群(孤立)程度。

(1),序号1的平均距离(就是1距离其他各个点的距离长度之和除以4)
s1=(18+20.6+22.4+7.07)/4=17.01;
序列2的平均距离 s2=(18+14.1+11.2+18)/4=15.32;
序列3的平均距离 s3=(20.6+14.1+5.0+25.0)/4=16.17;
序列4的平均距离 s4=(22.4+11.2+5.0+25.5)/4=16.07
序列5的平均距离 s5=(7.07+18+25+25.5)/4=18.89;

把5点的平均距离中,挑选一个最大平均相异度的点5放入part1中,剩余点放在party2中;
part1={5}, party2={1,2,3,4}

第二步,在party2里找出到最近的party1中的点距离不大于到party2中最近的点的距离的点,将该点放入party1中,该点就是1;
part1={1,5}, party2={2,3,4}

step1

第三步,在party2里继续找出到最近的part1的点距离不大于到party2中最近的点的距离的点,将该点放在part1中,此时没有满足条件的点。
party1={1,5}, party2={2,3,4}
如果此时达到阈值条件就结束,输出结果,否则继续。

step2

第四步,找到具有最大直径的簇,对簇中的每个点计算平均相异度。

簇1={1,5} 簇2={2,3,4}

分别的直径计算得:
d1=(25+25)/2=5d_1 = \sqrt{(25+25)/2}=5
d2=(125+200+125+25+25+200)/6=10.8d_2 = \sqrt{(125+200+125+25+25+200)/6} = 10.8
d2d_2最大,所以选择簇2进行分解。

step3

第五步,同上平均相异度最大的点为2号,所以将其放入party1={2} 其余点放入party2={3,4}。然后在party2里继续找出到最近的part1的点距离不大于到party2中最近的点的距离的点,将该点放在part1中,此时没有满足条件的点。
所以最终的簇分解为,簇1={1,5},簇2={3}。簇3={4,5},且满足最终分类簇数为3的条件,结束。