论文部分内容阅读
关联规则可以发现事务之间的相关关系,而且因具有实现简单、可解释性强等优点在很多领域中都有应用。然而数据量的不断变大使得传统算法往往不能及时地获取规则。因此,很多学者都致力于研究如何提高算法的运行效率。本课题的主要研究工作是基于等价类变换(Equicalence CLAss Transformation,Eclat)算法进行的,Eclat算法充分利用了垂直数据库的优势,将统计项集支持度的过程转化为求取两个集合交集的过程。而Eclat算法在执行时需要通过频繁地计算交集获取项集的支持度,因此当集合交集计算效率较低时,频繁地计算交集将严重影响Eclat算法的执行速度。Eclat算法在运行过程中因存在大量非频繁候选项集而导致很多无效计算,为了解决该问题,本课题从剪枝策略的角度提出了Eclat_LSH和Eclat_LSHCF算法,从挖掘近似结果的角度提出了Sim-Eclat算法,具体如下:Eclat_LSH算法从减少需要比较元素的角度出发:(1)利用局部敏感哈希的思想,将计算两个大集合交集的过程,转化为求取若干小集合交集再累加的过程,减少了每个元素需要比较的次数;(2)Eclat_LSH算法在计算项集支持度的过程中,充分发挥了最小支持度的作用,对项集支持度上界进行评估,当评估到项集的支持度不可能满足筛选条件时,则立即停止计算。实验结果表明,利用Eclat_LSH算法进行频繁项集挖掘,能够减少计算量,加快算法的运行速度。Eclat_LSHCF算法从减少计算交集次数的角度出发:该算法利用了Takuma提出的数据结构Cardinality Filter(CF),CF可以快速地计算出两个集合交集的上界,因此可以将CF与Eclat_LSH算法结合,在计算项集支持度之前,先利用CF计算项集支持度的上界,然后利用该上界对非频繁项集快速剪枝。实验结果表明,该方法在一定情况下能够减少不必要的交集计算,加快算法的运行速度。Sim-Eclat算法采用近似计算支持度大小的方法加快挖掘速度,其思想是:采用MinHash技术快速估算项集的支持度大小,以达到加快算法运行速度的目的;另外考虑到估算支持度会存在误差的情况,提出了易混边界Boundary的概念,对于那些支持度的估计值在最小支持度阈值附近的项集,用真实的集合重新计算其支持度大小,这样做可以提高算法的挖掘精度。本课题还从理论上分析了Sim-Eclat算法是误差可控的。Sim-Eclat算法还将计算集合交集大小的过程,转换为用布尔数组来实现。实验结果表明Sim-Eclat算法有效地缓解了Eclat在计算项集的支持度时效率低下的问题,大大加快了算法的运行速度。