科学网 › 标签 › 双聚类

标签: 双聚类

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

对CC算法进行改进的双聚类算法FLOC算法: 热度 1 yinlu1978 2013-5-4 17:52; 算法名称： FLOC ： flexibleoverlapped clustering 文章名称： Yang J, Wang W, Wang H, Yu P. -Clusters: capturing subspace correlation in a large dataset. Proceedings of the 18th IEEE international conference on data engineering.California,USA, 2002, 517 ～ 528 摘要：近年来，聚类由于其在实践中重要性而被大家活跃的研究。其中大多数聚类模型都是集中在分组一群具有相似值的个体也就是子空间聚类并假定每一个个体在每个维度上都有相关的值。这些已经存在的聚类模型并不够充分找到物体之间的内聚性。一群物体仍有可能在一组条件子集上有较强的内聚性即使他们在每一维上都取不同的值甚至没有值。这在包括生物信息学的很多领域上都有广泛的应用，比如数据有偏差且不充足的协同过滤分析领域上。在生物信息学里，双聚类模型已经被提出来捕捉一组子集在一个条件子集上的聚合性。在本文里引入了一个更广泛的称之为 - 聚类的模型来捕捉一组物体在一个条件子集上的内聚性且允许有缺失值。一个基于移动的算法（ FLOC ）被设计出来用以高效的产生一个接近最优的聚类结果。 - 聚类模型把双聚类模型当作一个特例，在 - 聚类上 FLOC 算法运行的远优于双聚类算法。我们证明了 - 聚类模型以及 FLOC 算法在大量实际和合成数据集上的正确性和有效性。论文概要内容：论文中首先提出了一个观点：一些样本点尽管就整体来说是不相似的，但在其子空间上仍有可能是高度相似的，并提出了 - 聚类的概念，并指出了其与空间子聚类的区别是 - 聚类模型中允许出现缺失值，随后给出了 - 聚类和 - 聚类体积的定义，以及关于物体，条件和 - 聚类的基（ base ）的定义，并据其引入了元素残差的概念，注意的是对于缺失值其残差定义为 0 ，最后给出了 - 聚类的残差的概念和行方差的概念。由于 - 聚类允许出现缺失值，所以克服了随机干扰效应（ random interference ）。接下来论文给出了动作（ action ）的概念，动作的定义是建立在一个双聚类和一个行或列上的，对于一个指定的双聚类和指定的行或列，动作被定义成行或列关于双聚类的成员变化，也就是如果双聚类有行或列 , 就删除它；否则就增加它到双聚类中。为了判断每一个动作的好与坏，在论文中结合算法的目的也就是说找到双聚类的残差小于指定值且双聚类的容量（ volume ）要大，引入了相应动作的收益（ gain ）概念。其定义为双聚类执行动作前后残差之差。 FLOC 算法描述：初始化：随机生成初始双聚类的集合。迭代：对所有的行和列寻找使得双聚类最优的动作，然后执行该动作，并判断该动作是否使得的双聚类集的总体残差有没有下降，如果下降重复第二阶段，否则结束程序。随后论文分析了算法的性能，并描述了如何有效生成初始双聚类，并分析了动作的执行顺序对算法的性能，同时提出了三种动作执行顺序，分别是顺序执行，随机执行和加权执行。最后通过实际数据集和合成数据集对算法的性能进行了验证，并给出了实验结果。注意的是在比较实验结果的时候除了残差外本文还提出了二个比较优劣的标准，分别回收率（ recall ）和精度（ precision ）。假定是数据集中真实双聚类的集合，是双聚类算法找到的双聚类的集合，那么回收率就定义为，精度就定义为。在论文中还提出了几个改进程序性能的策略，一是通过选择合适的参数来控制初始双聚类的大小以期望和实际的双聚类大小基本上一致。二是改进各个最优动作执行的顺序，基本版本算法采用的是顺序执行，本文还提出了二种改进策略：随机策略和加权随机策略。随机策略就是各个动作的执行是按照随机生成的行列顺序来执行动作，所有的行列以等概率的优先权来执行；加权随机策略是在随机顺序策略的基础上考虑了动作收益，动作收益大的行列优先执行的概率大，收益小的优先执行概率小。论文结论：实验数据表明双聚类算法优于传统的聚类算法。实现论文算法后的实验结果： 1 ，实现的 FLOC 算法在时间性能上和原论文相比由较大出入。 2 ，控制初始双聚类算法的参数对程序的结果影响较大 3 ，动作收益这个概念的定义没有考虑双聚类的大小，导致找到的双聚类在列的数目上没有办法控制。后续论文对其改进：论文名称： Yang J, Wang W, Wang H, Yu P.Enhanced biclustering on expression data. Proceedings of the third IEEEconference on bioinformatics and bioengineering. Bethesda, USA, 2003, 321 ～ 327. 改进地方： 1，在这篇论文中在前面论文的基础上改进了动作收益的定义，考虑了双聚类的大小和双聚类的最大阈值。 2，准确的定义了加权随机策略的实现机制，也就是如何根据动作收益计算该动作优先执行的概率。; 5339 次阅读|2 个评论

