基于随机相遇的频繁项集挖掘方法

频繁项集挖掘是关联规则挖掘的重要内容,而现有的频繁项集挖掘算法在数据库扫描和复杂数据结构构建方面消耗过多的时间,效率较低。为克服现有频繁项集挖掘算法的不足,提出了基于随机相遇的频繁项集挖掘算法。在随机相遇过程中,不断从原始事务集中随机挑选两条事务,将其交集作为新事务集中的元素,通过计算新事务集中最小支持度与原事务集中最小支持度的关系,将在原事务集上的频繁项集挖掘转化为在新事务集上的频繁项集挖掘,算法的时间复杂度和空间复杂度大大降低。由于随机样本蕴含原始数据集的主要统计特性,新事务集具有原事务集的统计特性,通过调整参数,算法在新事物集上挖掘结果的准确度可以得到保证。并利用一个零售超市的交易数据对该算法的有效性进行了测试。测试结果表明,该算法能将挖掘速度提升数十倍,同时挖掘结果的准确度和其它算法相差不大。     

基于MapReduce的频繁项集挖掘方法

为了改进关联规则挖掘的经典Apriori算法,设计一种基于Map/Reduce的频繁项集挖掘方法。通过搭建Hadoop平台,可使该方法得以实现,并籍此对该方法与Apriori算法的性能进行比较研究。实验结果表明该方法在对大数据集进行频繁项集挖掘时,可充分利用云计算的优势,从而能获得更好的时效性。     

一种基于倒排索引的频繁项集挖掘方法

针对频繁项集挖掘算法中多次扫描数据库、生成大量无效频繁项集的问题,提出一种基于倒排索引和二维数组的挖掘算法。通过一次扫描数据库建立包含事务的倒排索引,解决多次扫描数据库的问题。在二维数组存储候选频繁项集时,引入标志位约束,避免产生大量无效的频繁项集。与其他算法在不同规模的数据集上进行性能比较,发现算法在数据集超过25万时执行效率优于其他算法。通过实验验证了所提出算法的高效性和可行性。     

基于FP-Growth算法的多维关联规则挖掘方法

基于FP-Growth算法在不产生侯选项集的情况下产生所有的频繁项集的思想上提出一种多维关联规则挖掘方法。该方法以数据立方体下的多维数据为研究对象,通过挖掘频繁谓词集发现多维关联规则,并通过理论和实例验证的方法证明了该方法的可行性。     

基于关联规则的网络入侵检测方法

介绍了基于关系代数理论的ORAR关联规则算法,分析了在KDD CUP99中选择训练数据集和选择特征的基本方法,并在此基础上利用ORAR算法进行了频繁3、4、5、6项集入侵模式的挖掘,将挖掘结果应用于测试数据集的入侵检测,从检测的准确率和误检率两个方面较为系统地对不同的频繁项集检测的结果进行了比较,得到了检测效果最好的频繁项集,仿真结果对于入侵检测方法的进一步研究具有积极的借鉴意义.     

概率频繁闭项集挖掘

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

一种改进的Apriori算法

Apriori算法是挖掘关联规则频繁项集的最有影响的算法之一,它通过连接、剪枝等步骤产生频繁项集,进而产生强关联规则。由于面临海量数据,因此将会产生大量的候选项集,尤其是候选2-项集,严重影响了挖掘的效率。提出了一种改进的算法,此算法不产生小项候选集而直接产生大项候选集,从而提高了算法的效率。     

MapReduce框架下Aprioi算法的改进

海量数据利用传统Apriori算法进行挖掘会浪费大量存储空间和通信资源,导致算法效率低下,因此,提出MapReduce框架下Aprioi算法的改进方法,首先采用水平划分的方法将MapReduce数据库分成n个独立的数据块,然后发送到采用动态负载均衡划分的m个工作节点上。每个节点扫描各自的数据块,产生局部候选频繁项集,计算每个候选频繁项集的支持度阈值并与最小支持度阈值进行比较以确定最终的频繁项集。改进后的算法可以减少各个节点之间的数据流动,只需要扫描两次事务数据库就能挖掘出全部频繁项集,节省扫描时间和存储空间,提高挖掘效率。     

频繁项集快速挖掘算法研究

为了进一步提高频繁项集挖掘算法的可扩展性,对频繁项集的搜索空间以及FP-tree的操作方法进行了研究.提出了通过FP-tree的操作实现频繁项集快速挖掘的相关性质和新的搜索策略,在此基础上提出了基于FP-tree的频繁项集挖掘的改进算法.算法运用递增构建候选项集模式树的策略缩小搜索空间,运用FP-tree的部分遍历操作简化搜索过程.在多个标准测试数据集上的实验结果表明,该算法的执行时间比同类算法减少了一个数量级,且占用较少的内存空间,因此该算法对于提高频繁项集和频繁闭项集的挖掘效率具有明显的效果.     

一种最大频繁项集的增量更新算法

提出了一种基于最小支持度变化的挖掘最大频繁项集的增量式更新算法MFIU(Maximum Frequent Itemsets Updating).针对最大频繁项集更新时的特性,分别对最小支持度变大和变小提出了两种不同的处理方法,对于最小支持度变大的复杂情况,采取了分块的更新策略,并为减少不必要的候选项集,利用了如果X是一个最大频繁项集,则其所有子集都是频繁项集,但都不可能是最大频繁项集,而进行了独特的剪枝方法.最后通过实例分析了该算法.