第2期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·353· 用关联规则算法有Apriori、FP-Growth、Magnu- 种最小相关度优化PNARC算法的审计数据关联 mOpus、Closet等，，其中最常用也是最经典的挖 规则挖掘模型，提高负关联规则的程度，减少不 掘算法是Apriori算法。 相关的关联规则，然后对最小相关度进行概率分 为了挖取规模合适的规则，大部分关联规则 析，降低无关规则的产生几率。董博等©针对传 算法执行前需用户设置两个阈值：最小支持度和 统关联规则挖掘方法存在计算冗余度过高的问 最小置信度，以期找到所有超过用户设定阈值的 题，提出一种后处理闭包算子最小单约束的关联 规则。因此，用户必须具备一定的先验知识才能 规则算法有效降低算法冗余计算，提高算法计算 寻找到合适的最小支持度和最小置信度以便获得 效率。Li等山提出了一种新的联想分类器Sg 有应用价值的规则。但在实际应用过程中，)不 Direct,利用Fisher的精确检验作为一种剪枝策 同领域数据差异较大，导致算法在不同的数据集 略，直接挖掘分类关联规则。在没有最小支持度 中设置的最小支持数和最小置信度存在较大差 和最小置信度等阈值设置的情况下，SigDirect能 异，没有一个统一的标准；2)存在许多非专业用 够找到非冗余的分类关联规则，这些规则在一组 户，对算法参数的取值具有较大的随意性。因此 先前项和随后的类标签之间表现出统计上的显著 如何利用数据集本身的特性自动确定阈值而无须 依赖性。还有一些学者提出利用智能技术进行关 先验知识是一个很有意义且亟待解决的问题。本 联规则挖掘，而无需设置最小支持度和最小置信 文针对这一问题提出基于可决系数的自适应关联 度，如Qodmanan等利用多目标遗传算法进行 规则挖掘算法，依据待挖掘数据集中所有项的支 FP-Tree模式关联规则挖掘，Sarath等l提出使用 持数和所有规则的置信度的数据分布特性，采用 二进制粒子群优化策略，吴琼等针对量化关联 曲线拟合技术，根据可决系数自动确定拟合多项 规则的特点，提出基于多目标烟花算法全面搜索 式，并在此基础上自动确定具有数据统计依赖意 关联规则，Anping等提出了基于Pareto的多目 义的最小支持度和置信度，使其关联规则挖掘的 标二进制BAT算法(MBBA)。Can等I提出利用 应用门槛降低。 引力搜索算法(GSA)进行数值型关联规则挖掘。 这些基于智能技术，通过搜索全域空间，无须设 1相关研究 置最小支持度和最小置信度参数即可获取支持度 针对上述所提的参数阈值设置方面问题，在 最好、置信度最高的强关联规则，存在着需要很 过去的十多年中，研究者们从不同角度提出了一 大计算量的问题。另一角度是利用数据内在的某 些解决方法。一种角度是优化参数或减少参数的 些特性确定参数的方法。如王志愿等刃提出根 方法。例如，Scheffer提出的预测Apriori算法 据项集内部的语义相关度动态确定该项集的最小 它自动解决了最小支持度和最小置信度这两个参 支持度，并采用了项集语义相关度的增量计算方 数之间的平衡问题，最大限度地提高了对数据集 法。实验结果表明，DS-Apriori算法在很大程度 进行精确预测的可能性。该算法利用贝叶斯方法 上提高了关联规则挖掘算法的效率和效果。Saurav 计算了一个称为精确期望预测精度的参数，以实 等1)提出了一种基于动态阈值的FP生长规则挖 现精确的预测，从而提供规则的精确性信息。最 掘算法，该算法将基于加权最短距离的基因表 后的结果表明，预测Aprio算法的性能优于使用 达、甲基化和蛋白-蛋白质相互作用剖面结合起 增量因子的Apriori型算法。A-Magaleh等提出 来，在多视点数据集中寻找不同基因对之间的新 了一种有效的置信度综合算法，在挖掘频繁项集 关联，该方法主要优点之一是它考虑了属于每个 的过程中生成了真正有用的规则。吴瑞华等提 规则的所有成对基因之间的定量和交互意义。与 出了一种多重支持度关联规则挖掘算法，根据不 以往的方法相比，该算法生成的规则更少，运行 同数据项的特点定义多重支持度，通过挖掘数据 时间也更短，并且为得到的顶级规则提供了更大 库中的最大频繁项目集，计算最大频繁候选项目 的生物学意义，但该方法是基于生物学基础的统 集在数据库中的支持度来发现关联规则，可解决 计，缺乏通用性。Jitendra等u9提出了一种基于项 关联规则中经常出现的稀少数据项问题。陈柳等网 集范围和相关系数的关联规则集粒子群算法 提出了一个结合项集相关性的两级置信度阈值设 SARIC,该算法能快速、客观地自动确定支持度和 置方法(PNMC-TWO),该方法不仅可以更好地确 置信度。林甲祥等20提出一种新的自动确定支 保提取出的关联规则有效和有趣，还可以显著地 持度和置信度阈值的方法，该方法采用数据分布 降低可信度低的关联规则数。于海燕提出了一 特性进行曲线拟合确定阈值，为算法的更广泛合用关联规则算法有 Apriori、FP-Growth、Magnu￾mOpus、Closet 等 [1, 4] ，其中最常用也是最经典的挖 掘算法是 Apriori 算法。 为了挖取规模合适的规则，大部分关联规则 算法执行前需用户设置两个阈值：最小支持度和 最小置信度，以期找到所有超过用户设定阈值的 规则。因此，用户必须具备一定的先验知识才能 寻找到合适的最小支持度和最小置信度以便获得 有应用价值的规则。但在实际应用过程中，1) 不 同领域数据差异较大，导致算法在不同的数据集 中设置的最小支持数和最小置信度存在较大差 异，没有一个统一的标准；2) 存在许多非专业用 户，对算法参数的取值具有较大的随意性。因此 如何利用数据集本身的特性自动确定阈值而无须 先验知识是一个很有意义且亟待解决的问题。本 文针对这一问题提出基于可决系数的自适应关联 规则挖掘算法，依据待挖掘数据集中所有项的支 持数和所有规则的置信度的数据分布特性，采用 曲线拟合技术，根据可决系数自动确定拟合多项 式，并在此基础上自动确定具有数据统计依赖意 义的最小支持度和置信度，使其关联规则挖掘的 应用门槛降低。 1 相关研究 针对上述所提的参数阈值设置方面问题，在 过去的十多年中，研究者们从不同角度提出了一 些解决方法。一种角度是优化参数或减少参数的 方法。例如，Scheffer 提出的预测 Apriori 算法[5] ， 它自动解决了最小支持度和最小置信度这两个参 数之间的平衡问题，最大限度地提高了对数据集 进行精确预测的可能性。该算法利用贝叶斯方法 计算了一个称为精确期望预测精度的参数，以实 现精确的预测，从而提供规则的精确性信息。最 后的结果表明，预测 Apriori 算法的性能优于使用 增量因子的 Apriori 型算法。AI-Maqaleh 等 [6] 提出 了一种有效的置信度综合算法，在挖掘频繁项集 的过程中生成了真正有用的规则。吴瑞华等[7] 提 出了一种多重支持度关联规则挖掘算法，根据不 同数据项的特点定义多重支持度，通过挖掘数据 库中的最大频繁项目集，计算最大频繁候选项目 集在数据库中的支持度来发现关联规则，可解决 关联规则中经常出现的稀少数据项问题。陈柳等[8] 提出了一个结合项集相关性的两级置信度阈值设 置方法 (PNMC-TWO)，该方法不仅可以更好地确 保提取出的关联规则有效和有趣,还可以显著地 降低可信度低的关联规则数。于海燕[9] 提出了一 种最小相关度优化 PNARC 算法的审计数据关联 规则挖掘模型，提高负关联规则的程度，减少不 相关的关联规则，然后对最小相关度进行概率分 析，降低无关规则的产生几率。董博等[10] 针对传 统关联规则挖掘方法存在计算冗余度过高的问 题，提出一种后处理闭包算子最小单约束的关联 规则算法有效降低算法冗余计算，提高算法计算 效率。Li 等 [11] 提出了一种新的联想分类器 Sig￾Direct，利用 Fisher 的精确检验作为一种剪枝策 略，直接挖掘分类关联规则。在没有最小支持度 和最小置信度等阈值设置的情况下，SigDirect 能 够找到非冗余的分类关联规则，这些规则在一组 先前项和随后的类标签之间表现出统计上的显著 依赖性。还有一些学者提出利用智能技术进行关 联规则挖掘，而无需设置最小支持度和最小置信 度，如 Qodmanan 等 [12] 利用多目标遗传算法进行 FP-Tree 模式关联规则挖掘，Sarath 等 [13] 提出使用 二进制粒子群优化策略，吴琼等[14] 针对量化关联 规则的特点，提出基于多目标烟花算法全面搜索 关联规则，Anping 等 [15] 提出了基于 Pareto 的多目 标二进制 BAT 算法 (MBBA)。Can 等 [16] 提出利用 引力搜索算法 (GSA) 进行数值型关联规则挖掘。 这些基于智能技术，通过搜索全域空间，无须设 置最小支持度和最小置信度参数即可获取支持度 最好、置信度最高的强关联规则，存在着需要很 大计算量的问题。另一角度是利用数据内在的某 些特性确定参数的方法。如王志愿等[17] 提出根 据项集内部的语义相关度动态确定该项集的最小 支持度，并采用了项集语义相关度的增量计算方 法。实验结果表明，DS-Apriori 算法在很大程度 上提高了关联规则挖掘算法的效率和效果。Saurav 等 [18] 提出了一种基于动态阈值的 FP-生长规则挖 掘算法，该算法将基于加权最短距离的基因表 达、甲基化和蛋白−蛋白质相互作用剖面结合起 来，在多视点数据集中寻找不同基因对之间的新 关联，该方法主要优点之一是它考虑了属于每个 规则的所有成对基因之间的定量和交互意义。与 以往的方法相比，该算法生成的规则更少，运行 时间也更短，并且为得到的顶级规则提供了更大 的生物学意义，但该方法是基于生物学基础的统 计，缺乏通用性。Jitendra 等 [19] 提出了一种基于项 集范围和相关系数的关联规则集粒子群算法 SARIC，该算法能快速、客观地自动确定支持度和 置信度。林甲祥等[20] 提出一种新的自动确定支 持度和置信度阈值的方法，该方法采用数据分布 特性进行曲线拟合确定阈值，为算法的更广泛合 第 2 期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·353·