首次提出双聚类的CC算法: yinlu1978 2013-5-4 17:43; 算法名称： CC 论文名称： Cheng Y, Church GM. Biclusteringof expression data. In Philip Bourne, Michael Gribskov eds. proceeding of theeighth international conference on intelligent system for molecular biology.California,USA, 2000, 93 ～ 103 原文见附件 cc-ismb-Biclustering of expression data.pdf 论文摘要：为了发现表达数据中的有低的均方残差的子矩阵，本文引入了一种有效的节点删除算法，通过对酵母和人的基因表达数据集的测试，它被显示出在找到共调控的模式是执行良好的。本文引入了关于基因和条件双聚类或者说同时聚类这一概念和从表达数据中知识发现的概念。由于该方法允许自动发现基于属性子集的相似性，同时对条件及基因进行聚类和对重叠分组（它提供了一种对有多重功能或者被多种因素调控的基因更好的表示方式），使得它克服了和传统聚类算法相关的一些问题。论文内容概要：本文首先分析了传统聚类算法处理表达数据时的缺点：首先是传统聚类算法在对基因聚类时为了衡量基因间的相似性要利用基因在所有条件下的表达水平，也就是说对所有的条件给予相同的权重；或者是在对实验条件聚类时要利用所有基因在该条件下的表达水平，也就是给所有的基因同样的权重，这种对所有基因或条件同等对待的方法使得不能发现表达矩阵数据中的所有相似的基因组或条件组。第二是因为传统的聚类算法将基因只能分在一个聚类中从而人为的认定每一个基因只有单一的功能，然而这是和实际的情况冲突的，现实中大量基因承担了在不同的条件下或时间下承担了不同的功能，也就是具有不同的通路。基于上述传统聚类算法的缺点，在本文中提出了一个双聚类的概念，双聚类就是指具有按高度相似性的一组基因子集和一组条件子集。随后作者引入了均方残差（ mean square residue,MSR ）作为这种相似性的度量准则，并进行了相关的定义。这样从理论上指明了寻找双聚类的过程就是搜索表达矩阵找到使得 MSR 最小的所有子矩阵的过程。随后作者指出这样的一个最优的寻找过程等价于在一个二分图中寻找最大二分图极大团问题，并且该问题已经被证明是 NP 难的。但随后作者也指出在现实分析中并不需要搜索到最大的最优的双聚类，我们只要找到在一些特定条件下的一组基因具有共同上调或下调就行了。随后本文对 MSR 进行了严格的数学定义，并证明了寻找最大的低于指定阈值的双聚类是 NP 难的。然而由于要找到的双聚类并不需要是最大的，所以本方使用贪心算法给出了最基本的寻找双聚类的算法 - 算法 0 。算法 0 简述如下：算法 0 ( 蛮力删除和增加算法 ) 输入：一个实值矩阵，一个最大可接受的均方残差值。输出：一个均方残差不大于的用行集和列集表示的 - 双聚类。初始化：行集和列集分别用整个表达矩阵的基因集和条件集来初始化，即：。迭代： 1. 计算增加或删除任一行或列后得到的子矩阵的均方残差，选择相对原来均方残差来说减少最快的哪个操作，如果没有一个操作使得均方残差降低，或者，就返回随后分析了算法的复杂度是，其中和分别是表达矩阵的行数和列数。接下来对算法 0 进行了优化提出了时间复杂度为的算法 1 ，其详细内容如下：算法 1 （单点删除）输入：一个实值矩阵，一个最大可接受的均方残差值。输出：一个均方残差不大于的用行集和列集表示的 - 双聚类。初始化：行集和列集分别用整个表达矩阵的基因集和条件集来初始化，即：。迭代： 1. 对双聚类对应的行集分别计算其行平均值，，对其列集分别计算其列平均值，，计算其全体平均值，并计算其均方残差。如果，则返回双聚类。 2. 在行集中寻找使得最大的行，在列集中寻找使得最大的列，经比较后得出二者当中的最大值所对应的行或列，并在该双聚类删除这个最大值所对应的行或列后更新行集和列集。并给出了严格的数学证明（不过要注意的这些数学证明仅是对相似准则为 MSR 的时候才成立，换成其它相似度量准则的话就要重新证明了）。由于在算法 1 中每次只能删除表达矩阵中的一行或一列，使得算法搜索过程较慢，为了找到提高搜索速度，本文随后又提出了多点删除算法 2 并给出了数学证明，详细步骤如下：算法 2 （多点删除）输入：一个实值矩阵，一个最大可接受的均方残差值。一个多点删除的阈值。输出：一个均方残差不大于的用行集和列集表示的 - 双聚类。初始化：行集和列集分别用整个表达矩阵的基因集和条件集来初始化，即：。迭代： 1. 对双聚类对应的行集分别计算其行平均值，，对其列集分别计算其列平均值，，计算其全体平均值，并计算其均方残差。如果，则返回双聚类。 2. 删除双聚类中所有满足如下条件的行：。 3 重新计算双聚类中每列的列平均值，和全体平均值以及均方残差。 4. 删除双聚类中所有满足如下条件的列：。 5. 如果在本次迭代中如果没有满足上述的条件行或列，则调用算法 1. 随后本文分析了进行节点删除算法得到的双聚类可以增加特定的行或列而使得 MSR 不增加从而尽可能的得到较大的双聚类，并进行了相关的数学证明，提出了节点增加算法 3 ：算法 3 （节点增加）输入：一个实值矩阵，和一个用和表示的双聚类输出：一个用和表示的双聚类，其中，，并且满足。迭代： 1. 对双聚类中所有的行计算其行平均值，对其中所有的列计算列平均值，以及全体平均值和其对应的均方残差值。 2. 把满足如下条件的列集和都添加到双聚类的列集中。 3. 重新计算双聚类中每行的行平均值，整体平均值及其均方残差值。 4. 把满足如下条件的行集和都添加到双聚类的行集中。 5. 对不在双聚类行集中的每行，如果满足如下条件，也添加到双聚类的行集中。 6. 如果没有行或列可添加，则把最终的和作为和返回。最后为了找到给定数量的双聚类，论文整合了前面的算法给出了发现指定数量的双聚类算法 4 ，其描述如下：算法 4 （找出给定数目的双聚类）输入：可能有缺失值的实值矩阵，用于多点删除的参数，最大可接受的均方残差值和要找的双聚类数目。输出：中的个双聚类。初始化：中的缺失值用随机数来代替，这些随机数取值范围是中非空值的取值范围。是的一个副本。迭代（次）： 1. ，和作为输入参数来调用多点删除算法 2 。如果行或列的个数太小（小于 100 ）就不再针对行或列执行多点删除算法 2 ，这得到的矩阵是。 2. （算法 2 的第五步）和作为输入参数来调用单点删除算法 1 ，经单点删除算法得到矩阵。 3. 和作为输入参数调用算法 3 ，得到矩阵。 4. 返回，并把在又在中的元素用随机数代替。在算法 4 中由于算法执行的确定性，所以为了防止多次运行搜索到的都是基本相同的双聚类，对找到的双聚类用随机数进行覆盖并采用酵母数据集和人类 B 细胞数据集对算法进行了测试并和传统聚类算法结果进行了比较。论文结论：双聚类算法相对单聚类来说有好几个明显的优势。首先是双聚类自动地选择具有较一致的基因和条件，丢弃代表随机的噪音。这提供了一个方法来处理缺失数据和不准确的数据。第二，双聚类基于一个依赖于应用背景的相似性度量标准来分类的，而这个标准是根据属性的子集来定义的。它不仅发现分组，而且也能发现分组适用的背景，在一定程度上，这二者之间是不可分隔的且可以交换的，这是双聚类算法和先单聚类列再单聚类行的算法的主要区别。大多数表达矩阵来自于或多或少的完整的基因集，但其可能的条件是非常少的。任何基于可用条件的基因的相似性度量标准变得依赖于背景的。像这种基于准则的基因单聚类是没有双聚类算法那么有代表性。第三，双聚类算法允许行和列被包含在多个双聚类中，从而允许一个基因或条件被多个功能分类所确定。这附加的灵活性正确的反映了在组织样本和实验条件下基因功能多样性和重叠因素这一事实。通过证明该问题是一个 NP 难问题，我们尽力证明提出的算法的有效性和贪婪性。但由于问题的本质是 NP 难的，这就意味着有相当数量的具有很好度量标准的双聚类不能被任何有效的算法发现。和大多数有效的传统聚类算法一样，可以说最佳的双聚类能在大多数情况下能发现，但不能总在所在的情况下都能发现。论文的创新之处： 1，提出了双聚类的概念并结合贪心算法给出了相应的算法。 2，提出了 MSR 作为基因相似性的衡量标准。 3，对缺失数据的处理采用了随机数代替。 4，为了防止找到重复的双聚类，采用了随机数来屏蔽已经找到的双聚类 5，提出了使用双聚类的 MSR 和体积作为衡量双聚类算法结果的标准。论文的不足之处： 1，防止重复的策略会带来更大的随机干扰效应。 2，很难发现重叠的双聚类。; 9468 次阅读|0 个评论

