第15卷第2期 智能系统学报 Vol.15 No.2 2020年3月 CAAI Transactions on Intelligent Systems Mar.2020 D0:10.11992/tis.201809030 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190513.1210.002.html 基于可决系数的自适应关联规则挖掘算法 王雪平，林甲祥，巫建伟2，高敏节 (1.福建农林大学计算机与信息学院，福建福州350002：2.自然资源部第三海洋研究所，福建厦门361001) 摘要：针对以频繁项集产生-规则产生为核心的两阶段关联规则挖掘，存在需要人工以先验知识指定最小支 持度和最小置信度阈值的缺陷。本文提出以支持数和置信度为依据，采用曲线拟合技术，根据可决系数自动确 定曲线的次数及对应多项式的算法AARM_BR(Adaptation Association Rule Mining Based on Determination Coeffi- cient R),从而确定支持度和置信度阈值。在标准数据集Trolley和Groceries上进行关联规则挖掘实验，结果表 明本算法更具有数据依赖性，在用户不具备先验知识的情况下，无须人为指定多项式阶次、支持度和置信度阈 值的优点。 关键词：关联规则；阶次；自适应；可决系数：规则；支持度；置信度：曲线拟合；多项式；数据挖掘 中图分类号：TP391 文献标志码：A 文章编号：1673-4785(2020)02-0352-08 中文引用格式：王雪平，林甲样，巫建伟，等.基于可决系数的自适应关联规则挖掘算法.智能系统学报，2020,15(2)： 352-359. 英文引用格式：VANG Xueping,LIN Jiaxiang,.U Jianwei,et al.Adaptive-association-rule mining algorithm based on determina- tion coefficientJ].CAAI transactions on intelligent systems,2020,15(2):352-359. Adaptive-association-rule mining algorithm based on determination coefficient WANG Xueping',LIN Jiaxiang',WU Jianwei,GAO Minjie' (1.College of Computer and Information Sciences,Fujian Agriculture and Forestry University,Fuzhou 350002,China;2.Third Insti- tute of Oceanography,Ministry of Natural Resources,Xiamen 361001,China) Abstract:The two-stage association-rule-mining algorithm based on the frequent item set generation and rule genera- tion requires the manual assigning of minimum support and minimum confidence.To overcome this defect,this paper proposes a new method using the curve fitting technology based on the number of supports and confidence,in which the number of the order of curve and corresponding polynomial is automatically determined by a determination coefficient, which is called "adaptation association rule mining based on the determination coefficient R(AARM BR).As the pro- posed AARM_BR method is driven by data,the thresholds of support and confi-dence can be automatically obtained. The experiments on two standard datasets Trolley and Groceries show that compared with a recently published method, the proposed method is more data-dependent and automatically determines the number of order of polynomial and the threshold of support and confidence under the circumstance of not having a priori knowledge. Keywords:association rule;order,adaptive;coefficient of determination;rule;support;confidence;curve fitting;poly- nomial;data mining 收稿日期：2018-09-15.网络出版日期：2019-05-14. 关联规则挖掘是数据挖掘研究领域重要任务 基金项目：国家自然科学基金项目(41401458)：福建省自然科 之一，目标就是从事务数据集中发现隐藏的、有 学基金项目(2018J01644,2018J01645,2016J01753) 中国-东盟海上合作基金项目(2020399)：国家海洋 意义的联系，目前已广泛应用于购物篮分析、网 局第三海洋研究所项目(2016020)：福建省中青年教 师教育科研项目(JT180129). 络入侵检测、关联规则分类、交通事故模式分析、 通信作者：王雪平，E-mail:熙gfvgu@163.com 药物成分关联分析、病人症型判断等领域。常
DOI: 10.11992/tis.201809030 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190513.1210.002.html 基于可决系数的自适应关联规则挖掘算法 王雪平1 ，林甲祥1 ，巫建伟2 ，高敏节1 （1. 福建农林大学 计算机与信息学院，福建 福州 350002; 2. 自然资源部第三海洋研究所，福建 厦门 361001） 摘 要：针对以频繁项集产生−规则产生为核心的两阶段关联规则挖掘，存在需要人工以先验知识指定最小支 持度和最小置信度阈值的缺陷。本文提出以支持数和置信度为依据，采用曲线拟合技术，根据可决系数自动确 定曲线的次数及对应多项式的算法 AARM_BR(Adaptation Association Rule Mining Based on Determination Coefficient R2 )，从而确定支持度和置信度阈值。在标准数据集 Trolley 和 Groceries 上进行关联规则挖掘实验，结果表 明本算法更具有数据依赖性，在用户不具备先验知识的情况下，无须人为指定多项式阶次、支持度和置信度阈 值的优点。 关键词：关联规则；阶次；自适应；可决系数；规则；支持度；置信度；曲线拟合；多项式；数据挖掘 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)02−0352−08 中文引用格式：王雪平, 林甲祥, 巫建伟, 等. 基于可决系数的自适应关联规则挖掘算法 [J]. 智能系统学报, 2020, 15(2): 352–359. 英文引用格式：WANG Xueping, LIN Jiaxiang, WU Jianwei, et al. Adaptive-association-rule mining algorithm based on determination coefficient[J]. CAAI transactions on intelligent systems, 2020, 15(2): 352–359. Adaptive-association-rule mining algorithm based on determination coefficient WANG Xueping1 ，LIN Jiaxiang1 ，WU Jianwei2 ，GAO Minjie1 (1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou 350002, China; 2. Third Institute of Oceanography, Ministry of Natural Resources, Xiamen 361001, China) Abstract: The two-stage association-rule-mining algorithm based on the frequent item set generation and rule generation requires the manual assigning of minimum support and minimum confidence. To overcome this defect, this paper proposes a new method using the curve fitting technology based on the number of supports and confidence, in which the number of the order of curve and corresponding polynomial is automatically determined by a determination coefficient, which is called “adaptation association rule mining based on the determination coefficient R2 ” (AARM_BR). As the proposed AARM_BR method is driven by data, the thresholds of support and confi-dence can be automatically obtained. The experiments on two standard datasets Trolley and Groceries show that compared with a recently published method, the proposed method is more data-dependent and automatically determines the number of order of polynomial and the threshold of support and confidence under the circumstance of not having a priori knowledge. Keywords: association rule; order; adaptive; coefficient of determination; rule; support; confidence; curve fitting; polynomial; data mining 关联规则挖掘是数据挖掘研究领域重要任务 之一，目标就是从事务数据集中发现隐藏的、有 意义的联系，目前已广泛应用于购物篮分析、网 络入侵检测、关联规则分类、交通事故模式分析、 药物成分关联分析、病人症型判断等领域[1-3]。常 收稿日期：2018−09−15. 网络出版日期：2019−05−14. 基金项目：国家自然科学基金项目 (41401458)；福建省自然科 学基金项目 (2018J01644，2018J01645，2016J01753)； 中国−东盟海上合作基金项目 (2020399)；国家海洋 局第三海洋研究所项目 (2016020)；福建省中青年教 师教育科研项目 (JT180129). 通信作者：王雪平，E-mail：gggfvgu@163.com. 第 15 卷第 2 期 智 能 系 统 学 报 Vol.15 No.2 2020 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2020
第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、MagnumOpus、Closet 等 [1, 4] ，其中最常用也是最经典的挖 掘算法是 Apriori 算法。 为了挖取规模合适的规则，大部分关联规则 算法执行前需用户设置两个阈值：最小支持度和 最小置信度，以期找到所有超过用户设定阈值的 规则。因此，用户必须具备一定的先验知识才能 寻找到合适的最小支持度和最小置信度以便获得 有应用价值的规则。但在实际应用过程中，1) 不 同领域数据差异较大，导致算法在不同的数据集 中设置的最小支持数和最小置信度存在较大差 异，没有一个统一的标准；2) 存在许多非专业用 户，对算法参数的取值具有较大的随意性。因此 如何利用数据集本身的特性自动确定阈值而无须 先验知识是一个很有意义且亟待解决的问题。本 文针对这一问题提出基于可决系数的自适应关联 规则挖掘算法，依据待挖掘数据集中所有项的支 持数和所有规则的置信度的数据分布特性，采用 曲线拟合技术，根据可决系数自动确定拟合多项 式，并在此基础上自动确定具有数据统计依赖意 义的最小支持度和置信度，使其关联规则挖掘的 应用门槛降低。 1 相关研究 针对上述所提的参数阈值设置方面问题，在 过去的十多年中，研究者们从不同角度提出了一 些解决方法。一种角度是优化参数或减少参数的 方法。例如，Scheffer 提出的预测 Apriori 算法[5] ， 它自动解决了最小支持度和最小置信度这两个参 数之间的平衡问题，最大限度地提高了对数据集 进行精确预测的可能性。该算法利用贝叶斯方法 计算了一个称为精确期望预测精度的参数，以实 现精确的预测，从而提供规则的精确性信息。最 后的结果表明，预测 Apriori 算法的性能优于使用 增量因子的 Apriori 型算法。AI-Maqaleh 等 [6] 提出 了一种有效的置信度综合算法，在挖掘频繁项集 的过程中生成了真正有用的规则。吴瑞华等[7] 提 出了一种多重支持度关联规则挖掘算法，根据不 同数据项的特点定义多重支持度，通过挖掘数据 库中的最大频繁项目集，计算最大频繁候选项目 集在数据库中的支持度来发现关联规则，可解决 关联规则中经常出现的稀少数据项问题。陈柳等[8] 提出了一个结合项集相关性的两级置信度阈值设 置方法 (PNMC-TWO)，该方法不仅可以更好地确 保提取出的关联规则有效和有趣,还可以显著地 降低可信度低的关联规则数。于海燕[9] 提出了一 种最小相关度优化 PNARC 算法的审计数据关联 规则挖掘模型，提高负关联规则的程度，减少不 相关的关联规则，然后对最小相关度进行概率分 析，降低无关规则的产生几率。董博等[10] 针对传 统关联规则挖掘方法存在计算冗余度过高的问 题，提出一种后处理闭包算子最小单约束的关联 规则算法有效降低算法冗余计算，提高算法计算 效率。Li 等 [11] 提出了一种新的联想分类器 SigDirect，利用 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·
·354· 智能系统学报 第15卷 理应用提供了可能。但该方法对数据拟合时采用 础，在文献[20]所提基于自适应支持度和置信度 固定阶次的多项式拟合方式，实际应用中不同的 的基础上进一步改进，提出一种基于可决系数的 数据往往需要采用不同阶次的多项式拟合。 自适应关联规则挖掘算法AARM BR,该算法为 因此，在文献[20]基础上提出一种多项式曲 进一步确定更具统计意义的支持度和置信度阈值 线拟合的阶次自动确定算法AARM BR(Adapta- 提供可能。文献[20]提出一种支持度和置信度自 tion Association Rule Mining Based on Determination 适应的无参化关联规则挖掘算法AdapARM,该算 Coefficient R),为进一步自动确定支持度和置信 法是通过数学方法，拟合频繁项集支持数和规则 度阈值提供更具有数据统计依赖意义的基础。 置信度数据的曲线及其二阶导函数，确定数理意 义上最适合的数值作为关联规则挖掘的minCount 2概念术语 和minConf阈值。该文提出的自适应方法很有应 定义1D是一个事务数据集，其中每个事 用价值，但文中求取自适应支持度和自适应置信 务T是由一系列具有唯一标识TD的项目组成的 度时采用的拟合多项式是固定次数多项式。本文 项集。令={i,2,,im}是事务数据集D中所有 提出基于可决系数的自适应k次多项式拟合方 项的集合，每个事务T对应1上的一个子集，即 法，多项式次数k根据自动拟合精度确定，最后以 T,T可表示为T={t,2,,1},,eL,n为自然数 此自适应确定最小支持度和置信度阈值。 (n≤m),表示事务T项集所含的项数。包含k个 3.1自适应k次多项式 项的项集，称为k项集。 首先，根据事务数据集D中各项的支持数或 定义2项集X的支持度计数(nup(X)是指 某个关联规则集的置信度，按从大到小顺序排序 事务数据集D中包含项集X的事务个数。若项 并建立“序-值”队列，如式(1)所示。其中，V,代 集XcL,YsL,且XnY=中，则形如X=Y的蕴涵式称 表某个项在事务数据集D中的支持数或某个规 为关联规则。令事务数据集D中事务总个数为 则的置信度。对于支持数，序对的个数1等于事 hot。规则X-Y的支持度Support(X=)是指事务 务数据集D中项的个数：而对于置信度，1等于所 数据集D中同时出现X,Y的事务占事务数据库 产生的所有规则数目。 的百分比；规则X=Y的置信度Confidence(X-) {(序列值，序号)》={y,x)》={(V,1),(V2,2),…,(V,} 是指事务数据集中同时出现X,Y的事务数与包 (1) 含X的事务数之比。其计算表达式分别为 然后，以“序一值”队列中的序号为x,序列值 Support(X=Y)=amn(X UY) 为y建立有序的平面坐标点序列(x,y)(=1, 2,…,)。并采用k次多项式进行曲线拟合。拟合 Confidence(X→)="pXUy 的多项式曲线模型为 几aal 定义3最小支持度minSup和最小置信度 y=fx)=】 minConf是用户或专家定义的分别衡量支持度和 式中：k的取值根据自适应实现，从2次开始，每 置信度的两个阈值。最小支持数(minCount)是指 次递增1，求取对应多项式并判断曲线拟合程度， 某个项集X为达到最小支持度在事务数据集中至 少应出现的次数，等于最小支持度minSup乘于所 本算法中选取可决系数判断曲线的拟合程度。 有事务数：频繁项集是指支持度不小于最小支持 可决系数衡量因变量与自变量关系密切程度的 度minSup的项集；所谓强关联规则就是指满足最 指标，取值范围在[0,1]之间，越大代表曲线拟 小支持度minSup和最小置信度minConf的关联 合越好。 规则。 本算法拟合结束以相邻两阶可决系数的差 通常地，给定一个数据库D,挖掘关联规则的 小于某个值（设为Rend)为终止条件，Rend由用 过程可以转换成寻找满足最小支持度minSup和 户指定。多项式次数取拟合结束时的k值。自话 最小置信度minConf阈值的强关联规则过程，即 应k次拟合多项式算法的具体流程如图1所示， 分解成求解所有频繁项集和由频繁项集产生规则 流程中Rend取0.05。 两阶段实现。 然后，根据确定的k次多项式求取拟合曲线 的二阶导数f"(x): 3 AARM BR的设计与实现 y=f(=i-1)a2 以最经典的关联规则挖掘算法Apriori为基
理应用提供了可能。但该方法对数据拟合时采用 固定阶次的多项式拟合方式，实际应用中不同的 数据往往需要采用不同阶次的多项式拟合。 因此，在文献 [20] 基础上提出一种多项式曲 线拟合的阶次自动确定算法 AARM_BR(Adaptation Association Rule Mining Based on Determination Coefficient R2 )，为进一步自动确定支持度和置信 度阈值提供更具有数据统计依赖意义的基础。 2 概念术语 ⊆ 定义 1 D 是一个事务数据集，其中每个事 务 T 是由一系列具有唯一标识 TID 的项目组成的 项集。令 I={i1，i2，···，im}是事务数据集 D 中所有 项的集合，每个事务 T 对应 I 上的一个子集，即 T I，T 可表示为 T={t1，t2，···，tn}，ti∈I，n 为自然数 (n≤m)，表示事务 T 项集所含的项数。包含 k 个 项的项集，称为 k-项集。 ⊆ ⊆ ⇒ ⇒ ⇒ ⇒ ⇒ 定义 2 项集 X 的支持度计数 (nsup(X)) 是指 事务数据集 D 中包含项集 X 的事务个数。若项 集 X I，Y I，且 X∩Y=Φ，则形如 X Y 的蕴涵式称 为关联规则。令事务数据集 D 中事务总个数为 ntotal。规则 X Y 的支持度 Support(X Y) 是指事务 数据集 D 中同时出现 X，Y 的事务占事务数据库 的百分比；规则 X Y 的置信度 Confidence(X Y) 是指事务数据集中同时出现 X，Y 的事务数与包 含 X 的事务数之比。其计算表达式分别为 Support(X ⇒ Y) = nsup(X U Y) ntatal Confidence(X ⇒ Y) = nsup(X U Y) ntatal 定义 3 最小支持度 minSup 和最小置信度 minConf 是用户或专家定义的分别衡量支持度和 置信度的两个阈值。最小支持数 (minCount) 是指 某个项集 X 为达到最小支持度在事务数据集中至 少应出现的次数，等于最小支持度 minSup 乘于所 有事务数；频繁项集是指支持度不小于最小支持 度 minSup 的项集；所谓强关联规则就是指满足最 小支持度 minSup 和最小置信度 minConf 的关联 规则。 通常地，给定一个数据库 D，挖掘关联规则的 过程可以转换成寻找满足最小支持度 minSup 和 最小置信度 minConf 阈值的强关联规则过程，即 分解成求解所有频繁项集和由频繁项集产生规则 两阶段实现。 3 AARM_BR 的设计与实现 以最经典的关联规则挖掘算法 Apriori 为基 础，在文献 [20] 所提基于自适应支持度和置信度 的基础上进一步改进，提出一种基于可决系数的 自适应关联规则挖掘算法 AARM_BR，该算法为 进一步确定更具统计意义的支持度和置信度阈值 提供可能。文献 [20] 提出一种支持度和置信度自 适应的无参化关联规则挖掘算法 AdapARM，该算 法是通过数学方法，拟合频繁项集支持数和规则 置信度数据的曲线及其二阶导函数，确定数理意 义上最适合的数值作为关联规则挖掘的 minCount 和 minConf 阈值。该文提出的自适应方法很有应 用价值，但文中求取自适应支持度和自适应置信 度时采用的拟合多项式是固定次数多项式。本文 提出基于可决系数的自适应 k 次多项式拟合方 法，多项式次数 k 根据自动拟合精度确定，最后以 此自适应确定最小支持度和置信度阈值。 3.1 自适应 k 次多项式 首先，根据事务数据集 D 中各项的支持数或 某个关联规则集的置信度，按从大到小顺序排序 并建立“序−值”队列，如式 (1) 所示。其中，Vt 代 表某个项在事务数据集 D 中的支持数或某个规 则的置信度。对于支持数，序对的个数 t 等于事 务数据集 D 中项的个数；而对于置信度，t 等于所 产生的所有规则数目。 {(序列值,序号)} = {(y, x)} = {(V1,1),(V2,2),··· ,(Vt ,t)} (1) 然后，以“序−值”队列中的序号为 x，序列值 为 y 建立有序的平面坐标点序列 ( x i， y i )(i=1， 2，···，t)。并采用 k 次多项式进行曲线拟合。拟合 的多项式曲线模型为 y = f(x) = ∑k i=0 aix j R 2 k R 2 k R 2 k 式中：k 的取值根据自适应实现，从 2 次开始，每 次递增 1，求取对应多项式并判断曲线拟合程度， 本算法中选取可决系数 判断曲线的拟合程度。 可决系数 衡量因变量与自变量关系密切程度的 指标，取值范围在 [0，1] 之间， 越大代表曲线拟 合越好。 R 2 本算法拟合结束以相邻两阶可决系数 k的差 小于某个值 (设为 Rend) 为终止条件，Rend 由用 户指定。多项式次数取拟合结束时的 k 值。自适 应 k 次拟合多项式算法的具体流程如图 1 所示， 流程中 Rend 取 0.05。 f ′′ (x) 然后，根据确定的 k 次多项式求取拟合曲线 的二阶导数 ： y ′′ = f ′′(x) = ∑t i=2 i·(i−1)· ai · x i−2 ·354· 智 能 系 统 学 报 第 15 卷
第2期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·355· 开始 输入事务数据集D,拟合结束条件Rend 输出所有强规则SR,SR={SR1,SR2,, 初始化=l,R=0,Rend=0.05 SR,} 1)C=find candidate 1-itemsets(D); 从大到小排列支持数/置信度 2)C'=sort_InDescOrder((C)/降序排序 ∥自适应确定多项式拟合曲线的次数k =k+1 3)k=find_k_polynomial_curve_fitting(C); 产生支持数k次多项式， 创建次多项式进行曲线拟合，并计算阳 4)fx)=polynomial_curve_fitting(Ci,k); 5)find xo,where f"((xo)=0; Ri-Ri>Rend 6)minCount=int(xo),/∥xo下取整并赋给min- N Count; 7)(L,L2,,La)=find_all_frequent_k- 求k次多项式的二阶导，确定最小支持数 (minCount)/最小置信度(minConf) itemsets(D,minCount); 8){R1,R2,,R,)=generateRule_from_ 结束 frequent_k-itemsets((L,L2,,L,l/对所有规则按置 信度降序排序； 图1自适应k次拟合多项式流程 9)R'=sort InDescOrder(R,R2,·,R,∥自适应 Fig.1 The flow of adaptive k-order fitting polynomial 确定多项式拟合曲线的次数k 最后，求解拟合曲线中二阶导数f(x)=0的 10)k=find_k_polynomial_curve_fitting(R'); 点（记xo)及对应的函数值x,x下取整作为最 产生k次多项式 小支持数阈值minCount,.xo)作为最小置信度阈 11)h(x)=polynomial curve fitting(R,k); 值minConf。 12)find xo,where h"(xo)-0; 3.2 AARM BR算法实现 13)minConf=hx,/得到最小置信度； 基于可决系数自适应阶次的多项式曲线拟合 14)(SR,SR2,,SR,)=find_strong_rules((R, 模型下确定最小支持数和置信度阈值的关联规则 R2,,R),minConf); 挖掘算法AARM BR的核心流程如图2所示。 15)Return{SR,SR2,,SR}∥得到所有强 AARM BR算法描述如下： 规则。 2次 从大到小排 根据“序一 列支持数/ 多项式 值”对进行 计算R肥 置信度 曲线拟合 根据 确定 征数据 确定 求曲线二 次数 导 从大到小排 根据“序 n次 列支持数/ 值”对进行 计算吧 多项式 置信度 曲线拟合 由事务集D中所提取的特征（如支持数、置信度）→自动 确定最小支持数minCount、最小置信度ninConf 图2 AARM BR核心流程 Fig.2 Key process of AARM_BR 4实验与分析 ies数据集。Trolley数据集总共有9条消费记录 为了比较分析，选取文献[12]使用的数据集 (即9行)，包含7种不同商品；Groceries数据集有 进行实验。具体数据集为关联规则挖掘购物车 9835条消费记录（即9835行），包含169种不同 Trolley数据集和开源软件RGUI里的Grocer- 商品。下面对自适应k次多项式的挖掘流程进行
f ′′ 最后，求解拟合曲线中二阶导数 (x) = 0 的 点 (记 x0 ) 及对应的函数值 f(x0 )，x0 下取整作为最 小支持数阈值 minCount，f(x0 ) 作为最小置信度阈 值 minConf。 3.2 AARM_BR 算法实现 基于可决系数自适应阶次的多项式曲线拟合 模型下确定最小支持数和置信度阈值的关联规则 挖掘算法 AARM_BR 的核心流程如图 2 所示。 AARM_BR 算法描述如下： 输入 事务数据集 D，拟合结束条件 Rend 输出 所有强规则 SR，SR={SR1 , SR2 , ···, SRr} 1) C1 = find_candidate_1-itemsets(D); 2) C '1= sort_InDescOrder(C1 ); //降序排序 //自适应确定多项式拟合曲线的次数 k; 3) k=find_k_polynomial_curve_fitting(C '1 ); //产生支持数 k 次多项式; 4) f(x) = polynomial_curve_fitting(C '1 ,k); 5) find x0 , where f"((x0 )=0; 6) minCount =int(x0 ); //x0 下取整并赋给 minCount; 7) {L1 , L2 , ···, Lk}= find_all_frequent_kitemsets(D, minCount); 8) {R1 , R2 , ···, Rt}= generateRule_from_ frequent_k-itemsets(L1 , L2 , ···, Lk ); //对所有规则按置 信度降序排序; 9) R '= sort_InDescOrder(R1 , R2 , ···, Rt ); //自适应 确定多项式拟合曲线的次数 k 10) k=find_k_polynomial_curve_fitting(R'); //产生 k 次多项式 11) h(x) = polynomial_curve_fitting(R',k); 12) find x0 , where h"(x0 )=0; 13) minConf=h(x0 ); //得到最小置信度; 14) {SR1 , SR2 , ···, SRr} = find_strong_rules({R1 , R2 , ···, Rt}, minConf); 15) Return {SR1 , SR2 , ···, SRr} //得到所有强 规则。 由事务集D中所提取的特征 (如支持数、置信度)自动 确定最小支持数minCount、最小置信度minConf 从大到小排 列支持数/ 置信度 从大到小排 列支持数/ 置信度 根据“序- 值”对进行 曲线拟合 根据“序- 值”对进行 曲线拟合 … … 2次 多项式 n次 多项式 … 根据 R 2， 确定 曲线 拟合 次数 确定 支持 数/ 置信 度 计算R 2 计算R 2 … 特征数据 求曲线二阶导 图 2 AARM_BR 核心流程 Fig. 2 Key process of AARM_BR 4 实验与分析 为了比较分析，选取文献 [12] 使用的数据集 进行实验。具体数据集为关联规则挖掘购物车 Trolley 数据集和开源软件 R GUI 里的 Groceries 数据集。Trolley 数据集总共有 9 条消费记录 (即 9 行)，包含 7 种不同商品；Groceries 数据集有 9 835 条消费记录 (即 9 835 行)，包含 169 种不同 商品。下面对自适应 k 次多项式的挖掘流程进行 开始 从大到小排列支持数/置信度 创建k次多项式进行曲线拟合，并计算Rk 2 Y 求k次多项式的二阶导，确定最小支持数 (minCount)/最小置信度 (minConf ) N 结束 初始化k=1, R 2 k=0, Rend=0.05 k=k+1 Rk 2 -R 2 k-1>Rend 图 1 自适应 k 次拟合多项式流程 Fig. 1 The flow of adaptive k-order fitting polynomial 第 2 期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·355·
·356· 智能系统学报 第15卷 介绍，并对挖掘结果进行分析和讨论。 表1 Trolley数据集中不同k下的minCount 4.1不同阶次拟合对比 Table 1 MinCount of Trolley datasets under different k 首先，分析不同阶次多项式对自动确定支持 拟合曲线多项式 RminCount 度阈值的影响。下面给出Trolley数据集和Gro- y=0.0833x3-1.1429r2+3.5595x+4.28570.97544 ceries数据集两个数据集在不同阶次下曲线拟合 得到的minCount,.分别如表l、2所示。 4y=0.0417x-0.5833x3+2.4583x2-3.9167x+9 1 1 表2 Groceries数据集中不同k下的minCount Table 2 MinCount of Groceries datasets under different k k 拟合曲线多项式 R minCount 3 y=-0.0013x340.4135x2-42.763x+1486.1 0.887 107 4 y=2×10x-0.0081x3+1.163x2-71.273r+1734.8 0.9298 77 5 y=-4x107X+0.02x-0.0313x2+2.6457x2-107.71+1949.8 0.9545 57 Groceries数据集下确定minCount的不同阶 从表1和表2及图3可以看出：1)在相同的 次的多项式拟合曲线如图3所示。 结束条件下，不同数据集拟合采用的多项式次 +原始数据··二阶---三阶 数不一定相同，如本实验中数据集Groceries下 -·-四阶 一-五阶一一六阶 确定最小支持度时k取4次，而Trolley数据集 3000 2500 下k取3次；2)同一数据集下，拟合选取不同次 数的多项式，会影响minCount的值，从而也会影 2000 -.4x10440.0002.0.051342.6457r-107.7x+1949.8 -0.9545 响关联规则挖掘的效果。这说明不同的数据集 延1500 -2×10rY-0.0081r+1.163r-71.273r+1734.8 空1000 e-09298 下，不能采取统一阶次的多项次拟合，多项式拟 合的阶次应该根据数据拟合的实际情况自适应 500 确定。 0 其次，分析不同阶次多项式拟合对自动确定 -500 序号 置信度阈值的影响。对于Trolley数据集和Gro 图3 Groceries中不同阶次多项式拟合曲线 ceries数据集在上步minCount约束下所得规则的 Fig.3 Polynomial fitting curve of Groceries under differ- 基础上，自适应拟合确定最小置信度minConf,.得 ent order 到如表3和表4所示结果。 表3 Trolley数据集中不同k下的最小置信度 Table 3 MinConf of Trolley datasets under different k k 多项式拟合曲线公式 RE minConf 3 y=-6×10x3+0.0004x2-0.0199r+0.9358 0.9332 0.612 4 y=4×106x4-0.0003x3+0.0055x2-0.0565r+1.0007 0.9527 0.762 表4 Groceries数据集中不同k下的最小置信度 Table 4 MinConf of Groceries datasets under different k 多项式拟合曲线公式 R2 minConf 3 y=-7×1010x+2x105x2-0.0014r+0.5439 0.9954 0.094 4 y=8×105x-3×10x2+3x105x2-0.0018r+0.5647 0.9981 0.116 5 y=-1×1015x+4×102x-6×10”x3+4×1052-0.002r+0.5735 0.9985 0.065 同理，不同数据集中根据自动确定多项式次 0.02时，数据集Trolley下多项式次数为4次，而 数是不完全相同的，如本实验拟合精度差Rend 数据集Groceries的多项式次数为3次。同一数据 取O.O5时，数据集Trolley和数据集Groceries的多 集下不同阶次的多项式下得到的minConf也不尽 项式次数都是3次；而若拟合精度差Rend取 相同，如Trolley数据集下k取3次时得到min-
介绍，并对挖掘结果进行分析和讨论。 4.1 不同阶次拟合对比 首先，分析不同阶次多项式对自动确定支持 度阈值的影响。下面给出 Trolley 数据集和 Groceries 数据集两个数据集在不同阶次下曲线拟合 得到的 minCount，分别如表 1、2 所示。 Groceries 数据集下确定 minCount 的不同阶 次的多项式拟合曲线如图 3 所示。 3 000 2 500 2 000 1 500 1 000 500 -500 0 序列值 原始数据 二阶 三阶 序号 四阶 五阶 六阶 y=7×10-9x 6 -4×10-6x 5+0.000 8x 4 -0.925x 3+5.269 1x 2 -153.11x+2 144.5 R 2=0.970 4 y=-4×10-7 x 5+0.000 2x 4 -0.031 3x 3+2.645 7x 2 -107.71x+1949.8 R 2=0.954 5 y=2×10-5x 4 -0.008 1x 3+1.163x 2 -71.273x+1 734.8 R 2=0.929 8 y=-0.001 3x 5+0.413 5x 2 -42.763x+1 486.1 R 2=0.887 y=0.086 4x 2 -20.449x+1 165.3 R 2=0.791 2 1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 116 121 126 131 136 141 146 151 156 161 166 图 3 Groceries 中不同阶次多项式拟合曲线 Fig. 3 Polynomial fitting curve of Groceries under different order 从表 1 和表 2 及图 3 可以看出：1) 在相同的 结束条件下，不同数据集拟合采用的多项式次 数不一定相同，如本实验中数据集 Groceries 下 确定最小支持度时 k 取 4 次 ，而 Trolley 数据集 下 k 取 3 次 ；2) 同一数据集下，拟合选取不同次 数的多项式，会影响 minCount 的值，从而也会影 响关联规则挖掘的效果。这说明不同的数据集 下，不能采取统一阶次的多项次拟合，多项式拟 合的阶次应该根据数据拟合的实际情况自适应 确定。 其次，分析不同阶次多项式拟合对自动确定 置信度阈值的影响。对于 Trolley 数据集和 Groceries 数据集在上步 minCount 约束下所得规则的 基础上，自适应拟合确定最小置信度 minConf，得 到如表 3 和表 4 所示结果。 同理，不同数据集中根据自动确定多项式次 数是不完全相同的，如本实验拟合精度差 Rend 取 0.05 时，数据集 Trolley 和数据集 Groceries 的多 项式次数都是 3 次；而若拟合精度差 Rend 取 0.02 时，数据集 Trolley 下多项式次数为 4 次，而 数据集 Groceries 的多项式次数为 3 次。同一数据 集下不同阶次的多项式下得到的 minConf 也不尽 相同，如 Trolley 数据集下 k 取 3 次时得到 min- 表 1 Trolley 数据集中不同 k 下的 minCount Table 1 MinCount of Trolley datasets under different k k 拟合曲线多项式 Rk 2 minCount 3 y =0.083 3x 3 −1.142 9x 2 +3.559 5x+4.285 7 0.975 4 4 4 y =0.041 7x 4 −0.583 3x 3 +2.458 3x 2 −3.916 7x+9 1 1 表 2 Groceries 数据集中不同 k 下的 minCount Table 2 MinCount of Groceries datasets under different k k 拟合曲线多项式 Rk 2 minCount 3 y =−0.001 3x 3 +0.413 5x 2 −42.763x+1 486.1 0.887 107 4 y =2×10−5 x 4 −0.008 1x 3 +1.163x 2 −71.273x+1 734.8 0.929 8 77 5 y =−4×10−7 x 5 +0.000 2x 4 −0.031 3x 3 +2.645 7x 2 −107.71x+1 949.8 0.954 5 57 表 3 Trolley 数据集中不同 k 下的最小置信度 Table 3 MinConf of Trolley datasets under different k k 多项式拟合曲线公式 Rk 2 minConf 3 y =−6×10−6 x 3 +0.000 4x 2 −0.019 9x+0.935 8 0.933 2 0.612 4 y =4×10−6 x 4 −0.000 3x 3 +0.005 5x 2 −0.056 5x+1.000 7 0.952 7 0.762 表 4 Groceries 数据集中不同 k 下的最小置信度 Table 4 MinConf of Groceries datasets under different k k 多项式拟合曲线公式 Rk 2 minConf 3 y =−7×10−10 x 3 +2×10−6 x 2 −0.001 4x+0.543 9 0.995 4 0.094 4 y =8×10−13 x 4 −3×10−9 x 3 +3×10−6 x 2 −0.001 8x+0.564 7 0.998 1 0.116 5 y =−1×10−15 x 5 +4×10−12 x 4 −6×10−9 x 3 +4×10−6 x 2 −0.002x+0.573 5 0.998 5 0.065 ·356· 智 能 系 统 学 报 第 15 卷
第2期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·357· Conf为0.612，而k取4次时得到minConf为0.762； 动确定k的次数及对应的多项式。k从2开始，以 Groceries数据集下k取3次时得到minConf为 相邻两阶精度差R小于Rend为结束条件，本实 0.094,而k取4次时得到minConf为0.116。综合 验以Rend取0.05为例。本步实验结果与文献[12] 上述两部分分析说明多项式的阶次会影响阈值， 所提的AdapARM算法比较如表5所示。 从而也会影响挖掘结果。如何自适应确定多项式 然后，根据k阶多项式二阶导函数求取最小 阶次是很有必要的。 支持数，得到对应的二阶导函数及最小支持数 4.2结果对比与分析 minCount如表6所示。 根据挖掘的流程，首先选取待挖掘数据集中 按照Apriori算法思想，在上步求得的最小支 各事务项支持数作为特征数据并按支持数大小进 持数基础上，从一阶频繁项开始逐层向上，获取 行降序排序建立“序-值”对序列。 所有k阶频繁项集，并根据频繁项集产生关联规 其次，采用文中所提的自动阶次拟合方法建 则，得到如表7结果。 立“序-值”对序列的k次多项式曲线拟合模型，自 表5k次拟合多项式比较（支持数） Table 5 Comparison of k order polynomial fitting curves(support number) 数据集 算法 确定的拟合多项式（支持数） AARM BR 3 fx)=0.0833x3-1,1429r2+3.5595x+4.2857 Trolley AdapARM 3 fx=0.0833x-1.1429x2+3.5595r+4.2857 AARM BR ? f=2×10x-0.0081x3+1.163x2-71.273xr+1734.8 Groceries AdapARM fx-7x10-10x3+2×105x2-0.0014r+0.5439 表6最小支持数比较 Table 6 Comparison of Minimum support number 数据集 算法 二阶导函数（支持数） minCount AARM_BR "x)=-2.285740.5x 4 Trolley AdapARM f"x=-2.285740.5x 4 AARM_BR fcx2.3261-0.0488x42.4158×10x2 77 Groceries AdapARM fcx=0.8271-0.0077x 107 表7产生的规则数目比较 根据数据集Trolley和数据集Groceries产生 Table 7 Comparison of the produced rules number 的关联规则的置信度从大到小排序并进行k次多 项式曲线拟合，k从2开始，以相邻两阶精度差 数据集 算法 求得的关联规则数目 R小于Rend为结束条件，本实验以Rend取0.05 AARM BR 30 Trolley 为例。在本步中，两个方法得到的阶次k均为3， AdapARM 30 确定的拟合多项式如表8所示。 AARM_BR 1146 根据k次多项式二阶导函数求取最小置信 Groceries AdapARM 498 度，h(x)和hc(x)的二阶导函数h:(x)和h:(x)公 式及对应的最小置信度分别如表9所示。 表8k次拟合多项式比较（置信度） Table 8 Comparison of k order polynomial fitting curves(confidence) 数据集 算法 确定的拟合多项式（置信度） AARM BR 3 hxF-6x10x3+0.0004r2-0.0199r+0.9358 Trolley AdapARM 3 hx=-6×10x3+0.0004x2-0.0199r+0.9358 AARM_BR 3 hcx=6.7744×1010x3+1.5988x105x2-0.0014r+0.5439 Groceries AdapARM hGx)=-6.4263x10x3+6.7023x105x2-0.0027x+0.523
Conf 为 0.612，而 k 取 4 次时得到 minConf 为 0.762； Groceries 数据集下 k 取 3 次时得到 minConf 为 0.094，而 k 取 4 次时得到 minConf 为 0.116。综合 上述两部分分析说明多项式的阶次会影响阈值， 从而也会影响挖掘结果。如何自适应确定多项式 阶次是很有必要的。 4.2 结果对比与分析 根据挖掘的流程，首先选取待挖掘数据集中 各事务项支持数作为特征数据并按支持数大小进 行降序排序建立“序−值”对序列。 其次，采用文中所提的自动阶次拟合方法建 立“序−值”对序列的 k 次多项式曲线拟合模型，自 动确定 k 的次数及对应的多项式。k 从 2 开始，以 相邻两阶精度差 R 2 小于 Rend 为结束条件，本实 验以 Rend 取 0.05 为例。本步实验结果与文献 [12] 所提的 AdapARM 算法比较如表 5 所示。 然后，根据 k 阶多项式二阶导函数求取最小 支持数，得到对应的二阶导函数及最小支持数 minCount 如表 6 所示。 按照 Apriori 算法思想，在上步求得的最小支 持数基础上，从一阶频繁项开始逐层向上，获取 所有 k 阶频繁项集，并根据频繁项集产生关联规 则，得到如表 7 结果。 表 5 k 次拟合多项式比较 (支持数) Table 5 Comparison of k order polynomial fitting curves (support number) 数据集 算法 k 确定的拟合多项式(支持数) Trolley AARM_BR 3 fT (x)=0.083 3x 3 −1.142 9x 2 +3.559 5x+4.285 7 AdapARM 3 fT (x)=0.083 3x 3 −1.142 9x 2 +3.559 5x+4.285 7 Groceries AARM_BR 4 fG(x)=2×10−5 x 4 −0.008 1x 3 +1.163x 2 −71.273x+1 734.8 AdapARM 3 fG(x)=−7×10−10 x 3 +2×10−6 x 2 −0.001 4x+0.543 9 表 6 最小支持数比较 Table 6 Comparison of Minimum support number 数据集 算法 二阶导函数(支持数) minCount Trolley AARM_BR f"T (x)=−2.285 7+0.5x 4 AdapARM f"T (x)=−2.285 7+0.5x 4 Groceries AARM_BR f"G(x)=2.326 1−0.048 8 x+2.415 8×10−4 x 2 77 AdapARM f"G(x)=0.827 1−0.007 7 x 107 表 7 产生的规则数目比较 Table 7 Comparison of the produced rules number 数据集 算法 求得的关联规则数目 Trolley AARM_BR 30 AdapARM 30 Groceries AARM_BR 1 146 AdapARM 498 根据数据集 Trolley 和数据集 Groceries 产生 的关联规则的置信度从大到小排序并进行 k 次多 项式曲线拟合，k 从 2 开始，以相邻两阶精度差 R 2 小于 Rend 为结束条件，本实验以 Rend 取 0.05 为例。在本步中，两个方法得到的阶次 k 均为 3， 确定的拟合多项式如表 8 所示。 根据 k 次多项式二阶导函数求取最小置信 度，hT (x) 和 hG(x) 的二阶导函数 h"T (x) 和 h"G (x) 公 式及对应的最小置信度分别如表 9 所示。 表 8 k 次拟合多项式比较 (置信度) Table 8 Comparison of k order polynomial fitting curves (confidence) 数据集 算法 k 确定的拟合多项式(置信度) Trolley AARM_BR 3 hT (x)=−6×10−6 x 3 +0.000 4x 2 −0.019 9x+0.935 8 AdapARM 3 hT (x)=−6×10−6 x 3 +0.000 4x 2 −0.019 9x+0.935 8 Groceries AARM_BR 3 hG(x)=6.774 4×10−10 x 3 +1.598 8×10−6 x 2 −0.001 4x+0.543 9 AdapARM 3 hG(x)=−6.426 3×10−9 x 3 +6.702 3×10−6 x 2 −0.002 7x+0.523 第 2 期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·357·
·358· 智能系统学报 第15卷 表9最小置信度比较 Table 9 Comparison of minimum confidence 数据集 算法 二阶导函数（置信度） minConf AARM BR hx)=8.0101×10-3.3710x10x 0.6126373 Trolley AdapARM hfx)=8.0101×10-3.3710×103x 0.6126373 AARM BR h6(x=3.1976x106-4.0646×109x 0.0994309 Groceries AdapARM h6xF1.3405x105-3.8558×108x 0.1158444 最后，根据最小置信度确定强关联规则，得到 持数和置信度阈值，进而获取数据依赖意义下最 结果如表10所示。 小支持数和最小置信度及其强关联规则。该方法 上述算法挖掘结果比较可以看出，自适应多 根据数据自身特点，在用户不具备经验知识、不 项式挖掘的结果与人为确定多项式次数的挖掘结 指定支持度和置信度阈值的情况下，自动确定拟 果不一定相同，如Groceries数据集下人为确定次 合曲线、最小支持度和最小置信度阈值。在两个 数有可能遗漏一些重要的规则。根据数据本身的 标准数据集Trolley和Groceries上的实验结果和 特性确定多项式的拟合次数算法，不需要用户具 分析表明，该方法对关联规则的进一步推广应用 备先验知识，在不指定多项式阶数、不指定最小 具有一定价值。 支持度和最小置信度阈值的情况下，自动获取数 据统计意义下的强关联规则。自适应多项式曲线 参考文献： 拟合方法为支持度和置信度的自动确定提供了更 [1]MALIK M,MAMTA,AGARWAL R P.A survey on asso- 具数据依赖意义的解决方案。 ciation rule mining[J].International journal of research in 表10强关联规则数目比较 engineering and applied sciences,2015,5(6):48-56. Table 10 Comparison of the strong association rules num- [2]XI Jianfeng,ZHAO Zhonghao,LI Wei,et al.A traffic ac- ber cident causation analysis method based on AHP-apriori[J]. 数据集 算法 强关联规则数目 Procedia engineering,2016,137:680-687 [3]ALWIDIAN J.HAMMO B H.OBEID N.WCBa: AARM BR 22 Trolley weighted classification based on association rules al- AdapARM 22 gorithm for breast cancer disease[J].Applied soft comput- AARM BR 786 ing.2018,62:536-549. Groceries AdapARM 339 [4]张良均，杨坦，肖刚，等.MATLAB数据分析与挖掘实 战M个.北京：机械工业出版社，2016. 从时间复杂度角度分析，本算法只在经典算 [5]SCHEFFER T.Finding association rules that trade support 法Aprori算法的基础上增加了两个步骤：排序和 optimally against confidence[C]//European Conference on 多项式阶次自动确定，其中排序的时间复杂度为 Principles of Data Mining and Knowledge Discovery.Ber- O(nlogn)),多项式阶次的自动确定时间复杂度为 lin,Heidelberg,2001:424-435. Okm:与AdapARM算法比较，只多了一步自动确 [6]AL-MAQALEH B M,SHAAB S K.Efficient algorithm 定多项式阶次的单层循环。这里增加的时间在整 for mining association rules using confident frequent item- 个算法中占用很小，可忽略不计，同时对自动确 sets[C]//Third International Conference on Advanced 定最小支持度和最小置信度具有指导意义。 Computing and Communication Technologies.Rohtak,In- dia,2013 5结束语 [7]吴华瑞，张凤霞，赵春江.一种多重最小支持度关联规则 挖掘算法[].哈尔滨工业大学学报，2008,40(9)： 文中提出一种基于可决系数的数据自适应多 1447-1451 项式拟合曲线确定支持度和置信度阈值的关联规 WU Huarui,ZHANG Fengxia,ZHAO Chunjiang.An al- 则挖掘算法AARM BR。以曲线拟合的精确程度 gorithm for mining association rules with multiple minim- R为判断依据，自适应确定多项式拟合曲线的次 um supports[J].Journal of Harbin Institute of Technology, 数及多项式，在此基础上求取k次拟合多项式的 2008,40(9):1447-1451. 二阶导函数为零的点x及其函数值xo),作为支 [8]陈柳，冯山.正负关联规则两级置信度阈值设置方法
最后，根据最小置信度确定强关联规则，得到 结果如表 10 所示。 上述算法挖掘结果比较可以看出，自适应多 项式挖掘的结果与人为确定多项式次数的挖掘结 果不一定相同，如 Groceries 数据集下人为确定次 数有可能遗漏一些重要的规则。根据数据本身的 特性确定多项式的拟合次数算法，不需要用户具 备先验知识，在不指定多项式阶数、不指定最小 支持度和最小置信度阈值的情况下，自动获取数 据统计意义下的强关联规则。自适应多项式曲线 拟合方法为支持度和置信度的自动确定提供了更 具数据依赖意义的解决方案。 从时间复杂度角度分析，本算法只在经典算 法 Aprori 算法的基础上增加了两个步骤：排序和 多项式阶次自动确定，其中排序的时间复杂度为 O(nlogn)，多项式阶次的自动确定时间复杂度为 O(kn)；与 AdapARM 算法比较，只多了一步自动确 定多项式阶次的单层循环。这里增加的时间在整 个算法中占用很小，可忽略不计，同时对自动确 定最小支持度和最小置信度具有指导意义。 5 结束语 文中提出一种基于可决系数的数据自适应多 项式拟合曲线确定支持度和置信度阈值的关联规 则挖掘算法 AARM_BR。以曲线拟合的精确程度 R 2 为判断依据，自适应确定多项式拟合曲线的次 数及多项式，在此基础上求取 k 次拟合多项式的 二阶导函数为零的点 x0 及其函数值 f(x0 )，作为支 持数和置信度阈值，进而获取数据依赖意义下最 小支持数和最小置信度及其强关联规则。该方法 根据数据自身特点，在用户不具备经验知识、不 指定支持度和置信度阈值的情况下，自动确定拟 合曲线、最小支持度和最小置信度阈值。在两个 标准数据集 Trolley 和 Groceries 上的实验结果和 分析表明，该方法对关联规则的进一步推广应用 具有一定价值。 参考文献： MALIK M, MAMTA, AGARWAL R P. A survey on association rule mining[J]. International journal of research in engineering and applied sciences, 2015, 5(6): 48–56. [1] XI Jianfeng, ZHAO Zhonghao, LI Wei, et al. A traffic accident causation analysis method based on AHP-apriori[J]. Procedia engineering, 2016, 137: 680–687. [2] ALWIDIAN J, HAMMO B H, OBEID N. WCBa: weighted classification based on association rules algorithm for breast cancer disease[J]. Applied soft computing, 2018, 62: 536–549. [3] 张良均, 杨坦, 肖刚, 等. MATLAB 数据分析与挖掘实 战 [M]. 北京: 机械工业出版社, 2016. [4] SCHEFFER T. Finding association rules that trade support optimally against confidence[C]//European Conference on Principles of Data Mining and Knowledge Discovery. Berlin, Heidelberg, 2001: 424–435. [5] AL-MAQALEH B M, SHAAB S K. Efficient algorithm for mining association rules using confident frequent itemsets[C]//Third International Conference on Advanced Computing and Communication Technologies. Rohtak, India, 2013. [6] 吴华瑞, 张凤霞, 赵春江. 一种多重最小支持度关联规则 挖掘算法 [J]. 哈尔滨工业大学学报, 2008, 40(9): 1447–1451. WU Huarui, ZHANG Fengxia, ZHAO Chunjiang. An algorithm for mining association rules with multiple minimum supports[J]. Journal of Harbin Institute of Technology, 2008, 40(9): 1447–1451. [7] [8] 陈柳, 冯山. 正负关联规则两级置信度阈值设置方法 [J]. 表 9 最小置信度比较 Table 9 Comparison of minimum confidence 数据集 算法 二阶导函数(置信度) minConf Trolley AARM_BR h"T (x)=8.010 1×10−4−3.371 0×10−5 x 0.612 637 3 AdapARM h"T (x)=8.010 1×10−4−3.371 0×10−5 x 0.612 637 3 Groceries AARM_BR h"G (x)=3.197 6×10−6−4.064 6×10−9 x 0.099 430 9 AdapARM h"G (x)=1.340 5×10−5−3.855 8×10−8 x 0.115 844 4 表 10 强关联规则数目比较 Table 10 Comparison of the strong association rules number 数据集 算法 强关联规则数目 Trolley AARM_BR 22 AdapARM 22 Groceries AARM_BR 786 AdapARM 339 ·358· 智 能 系 统 学 报 第 15 卷
第2期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·359· 计算机应用，2018,38(5)1315-1319,1338 法研究.计算机工程与设计，2011,32(3)：936-939， CHEN Liu,FENG Shan.Two-level confidence threshold 944 setting method for positive and negative association WANG Zhiyuan,XIA Shixiong,ZHANG Lei,et al. rules[J].Journal of computer applications,2018,38(5): Study on semantic-driven association rule mining al- 1315-1319.1338. gorithm[J].Computer engineering and design,2011, [9]于海燕.最小相关度优化PNARC算法的审计数据关联 32(3:936-939,944. 规则挖掘模型).科技通报，2017,3312：158-161 [18]MALLIK S,BHADRA T.MUKHERJI A.DTFP-growth: YU Haiyan.Research on audit data association rule min- dynamic threshold-based FP-growth rule mining al- ing model with minimal relevance optimized PNARC al- gorithm through integrating gene expression,methylation. gorithm[J].Bulletin of science and technology,2017, and protein-protein interaction profiles[J].IEEE transac- 33(12):158-161. tions on nanobioscience,2018,17(2):117-125. [10]董博，王雪.关联规则算法的计算效率优化研究).计 [19]AGRAWAL J.AGRAWAL S,SINGHAI A.et al.SET- 算机仿真，2017,349)：247-253. PSO-based approach for mining positive and negative as- DONG Bo,WANG Xue.Closure operator based post pro- sociation rules[J].Knowledge and information systems, cessing minimum single constraint association[J.Com- 2015,45(2):453-471. puter simulation,2017,34(9):247-253. [20]林甲祥，巫建伟，陈崇成.等.支持度和置信度自适应的 [11]LI Jundong,ZAIANE O.Exploiting statistically signific- 关联规则挖掘.计算机工程与设计，2018,39(12)： ant dependent rules for associative classification[].Intel- 3746-3754. ligent data analysis,2017,21(5):1155-1172 LIN Jiaxiang,WU Jianwei,CHEN Chongcheng,et al.As- [12]Qodmanan H R,Nasiri M,Minaei-Bidgoli B.Multi ob- jective association rule mining with genetic algorithm sociation rule mining algorithm with adaptive support and without specifying minimum support and minimum con- confidence[J].Computer engineering and design,2018, fidence[J].Expert systems with applications,2011,38(1): 39(12:3746-3754 288-298. 作者简介： [13]SARATH K N V D.RAVI V.Association rule mining us- 王雪平，讲师，主要研究方向为数 ing binary particle swarm optimization[J].Engineering 据挖掘、模式识别。主持省级科研项 applications of artificial intelligence,2013,26(8): 目1项，参与省级科研项目10余项。 1832-1840. [14]吴琼，曾庆鹏.基于多目标烟花算法的关联规则挖掘 ).模式识别与人工智能，2017,30(4)：365-376. WU Qiong,ZENG Qingpeng.Association rules mining based on multi-objective fireworks optimization al- 林甲样，博士。主要研究方向为 gorithm[J].Pattern recognition and artificial intelligence, 空间数据挖掘、人工智能和大数据。 2017,30(4)365-376. 主持国家级和省部级科研项目4项 参与省部级科研项目20余项：获福建 [15]A.S.1,X.D.1,J.C.2,et al.Multi-objective associati-on 省科学技术奖二等奖1项.获国家发 rule mining with binary bat algorithm[M].School of 明专利授权2项.获国家计算机软件 Computer Engineering and Science,Shanghai University, 著作权登记5项。发表学术论文40 Shanghai,China.Yale Stem Cell Center and Department 余篇。 of Cell Biology,Yale University School of Medicine, New Haven,USA,2016:105-128. 巫建伟，工程师，博土。主要研究 方向为海洋环境管理信息系统、空间 [16]CAN U,ALATAS B.Automatic mining of quantitative 数据挖掘、海洋大数据分析。主持或 association rules with gravitational search algorithm[J]. 参与国家级和省部级科研项目10余 International journal of software engineering and know- 项。发表学术论文10余篇。 ledge engineering,2017,27(3):343-372 [17刀王志愿，夏土雄，张磊，等.语义驱动的关联规则挖掘算
计算机应用, 2018, 38(5): 1315–1319, 1338. CHEN Liu, FENG Shan. Two-level confidence threshold setting method for positive and negative association rules[J]. Journal of computer applications, 2018, 38(5): 1315–1319, 1338. 于海燕. 最小相关度优化 PNARC 算法的审计数据关联 规则挖掘模型 [J]. 科技通报, 2017, 33(12): 158–161. YU Haiyan. Research on audit data association rule mining model with minimal relevance optimized PNARC algorithm[J]. Bulletin of science and technology, 2017, 33(12): 158–161. [9] 董博, 王雪. 关联规则算法的计算效率优化研究 [J]. 计 算机仿真, 2017, 34(9): 247–253. DONG Bo, WANG Xue. Closure operator based post processing minimum single constraint association[J]. Computer simulation, 2017, 34(9): 247–253. [10] LI Jundong, ZAIANE O. Exploiting statistically significant dependent rules for associative classification[J]. Intelligent data analysis, 2017, 21(5): 1155–1172. [11] Qodmanan H R, Nasiri M, Minaei-Bidgoli B. Multi objective association rule mining with genetic algorithm without specifying minimum support and minimum confidence[J]. Expert systems with applications, 2011, 38(1): 288–298. [12] SARATH K N V D, RAVI V. Association rule mining using binary particle swarm optimization[J]. Engineering applications of artificial intelligence, 2013, 26(8): 1832–1840. [13] 吴琼, 曾庆鹏. 基于多目标烟花算法的关联规则挖掘 [J]. 模式识别与人工智能, 2017, 30(4): 365–376. WU Qiong, ZENG Qingpeng. Association rules mining based on multi-objective fireworks optimization algorithm[J]. Pattern recognition and artificial intelligence, 2017, 30(4): 365–376. [14] A. S. 1, X. D. 1, J. C. 2, et al. Multi-objective associati-on rule mining with binary bat algorithm[M]. School of Computer Engineering and Science, Shanghai University, Shanghai, China. Yale Stem Cell Center and Department of Cell Biology, Yale University School of Medicine, New Haven, USA, 2016: 105–128. [15] CAN U, ALATAS B. Automatic mining of quantitative association rules with gravitational search algorithm[J]. International journal of software engineering and knowledge engineering, 2017, 27(3): 343–372. [16] [17] 王志愿, 夏士雄, 张磊, 等. 语义驱动的关联规则挖掘算 法研究 [J]. 计算机工程与设计, 2011, 32(3): 936–939, 944. WANG Zhiyuan, XIA Shixiong, ZHANG Lei, et al. Study on semantic-driven association rule mining algorithm[J]. Computer engineering and design, 2011, 32(3): 936–939, 944. MALLIK S, BHADRA T, MUKHERJI A. DTFP-growth: dynamic threshold-based FP-growth rule mining algorithm through integrating gene expression, methylation, and protein-protein interaction profiles[J]. IEEE transactions on nanobioscience, 2018, 17(2): 117–125. [18] AGRAWAL J, AGRAWAL S, SINGHAI A, et al. SETPSO-based approach for mining positive and negative association rules[J]. Knowledge and information systems, 2015, 45(2): 453–471. [19] 林甲祥, 巫建伟, 陈崇成, 等. 支持度和置信度自适应的 关联规则挖掘 [J]. 计算机工程与设计, 2018, 39(12): 3746–3754. LIN Jiaxiang, WU Jianwei, CHEN Chongcheng, et al. Association rule mining algorithm with adaptive support and confidence[J]. Computer engineering and design, 2018, 39(12): 3746–3754. [20] 作者简介： 王雪平，讲师，主要研究方向为数 据挖掘、模式识别。主持省级科研项 目 1 项，参与省级科研项目 10 余项。 林甲祥，博士。主要研究方向为 空间数据挖掘、人工智能和大数据。 主持国家级和省部级科研项目 4 项， 参与省部级科研项目 20 余项；获福建 省科学技术奖二等奖 1 项，获国家发 明专利授权 2 项，获国家计算机软件 著作权登记 5 项。发表学术论文 40 余篇。 巫建伟，工程师，博士。主要研究 方向为海洋环境管理信息系统、空间 数据挖掘、海洋大数据分析。主持或 参与国家级和省部级科研项目 10 余 项。发表学术论文 10 余篇。 第 2 期 王雪平，等：基于可决系数的自适应关联规则挖掘算法 ·359·