在流滑动窗体上挖掘Top-K高效用项集的有效算法

数据流上的频繁项集挖掘是数据挖掘的一个重要话题,并在现实生活中应用广泛.可是这个问题存在两个限制:(1)项在数据流中的权重没有被考虑;(2)项在每条事务中的数量没有被考虑.因此,研究人员提出了"数据流上的高效用项集挖掘"的研究问题.在这一问题中,项的权重及项在事务中的数量被考虑,数据流上的高效用项集挖掘是指在数据流中挖掘所有效用值不小于用户指定最小效用阈值的项集.对用户而言,由于不了解数据流中数据的统计特性,很难设置一个合适的最小效用阈值,如果最小效用阈值设置过高,则挖掘算法返回高效用项集的数量过少,使得用户无法准确分析;如果最小效用阈值设置过低,则挖掘算法返回太多的高效用项集,使得用户需要对结果集二次分析,为此研究人员提出了"数据流上的Top-K高效用项集挖掘"的研究问题.数据流上的Top-K高效用项集挖掘是指在数据流中寻找前k个具有最高效用值的项集,通过设置k值取代最小效用阈值,可有效地控制算法的输出规模,对用户而言更直观.与静态数据相比,数据流具有如下特点:快速的数据到达速率、数据流的尺寸未知和不能访问以前到达数据的特点,因此很难将整个数据流放入内存中处理,通常研究人员采用流滑动窗体模型.流滑动窗体是由固定数量的、最近到达的批数据组成,每个批数据包含一组事务集.现有的挖掘流滑动窗体上Top-K高效用项集的研究方法通常包含两个阶段:(1)采用高估技术高估项集在流滑动窗体中的效用,将高估效用不小于由阈值提升技术获得的最小效用阈值的项集选定为Top-K高效用项集候选项集;(2)通过扫描流滑动窗体内的批数据,计算第一阶段生成的候选项集的真实效用.可是,这个方法存在两个问题:(1)第一阶段生成的候选项集通常数量巨大,需要大量的存储空间;(2)计算第一阶段生成的候选项集的真实效用是非常耗时的.因此,本文提出一个在挖掘过程中不生成候选项集的流滑动窗体上Top-K高效用项集挖掘算法TK-HIS,TK-HIS采用提出的HUIL-Tree和效用数据库存储流滑动窗体中的项集及其在窗体事务中的效用,在HUIL-Tree和效用数据库的构建过程中提出两个阈值提升策略提升初始值为0的最小效用阈值,在挖掘过程中TK-HIS维护前k个具有最高效用值的项集,使用模式增长的方法生成搜索空间中的项集,对每一个项集通过效用数据库直接计算其在流滑动窗体中的效用.研究在稀疏数据流上进行了大量的实验评估TK-HIS的性能,并与当前最好的流滑动窗体Top-K高效用项集挖掘算法T-HUDS进行比较,实验结果表明在稀疏数据流上TK-HIS显著优于T-HUDS:运行时间最快可提升一个数量级.     

关联规则挖掘中改进型Diffsets算法

频繁项集挖掘是关联规则挖掘中至关重要的一步。对于稠密数据集的频繁项集挖掘,传统的挖掘算法往往产生大量无用的中间结果,造成内存利用率的极大浪费,尤其是在支持度较低的情况下。Diffsets算法通过引入"差集"的概念,在一定程度上解决了挖掘过程中产生的大量中间结果与内存容量之间的矛盾。改进型Diffsets算法是在原算法的基础上,在差集运算过程中根据差集中所包含的事务标识个数进行递减排序,进一步减少了挖掘过程中产生的中间结果数量。分析与实例表明,改进后的算法在执行过程中将占用更少的内存空间,加快了算法的收敛速度。     

一种基于邻接表的最大频繁项集挖掘算法

针对Apriori算法与FP-Growth算法在最大频繁项集挖掘过程中存在的运行低效、内存消耗大、难以适应稠密数据集的处理、影响大数据价值挖掘时效等问题,该文提出一种基于邻接表的最大频繁项集挖掘算法。该算法只需遍历数据库一次,同时用哈希表对邻接表进行辅助存储,减小了遍历的空间规模。理论分析与实验结果表明,该算法时间与空间复杂度较低,提高了最大频繁项集挖掘速率,尤其在处理稠密数据集时具有较好的优越性。     

基于图论的频繁闭项集挖掘