寻找致癌基因: 基因表达数据的双聚类: shamolvzhou79 2011-11-15 19:28; 基于基因表达数据寻找致癌基因 , 尝试癌症的早期诊断和基因治疗是系统生物学领域的一个经典问题 . 实际上 , 许多基因仅仅是在某些类型的肿瘤中异常表达 ( 高表达或者低表达 ), 而在其它类型的肿瘤疾病中不异常表达 , 因此探测基因 - 肿瘤的高度相关结构对于癌症病理学的研究有重要意义 . 数据挖掘领域中的双聚类问题就是据此抽象出来的 ( ). 我们提出了一种新的双聚类模型 --- 二值矩阵分解模型 (binary matrix factorization, BMF). 我们将 BMF 应用于基因表达数据中来寻找在特定肿瘤中异常表达的基因 , 取得了极好的结果 : 我们的肿瘤诊断正确率提高了十五个百分点左右 , 而寻找的特异表达基因占总数百分比下降了五十个百分点左右 ( 这意味着通过更少的基因我们就更好地诊断了肿瘤 , 说明找到的基因更具特异性 , 并且在未来应用中可以更经济 ). 简单来说 , 我们有三个方面的工作值得一提 : 1. 在理论方面，给出了界值性质，该性质揭示了两类最流行的矩阵分解模型：非负矩阵分解模型和主成分分析模型 ( 奇异值分解 ) 之间的区别。非负矩阵分解是聚类分析领域中的一项新技术，其与奇异值分解的一个最显著不同在于非负矩阵分解有非负性的约束，但是该约束的本质含义是什么，一直以来还缺乏理论上的研究，我们给出的界值性质在很大程度上解决了这一问题 ; 2. 在算法方面，为二值矩阵分解模型设计了两种算法，即罚函数方法和阈值方法，并对它们的数值表现进行了系统比较，阐明了它们各自适用的情况 ; 3. 在应用方面，我们将二值矩阵分解模型成功地应用于基因表达数据的双聚类分析，结果表明，该模型与同类模型相比，提高计算精度十五个百分点以上 ( 作为参照，我们的结果还和聚类模型 nsNMF, NMF/R 进行了比较，结果也是我们的模型计算结果最好，而且 nsNMF 和 NMF/R 不能给出精确的双聚类结构 ) ，提高了结果的稀疏化水平约二十到五十五个百分点 ( 依数据而定 ) ，统计学分析表明我们给出的计算结果具有生物显著性 . 二值矩阵分解模型作为聚类分析领域中的新模型，其在文本挖掘、观点分析、股票市场走势分析等领域都有广阔的应用前景。文章地址 : http://www.springerlink.com/content/y62142r517762595/?p=63070935b51d4d4aaef31c7a3378841epi=4 Cheng Y, Church G (2000) Biclustering of expression data. In: Proceedings of the 8th international conference on intelligent systems for molecular biology: 93 – 103; 5995 次阅读|0 个评论

