论文部分内容阅读
当前数据技术的发展依然是热点,技术的进步使得我们从各方面积累数据集,数据挖掘技术是我们从数据中获取信息的重要手段,面对急剧增长的数据,如何提高数据挖掘的效率并高效的应用于不同领域依然是我们关注的热点。关联规则挖掘算法可以从数据集中发现随机数据之间的潜在联系,是基础的数据分析功能之一。作为数据挖掘的经典算法,Apriori算法因其挖掘频繁项集时需要多次遍历数据库,同时缺乏合适的剪枝策略,会产生过多的候选项集,导致算法效率不高、内存负载较大等问题。基于此,许多学者提出了对Apriori算法的各类改进方法,其中基于位图的MBSA(Map-based Bitset Association Rule)算法,在遍历一次数据库后,将数据映射到位图中,利用位图的逻辑运算实现连接操作,具有较高的挖掘效率。在将基于位图算法应用与实际数据时,发现将一些特定的数据转为位图后,因为数据自身的特点,会产生大量的0值,并在实际的位运算存储中造成空间的大量占用。在位图映射的表示中“1”代表该项出现,“0”值代表该项未出现,而“0”值仅在和“1”值执行连接步的位运算时有意义,大量0值之间的运算其实是毫无意义的,因此会降低算法在空间和时间上的效率。基于此,本文提出一种基于压缩位图的关联规则挖掘算法,该算法只考虑位图中“1”值(本文称为有效值)的存储及运算,采用数组的方式存储有效值的位置索引,实现了对位图的简单压缩,从而节省了存储空间。基于新的存储方式,本文重新设计了连接算法,通过使用数组的交集运算实现连接操作,同时采用更优秀的交集策略,有效节约了运算时间。交集运算得到的数组即为新候选项集的存储数组,新数组的大小即为新项集的支持度。由于传统的位图的算法在连接步中,未利用合适的方法剪枝频繁项集,项集之间的多次组合会产生数量庞大的候选项集,降低了算法效率。因此,本文在生成候选项集时,通过优化的剪枝策略,剔除掉无用的候选项集,提高运算效率。虽然基于数组的交集运算的效率不如位运算,但由于对数据进行了压缩,减少了数据的数目及运算量,从算法的整体性能上来看,反而提高了效率。如果有效值的占比低于1/16,基于有效值存储方式对应的存储容量就会比位图小。由于本文使用简单的数据压缩方式,有效值数量的多少会对算法效率造成影响,因此使用生成数据和实际数据对两种算法做对比试验,对比各自在时间和空间上的性能。在对实际数据的应用中,我们发现一些超市数据,在转换位图存储后有效值“1”的占比非常低,位图分布比较稀疏。本文提出的算法比传统的位图算法在时间和空间上具有更好的性能。因此,本文提出的算法在稀疏数据集的关联规则挖掘中具有更高的实用价值。