基于定量关联规则树的分类及回归预测算法

工程科学学报，第38卷，第6期：886892,2016年6月 Chinese Journal of Engineering,Vol.38,No.6:886-892,June 2016 DOI:10.13374/j.issn2095-9389.2016.06.020:http://journals.ustb.edu.cn 基于定量关联规则树的分类及回归预测算法 玲12四，李树林12，吴璐璐2》 1)北京科技大学自动化学院，北京1000832)北京科技大学钢铁流程先进控制教有部重点实验室，北京100083 ☒通信作者，E-mail:lingwang@usth.ed.cen 摘要为了解决基于Apriori的分类关联规则算法挖掘数值型数据时效率和准确率偏低的问题，提出基于定量关联规则树 的分类及回归预测算法.采用改进的定量关联规则算法挖掘数值型数据生成关联规则库，并基于关联规则树结构实现分类 及回归预测.研究结果表明：改进的Apoi定量关联规则挖掘算法提高了分类预测的准确率并降低了计算复杂度：而采用关 联规则树结构可使分类与回归预测时间明显加快，提高了样本匹配学习的速度 关键词数值挖掘：算法：关联规则：分类方法：回归方法 分类号TP311 Categorization and regression algorithm based on the quantitative association rule tree WANG Ling,LI Shu-in'),WU Lu-u2 1)School of Automation and Electrical Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Key Laboratory of Advanced Control of Iron and Steel Process (Ministry of Education),Beijing 100083,China Corresponding author,E-mail:lingwang@ustb.edu.cn ABSTRACT To solve the problem of the low efficiency and accuracy of numerical data mining based on the Apriori categorization association rule algorithm,this article introduces a categorization and regression algorithm based on the quantitative association rule tree.The modified quantitative association rule algorithm is adopted to mine numerical datasets to generate an association rule base, and the association rule tree (QART)is reconstructed to realize the categorization and regression prediction.The results show that quantitative association based on the modified Apriori algorithm is helpful for improving the accuracy of categorization and regression and reducing the computational complexity,and the quantitative association rule tree can improve the efficiency of categorization and regression and increase the rule matching speed. KEY WORDS data mining:algorithms;association rules;categorization methods:regression methods 关联规则挖掘是数据挖掘技术的主要研究内但占用了大量的内存.此外，关联规则算法一旦形成 容，它表现了频繁出现在给定数据集中的属性-值之 分类规则，在分类新样本时，需要多次扫描数据库且 间的强关联.目前关联规则已用于解决分类问题，其 需要逐条匹配每个侯选项集的关联规则，其效率会 基本思想是搜索频繁模式与类标号之间的强关联， 急剧下降，并且都不能实现对数值数据的回归预测. 其中关联分类算法CBA四最早被提出，它类似于 本文在采用改进的Apriori网算法的基础上挖掘 Apriori算法，主要缺点是需要多次扫描数据库，产生 定量关联规则，重构关联规则实现对分类及回归的 大量的侯选项集，CMAR可算法则是采用频繁模式 预测.为了便于规则存储及匹配学习，仅扫描两次关 增长算法，只需扫描数据库两次就可以产生频繁项， 联规则库，实现关联规则树的构建.对新样本预测 收稿日期：2015-06-19 基金项目：国家自然科学基金资助项目(61572073)：中央高校基本科研业务费资助项目(RF-SD-12-009B):北京科技大学研究生教材专 项基金资助项目

工程科学学报，第 38 卷，第 6 期: 886--892，2016 年 6 月 Chinese Journal of Engineering，Vol． 38，No． 6: 886--892，June 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 06． 020; http: / /journals． ustb． edu． cn 基于定量关联规则树的分类及回归预测算法 王 玲1，2) ，李树林1，2) ，吴璐璐1，2) 1) 北京科技大学自动化学院，北京 100083 2) 北京科技大学钢铁流程先进控制教育部重点实验室，北京 100083  通信作者，E-mail: lingwang@ ustb． edu． cn 摘 要 为了解决基于 Apriori 的分类关联规则算法挖掘数值型数据时效率和准确率偏低的问题，提出基于定量关联规则树 的分类及回归预测算法． 采用改进的定量关联规则算法挖掘数值型数据生成关联规则库，并基于关联规则树结构实现分类 及回归预测． 研究结果表明: 改进的 Apriori 定量关联规则挖掘算法提高了分类预测的准确率并降低了计算复杂度; 而采用关 联规则树结构可使分类与回归预测时间明显加快，提高了样本匹配学习的速度． 关键词 数值挖掘; 算法; 关联规则; 分类方法; 回归方法 分类号 TP311 Categorization and regression algorithm based on the quantitative association rule tree WANG Ling1，2)  ，LI Shu-lin1，2) ，WU Lu-lu1，2) 1) School of Automation and Electrical Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Key Laboratory of Advanced Control of Iron and Steel Process ( Ministry of Education) ，Beijing 100083，China  Corresponding author，E-mail: lingwang@ ustb． edu． cn ABSTＲACT To solve the problem of the low efficiency and accuracy of numerical data mining based on the Apriori categorization association rule algorithm，this article introduces a categorization and regression algorithm based on the quantitative association rule tree． The modified quantitative association rule algorithm is adopted to mine numerical datasets to generate an association rule base， and the association rule tree ( QAＲT) is reconstructed to realize the categorization and regression prediction． The results show that quantitative association based on the modified Apriori algorithm is helpful for improving the accuracy of categorization and regression and reducing the computational complexity，and the quantitative association rule tree can improve the efficiency of categorization and regression and increase the rule matching speed． KEY WOＲDS data mining; algorithms; association rules; categorization methods; regression methods 收稿日期: 2015--06--19 基金项目: 国家自然科学基金资助项目( 61572073) ; 中央高校基本科研业务费资助项目( FＲF － SD － 12 － 009B) ; 北京科技大学研究生教材专 项基金资助项目 关联 规 则 挖 掘 是 数 据 挖 掘 技 术 的 主 要 研 究 内 容，它表现了频繁出现在给定数据集中的属性!值之 间的强关联． 目前关联规则已用于解决分类问题，其 基本思想是搜索频繁模式与类标号之间的强关联， 其中关 联 分 类 算 法 CBA［1］ 最 早 被 提 出，它 类 似 于 Apriori 算法，主要缺点是需要多次扫描数据库，产生 大量的侯选项集． CMAＲ［2］算法则是 采 用 频 繁 模 式 增长算法，只需扫描数据库两次就可以产生频繁项， 但占用了大量的内存． 此外，关联规则算法一旦形成 分类规则，在分类新样本时，需要多次扫描数据库且 需要逐条匹配每个侯选项集的关联规则，其效率会 急剧下降，并且都不能实现对数值数据的回归预测． 本文在采用改进的 Apriori［3］算法的基础上挖掘 定量关联规则，重构关联规则实现对分类及回归的 预测． 为了便于规则存储及匹配学习，仅扫描两次关 联规则库，实现关联 规 则 树 的 构 建． 对 新 样 本 预 测