词和论文同时聚类告诉我们什么了？: 热度 1 zilu85 2010-11-19 09:55; 最初的目的，是想研究一下如何利用主题词关联规则从文章中抽取informative sentence。首先，选定一个主题阿司匹林引起胃肠道出血，在PubMed中输入了检索词： Aspirin/adverse effects AND Gastrointestinal Hemorrhage/chemically induced 并限定要有文摘的文献记录，得到了141条记录。对这141条记录抽取了主题词并进行了统计，截取出现频次高于5次的主题词，得到了一个数据矩阵，局部如下：其中的行是高频主题词12个，其中的列是相关的论文若干（141篇中，涉及到12个高频主题词中任何一个的文献记录）。然后，用gCLUTO进行聚类，就是对词和文章的同时聚类，得到了聚类结果，对其中部分内容进行可视化表达，局部如下：正中间是小格子，可以叫做矩阵可视化，红颜色表示出现，白色的是没有出现。右侧的是被聚类的三个主题词，左侧则它们的是聚类树图。下侧是文献记录的标号，而上方则是这些文献聚类树图。这里显示的是3个词被聚类在一起，胃疾病/化学引起（Stomach Diseases/chemically induced），胃粘膜/药物作用（Gastric Mucosa/drug effects），阿司匹林/毒性（Aspirin/toxicity）。最有意思的是，这个图形清晰地展示出聚类分析是如何进行的：：这三个词，胃粘膜/药物作用和阿司匹林/毒性由于它们在371629，2813856，和3259918号文献记录上共现而首先聚集在一起。然后，胃粘膜/药物作用又和胃疾病/化学引起聚类在一起，从标记为红色的方块可以看出，它们是因为同时在2509266和1888645两篇论文中同时出现而被聚类在一起的。然后就是问题，其实阿司匹林/毒性与胃疾病/化学引起这两个词根本就没有在这些文章中共同出现过，全图如下：双聚类中显示出来的虚假联系，说明了什么？这是好事还是坏事？如果说是虚假联系，这是坏事。如果说是潜在的联系，这是好事。我比较倾向于好事，因为：第一，这三个词确实能够解释为：阿司匹林药物对胃粘膜的毒性作用引起胃部疾病，其语义关系相当明确。第二，通过共现的论文查看，这些论文（被称作对该类别描述度比较强的属性）也确实介绍了对阿司匹林的胃粘膜毒性作用引起胃疾病的预防。其实这几篇论文的实际内容更为复杂，大致的内容是：为治疗心血管疾病服用阿司匹林，阿司匹林对胃粘膜有毒性作用引起胃疾病，然后用某种药物进行预防。第三，我相信这两个非相关的词是通过模式上的相似性而聚集到一起的。这与Swanson的非相关互补文献是否为一个原理呢？如果扩大范围（文献量和主题覆盖面，以及高频词的阈值），是不是会有更多发现呢？能吗？比如中西医结合的主题？局限性：这个检索刚开始限定了带有文摘，同时检索的是主要主题词。同时，如果范围过大，超出了聚类分析合理性的范围，也会很荒谬的哟。后来，我用一个比较大的范围的主题重新试验了一下，比较失望，表现的都是很合理的语义关系。不急，哪有随随便便成功的呢，慢慢来吧。; 个人分类: 休闲|6263 次阅读|2 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 双聚类

相关帖子

相关日志

关闭安全验证