[PPT模板]ppt聚类分析.ppt

第五组计11 曾建强 芯片数据的 聚类分析 芯片数据的聚类分析 一、聚类的含义 二、距离、相似函数 三、分层聚类 四、K-means聚类 五、聚类结果的可视化 一、聚类的含义 聚类分析起源于分类学，在古老的分类学 中，人们主要依靠经验和专业知识来实现分类 ，很少利用数学工具进行定量的分类。 随着人类科学技术的发展，对分类的要求 越来越高，以致有时仅凭经验和专业知识难以 确切地进行分类，于是人们逐渐地把数学工具 引用到了分类学中，形成了数值分类学，之后 又将多元分析的技术引入到数值分类学形成了 聚类分析。 一、聚类的含义 聚类分析内容非常丰富，有系统 聚类法、动态聚类法、有序样品 聚类法、模糊聚类法、图论聚类 法、聚类预报法等。 一、聚类的含义 生物芯片数据聚类是指根据基因片的基因 表达数据，将基因按照不同的功能，或者相同 的表达行为进行归类。 聚类的基因表达谱为研究人员提供基因表 达差异，启动子分析，表达模式研究等等便利 的条件。目前已经有很多种聚类的方法应用到 基因芯片的研究当中，如分层聚类、K 均值聚 类(K-means clustering)、自组织图谱SOM 、 PCA等等。 二、距离和相似函数 二、距离和相似函数 1、距离 变量的测量尺度不同，聚类的结果 也不同 在生物芯片数据分析（基因表达数 据分析）中，我们一般考虑间隔尺 度变量，即基因数据间的“距离” 。 二、距离和相似函数 二、距离和相似函数 距离有多种定义方法，在聚类分析中最常用的是欧 氏距离，即有 当各变量的单位不同或测量值范围相差很大时，应 先对各变量的数据作标准化处理。最常用的标准化 处理是，令 其中 和 分别为第 个变 量的样本均值和样本方差。 一、最短距离法 定义类与类之间的距离为两类最近样品间的距离， 即 最短距离法的聚类步骤 (1) 规定样品之间的距离，计算 个样品的距离矩阵 ，它是一个对称矩阵。 (2) 选择 中的最小元素，设为 ，则将 和 合 并成一个新类，记为 ，即 (3) 计算新类 与任一类 之间距离的递推公式为 最短距离法的聚类步骤 在 中， 和 所在的行和列合并成一个新行新列 ，对应 ，该行列上的新距离值由（6.3.2）式求得 ，其余行列上的距离值不变，这样就得到新的距离 矩阵，记作 。 (4) 对 重复上述对 的两步得 ，如此下去直 至所有元素合并成一类为止。 如果某一步 中最小的元素不止一个，则称此现象 为结(tie)，对应这些最小元素的类可以任选一对合并 或同时合并。 二、最长距离法 类与类之间的距离定义为两类最远样品间的距离， 即 二、距离和相似函数 2、相似函数 聚类分析方法不仅用来对样品进行分类，而且可用来对 变量进行分类，在对变量进行分类时，常常采用相似系 数来度量变量之间的相似性。 变量之间的这种相似性度量，在一些应用中要看相似系 数的大小，而在另一些应用中要看相似系数绝对值的大 小。 相似系数(或其绝对值)越大，认为变量之间的相似性程 度就越高；反之，则越低。 聚类时，比较相似的变量倾向于归为一类，不太相似的 变量归属不同的类。 二、距离和相似函数 相似函数一般满足的条件 （1） ，当且仅当 和 是常数； （2） ，对一切 ； （3） ，对一切 。 最常用的两个相似系数 三、分层聚类法 三、分层聚类法 分层聚类法即系统聚类法 系统聚类法是聚类分析诸方法中用得最多的一种。 基本思想是：开始将个样品各自作为一类，并规定样品之间的 距离和类与类之间的距离，然后将距离最近的两类合并成一个新类， 计算新类与其他类的距离；重复进行两个最近类的合并，每次减少一 类，直至所有的样品合并为一类。 常用的系统聚类方法： 一、最短距离法 二、最长距离法 三、中间距离法 四、类平均法 五、重心法 六、离差平方和法(Ward方法) 三、分层聚类法 1、 分层聚类(Hierarchical clustering) 分层聚类是最早也是最普遍的应用在基因芯片 数据分析研究中的聚类算法。步骤如下： （1） 建立Gene-experiment 矩阵 每一列是不同的组织，或者在不同条件下的样 本，每一行是基因的编号，每个基因的表达量 用标准化后log2 R /G 的表示。 三、分层聚类法 （2） 计算所有基因之间的相关系数correlation coefficient。 基因的相似分值（similarity score）可以由 Pearsons correlation 公式计算 三、分层聚类法 (3) 建立Gene-Gene 的距离矩阵 三、分层聚类法 (4)建立系统发育树（dendrogram） 根据Gene-Gene 的距离矩阵的分值，首先找到距离最近的两 个基因，然后合并，再找距离相近两组再合并，直到所有的 基因合并到一个组中 三、分层聚类法 (5)建立表达图谱 四、K-均值聚类法 四、K-中值聚类法 K-均值聚类是动态聚类的一种 动态聚类法的基本思想是，选择一批凝聚点或给 出一个初始的分类，让样品按某种原则向凝聚点 凝聚，对凝聚点进行不断的修改或迭代，直至分 类比较合理或迭代稳定为止。类的个数k可以事 先指定，也可以在聚类过程中确定。 K means 聚类与分层聚类（系统聚类）有本质 的区别，首先要估计出将要分出几个类，然后将 全部的基因按照相似性的距离，归入这几类中 四、K-中值聚类法 1967 年,MacQueen 首次提出了K均值聚类算法(K- means 算法).迄今为止,很多聚类任务都选择该经典 算该算法的核心思想是找出K 个聚类中 C1,C2,Ck,使得每一个数据点xi 和与其最近的聚 类中心Cv的平方距离和被最小化(该平方距离和被 称为偏差D). 四、K-中值聚类法 具体操作： K 均值(K-means)聚类算法(对n 个样本进行聚类) 1初始化. 随机指定K 个聚类中心(C1,C2,Ck); 2分配xi. 对每一个样本xi,找到离它最近的聚类中心 Cv,并将其分配到Cv所标明类; 3修正Cw. 将每一个Cw移动到其标明的类的中心; 4计算偏差. 5D 收敛?. 如果D 值收敛,则return(C1,C2,Ck)并 终止本算法;否则,返回步骤K2. 四、K-中值聚类法 首先也是要先将gene-expriments 矩阵转化成gene- gene distance 矩阵，但是计算基因的相关系数的方法 与分层聚类有所不同，用欧及里距离(Euclidean distance)公式计算： 然后，将所有的基因随机的分配到K 类中，计算出每 个类中的基因的均值，然后，将每个基因分配到均值 与它最相近的那个类中。 重复以上两个步骤，直到所有的基因都被分配到类 中。 K-means聚类过程 2、聚类分析 K-means聚类图示 的最后结果 图中彩色小圈代表测 得的数据，红点（数 字110）为选择的 初始凝聚点。 四、K-中值聚类法 五、聚类结果的可视化 五、聚类结果的可视化 五、聚类结果的可视化 分层聚类结果。红色标记的样本代表肿瘤病人，从结果中可以明显辨 别出该类型肿瘤分为两类。预示着该肿瘤可能为两个亚型。 五、聚类结果的可视化 对微阵列基因表达谱的聚类分析得到的一般是 基因的分组信息，如何进一步了解同组基因的 表达谱差异？或者，不同组基因之间是否存在 相似关系？哪些基因是上调或下调？幅度多大 ？ 而数据对于大多数人来说太抽象了 五、聚类结果的可视化 在数据挖掘中，可视化方法可以发现数据中的 固有结构，因为人眼和大脑具有强大的结构探 索能力。 通过可视化方法，利用人脑这部最强大的计算 机，发挥人在模式处理方面的特殊能力，从而 筛选数据、寻找数据关系 五、聚类结果的可视化 1、彩色盒图 基因表达谱的数据特点 五、聚类结果的可视化 2、树状图 系统发生分析 五、聚类结果的可视化 以分层聚类为例 芯片数据的聚类分析 OVER，THANKS