高效高维数据集巨闭项集挖掘算法方面的研究及应用

沙特国王大学学报一种高效的高维数据集巨型闭项集挖掘算法曼朱纳特湾Vanahalli，Nagamma Patil印度卡纳塔克邦国家技术学院阿提奇莱因福奥文章历史记录：收到2019年2020年2月27日修订2020年4月8日接受2020年4月17日网上发售关键词：决策生物信息学行集接近度检查剪枝策略高维挖掘搜索空间A B S T R A C T生物信息学领域的研究兴趣越来越大，不同领域的大量可用数据为生成高维数据集铺平了道路。高维数据集中的特征数量多，行数少，频繁巨闭项集（FCCI）对于各种应用和生物信息学领域具有重要意义。FCCI在决策过程中起着非常重要的作用。从高维数据集中提取信息量是巨大的，并且这种提取是一项不平凡的任务。所有不可接受的特征和行的修剪不由最先进的算法执行。提出的工作阐明了所有的不可接受的功能和行，一个有效的修剪策略，修剪的行枚举挖掘搜索空间和封闭方法检查行集的封闭性修剪。设计了一种高效的行枚举算法，结合行集闭包检查方法和剪枝策略，有效地挖掘FCCI完备集。实验结果表明，修剪所有的不可接受的功能和行的有效性©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍关联规则挖掘（ARM）最基本、最突出的部分项集挖掘的应用非常广泛，并且已经在各个领域得到了广泛的应用。 客户分析、文本分析、化合物预测、网络分析、毒理学分析、时空分析、核糖核酸（RNA）分析、检测事件和软件错误是一些应用（Aggarwal，2014;Li等人，2001; Naulaerts等人，2015; Parsons等人，2004; Silva等人，2016; Yin和Han，2003; Zhong等人，2012年）。最初的研究集中在设计有效的频繁项集挖掘（Frequent Itemset Mining，简称 频 繁 项 集 挖 掘 ） 算 法 （ Han et al. ， 2000; Lin 等 人 ， 2014;Tanbeer等人，2009;Yildiz和Selale，2011）来从事务数据集中提取频繁出现的项集。这些挖掘算法在挖掘频繁出现的*通讯作者。电 子 邮 件 地 址 ： manjunath.k.gmail.com （ M.K.Vanahalli ） ， nagam-mapatil@nitk.edu.in（N. 帕蒂尔）。沙特国王大学负责同行审查大型事务数据集的项集。通过设计并行和分布式并行算法克服了顺序并行 算 法 的 缺 点 （ Lin 和 Deng ， 2010; Lin 和 Lo ， 2013; Sohrabi 和Barforoush，2013; Yu和Zhou，2010）。频繁项集的大集合产生冗余规则，这导致频繁闭项集挖掘的研究。研究人员专注于设计算法（Apiletti等人，2015;Lucchese等人，2006; Uno等人，2004; Wang等人，2003; Wang例如，2012年; Zaki和Hsiao，2005年），用于从交易数据集中挖掘频繁闭项集（FCI）。事务数据集中的特征数量非常少，而行数更多。这些串行和并行算法从事务数据集中挖掘FCI所采用的项集空间搜索方法使这些算法成为基于特征枚举的算法。传统的串行和并行算法在挖掘大型事务数据集的FCI时，运行时间呈指数级增长。平均事务长度的增加是传统的顺序和并行算法效率低下的主要原因。各领域海量数据的存在和生物信息学的数据集中具有高维度的特征的数量非常高，并且行数较少。这些高维数据集和事务数据集的特征彼此不同。信息提取量https://doi.org/10.1016/j.jksuci.2020.04.0081319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comM.K. Vanahalli，N.Patil/ Journal of King Saud University2799具有高维度的数据集是巨大的，并且这种提取是一项重要的任务。传统的基于特征枚举的顺序（Lucchese等人，2006; Uno等人，2004;Wang等人，2003; Zaki和Hsiao，2005）和并行算法（Apiletti等人，2015; Lucchese等人，2007; Negrevergne等人， 2010;Wang等人，2012）在从高维数据集中挖掘FCI时效率低下。研究人员设计了基于顺序行枚举的算法，如Carpenter（Pan等人，2003）、TD-Close（Liu等人， 2006）和TDD-Close（Liu等人，2009），以克服特征枚举算法在从高维数据集中提取FCI时的效率低下。COBBLER算法（Pan等人，2004）提出了一种结合行枚举和特征枚举的FCI挖掘方法。许多应用的完整和重要信息（Alves等人，2009;Carmona-Saez等人，2006年; Koyutürk等人，2006; Manda等人，2012;Naulaerts等人，2015; Nguyen等人，2017; Nguyen等人，2016;Nguyen 等 人 ， 2017; Okubo 和 Haraguchi ， 2012; Sohrabi 和Barforoush，2012; Zhu等人，2007; Zulkurnain等人，2012年）不能从大量的小型和平均大小的FCI中获取。规则项集挖掘算法需要花费大量的时间来挖掘大量的小而平均的频繁项集。ARM为处理高维数据集的应用程序提供了对巨大项集的更高兴趣（Alves等人，2009; Naulaerts等人，2015; Nguyen等人，2017;Nguyen等人，2016; Nguyen等人，2017; Okubo和Haraguchi，2012; Sohrabi和Barforoush，2012; Zhu等人，2007; Zulkurnain等人，2012年）。对于许多应用，巨大的项集在决策过程中非常重要并且非常有影响力（Carmona-Saez等人，2006年; Koyutürk等人，2006; Manda等人，2012; Yoon和Lee，2012）。从高维生物数据集中挖掘colosal项集的重要性由Naulaerts etal.（2015）和Alves et al.（2009）证明。现有的特征枚举和行枚举FCI挖掘算法所花费的时间的指数量（Apiletti等人，2015年;Liu等人，2006; Liu等人，2009; Lucchese等人，2006; Lucchese等人，2007; Negrevergne等人，2010; Pan等人，2003; Pan等人，2004;Uno 等 人 ， 2004; Vimietry 和 Moscato ， 2014; Wang 等 人 ， 2003;Wang等人，2012; Zaki and Hsiao，2005）在提取短项集和平均项集方面的局限性使得它们不适合从高维数据集中提取频繁大型闭合项集（FCCI）。第一个巨型项集挖掘算法是由Zhu等人（2007年）。模式融合算法采用近似的方法挖掘庞大的项目集。模式融合算法由于采用了近似方法，无法挖掘出所有庞大的项目集。所有的关联规则都不会被生成，这会影响决策。BVBUC算法不 会 挖 掘 所 有 的 colos-sal 项 集 和 巨 大 的 闭 项 集 （ Sohrabi andBarforoush，2012）。不会生成所有关联规则，这会影响决策。从BVBUC中挖掘出的大规模闭项集的支持信息大多是错误的。这就产生了不正确的关联规则，影响了决策。Zulkurnain等人（2012）提出了一种DisClose算法，该算法利用CompactRow树（CR-tree）从高维数据集中挖掘FCCI。在从高维数据集挖掘FCCI的过程中，现有的算法没有对所有不可接受的特征和行进行剪枝。这会以指数方式增加行枚举挖掘搜索空间，并使算法效率低下。现有的FCCI挖掘算法（Sohrabi和Barforoush，2012; Zhu等人，2007;Zulkurnain等人，2012）不包括用于削减行枚举挖掘搜索空间的有效修剪方法和用于检查行集的封闭性的有效封闭方法。针对现有算法的不足，提出了一种有效的比特集频繁巨闭项集挖掘算法（BSFCCIM），用于从具有高重复度DHD的数据集中挖掘所有的FCCI。该算法在从DHD中挖掘FCCI之前，先从DHD中删除所有不可接受的特征和不可接受的行，这是现有工作的缺点之一。最小支持度阈值有效地去除了不可接受的特征，最小基数阈值有效地去除了不可接受的行。该算法通过自底向上遍历行枚举树，有效地从DHD中挖掘FCCI。使用深度优先搜索遍历自底向上的行枚举树的分支来挖掘FCCI。算法中还附有行集闭包法，用于检查行集的封闭性.如果行集闭包方法指示行集已关闭，则从行集中提取的项集将关闭。所提出的行集闭包检查方法利用该特定行集上的rsid的更新基数。该算法还附有修剪策略，有效地剪掉行枚举树中不产生FCCI的节点。剪枝策略不需要遍历后代节点，而是从这些节点中获取待挖掘项集的基数信息，这是现有工作的缺点之一。所提出的算法利用了计算速度快的位集方法。实验结果表明，BSFCCIM算法具有高效的剪枝策略和行集闭包检查方法，性能优于现有算法。2. 相关工作对项集挖掘的各个领域进行了详细的研究。使用频繁项集挖掘和关联规则挖掘来解决各种数据域的问题（Aggarwal，2014; Li等人，2001; Naulaerts等人，2015; Parsons等人，2004;Silva等人，2016;Yin和Han，2003; Zhong等人，2012年）。通过许多有效设计的顺序算法（Han等人，2000; Lin等人，2014; Tanbeer等人，2009; Yildiz和Selale，2011）。由于平均事务长度的增加，运行时间呈指数级增加，因此顺序并行算法效率低下。并行算法（Lin和Deng，2010; Lin和Lo，2013; Sohrabi和Barforoush，2013; Yu和Zhou，2010）是由于大型事务数据集无法通过顺序并行算法有效处理而设计的。针对从事务数据集中挖掘出的大量频繁项集产生的冗余规则，提出了频繁闭项集的概念。研究人员专注于设计基于特征枚举的FCI挖掘算法（Apiletti等人，2015; Lucchese等人，2006; Uno等人，2004;Wang等人，2003;Wang等人，2012; Zaki and Hsiao，2005）.由于高维数据集的数据特性，使用基于特征枚举的算法从高维数据集中挖掘FCI的计算量很大。通过设计基于行枚举的算法来处理从具有高维度的数据集挖掘FCI的计算复杂性（Liu等人，2006; Liu等人，2009; Pan等人，2003; Pan等人，2004年; Vimietry和Moscato，2014年）。这些基于行枚举的算法遍历行集空间，从高维数据集中提取FCI。利用现有的基于行枚举的FCI算法，从高维数据集中挖掘出大量的中小型FCI。大量的中小型项目集包含有限的信息，可用于各种应用。巨项集为各种应用提供了非常重要的信息，并且在决策过程中也具有很大的 重要性（Alves等人，二○ ○九年;2800M.K. Vanahalli，N.Patil/ Journal of King Saud UniversityNaulaerts 等 人 ， 2015; Nguyen 等 人 ， 2017; Nguyen 等 人 ，2016;Nguyen等人，2017; Sohrabi和Barforoush，2012; Zhu等人，2007; Zulkurnain等人， 2012年）。现 有 的 FCCI 利 用 基 于 行 枚 举 和 特 征 枚 举 的 方 法 （ Sohrabi 和Barforoush，2012; Zhu等人，2007; Zulkurnain等人，2012）和频繁庞 大 项 集 挖 掘 算 法 （ Nguyen et al. ， 2017; Nguyen 等 人 ，2016;Nguyen 等 人 ， 2017; Okubo 和 Haraguchi ， 2012; Sohrabi 和Barforoush，2012; Zhu等人，2007年）。事务数据集的数据特性使得基于特征枚举的方法最适合从事务数据集中挖掘FCCI和频繁巨项集。现有的基于特征枚举的FCCI和频繁巨项集挖掘算法不能有效地从高维数据集中删除所有不可接受的特征和行。巨大项集的概念是由Zhu等人（2007）通过模式融合算法提出的。模式融合算法采用的是基于特征枚举的方法，在处理高维数据时效率低下。算法（Vanahalli和Patil，2016; Vanahalli和Patil，2018; Vanahalli和Patil，2019）从高维数据集中挖掘大基数项集。Nguyen et al.（2017）提出了基于行分类的CP-Miner和PCP-Miner算法，用于从高维数据集中挖掘频繁的巨大项集。FCCI是针对频繁巨项集产生冗余规则而提出的。CP-Miner和PCP-Miner不从数据集中挖掘FCCI由于它 只挖掘频繁 的巨大项目 集，因此具 有高维性 。Sohrabi和Barforoush（2012）的BVBUC算法和Zulkurnain等人（2012）的DisClose算法利用基于行枚举的方法从具有高维度的数据集中挖掘FCCI。通过BVBUC算法对行枚举树中minsup层之后的搜索空间进行剪枝，从只属于minsup层的行集中挖掘FCCI。BVBUC算法不会挖掘出所有的巨型项集和巨型闭项集。所有的关联规则将不会被生成，这影响了决策。从BVBUC中挖掘出的大规模闭项集的支持信息大多是错误的。这会产生不正确的关联规则并影响决策。在对高维数据集进行FCCI挖掘之前，必须对所有不可接受的特征和行进行剪枝。在进行从高维数据集挖掘FCCI的过程之前，所有不可接受的特征和行的修剪不是由最先进的算法执行的。这以指数方式增加了行分层的挖掘搜索空间，并使算法效率低下。现有的FCCI挖掘算法不包括一个有效的修剪方法来削减行枚举挖掘搜索空间和一个有效的封闭方法来检查行集的封闭3. 预赛设数据集为高维数据集，DHD（R，F）有m个基因行（样本），R={gr1;gr2，，gr m}和n个基因特征F ={gf1;gf2，，gf n}。唯一的行（示例）标识符为DHD的每行gri提供特征集（rsid），并且每行中存在一组特征。项目集X是基因特征的集合，X∈GF。具有d个基因特征的项集称为d-itemset。由DHD的第j个特征组成的子图由gener（gfj）表示。一个行集Y，是一个rsid的集合，Y=GR。一个具有d个rsid的行集称为d-行集。基因特征存在于DHD的第i行由genef（gri）表示。表1示出了DHD的示例，具有11个基因特征，F={gf1;gf2;gf3;gf4;gf5;gf6;gf7;gf8;gf9;gf10;gf11}和8个基因行，R ={1，2，3，4，5，6，7，8}。定义了项集X的支持度表1具有高分辨率DHD的数据集。Row（sample）id（rsid）特点1第1、 2、 4、 6、 10节2gf1;gf 2;gf 4;gf 7;gf 83gf2;gf 4;gf 7;gf 84第1、 2、 6、 8、 9、 10段5第1、 3、 4、 7、 8、 10段6第2节;第 4节;第 9节7第5节;第 7节8第5节;第 11节作为X在数据集的多个行中的出现，并且表示为sup（X）。 例如，表1中的项集X= {gf1;gf4}，sup（（gf1）（gf4））的支持度是3。项集X的基数被定义为存在于其中的基因特征的数量项集，记作card（X）。例如，表1中的项目集X= {gf1;gf4}，card（（gf1）（gf4））的基数是2。表2突出显示了DHD的位表。行的基数（卡）由rs表示，如表2所示。支撑如表2所示，基因特征的（sup）由cs表示。当项目集X的支持度等于或大于最小支持度阈值（minsup），sup（X）Pminsup，并且不存在与项目集X的支持度相同的适当超集X00，sup（X）=sup（X00）时，称之为频繁闭项目集（FCI）。例如，来自表1的项集X={gf1;gf4;gf8}是fre。quent封闭项集，minsup设置为2，因为它没有与项集X的支集相同的真超集={gf1;gf4;gf8}。项集X，其基数等于或大于最小基数阈值（mincard），（X）PMincard和频繁闭项集被称为频繁巨闭项集（FCCI）。例如，用4作为mincard，2作为minsup，表1中的项集X= {gf1;gf2;gf6;gf8}是频繁巨型闭项集，因为它经常是闭的，基数等于或大于明卡的，card（（gf1）（g f2）（g f6）（g f8））P明卡d.定义1（结束）。给定一个具有高重复性的数据集DHD（R，F）中的项集X<$F和行集Y<$R，我们定义genererXgf fgri2Rj8gfj2X;gfj存在于DHDg1的gr i中genefj2Fj8gri2Y;gfj存在于DHDg200项集X的闭包C（X）和行集Y的闭包C（Y）定义如下C XCYgenergenefY 4例1.给定来自DHD的项集gf1gf2和行集{2，3}，如表1所示，则gener（gf1gf2）= {1，2，4}，其中存在项集gf1gf2的DHD的行。genef（{2，3} ） =gf2gf4gf7gf8 ， DHD 的基因 特征存在 于行集 {2 ， 3} 中。 项集gf1gf2，C（gf1gf2）和行集{2，3}，C（{2，3}）的闭包如下C/gf1gf2/gf1/gf2/gf1; 2; 4/gf 1/gf2/5/gfC=2; 3g/kggener= 2; 3g/kg gener=2gf4gf7gf8/kg 2; 3g/kg gener4. 拟议工作在挖掘FCCI之前，必须对高分辨率数据集（DHD）进行预处理。一整套不可接受的证据-M.K. Vanahalli，N.Patil/ Journal of King Saud University2801828表2bitTable对应于具有高重复性DHD的数据集。RSIDgf1gf2gf3GF4gf5GF6gf7gf8gf9gf10第十一章Rs11101010001052110100110005301010011000441100010111065101100110106601010000100370000101000028000010000012CS45152244231现有的基于行枚举的FCCI挖掘算法不能对错误和不可接受的行进行剪枝。为了克服这个缺点，DHD的预处理应该包括修剪所有不可接受的特征和不可接受的行。不可接受的特征是DHD的基因特征，其支持度小于最小支持度阈值。这些不可接受的功能，必须从DHD修剪，因为它们不有助于FCCI的最终集，也恶化了算法的性能。F1¼F-F07当量（7）示出了不可接受特征集的修剪，其中F0被表示为不可接受特征集 一些现有的算法（Sohrabi和Barforoush，2012; Zhu等人，2007）修剪不可接受的特征，而不修剪不可接受的行。如表3所示，仅对不可接受的特征进行修剪是由两个现有算法完成的。当minsup设置为2时，DHD中的不可接受特征为gf3和gf11从DHD中修剪不可接受的特征，如在Eq.（7）影响DHD中行（card（srid），rsidR）的基数。不满足最小基数阈值标准的DHD行是不可接受的行。这些不可接受的行必须从DHD中修剪，因为从涉及无关紧要的行的行集中挖掘的项集对FCCI的最终集合没有贡献，并且还指数地增加了行枚举挖掘搜索空间。不可接受的行的修剪是通过几个现有的算法来执行的（Nguyen等人，2017; Nguyen等人，2016; Nguyen等人，2017; Zulkurnain等人，2012年，在删除了不可接受的特征之后。R1¼英寸R-R0¼英寸8英寸当量（8）示出了不可接受行集合的修剪，其中R0被表示为不可接受行集合。现有的几个基于行枚举的FCCI挖掘算法只修剪一次不可接受的功能集。现有的几种基于行删除的算法在删除不允许特征集后只删除一次不允许行集。这些算法对不可接受特征集和不可接受行集的修剪只执行一次，因此不修剪不可接受特征集和不可接受行集如表4所示，修剪不可接受的行是由一对夫妇的现有算法修剪不可接受的功能后形成的。当mincard设置为2时，DHD中不可接受的行是（srid，8）。从DHD中修剪不可接受行的集合影响F1中的特征（sup（gfj），gfj2F1）的支持，并且可以将来自DHD的剩余特征的特征的集合转换为不可接受。如果来自DHD的剩余特征的特征集被转换为不可接受的，则修剪过程必须继续，直到所有剩余特征和DHD的行是可接受的。如表4所示，不允许的行8的修剪影响基因特征gf5的支持，并最终将其转换为不允许的。 因此，修剪过程必须继续。现有的FCCI挖掘算法没有充分利用DHD中由于不可接受行集的修剪而减少剩余特征支持度的优点建议的工作修剪的一组不可接受的功能和一组不可接受的行连续，一个接一个，直到所有其余的功能和行从DHD是可接受的。所提出的工作成功地利用的优势，从DHD的剩余功能的支持减少，由于一组不允许的行的修剪和从DHD的剩余行的基数减少，由于一组不允许的功能的修剪的优势。建议的工作利用这两个优点，从DHD中修剪完整的不可接受的功能和不可接受的行。表5显示了修剪一个完整的一组不可接受的功能和不可接受的行后，所提出的工作的bitTable。从表3-在修剪不可接受的基因特征和行的完整集合之后，令可接受的行的最终集合为Rfinal，可接受的基因特征的最终集合为Ffinal;mfinal为最后的行数和nfinal是最终的基因数功能.从DHD中挖掘FCCI时，选择有效的枚举方法是非常重要的。DHD的数据特点说明设计基于行枚举的算法是可行的表3修剪不可接受的特征后的bitTable {gf 3; gf 11}。现有的几种算法（Sohrabi和Barforoush，2012; Zhu等人， 2007年，他只做了一个不合格的实验。RSIDgf1gf2GF4gf5GF6gf7gf8gf9gf10Rs1111010001521110011005301100110044110010111651010011015601100001037000101000280001000001CS4552244232802M.K. Vanahalli，N.Patil/ Journal of King Saud University表4在修剪不可接受的行8之后的bitTable，现有算法的一对（Nguyen等人，2017; Nguyen等人，2016; Nguyen等人，2017; Zulkurnain等人， 2012）只修剪一次不可接受的特征和不可接受的行。RSIDgf1gf2GF4gf5GF6gf7gf8gf9gf10Rs11110100015211100110053011001100441100101116510100110156011000010370001010002CS455124423表5bitTable在修剪完不可接受的特征集和不可接受的行后，提出了改进的工作。RSIDgf1gf2GF4GF6gf7gf8gf9gf10Rs111110001521110110053011011004411010111651010110156011000103CS45523423而不是特征枚举方法。采用行枚举空间的决定性遍历方法，有效地挖掘FCCI从较小的行集到较大的行集开始行枚举树遍历被描述为自底向上方法中的行枚举树遍历。自底向上的行枚举树遍历表明，庞大的项集在其最前面的层次上是高度可访问的这就实现了自底向上遍历行枚举树的方法有效地从DHD中挖掘FCCI。在自底向上方法中对应于预处理位表5的行枚举树的遍历如图1所示。行集由节点表示，在每个节点下都提到了相应的形成行集的rsid的按位AND操作有助于获得该行集处的位集结果，并且在位集结果的帮助下挖掘FCCI利用Mincard的反单调性，大大减少了行填充挖掘的搜索空间.这表明，行集的后代节点，不挖掘巨大的项目集被修剪。例如，当minsup被固定为2并且mincard被固定为2时，行集134不挖掘庞大项集。因此，行集134的后代节点被削减。一种新的BitSet频繁大型闭项集挖掘算法（BSFCCIM）算法中，包含了一个有效的剪枝策略，以削减行枚举搜索空间和行集闭包检查方法，检查行集的封闭性。行集闭包检查方法利用相应行集的更新基数。更新后的基数在检查行集的紧密性方面起着至关重要的作用，而无需参考早期挖掘的FCCI。在行集合Y处，如表5中所示的rs（基数）针对预处理的bitTable的rsid被更新，除了在行集合中出现的rsid之外通过考虑行集Y处的挖掘项集基数来更新基数。如果Z是行集Y处的位集结果，则i（Z）提供Z中出现的索引1。在行集合Y处，更新的rs将是来自在从i（Z）获得的索引处出现的相应rsid的1的数目节点13、24、25、46、124、125、234的更新后的rs和245在表6中示出。在行集合13处，针对预处理的bitTable的rsid{2，4，5，6}更新rs ，除了在行集合 13 中出现的rsid{1 ， 3} 之外。位集结果（ Z =01100000）在行集13处获得，i（01100000）={2，3}提供了在Z中出现的索引1。如表6a所示，行集合13处的更新的rs将是来自在从i（Z）= {2，3}获得的索引处出现的相应rsid {2，4，5，6}的1的数目在行集合124处，针对经预处理的bitTable的rsid{3，5，6}更新rs，除了行集合124中出现的rsid{1，2，4}之外。bitset结果（Z = 11000000），i（11000000）= {1，2}提供了在Z中出现的索引1。如表6e所示，行集124处的更新的rs将是来自相应rsid {3，5，6}的1的数量如果行集关闭检查方法指示行集已关闭，则从行集中提取的项集将关闭。行集闭包检查是在特定行集上更新的rs的帮助下执行的。当且仅当rsid的更新rs小于在该特定行集中获得的位集结果的基数行集24被关闭，因为相应rsid{1，3，5，6}的更新的rs {2，2，2，1}小于位集结果的基数（11000100）。行集46被关闭，因为相应rsid{1，2，3，5}的更新的rs {1，1，1，0}小于位集结果的基数（01000010）。BSFCCIM算法的剪枝策略利用行集上更新的rs有效地削减了行枚举挖掘的搜索空间。更新后的rs提供了要从行集的后代节点挖掘的项集的基数信息该基数信息作为先验信息削减行枚举空间，而现有的FCCI挖掘算法没有享受到基数信息的好处。关于节点134、135和136的项集基数信息由行集13处的更新的rs提供，如表6a所示。例如，当mincard被设置为2时，如表6a所示的rsid 4和rsid5的更新的rs小于mincard这表明节点134、1345、13456、1346、135和1356对巨大项集的生成没有贡献因此，这些后代节点将被修剪。BSFCCIM算法从高维数据集中挖掘所有的FCCI。算法2重点介绍了BSFCCIM算法，它调用过程1从高维数据集中挖掘FCCI。在过程1中重点介绍了BSFCCIM过程，包括有效的剪枝策略和行集闭包检查方法。BSFCCIM程序以深度优先的方式遍历自底向上的行分类树，从高维数据集中挖掘FCCIM.K. Vanahalli，N.Patil/ Journal of King Saud University2803JJ图1.一、自底向上方法中行枚举树的构造BSFCCIM算法的输入是mincard、minsup和预处理的bitTable。FCCI集被初始化为空。需要枚举的行的集合由R0f0inal表示. 在深度优先方法中遍历的自底向上行枚举树的初始节点是rcomb。调用BSFCCIM过程从预处理的bitTable中挖掘FCCI。算法2. BSFCCIM算法输入：预处理的bitTable，minsup，mincard。输出：频繁大型闭合项集初始化：FCCI=£R0f0inal=要枚举的行集rcomb=行枚举1中的初始节点：BSFCCIM（rcomb，bitset_result，R0f0inal，FCCI）1. BSFCCIM（rcom_b，bitset_r_e_sult，R0f0ina_l，FCCI）1： 如果节点rcomb分支直到minsup才到达。2：修剪树枝。3：计算枚举的行rcomb处的bitset_resultnode.4.8rsid2（R0f0inal-rcomb），if（updatedrs（rsid）mincard）5.从R0f0inal中删除rid6.如果 rcomb

下载后可阅读完整内容，剩余1页未读，立即下载