王玲等：基于定量关联规则树的分类及回归预测算法 ·887· 时，可以有效提高预测的快速性及精确性 Rule,If min (c.)<x<max(c), 算法主要步骤如下：(1)将训练样本表示成标称 min(c2.,）<x2<max(c2.）, 向量的形式：(2)利用改进的Apriori定量关联规则挖 掘算法找出各类别的频繁模式集，每个频繁模式与所 …,min(ca.)<xn<max(c） 属类别构造分类与回归规则，并计算规则置信度：(3) Then min(c)<<max(c), 构建关联规则树实现规则的存储：(4)找出与新样本 y=a+店 (1) 匹配的分类与回归规则，预测其输出. 其中Rule,表示第I条规则，规则前件是定量关联规则 1概念与算法 导出的规则前件，min(c.)和max(c.t)分别表示属性 1.1基本理论概念 x,第i,(1≤i,≤n,)个离散状态区间的最小和最大值. 定义1属性的离散化表示：给定原始数据集 规则后件min(c.n)<y0<max(c.m）是输出类别为m D.={T,T2,…,Tw},其中N为数据样本的个数，每个 的离散状态区间.规则后件还可表达为一个回归预测 样本为T=(x,,…,),其中T(1≤j≤N)∈D., 函数，其系数a可由最小二乘算法估计得出. (1≤i≤n)表示第j样本的第i维属性.通过基于聚 1.2改进的定量关联规则挖掘算法 类的离散化技术，属性x:离散化为项集c:={c.1c.2, 为了利用Apriori算法实现数值型数据的规则挖 …,cn},其中cn表示第i维属性的第n:个离散状态 掘，同时减少数据库的扫描次数，提高该算法的运行效 区间，状态区间数用1到n:的一组整数表示，这些整 率，首先提出一种改进的定量关联规则挖掘算法，实现 数不代表任何特定的顺序. 定量关联规则的高效快速挖掘，算法流程图如图1 定义2项集的标称向量表示：对一个特定状态 所示 的属性维，对应该状态值的二元变量为1，而其他的二 由离散化数据构建标称向量矩阵X, 元变量为0.对应这种形式的编码，样本可以表示为标 称向量.比如，对于样本{x,x},属性x,和x2分别 构建支持度存储向量S,并得到频繁1-项集 离散化为三个状态和两个状态，则离散化项集{1,2} 表示为标称向量v=(10001),属性x,的第1个状态赋 由频繁k-1项集L,得到候选频繁-项集C, 值为1，其余状态赋值为0，属性2的第2个状态赋值 并山知阵运算得到颇繁k-项集L 为1，其余状态赋值为0. 定义3支持度：已知数据样本集D.,其对应的标 令=k+】.判断 称向量矩阵表示为X。,频繁k项集L的标称向量表 频繁项集L,是否为空 示为，频繁k-项集L4在D,中的支持度是矩阵X:与 标称向量v相乘得到的向量中“k”的个数，记为S,则 是上 算规则置信度，保留数值大于min col的项集 称S。为项集L的支持度 得到定量关联规则 定义4支持度存储向量：向量S记录所有频繁k 图1算法流程图 项集的支持度，对某个频繁k-项集L形成一个标称向 Fig.1 Flow chart of algorithm 量v,并将其看成一组二进制数据，进而转换成十进制 数为d,利用向量S的第d位存储项集L的支持度，构 步骤1将离散化的数据转化为标称向量矩阵 成的向量S称为支持度存储向量. 定义5频繁模式：给定最小支持度阈值minsup, 步骤2将标称向量矩阵每列的元素相加，得到 若项集L4的支持度大于等于minsup,称项集L4是频 一个支持度存储向量S,行向量中每一位元素代表相 繁的，频繁项集也称频繁模式。 应变量类别的支持度，如果该支持度大于最小支持度 定义6分类与回归预测关联规则：将频繁k项 minsup,则为频繁l-项集L,并将每个频繁l-项集的支 集L,的各个频繁项集中输入变量作为规则前件（记为 持度记录在向量S中.令k=2,继续挖掘频繁k-项集. A),将输出变量作为规则后件（记为B),形成定量关 步骤3将频繁k-1项集L-中只有一项不同的 联规则A三B. 项集两两连接，作为候选频繁k项集C.利用矩阵运 通过引入TS模糊规则推理，将已有的定量关联规 算统计项集的支持度，将各项集的支持度同样记录在 则改写为式(1)，其与TS模糊规则有类似前后件表达 向量S中，并与最小支持度相比较得出频繁k-项集L: 式，并可以利用模糊推理计算回归预测输出值. 步骤4令k=k+1,如果频繁项集L-1为空，则

王 玲等: 基于定量关联规则树的分类及回归预测算法 时，可以有效提高预测的快速性及精确性． 算法主要步骤如下: ( 1) 将训练样本表示成标称 向量的形式; ( 2) 利用改进的 Apriori 定量关联规则挖 掘算法找出各类别的频繁模式集，每个频繁模式与所 属类别构造分类与回归规则，并计算规则置信度; ( 3) 构建关联规则树实现规则的存储; ( 4) 找出与新样本 匹配的分类与回归规则，预测其输出． 1 概念与算法 1. 1 基本理论概念 定义 1 属性的离散化表示: 给 定 原 始 数 据 集 Ds = { T1，T2，…，TN } ，其中 N 为数据样本的个数，每个 样本为 Tj = ( xj 1，xj 2，…，xj n ) ，其中 Tj ( 1≤j≤N) ∈Ds， xj i ( 1≤i≤n) 表示第 j 样本的第 i 维属性． 通过基于聚 类的离散化技术，属性 xi 离散化为项集 ci = { ci，1，ci，2， …，ci，ni } ，其中 ci，ni 表示第 i 维属性的第 ni 个离散状态 区间，状态区间数用 1 到 ni 的一组整数表示，这些整 数不代表任何特定的顺序． 定义 2 项集的标称向量表示: 对一个特定状态 的属性维，对应该状态值的二元变量为 1，而其他的二 元变量为 0． 对应这种形式的编码，样本可以表示为标 称向量 v． 比如，对于样本{ x1，x2 } ，属性 x1 和 x2 分别 离散化为三个状态和两个状态，则离散化项集{ 1，2} 表示为标称向量 v = ( 10001) ，属性 x1 的第 1 个状态赋 值为 1，其余状态赋值为 0，属性 x2 的第 2 个状态赋值 为 1，其余状态赋值为 0． 定义 3 支持度: 已知数据样本集 Ds，其对应的标 称向量矩阵表示为 XB，频繁 k-项集 Lk 的标称向量表 示为 v，频繁 k-项集 Lk 在 Ds 中的支持度是矩阵 XB 与 标称向量 v 相乘得到的向量中“k”的个数，记为 Sk，则 称 Sk 为项集 Lk 的支持度． 定义 4 支持度存储向量: 向量 S 记录所有频繁 k 项集的支持度，对某个频繁 k-项集 Lk 形成一个标称向 量 v，并将其看成一组二进制数据，进而转换成十进制 数为 d，利用向量 S 的第 d 位存储项集 Lk 的支持度，构 成的向量 S 称为支持度存储向量． 定义 5 频繁模式: 给定最小支持度阈值 minsup， 若项集 Lk 的支持度大于等于 minsup，称项集 Lk 是频 繁的，频繁项集也称频繁模式． 定义 6 分类与回归预测关联规则: 将频繁 k-项 集 Lk 的各个频繁项集中输入变量作为规则前件( 记为 A) ，将输出变量作为规则后件( 记为 B) ，形成定量关 联规则 AB． 通过引入 TS 模糊规则推理，将已有的定量关联规 则改写为式( 1) ，其与 TS 模糊规则有类似前后件表达 式，并可以利用模糊推理计算回归预测输出值． Ｒulel : If min( c1，i1 ) ＜ x1 ＜ max( c1，i1 ) ， min( c2，i2 ) ＜ x2 ＜ max( c2，i2 ) ， …，min( cn，i n ) ＜ xn ＜ max( cn，i n ) Then min( cy，m ) ＜ y ( l) ＜ max( cy，m ) ， y ( l) = a( m) 0 + ∑ n i = 1 a( m) i xi ( 1) 其中 Ｒulel 表示第 l 条规则，规则前件是定量关联规则 导出的规则前件，min( c1，i1 ) 和 max( c1，i1 ) 分别表示属性 x1 第 i1 ( 1≤i1≤n1 ) 个离散状态区间的最小和最大值． 规则后件 min( cy，m ) ＜ y ( l) ＜ max( cy，m ) 是输出类别为 m 的离散状态区间． 规则后件还可表达为一个回归预测 函数，其系数 a( m) i 可由最小二乘算法估计得出． 1. 2 改进的定量关联规则挖掘算法 为了利用 Apriori 算法实现数值型数据的规则挖 掘，同时减少数据库的扫描次数，提高该算法的运行效 率，首先提出一种改进的定量关联规则挖掘算法，实现 定量关联规则的高效快速挖掘，算法流程图 如 图 1 所示． 图 1 算法流程图 Fig． 1 Flow chart of algorithm 步骤 1 将离散化的数据转化为标称向量矩阵 XB ． 步骤 2 将标称向量矩阵每列的元素相加，得到 一个支持度存储向量 S，行向量中每一位元素代表相 应变量类别的支持度，如果该支持度大于最小支持度 minsup，则为频繁 1-项集 L1，并将每个频繁 1-项集的支 持度记录在向量 S 中． 令 k = 2，继续挖掘频繁 k-项集． 步骤 3 将频繁 k － 1 项集 Lk － 1中只有一项不同的 项集两两连接，作为候选频繁 k-项集 Ck ． 利用矩阵运 算统计项集的支持度，将各项集的支持度同样记录在 向量 S 中，并与最小支持度相比较得出频繁 k-项集 Lk ． 步骤 4 令 k = k + 1，如果频繁项集 Lk － 1 为空，则 · 788 ·

·888· 工程科学学报，第38卷，第6期 跳转到步骤5.否则返回步骤3. cass=0.0151-0.0900x2+0.1694x3+0.4979x4 步骤5首先删除不包含输出变量的项集，然后 (3) 将各个频繁项集的输入变量作为规则前件（记为 在扫描第1条关联规则时，由于当前关联规则树 A),将输出作为规则后件（记为B),计算规则的置信 为空，所以第1条关联规则即为关联规则树的第1个 度.此时无需再次扫描数据库，直接根据向量中记录 分支，关联规则第1项成为关联规则树根节点的子节 的项集支持度即可.保留置信度大于最小置信度阈 点，其余各项沿着路径分支依次链接。继续扫描下一 值min cof的项集，令关联规则前件为项集中所有输 条关联规则，首先判断关联规则树第1层节点中是否 入变量相关项，关联规则后件为输出变量相关项. 存在该条关联规则的第1项，如果存在则树中第1层 为了实现分类和回归预测，在改进的定量关联规 无需新增节点，反之亦然.依此类推，如果关联规则的 则挖掘算法的基础上，对关联规则库进行重构.考虑 第2项已经是关联规则树第1层节点的子节点，则关 到规则存储的便捷，同时为了提高数据与规则匹配学 联规则树第2层无需新增节点，否则需要新增节点. 习的效率，提出了一种关联规则树的构建方法，确保快 当扫描到某条关联规则的最后一项（假设为该条规则 速并准确地实现新数据的分类和回归预测. 第i项)时，在树的相应层（第i层）新增一个叶节点， 1.3关联规则树构建 并在叶节点中记录这条关联规则的后件的输出类别、 与频繁模式树构建方法不同，利用已形成的关联 关联规则后件线性表达式系数和置信度.如此进行， 规则的基础上构建关联规则树，无需扫描原始数据集， 形成最终的关联规则树. 只需要扫描两遍关联规则库.主要分为以下两步. 表1lis数据集关联规则项头表 第1遍扫描关联规则库生成项头表.计算各个 Table 1 Header table of association rules with Iris dataset 1-项集在关联规则库中的支持度，并按支持度降序的 序号变量编码类别支持度重要度最小值最大值宽度 顺序排序.将其中输入输出变量所含项集分别按其支 1 4 360.021.01.50.170106 持度的降序进行排序构成项头表的两部分，分别记为 4 4 0.020.1 0.30.056955 filist,filist-2.若两项的支持度相同，则按其重要度排 3 3 3 4 0.02 3.0 4.3 0.343608 序项，重要度定义如下式： 3 0.02 2.0 2.70.186982 Importance(I,)=∑ p(L,0) 5 3 2 2 0.02 0.116697 (2) 1.5 1.9 P (I)p(O) 6 002 1.0 1.40.108530 式中，！和O分别表示输入及输出变量的相关项集， 7 1.6 2.0 0.127210 ko表示输出变量的类别数.p(I,O)表示项集(I,O) 57 5.90.204978 在规则库中的支持度，p(I:)和p(O)分别表示项I:和 9 2.1 2.5 0.135571 0在规则库中的支持度 10 3.2 3.50.112706 以Iis数据集为例，表1给出了扫描关联规则库 0.02 4.4 5.10.245571 后生成的项头表.项头表记录着项变量及所属类别、 3 007 4.8 5 0.083095 支持度、项重要度、项变量某一类别的最大最小值、项 2 1 0.02 2.8 3.10.104878 变量某一类别的宽度（数据方差的平方根）.当有新的 14 0 2.0 2.00 预测样本时，可以根据项头表判断该数据的每个维度 1.0 1.00 是否与规则库中涉及的变量类别相匹配，实现新样本 16 5 3 0 3.0 3.00 的离散化. 第2遍扫描关联规则库构造关联规则树，用项头 关联规则树构建算法： 表中的序号来表示每个关联规则中对应的各个项.例 步骤1第1次扫描关联规则库，统计规则库中 如表1中变量为4且类别为3的项对应项头表中的序 每个项的支持度，将有关输入输出变量的项分别按支 号为1，因此可以用序号1来表示这一项.按照此方法 持度和重要度进行降序排序作为项头表的两部分，并 将所有关联规则中的项转化为各个项集的序号.例如 合并为最终的项头表. 一条关联规则如式(3)所示（其中x,中i为变量编码）， 步骤2因为关联规则中的每一项与项头表中 转换得到表达形式为“1and3and4==>14” 的记录一一对应，再次扫描关联规则库时，用项头表 f2≤x2≤2.7，and3≤x3≤4.3， 中项的序号表示原始关联规则.初始创建规则树是 and1≤x.≤1.5， 空树，没有节点（记为T).假设pIP]是其中一条关 Then class is 2, 联规则ule,p即为rule的第1项，P为rule的剩余

