基因表达谱聚类分析
[ 文章来源：| 文章作者：| 发布时间：2006-12-21| 字体：[大中小] 学习过程可以采用从全局到局部的策略。采取这种策略时，学习初期可设定较大的交互作用半径R ，随着学习过程的不断推进，逐步减小R ，直至不考虑对邻近单元的影响。邻域的形状可以是正方形或者圆形。
KFM 的聚类结果与K 均值相似，它的优点是自动提取样本数据中的信息，同时也是一种全局的决策方法，能避免陷入局部最小，缺点在于必须实现人为设定类的数目与学习参数，而且学习时间较长。KFM 方法克服了K- 均值聚类的一些缺点：它应用类间的全局关系，能提供大数据集内相似性关系的综合看法，便于研究数据变量值的分布及发现类结构。而且，它具有更稳健更准确的特点，对噪声稳定，一般不依赖于数据分布的形状。
8.4.2.5 其它聚类方法
聚类方法是数据挖掘中的基本方法，数据挖掘的方法很多，在基因表达谱的分析中，除了以上常用方法外，还有一些其它的方法。由于对聚类结果尚没有一种有效的方法进行评价，尤其是对聚类结果的进一步生物学知识发现尚没有新的分析思路和成功应用，因此，科学家们在不断地研究一些新方法。这些方法有不同的原理，能够提取不同数据特征，有可能对具体的数据得到更有意义的结果，发现更多的生物学知识。这里，简单介绍这些方法的原理，更详细的介绍请参看相关文献。
(1)模糊聚类分析方法:这是一种模拟人类的思维方法，通过隶属度函数来反映某一对象属于某一类的程度。基本思路是计算两两基因表达谱之间的相似性程度，构建模糊相似矩阵，利用模糊数学中的传递闭包计算方法得到模糊等价矩阵，选择不同的置信水平从模糊等价矩阵中构建动态聚类图。对于特定的置信水平，可以实现对基因表达谱的分类。该方法的优点是利用了模糊数学中的隶属度概念，能够更好的反映基因表达谱之间的相互关系，而且它是一种全局的优化方法，与向量的顺序无关。
(2)模糊C均值算法:该方法同样将模糊数学中的隶属度概念引入到常用的K 均值聚类方法中。对于K 均值算法，一个基因表达谱所属的类只有一个，因此，它与各类别的关系要么是 1 ，要么是0 ，即属于或不属于某一类。而对于模糊 C 均值法，一个基因表达谱是否属于某一类，是以隶属度来确定第i 个样本属于第j 类的可能性。最终的聚类结果取决于分析的目的，可以根据最大隶属度来确定基因表达谱的分类，即一个基因表达谱只属于一类；但往往是确定隶属度的阈值，只要大于该阈值，就可以将基因表达谱划分为该类，这样的划分结果是一个基因表达谱可以属于多个类，这也是可以被生物学家接受的。模糊 C 均值法与K 均值法的实现过程基本相同，所不同的是对于
模糊 C 均值法并不是直接将样本向量归类，而是计算属于各类别的隶属度；同样它没有一个明确的类界限，在计算聚类中心时，需要考虑所有的样本向量，根据隶属度μ来计算聚类中心。
(3)谱聚类:K 均值聚类对于聚类中心相距较远的数据样本具有很好的聚类效果，而对于具有同心圆特征的数据样本很难得到好的分类效果，而谱聚类（Spectral clustering ）能够很好的对具有这种特征的样本进行聚类。谱聚类是一种基于矩阵特征向量的方法，也是一种能根据顶点之间的权值对图进行划分的方法。用图表示基因表达谱矩阵，基因表达谱可以看作是一组顶点，连接顶点的边的权值反映了两个表达谱之间的相似性，这样就得到有权无向图G(V ，
A) ，聚类过程等价于将G 划分为不连接的子集，这可以通过简单地删除连接边来实现。聚类过程包括两个步骤：第
1 步是将表达谱空间转化为相似度矩阵的特征向量空间；第
2 步是应用简单的K 均值法对特征向量空间的特征向量进行聚类，得到的结果就对应了基因表达谱的聚类结果。该方法可以根据特征值自动确定分类数目。谱聚类在聚类过程中进行了特征空间的转换，可以将大的空间转化为较小的空间，从而可以更快速地处理大规模的数据。
(4)超顺磁性聚类:超顺磁性聚类（superparamagnetic clustering ）是一种基于模拟非均匀铁磁物质的物理特性的聚类方法，将数据聚类问题视为检验不均匀Potts 模型的平衡特性。根据表达谱向量之间的距离矩阵构建图，顶点是数据点，如果两个点之间的距离满足K-mutual-neighbor 准则，则称为邻居。数据点的聚类等价于有权图的划分。给每一数据点分配一个Potts 自旋子，相邻数据点间引入强度随距离下降的相互作用函数。非均匀Potts 模型系统随温度变化表现出三相：在低温下，所有自旋子呈现完全有序的排列，系统为铁磁相；随着温度的升高，小区域自旋子形成磁化“颗粒”，附属于同一“颗粒”者相互间产生强耦合，而无关者间相互作用很弱，不同“颗粒”的排列呈无序状态，为超顺磁相；在高温下，系统不表现任何有序性，为顺磁相。在超顺磁相的转换温度下，磁化率表现出显著的峰值。原则上，超顺磁相可以有一系列的转换点。随着温度的升高，系统可以首先分裂为两类，其中每一类又可以分裂为更多的子类，这样，数据就分层组织为类。超顺磁性聚类算法的优点是对噪声及初始化不敏感，因为类由系统的综合性质产生。由磁化率的峰值很容易鉴别主要的分界，从而能清楚显示类的构成和分界，并且在每一个分辨率上能自动确定类数。
(5)双向聚类法:以上所述方法主要是对基因表达谱进行聚类，或针对基因表达矩阵的行进行聚类分析，将具有相似模式的基因表达谱分为一组，这是在应用中要解决的主要问题。基因表达数据矩阵中的列表示了实验条件，可以是时间序列，也可以是不同的肿瘤样本或病人样本。从生物学应用的角度，针对列的聚类可以发现各实验条件之间的相互关系，例如，同一肿瘤类型的样本可以聚成一类，它们具有相似的基因表达模式，这样就可以基于表达谱对肿瘤进行分类。从数学的角度，数据矩阵中的每一列对基因表达谱的行聚类结果有着不同的影响，挑选部分列进行聚类的结果与选择所有列进行聚类的结果是不同的。将两者结合起来，就称为双向聚类法，在行和列两个方向上进行聚类分析，
通常采用贪婪迭代检索的方法来发现子矩阵或稳定的类，这些子矩阵中感兴趣的模式具有特定的生物学意义。在应用中，可以根据具体的目的，确定以降低基因维数还是以降低样本维数为主，通过迭代得到稳定的若干样本分类或基因分组。
8.4.3 基于模型的聚类方法
在基因表达数据显著性分析时，我们提到贝叶斯方法的应用，它分别对两种条件下的数据构建模型，通过比较它们的模型参数来确定表达差异的显著性。同样，基因表达谱分析也可以引入建模的方法，假定每一个基因表达谱是由一种内在的概率模型产生的，它满足一定概率分布或者分布的有限组合，例如多元正态分布，而所有的基因表达谱是由若干个概率模型混合产生的，这样就可以通过确定这些概率模型，来实现对基因表达谱聚类的目的。高斯混合模型是该聚类方法中的常用模型。与上面所述的各种启发式聚类算法比较，基于模型的方法具有的最大优点是，不需要使用严格的方法来确定类的数目或最佳的聚类方法，但是不足是计算量非常大，对于大量数据的分析比较困难。
基于混合模型的聚类，首先假设数据中蕴含的每一类样本由一种内在的概率分布混合产生，例如高斯混合模型，独
立多元观测y1，y2，… ，y n组成的数据Y中每一元素y k由参数为u k（均值向量）和Σk（协方差矩阵）的多元正态分布模拟，
（8-24）
式中的det是求矩阵行列式值的函数。算法的目标是由数据预测参数u k和Σk并确定相应于这些参数预测的类。为了便于参数预测，对Σk进行特征值分解：，D 为特征向量组成的正交矩阵，确定模型的取向，A为对角矩阵，元素与Σk的特征值成正比，确定模型的形状λ为标量，确定模型的体积。约束和改变部分参数，可以得到这一概率框架下的一组模型，如, 等体积球模型（EI ：，I 为单位矩阵）、不等体积球模型(VI: ) 等，以适应数据特征的变化。模型参数可以通过EM （期望最大化）方法估计。每一种协方差矩阵与类数组合情况相应于不同的概率模型，由贝叶斯信息准则(BIC) 估计每一种模型下数据被观测到的概率，计算模型的BIC 得分，最后选择BIC 得分最大的模型和参数对该样本进行分类。
8.4.4 支持向量机
如上所述，对于基因表达谱数据矩阵M，在对行或列向量进行聚类分析时很少或根本没有用到生物学知识，所得到
的结果是否具有生物学意义，还需要进一步的分析。然而，对于特定的数据矩阵，都有特定的生物学背景，例如，基因之间存在相关性，可以分成若干功能类，样本之间也存在某种关系，可能来自患有相同肿瘤的病人。将这些知识应用于聚类方法中，挑选部分样本作为训练样本，可以提取特征构建分类器，然后对其它的样本进行分类，实现聚类的目的。这种方法称为有监督学习方法，支持向量机（support vector machine ，SVM ）就是这样一种从少量样本中提取分类信息的机器学习方法。因为SVM 仅仅需要少量样本，而实现对大量样本的分类，这与分类问题中通常有明确类别存在的情况下对未知类别进行分类是不同的，所以，在这里将它作为一种聚类方法进行介绍。
统计学习理论是目前针对小样本统计估计和预测学习的最佳理论，它从理论上较系统地研究了风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系以及如何利用这些理论找到新的学习原则和方法等问题。支持向量机是实现统计学习理论思想的具体方法，可以用于解决小样本、非线性及高维学习问题，不需要足够的样本来构建特征空间，而仅仅需要少量的样本来构建分类界面，这些用来构建分类界面的样本就称为支持向量。
考虑图8.4 所示的二维两类线性可分情况，图中实心点和空心点分别表示两类训练样本点，分类线H 能把两类正确地分开，H 1 ，H 2 平行于H ，并且分别为两类样本中离分类线H 最近的点，H 1 、H 2 之间的距离叫做两类的分类空隙或分类间隔，最优分类线就是要求分类线不但能将两类正确地分开，同时要求使两类的分类空隙最大，从而使真实风险最小。对于高维空间，最优分类线就成为最优分类面。
假设线性可分样本集为是类别标号，则分类判别函数为, 分类面方程为。将判别函数归一化，使两类所有样本都满足，即使离分类面最近的样本的判别值为 1 ，这样分类间隔=2/。要使间隔最大，必须使最小，要求分类线对所有样本能正确分类，就要求它满足：
（8-25）
因此，满足上述条件且使最小的分类面就是最优分类面。过两类样本中离分类面最近的点且平行于最优分类面的超平面H 1 ,H 2 上的训练样本就是使等号成立的那些样本，即支持向量。
那么，如何求最优分类面？根据上述讨论，最优分类面问题可以表示成在条件（8-25 ）的约束下，求函数
的最小值。为此，可以构建Lagrange 函数
（8-26）
其中>0，为Lagrange 系数，问题转化为对w和b求Lagrange函数的极小值，分别对w和b求偏微分并令它们等于0，在约束条件
（8-27）
之下，对求解下述函数的最大值，
(8-28)
若为最优解，则，即最优分类面的权系数向量是训练样本向量的线性组合。
求解上述问题后得到的最优分类函数是:
(8-29)
sgn() 为符号函数。由于非支持向量对应的均为0 ，因此，式中的求和实际上只对支持向量进行，而是分
类的阈值，可以由任意一个支持向量求得，或通过两类中任意一对支持向量取中值求得。从最终的分类判别函数中可以看到，只含有待分类样本与训练样本中的支持向量的内积运算。
对于两类情况的分类，就是要构建最优分类面或超平面。对于大多数真实世界的问题，包含不可分的数据，也就是在数据空间中不存在一个超平面可以成功的区分两类样本。一个解决办法是将数据映射到更高维的空间，在那里定义一个可分隔的超平面。这个更高维的空间称为特征空间，而对应的训练样本所在的空间叫输入空间。问题就成为如何选择一个足够维度的特征空间，使得训练数据可分。
SVM 的基本思想是首先通过非线性变换将输入空间变换到一个高维的特征空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当的内积函数实现的。用于超平面分类点的决策函数仅仅包含特征空间中点之间的点积，因此寻找特征空间中可分隔超平面的算法完全可以用输入空间中的向量和特征空间中的点积来陈述。SVM 能够定位超平面，不需要明确地表示特征空间，只需要简单地定义称为核心函数的函数K ，它在特征空间中起着点积的作用，这个技术避免了明确表示特征向量的计算负担。
SVM 的判别函数为：
(8-30)
一些简单的核心函数有多项式形式的内积函数（8-31 ）和核函数型内积（8-32 ）
(8-31)
(8-32)
是高斯宽度，等于正样本与最近负样本间欧氏距离的中值，得到的SVM 是一种径向基函数分类器。
8.4.5 聚类结果的可视化
对微阵列基因表达谱的聚类分析得到的一般是基因的分组信息和基因表达谱的相互关系，如何进一步了解同组基因的表达谱差异？不同组基因之间是否存在相互关系？哪些基因是上调或下调的？幅度变化有多大？在何种条件下发
生较大的变化？这些问题是生物学家普遍关注的问题，需要通过简单、直观的方法来给出这些答案。数据对于大多数人来说太抽象了，而文字的描述又难以反映数据的本质，采用可视化的方法可以大大方便对表达谱分析结果的理解，
有利于对这些问题的回答。
在数据挖掘中，可视化方法可以用来发现数据中的固有结构，这是因为人类的眼睛和大脑具有强大的结构探测能力——这是长期进化的成果。可视化方法就是以各种可以发挥出人类在模式处理方面的特殊能力的方式来显示数据。可视化方法在数据挖掘中占有非常重要的地位，它是筛选数据寻找未知数据关系的理想方法。可视化方法是生物信息学中常用的一种表示和发现生物学知识的方法，典型的例子有蛋白质三维构象的显示、转录因子DNA 结合位点一致序列的logo 表示、基因调控网络的图形表示等。
基因表达谱的数据特点是基因数目多，样本少，而每一个数据点所表示的是基因在特定条件下的表达数据，经过数据预处理后，往往是与参考样本表达水平的比值的对数值，负值表示基因表达水平的下调，正值表示上调，值的绝对值反映了变化的幅度。因此，对于表达谱数据及其聚类结果通常用两种方式表示。
第一种可视化表示方式是彩色盒图和树状图(dendrogram) 。所谓的彩色盒图是用不同的颜色小方盒来表示基因表达谱数据，一个小方盒表示一个数据，绿色表示数据小于0 ，红色表示数据大于0 ，相对应的生物学意义是对应的基因在相应的条件下是上调还是下调，而颜色的深浅反映了数据的绝对值大小。基因表达谱的很多聚类结果是以树状图的形式表示的，例如，对于层次聚类法、模糊聚类等方法，这些结果的可视化是通过树状图和彩色盒图相结合表达的（如图8.5 （ a ）所示）。树状图是系统发生分析中常用的物种进化关系的表示方法，在这里反映了基因表达谱之间的关系，通过不同层次的剪枝，可以得到不同的基因子集。树状图和彩色盒图的结合，可以很好地反应具有不同表达特征的基因之间的相互关系，例如，对于细胞周期的基因表达检测，可以很方便地知道哪些基因是周期性表达的，它们的表达高峰分别在哪一个时期等。从这种方式的表示中，可以方便地发现相关的基因，并对它们进行深入的分析。对于k 均值、SOM 等聚类方法得到的结果也可以用彩色盒图表示，分在同一组的基因安排在一起，也能基本反映基因表达谱之间的相互关系。该方法的局限性在于基因的数量很大，很难对全部基因进行同时的细节观察。
第二种可视化表示方式是点线图。在直角坐标系的第一象限中用点表示基因表达数据，并用线将相邻的点连接起来。这样，一条曲线就表示了一个基因在不同条件下的表达水平，对于时间相关的数据，可以在一定程度上反应基因的动力学行为。对表达谱聚类分析后，得到的每一个基因子集可以在一个图中显示出来，如图8.5（ b ）所示。点线图比盒形图更能直观地表示基因的表达水平和不同基因在相同条件下的差异。
可视化方法对于基因表达谱聚类结果的理解非常重要，对于生物学家分析和理解生物学意义具有不可替代的作用。除了上述两种主要的表示方法外，还有一些方法可以直观地根据表达谱数据显示基因之间的相互关系，例如，多维缩放分析和主成分分析的图示结果等。将表达谱分析结果与基因序列、转录调控因子、启动子等其它数据结合起来，应用可视化技术显示这些数据及其关系，有助于深入理解基因表达调控，认识基因之间的相互作用，发现新的生物学知识。
8.4.6 聚类结果的定量评价
从上述对聚类算法的介绍来看，聚类方法很多，针对同一个数据集，可以选择不同的相似度函数和不同的聚类方法，自然会产生一个问题，针对特定的数据集，这么样的聚类结果是“好”的？很显然，不同的聚类方法得到的结果是不一样的，也许它们可能会从不同的侧面来反映特定的生物学知识。但是，从目前在生物医学中的应用看，对特定的表达谱数据，最常用的还是层次式聚类、K 均值算法或自组织特征映射法。为什么有许多其它的方法而不用呢？这也是拥有基因表达实验数据的生物学家面临的一个主要问题，如何为他的数据集选择正确的聚类算法？要选择“好”的聚类方法，首先必须对各种聚类方法进行评价，分析其适用的数据集类型，然后才能针对特定的数据集推荐“好”的聚类方
法，最后还得对聚类结果进行评价，判断所得结果是有效的，正确的。
要对聚类结果进行评价，黄金标准当属于能否发现生物学知识，即从数据出发，能够找到新的生物学知识或得到明确的对某些生物学问题的答案，例如，能够预测未知功能的基因，能够明确样本的肿瘤分型，能够获得基因之间的调控关系等等。能够在生物医学中得到应用，该方法就是有效的，就是好的方法。但是，对方法进行生物学评价是非常困难的。聚类方法作为一种探索性的知识发现方法，它的结果是预测性的，而生物学知识还是非常不完备的，很难从理论上来证明，因此必须通过生物学实验的验证才能证明其预测的正确性。就目前的生物分子信息检测技术而言，还是非常困难的。目前，对聚类结果的评价主要从内部标准和外部标准两个方面进行。所谓的内部标准，是指利用结果的统计特征，而不借助任何外来信息进行评价，例如，类间分离度、类内紧致性等；所谓外部标准是指有一个参考标准，分析新的聚类结果与参考标准的匹配性，来判断聚类方法的好坏。聚类结果的有效性分析是聚类分析方法的瓶颈，以下介绍常用的几种聚类算法的定量评价指标。
（ 1 ）误差平方和准则:
假定有一组样本，要求将这些样本分成c 个类，由于存在多种可能的分类方案，到底哪种分法最好？这就必须定义一个准则函数，聚类问题就变成对这个准则函数求极值的问题。最简单的准则是误差平方和准则，其准则函数定义如下：
(8-33)
其中 c 为聚类数，f i表示第i 个聚类的样本集合，m i是集合f i中所有样本的中心。显然，使J 最小化的聚类就是最好的聚类。当每类的样本都很密集，而各类之间又有明显的分离，使用这种准则进行聚类可得到最好的结果。而当各类界限不清楚时，利用这种准则得到的聚类结果往往不能令人满意。
（ 2 ）Silhouette 值:
采用类间分离度和类内紧致性来评价聚类结果的好坏是常用的方法。如果在样本空间中，各个聚类彼此分隔得比较远，而每个聚类中的样本又彼此靠近，则可以认为聚类效果好。因此，可以用类间距离与类内距离的比值作为衡量聚类结果的标准。基因表达谱的分类有效性分析的另一种方法是采用最小类间距离与类内平均距离的相对差值作为判断依据，其计算公式如下：
(8-34)
其中b(i) 为某类中的样本i到其它类样本的平均距离的最小值，a(i) 为某类中的样本i与类内其它样本的平均距离。S(i) 的值反映了样本i 的分类情况，一般通过某类中所有样本的平均S(i) 值作为判断该类的好坏的标准。
（ 3 ）FOM 值:
FOM(figure of merit ，量度优值) 法，是一种数据驱动的方法，用于比较来自基于启发式聚类算法的分类质量。本质上属于留一交叉验证方法(leave-one-out cross validation) ，即在G 个基因、n 个条件中保留{1,2,…,e-1,e+1,…,n} 进行聚类分析，留出条件 e 用于验证，聚类后有k 个类，用f1, … ，f k表示每一类的基因集合。x ge表示基因g 在条件e 下的表达水平，是类f i中的基因在e 条件下的平均表达水平，则
(8-35)
对n 个条件分别计算FOM （ e ,k ）值，并求和作为聚类方法的评价指标，
(8-36)
FOM 法存在一些应用上的限制，首先是该方法并非对所用的情况都适用，如果所有的实验条件之间是相互独立的，那么取出条件 e 后的n-1 个条件下的聚类结果就不能对 e 条件有预测效果。但是，在实际情况下，FOM 法对于许多基因表达数据集是可用的，可以应用于时间系列数据、来自不同组织样本的数据集。其次，对于比较具有不同类数目的聚类结果是不合适的。因为FOM(e,k) 定义为类内方差在所有k 类上的和，随着类数目的增加，FOM 会下降。因此，可以定义调整的FOM ，将FOM 除以一个因子，来弥补由于类数目不同而造成的统计偏差，计算公式如下：
(8-37)
（ 4 ）Rand 指数：
根据生物学知识对基因的分类或用其它方法形成的聚类结果，称为外部参考分类。比较外部参考分类与当前聚类方法的结果，可以判断该聚类方法的性能。假设外部参考分类集合，当前聚类的结果为
。令a 是在U 中分在同一类、同时在V 中也分在同一类的基因数目，b 是在U 中属于同一类而在V 中不属于同一类的基因数目，c 是在U 中不属于同一类而在V 中属于同一类的基因数目，d 是在U 和V 中都不在同一类中的基因数目，a 和d 可以解释为一致的，而b ，c 解释为不一致的，则Rand 指数可以定义为：
（8-38）
如果参考分类与当前分类很吻合，则RI=1 。
共2页: 上一页[1] 2 下一页
上一篇：基因表达差异的显著性分析下一篇：基因表达数据的分类分析
全基因组表达谱分析方法（DGE）----基于新一代测序技术的 技术路线 该方法首先从每个mRNA的3’端酶切得到一段21bp的TAG片段（特异性标记该基因）；然后通过高通量测序，得到大量的TAG序列，不同的TAG序列的数量就代表了相应基因的表达量；通过生物信息学分析得到TAG代表的基因、基因表达水平、以及样品间基因表达差异等信息。技术路线如下： 1、样品准备： a) 提供浓度≥300ng/ul、总量≥6ug、OD260/280为1.8~2.2的总RNA样品； 2、样品制备（见图1-1）： a) 类似SAGE技术，通过特异性酶切的方法从每个mRNA的3’末端得到一段21bp 的特异性片段，用来标记该基因，称为TAG； b) 在TAG片段两端连接上用于测序的接头引物； 3、上机测序： a) 通过高通量测序每个样品可以得到至少250万条TAG序列； 4、基本信息分析： a) 对原始数据进行基本处理，得到高质量的TAG序列； b) 通过统计每个TAG序列的数量，得到该TAG标记的基因的表达量； c) 对TAG进行注释，建立TAG和基因的对应关系； d) 基因在正义链和反义链上表达量间的关系； e) 其它统计分析； 5、高级信息分析： a) 基因在样品间差异表达分析； b) 库容量饱和度分析；
c) 其它分析； 测序优势 利用高通量测序进行表达谱研究的优势很明显，具体如下： 1．数字化信号：直接测定每个基因的特异性表达标签序列，通过计数表达标签序列的数目来确定该基因的表达量，大大提高了定量分析的准确度。整体表达差异分布符合正态分布，不会因为不同批次实验引起不必要的误差。 2．可重复性高：不同批次的表达谱度量准确，能够更准确的进行表达差异分析。 3．高灵敏度：对于表达差异不大的基因能够灵敏的检测其表达差异；能够检测出低丰度的表达基因。 4．全基因组分析，高性价比：由于该技术不用事先设计探针，而是直接测序的方式，因此无需了解物种基因信息，可以直接对任何物种进行包括未知基因在内的全基因组表达谱分析，因此性价比很高。 5．高通量测序：已有数据表明，当测序通量达到200万个表达标签时，即可得到样本中接近全部表达基因的表达量数据，而目前每个样本分析可以得到300 万~600万个表达标签。
本科生毕业设计 姓名：学号： 学院：计算机科学与技术学院 专业：计算机科学与技术 设计题目：基于谱聚类的图像分割 专题：图像分割的设计与实现 指导教师：职称：副教授
大学毕业设计任务书 学院计算机专业年级学生姓名 任务下达日期： 毕业设计日期： 毕业设计题目： 毕业设计专题题目 毕业设计主要内容和要求： 院长签章：指导教师签字：
中国矿业大学毕业设计指导教师评阅书 指导教师评语（①基础理论及基本技能的掌握；②独立解决实际问题的能力；③研究内容的理论依据和技术方法；④取得的主要成果及创新点；⑤工作态度及工作量；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：指导教师签字： 年月日
中国矿业大学毕业设计评阅教师评阅书 评阅教师评语（①选题的意义；②基础理论及基本技能的掌握；③综合运用所学知识解决实际问题的能力；③工作量的大小；④取得的主要成果及创新点；⑤写作的规范程度；⑥总体评价及建议成绩；⑦存在问题；⑧是否同意答辩等）： 成绩：评阅教师签字： 年月日
中国矿业大学毕业设计答辩及综合成绩
需求分析 一、利用前台，得到一张原始JPG图片； 二、把这张图片传到后台，JAVA通过JRI调用R； 三、利用R调用K-Means的改进算法，实现对这张图片的处理，由于一张图片的 像素值是一个矩阵，可以得到一组关于像素值的数据； 四、把这组像素值进行分类，对各类赋予不同的颜色进行标记，从而区分出需要的 图片信息； 五、把得到的新图片传到前台； 六、前台对进行处理后的图片进行显示，从图像中得到需要的信息，从而实现图像 的分割。
基因表达谱测序 背景介绍 基因表达谱分析利用HiSeq 2000高通量测序平台对mRNA进行测序，获得10M读长为49nt的原始reads，每一个reads可以对应到相应的转录本，从而研究基因的表达差异情况。与转录组测序相比，基因表达谱分析要求的读长更短，测序通量更小，仅可用于基因表达差异的研究。该方法具有定量准、可重复性高、检测阈值宽、成本低等特点，能很好的替代以往的数字化表达谱分析。 技术路线
生物信息学分析 送样要求 样品要求 1. 所需Total RNA 的量均不少于 20μg/文库，Total RNA 可以保存在DEPC 处理过的水中、75%的乙醇、异丙醇中，具体以什么方式保存请注明。 2. 如提供实验材料为动物组织材料，样品质量需大于2g ； 3. 如提供实验材料为植物样品，样品质量需大于4g ； 4. 如提供实验材料为培养细胞，请提供1×107培养好的细胞； 5. 如提供实验材料为血液样品，请提供≥2ml 的样品。 我们强烈建议在送样的同时客户做好备份，以备后续实验之用。 样品纯度要求 1. OD 260/OD 280在1.8- 2.0之间，RNA 无降解、28S 和18S 核糖体RNA 条带非常亮且清晰（其
大小决定于用于抽提RNA的物种类型），28S的密度大约是18S的2倍；Agilent 2100检测仪分析RNA完整性数据RIN≥8。 2. 无蛋白质、基因组DNA污染，如有污染请去蛋白并进行DNase I处理。 请提供至少一种样品的凝胶电泳或者Agilent 2100检测仪检测图片，并注明其浓度、体积、OD260/OD280、溶剂名称、制备时间、物种来源以及特别备注。最终以我方定量、质检为准。 样品采集 为了保证提取RNA的完整性，确保后续实验的顺利进行，请务必确保样品的新鲜，对于如何确保样品的新鲜针对不同的样品获取材料的方法如下： 1. 动物组织：从活体上迅速的取下组织（切成黄豆粒大小的块状），每切成一个黄豆粒大小的块状立即放入液氮中，重复上述操作，直至足够提取总RNA的量；准备一个50ml的离心管，做相应的标记（样品名称、编号、客户姓名、时间），最好既在管盖上做好标记，也在管壁上做好相应的标记，先放入液氮中预冷2-3min，拿出离心管（离心管的下部分还是保持在液氮中），打开离心管的盖子，将液氮中黄豆粒大小的块状收集进离心管中。 2. 植物组织： （1）如所采集的是果实、麦穗等体积偏大的样品，收集样品请参照1.动物组织取样方法；（2）如采集的是叶片等体积偏小的样品，请尽量采集嫩叶、幼芽等，每采集一片叶片立即放入液氮中，直至足够提取总RNA的量，后续操作请参照动物组织的采集。 （3）如是植物的花，在采集花骨朵的时候请尽量不要采集到花萼、叶片等，每采集一个花骨朵请立即放入液氮中，直至足够提取总RNA的量；后续操作请参照动物组织的采集。3. 如提供实验材料为菌丝体，请取500μl的菌液于1.5ml离心管中，离心去上清，剩余菌丝体放入液氮或干冰中，请提供不少于5管的菌丝体。 样品运输 从液氮中取出准备好的样品，请立即放入干冰中，并用干冰掩埋好样品。请填写完整订单，放入自封袋中与样品一起邮寄。为防止RNA的降解，请确保干冰的量足够运送到目的地。我们强烈建议在寄送RNA样品时将RNA保存在75%的乙醇或异丙醇中。 如是特殊样品，关于送样量和保存问题请与我们联系沟通，以便双方共同协商解决。 提供结果 根据客户需求，提供不同深度的信息分析结果。
基因表达谱芯片的数据分析(2012-03-13 15:25:58)转载▼ 标签：杂谈分类：生物信息 摘要 基因芯片数据分析的目的就是从看似杂乱无序的数据中找出它固有的规律, 本文根据数据分析的目的, 从差异基因表达分析、聚类分析、判别分析以及其它分析等角度对芯片数据分析进行综述, 并对每一种方法的优缺点进行评述, 为正确选用基因芯片数据分析方法提供参考. 关键词: 基因芯片; 数据分析; 差异基因表达; 聚类分析; 判别分析 吴斌, 沈自尹. 基因表达谱芯片的数据分析. 世界华人消化杂志2006;14(1):68-74 https://www.doczj.com/doc/6c970690.html,/1009-3079/14/68.asp 0 引言 基因芯片数据分析就是对从基因芯片高密度杂交点阵图中提取的杂交点荧光强度信号进行的定量分析, 通过有效数据的筛选和相关基因表达谱的聚类, 最终整合杂交点的生物学信息, 发现基因的表达谱与功能可能存在的联系. 然而每次实验都产生海量数据, 如何解读芯片上成千上万个基因点的杂交信息, 将无机的信息数据与有机的生命活动联系起来, 阐释生命特征和规律以及基因的功能, 是生物信息学研究的重要课题[1]. 基因芯片的数据分析方法从机器学习的角度可分为监督分析和非监督分析, 假如分类还没有形成, 非监督分析和聚类方法是恰当的分析方法; 假如分类已经存在, 则监督分析和判别方法就比非监督分析和聚类方法更有效率。根据研究目的的不同[2,3], 我们对基因芯片数据分析方法分类如下: (1)差异基因表达分析: 基因芯片可用于监测基因在不同组织样品中的表达差异, 例如在正常细胞和肿瘤细胞中; (2)聚类分析: 分析基因或样本之间的相互关系, 使用的统计方法主要是聚类分析; (3)判别分析: 以某些在不同样品中表达差异显著的基因作为模版, 通过判别分析就可建立有效的疾病诊断方法. 1 差异基因表达分析(difference expression, DE) 对于使用参照实验设计进行的重复实验, 可以对2样本的基因表达数据进行差异基因表达分
二、近似谱聚类算法描述 本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。 表3.2 近似谱聚类算法（ASCA） 算法：近似谱聚类算法（ASCA） 输入：数据点，待聚类数目 输出：聚类 1. 使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵； 2. 使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵； 3. 使用优化公式对矩阵进行离群点调优； 4. 计算对称半正定拉普拉斯矩阵； 5. 计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵； 6. 计算标准化矩阵（）； 7. 使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类，把其聚类成k组（）。 基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP: Orthogonalization Nystr?m Spectral Clustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC: Spectral Clustering）进行对比，并验证其聚类效果。 图3.1 近似谱聚类算法流程示意图 三、近似谱聚类算法时间复杂度分析 现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard （Non deterministic Ploynomial Hard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。 第三节近似谱聚类算法实验分析 一、近似谱聚类算法辅助实验 （1）Matlab辅助实验环境描述 为验证表3.2所示近似谱聚类算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于Hadoop MapReduce并行实验对
聚类分析 1.聚类分析定义： 2.聚类方法： 3.谱聚类： 3.1 常见矩阵变换 3.2 谱聚类流程 3.3 谱聚类理论前提、证明 3.4 图像分割实例结果 4.总结：
聚类分析： ?聚类分析（Cluster analysis，亦称为群集分析）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
算法分类： ?数据聚类算法可以分为结构性或者分散性。 ?结构性算法以前成功使用过的聚类器进行分类。结构性算法可以从上至下或者从下至上双向进行计算。从下至上算法从每个对象作为单独分类开始，不断融合其中相近的对象。而从上至下算法则是把所有对象作为一个整体分类，然后逐渐分小。 ?分散型算法是一次确定所有分类。K-均值法及衍生算法。 ?谱聚类（spectral clustering）
结构型：层次聚类的一个例子：
分散型：K-均值算法：
分散型k-means 及其衍生算法的比较：K-means K-Medoids K-Means算法： 1. 将数据分为k个非空子集 2. 计算每个类中心点（k-means
第24章 基因表达谱分析的生物信息学方法 思考与练习参考答案 1．据教材表24–3提供的数据信息可以构建一棵决策树，请利用最大信息增益方法写出如何选出根结点中用于分割的特征。 教材表24-3 天气情况与是否去打球的关系数据集 注：该信息表示根据天气情况决定是否出去打球，数据集共包含14个样本，两个类别信息（Yes 、No ），每个样本包含3 个特征信息（Outlook 、Temp 、Windy ）。 解：计算用每一个特征进行分割时所获取的信息增益，取信息增益最大的那个特征作为分割特征，以Outlook 特征为例计算（参照练习图24-1） 练习图24-1 同Outlook 特征进行分割所获得的信息增益 )14 9 log 149145 log 145()(220+-=S H
)5 2 log 5253 log 53()(2211+-=S H 0)4 4 log 44()(212=-=S H )52 log 5253 log 53()(2213+-=S H )(14 5 )(144)(145)(1312111S H S H S H S H ++= infor-gain （Outlook ）=)()(10S H S H - 同理，计算其他两个特征的信息增益，最后从三个值中选取最大的一个对应的特征作为根结点的分割特征。 2．请从https://www.doczj.com/doc/6c970690.html,/上下载一原始未经标准化的表达谱数据，并对该数据进行如下分析： （1）对数据进行标准化处理。 （2）对数据进行分类分析。 （3）分别对基因和样本进行聚类分析。 （4）选择特征基因。 （答案略）
基因表达谱数据 基因表达谱可以用一个矩阵来表示，每一行代表一个基因，每一列代表一个样本（如图1）。所有基因的表达谱数据在“gene_exp.txt ”文件中存储，第一列为基因的entrez geneid ，第2~61列是疾病样本的表达，第62~76列是正常样本的表达。 图1 基因表达谱的矩阵表示 寻找差异表达的基因： 原理介绍： 差异表达分析是目前比较常用的识别疾病相关miRNA 以及基因的方法，目前也有很多差异表达分析的方法，但比较简单也比较常用的是Fold change 方法。它的优点是计算简单直观，缺点是没有考虑到差异表达的统计显著性；通常以2倍差异为阈值，判断基因是否差异表达。Fold change 的计算公式如下： normal Disease x x c Fold = _ 即用疾病样本的表达均值除以正常样本的表达均值。 差异表达分析的目的：识别两个条件下表达差异显著的基因，即一个基因在两个条件中的表达水平，在排除各种偏差后，其差异具有统计学意义。我们利用一种比较常见的T 检验（T-test ）方法来寻找差异表达的miRNA 。T 检验的主要原理为：对每一个miRNA 计算一个T 统计量来衡量疾病与正常情况下miRNA 表达的差异，然后根据t 分布计算显著性p 值来衡量这种差异的显著性，T 统计量计算公式如下： n s n s x x t normal Disease normal Disease miRNA //22+-= 对于得到的显著性p 值，我们需要进行多重检验校正（FDR ），比较常用的是BH 方法（Benjamini and Hochberg, 1995）。
网络社区划分算法 目录 ? 1 简介 ? 2 构建一个点击流网络 ? 3 网络社区划分的两种主要思路：拓扑分析和流分析 ? 4 拓扑分析 o 4.1 计算网络的模块化程度Q-Modularity o 4.2 计算网络的连边紧密度Edge betweenness o 4.3 计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4 通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5 通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ? 5 流分析 o 5.1 随机游走算法Walk Trap o 5.2 标签扩散算法label propagation o 5.3 流编码算法the Map Equation o 5.4 流层级算法Role-based Similarity ? 6 总结 [1]简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。 社区划分的算法比较多，但我个人认为大致可以分为两大类：拓扑分析和流分析。前者一般适用于无向无权网络，思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、
江北区街道： 中马街道：槐树社区、新马社区、浮石社区、外滩社区、盐仓社区、咸宁社区 白沙街道：白沙社区、北站社区、大庆社区、正大社区、桃源社区 孔浦街道：绿梅、怡江、红梅、百合、白杨、孔浦一村、孔浦二村、文竹 文教街道：双东坊社区、范江岸社区、育才社区、翠柏社区、大闸社区、繁景社区、北岸琴森社区，永红村 甬江街道：白杨社区、百合社区、梅堰社区，北郊、湾头，河西村、畈里塘村、外漕村、夏家村、河东村、压赛村、孔浦村、甄隘村、下江村、姚江村 庄桥街道：河东社区、河西社区、广厦社区、广庭社区、天水社区、天合社区、费市社区、天成社区；（7个居民点）车站、镇北、费市、马径、镇南、上邵、袁陈；（25个行政村）孔家村、葛家村、李家村、马径村、西卫桥村、童家村、姚家村、东邵村、西邵村、袁陈村、谢家村、颜家村、邵家村、冯家村、费市村、居陆村、灵山村、胡家村、苏冯村、上邵村、邵余村、应家村、洪家村、联群村、塘民村 洪塘街道：洪塘社区、姚江社区、亲亲社区、洪都社区、宁沁社区、洋市社区、裘市社区、北欣社区、逸嘉社区（22个行政村）洪塘村、荪湖村、安山村、周陈村、后张村、上沈村、旧宅村、赵家村、下沈村、前后潘村、林家村、叶家斗村、洋市村、孙家村、上宅村、西江村、横山村、郎家村、裘市村、朱界村、邵家渡村、西洪村 海曙区街道： 灵塔街道：新街社区、郡庙社区、天封社区、莲桥社区。 月湖街道：太阳社区、梅园社区、桂井社区、县学社区、迎凤社区、平桥社区、天一社区。 鼓楼街道：苍水社区、秀水社区、孝闻社区、文昌社区、中山社区、和义社区。 南门街道：澄浪社区、柳锦社区、万安社区、红起社区、周江岸社区、朝阳社区、车站社区、马园社区、朗官社区、尹江岸社区、迎春社区。 西门街道：汪弄社区、北郊社区、文化社区、龙柏社区、柳庄社区、新高社区、永丰社区、芝红社区、新芝社区、翠南社区、胜丰社区、翠中社区、东社区。 白云街道：云和社区、云乐社区、联南社区(泰丰街10号)、牡丹社区、云丰社区、联北社区、安丰社区、宝善社区、安泰社区、南雅社区。 段塘街道：南苑社区、华兴社区、新典社区、南塘社区、洞桥社区、雄镇社区、小漕社区、南都社区。 望春街道：天一家园社区、泰安社区、徐家漕社区、西成社区、信谊社区、新星村、后孙村、徐家漕村、望春桥村、双杨村、西成村、胜丰村、姚丰村、前丰村、甬丰村、联丰村、震丰村。 江东区街道： 白鹤街道：孔雀、黄鹂、丹凤、镇安、王隘、白鹤、贺丞、丹顶鹤、紫鹃、周宿渡、日月星辰。百丈街道：后塘、朱雀、七塔、宁舟、舟孟、演武、华严、潜龙、中山、划船。 东胜街道：张斌、庆安、史家、曙光、大河、泰和、樱花、戎家、王家。 明楼街道：辖惊驾、林家、徐家、东海、明南、徐戎、明北、朝晖、明东、常青藤。 东柳街道：辖园丁、锦苑、东柳坊、太古城、华侨城、幸福苑、华光城、安居、中兴、月季、东海花园。 东郊街道：仇毕、宁丰社区。 福明街道：江南、明一、南余、余隘、戚隘桥、七里垫、史魏家、张隘、柳隘、松下、桑家、邵家、王家园、福明家园、新源、陆嘉、波波城、碧城、新城、福城、东城、江城、宁城、明城。新明街道：辖老庙、朱一、新晖、明月、滨江。
基因表达谱芯片数据分析及其Bioconductor实现 1.表达谱芯片及其应用 表达谱DNA芯片（DNA microarrays for gene expression profiles）是指将大量DNA片段或寡核昔酸固定在玻璃、硅、塑料等硬质载体上制备成基因芯片，待测样品中的mRNA被提取后，通过逆转录获得cDNA,并在此过程中标记荧光，然后与包含上千个基因的DNA芯片进行杂交反应30min~20h后，将芯片上未发生结合反应的片段洗去，再对玻片进行激光共聚焦扫描，测定芯片上个点的荧光强度，从而推算出待测样品中各种基因的表达水平。用于硏究基因表达的芯片可以有两种：①cDNA芯片；② 寡核昔酸芯片。 cDNA芯片技术及载有较长片段的寡核昔酸芯片采用双色荧光系统：U前常用Cy3—dUTP （绿色）标记对照组mRNA, Cy5—dUTP （红色）标记样品组mRNAUl。用不同波长的荧光扫描芯片，将扫描所得每一点荧光信号值自动输入计?算机并进行信息处理，给出每个点在不同波长下的荧光强度值及其比值（ratio值），同时计算机还给出直观的显色图。在样品中呈高表达的基因其杂交点呈红色，相反，在对照组中高表达的基因其杂交点呈绿色，在两组中表达水平相当的显黄色，这些信号就代表了样品中基因的转录表达情况⑵。 基因芯片因具有高效率，高通量、高精度以及能平行对照研究等特点，被迅速应用于动、植物和人类基因的研究领域，如病原微生物毒力相关基因的。基因表达谱可直接检测mRNA的种类及丰度，可以同时分析上万个基因的表达变化，来揭示基因之间表达变化的相互关系。表达谱芯片可用于研究：①同一个体在同一时间里，不同基因的表达差异。芯片上固定的已知序列的cDNA或寡聚核昔酸最多可以达到30 000多个序列，与人类全基因组基因数相当，所以基因芯片一次反应儿乎就能够分析整个人的基因⑶。②同一个体在不同时间里，相同基因的表达差异。 ③不同个体的相同基因表达上的差异。利用基因芯片可以分析多个样本，同时筛选不同样本（如肿瘤组织、癌前病变和正常组织）之间差异表达的基因，这样可以避免了芯片间的变异造成的误差⑷。张辛燕⑸ 等将512个人癌基因和抑癌基因的cDNA用点样仪点在特制玻片上制成表达谱芯片，对正常人卵巢组织及卵巢癌组织基因表达的差异性进行比较研究，结果发现在卵巢癌组织中下调的基因有23个，上调的基因有15个，初步筛选出了卵巢癌相关基因。Lowe⑹等利用胰腺癌、问充质细胞癌等组织的cDNA制备基因芯片，筛选到胰腺癌细胞中高表达的基因，为医疗诊断、病理研究及新药设计 奠定基础。 2.表达谱芯片的数据处理技术
谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)，也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。 图1 谱聚类无向图划分——Smallest cut和Best cut 这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。 1 理论基础 对于如下空间向量item-user matrix： 如果要将item做聚类，常常想到k-means聚类方法，复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数： 1 如果M足够大呢？ 2 K的选取？ 3 类的假设是凸球形的？ 4 如果item是不同的实体呢？ 5 Kmeans无可避免的局部最优收敛？ …… 这些都使常见的聚类问题变得相当复杂。 1.1 图的表示
如果我们计算出item与item之间的相似度，便可以得到一个只有item的相似矩阵，进一步，将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)，这样便得到我们常见的图的概念。 对于图的表示(如图2)，常用的有： 邻接矩阵：E，e ij表示v i和v i的边的权值，E为对称矩阵，对角线上元素为0，如图2-2。 Laplacian矩阵：L = D – E，其中d i (行或列元素的和)，如图2-3。 图2 图的表示 1.2 特征值与L矩阵 先考虑一种最优化图像分割方法，以二分为例，将图cut为S和T两部分，等价于如下损失函数cut(S, T)，如公式1所示，即最小(砍掉的边的加权和)。 假设二分成两类，S和T，用q(如公式2所示)表示分类情况，且q满足公式3的关系，用于类标识。 那么：
谱聚类 七月算法邹博 2015年11月15日
9月机器学习班2/21 谱和谱聚类 ?方阵作为线性算子，它的所有特征值的全体统称方阵的谱。 ?方阵的谱半径为最大的特征值 ?矩阵A 的谱半径：(A T A)的最大特征值 ?谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
9月机器学习班3/21 谱分析的整体过程 ?给定一组数据x 1,x 2,...x n ，记任意两个点之间的相似度(“距离”的减函数)为s ij =
9月机器学习班4/21 若干概念 ?无向图G=(V,E) ?邻接矩阵 ?顶点的度di →度矩阵D (对角阵)
9月机器学习班5/21 若干概念 ?子图A 的指示向量 ?A 和B 是图G 的不相交子图，则定义子图的连接权：
9月机器学习班6/21 相似度图G 的建立方法 ?全连接图 ?高斯相似度函数：距离越大，相似度越小 ?ε近邻图 ?给定参数ε ?思考：如何选择ε？ ?图G 的权值的均值 ?图G 的最小生成树的最大边 ?k 近邻图(k-nearest neighbor graph) ?若vi 的k 最近邻包含vj ，vj 的k 最近邻不一定包含vi ：有向图?忽略方向的图，往往简称“k 近邻图” ?两者都满足才连接的图，称作“互k 近邻图(mutual)”
基因表达谱聚类分析 [ 文章来源：| 文章作者：| 发布时间：2006-12-21| 字体：[大中小] 学习过程可以采用从全局到局部的策略。采取这种策略时，学习初期可设定较大的交互作用半径R ，随着学习过程的不断推进，逐步减小R ，直至不考虑对邻近单元的影响。邻域的形状可以是正方形或者圆形。 KFM 的聚类结果与K 均值相似，它的优点是自动提取样本数据中的信息，同时也是一种全局的决策方法，能避免陷入局部最小，缺点在于必须实现人为设定类的数目与学习参数，而且学习时间较长。KFM 方法克服了K- 均值聚类的一些缺点：它应用类间的全局关系，能提供大数据集内相似性关系的综合看法，便于研究数据变量值的分布及发现类结构。而且，它具有更稳健更准确的特点，对噪声稳定，一般不依赖于数据分布的形状。 8.4.2.5 其它聚类方法 聚类方法是数据挖掘中的基本方法，数据挖掘的方法很多，在基因表达谱的分析中，除了以上常用方法外，还有一些其它的方法。由于对聚类结果尚没有一种有效的方法进行评价，尤其是对聚类结果的进一步生物学知识发现尚没有新的分析思路和成功应用，因此，科学家们在不断地研究一些新方法。这些方法有不同的原理，能够提取不同数据特征，有可能对具体的数据得到更有意义的结果，发现更多的生物学知识。这里，简单介绍这些方法的原理，更详细的介绍请参看相关文献。 (1)模糊聚类分析方法:这是一种模拟人类的思维方法，通过隶属度函数来反映某一对象属于某一类的程度。基本思路是计算两两基因表达谱之间的相似性程度，构建模糊相似矩阵，利用模糊数学中的传递闭包计算方法得到模糊等价矩阵，选择不同的置信水平从模糊等价矩阵中构建动态聚类图。对于特定的置信水平，可以实现对基因表达谱的分类。该方法的优点是利用了模糊数学中的隶属度概念，能够更好的反映基因表达谱之间的相互关系，而且它是一种全局的优化方法，与向量的顺序无关。 (2)模糊C均值算法:该方法同样将模糊数学中的隶属度概念引入到常用的K 均值聚类方法中。对于K 均值算法，一个基因表达谱所属的类只有一个，因此，它与各类别的关系要么是 1 ，要么是0 ，即属于或不属于某一类。而对于模糊 C 均值法，一个基因表达谱是否属于某一类，是以隶属度来确定第i 个样本属于第j 类的可能性。最终的聚类结果取决于分析的目的，可以根据最大隶属度来确定基因表达谱的分类，即一个基因表达谱只属于一类；但往往是确定隶属度的阈值，只要大于该阈值，就可以将基因表达谱划分为该类，这样的划分结果是一个基因表达谱可以属于多个类，这也是可以被生物学家接受的。模糊 C 均值法与K 均值法的实现过程基本相同，所不同的是对于
对于基因表达谱数据的分析是生物信息学的研究热点和难点。转化为数学问题，分析任务是从数据矩阵 M 中找出显著性结构，结构类型包括全局模型 (model) 和局部模式 (pattern) 。对基因表达谱数据的分析是数据挖掘问题，所采用的方法包括通过可视化进行探索性数据分析（ Exploratory Data Analysis ）、描述建模 (descriptive modeling) 、分类、聚类、回归和机器学习等。 基因表达谱分析所采用的常用方法是聚类，其目的就是将基因分组。从数学的角度，聚类得到的基因分组，一般是组内各成员在数学特征上彼此相似，但与其它组中的成员不同。从生物学的角度，聚类分析方法所隐含的生物学意义或基本假设是，组内基因的表达谱相似，它们可能有相似的功能。然而，产物有相同功能的编码基因（例如对其它蛋白质有磷酸化作用），不一定共享相似的转录模式。相反，有不同功能的基因可能因为巧合或随机扰动而有相似的表达谱。尽管有许多意外的情况存在，大量功能相关的基因的确在相关的一组条件下有非常相似的表达谱，特别是被共同的转录因子共调控的基因，或者产物构成同一个蛋白复合体，或者参与相同的调控路径。因此，在具体的应用中，可以根据对相似表达谱的基因进行聚类，从而指派未知基因的功能。 聚类分析是模式识别和数据挖掘中普遍使用的一种方法，是基于数据的知识发现的有效方法，特别适用于模式分类数不知道的情况。聚类分析是一种无监督学习方法，不需要任何先验领域知识，它根据数学特征提取分类标准，对数据进行分类，这种数学特征的例子有统计平均值、相关系数、协方差矩阵的本征值及本征向量等。聚类分析在基因表达数据分析中应用得很多，主要有层次聚类、 K 均值、自组织特征映射网络等。本节将介绍基因表达数据分析中常用的聚类方法及与此相关的内容。 8.4.1 相似性度量函数 对基因表达谱进行聚类分析之前，必须首先确定反映不同基因表达谱相似程度的度量函数，根据该函数可以将相似程度高的基因分为一类。在实际计算中，还可以用距离代替相似的概念，相似性度量被转化为两个基因表达谱之间的距离。距离越小，表达模式越相近；反之，则表达模式差异大。 常见的相似性度量有距离、点积、相关系数（ correlation coefficient ）、互信息（ mutual information ）等。假设两个基因表达谱分别为X = （x 1 ,x 2 ,…,x m ）和Y = （y 1 ,y 2 ,…, y m ） , 距离函数 d( X ，Y ) 必须满足如下条件： d( X ，Y ) ≧ 0 d( X ，Y ) = d( Y ，X ) d( X ，Y ) = 0 if X = Y
网络社区划分算法 目录 ?1简介 ?2构建一个点击流网络 ?3网络社区划分的两种主要思路：拓扑分析和流分析 ?4拓扑分析 o 4.1计算网络的模块化程度Q-Modularity o 4.2计算网络的连边紧密度Edge betweenness o 4.3计算网络拉普拉斯矩阵的特征向量Leading eigenvector o 4.4通过fast greedy方法搜索网络模块化程度Q-Modularity的最大值 o 4.5通过multi level方法搜索网络模块化程度Q-Modularity的最大值 ?5流分析 o 5.1随机游走算法Walk Trap o 5.2标签扩散算法label propagation o 5.3流编码算法 the Map Equation o 5.4流层级算法 Role-based Similarity ?6总结 []简介 使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。 假设我们手头有一批用户在一段期间内访问某类资源的数据。为了减少数据数理规模，我们一般只考虑最经常被访问的一批资源。因此在数据处理中，我们考虑UV（user visit）排名前V的资源，得到节点集合|V|，然后对于一个用户i在一段时间内（例如一天）内访问的资源，选择属于|V|的子集vi。如果我们有用户访问资源的时间，就可以按照时间上的先后顺序，从vi中产生vi-1条有向边。如果我们没有时间的数据，可以vi两两间建立联系，形成vi(vi-1)/2条无向边。因为后者对数据的要求比较低，下文中，暂时先考虑后者的情况。对于一天内的n个用户做这个操作，最后将得到的总数为的连边里相同的边合并，得到|M|个不同的边，每条边上都带有权重信息。 这样，我们就得到了V个节点，M条边的一个加权无向网络，反应的是在一天之内用户在主要的信息资源间的流动情况。在这个网络上，我们可以通过社区划分的算法对信息资源进行分类。
谱聚类算法及其在图像分割中的应用 1 引言 在对图像的研究和应用中，人们往往仅对图像中的某些部分或者说某些区域感兴趣。这些部分常称为目标或前景（其他部分称为背景），它们一般对应图像中特定的具有独特性质的区域。为了辨识和分析目标，需要将它们从图像中分离提取出来，在此基础上才有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等，预先定义的目标可以对应单个区域，也可以对应多个区域。 多年来，对图像分割的研究一直是图像技术研究中的热点和焦点，它不但是从图像处理到图像分析的关键步骤[1]，而且是计算机视觉领域低层次视觉中的主要问题。图像分割的结果是图像特征提取和识别等图像理解的基础，只有在图像被分割后，图像的分析才成为可能。 图像分割在实际应用中已得到了广泛的应用，如图像编码、模式识别、位移估计、目标跟踪、大气图像、军用图像、遥感图像、生物医学图像分析等领域。同时，图像分割也在计算机视觉和图像识别的各种应用系统中占有相当重要的地位，它是研制和开发计算机视觉系统、字符识别和目标自动获取等图像识别和理解系统首先要解决的问题。概括地说只要需对图像目标进行提取测量等都离不开图像分割。 对分割算法的研究已经有几十年的历史，至今借助于各种理论已经提出了数以千计的分割算法[2]，而且这方面的研究仍然在积极进行。尽管人们在图像分割方面做了许多工作，但至今仍无通用的分割算法，也不存在一个判断分割是否成功的客观标准。因此已经提出的分割算法大都是针对具体问题的，并没有一种适合于所有图像的通用的分割算法。实际上由于不同领域的图像千差万别，也不可能存在万能的通用算法。 现有的分割算法非常多，大体上可以分为以下几类：阈值化分割、基于边缘检测的、基于区域的、基于聚类的和基于一些特定理论工具的分割方法。从图像的类型来分最常见的：有灰度图像分割、彩色图像分割和纹理图像分割等等。本
基因表达谱分析技术 1微阵列技术（microarray） 这是近年来发展起来的可用于大规模快速检测基因差别表达、基因组表达谱、DNA序列多态性、致病基因或疾病相关基因的一项新的基因功能研究技术。其原理基本是利用光导化学合成、照相平板印刷以及固相表面化学合成等技术,在固相表面合成成千上万个寡核苷酸“探针”（cDNA、ESTs或基因特异的寡核苷酸），并与放射性同位素或荧光物标记的来自不同细胞、组织或整个器官的DNA或mRNA反转录生成的第一链cDNA进行杂交，然后用特殊的检测系统对每个杂交点进行定量分析。其优点是可以同时对大量基因，甚至整个基因组的基因表达进行对比分析。包括cDNA芯片（cDNA microarray）和DNA芯片（DNA chips）。 cDNA芯片使用的载体可以是尼龙膜，也可以是玻片。当使用尼龙膜时，目前的技术水平可以将20000份材料点在一张12cm×18cm的膜上。尼龙膜上所点的一般是编好顺序的变性了的双链cDNA片段。要得到基因表达情况的数据，只需要将未知的样品与其杂交即可。杂交的结果表示这一样品中基因的表达模式，而比较两份不同样品的杂交结果就可以得到在不同样品中表达模式存在差异的基因。杂交使用的探针一般为mRNA的反转录产物，标记探针使用32PdATP。如果使用玻片为载体，点阵的密度要高于尼龙膜。杂交时使用两种不同颜色的荧光标记不同的两份样品，然后将两份样品混合起来与一张芯片杂交。洗去未杂交的探针以后，能够结合标记cDNA的点受到激发后会发出荧光。通过扫描装置可以检测各个点发出荧光的强度。对每一个点而言，所发出的两种不同荧光的强度的比值，就代表它在不同样品中的丰度。一般来讲，显示出来的图像中，黄色的点表示在不同的样品中丰度的差异不大，红色和绿色的点代表在不同样品中其丰度各不相同。使用尼龙膜为载体制作cDNA芯片进行研究的费用要比玻片低，因为尼龙膜可以重复杂交。检测两种不同的组织或相同组织在不同条件下基因表达的差异，只需要使用少量的尼龙膜。但是利用玻片制作的cDNA芯片灵敏度更高，而且可以使用2种探针同时与芯片杂交，从而降低了因为杂交操作带来的差异；缺点是无法重复使用还必须使用更为复杂的仪器。 Guo等（2004）将包含104个重组子的cDNA文库点在芯片上，用于检测拟南芥叶片衰老时的基因表达模式，得到大约6200差异表达的ESTs，对应2491个非重复基因。其中有134个基因编码转录因子，182个基因预测参与信号传导，如MAPK级联传导路径。Li等（2006）设计高密度的寡核苷酸tiling microarray方法，检测籼稻全基因组转录表达情况。芯片上包含13,078,888个36-mer寡核苷酸探针，基于籼稻全基因组shot-gun测序的序列合成，大约81.9%（35,970）的基因发生转录事件。Hu等（2006）用含有60,000寡核苷酸探针（代表水稻全部预测表达基因）的芯片检测抗旱转基因植株（过量表达SNAC1水稻）中基因的表达情况，揭示大量的逆境相关基因都是上升表达的。 2基因表达系列分析（Serial analysis of gene expression,SAGE） 基因表达系列分析（SAGE）是一种转录物水平上研究细胞或组织基因表达模式的快速、有效的技术，也是一种高通量的功能基因组研究方法，它可以同时将不同基因的表达情况进行量化研究（Velculescu et al.,1995）。SAGE的基本原理是：每一条mRNA序列都可以用它包含的9bp的小片段（TAG）代替，因此考查这些TAGs出现的频率就能知道每一种mRNA 的丰度。首先利用生物素标记的oligo（dT）引物将mRNA反转录成双链cDNA，然后利用NlaIII 酶切双链cDNA。NlaIII酶的识别位点只有4bp，因此cDNA都被切成几十bp的小片段。带有生物素标记的小片段cDNA被分离出来，平均分成2份。这2份cDNA分别跟2个接头连接，2个接头中均有一个FokI酶切位点。FokI是一种II S型核酸内切酶，其识别位点不对称，切割位点位于识别位点下游9bp且不依赖于特异的DNA序列。FokI酶切分成2份的cDNA之