正在加载图片...
.904 北京科技大学学报 2006年第9期 定理3设HB三C,Hc∈C且cB,U'= 决策类进行步骤5的操作. U一P0Sg(D)为粗糙边界，则有： 步骤5在同一决策类中，设条件属性B'三 IPOSUIe(D)= B≤A,对Hx:∈MOS进行如下操作： IPOSUI(D)I-IPOS (D)I. ()若∈B,且rB(F)=rB\B(F),则由 证明对Hc∈C且cB有两种情况 推论知4(x:)可以取任一断点值. (1)若c为冗余属性，则： (2)否则，进行如下操作： IPOSEUI(D)I=IPOS (D)I=0, ①对Hx:∈MOS,在属性集B\{B'}中计算 IPOSHU(D)I=IPOS (D)I-IPOS (D)I=0. NS(xi): (2)若c为重要属性，则： ②若NS(x)=y,则令a4(xi)=a(y): U'=U-POSB(D), ③若NS(x)=y1,y2,…,ym},则令y=yi 即 (y:的等价类的势最大)，且a(xi)=a(y) U=U'十POSB(D)· (3)直至全部x:∈MOS操作完毕， 步骤6在决策表中取第二个分类，进行步 所以有 骤5的操作.直至所有决策类进行操作完毕，最 POSEUIci(D)=POS D)UPOSHUICI(D), 后得到新的信息表S只U,A,V,)· IPOSUI(D)=IPOSAUI(D)1++IPOS(D)1. 步骤7根据超立方体的概念，对每个属性 定理4在一个差别向量中，如果它的频率 进行泛化： 向量中的某一项元素取值为1，则该元素所对应 (1)按照决策属性对信息表中的实例进行归 的属性为原信息表的核属性 类 证明依据题意，令频率向量中的任意一个 (2)对同一个类别的实例进行泛化· f(a)=1.因为F=(f(a1),f(a2),…,f(an), 步骤8根据步骤7求取整体离散化断点 f(a)=DC=1,所以DC|=1.也就是差别向 集 量中的差别属性集只有一个属性，而在整个属性 初始化始断点集W=①： 集合中也只有这个属性能够区分这两个对象，因 F0R(=l;≤n:i++) 此这个属性就是原信息表的核属性 取属性：的各类泛化区间进行两两比较，如任 意选两个泛化区间[，]，[，]进行比较(j, 2不完备信息表预处理算法的描述 k为决策类标示号)： 设原始信息系统为s=(U°，A°，V,9, f<<<,则新取断点集W={,}; 计算信息表相对信息嫡E”. f<<<,则新取断点集W=马，}： 步骤1根据原始信息表建立差别向量组， others新取断点集W/i=,};W=WUWi} 进行差别向量加法运算， 输出W. 步骤2在U\MOS中计算各属性值的重 步骤9根据信息表中断点集，计算此时信 要性，并按照属性的重要性从左到右降序排列形 息表相对信息熵E,如果E>E”,则执行步骤 成序偶(a1,a2,…,an),MOS排在信息表的最后， 10;否则执行步骤12. 建立新的信息表S'只U',A',V',f)· 步骤10在差别向量组中对不同类别对象 步骤3设U\MOS中每个属性a:的断点 进行如下操作： 集P,断点为P(j=1,2,,n一1)，与之相邻的 假设不同类别对象的两个离散区间为[， 两个值x,x+1,并且xp<+1,对于每一个 ],[,],则： 属性a:进行如下操作： (1)若两个实例子集满足包含关系，则聚为 (1)令a=x,x=xj+1·若信息表无冲突， 一类. 则p=p\{P;否则，x=a,x+1=x+1 (2)若两个实例子集聚为一类后不包含异类 (2)直至全部属性操作完毕， 实例，则聚为一类 步骤4在信息表中按照决策属性对全部对 新形成的断点集为Wi=imin(,), 象分类，按各分类的势由大到小排序，并取第一个 max(u,u);定理3 设∀B⊆ C∀c∈ C 且 c∈／BU′＝ U－POS U B （ D）为粗糙边界则有： ｜POS U′ B∪｛c｝（ D）｜＝ ｜POS U B∪｛c｝（ D）｜－｜POS U B （ D）｜． 证明 对∀c∈C 且 c∈／B 有两种情况． （1） 若 c 为冗余属性则： ｜POS U′ B∪｛c｝（ D）｜＝｜POS U′ B （ D）｜＝0 ｜POS U B∪｛c｝（D）｜＝｜POS U B （D）｜－｜POS U B （D）｜＝0． （2） 若 c 为重要属性则： U′＝ U－POS B（ D） 即 U＝ U′＋POS B（ D）． 所以有 POS U B∪｛c｝（ D）＝POS U B （ D）∪POS U′ B∪｛c｝（ D） ｜POS U B∪｛c｝（D）｜＝｜POS U′ B∪｛c｝（D）｜＋｜POS U B （D）｜． 定理4 在一个差别向量中如果它的频率 向量中的某一项元素取值为1则该元素所对应 的属性为原信息表的核属性． 证明 依据题意令频率向量中的任意一个 f （ ai）＝1．因为 F＝（ f （ a1）f （ a2）…f （ an）） f （ ai）＝ 1 ｜DC｜ ＝1所以｜DC｜＝1．也就是差别向 量中的差别属性集只有一个属性而在整个属性 集合中也只有这个属性能够区分这两个对象因 此这个属性就是原信息表的核属性． 2 不完备信息表预处理算法的描述 设原始信息系统为 S 0＝〈U 0A 0V 0f 0〉 计算信息表相对信息熵 E 0． 步骤1 根据原始信息表建立差别向量组 进行差别向量加法运算． 步骤2 在 U ＼MOS 中计算各属性值的重 要性并按照属性的重要性从左到右降序排列形 成序偶（ a1a2…an）MOS 排在信息表的最后 建立新的信息表 S′＝〈U′A′V′f′〉． 步骤3 设 U＼MOS 中每个属性 ai 的断点 集 P i断点为 P i j（ j＝12…n－1）与之相邻的 两个值 x i jx i j＋1并且 x i j＜P i j＜ x i j＋1对于每一个 属性 ai 进行如下操作： （1） 令 α＝ x i jx i j＝ x i j＋1．若信息表无冲突 则 P i＝P i＼｛P i j｝；否则x i j＝αx i j＋1＝ x i j＋1． （2） 直至全部属性操作完毕． 步骤4 在信息表中按照决策属性对全部对 象分类按各分类的势由大到小排序并取第一个 决策类进行步骤5的操作． 步骤5 在同一决策类中设条件属性 B′⊆ B≤ A对∀ xi∈MOS 进行如下操作： （1） 若 ak∈ B′且 rB （ F）＝ rB＼B′（ F）则由 推论知 ak（ xi）可以取任一断点值． （2） 否则进行如下操作： ① 对∀ xi∈MOS在属性集 B＼｛B′｝中计算 NS（ xi）； ② 若 NS（ xi）＝y则令 ak（ xi）＝ ak（ y）； ③ 若 NS（ xi）＝｛y1y2…ym｝则令 y＝yi （ yi 的等价类的势最大）且 ak（ xi）＝ ak（ y）． （3） 直至全部 xi∈MOS 操作完毕． 步骤6 在决策表中取第二个分类进行步 骤5的操作．直至所有决策类进行操作完毕最 后得到新的信息表 S＝〈UAV f〉． 步骤7 根据超立方体的概念对每个属性 进行泛化： （1） 按照决策属性对信息表中的实例进行归 类． （2） 对同一个类别的实例进行泛化． 步骤8 根据步骤7求取整体离散化断点 集． 初始化始断点集 W＝／○； FOR （ i＝1；i≤ n：i＋＋） ｛取属性 ai 的各类泛化区间进行两两比较如任 意选两个泛化区间［ l j iu j i ］［ l k iu k i ］进行比较（ j k 为决策类标示号）； If l i i＜ l k i＜ u j i＜ u k i则新取断点集 W i＝｛l k iu j i｝； If l j i＜ u j i＜ l k i ＜ u k i则新取断点集 W i＝｛l j iu k i｝； others 新取断点集 W i＝｛u k il j i｝；W＝ W∪ W i｝ 输出 W． 步骤9 根据信息表中断点集计算此时信 息表相对信息熵 E．如果 E＞ E 0则执行步骤 10；否则执行步骤12． 步骤10 在差别向量组中对不同类别对象 进行如下操作： 假设不同类别对象的两个离散区间为 ［ l j i u j i］［ l k iu k i ］则： （1） 若两个实例子集满足包含关系则聚为 一类． （2） 若两个实例子集聚为一类后不包含异类 实例则聚为一类． 新形 成 的 断 点 集 为 W i ＝｛min （ l j il k i ） max（ u j iu k i ）｝； ·904· 北 京 科 技 大 学 学 报 2006年第9期