王玲等：基于定量关联规则树的分类及回归预测算法 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 ·