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

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

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

相对于频繁项集,最大频繁项集的数目较少,挖掘最大频繁项集的算法具有较高的时空效率.提出了一种新的基于文法顺序FP-Tree的最大频繁项集单遍挖掘算法FPMFI-DS.该算法采用了一种混合搜索空间项顺序策略,并利用我们所提出的一种新的剪枝技术-"子集等价剪枝技术",有效缩小搜索空间的大小.基于该算法,提出了一种能够在线更新挖掘数据流滑动窗口中最大频繁项集的算法FPMFI-DS+.FPMFI-DS+算法能够在任意时刻都维护数据流当前窗口中的最大频繁项集.仿真实验表明,FPMFI-DS算法的效率接近于多遍挖掘算法FPMax*,并具有良好的可扩展性,FPMFI-DS+算法更新挖掘速度快.     

基于FP-tree和支持度数组的最大频繁项集挖掘算法

提出了一个基于频繁模式树即FP-tree和支持度数组相结合的最大频繁项集挖掘算法,首先建立FP-tree,同时建立支持度数组,然后在此基础上建立最大频繁项集树MAXFP-tree,MAXFP-tree中包含了所有最大频繁项集,缩小了搜索空间,提高了算法的效率。算法分析和实验表明,该算法对稠密型数据集和稀疏型数据集均适用,并且特别适于挖掘具有长频繁项集的数据集。     

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

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

一种基于树的频繁模式挖掘算法

提出了一种基于树的频繁模式挖掘算法TBA-FP。它以树表示法压缩数据库所含模式信息，将挖掘问题转化为按深度优先策略构造频繁模式树，并引入了虚拟裁剪等优化技术。实验表明，TBA-FP挖掘“长”模式的时间效率与空间可伸缩性远远优于经典算法Apriori.     

一种基于滑动窗口的多关系模式频度更新算法

面向多个相关数据流的挖掘算法研究尚处于起步阶段。作为多数据流挖掘算法的基础,模式频度更新算法仍然存在计数不准确、性能较低等问题,难以以此构造有效的挖掘算法。通过引入多关系挖掘概念以及目标关系定义,进而限定计数对象,提出了一种基于滑动窗口的多关系模式频度更新算法MRPFU。该算法监视各数据流窗口的更新情况,采用计数传播策略,减少了时间与空间复杂度。理论分析及实验结果证明了所提算法的有效性且具有较高性能。     

一种挖掘最大频繁子图的新算法

如何从大量的图中挖掘出令人感兴趣的子图模式已经成为数据挖掘领域研究的热点之一.由于其内在的计算复杂性,挖掘全部频繁子图非常困难,且得到的频繁子图过多,影响着结果的理解和应用.解决方案之一是挖掘最大频繁子图.在经典的Apriori算法的基础上,提出了一种挖掘最大频繁予图的新算法Apriori-MaxGraph.首先给出了一种新的、用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可以加速子图规范编码序列匹配的速度.其次,针对最大频繁子图,对候选子图的生成进行了规范.最后,采用双向搜索与剪枝策略,大大减小了搜索空间,提高了算法的效率,实验结果表明,Apriori-MaxGraph算法具有较高的挖掘效率.     

基于数据流频繁子图挖掘的可疑金融交易动态识别

目前,我国基于交易上报制度和静态数据挖掘的可疑金融交易识别方法存在着监测覆盖面窄、识别时效性差两大瓶颈问题。一种可行的改进是在现有方法中引入对可疑金融交易的动态识别,其中需解决的关键问题是如何及时有效地从大规模动态数据集中发现相应的可疑交易特征。设计一种基于数据流频繁子图挖掘的可疑关联特征动态识别算法,并用实验证明该算法的可行性和有效性。     

面向个性化交通信息服务的车辆行驶路径关联规则挖掘

为了向驾驶者自动提供个性化的交通服务信息，需要对车辆行驶路径进行分析和预测.面向基于RFID的个性化交通服务系统，提出改进的车辆行驶路径关联规则挖掘方法，挖掘车辆历史行驶路径数据中的频繁序列模式，由频繁序列模式产生序列关联规则，根据当前行程车辆已行驶的路径，实现对车辆未来行驶路径的预测.本方法主要通过0-N数据结构和候选2-序列产生方法的改进，提高车辆行驶路径序列模式挖掘的效率.最后，通过数据测试验证了改进算法在运行效率上与GSP相比的性能优越性.     

建立频繁项目集向量的极大频繁项目集挖掘

在分析和研究诸多经典关联规则挖掘算法或最大频繁项目集挖掘算法的基础上,提出了一种新的极大频繁项目集挖掘算法BOFPV_MMFIA算法.该算法引入频繁项目集向量FP-V,将极大频繁项目集的挖掘过程转化为频繁项目集向量FP-V的与运算过程.算法只需扫描数据库一次,克服了Apriori及其相关算法产生大量候选集和需多次扫描数据库的缺点.又不同于BOM算法,挖掘频繁k_项目集时,需要进行 次k个向量的与运算.因此,BOFPV_MMFIA算法的效率明显高于Apriori、DMFIA及BOM算法.     

