第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 卷