一、
下面的HIERARCHICALCLUSTERING算法需要输入一个n*n的距离矩阵d，并产生数据的n个不同的分划，以树的形式输出。
HIERARCHICALCLUSTERING（d,n）
形成n个类，每个类含有一个元素
构建图T，为每个类分配一个单独的顶点
while 存在多于一个类
找到最近的2个类C1和C2
将C1和C2合并成一个新的类C，C含有|C1|+|C2|个元素
计算C与其他各类的距离
在图T中增加一个顶点C，且与C1和C2相连
在d中删除与C1和C2相对应的行和列
在d中为新类C增加一行一列
return T
二、
将一个n*m的表达矩阵的n行看成为m维空间中n个点的集合,将其划分成k个子集，并假定类的个数k是已知的。
K均值聚类问题
给定n个数据点，找到k个凝聚点，满足平方误差失真最小。
输入：含有n个点的集合v和参数k
输出：含有k个点(凝聚点)的集合，满足d(x,y)对X所有可能的选择为最小。
我们假设将n个元素的集合分划成k个类的每个分划P都有与之相关联的聚类成本，记为cost(P），以此来衡量分划P的质量：分划的聚类成本越低，聚类的效果就越好。
给定一个分划P、一个该分划下的类C以及类C外一个元素i,Pi->c表示在分划P中将元素i移动到类C中得到的分划。△(i->C)=cost(P)-cost(Pi->c)>0时，移动改善了聚类成本
PROGRESSIVEGREEDYK-MEANS(k)
选择一个任意分划P，将元素分成k个类。
while 不断循环
bestchange<-0
for 每个类C
for 每个元素i不属于C
if将i移动到类C中会减少聚类成本
if △(i->C)>bestchange
bestchange<-△(i->C)
i*<-i
C*<-c
ifbestchange>0
通过将i*移动到类C*来改进分划
else
returnP
三、有瑕图
确定将一个图转换成团图时所需要增加或者删除的最小边数
输入：图G
输出：将图G转换成一个团图需要增加或删除的最小边数
距离图上顶点表示不同的基因，且基因i和基因j之间有一条边相连，当且仅当这2个基因之间的距离小于阈值θ，即di,j<θ，对于一个合适地选择θ，一个满足同质性和差异性原则的基因聚类将对应于一个距离图，且该图是一个团图。
将基因i和类C之间的距离定义为基因i和类C中所有基因之间的平均距离：d(i,C)，给定一个θ，如果d(i,C)<θ，则称基因i邻近于类C，反之称为基因i远离于类C。
CAST（G，θ）
S<-距离图G中顶点的集合
P<-φ(φ表示空集)
while S≠φ
v<-距离图G中度最大的顶点
C<-{v}
while存在一个邻近的基因i不属于C，或一个远离的基因i属于C
找到一个最邻近的基因i不属于C，并将其加到类C中
找到一个最远离的基因i属于C，并将其从类C中删除
将类C增加到分划P中
S<-S\C
从距离图G中剔除类C中的顶点
returnP