Hierarchical Clustering-DIANA

DIANA算法（DIvisive ANAlysis)算法是一种分裂式层次聚类算法，它的主要步骤步骤如下：

举例说明，假设二维空间八个元素，分布位置如下：

坐标点	属性1	属性2
\(P_1\)	1	1
\(P_2\)	1	2
\(P_3\)	2	1
\(P_4\)	2	2
\(P_5\)	3	4
\(P_6\)	3	5
\(P_7\)	4	4
\(P_8\)	4	5

步骤1：找出具有最大直径的集群，开始时指的就是所有集群。

步骤2：在最大直径集群中，找到每个点与其他点的平均距离：
\(P_1\)与其他点平均距离为：
\(\begin{align*}
d(P_1)&=(\sqrt{(1-1)^2+(2-1)^2}+\sqrt{(2-1)^2+(1-1)^2}+\dots+\sqrt{(4-1)^2+(5-1)^2})/7\\
&=(1+1+1.1414+3.6+4.24+4.47+5)/7\\
&=2.96
\end{align*}\)
同理：
\(d(P_2)=(1+1.414+1+2.828+3.6+3.6+4.24)/7=2.526\)
\(d(P_3)=(1+1.414+1+3.16+4.12+3.6+4.27)/7=2.68\)
\(d(P_4)=(1.414+1+1+2.24+3.16+2.828+3.6)/7=2.18\)
\(d(P_5)=2.18\)
\(d(P_6)=2.68\)
\(d(P_7)=2.526\)
\(d(P_8)=2.96\)

在上面所有的距离中，\(P_1\)与其他点的平均距离最远，放入splinter group，其他点放入old party中，那么
splinter group={\(P_1\)}
old party={\(P_2\),\(P_3\),\(P_4\),\(P_5\),\(P_6\),\(P_7\),\(P_8\)}

步骤3：找出old party中到splinter group最近的点的距离不大于到old party其他点最小距离的点，加入到splinter group中。对于old party中的每一个点依次计算：
\(P_2\)到splinter group中点\(P_1\)的距离为1，因为splinter group中只有一个点，依次\(P_2\)到splinter group中最近的点的距离为1
\(P_2\)到old party中点\(P_3\)的距离为1.1414
\(P_2\)到old party中点\(P_4\)的距离为1
\(P_2\)到old party中点\(P_5\)的距离为2.828
\(P_2\)到old party中点\(P_6\)的距离为3.6
\(P_2\)到old party中点\(P_7\)的距离为3.6
\(P_2\)到old party中点\(P_8\)的距离为4.24
因此\(P_2\)到old party中最近的点(\(P_4\))的距离是1，满足到splinter group最近的点距离不大于到old party其他点最小距离的条件，因此将\(P_2\)加入splinter group中。
此时splinter group={\(P_1\),\(P_2\)}
old party={\(P_3\),\(P_4\),\(P_5\),\(P_6\),\(P_7\),\(P_8\)}

步骤4：重复步骤3，直到不存在这样的点结束，此时已经将最大的集群分成两个。如果此时集群的数量未达到终止条件，则继续重复步骤2，选择一个最大直径的集群进行分裂。