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