凝聚法和分裂法的比较
分裂算法快速（运算复杂度为nlgn,n2)，但
不一定得到更好的结果，也不一定能非常准 确反映数据的结构特征。
凝聚法运算复杂度（n2,n3)
比较不同的聚类方法的聚类结果
聚类树的切割
系统聚类
系统聚类是目前基因聚类中最常用的方法之
一，因为它仅需要确定类的合并规则和相似 性度量指标．且得到的系统树图便于对基因 间的相似性进行评价。它的主要缺点在于基 因的分类数需要由用户确定，且当相似短阵 较大时计算量较大。
利用相关系数计算距离
平均点积
向量间的角度 协方差
Pearson相关距离
第二节 聚类算法
聚类算法任务就是寻找到最优函数C，使得
类内的非相似性最小。
聚类算法常被分为两大类：分割方法和系统
方法。分割方法把观测个体最优地分割到固
定数目的类中，系统方法将产生类的嵌套式
的分类序列。
一、系统聚类
确定相似性指标
第一节 相似性或距离的度量
n维空间中的两个点x、y间的距离d具有如下
属性：
1)
对称性: d(x,y)＝d(y,x) 指从x到y的距离等于y到x
的距离
2)
非负性: d(x,y) ≥0 指两点x,y间的距离大于或等于0
3)
三角不等性: d(x,y) ≤d(z,x)十d(z,y)指两个点
利用极差标化欧氏距离
二、马氏距离
马氏距离（Manhattan
distance)，又称为
city-block距离
三、Chebychev（最大）距离
使用在n次实验中两个基因测量值差别最大的
值作为两个基因间的距离。
四、Minkowski距离
明考夫斯基距离是欧氏距离和马氏距离的更
一般形式
当m=1，Minkowski距离即为马氏距离；当
m=2时，Minkowski距离即为欧氏距离。
欧氏距离与马氏距离的区别 欧氏距离，即两项间的差是每个变量值差的平方和 再平方根，目的是计算其间的整体距离即不相似性。 欧氏距离的缺点是将样品的不同属性（即各指标或各 变量）之间的差别等同看待，这一点有时不能满足实 际要求。 马氏距离不受量纲的影响，两点之间的马氏距离与 原始数据的测量单位无关；由标准化数据和中心化数 据(即原始数据与均值之差）计算出的二点之间的马 氏距离相同。马氏距离还可以排除变量之间的相关性 的干扰。它的缺点是夸大了变化微小的变量的作用。
第九章 聚类分析和可视化
Department of Bioinformatics College of Bio-safety Science & Technology Hunan Agricultural University
聚类分析

聚类分析(clustering anaIysis)是基因表达数据 分析最常用的多变量技术，在没有关于数据的 先验知识时，对不同的样本或实验间的相似性 进行研究。
在机器学习的框架内聚类分析又称为非监督学 习方法。 基因表达数据矩阵中，聚类的对象：基因、样 本或序列

ห้องสมุดไป่ตู้
聚类的基础是对象(或称观测个体)间的相似
性(或非相似性)。相似性指标用于度量欲对
其进行聚类的对象之间的相似程度。
聚类就是把相似的个体划分到相同的组别，
而把不相似的个体划分到不同组别的过程。
分割聚类
对于一个给定的微阵列矩阵，分割聚类
(partitioning methods)将把观察个体分为预 定的几部分，使得对个体的分割达到最忧的 客观标准．即类内个体问的相似性达到最大， 而类间的相似性达到最小。最常用的分割算 法为k—means法、k—medoids法和自组织 图。
优点：适合于需要关注不同水平分类细节时
的分类。
系统树图（dendrogram)
相同的系统聚类方法产生的结果确定，分割
法（K-均值聚类）产生的结果不确定。
凝聚法和分裂法
（一）凝聚法：
初始时n个观测个体形成n个类，每个类中包含一个模式(观测 个体)，在每一步中，最相似的两个类进行合并，直到所有的 观测形成一个类。
x,y间的距离小于或等于它们与第三个点z之间的距离和
一、欧氏距离

欧氏距离(Euclidean distance)

平方欧氏距离(squared Euclidean distance)

标化欧氏距离(standardized Euclidean distance)
标化欧氏距离在特定情况下提供较好的结果
1.单联结 2.全联结 3.平均联结 4.质心联结 5.Wald法
系统聚类图（平均联结）
单联结
全联结
（二）分裂法

凝聚算法在系统树的顶部通常并不能较好地反 映数据的结构，因为在顶部阶段时已完成很多 次的合并，而这些类的合并都是建立在前期合 并的基础上，因此，如果早期的合并存在问题， 将影响后面的合并，并且前期的合并是不可逆 的。如果聚类的目标在于把所有观测个体分为 少数几个类，分裂法期望能产生更有判断力、 更灵敏的分割，但是，进行多次分割后的结果 通常也不能给出较好的分类结果。