CBC-DS:基于频繁闭模式的数据流分类算法

基于关联规则的分类算法通常根据频繁模式生成类关联规则,但频繁模式挖掘易遭受组合爆炸问题,影响算法效率.并且数据流的出现也对分类算法提出了新的挑战.相对于频繁模式,频繁闭模式的数目较少,挖掘频繁闭模式的算法通常具有较高的效率.为此,提出了一种高效的基于频繁闭模式的数据流分类算法—CBC-DS.主要贡献在于:1)提出了一种基于逆文法顺序FP-Tree的频繁闭项集单遍挖掘过程,用于挖掘类关联规则,该过程采用了一种混合项顺序搜索策略以满足数据流挖掘的单遍性需求,并采用位图技术提高效率;2)提出了"自支持度"概念,用于筛选规则以提高算法分类精度.实验表明,位图技术能够提高算法速度2倍以上,利用自支持度能够提高算法平均精度0.5%左右;最终CBC-DS算法的平均分类精度比经典算法CMAR高1%左右,并且CBC-DS算法的规则挖掘速度远快于CMAR算法.

基于关联图的频繁闭模式挖掘

将关联图的数据挖掘思想应用到频繁闭模式的挖掘中,使用位向量的技术简化项集支持度的计算,构造关联图表示项集间的频繁关系。在此基础上,提出一种频繁闭模式挖掘算法,针对频繁闭模式的特点,结合剪枝策略、子集检测策略、搜索策略等技术手段,优化算法性能。实验结果表明,该算法在时间性能上优于经典的频繁闭模式算法CLOSET。

基于频繁闭模式的故障状态简洁关联规则挖掘

利用关联规则建立故障与故障表象之间的关系,对故障进行分析和预测是一种重要的故障检测手段.然而普通关联规则具有表达冗余量大和计算复杂的缺点,为此,提出采用频繁闭模式的方法来挖掘故障特征间的关联关系,并以此建立故障分析过程.由于频繁闭模式挖掘剔除冗余复杂,计算量大,在挖掘简洁故障状态关联规则过程中,采用搜索空间提前剪枝的方法直接生成频繁闭模式,避免了保存频繁模式并反复扫描原始数据和过滤候选频繁闭模式的过程.同时整个挖掘结构在挖掘过程中由于不断被删除回收,占用内存会越来越少,最终在枚举出的基于闭模式简洁规则的基础上,建立故障事件转换图,进行故障诊断.实验部分验证了方法的有效性.

一种高效的闭频繁模式挖掘算法

为了构造条件FP树,必须两次遍历FP树。提出一种FP阵列技术,直接从FP阵列得到频繁项的计数,从而省略了第一次遍历。为了检查闭频繁项集,采用FP树的一种变形结构,并将它与FP阵列结合起来,提出了一种高效的闭频繁模式挖掘算法。实验表明,该算法具有很好的性能。

基于包含索引的频繁闭序列模式挖掘的新算法

频繁闭序列模式惟一确定全体频繁序列模式,且规模小得多。传统的闭序列模式挖掘算法对每个频繁项目都进行扩展,往往会产生大量的非闭合序列。为解决这一问题,提出了一种新的基于包含索引的频繁闭序列模式挖掘算法,其主要思想是只对闭项集进行扩展,大大减少了非闭合序列的产生。首先,论证了闭序列模式只能由闭项集组成;其次,说明了如何利用包含索引来快速发现闭项集;最后,给出了一种深度优先的挖掘频繁闭序列模式的新算法。实验结果表明,该算法具有较高的效率。

一种面向分布式数据流的闭频繁模式挖掘方法

对智能交通系统中面向分布式数据流的频繁模式挖掘问题进行了研究。针对智能交通系统中传感器网络数据流的特点,提出一种基于分布式窗口树的分布式数据流闭频繁模式挖掘方法。该方法在分布式节点中构建分布式窗口树,通过对分布式窗口树进行更新、剪枝及挖掘,能够快速响应用户的查询请求,返回任意时间窗口内数据中的闭频繁模式。实验表明,在保证挖掘准确性的前提下,该方法能够有效缩短查询响应时间,并具有良好的可扩展性。

基于不确定数据的可能频繁闭序列模式挖掘