工程科学学报，第 38 卷，第 6 期 跳转到步骤 5． 否则返回步骤 3． 步骤 5 首先删除不包含输出变量的项集，然后 将各个 频 繁 项 集 的 输 入 变 量 作 为 规 则 前 件 ( 记 为 A) ，将输出作为规则后件( 记为 B) ，计算规则的置信 度． 此时无需再次扫描数据库，直接根据向量中记录 的项集支持度即可． 保留置信度大于最小置信度阈 值min cof的项集，令关联规则前件为项集中所有输 入变量相关项，关联规则后件为输出变量相关项． 为了实现分类和回归预测，在改进的定量关联规 则挖掘算法的基础上，对关联规则库进行重构． 考虑 到规则存储的便捷，同时为了提高数据与规则匹配学 习的效率，提出了一种关联规则树的构建方法，确保快 速并准确地实现新数据的分类和回归预测． 1. 3 关联规则树构建 与频繁模式树构建方法不同，利用已形成的关联 规则的基础上构建关联规则树，无需扫描原始数据集， 只需要扫描两遍关联规则库． 主要分为以下两步． 第 1 遍扫描关联规则库生成项头表． 计算各个 1-项集在关联规则库中的支持度，并按支持度降序的 顺序排序． 将其中输入输出变量所含项集分别按其支 持度的降序进行排序构成项头表的两部分，分别记为 filist-1，filist-2． 若两项的支持度相同，则按其重要度排 序． 项 Ii 重要度定义如下式: Importance( Ii ) = ∑ kO j = 1 p( Ii，Oj ) p( Ii ) p( Oj ) ． ( 2) 式中，Ij 和 Oj 分别表示输入及输出变量的相关项集， kO 表示输出变量的类别数． p( Ii，Oj) 表示项集( Ii，Oj) 在规则库中的支持度，p( Ii ) 和 p( Oj) 分别表示项 Ii 和 Oj 在规则库中的支持度． 以 Iris 数据集为例，表 1 给出了扫描关联规则库 后生成的项头表． 项头表记录着项变量及所属类别、 支持度、项重要度、项变量某一类别的最大最小值、项 变量某一类别的宽度( 数据方差的平方根) ． 当有新的 预测样本时，可以根据项头表判断该数据的每个维度 是否与规则库中涉及的变量类别相匹配，实现新样本 的离散化． 第 2 遍扫描关联规则库构造关联规则树，用项头 表中的序号来表示每个关联规则中对应的各个项． 例 如表 1 中变量为 4 且类别为 3 的项对应项头表中的序 号为 1，因此可以用序号 1 来表示这一项． 按照此方法 将所有关联规则中的项转化为各个项集的序号． 例如 一条关联规则如式( 3) 所示( 其中 xi中 i 为变量编码) ， 转换得到表达形式为“1 and 3 and 4 = = ＞ 14”． If 2≤x2≤2. 7，and 3≤x3≤4. 3， and 1≤x4≤1. 5， Then class is 2， class = 0. 0151 － 0. 0900x2 + 0. 1694x3 + 0. 4979x4 ( 3) 在扫描第 1 条关联规则时，由于当前关联规则树 为空，所以第 1 条关联规则即为关联规则树的第 1 个 分支，关联规则第 1 项成为关联规则树根节点的子节 点，其余各项沿着路径分支依次链接． 继续扫描下一 条关联规则，首先判断关联规则树第 1 层节点中是否 存在该条关联规则的第 1 项，如果存在则树中第 1 层 无需新增节点，反之亦然． 依此类推，如果关联规则的 第 2 项已经是关联规则树第 1 层节点的子节点，则关 联规则树第 2 层无需新增节点，否则需要新增节点． 当扫描到某条关联规则的最后一项( 假设为该条规则 第 i 项) 时，在树的相应层( 第 i 层) 新增一个叶节点， 并在叶节点中记录这条关联规则的后件的输出类别、 关联规则后件线性表达式系数和置信度． 如此进行， 形成最终的关联规则树． 表 1 Iris 数据集关联规则项头表 Table 1 Header table of association rules with Iris dataset 序号 变量编码 类别 支持度 重要度 最小值 最大值 宽度 1 4 3 6 0. 02 1. 0 1. 5 0. 170106 2 4 1 4 0. 02 0. 1 0. 3 0. 056955 3 3 3 4 0. 02 3. 0 4. 3 0. 343608 4 2 1 3 0. 02 2. 0 2. 7 0. 186982 5 3 2 2 0. 02 1. 5 1. 9 0. 116697 6 3 1 2 0. 02 1. 0 1. 4 0. 108530 7 4 4 1 0. 02 1. 6 2. 0 0. 127210 8 3 5 1 0. 02 5. 2 5. 9 0. 204978 9 4 5 1 0. 02 2. 1 2. 5 0. 135571 10 2 3 1 0. 02 3. 2 3. 5 0. 112706 11 3 4 1 0. 02 4. 4 5. 1 0. 245571 12 1 3 1 0. 02 4. 8 5 0. 083095 13 2 2 1 0. 02 2. 8 3. 1 0. 104878 14 5 2 8 0 2. 0 2. 0 0 15 5 1 7 0 1. 0 1. 0 0 16 5 3 3 0 3. 0 3. 0 0 关联规则树构建算法: 步骤 1 第 1 次扫描关联规则库，统计规则库中 每个项的支持度，将有关输入输出变量的项分别按支 持度和重要度进行降序排序作为项头表的两部分，并 合并为最终的项头表． 步骤 2 因为关联规则中的每一项与项头表中 的记录一一对应，再次扫描关联规则库时，用项头表 中项的序号表示原始关联规则． 初始创建规则树是 空树，没有节点( 记为 T) ． 假设［p | P］是其中一条关 联规则 rule，p 即 为 rule 的 第 1 项，P 为 rule 的 剩 余 · 888 ·