利用了有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的频繁闭项集挖掘算法。不仅实现了事务数据库的一次扫描,减少了I/O代价,而且提高了数据结构的存储空间效率和频繁闭项集挖掘算法的执行时间效率。     

关联规则中Apriori算法的创新研究

在关联规则理论的基础上,通过对现有算法的效率分析,在原有A研ori关联规则挖掘算法的基础上,从减少事务数据库中扫描记录量入手,提出一个改进的快速关联规则挖掘算法Fast_Apriori。利用候选项集和频繁项集中的结果对数据库中的记录进行筛选,对不包含候选项集中任何项集的记录和不包含在候选项集中的事物记录直接删除,减少扫描的记录数,提高整个算法的效率。     

基于团的频繁项集挖掘算法

高效地找出所有的频繁项集是关联规则挖掘中的核心问题。通过对已有的基于矩阵的频繁项集挖掘算法的研究,提出一种基于团的频繁项集快速生成算法。该算法采用关联图存储频繁两项集信息,找关联图中团,逐步减少团中项来搜索所有最大频繁项集,并且其扫描数据库仅需一次。通过使用标准数据集进行验证测试并与其他算法进行比较,实验结果表明,该算法具有较快的挖掘速度。     

基于完全图的多支持度阈值关联规则挖掘算法

提出了基于完全图的最大约束条件下多支持度闻值关联规则挖掘改进算法。该算法利用完全图与频繁项集之间的关系，以完全图结点的度作为判断标准，使得寻找单个候选项集Ck（k≥3）的复杂度降低了。在由候选集得到频繁集的过程中，该算法避免了对事务数据库的扫描，从而减小了系统的I/O开销。因此，该算法减小了存储空间，加快了挖掘速度，提高了算法的效率。     

一种基于矩阵的Apriori改进算法

Apriori算法是经典的关联规则挖掘算法之一。该算法可以很好地挖掘关联规则,通过连接步和剪枝步从频繁项集中获取候选项集,但产生大量的候选项集,这就需要重复扫描数据库,大大增加算法运行时间。文中提出一种基于矩阵的改进算法,通过事务矩阵和候选项集项目矩阵相乘的矩阵操作来改进频繁扫描数据库的问题。事务数组的建立可以删除不能生成下一频繁项集的事务,删除不必要的项,针对频繁项集的产生过程优化Apriori算法的连接步和修剪步。在不同的数据集下通过实验验证改进算法不仅能准确地挖掘出频繁项集而且大大地缩短挖掘时间。     

基于项集特性的关联规则挖掘中Apriori算法的改进

提出一个改进Apriori的算法IApr,利用事务数据库的事务数相对于项集的项的个数而言要大得多这一特点,采用线性存储结构,并结合推出并证明的项集特性,考虑候选频繁项目集的各个项的应满足的条件,只需扫描一次事务数据库,有效减少了生成候选频繁项集的数目,从数据扫描量、搜索空间、时间复杂度上分析都提高了算法效率。     

应用于音乐节目分类的Apriori挖掘算法设计

传统Apriori挖掘算法需多次扫描数据库、多次连接频繁项集,导致挖掘效率较低,为此对Apriori挖掘算法加以改进,设计一种新的Apriori挖掘算法用于音乐节目分类。改进的Apriori挖掘算法采用莱特准则对音频数据进行野值与噪声平滑处理,改进Apriori挖掘算法的音频数据库映射令两个线性表分别负责音频数据存储和对应项存储,音频数据库扫描次数降为一次;改进Apriori挖掘算法的连接次数无需对不具备交运算能力的元素进行交运算操作,减少频繁项集连接次数。基于改进频繁项集Apriori挖掘算法挖掘频繁项集、生成音频数据关联规则,基于关联规则集构建分类器,实现音乐节目分类。实验结果显示,改进Apriori挖掘算法用于音乐节目分类的效率优势突出,准确度高。     

High Utility Itemsets Mining Based on Divide-and-Conquer Strategy

High utility itemsets mining has become a hot research topic in association rules mining. But many algorithms directly mine datasets, and there is a problem on dense datasets, that is, too many itemsets stored in each transaction. In the process of mining association rules, it takes a lot of storage space and affects the running efficiency of the algorithm. In the existing algorithms, there is a lack of efficient itemset mining algorithms for dense datasets. Aiming at this problem, a high utility itemsets mining algorithm based on divide-and-conquer strategy is proposed. Using the improved silhouette coefficient to select the best K-means cluster number, the datasets are divided into many smaller subclasses. Then, the association rules mining is performed by Boolean matrix compression operation on each subclass, and iteratively merge them to get the final mining results. We also analyze the time complexity of our method and Apriori algorithm. Finally, experimental results on several well-known real world datasets are conducted to show that the improved algorithm performs faster and consumes less memory on dense datasets, which can effectively improve the computational efficiency of the algorithm.

     