对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果会引起频繁序列的冗余。针对上述不足,提出了可能频繁闭序列模式(p-FCSPs)的定义,以及一种基于不确定数据的可能频繁闭序列挖掘算法U-FCSM。此算法中,基于一种元组不确定数据模型计算序列的可能频繁性,应用BIDE算法的闭序列思想判断可能频繁序列是否是可能频繁闭序列模式;为了减少搜索空间与避免冗余的计算,应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。

基于FC-tree的频繁闭项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,但这类算法会产生巨大的候选集并且重复扫描数据库。本文针对这一问题,给出了一种基于FC-tree的频繁闭项目集挖掘算法Max-FCIA,该算法将频繁项目集存储在哈希表中,节省了程序的搜索时间。此外,利用广度优先搜索和有效的剪枝策略,大大限制了候选项目集的生成,缩小了搜索空间从而提高了程序的性能。实验结果表明该算法是快速有效的。

在线挖掘数据流混合窗口中闭频繁项集

在数据流挖掘中,界标窗体考虑了历史模式对当前挖掘的影响,但没考虑到随时间的推移模式衰减的问题。滑动窗口能记录最新、最有用的模式,但窗口的最佳大小无法准确确定。针对一些仿真系统中具有数据流特点的数据,提出了一种挖掘混合窗口中闭频繁项集的方法T-Moment。该方法能在单遍扫描数据流的条件下完整地记录模式信息。同时,T-Moment提出的减枝方法能很好地降低滑动窗口树F-tree的空间复杂度与闭频繁模式树T-tree的维护代价。此外,该方法提出的时间衰减机制能区分历史和最新模式。大量仿真实验结果表明,T-Moment有很好的效率和准确性。

一种改进的压缩频繁模式挖掘算法

传统的频繁模式挖掘算法产出大量的频繁模式,这些大量的频繁模式对于后期的分析、处理以及理解都带来了相当大的挑战.针对上述问题,该文提出了一种改进的压缩频繁模式挖掘算法,该算法基于CFP-树通过对传统频繁模式挖掘算法的改进能够从大量的频繁模式中选择出规模更小的频繁模式代表集合,从而起到减小庞大的频繁模式挖掘结果规模的目的.实验中还将该算法和现有的RPlocal算法进行了对比,结果表明改进的压缩频繁模式挖掘算法能够在合理的时间及容错范围内获得更小的频繁模式代表集,同时大大降低了时间复杂度,提高了挖掘效率.

基于时间段的时序规则发现

时序规则挖掘用以挖掘数据库中与时间相关的规则及模式。现今大部分时序数据挖掘均是针对基于时间点的,基于时间段的挖掘相对较少。在此提出一个新的基于时间段的时序规则挖掘算法,通过挖掘频繁闭模式集取代完整频繁模式集,减少了挖掘时间,算法效率很高。

New algorithm of mining frequent closed itemsets

A new algorithm based on an FC-tree （frequent closed pattern tree） and a max-FCIA （maximal frequent closed itemsets algorithm） is presented, which is used to mine the frequent closed itemsets for solving memory and time consuming problems. This algorithm maps the transaction database by using a Hash table,gets the support of all frequent itemsets through operating the Hash table and forms a lexicographic subset tree including the frequent itemsets.Efficient pruning methods are used to get the FC-tree including all the minimum frequent closed itemsets through processing the lexicographic subset tree.Finally,frequent closed itemsets are generated from minimum frequent closed itemsets.The experimental results show that the mapping transaction database is introduced in the algorithm to reduce time consumption and to improve the efficiency of the program.Furthermore,the effective pruning strategy restrains the number of candidates,which saves space.The results show that the algorithm is effective.

基于类FP-tree的多层关联分类器

针对传统多层关联分类挖掘产生大量冗余规则而影响分类效率的问题,提出了一种基于类FP-tree的多层关联分类器MACCF(Multi-level Associative Classifier based on Class FP-tree)。该分类器依据事务的类标号划分训练集,采用闭频繁模式(CLOSET+)产生完全候选项目集,通过设计适当的类内规则剪枝策略和类间规则剪枝策略,减少了大量冗余的分类规则,提高了分类的准确率;采用交叉关联规则方法,解决了交叉层数据的分类问题,实验结果表明了算法的高效性。