基于邻接比特压缩表的频繁闭项集挖掘算法

频繁闭项集(Frequent Closed Items,FCI)是一种表示事物之间关联关系的有效方式,它能克服频繁项集(Frequent Items,FI)信息冗余的缺点。FCI挖掘算法研究旨在以更优的时空效率,在原始数据集中找到所有的FCI。相关研究成果重在关注时间效率的提升,但空间效率欠佳。提出一种高空间压缩率数据结构——邻接比特压缩表(Compressed Adjacency Byte table,Cab-table),将项集与交易集压缩到剔除全部0之后的比特表中,使空间高度压缩。基于此数据结构的频繁闭项集挖掘算法(Cab-Miner),采用运算栈与检索栈来实现非递归方式的频繁闭项集挖掘,相较于之前普遍采用递归方式的算法,在理论上可使空间占用率由O(L*N+M)降为O(3N)。基于公开数据集与真实数据集的实验表明,上述算法在原始数据集压缩,以及运算内存消耗上,都有较优的表现,尤其在处理真实数据集时,空间表现极佳。另外在某些属性的数据集上也表现出优越的时间效率。

Q-CFIsL：挖掘频繁闭项集并构建其格的快速算法

提出了一种快速挖掘频繁闭项集并构建其格的算法Q-CFIsL。该算法引入了preC(X)的概念,使用preC(X)加快了包容检测和建格的速度。实验表明,对于真实数据集以及合成数据集,Q-CFIsL的性能都优于当前最新的同类算法CHARM-L。

不确定数据中的频繁闭项集挖掘

研究不确定数据中的频繁闭项集挖掘,介绍不确定数据与概率频繁项集的概念,概率频繁闭项集挖掘的基本概念和概率频繁闭项集的挖掘算法,并分析该算法的性能.

概率频繁闭项集挖掘

许多新的应用中出现了不确定数据,比如使用无线传感器网络进行监听和对移动对象进行搜寻等。对这些不确定数据进行挖掘是一项重要工作,尤其是在不确定数据中挖掘概率频繁项集。但是,概率频繁项集的数量非常大,用户很难直接使用。为了解决这一问题,提出了不确定数据中的概率频繁闭项集挖掘方法。

基于频繁闭项集的新关联分类算法ACCF

提出了基于频繁闭项集的新关联分类算法ACCF。ACCF首先挖掘出所有频繁闭项集(CFIs)和候选分类关联规则,然后从候选分类关联规则中产生和筛选出若干规则,并用其构建分类器;在分类应用时,采用了一种新的匹配方式对分类实例进行分类。通过理论分析和对18个UCI公共数据集的实验结果表明,ACCF不仅能挖掘出高质量且不丢失信息的关联分类规则,而且大大减少了关联分类规则的数量,在分类准确率上也比现有的关联分类典型算法更高。

一种改进的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多,但挖掘频繁闭项集仍是很费时的.为提高挖掘效率,提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index.该算法用"索引数组"来组织数据,通过为每个项目增加包含索引,找到频繁共同出现的项集.利用二进制位图技术,给出了一个求包含索引的快速算法.然后根据项目在包含索引中出现的频率由高到低进行排序,并利用包含索引作为启发信息,合并同时出现且支持度相等的频繁项,得到初始生成子,从而大大缩小了搜索空间.同时利用索引数组对每一个生成子的前序集和后序集进行约简,得到新的、较小的约简前序集和约简后序集.并证明了约简前序集和后序集与原来的前序集和后序集的功能是一样的.从而减少了候选生成子的集合包含判断的操作.实验结果表明,该算法的性能优于其他主流算法.

数据流中频繁闭项集的近似挖掘算法

在数据流中挖掘频繁项集得到了广泛的研究,传统的研究方法大多关注于在数据流中挖掘全部频繁项集.由于挖掘全部频繁项集存在数据和模式冗余问题,所以对算法的时间和空间效率都具有更大的挑战性.因此,近年来人们开始关注在数据流中挖掘频繁闭项集,其中一个典型的工作就是Moment算法.本文提出了一种数据流中频繁闭项集的近似挖掘算法A-Moment.它采用衰减窗口机制、近似计数估计方法和分布式更新信息策略来解决Moment算法中过度依赖于窗口和执行效率低等问题.实验表明,该算法在保证挖掘精度的前提下,可以比Moment获得更好的效率.

