正在加载图片...
.964 北京科技大学学报 第30卷 较高的时间代价10， 基于图1，可以很容易地计算每一个属性和目 本文扩展互信息标准（它属于过滤方法）到多关 标属性间的互信息量大小，那么多关系情况下，不 系情况下，以提高多关系朴素贝叶斯分类方法的分 同关系中的属性是否应平等对待呢？文献[9]中实 类性能.基于元组号传播方法和面向元组的统计计 验证明了多关系情况下，每个关系同目标关系间的 数方法，本文给出了基于扩展互信息标准进行属性 相关程度是不相同的，基于上述考虑，为每张表指 选择的方法和步骤，并建立了一种基于扩展互信息 定一个权值心，它表示此表与目标表间的相关程 的多关系朴素贝叶斯分类器(MI一MRNBC)·标准 度，一般由领域专家指定，心取值范围为[0,1]，其 数据集上的实验显示，基于扩展互信息标准进行属 中目标表的值w为1.因此基于互信息的多关系属 性选择，可以在不增加算法时间复杂度的前提下，找 性选择步骤如下， 到与分类属性最相关的属性，并在仅有极少属性参 (1)根据一定知识（如语义关系图）进行元组 与分类时，得到较高的分类准确率 号传播 (2)依据传播后的表计算每个属性x和目标属 1基于互信息的多关系朴素贝叶斯分类器 性c间的互信息值： (MI一MRNBC) Ie.x)p(p(e)p( 卫(C,x) (1) 1.1互信息标准的一阶扩展 i.j 分类是主要的数据挖掘任务之一，为获得最小 其中，p(ci,xj)为c和xj的联合概率，p(c:)为c: 的分类错误率，通常需要得到与目标c类最大统计 的概率，p(x)为x的概率. 依赖的属性集合，实现最大依赖的最流行的方法是 (③)根据加权互信息值wI(c,x)的大小对所 最大相关特征选择：选择与目标类c最大相关的属 有属性由大到小排序，然后选取前m(用户指定)个 性，相关性则通常根据自相关和互信息来衡量，互信 属性参与分类 息则是衡量变量依赖广泛使用的测度 1.2 MII-MRNBC算法 单关系（表）情况下，表内属性与目标属性间的 MI一ARNBC根据传播的类标签的数目和类别 相关性大小可以直接由相应的互信息量大小表示； 进行计数（面向元组的统计计数方法，不考虑元组号 而多关系情况下，属性分布在不同的关系中，要计算 重复问题)，并用Laplace估计方法避免零概率出 与目标属性间的互信息量需要首先进行关系连接， 现，多关系分类公式见文献[9] 为降低关系间连接时的时空代价，本文采用元组号 输入：数据集，语义关系图R,交叉验证次数， 传播方法进行虚拟的连接.图1是多关系情况下， 参与分类的属性个数m, 进行元组号传播后的例子. 步骤： (1)根据用户要求选择数据集中合适元组，并 贷款表 进行类别属性取值替换等预处理操作，将目标表元 贷款号账目号 数额 借贷期 已还款金额 类别 组随机分为n组（作n次交叉验证）， 1 14 1200 100 (②)根据R进行元组号传播，此时也要将元组 2 14 3000 300 + 分组标志传播，以判断非目标关系中元组是训练数 3 18 9000 品 500 据还是测试数据. 50 2000 36 200 (3)从n组中选一组数据作为测试数据，其余 50 15000 24 1000 n一1组作为训练数据，并分别进行连续属性离 散化， 账目表 (4)对传播后的训练数据进行统计计数，计算 账目号 颜率 日期 贷款号 类别 4 所需互信息值和类条件概率值 每月 95-02-11 1.2 2十，0- (5)根据加权互信息值为属性排序. 18 每周 9605—22 3 0+,1- (6)用多关系朴素贝叶斯分类公式对测试数据 50 每月 97-0-24 4.5 1+,1- 进行分类（仅取加权互信息值最大的m个属性参与 60 每周 9808-26 0十，0- 分类) 图1传播后的样例数据库 输出：分类准确率(accuracy)· Fig.1 A sample database of tuple ID propagation 其中(3)一(6)执行n次，最后取n次交叉验证较高的时间代价［10］． 本文扩展互信息标准（它属于过滤方法）到多关 系情况下以提高多关系朴素贝叶斯分类方法的分 类性能．基于元组号传播方法和面向元组的统计计 数方法本文给出了基于扩展互信息标准进行属性 选择的方法和步骤并建立了一种基于扩展互信息 的多关系朴素贝叶斯分类器（MI—MRNBC）．标准 数据集上的实验显示基于扩展互信息标准进行属 性选择可以在不增加算法时间复杂度的前提下找 到与分类属性最相关的属性并在仅有极少属性参 与分类时得到较高的分类准确率． 1 基于互信息的多关系朴素贝叶斯分类器 （MI－MRNBC） 1∙1 互信息标准的一阶扩展 分类是主要的数据挖掘任务之一为获得最小 的分类错误率通常需要得到与目标 c 类最大统计 依赖的属性集合．实现最大依赖的最流行的方法是 最大相关特征选择：选择与目标类 c 最大相关的属 性相关性则通常根据自相关和互信息来衡量互信 息则是衡量变量依赖广泛使用的测度． 单关系（表）情况下表内属性与目标属性间的 相关性大小可以直接由相应的互信息量大小表示； 而多关系情况下属性分布在不同的关系中要计算 与目标属性间的互信息量需要首先进行关系连接． 为降低关系间连接时的时空代价本文采用元组号 传播方法进行虚拟的连接．图1是多关系情况下 进行元组号传播后的例子． 贷款表 贷款号 账目号 数额 借贷期 已还款金额 类别 1 14 1200 12 100 ＋ 2 14 3000 12 300 ＋ 3 18 9000 24 500 — 4 50 2000 36 200 — 5 50 15000 24 1000 ＋ 账目表 账目号 频率 日期 贷款号 类别 14 每月 95—02—11 12 2＋0— 18 每周 96—05—22 3 0＋1— 50 每月 97—01—24 45 1＋1— 60 每周 98—08—26 — 0＋0— 图1 传播后的样例数据库 Fig．1 A sample database of tuple ID propagation 基于图1可以很容易地计算每一个属性和目 标属性间的互信息量大小．那么多关系情况下不 同关系中的属性是否应平等对待呢？文献［9］中实 验证明了多关系情况下每个关系同目标关系间的 相关程度是不相同的．基于上述考虑为每张表指 定一个权值 w它表示此表与目标表间的相关程 度一般由领域专家指定w 取值范围为［01］其 中目标表的值 w 为1．因此基于互信息的多关系属 性选择步骤如下． （1） 根据一定知识（如语义关系图［5］ ）进行元组 号传播． （2） 依据传播后的表计算每个属性 x 和目标属 性 c 间的互信息值： I（ cx）＝ ∑ij p（ cixj）lg p（ cixj） p（ ci） p（ xj） （1） 其中p（ cixj）为 ci 和 xj 的联合概率p （ ci）为 ci 的概率p（ xj）为 xj 的概率． （3） 根据加权互信息值 wI（ cx ）的大小对所 有属性由大到小排序然后选取前 m（用户指定）个 属性参与分类． 1∙2 MI－MRNBC 算法 MI—MRNBC 根据传播的类标签的数目和类别 进行计数（面向元组的统计计数方法不考虑元组号 重复问题）并用 Laplace 估计方法避免零概率出 现多关系分类公式见文献［9］． 输入：数据集语义关系图 R交叉验证次数 n 参与分类的属性个数 m． 步骤： （1） 根据用户要求选择数据集中合适元组并 进行类别属性取值替换等预处理操作将目标表元 组随机分为 n 组（作 n 次交叉验证）． （2） 根据 R 进行元组号传播此时也要将元组 分组标志传播以判断非目标关系中元组是训练数 据还是测试数据． （3） 从 n 组中选一组数据作为测试数据其余 n—1组作为训练数据并分别进行连续属性离 散化． （4） 对传播后的训练数据进行统计计数计算 所需互信息值和类条件概率值． （5） 根据加权互信息值为属性排序． （6） 用多关系朴素贝叶斯分类公式对测试数据 进行分类（仅取加权互信息值最大的 m 个属性参与 分类）． 输出：分类准确率（accuracy）． 其中（3）～（6）执行 n 次最后取 n 次交叉验证 ·964· 北 京 科 技 大 学 学 报 第30卷