1、,聚类和分类分析,生物芯片数据分析方法,聚类,一、引言,物以类聚，人以群分。,基于物体的相似性将物体分成不同的组,1.相似性指标,2.聚类算法,二、基因表达谱数据的聚类分析,聚类分析是基因表达数据分析最常用的多变量技术。在没有关于数据的先验知识时，对不同的样本或实验间的相似性进行研究。机器学习：无监督学习。,二、基因表达谱数据的聚类分析,聚类的基础是对象间的相似性。相似性指标用于度量对其进行聚类的对象之间的相似程度。聚类：把相似的个体划分到相同的组别，不同的个体划分到不同组别的过程。,二、基因表达谱数据的聚类,对样本进行聚类（Q型）实验样本的质量控制检查样本是否按已知 类别分组发现亚型对基因进
2、行聚类（R型）识别功能相关的基因识别基因共表达模式,样本,基因,基因表达谱,三、距离尺度函数相似性指标,相似性的计算是取输入空间中的两个点，计算出一个正数，该正数包含了这两个点之间的相似性程度的信息。假定输入空间为n维空间，则两个数据点可以是：两个基因在n个样本中的测量值两个样本在在n个基因上的测量值,三、距离尺度函数相似性的度量,n维空间中的两个点x、y间的距离d具有如下属性：对称性d（x,y）d(y,x)非负性d(x,y)0三角不等性 d(x,y) d(x,z)+ d(z,y),三、距离尺度函数相似性的度量,几何距离线性相关系数非线性相关系数向量间的角度其他,常用的距离度量指标：,（一）几
3、何距离,欧氏距离曼哈顿距离切氏距离广义欧氏距离明氏距离,1.欧氏距离（）,两个n维向量 和 间的欧氏距离的定义： 向量形式：欧氏距离的其他形式：平方欧氏距离：倾向于对异常值给予更大的权重标化欧氏距离：每维上除以相应的变异（如标准差）,利用计算距离,利用计算欧氏距离,pdist函数,利用计算标化欧氏距离,pdist函数D = pdist(X)D = pdist(X,distance),2.曼哈顿距离（Manhattan distance）,两个n维向量 和 间的曼哈顿距离的定义：曼哈顿距离又称城市街区（city-block）距离。,18,在曼哈顿要从一个十字路口开车到另外一个十字路口。,显然不是
4、，除非你能穿越大楼。,驾驶距离是两点间的直线距离吗？,实际驾驶距离就是这个“曼哈顿距离”。,利用计算曼哈顿距离,pdist函数,3.切比雪夫距离（Chebychev distance）,两个n维向量 和 间的切比雪夫距离定义为：,20,1 2 3 4 5,国王走一步能够移动到相邻的8个方格中的任意一个。,54 321,最少步数总是max( | x2-x1 | , | y2-y1 | ) 步。,那么国王从格子(2,4)走到格子(4,1)最少需要多少步？,从（2,3）到（5,5）走几步？,利用计算切氏距离,pdist函数,4.广义欧氏距离（Mahalanobis distance）,设Xi与Xj是
5、来自均值向量为 ，协方差为 的总体G中的p维样品，则两个样品间的马氏距离为：实际应用中，总体协差阵未知可以用样本协差阵来代替。,广义欧氏距离的优点在于：广义欧氏距离又称为马氏距离。马氏距离考虑了观测变量之间的相关性。马氏距离还考虑了观测变量之间的变异性，不再受各指标量纲的影响。将原始数据作线性变换后，马氏距离不变。,利用计算广义欧氏距离,pdist函数,5.明考夫斯基距离（Minkowski distance）,令dij 表示向量Xi与Xj的距离，则明考夫斯基的距离公式为： 其中，当q取不同的值时，又会产生不同的距离。,明考夫斯基距离简称明氏距离，按取值不同又可分成：绝对距离(q=1 ） 曼哈
6、顿距离欧氏距离（q=2 ）切比雪夫距离(q=),明氏距离的不足之处及解决办法：明氏距离没有考虑指标的数量级水平及量纲。当各变量数量级相差悬殊且量纲不同时，采用明氏距离并不合理。解决办法：先对数据标准化，然后用标准化后的数据计算距离。使用欧氏距离要求各坐标对欧氏距离的贡献是同等的且变差大小也是相同的。这样的欧氏距离才合适，效果也较好，否则就不能如实的反映情况。解决办法是对坐标加权，产生“统计距离”。,利用计算明氏距离,pdist函数,（二）线性相关系数,皮尔森相关系数： 其中， 为基因向量x的期望值， 为x的标准差； 为基因向量y的期望值， 为y的标准差； n为向量的维数。皮尔森相关距离：1-r
7、，取值在0-2之间。,皮尔森相关系数主要考虑坐标变化的一致性（对应坐标同时增加或减少）；若向量代表特定实验条件的基因的测量值时，当基因在两个实验中的值以相同的方式变化时，即使改变的大小有很大的不同，这两个实验的Pearson相关系数也会很高。,皮尔森相关系数,皮尔森相关系数有正负号，分别表示正相关和负相关的基因表达关系。正相关,皮尔森相关系数,皮尔森相关系数有正负号，分别表示正相关和负相关的基因表达关系。负相关,利用matalb计算Pearson相关距离,三、非线性相关系数,某些在功能上有相关关系的基因虽然在表达上不具有严格的线性相关关系，但是在时间点的波动趋势上却是相似的。,三、非线性相关系
8、数,两个n维向量间的非线性相关关系模式可以用斯皮尔曼相关系数进行衡量。把 、 分别用它们在x和y中秩次代替，那么x和y相应的秩次之间的相关系数即为Spearman秩相关。其中，d为每对观察值 、 的秩次之差。,利用matalb计算SPearmon相关距离,四. 向量间角度（夹角余弦）,两向量间的角度又称cosine相关系数。两个n维向量间的角度距离为： 其中，分子为两个向量的点积，坟墓为两个向量模的积。,利用matalb计算夹角余弦,六.其他,互信息协方差点积,距离选择的原则,通常选择距离公式应注意遵循以下的基本原则：要考虑所选择的距离公式在实际应用中的意义。要综合考虑对样本观测数据的预处理和
9、将要采用的聚类分析方法。要考虑研究对象的特点和计算量的大小。,40,四、聚类的类型,层次聚类又称系统聚类：连接相似的基因，将所有的基因建成一颗树。K-均值 - 将基因划分到预先设定的K个组里自组织映射(SOM)主成分分析,层次聚类算法将研究对象按照它们的相似性关系用树形图进行呈现，进行层次聚类时不需要预先设定类别个数，树状的聚类结构可以展示嵌套式的类别关系。,(一)层次聚类,层次聚类-类间距离度量,在对含非单独对象的类进行合并或分裂时，常用的类间度量方法：,层次距离-类间距离度量,最小距离：倾向于形成链状的类，仅仅一个小的距离就能使两个差异很大的类融合到一起，因此形成的类呈现出长的链状。最大距
10、离：当数据在多维空间中形成自然分割的数据团时，最大距离通常能取得较好的分析结果，形成紧凑的类平均距离：该方法对于自然分开的类、伸长的甚至链状的类都能得到较好结果，对未知分布的数据具有较稳定的聚类结果。质心法：通常能更好地反映数据的真实结果特征，但是计算速度很慢。,平均距离 最大距离 最小距离,层次聚类,根据层次的形成方式，可以分为凝聚法：自底向上，首先将每个对象作为单独的一个类，然后不断合并相近的对象。分裂法：自顶向下，一开始将所有对象置于一个类中，然后一个类被不断地分裂为更小的类。,2000年Alizadeh等运用基因芯片数据，基于层次聚类算法证实了DLBCL肿瘤病人在mRNA层面确实存在两
11、种亚型。,凝聚法层次聚类的基本思想是：初始时n个观测对象形成n个类，每个类中包含一个对象（ （基因或样本，由应用目标决定），然后距离相近（最相似）的先聚成类，距离相远的后聚成类，过程一直进行下去，每个样品（或变量）总能聚到合适的类中。,凝聚法聚类过程是：假设总共有n个样品（或变量），首先将每个样品（或变量）独自聚成一类，共有n类；然后根据所确定的样品（或变量）“距离”公式，形成初始距离矩阵。之后，将其中距离较近的两个样品（或变量）聚合为一类，其它的样品（或变量）仍各自聚为一类。第二步再根据新合并类与其他类的“距离”计算公式，在形成的新的距离阵中，将“距离”最近的两个类进一步再聚成一类；以上步骤
12、一直进行下去，最后将所有的样品（或变量）全聚成一类。,凝聚法层次聚类,层次聚类法有8种，分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法。它们的归类步骤基本上是一致的，主要差异是：两类间距离；新合并类与其他类间距离的计算方法不同。,51,1、最短距离法,欧氏距离+最小距离设有四个样本A、B、C、D，每个样本自成一类。,1、最短距离法,欧氏距离+最小距离 A与D距离最小，首先合并A和D：,AD,欧氏距离+最小距离 重新计算每类之间的距离：,1、最短距离法,欧氏距离+最小距离,1、最短距离法,欧氏距离+最小距离,1、最短距离法,欧氏距离+最小距离,1、
13、最短距离法,2. 中间距离法,在定义类与类之间的距离时采用介于两者之间的距离的聚类方法称为中间距离法。设将类Gp与Gq类合并为类Gr，然后计算任意的类Gk和Gr的距离：若DkqDkp：如果采用最短距离法，则Dkr = Dkp，如果采用最长距离法，则Dkr = Dkq。而中间距离法是取它们（最长距离与最短距离）的中间一点作为计算Dkr的根据。,中间距离法取最短距离与最长距离的中线，则由初等几何可知这个中线的平方为：由于此公式中出现的全是距离的平方，所以为了计算的方便，距离矩阵的元素也可以都为平方。,2. 中间距离法,上述八种系统聚类法的步骤完全一样，只是距离的递推公式不同。兰斯（Lance）和威
14、廉姆斯（Williams）于1967年给出了一个统一的公式，即将Gp和Gq合并为新类Gr，类Gk与新并类Gr的距离公式为： 其中ap、aq、 、 是参数，不同的系统聚类法，它们取不同的数。,60,61,系统聚类法参数表,聚类树的分割,系统聚类树可以用于分割数据，分割的类数由用户确定。分割的方法为：在树的一定深度上（从根部开始的距离）进行切割，不同深度的切割产生不同的分类结果。,3 clusters?,2 clusters?,层次聚类,确定类别个数？指定类别数相似性阈值,如何比较不同聚类方法的聚类结果？,不同聚类方法产生的系统树图间存在差异。常用的方法：在固定分类的情况下比较不同方法聚类结果的一
15、致性。假定有两个系统树，把两棵树都进行切割，把对象分成K类。两棵树的相似性可以定义为在一棵树中分到相同的类中而在另一个棵树中分到不同的类中的所有的配对观测对象的比例。,层次聚类在基因芯片实验中的应用,Step1: 建立Gene-experiment矩阵,每一列是不同的组织，或者在不同条件下的样本，每一行是基因的编号，每个基因的表达量用标准化后log2R/G的表示,Step2 计算所有基因之间的相关距离,基因的相似分值（similarity score)可以由Pearsons correlation公式计算：,Goffset 一般取标准化后的中位数或平均值；等于0，即log2R/G=0,表示表达
16、无差异。,层次聚类,Pearsons 相关的例子,Step3 建立Gene-Gene的距离矩阵,根据Gene-Gene 的距离矩阵的分值，首先找到距离最近的两个基因，然后合并，再找距离相近两组再合并，直到所有的基因合并到一个组中。,Step4 建立系统发育树（dendrogram),-log2（D）,Step5 建立表达图谱,绘制表达谱图时，log 值为正，用红色表示，越大红色越亮，基因表达的水平越高，受到的诱导（induced）越强；log 值为负则用绿色表示，越小绿色越亮，基因表达的水平越低，受到的抑制(depressed)越强,系统聚类是目前基因聚类中最常用的的方法之一。因为它她仅需要确
17、定类的合并类的合并规则和和相似性度量指标，且得到的系统树图便于对基因的相似性进行评价。主要缺点：基因的分类树需要用户确定，且当相似矩阵较大时计算量大。在基因表达应用的背景下，进行较为复杂的聚类分析前，应尽可能减少感兴趣的基因数量，以降低计算复杂度。,系统聚类法一次形成类以后就不能改变了，这就要求一次分类分得比较准确，对分类的方法就提出较高的要求，相应的计算量自然也比较大。如Q型系统聚类法，聚类过程是在样品间的距离矩阵基础上进行的，而且在并类过程中，需要将每类样品和其他类样品间的距离逐一加以比较，以决定应合并的类别，因此当样本容量很大时，需要占据足够大的计算机内存空间和计算时间。基于这种情况，产
18、生了动态聚类。,利用matlab进行层次聚类,利用matlab进行层次聚类,首先计算距离以欧式距离为例,利用matlab进行层次聚类,层次聚类函数linkage：Z = linkage(X),前两列是索引下标列，最后一列是距离列。第三和第六个基因首先聚成一类，它们的距离为0.1671可利用dendrogram来显示聚类图。,利用matlab进行层次聚类,利用matlab进行层次聚类,(二)k均值聚类,基本思想,K-Means Clustering K-均值聚类方法,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2任意选择K 个目标作为初始的类中
19、心,将每个目标分配给与其最相似的类中心,更新类中心（均值）,重分配,更新类中心（均值）,动态聚类法又称为逐步聚类法，其基本思想是：开始先粗略地分一下类，然后按照某种最优的原则修改不合理的分类，直至类分得比较合理为止，这样就形成一个最终的分类结果。该方法具有计算量较小，占用计算机内存空间较少，方法简单，适用于大样本的Q型聚类分析。,81,K均值法和系统聚类法一样，都是以距离的远近亲疏为标准进行聚类的。但是两者的不同之处也是明显的：系统聚类对不同的类数产生一系列的聚类结果，而K均值法只能产生指定类数的聚类结果。,【例5.3】假定我们对A、B、C、D四个样品分别测量两个变量,得到结果见下表。试将以上
20、的样品聚成两类。,第一步：按要求取K=2，将这些样品随意分成两类，比如（A、B）和（C、D），然后计算这两个聚类的中心坐标，见下表所示。 其中，表中的中心坐标是通过原始数据计算得来的，比如（A、 B）类的中心坐标为 等等。,(2，2),(-1，-2),第二步：计算某个样品到各类中心的欧氏平方距离，然后将该样品分配给最近的一类。先计算A到两个类的平方距离：由于A到（A、B）的距离小于到（C、D）的距离，因此A不用重新分配。计算B到两类的平方距离：,由于B到（A、B）的距离大于到（C、D）的距离，因此B要分配给（C、D）类。同样，C到到（A、B）的距离大于到（C、D）的距离,D 到到（A、B）的距
21、离大于到（C、D）的距离，因此C、D不用重新分配。得到新的聚类是（A）和（B、C、D）。更新中心坐标如表所示。,K 均值聚类与分层聚类有本质的区别，首先要估计出将要分出几个类，然后将全部的基因按照相似性的距离，归入这几类中。,K 均值聚类在基因芯片实验中的应用,首先也是要先将gene-expriments 矩阵转化成gene-gene distance 矩阵，但是计算基因的相关系数的方法与分层聚类有所不同，用欧及里距离(Euclidean distance)公式计算：d(X,Y)= X，Y 为两个基因,K 均值聚类在基因芯片实验中的应用,然后，将所有的基因随机的分配到K 类中，计算出每个类中的
22、基因的均值，然后，将每个基因分配到均值与它最相近的那个类中。重复以上两个步骤，直到所有的基因都被分配到类中。,K 均值聚类在基因芯片实验中的应用,K 均值聚类在基因芯片实验中的应用,Step 1: 假设基因表达模式的距离为基于距离矩阵的二维空间中的变量,Step 2: 随机选择第一个类中心（质心，红色），然后通过寻找与已选择的类中心最远的数据点来确定下一个类中心。本例中, k=3。,K 均值聚类在基因芯片实验中的应用,91,K-means clustering algorithm(continued),Step 3: 每一个点被分配到与其最近的类中心,Step 4: 重新计算每一个类的质心，通
23、过最小化类内每个点与质心的距离平方和来移动质心、计算下一个类中心,K-means clustering algorithm(continued),重复步骤3、4、5直至质心不变或变化很小。,Step 5: 重复步骤3和4，获取新的替代质心,利用matlab进行k-均值聚类,IDX = KMEANS(X, K),利用matlab进行k-均值聚类,(三)自组织映射聚类,基本思想：在不断的学习过程中，输出层的神经元根据输入样本的特点进行权重调整，最后拓朴结构发生了改变,3、自组织映射聚类(SOM),自组织映射聚类(Self-Organizing Map, SOM)，是由T.Konohen 于1980
24、 年提出的模型，属于非监督学习的神经网络聚类，与K-means 相似，采用SOM 聚类算法之前，也要首先估计出想要得到的类的个数。在SOM 神经网络中，输出层的神经元是以列阵的方式排列于一维或二维的空间中的。根据当前输入向量与神经元的竞争，利用欧氏距离，寻找最短距离当作最有效神经元，以求得调整向量神经元的机会，而其他神经元也可以彼此学习。而最后的神经元就可以根据输入向量的特征，以拓扑结构展现于输出空间中。,四 主成分分析算法（PCA）,能把复杂的数据集转换为比较简洁的数据集。PCA可以降低数据集的多维空间，从而能将数据集在2维图或3维图上表现出来，以至于能从中找到类中对象之间的相互关系。,(五)双向聚类,双向聚类就是识别基因表达谱矩阵中同质的子矩阵，运用特定的基因子类识别样本子类。,层次聚类,采用嵌套式基因和疾病两个方向的循环搜索，识别疾病亚类及导致疾病亚类发生的对应基因簇,双向聚类局部相似性识别出特定条件子集中表达模式一致的基因类单向聚类算法不允许基因或条件属于多个相互重叠的类,
