·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 ·