王玲等：基于定量关联规则树的分类及回归预测算法 889 项，调用insert-tree([plP],T)方法不断向关联规则 径中有多个输出类别，选择置信度最高的叶节点所表 树中增加节点，具体做法是如果当前树非空，则遍历 示的输出类别即为样本预测输出类别.否则跳转到步 树的孩子节点，看是否存在节点Node,使得Node. 骤3. name=p.若存在，则无需新增节点：否则建立一个新 步骤3若在关联规则树中不存在与样本x相匹 的节点Node,令Node.name=p.将节点Node的父节 配的规则，则利用模糊推理的方法实现对新数据输出 点指针指向父节点T,并将相同的节点通过节点链指 的精确预测，如下式： 针链接.如果P非空，则递归地调用insert-tree(P,T) 直到关联规则最后一项.当扫描到某条关联规则的 y= (4) 最后一项（假设为该条规则第项），在树的相应层 (第i层)新增一个叶节点，并在叶节点中记录这条 关联规则的后件的输出类别、关联规则后件线性表 达式系数和置信度.一直重复步骤2直到所有关联 (5) 规则扫描完毕为止 1.4规则匹配与推理 式中，=口4，R表示挖据得到的关联规则个数， 基于上述构建的关联规则树，当有新样本待预测 ”表示样本x对第I条关联规则中第h个项集的高 时，规则匹配过程分为两个阶段：用项头表中项的序号 斯隶属度，M(1≤M≤n)表示第l条关联规则中包含项 来表示原始数据实现新样本离散化：然后从关联规则 集的个数，”表示第1条规则第h个项集的均值，σ” 表示第l条规则第h个项集的标准差.和σ”也 树的根节点开始逐一与离散化以后的新样本匹配，如 分别表示各个维度的聚类中心和聚类方差. 果沿根节点开始的某一条分支路径，没有与新数据相 匹配的节点，则停止查询，否则将一直沿着这条路径匹 2算法性能分析及实例应用 配到叶节点得出输出类别.令Node表示关联规则树 中第i层第j(I≤j≤n:)个节点，Node.Next表示第i层 2.1算法性能分析 的子节点，具体的算法如下所示 为了验证本算法的预测性能以及学习效率，使用 步骤1假设待预测样本为x,首先将样本按照项 UCI基准数据库中的ris、Wine、Seed以及Breast 头表离散化，然后沿着关联规则树的根节点开始，指向 Cancer作为实验数据集进行仿真. 第1层子节点Node,=1,2,…,n,). 这里以is数据集为例，首先获得关联规则项头 步骤2从第i层子节点开始查询每一个子节点 表，如表1所示，然后利用关联规则项头表的序号来表 中是否存在与x相匹配的节点.如果存在，则沿着该 示每个关联规则中对应的各个项，进而构建is数据 节点的分支路径继续查询第i+1层中是否存在与输 集的关联规则树，当有新待预测样本时，可快速获得预 入数据相匹配的子节点，直到到达叶节点，如果分支路 测输出，如图2所示 ○根节点 6) 12 3 ④ 图2Iis数据集关联规则树 Fig.2 Association rule tree of Iris dataset 图3对比了关联规则树匹配以及关联规则逐条匹 关联规则树匹配查询新样本输出类别所需的时间明显 配两种方法预测新样本输出类别的效率，对于is、 少于关联规则逐条匹配的查询方法. Wine、Seed和Breast Cancer数据集，利用关联规则树匹 2.2应用实例 配查询新样本所需的时间分别为0.022、0.043、0.038 由于钢铁行业中中厚板生产过程复杂，影响产品 和0.081s,而采用关联规则逐条匹配查询所需时间分 质量的因素众多，本文提出采用定量关联规则树方法 别为0.030、.0.100、0.061和0.209s.可以看出，利用 从中厚板生产过程数据中提取重要信息，发现它们与

