马博双聚类-PPT课件.pptx

双聚类在生物信息大数据的应用1分类？2聚类？3聚类VS分类分类与聚类的区别：在分类中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。聚类分析也称无监督学习或无指导学习，聚类的样本没有标记，需要由聚类学习算法来自动确定。4聚类算法划分方法：K-means层次方法：BIRCH基于密度的方法：DBSCAN、OPTICS、DENCLUE基于网格的方法：STING、CLIQUE5K-MEANS算法6K-MEANS算法缺点？7Big data=“Large-scale dataBig data=“Large-scale data”+“Complex types data+“Complex types data”聚类的应用金融通信社交医疗基因气候B Bi ig g d da at ta a e ex xi is st t i in n v va ar ri io ou us s a ar re ea as s8生物信息大数据生物信息学是一门重要的交叉学科，又称作基因组信息学如何从海量基因数据中获取有效信息成为生物信息学迫切要解决的问题序列分析、基因表达等为数据挖掘提供了广阔的研究空间数据挖掘技术帮助人们了解生物数据所代表的生物学意义9基因表达数据可以用矩阵形式表示，用行集合来代表基因集合，用列集合代表各种实验条件，其中的每个元素表示某个基因在某个给定条件下的表达水平值。10传统的聚类技术如k-means和hierarchical clustering等已经被广泛地用于基因表达数据的分析。该技术根据基因在所有条件下表达模式的相似性，把基因分成互不相交的子集，每一个子集对应于一个簇，并认为在同一个簇中的基因具有相同的管理机制或生物功能。缺陷：部分基因可能只在某一特定的条件子集下具有相似的表达模式(只对行或者列来进行聚类)一个基因可能参加不止一个生物过程，因此一个基因可能属于多个基因簇11 双聚类算法为了克服传统聚类的缺陷，大量的双聚类算法也相继被提出。双聚类算法通过对行集合和列集合同时进行聚类，寻找在特定条件子集下显示了相似表达模式的基因集。12聚类和双聚类的比较13双聚类的分类14CC算法 CC算法是双聚类算法的鼻祖 目的是为了在基因表达值矩阵中寻找子矩阵，使得子矩阵中的表达值水平具有高度一致性。定义了一个均方残差用以衡量一个双聚类的一致相关性，并提出一个贪心算法对基因和条件进行行、列交替删除操作，最终找到具有低均方残差值的子矩阵，并且每次只能产生一个双聚类，并且用随机数来代替原来的值，如此重复。缺点：此方法具有很大的不确定性，即使是同样的参数在两次实验中将会得到不同的结果，而且此法是一种贪心算法，不能确保找出所有的双聚类。15基于模式的双聚类因为基因表达矩阵通常维度很高，而传统的聚类如k-means、hierarchical clustering在识别这些只有部分子集的表达值模式方法方面非常困难。近年来，基于模式的双聚类模型（Pattern-based biclustering model），这种使用模式相似性（pattern similarity）而不使用距离相似性（distance similarity）进行聚类的模型，已经广泛应用于包括基因表达值分析，自动推荐系统，定向营销等多个方面。16OPSM算法 “保序子矩阵”（order preserving submatrix），简称OPSM，是一种基于模式的双聚类。一个矩阵的子矩阵是OPSM需满足的条件是对于该子矩阵，存在一个列排列，使得该子矩阵中的所有行在这个排列下都是严格单调递增的。即该模式关注数据矩阵中元素之间相对大小在不同列下的一致性，忽略实际的元素值大小。17OPSM算法18关联规则关联规则挖掘:在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。规则形式：“Head Bodysupport,confidence”.buys(x,“diapers”)buys(x,“beers”)0.5%,60%应用：顾客购物分析、目录设计、商品广告邮寄分析、追加销售、商品货架设计、仓储规划、网络故障分析以及根据购买模式对用户进行分类,医疗诊断,医药销售19规则度量：支持度与可信度买尿布的客尿布的客户二者都二者都买的客的客户买啤酒的客啤酒的客户查找所有的找所有的规则 X Y 具有最小具有最小支支持度持度和和可信度可信度支持度支持度 s:一次交易中包含一次交易中包含X、Y的的可能性可能性可信度可信度 c,包含包含X的交易中也包含的交易中也包含Y的的条件条件概率概率设最小支持度最小支持度为50%,最小可信度最小可信度为 50%,则可得到可得到A C (50%,66.6%)C A (50%,100%)20购物分析 作为商家主管，想了解顾客的购物习惯，尤其希望了解在一次购物过程中，哪些商品会在一起被购买，这就需要进行市场货物分析，即对顾客在商场购物交易记录数据进行分析，分析的结果可帮助商家制定有效的营销策略。21记录号购物清单1啤酒，尿布，婴儿爽身粉，面包，雨伞2尿布，婴儿爽身粉3啤酒，尿布，牛奶4尿布，啤酒，洗衣粉5啤酒，牛奶，可乐(coke)R1：啤酒尿布，supp=60%，conf=0.6/0.8=75%。R2：尿布啤酒，supp=60%，conf=0.6/0.8=75%。R3：牛奶啤酒，supp=40%，conf=0.4/0.4=100%。R4：啤酒牛奶，supp=40%，conf=0.4/0.8=50%。R5：尿布婴儿爽身粉，supp=40%，conf=0.4/0.8=50%。R6：婴儿爽身粉尿布，supp=40%，conf=0.4/0.4=100%。单 项 集支 持 度双 项 集支 持 度啤酒4/5啤酒，尿布3/5尿布4/5啤酒，牛奶2/5婴儿爽身粉2/5尿布，婴儿爽身粉2/5牛奶2/522如果把商店中所有销售商品设为一个集合，则每种商品（Item)可看成一个布尔变量，表示该商品是否被购买。每次购物可用一个布尔向量表示。这样就可以分析布尔向量，得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示：Buys(X,”computer”)Buys(X,”financial_management_software”)support=2%,confidence=60%规则的支持度和置信度是两个规则兴趣度度量,分别反映发现规则的有用性和确定性。如果关联规则满足最小支持度阈值和最小置信度阈值，则该关联规则被认为是有趣的。23Apriori算法典型的关联规则算法是R.Agrawal等1994年提出的Apriori算法。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。24项的集合同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）的规则称作强规则。项的集合称为项集(itemset)。包含k个项的项集称为k-项集。集合computer，financial_management_software是一个2-项集。项集的出现频率是包含项集的事务数(支持计数或计数)。如果项集的出现频率大于或等于min_sup与D中事务总数的乘积,则称该项集满足最小支持度min_sup。如果项集满足最小支持度，则称它为频繁项集(frequent itemset)。频繁k-项集的集合通常记作Lk。25关联规则挖掘例子最小支持度 50%最小可信度 50%对于 A C：support=support(A、C)=50%confidence=support(CA)/support(A)=66.6%26Apriori算法分两步进行：（1）找出所有频繁数据项集，即找出所有支持度超过指定阈值的数据项集。（2）利用频繁数据项集，生成侯选的关联规则，并验证其可信度。如果可信度超过指定阈值，则该侯选关联规则为要找的关联规则Apriori的基本思想:频繁项集的任何子集也一定是频繁的 Apriori使用一种称作逐层搜索的迭代方法，利用k-项集来产生(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作 L1。然后利用L1找频繁2-项集的集合L2，如此不断循环下去，直到不能找到频繁k-项集。每挖掘一层Lk,就需要扫描整个数据库。27为提高频繁项集逐层产生的效率，Apriori算法利用Apriori性质压缩搜索空间。Apriori性质：频繁项集的所有非空子集都必须也是频繁的。根据定义，如果项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P(I)min_sup。如果项A添加到I，则结果项集（AI）不可能比I更频繁出现。因此，也不是频繁的，即P（AI）min_sup。根据逆反公理：如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。即：任何非频繁的(k-1)-项集都不可能是频繁k-项集的子集。28例：交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。29301)计算C1并计数.在算法的第一次迭代，每个项都是候选1-项集的集合的成员。扫描所有的事务，对每个事务出现次数计数。2)确定L1.假定最小事务支持计数为2（即min_sup=2/9=22%）。可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。313）生成C2 为发现频繁2-项集的集合，算法使用产生候选2-项集的集合。由多个2-项集组成。4）计算C2中成员出现的次数 扫描D中事务，计算中每个候选项集的支持计数，5）由C2确定L2 确定频繁2-项集的集合，它由具有最小支持度的候选2-项集组成。6）候选3-项集的集合的产生如下表5-2所示：32表5-2337)扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成 8)算法使用L3L3 产生候选4-项集的集合C4。C4=I1，I2，I3，I5，因为它的子集I2,I3，I5不是频繁的，这个项集被剪去，这样C4=，因此算法终止，找出了所有的频繁项集。34例：假定数据包含频繁项集I=I1,I2,I5(计数2)，可以由I产生哪些关联规则？I的非空子集有:I1,I2,I1,I5,I2,I5,I1,I2和I5，其频繁数分别为：4，2，2，6，7，235 结果关联规则如下，每个都列出置信度 （1）I1I2I5，confidence=24=50 （2）I1I5I2，confidence=22=100 （3）I2I5I1，confidence=22=100 （4）I1 I2 I5，confidence=26=33 （5）I2 I1 I5，confidence=27=29 （6）I5 I2 I，confidence=22=100 如果最小置信度阈值为70，则只有第2、3和最后一个规则可以输出，因为只有这些是产生的强规则。36序列模式挖掘 序列模式挖掘(sequential pattern mining）是指挖掘相对时间出现频率高的模式例子1：在两年前购买了Ford 牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒37序列模式 VS 关联规则 问题序列模式挖掘关联规则挖掘数据集序列数据库事务数据库关注点单项间在同一事务内以及事务间的关系单项间在同一事务内的关系关联规则挖掘不考虑事务间的顺序，序列模式挖掘注重事务间的顺序38通过序列模式寻找OPSM 在数据预处理阶段，如果对于矩阵中的每一行，我们把所有的值按升序排列，用对应的列标号替代原来的值，原始矩阵转化为一个序列数据集。如果数据矩阵有相同值，我们默认把出现较早的那个排在前面。如果一个序列的支持度大于预先定义的支持度阈值，则称这个序列模式是频繁的。因此，OPSM挖掘问题可以简化为频繁序列模式挖掘问题的一个特例。每一个频繁的序列模式唯一地定义一个OPSM，该序列的模式为OPSM的列，支持该模式的序列为OPSM的行。39通过序列模式寻找OPSM例如，4，2序列的支持度为4（row1，2，3，4），4，3，2的支持度为3（row2，3，4）如果对于矩阵中的每一行，我们把所有的值按升序排列，用对应的列标号替代原来的值，原始矩阵转化为一个序列数据集。如果数据矩阵有相同值，我们默认把出现较早的那个排在前面40OPSM的算法两个子矩阵可以合并只要满足下列条件：它们都是OPSM。它们中的其中一个的前面length-k-2的子pattern和另一个的后面length-k-2的子pattern必须是完全一样的。Length为子矩阵的列长度。（ABC和BCD可以合并成ABCD）它们行号集合的交集中的行标数必须满足大于或者等于行支持度阈值41OPSM的算法任取一行作为参考行，列置换之后成为递增序列，任取两个列号，生成全部的length-2 pattern，之后将其合并为length-3 pattern，重复此步骤，直到不能生成满足条件的模式。缺点：为了精简算法复杂度，把行阈值设置的较大，可能忽略掉一些有生物意义的双聚类。42Deep OPSM 指那些序列很长但是行支持度很小的模式。对行阈值的要求不高。它们不仅对解释基因调控网络有非常重要的作用，而且具有关键的生物意义。43Deep OPSM利用任意两行的所有公共子序列可以有效挖掘Deep OPSMs44Deep OPSM 45 通过上面的算法可以有效的挖掘所有公共子序列，但是时间和空间复杂度都十分庞大。使用前缀树的数据结构与算法结合可以减少复杂度。46前缀树 一棵 2-候选树47设置行阈值为3后，得到的2-频繁树如下。请大家写出前两个节点为5和4的3-频繁树分支。48 3-候选树49 阈值为3的3-频繁树50515253