改进的数据流频繁闭项集挖掘算法

为提高数据流频繁闭项集的查找效率,提出一种改进的NewMoment频繁闭项集挖掘算法,通过在LevelCET数据结构中加入层次结点,并利用层次检测策略与最佳频繁闭项集检测策略快速挖掘数据流滑动窗口中所有的频繁闭项集。实验结果证明,与NewMoment算法相比,改进的算法性能更优。

一种基于位运算的频繁闭项集挖掘算法

针对相关算法在挖掘频繁闭项集时所存在的问题,提出了一种基于位运算的频繁闭项集挖掘算法。该算法首先将数据集转换成布尔矩阵,只需扫描数据集一次;通过位运算计算支持度,利用矩阵和数组存储辅助信息,减少时间和空间消耗;深度优先搜索产生频繁闭项集时利用剪枝策略进一步减少挖掘时间;利用同生项集性质进行闭合性检测,无须检查超集或子集。理论分析和实验结果验证了该算法的有效性。

在单向FP-tree上挖掘频繁闭项集

频繁闭项集提供了频繁项集的一种完整的、最小表示。针对稠密数据集,提出一种基于单向FP-tree的频繁闭项集挖掘算法Unid_FP-FCI。该算法在挖掘过程中只生成被约束子树,而它是一种虚拟的树结构,在原有的单向FP-tree基础上用三个很小的数组来表示,因而避免了以往算法需递归构造条件FP-tree来计算频繁闭项集的弊端,极大地降低了内存空间和时间开销,提高了挖掘效率。

基于频繁项集挖掘最大频繁项集和频繁闭项集

提出了基于频繁项集的最大频繁项集(BFI-DMFI)和频繁闭项集挖掘算法(BFI-DCFI)。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等的频繁项集中的最大频繁项集组合生成频繁闭项集。该类算法的提出,为关联规则的精简提供了一种新的解决方法。

在线挖掘数据流滑动窗口中频繁闭项集

在线挖掘滑动窗口中的频繁闭项集是一类重要的数据流挖掘问题。提出了一种新的频繁闭项集挖掘算法FPCFI-DS。该算法能够在有限的存储空间中高速挖掘数据流滑动窗口中的频繁闭项集,并且能够在任意时刻维护当前窗口中精确的频繁闭项集。对于第一个窗口中的数据,FPCFI-DS算法采用单遍过程FPCFI进行挖掘,挖掘结果被保存于一棵全局闭项集树GCT中。当窗口向前滑动时,FPCFI-DS算法采用更新挖掘方式快速挖掘出当前窗口中的频繁闭项集。实验结果表明,FPCFI-DS算法的空间效率和时间效率都显著优于同类经典算法Moment。

一种挖掘频繁闭项集的深度优先算法

频繁闭项集挖掘是许多数据挖掘应用中的重要问题。为减少候选项集数量和降低支持度计算的开销,提出一种新的深度优先搜索频繁闭项集(DFFCI)的算法。将改进的压缩频繁模式树(CFP-Tree)表示的数据集信息投影到划分矩阵,使用二进制向量逻辑运算计算支持度,简化了计算过程,减少了时间开销;采用基于支持度预计算技术的全局2-项剪枝和局部扩展剪枝,有效削减了搜索空间。实验结果表明该算法的性能优于其他主流深度优先算法。

基于频繁闭项集压缩方法的郭淑云教授用药经验挖掘

目的通过对郭淑云教授2018年门诊处方数据进行分析,总结郭淑云教授用药经验。方法通过门诊HIS系统提取郭淑云教授2018年中药处方数据,经过预处理之后,应用基于最小覆盖的频繁闭项集压缩方法进行分析,从中总结郭淑云教授用药经验。结果 4936个中药处方中包含287味中药,通过344个频繁闭项集可以覆盖所有数据,从中进一步筛选出74个出现频次较高、更具有代表性的频繁项集。结论郭淑云教授临证常用小方,常用药对多为两三个药物的组合,例如枳实与白术,山药与茯苓,海螵蛸与煅瓦楞子,白芍与甘草等,研究方法有助于对名老中医经验进行挖掘。

基于概念格的频繁闭项集挖掘方法