一种基于划分的带项目约束的频繁项集挖掘算法

为提高关联规则挖掘算法的效率及其对大型数据集的适应性,提出了基于划分的带项目约束的频繁项集挖掘算法Partition CHS Miner。算法按照约束条件裁减数据集,并采用基于约束的超结构CHS(con-straint-based hyper-structure)存储数据。对大型数据集,先将其划分为多个不相交的数据子集,使子集的大小适合主存,然后在子集上采用基于超结构的带项目约束的挖掘算法挖掘出局部频繁项集,最后合并所有子集中的频繁项集形成全局的带约束的候选项集,计算出全局频繁项集。实验证明了算法的有效性。     

频繁项目集二次挖掘方法研究

针对关联规则数据挖掘中频繁项目集的二次挖掘问题,提出了一种能够解决当最小支持度发生变化而交易数据库不变情况下进行二次挖掘的改进算法(UMSA)。该算法充分利用频繁项目集的特性,通过新的拼接方法来减少候选项目集的生成,在扫描交易数据库确定k维频繁项目集时,采用在交易数据库中剔除无用的交易,达到不断减小交易数据库规模的目的,克服了一些算法中存在的漏采现象,并在一定程度上解决了非确定性问题。通过举例说明该算法的执行过程及其算法的正确性和有效性,并对其性能进行了分析。     

Efficient Algorithm Based on Itemset-lattice and Bitmap Index for Finding Frequent Itemsets

Finding frequent itemsets is the key problem in association rules mining. A new algorithm based on the lattice theory and bitmap index for mining frequent itemsets is proposed. The algorithm converts the original transaction database to an itemset-lattice in the pre-processing, where each itemset vertex has a label to save its support, and the complicated task of mining frequent itemsets in the database is thus changed to the simpler one that searches vertexes in the lattice. The efficiency of the mining process is enhanced greatly. Since the support counting in the association rules mining incurs a high cost regarding the I/O, a bitmap index technique is used to speed up the counting process. To address the issue that the intact bitmap usually needs a big memory space for storage, the bit vector is partitioned into blocks, which can be encoded as a symbol. This makes the original bitmap more compact in storage and improve the support counting efficiency as well. Finally, experimental and analytical results are presented.     

基于网络的数值关联规则挖掘方法

关联规则 ( Association Rules)发现的是属性间的关系 .属性可以是逻辑型的 ,也可以是数值型的 .在从逻辑型属性描述的数据中发现关联规则方面已经有许多比较成熟的算法 ,而在数值型属性方面则不然 .将数值关联规则挖掘问题映射成逻辑关联规则挖掘问题是一种方便有效的方法 .本文给出了一个新的数值属性关联规则挖掘算法 ,该算法利用数据本身的特征决定对数值属性值域的划分 ,进而将划分后的所有区间映射为逻辑属性 (项目 ) ,在此基础上可以挖掘出更容易理解、更具有概括性的有效关联规则 .本文给出了一个发现频繁项目集搜索算法 ,并采用一种纵向数据库格式来简化项目集支持度的计算.     

基于自适应哈希链的分布式频繁模式挖掘算法

针对分布式系统,提出了自适应哈希链结构的频繁模式挖掘算法。该算法首先在每个站点产生局部频繁1-项集,再产生全局频繁1-项集,根据全局频繁1-项集产生各站点的投影数据库,在各个站点分别扫描投影数据库中的交易,并根据站点可用内存情况形成相应大小的哈希链结构。通过挖掘各站点的哈希链结构得到全局频繁项集。给出了基本步骤和挖掘算法。研究表明该算法不但效率高,而且适应性强。     

基于关联规则赋权特征选择集成的信用分类研究

针对信用分类数据集中常见的高维性特征,本文基于特征袋装法和关联规则挖掘算法,构建了新的赋权特征选择集成模型AR-WSAB.该模型能根据频繁项集的支持度和置信度,对各特征的重要度进行测度,进而选择出各特征子集,训练子分类器,再通过集成得到最终结果.通过在贷款违约预测数据集上进行实证分析,结果表明该模型分类正确率相对于Bagging集成模型和PCA算法都有显著优势,所提方法能够有效处理高维性特征,并且在各分类算法上都具有普适性.     

频繁项集的简洁表示方法研究

提出了通过逻辑蕴涵的演绎规则来构建频繁项集的简洁表示,而不是挖掘所有的频繁项,来降低频繁项集中的冗余性,并利用演绎规则来构建所有频繁项集的简洁表示,从而减少存取数据库和对项集进行计数的次数,最终提供一个更加紧凑的频繁项集输出.最后,通过试验说明了该方法的有效性.