Mining of High-Utility Patterns in Big IoT-based Databases

When focusing on the general area of data mining, high-utility itemset mining (HUIM) can be defined as an offset of frequent itemset mining (FIM). It is known to emphasize more factors critically, which gives HUIM its intrinsic edge. Due to the flourishing development of the IoT technique, the uncertainty patterns mining is also attractive. Potential high-utility itemset mining (PHUIM) is introduced to reveal valuable patterns in an uncertainty database. Unfortunately, even though the previous methods are all very effective and powerful to mine, the potential high-utility itemsets quickly. These algorithms are not specifically designed for a database with an enormous number of records. In the previous methods, uncertainty transaction datasets would be load in the memory ultimately. Usually, several pre-defined operators would be applied to modify the original dataset to reduce the seeking time for scanning the data. However, it is impracticable to apply the same way in a big-data dataset. In this work, a dataset is assumed to be too big to be loaded directly into memory and be duplicated or modified; then, a MapReduce framework is proposed that can be used to handle these types of situations. One of our main objectives is to attempt to reduce the frequency of dataset scans while still maximizing the parallelization of all processes. Through in-depth experimental results, the proposed Hadoop algorithm is shown to perform strongly to mine all of the potential high-utility itemsets in a big-data dataset and shows excellent performance in a Hadoop computing cluster.

     

A single-phase algorithm for mining high utility itemsets using compressed tree structures

Mining high utility itemsets (HUIs) from transaction databases considers such factors as the unit profit and quantity of purchased items. Two-phase tree-based algorithms transform a database into compressed tree structures and generate candidate patterns through a recursive pattern-growth procedure. This procedure requires a lot of memory and time to construct conditional pattern trees. To address this issue, this study employs two compressed tree structures, namely, Utility Count Tree and String Utility Tree, to enumerate valid patterns and thus promote fast utility computation. Furthermore, the study presents an algorithm called single-phase utility computation (SPUC) that leverages these two tree structures to mine HUIs in a single phase by incorporating novel pruning strategies. Experiments conducted on both real and synthetic datasets demonstrate the superior performance of SPUC compared with IHUP, UP-Growth, and UP-Growth+ algorithms.     

基于回溯的最大频繁项集挖掘算法

针对Apriori类算法多次扫描数据库和FP-tree类算法需要构建大量条件模式树的问题,文中提出了挖掘最大频繁项集的GBMFI算法。采用垂直格式存储事务数据库,以枚举树为基础,利用子集非频繁性质和父子节点支持度信息在搜索过程中对枚举树进行剪枝,最终得到最大频繁项集。通过实验对比,结果证明了算法的有效性,尤其适用于稀疏数据集。     

ODAM: An optimized distributed association rule mining algorithm

Association rule mining is an active data mining research area. However, most ARM algorithms cater to a centralized environment. In contrast to previous ARM algorithms, we have developed a distributed algorithm, called optimized distributed association mining, for geographically distributed data sets. ODAM generates support counts of candidate itemsets quicker than the other DARM algorithms and reduces the size of average transactions, data sets, and message exchanges.     

双数组穷举法挖掘医药销售数据库频繁集

为了挖掘医药销售数据库频繁集,采用双数组穷举算法DAEA。该算法主要使用两个数组和穷举算法,实现挖掘医药销售数据库的频繁集功能。该算法的优点是只需对医药销售数据库进行数据预处理就可以直接挖掘该数据库的频繁集,无需把医药销售数据库转换成相应的事务数据库。根据DAEA算法,开发了医药销售数据库频繁集挖掘系统,使用该系统挖掘医药销售数据库的频繁集,挖掘的结果与实际相吻合,说明该算法是可行的和有效的。     

一种约束最大频繁项目集挖掘算法

提出了一种基于频繁模式矩阵(FP-array)的约束最大频繁项目集挖掘及其更新算法。算法只扫描事务数据库一遍,把满足约束条件的所有事务转换成一个频繁模式矩阵,显著缩小了FP-array的大小规模。挖掘过程采用逻辑运算,在效率上有独特的优势。实验结果表明该算法是快速有效的。