频繁项集挖掘是数据挖掘研究领域的一个基本问题,其瓶颈在于频繁项集全集的结果过多,冗余现象严重,而频繁闭项集能唯一确定频繁项集且规模小得多。针对如何快速生成频繁闭项集,分析不可分辨矩阵、概念格和频繁闭项集之间的关系,提出一种新的更有利于生成频繁闭项集的格结构,并给出相应的渐进式生成算法和频繁闭项集提取算法。实验表明该方法能够高效地挖掘频繁闭项集。

挖掘事务间频繁闭项集的高效率算法

事务间频繁项集将传统的单维事务内关联规则扩展到多维跨事务关联规则,但事务间频繁项集的数量随滑动时间窗口的增大而迅速增加.利用频繁闭项集的特点,提出事务间频繁闭项集的概念及其挖掘算法(FCITA).该算法采用分割和条件数据库技术,避免生成庞大的扩展数据库;利用扩展二进制形式压缩事务,从而提高支持度的计算效率.此外,动态排序和哈希表极大地减少了频繁闭项集的测试次数.仿真比较表明,FCITA算法具有较高的挖掘效率.

基于频繁闭项集压缩方法的小儿脑瘫穴位配伍规律研究

目的利用西安中医脑病医院住院病历针灸穴位处方数据,分析治疗小儿脑瘫穴位配伍规律。方法从住院电子病历数据中提取诊断及针灸穴位处方信息,经过预处理之后,应用基于最小覆盖的频繁闭项集压缩方法进行分析,从中发现治疗小儿脑瘫的穴位配伍规律,并进一步分析穴位组合与证候诊断的相关性。结果701个针灸穴位处方中包含77个穴位,通过88个频繁闭项集可以覆盖所有数据,从中进一步筛选出15个更具有代表性的项集,覆盖了85%的数据。结论西安中医脑病医院治疗小儿脑瘫用穴相对固定,每个证型有对应的穴位基本方,在此基础上进行少量的加减,本研究方法可以应用于临床针灸处方数据的挖掘分析和名中医的经验传承。

基于索引数组和复合频繁模式树的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多。CROP是一种基于复合频繁模式树的、频繁闭项集高效挖掘算法,但存在着候选结点过多的问题。这些非闭合结点的生成、检查和剪裁带来了大量不必要的操作。提出了一种改进的频繁闭项集挖掘算法CROP_Index。该算法用"索引数组"来组织数据,找到频繁共同出现的项集。基于二进制位图,给出了一个包含索引的计算方法,并利用索引启发信息合并,得到复合型频繁模式树的初始结点;同时给出一些新的性质,使得改进的算法只生成闭合结点,从而节省了大量不必要的操作,缩小了搜索空间。实验结果表明该算法效率较高。

不确定数据频繁闭项集挖掘算法

由于不确定数据的向下封闭属性,挖掘全部频繁项集的方法会得到一个指数级的结果。为获得一个较小的合适的结果集,研究了在不确定数据上挖掘频繁闭项集,并提出了一种新的频繁闭项集挖掘算法——NA-PFCIM。该算法将项集挖掘过程看作一个概率分布函数,考虑到基于正态分布模型的方法提取的频繁项集精确度较高,而且支持大型数据库,采用了正态分布模型提取频繁项集。同时,为了减少搜索空间以及避免冗余计算,利用基于深度优先搜索的策略来获得所有的概率频繁闭项集。该算法还设计了两个剪枝策略:超集修剪和子集修剪。最后,在常用的数据集(T10I4D100K、Accidents、Mushroom、Chess)上,将提出的NA-PFCIM算法和基于泊松分布的A-PFCIM算法进行比较。实验结果表明,NA-PFCIM算法能够减少所要扩展的项集,同时减少项集频繁概率的计算,其性能优于对比算法。

基于等价类划分的并行频繁闭项集挖掘算法

针对海量数据的关联规则挖掘问题,提出了一种有效的基于等价类划分的并行频繁闭项集挖掘算法.该算法在MapReduce框架下,通过等价类的产生与划分、数据集的分配、异步频繁闭项集挖掘和汇总等步骤,不但较好地解决了多节点间的负载均衡问题,而且易于获得可靠的频繁闭项集.实验表明,该算法能有效克服传统算法挖掘效率低、冗余规则较多的缺点,整体上具有较高的性能.