·762· 北京科技大学学报 2005年第6期 D,D,,D占XUX的比例与原来相同，分别为 性公式得：属性a的重要性/属性b的重要性=53. P,P,…,Pn.因此由Shannon熵的定义可以得出： 原始划分断点为：P-[0.8,1],P=[1,13],P= IXUX)FX=K),进而可得EXUX)=EX)- [1.3,1.4],P=[1.4,1.6],P=[1.6,41,P=[0.5,1],P=[1,2], E(X). P-[2,3],根据断点重要性公式计算P-[1.3,1.4]为 最重要断点.UNDD){x,x4wx6x,x},{x,x,x},a 2离散算法描述 和b为核属性.d0时，b的离散点为[0.5,2]，[2,3]： 本算法应用自定义的属性重要性公式及以 d1时，b的离散点为[1,2]，[2,3].d0时，a的离散点 上述定理为依托，具体描述如下. 为[1,1.3]，[1.3,1.4小：1时，a的离散点为0.8,1.3]， Stepl应用自定义公式对数据属性的重要性 [1.3,1.4],[1.4,1.61,[1.6,6).通过整体划分得b的断 进行计算，去掉冗余属性：计算原信息表相对信 点泛化区间为1,2，a的断点泛化区间为[1,1.4】. 息熵E. 再进行算法中Step5到Step8的操作，得b的断点 Step2根据原有的信息表S°构造新的信息表 集为{[1,2]}，a的断点集为[1,1.3]，[1.4,1.6]}，最终 S,构造差别矩阵. 结果如表2. Step3根据超立方体的概念，对每个属性进 表1原始信息表 行泛化： Table 1 Initial table ①按决策属性对信息表中的实例进行归类 U a b d ②对同一个类别的实例进行泛化. X 0.8 2.0 1 Step4根据Step3求取整体离散化断点集. 古 1.0 0.5 0 初始化始断点集W=O: X 1.3 3.0 0 FOR(i=l;is:计+)取属性a,的各类泛化区间 X 1.4 1.0 X 1.4 2.0 0 进行两两比较，例如任意选两个泛化区间[，]， X 1.3 1.0 1 [,胡进行比较，j,k为决策类标示号； 出 1.6 3.0 If<<<,则新取断点集={l,}: X 4.0 3.0 If≤d,则新取断点集严={化，}：Others,, 表2最终表 新取断点集={，}：W=U: Table 2 Final table 输出W. U b d Step5根据断点集计算信息表相对信息熵E, X 0 如果E≥E,则执行Step6:否则执行Step8. X 0 0 0 Step6在差别矩阵中去掉w中所包含的断点 X 1 1 0 所在的列及该列为1的行，构造新的差别矩阵， X 0 根据公式“候选断点的重要性程度=属性重要性 X 0 名 ×候选断点区分对象的个数”在差别矩阵中取断 X 2 点重要性最差的两个断点进行聚类：如两个离散 名 2 区间为[，，[，]，若两个实例子集满足定理5， 则聚为一类：若两个实例子集聚为一类后不包含 为了验证该算法，本文对is数据库进行试 异类实例，则聚为一类，新形成的断点集为 验，经过本算法处理后得到的划分区间为： W-{min(化，月，max(,)}. petal--length[1.0,3.0),[3.0,5.2),[5.2,6.9], petal--width[0.1,l.8),[1.8,2.5], Step7根据W=WUW对信息表进行离散化并 sepal-length[4.3,5.9),[5.9,7.1),[7.1,7.9], 计算相对信息熵E.如果E≥E,则执行Step6:否则 sepa-width[2.0,3.4),[3.4,4.4]. 执行Step8 Step8根据断点集W对信息表的属性值进行 从离散化后的划分区间看，基本反映了数据 的真实情况 相应的整数映射. 3数值示例及实验 4结论 原始信息表如表1，按照自定义的属性重要 本算法由于自定义了新的属性重要性公式，北 京 科 技 大 学 学 报 200 5 年 第 6 期 D Z , D 3 , … , 氏 占戈 u 不 的 比 例 与 原 来相 同 , 分 别 为 几 ,户 , … , P 二 . 因此 由 S h a n n o n 嫡 的定义 可 以得 出 : 了忱 口 戈)习忱 )斌戈) , 进 而 可 得 百忱 U 不)绍忱卜 万怀 ) . 性 公 式 得 : 属性 a 的重 要 性 /属性 b的 重要 性 = 5/ 3 . 原 始 划 分 断 点 为 :月二 【.0 8 , 1」 , 代= 【l , 1 . 3] , 只= [ 1 . 3 , 1 . 4 ] , 代二 【1 . 4 , 1 . 6〕 , 只= 〔1 . 6 , 4 ] , 君= 〔0 . 5 , l ] ,代二【l , 2 ] , 只= 2[ ,3〕 , 根 据 断 点重要 性 公 式计 算月= 〔1 . 3 , 1 . 4] 为 最 重 要 断点 . 酬NI D (D ) 一 {x( 1再.x0 丙.x , } , { 、 .xs 声 5 } , a 和 b 为核属 性 . =d 0 时 , b 的离 散 点为 .0[ 5, 2] , 2[ ,3 1 ; 击 l时 , b 的离散 点 为 [ l , 2 ] , [ 2 , 3 ] . 少0 时 , a 的 离散 点 为 [ l , 1 . 3 ] , [ 1 . 3 , 1 . 4 ] ; =d l 时 , a 的离 散 点为 【0 . 8 , 1 . 3 ] , 11 . 3 , 1 . 4 ] , [ 1 . 4 , 1 . 6 1 , [ 1 . 6 , 6 ] . 通 过 整体 划 分得 b 的 断 点 泛化 区间 为 【1 , 2] , a 的断 点泛 化 区 间为 〔l , 1 . 叼 . 再 进行 算 法 中 S et PS 到 st eP S 的操 作 , 得 b 的断 点 集 为 {〔l , 2〕} , a 的断 点集 为 {〔l , 1 . 3〕 , ! 1 . 4 , 1 . 6 }} , 最终 结 果如 表 2 . 表 1 原 始信 息表 1油b l e 1 I n i6 a l t妞b l e U a b d Cx ù 功 0011 .2知3005.301. :8 34 4 n ` 1 1 ,l 龙不 `UO , . 不瓜 4 2 离散算法描 述 本 算 法 应 用 自定义 的属 性 重 要 性 公式 及 以 上述 定理 为 依托 , 具体 描述 如 下 . S et IP 应用 自定 义公式 对数 据属性 的重 要性 进 行 计算 , 去 掉冗 余属 性 ; 计算 原信 息表 相对 信 息 嫡 OE . S et p Z 根据 原有 的信 息表 夕 构造 新 的信 息表 夕 , 构造 差别 矩 阵【31 . s et 3P 根 据超 立 方体 的概 念 , 对 每 个属 性 进 行 泛化 : ① 按 决策 属性 对信 息表 中 的实例进 行 归类 . ② 对 同一 个类 别 的 实例进 行 泛化 . st eP 4 根 据 S etP 3 求 取整 体 离散 化 断点 集 . 初 始 化始 断 点集 聆必 ; FO R 〔=1 1; 迷:n j什) 取 属 性 ia 的各 类泛 化 区 间 进 行两 两 比较 , 例如 任 意选 两个 泛 化 区间 〔l(, iu] , [!l, 诸 ]进 行 比较 , j, k为 决策 类 标示 号 ; if l污 l夕< u{< 诸 , 则新 取 断 点集 甲= {!I, 留 } ; if l(<昨!l<诸 , 则新 取 断 点集 甲= {l{, 诸} ; Oht er s, 新取 断 点集 平= {uf, l}t ; 肚牙日 尸 ; 输 出班 Set SP 根据 断 点集计 算信 息表 相对 信息嫡瓦 如 果 E之 E “ , 则 执行 st e p 6 ; 否则 执 行 tS eP S . S etP 6 在 差别 矩 阵 中去掉 w 中所包 含 的 断点 所 在 的列及 该 列为 1 的行 , 构造 新 的差 别矩 阵 . 根 据公 式 “ 候选 断 点 的重要 性程 度 = 属 性重 要性 ` 候 选 断点 区分对 象 的个数 ” 在 差别 矩 阵 中取 断 点重 要性最 差 的两个 断 点进行 聚类 : 如 两 个离散 区 间为【lt, 坷」 , 【lf, 讨〕 , 若两 个 实例 子集 满足 定 理 5 , 则 聚为 一类 ; 若 两个 实例 子集 聚为 一类后 不包 含 异 类 实 例 , 则 聚 为 一 类 . 新 形 成 的 断 点 集 为 尸二 {m in (几lf) , m ax ( u 人动 } . st eP 7 根 据 聆砰口 甲对 信 息表 进 行 离散化 并 计 算相 对信 息嫡 E . 如果 E 全 0E , 则执 行 S et 6P : 否则 执 行 st eP .S S et PS 根据 断点集 砰对 信息表 的属 性 值进 行 相 应 的整 数 映射 . 3 数值 示例 及 实 验 原始信 息表如 表 1 `习 , 按照 自定义 的属 性重 要 表 2 最终 表 1知b l e Z F加自I 妞 b k 龙瓜 为 了验 证该 算法 , 本文 对 Iir s 数 据库 进行 试 验 , 经 过本 算 法 处理 后得 到 的划 分 区 间为 : P e at l 一 l e n hgt 11 . 0 , 3 . 0 ) , 13 . 0 , 5 . 2 ) , [ 5 . 2 , 6 . 9〕 , P e at l 一 w i dht [ 0 . 1 , 1 . 8) , [ 1 . 8 , 2 . 5 ] , s e P a l 一 l e n ght 【4 . 3 , 5 . 9 ) , 「5 . 9 , 7 . 1) ,【7 . 1 , 7 . 9 ] , s e P a l 一 w i d ht 【2 . 0 , 3 . 4 ) , 【3 . 4 , 4 . 4」 . 从 离散化 后 的划 分 区 间看 , 基本 反 映 了数据 的真 实情 况 . 4 结论 本算 法 由于 自定 义 了新 的属性 重 要性 公式