王 玲等: 基于定量关联规则树的分类及回归预测算法 项，调用insert-tree( ［p | P］，T) 方法不断向关联规则 树中增加节点，具体做法是如果当前树非空，则遍历 树的孩 子 节 点，看 是 否 存 在 节 点 Node，使 得 Node． name = p． 若存在，则无需新增节点; 否则建立一个新 的节点 Node，令 Node． name = p． 将节点 Node 的父节 点指针指向父节点 T，并将相同的节点通过节点链指 针链接． 如果 P 非空，则递归地调用 insert-tree( P，T) 直到关联规则最后一项． 当扫描到某条关联规则的 最后一项( 假设为该条规则第 i 项) ，在树的相应层 ( 第 i 层) 新增一个叶节点，并在叶节点中记录这条 关联规则的后件的输出类别、关联规则后件线性表 达式系数和置信度． 一直重复步骤 2 直到所有关联 规则扫描完毕为止． 1. 4 规则匹配与推理 基于上述构建的关联规则树，当有新样本待预测 时，规则匹配过程分为两个阶段: 用项头表中项的序号 来表示原始数据实现新样本离散化; 然后从关联规则 树的根节点开始逐一与离散化以后的新样本匹配，如 果沿根节点开始的某一条分支路径，没有与新数据相 匹配的节点，则停止查询，否则将一直沿着这条路径匹 配到叶节点得出输出类别． 令 Nodeij表示关联规则树 中第 i 层第 j( 1≤j≤ni ) 个节点，Nodeij． Next 表示第 i 层 的子节点，具体的算法如下所示． 步骤 1 假设待预测样本为 x，首先将样本按照项 头表离散化，然后沿着关联规则树的根节点开始，指向 第 1 层子节点 Node1j ( j = 1，2，…，ni ) ． 步骤 2 从第 i 层子节点开始查询每一个子节点 中是否存在与 x 相匹配的节点． 如果存在，则沿着该 节点的分支路径继续查询第 i + 1 层中是否存在与输 入数据相匹配的子节点，直到到达叶节点，如果分支路 径中有多个输出类别，选择置信度最高的叶节点所表 示的输出类别即为样本预测输出类别． 否则跳转到步 骤 3． 步骤 3 若在关联规则树中不存在与样本 x 相匹 配的规则，则利用模糊推理的方法实现对新数据输出 的精确预测，如下式: y = ∑ Ｒ l = 1 τly ( l) ∑ Ｒ l = 1 τl ， ( 4) μ ( l) h = e － ( xh － x － ( l) h ) 2 2( σ( l) h ) 2 ． ( 5) 式中，τl = ∏ M h = 1 μ ( l) h ，Ｒ 表示挖掘得到的关联规则个数， μ ( l) h 表示样本 x 对第 l 条关联规则中第 h 个项集的高 斯隶属度，M( 1≤M≤n) 表示第 l 条关联规则中包含项 集的个数，x( l) h 表示第 l 条规则第 h 个项集的均值，σ( l) h 表示第 l 条规则第 h 个项集的标准差． x( l) h 和 σ( l) h 也 分别表示各个维度的聚类中心和聚类方差． 2 算法性能分析及实例应用 2. 1 算法性能分析 为了验证本算法的预测性能以及学习效率，使用 UCI 基 准 数 据 库［4］ 中的 Iris、Wine、Seed 以 及 Breast Cancer 作为实验数据集进行仿真． 这里以 Iris 数据集为例，首先获得关联规则项头 表，如表 1 所示，然后利用关联规则项头表的序号来表 示每个关联规则中对应的各个项，进而构建 Iris 数据 集的关联规则树，当有新待预测样本时，可快速获得预 测输出，如图 2 所示． 图 2 Iris 数据集关联规则树 Fig． 2 Association rule tree of Iris dataset 图 3 对比了关联规则树匹配以及关联规则逐条匹 配两种方法预测新样本输出类别的效率，对于 Iris、 Wine、Seed 和 Breast Cancer 数据集，利用关联规则树匹 配查询新样本所需的时间分别为 0. 022、0. 043、0. 038 和 0. 081 s，而采用关联规则逐条匹配查询所需时间分 别为 0. 030、0. 100、0. 061 和 0. 209 s． 可以看出，利用 关联规则树匹配查询新样本输出类别所需的时间明显 少于关联规则逐条匹配的查询方法． 2. 2 应用实例 由于钢铁行业中中厚板生产过程复杂，影响产品 质量的因素众多，本文提出采用定量关联规则树方法 从中厚板生产过程数据中提取重要信息，发现它们与 · 988 ·

