这篇文章所提到的图论里面定义，参考我之前的文章http://blog.csdn.net/tyh70537/article/details/75309042
这篇文章将详细介绍阈值图（threshold graph)，单连接算法和全连接算法的一般步骤。 我前面已经提到过，单连接算法和全连接算法都是从一个邻近度矩阵（proximity matrix）开始。一般情况下，给定n个待聚类的对象， X={x1,x2,⋯,xn} ，邻近度矩阵是一个 n×n 的对称阵， D=[d(i,j)] 。矩阵对角线上的元素为零，由于矩阵是对称的，我们只考虑对角线右侧的n(n-1)/2个元素。 为了简单起见，我们做出如下假定： 一：每个元素表示不同对象之间的不相似度（dissimilarity)，比如d(1,2)>d(1,3)说明对象1和3之间的相似程度大于1和2的。 二：这n(n-1)/2个元素的值取1到n(n-1)/2间的整数，且没有重复值。也就是说邻近度是序数变量。后面我们也会使用包含连续变量的邻近度矩阵，其实不影响。 本文用到的邻近度矩阵如下（n=5）：
D=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪068276015381010925100473940⎫⎭⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪(1)在介绍单连接算法和全连接算法之前，先介绍下什么是阈值图。 阈值图是一个有n个节点的无向图，每个节点代表一个对象，图中不存在环（self-loops)和多重边（multiple edges)。一个阈值图用G(v)表示，其中v表示不相似的水平(dissimilarity level)。给定一个v，如果节点i和j之间的不相似度小于v，就在i和j之间插入一条边 edge(i,j) 。 也就是说，
(i,j)∈G(v)ifandonlyifd(i,j)≤v(2) 以(1)中数据为例，取v=5，将得到如下阈值图：step 1. 画出图G(0)，此时图中只有n个节点，一条边都没有，每个对象都被划分为一个簇，即有n个簇。Set k←1 。 step 2. 画出图G(k)，如果G(k)中的最大连通子图（maximal connected subgraph)的数量少如当前簇的数量，则把G(k)中的每个最大连通子图都作为一个簇。 step 3. 如果G(k)中只剩下一个连通子图，则算法停止。否则Set k←k+1 ，并返回step 2。 下面通过例子(1)的阈值图来详细说明。 首先G(0)阶段把对象划分成了5个簇。 到G(1)阶段，阈值v取1的时候，只有d(2,3)满足要求，故G(1)中只有2和3之间有边，此时G(1)中最大连接子图的数量变为4（分别是{2,3},{1},{4},{5})。因此把每个最大连接子图都划分成一个新的簇。 同理，到了G(2)阶段，对象分别被划分成3个簇。G(3)阶段，对象被划分成2个簇。 最后，G(4)阶段的时候，图中只剩下一个连通子图，所有的对象被划分成一个簇，算法结束。
聚类结果用树状图表示如下，其记录了聚类的顺序。
step 1. 画出图G(0)，此时图中只有n个节点，一条边都没有，每个对象都被划分为一个簇，即有n个簇。Set k←1 。 step 2. 画出图G(k)， 如果当前有2个簇在图G(k)中形成了最大完全子图(maximal complete subgraph)那么就把这2个簇合并成一个簇。 step 3. 如果k=n(n-1)/2，也就是图G(k)成为了一个完全图时，算法停止。 否则，Set k←k+1 ，并返回step 2。 同样的，通过阈值图来说明聚类的过程： 聚类结果树状图表示如下： 完全连接算法和单连接算法在形成簇的要求上有很大不同。单连接算法把只要是相连的点都归为一个簇，因此当整个阈值图变成连通图时，聚类就完成了。而完全连接算法对形成簇的要求更加严格，新形成的簇必须是一个最大完全子图，也就是说簇中的每个点之间都必须相连。 我们按顺序来解释完全连接算法的阈值图： G(0): 这里和单连接算法是一样的，每个点都是一个单独的簇。每个点其实也可看作只包含一个点的最大完全子图。 G(1): 这里节点2和3是G(0)中的簇，它们此刻又构成了一个最大完全子图，故簇2和3被合并成一个新簇。 G(2): 同上，簇1和4合并成一个新簇。 G(3): 虽然2和5相连，但2，3，5并没有构成一个最大完全子图，所以G(3)阶段没有新簇产生。 G(4): 没有新簇产生，理由同上。 G(5): 现在问题就来了，2，4，5构成了一个最大完全子图，但我们并没有把它们划分成一个簇，这是为什么呢？这是因为簇 {x2,x3} 和簇 {x1,x4} 已经存在了，对象 x5 只能想办法合并到这两个已经存在的簇当中去，而不能把已经形成的簇重新拆开，这也是层次聚类算法的要求。 G(6): 这里由于同样的原因，1，2，4不能聚成一个簇。 G(7): 到这里终于有满足条件的新簇产生了，即1，4，5。 本来按照完全连接算法的要求，一直要进行到G(10)时，算法才停止，但实际上只需要进行到G(7)就行了，因为G(7)的时候只有2个簇了，后面的步骤肯定是将这两个簇合成一个簇，也就没必要进行了。同理，单连接算法在进行到G(3)的时候就已经没有悬念了。