·890 工程科学学报，第38卷，第6期 0.25 0.5833 ☑关联规则树匹配查询 ☒关联规则逐条匹配查询 Then0.4687≤s≤0.5777， 0.20 31=-0.3265-4.4205×(Cr）-3.3825× 1w(H)+3.4450×w(Mo)+0.2379×w(Si)- 0.15 0.6286×0(S) 0.10 Rule2:f0.0945<Te≤0.1435，and0.4638< TnAe≤0.681l,and 0.05 0.1430<TAa≤0.1576，and0.4409< w(Mn)≤0.6929and Iris Wine Seed BreaslCancer 0.2667<e(0)≤0.3778，and0.0000< 数据集 w(Si)≤0.0580，and 图3关联规则查询效率对比 0.3229<心(S)≤0.4271， Fig.3 Comparison of query efficiency for association rule Then0.5913≤s2≤0.7275， 产品质量的关联关系，最终实现中厚板质量的预测，为 s2=0.0111+16.1103Te-0.0397TA- 生产提供有价值的决策支持. 16.1699Ta=+0.1243×w(Mn)-0.9588× 通过数据预处理，最终确定中厚板的力学性能指 e(0)+0.4298×w(Si)-0.0316×w(S) 标一屈服度作为输出变量，其他15个重要变量作为影 其中，T。为中厚板数据中的钢卷厚度，Tn为终轧 响该质量指标的主要因素，分别为钢卷厚度、终轧温度 温度平均值，T。为平均温度，w(Mn)为元素锰的质 平均值、平均温度、铬、铜、碳、氢、锰、钼、镍、氮、氧、硅、 量分数，w(0)为氧元素的质量分数，心(Si)为硅元素 硫和钛的质量分数，并进一步实现离散化.在此基础 的质量分数，w(S)为硫元素的质量分数，w(Cr)为铬 上，首先利用上文提出的算法提取定量关联规则，并根 元素的质量分数，心(H)为氢元素的质量分数， 据定义6重构定量关联规则.针对关联规则前后件各 心(Mo)为钼元素的质量分数，s,为第I条关联规则的 项表示的各个维度的取值区间，获取前后件高斯隶属 屈服度 度函数.为了实现定量关联规则的精确推理预测，将 Rule2中0.0945<Te≤0.1435”表示输入变量Tc 数据按照输出类别划分训练数据，分别对每个规则后 相关的1项集，0.5913≤s2≤0.7275表示输出变量屈 件采用最小二乘算法估计线性表达式系数.此处仅列 服强度相关的1项集. 出了两条中厚板定量关联规则： 为了实现规则的快速匹配学习，根据上文的关联 Rule,:f0.8135<w(Cr)≤0.8645，and0.3333< 规则树的构建方法，第1遍扫描中厚板关联规则得到 w(H)≤0.6333，and 中厚板关联规则项头表如表2所示.接着用表2中的 0.5000<t(Mo)≤1.0000，and0.1530< 序号表示关联规则的各个项，再次扫描转化后的关联 w(Si)≤0.2296，and0.4479<w(S）≤ 规则，构建关联规则树，树中每个中间节点表示项头表 表2中厚板关联规则树项头表 Table 2 Header table of association rule tree with plates 序号 变量 类别 支持度 重要度 最小值 最大值 宽度 20 256 0.001577118 0 0.058047493 0.058047 2 18 1 240 0.002638180 0 0 0 3 14 3 208 0.000542179 0.165354331 0.283464567 0.015805 4 13 1 172 0.002591298 0 0 0 10 160 0.003019993 0.033898305 0.033898305 0 6 17 1 128 0.000579059 0 0.196078431 0.196078 … … … 子 23 2 280 0.305177112 0.455040872 0.0350094 23 3 183 0.468664850 0.5776566769 0.030269 30 23 5 31 0 0.291553134 0.291553 31 23 1 19 0.591280654 0.727520436 0.023767 32 23 15 0 0.058047493 0.058047

工程科学学报，第 38 卷，第 6 期 图 3 关联规则查询效率对比 Fig． 3 Comparison of query efficiency for association rule 产品质量的关联关系，最终实现中厚板质量的预测，为 生产提供有价值的决策支持． 通过数据预处理，最终确定中厚板的力学性能指 标—屈服度作为输出变量，其他 15 个重要变量作为影 响该质量指标的主要因素，分别为钢卷厚度、终轧温度 平均值、平均温度、铬、铜、碳、氢、锰、钼、镍、氮、氧、硅、 硫和钛的质量分数，并进一步实现离散化． 在此基础 上，首先利用上文提出的算法提取定量关联规则，并根 据定义 6 重构定量关联规则． 针对关联规则前后件各 项表示的各个维度的取值区间，获取前后件高斯隶属 度函数． 为了实现定量关联规则的精确推理预测，将 数据按照输出类别划分训练数据，分别对每个规则后 件采用最小二乘算法估计线性表达式系数． 此处仅列 出了两条中厚板定量关联规则: Ｒule1 : If 0. 8135 ＜ w( Cr) ≤0. 8645，and 0. 3333 ＜ w( H) ≤0. 6333，and 0. 5000 ＜ w( Mo) ≤1. 0000，and 0. 1530 ＜ w( Si) ≤0. 2296，and 0. 4479 ＜ w( S) ≤ 0. 5833 Then 0. 4687≤sy1≤0. 5777， sy1 = － 0. 3265 － 4. 4205 × w( Cr) － 3. 3825 × w( H) + 3. 4450 × w( Mo) + 0. 2379 × w( Si) － 0. 6286 × w( S) Ｒule2 : If 0. 0945 ＜ TC ≤ 0. 1435，and 0. 4638 ＜ TFt_Aver≤0. 6811，and 0. 1430 ＜ TAver ≤0. 1576，and 0. 4409 ＜ w( Mn) ≤0. 6929 and 0. 2667 ＜ w( O) ≤0. 3778，and 0. 0000 ＜ w( Si) ≤0. 0580，and 0. 3229 ＜ w( S) ≤0. 4271， Then 0. 5913≤sy2≤0. 7275， sy2 = 0. 0111 + 16. 1103TC － 0. 0397TFt_Aver － 16. 1699TAver + 0. 1243 × w ( Mn) － 0. 9588 × w( O) + 0. 4298 × w( Si) － 0. 0316 × w( S) 其中，TC 为中厚板数据中的钢卷厚度，TFt_Aver为终轧 温度平均值，TAver为平均温度，w( Mn) 为元素锰的质 量分数，w( O) 为氧元素的质量分数，w( Si) 为硅元素 的质量分数，w( S) 为硫元素的质量分数，w( Cr) 为铬 元素 的 质 量 分 数，w ( H) 为氢元素的质量分数， w( Mo) 为钼元素的质量分数，syl为第 l 条关联规则的 屈服度． Ｒule2 中“0. 0945 ＜ TC≤0. 1435”表示输入变量 TC 相关的 1-项集，0. 5913≤sy2≤0. 7275 表示输出变量屈 服强度相关的 1-项集． 为了实现规则的快速匹配学习，根据上文的关联 规则树的构建方法，第 1 遍扫描中厚板关联规则得到 中厚板关联规则项头表如表 2 所示． 接着用表 2 中的 序号表示关联规则的各个项，再次扫描转化后的关联 规则，构建关联规则树，树中每个中间节点表示项头表 表 2 中厚板关联规则树项头表 Table 2 Header table of association rule tree with plates 序号 变量 类别 支持度 重要度 最小值 最大值 宽度 1 20 1 256 0. 001577118 0 0. 058047493 0. 058047 2 18 1 240 0. 002638180 0 0 0 3 14 3 208 0. 000542179 0. 165354331 0. 283464567 0. 015805 4 13 1 172 0. 002591298 0 0 0 5 10 3 160 0. 003019993 0. 033898305 0. 033898305 0 6 17 1 128 0. 000579059 0 0. 196078431 0. 196078 … … … … … … … … 28 23 2 280 — 0. 305177112 0. 455040872 0. 0350094 29 23 3 183 — 0. 468664850 0. 5776566769 0. 030269 30 23 5 31 — 0 0. 291553134 0. 291553 31 23 1 19 — 0. 591280654 0. 727520436 0. 023767 32 23 4 15 — 0 0. 058047493 0. 058047 · 098 ·