基于超立方体与信息熵的离散化方法

D0I:10.13374/i.issn1001-053x.2005.06.029 第27卷第6期 北京科技大学学报 Vol.27 No.6 2005年12月 Journal of University of Science and Technology Beijing Dec.2005 基于超立方体与信息熵的离散化方法 鄂旭12高学东)谭文东”王莹) 1)辽宁工学院计算机系，锦州1210012)北京科技大学管理学院，北京100083 摘要针对粗糙集中连续属性需要离散化问题进行了研究.根据数据对象的可分辨性原理 构造超立方体，在数据空间上对信息表中的连续属性进行整体离散化处理.根据条件属性与 决策属性的一致性关系，依照条件属性在粗糙集边界域中的分类能力来确定条件属性的重 要性，在此基础上选取重要划分点对信息表中的连续属性进行局部离散化，同时以信息熵作 为迭代约束条件.数值示例和实验表明这种整体与局部相结合的离散化方法是有效可行的. 关键词粗糙集；离散化；超立方体；信息熵 分类号TP18 在许多领域中连续属性离散化问题都是一 的x,为对象：A是对象的属性集合，分为两个不相 项重要的数据预处理内容.领域不同，离散化方 交的子集，即条件属性集C和决策属性集D, 法也不同.在粗糙集中要对信息表中的数据进行 A=CUD;P是属性值的集合，V=U(V),a∈A,V,是 处理分析，就必须先对其连续属性进行离散 属性a的值域：f是一个函数，即UxA一V是一个映 化，其本质就是利用选取的断点来对条件属性构 射函数，它为每个对象的每个属性赋予一个属性 成的空间进行划分，把N维空间划分成有限个 值，即Ha∈A,x,∈U,fxa)∈V. 区域，使得每个区域中的对象都具有相同的决 定义2在信息系统S中，如果设U={x,,, 策值， xnx}为相容性例子全集，属性C-={a,a,,an}中 针对粗糙集理论中的离散问题，基本的数据 只包含连续型属性，每个例子x,所对应的属性值 离散化方法有等距离划分、等频率划分，Naive向量为{a,(x),a(x,,a(x)》,一组例子集合 Scaler法、Semi Naive Scaler法、布尔逻辑和粗糙集X-{x,,}sU在同一个属性a,eC上的连续属性 理论相结合的方法等，这些方法基本上属于单 值集合为{a(x),a(),…,a(x},则X={x,…,x}U 属性离散化方法，存在着计算复杂、离散化质量 在属性a,上属性值的泛化区间为[min(a(x),a(x), 不高的缺点.本文以粗糙集理论为基础，提出一 …,a(x》,max(a(x),ax,…,axl,那么集合X所 种在整体上按照信息表整个属性进行离散化，在 构成的超立方体可以用其每个属性轴上的泛化 局部按照单个属性进行离散化，同时兼顾信息表 区间来表示： 原有分类能力的混合型连续属性离散化方法，并 [[min(a(x),a(x2),a(x)),max(a(x),a(x),a))] 通过实例验证此方法是有效可行的. [min(a.(xi).a.(x2).a.(x)),max(a.(x),a.(x2).a.(x)] 1相关定义及定理 一组例子能否形成一个超立方体，关键在于 它们所形成的超立方体是否含有异类例子或者 粗糙集的有关定义参见文献[3]，这里只介绍 是否与其他超立方体相交. 几个与本文算法相关的重要定义. 定义3在信息系统S中，P是U上的一个等 定义1信息系统S定义为S-(U,A,”,),其中， 价关系簇，如2=P且2+☑，则信息熵№(Q的所 U是一个非空有限对象集合，U={x,,,x,式中 有等价关系的交)记作ND(Q),它是一个等价 收稿日期：2004-09-16修回日期：200503-14 关系. 基金项目：国家自然科学基金资助项目No.70271068):辽宁省 教育厅重点科技基金0No.202163345) 定义4在信息系统S中，设X∈U是一个拥 作者简介：鄂旭(1971一)，男，副教授，博士研究生 有X个样本的集合，则ND(D)={Y,Y,,Y}

第 2 7 卷 第 6期 2 0 0 5年 1 2 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n vi e r s iyt o f S e i e n e e a n d Te e h n o l o yg B e ij ni g V b L2 7 N o . 6 D e e . 2 0 5 基于超立方体与信息嫡的离散化方法 鄂 旭 ` ,2) 高学东” 谭文 东 ” 王 莹 ” l )辽 宁工 学院计算 机 系 , 锦 州 12 10 0 1 2 ) 北 京科 技大学 管理学 院 , 北京 10 0 0 8 3 摘 要 针对 粗糙 集 中连 续属 性需要 离散 化 问题 进行 了研 究 . 根 据数 据对象 的可 分辨 性 原理 构 造超 立方体 , 在数 据空 间上对 信息 表 中的连续 属性进 行整 体 离散化 处理 . 根据 条件属 性 与 决策 属性 的 一致性 关系 , 依照 条件 属性在 粗糙 集边 界域 中 的分类 能力来 确定 条件 属性 的重 要性 , 在此 基础 上选取 重要 划分 点对信 息表 中的连 续属 性进行 局部 离散 化 , 同 时 以信息 嫡作 为迭 代约束 条件 . 数值 示例和 实验 表 明这 种整 体 与局部相 结合 的离 散化 方法 是有 效可行 的 . 关键 词 粗 糙集 ; 离 散化 ; 超立 方体 ; 信息墒 分 类号 T P 18 在 许 多领 域 中连 续 属 性 离 散化 问题 都 是 一 项 重要 的数 据 预处 理 内容 . 领 域 不 同 , 离 散化 方 法也 不 同 . 在粗 糙 集 中要对 信息表 中的数据 进行 处理 分析 ` .l2] , 就必 须 先对 其连 续 属 性进 行 离散 化 , 其 本质 就是 利用 选取 的 断点来对 条 件属性 构 成 的空 间进 行 划 分 , 把 N 维 空 间划 分 成 有 限个 区 域 口, , 使 得每 个 区域 中 的对象 都 具有 相 同的 决 策值 . 针 对粗 糙 集理 论 中的 离散 问题 , 基 本 的数据 离散 化方 法 有 等距 离划 分 、 等 频 率划 分 , N a 扮e s e a 一e r 法 、 s e m i N ’iav e s e a ler 法 、 布尔 逻 辑和粗 糙集 理论 相 结合 的方 法等 , 司 , 这些 方法 基本 上属 于单 属性 离散 化 方法 , 存在 着 计算 复 杂 、 离 散化质 量 不高 的缺 点 . 本 文 以粗 糙集 理 论 为基础 , 提 出一 种 在整 体上 按照信 息 表整 个属性 进 行离散 化 , 在 局 部按照 单个 属性 进行 离 散化 , 同时兼顾 信息表 原有 分类 能力 的混 合型 连续 属性 离散化 方法 , 并 通过 实例 验 证此 方法 是 有 效可 行 的 . 的x `为 对象 ; A 是对 象 的属 性集 合 , 分 为两 个不 相 交 的 子 集 , 即 条 件 属 性 集 C 和 决 策 属 性 集 D, A= C u D ; V是属 性 值 的 集 合 , =V u ( Va ) , a 任 A , Va 是 属 性 a 的值 域 J 是 一 个 函数 , 即 xU A 一 V是 一个 映 射 函数 , 它 为每个 对象 的每 个属 性赋 予 一个属 性 值 , 即 V a 任 A , 龙 任 U, 了x( `, a) 任 代 . 定 义 2 在信 息系 统S 中 , 如果 设 =U x{ , , 瓜 , … , 几 凡 }为相 容 性例 子 全集 , 属 性 =C { a , , 角 , … , 编 } 中 只 包含 连 续 型属性 , 每个 例 子x , 所对 应 的属 性值 向 量 为 {场 x(,) , 负(x,) , … , 编 (x,) } , 一 组 例 子 集 合 =x {x, , … 凡} g U 在 同 一个 属 性试任 C 上 的连 续 属 性 值 集 合 为低 (x 1 ) , ia (xz ) , … , ia (x,) } , 则=x {x , , … , xk } g U 在 属性场 上 属 性值 的泛化 区 间 为〔m in a(t (x, ) , a 众)z, … ,风 (xk) ), m ax a(t x(, ) , 风(xz ) , … , 风(x, )] , 那 么 集 合x 所 构 成 的超 立 方 体可 以用 其 每个 属 性 轴 上 的泛 化 区 间来表 示 : [m i n ( a l X( l ) , a l (xz ) , … , a l (x^ )) , m ax ( a , X( : ) , a , (xz ) , … , a : (扁)) ] 1 相 关定 义 及 定 理 粗 糙集 的有 关 定义参 见文 献 3[ 〕 , 这 里只 介绍 几 个 与本 文算 法 相关 的重要 定义 . 定义 1 信 息 系 统 S 定义 为=S ( U, A , V, 力 , 其 中 , U 是 一个 非空 有 限对 象集 合 , 卜 x{ , , 戈 , … , 戈 } , 式 中 收稿 日期 : 2 0 0斗习 -9 16 修回 日期 : 2 0 5刁3 一 14 基金项 目 : 国家自然 科学基 金 资助项 目N( 。 夕0 2 71 0 6 ;8) 辽 宁 省 教育厅 重点科 技基 金困.0 2 0 2 16 3 3 4 5) 作 者简介 : 鄂 旭 ( 19 71 一 ) , 男 , 副 教授 , 博士 研究 生 ! [m i n低X( 1 ) ,编 (xz ) , … , a 二 X(k) ) , m a x 伍 , X( 1 ) ,氏(xz ) , … , a , X(k) )〕 一 组例 子 能否 形成 一个 超立 方 体 , 关键 在 于 它 们 所 形成 的超 立 方体 是 否 含 有异 类 例 子 或者 是 否 与其 他超 立方 体 相 交 . 定义 3 在信 息 系统 S 中 , 尸 是 U 上 的一个 等 价 关系 簇 , 如 Q 二 尸 且 Q 羊 0 , 则信 息 嫡QI ( Q 的所 有 等价 关 系 的交 ) 记 作 IN D (Q) , 它 是 一个 等 价 关系 . 定义 4 在 信 息系 统 S 中 , 设 J丫住 U 是 一个拥 有 因个 样 本 的 集 合 , 则 酬NI D (D ) 二 {艺工 , … ,乙} , DOI: 10. 13374 /j . issn1001 -053x. 2005. 06. 029

Vol.27 No.6 鄂旭等：基于超立方体与信息熵的离散化方法 ·761· ND(C)={X,,,X},则对于任意子集X∈X, POSauta(D)>POSau((D),所以有： xy是子集X,中含有类Y,的样本数，则信息熵 sig(a)-sig(b)-POSD)-POS(D) x,x,,X-lgp,其中，P, U-POSD POSUAb (D)-POS(D) U-POSD)>0 定义5在信息系统S中，样本集X相对于 定理证毕. UNDD)的信息熵： Shannon熵是用来衡量一个系统不确定性程 E0X0-2+IK,X,,X) 度的指标.根据其最大值定理和最小值定理及 叫作相对信息熵. 信息表的特性，可以给出如下定理. 由粗糙集的基本概念，设决策表为S-(U,A, 定理4设决策表为S(U,A,',F),D,为某一决 ”,),其中论域U是一个非空有限对象集合，是对 策属性值集，[4，]n为按条件属性划分的某一等价 象的属性集合，分为条件属性集C和决策属性集 类，令0 c2在倍 D两个不相交的子集，即A=CUD. 息表分别按照条件属性和决策属性进行等价 定义6在信息表S中BsC,c∈C,U=U- 划分的结果中，若VD,3[u,]o,PD4,]nwo上l,则 POS(D)是粗糙边界，可以定义属性c的重要性公 E(U)>E(U)>>E(U),n为等价划分的类别数. 式： 证明：设决策表的论域为U,按照某一个等价 sgoP品 关系在U上的划分为： 根据条件属性与决策属性间的关系及定义 A1={X,X2,,X-1,X,X1,…,X-1,X,Xn,,X}, 的属性重要性公式，可以给出如下定理， A={X,X2,…,X-1,X1,…,X-,X41,,X,XUX} 定理1设决策表为S-(U,A,”,力，其中论域U 则有： 是一个非空有限对象集合，A是对象的属性集合， E(A)-E(A))- 分为条件属性集C和决策属性集D两个不相 交的子集，即A=CUD,HBSC,令U'=U-POS(D) Xutxtx[0u+怀KatXs,…xtx+ 为粗糙边界，如果UND(BU{c})={m,m,…,m,}, x"…x- UND(D小{n,n,,n,},则在粗糙边界中， ttt0 kutXuXatXx…xtx） VcEC,POSKte(D)=UPOSL)(D).. 因为 x+tt+xmn…xn） X 证明： t2t+比0 Cu+XuXar+xa…xm+x20 POS(D)=UBU{cX)=U{Y,∈U1BU{c:Y,二x}= 又因为y+w,x》 U(Y∈{U{UU{Y.Y,eX= Kytxatitxxu)0 U(YE(Y.):Y,X)=UPOSK(D). 所以，E(A)之A).由此可以导出： 定理2设HBsC,Hc∈C且c年B,U=U- E,(U>E,(亿U>>E(U0. POSD)为粗糙边界，则有： 定理5如果一个信息表中的两个实例子集 IPOSL(D)=POS(D)-POS%(D) X,XCU中含有且只含有相同比例数目的决策 证明：对廿c∈C且ctB有两种情况： 类，则两个实例子集的并集XUX具有与X,X相 若c为冗余属性，则 同的相对信息熵. POS(D)=POS(D)=0, 证明：设实例子集X中含有的决策类为 POSKRe (D)=POS(D-POS(D)=0 D,D,…,D,实例子集X中含有的决策类为 若c为重要属性，因为U'=:U-POS(D),所以U= D列_D DD. U+POS(D),POSte(D)=POS(D)UPOSKte,(D), D,D,…D,并且有-7P“xP, 所以lPOS8e(D=POSe(D+POS(D儿. 可得DpKl,D=p,XUX中含有实例总数 定理3设B∈C,Va,b∈C且a,bB,如果属 为X+X,含有的决策类D的数目为D+D 性a比属性b重要，则有siga)-sig(b)>0. pK+pX,由此可以得出决策类D占XUX的比 D(px tpixD 证明：如果属性a比属性b重要，由定理2可 例为X议p,与原实例子集x,名 知属性a比属性b在粗糙边界的分类能力强，即 中的相同.同理可以证明其余的决策类

M 〕 1 . 2 7 N 0 . 6 鄂 旭 等 : 基 于 超 立方体 与 信息嫡 的离散 化方 法 川 IN D (C) = {戈 ,戈 , … , 瓜 } , 则 对 于任 意 子集戈任 X, x , 是 子 集 不 , 中含 有 类 X 的样 本 数 , 则信 息 嫡 (IH 几 一 “ 一纳如, , 其 中 ,P愉 · 定 义 5 在 信息 系 统 S 中 , 样 本 集 X 相对 于 训NI D (D ) 的信 息嫡 : p O S , u { 口 } (D ) > PO S , u {。 , (D ) , 所 以有 : 5 19 ( a ) 一 5 19( b ) = (EP 琪 互竺窗生五` 帆 , Xjz , 一 瓜’ 叫作 相对 信 息墒 . 由粗 糙集 的 基本 概念 〔:i] , 设决 策表 为个( U, ,A V, 力 , 其 中论域 u 是 一个 非 空有 限对 象集 合 , 是对 象 的属性 集 合 , 分 为条 件属 性 集 C 和 决策 属性 集 D 两 个 不 相交 的 子集 , 即才 二 C u D . 定义 6 在 信 息表 豹扣V B g C , c 任 C , U =, U一 PO S戮D )是粗 糙边 界 , 可 以定义 属性 c 的重要 性 公 式 : “ ` · 卜!淄韶旱 定理 证 毕 . S h an o n 墒 是用 来衡 量 一个 系 统不 确 定性 程 度 的指 标 . 根 据其 最 大值 定 理 和最 小 值定 理 〔7] 及 信 息 表 的特 性 , 可 以给 出 如下 定 理 . 定理 4 设 决策 表 为赓(口月尤月 , jD 为某 一 决 策属 性值 集 , 〔ut] NDI 为按条 件 属性 划分 的某 一等 价 举 . 今尸 (D 打u,1 _ 卜舆契奥醉 二 丝照犯奥醉霖 信 玖 L封 x J加 ) C盯 Q LL封`」彻 ) 一 ’ ~ 息 表 分 别 按 照 条 件 属 性 和 决 策 属 性 进 行 等 价 划分 的结 果 中 , 若 V 几 〕 「u,] NDI , 尸(p 尹 }【ut] NDI )月 , 则 E , (功> 石2 (功>. 二 > 瓦 (功 , n 为等 价 划 分 的类 别数 . 证 明 : 设 决策表 的论域 为 U , 按照 某 一个 等价 关系 在 U 上 的划 分 为 : 根据 条 件 属 性 与 决 策 属 性 间 的 关 系及 定义 的 属性 重 要性 公 式 , 可 以给 出如 下 定理 . 定理 1 设 决策 表 为=S ( U, A , V, 力 , 其 中论 域 U 是 一个非 空有 限对象 集 合 , A 是对 象 的属性集 合 , 分 为 条 件 属 性 集 C 和 决 策 属 性 集 D 两 个 不 相 交 的子 集 , 即A 二 C u D , V B 互 C , 令 U 任 U 一 PO S戮D ) 为粗糙 边 界 , 如 果 U llN D (B U { c }) = { m l , m Z , … , 札 } , 川NI D (D ) 一 { n , ,从 , … , 久} , 则在 粗 糙边 界 中 , 川= {戈 ,龙 A Z= {戈 ,龙 则 有 : , … ,戈 一 , ,尤 , 恙 1 , … , 不 一 , , 戈 , , … ,戈 一 1 ,戈 十1 , … ,戈 一 , ,戈 + , , 养 1 , … , Xn } , ,龙 ,戈 U戈 } , V e 任 C , P O S能、 。 , (D ) = u P O S乳{ 。 }归 ) , . J= 1 证 明 : P O S筑、 : } (D ) = u 刀 u { e }氏 ) = u { X 任 U ( B 口 { e } : X 二戈 } 二 u {X 任 {叭 } u {乙 } u … u {式} : X 二 戈卜 u {艺e { X } : 艺二不 } = u P O S乳{ 。 } (D ) , (EA 1 , 一 (EA 2 )里翁鱼堆 苦1声 Z j, … 声 , ` , - 业裔热称 . 、 砂 2j , … 、 周 + 互号均 以内 , … 、 - 业裔丛取 1 +,x1j 丙+vx , … 声, 、 因为 业裔场心 1丙 , …励 - 世翁 兰鱼心+l,x1j 砂 2j , … 声两 ) 二 0 又 因为 星翁均 以 ljN 二 司 - 业裔卿取、 、 2j , … 声两 ) 二 0 定 理 2 设 V B 互 C , V c 任 C 且 c 子B , 甘 = 口一 P O S欲刀) 为粗糙 边 界 , 则 有 : ! p O S筑{ 。 } (D )卜} p O S跳{ 。 } (I ) )卜} p O S班D )! 证 明 : 对 V c 任 C 且 c 磋B 有 两种 情 况 : 若 。 为 冗余 属性 , 则 ! P O S能{ 。 } (D ){ = } p O S了(D )} = 0 , } p O S乳、 。 、 (D )} = { p O S别刀: .卜{ p O S欲刀)} = 0 若 c 为重 要属 性 , 因为 理= U 一 P O S B沪) , 所 以 =U “ +, P O S 。 (D ) , 则 P O S箭{ 。 } (D ) = PO S言(D ) 曰 p O S能( 。 } (D ) , 所 以 } p O S乳、 。 } (D )卜} p O S跳。 。 }心, )卜} p O S会飞D )} . 定理 3 设 V B 生 C, V a才 ,任 C 且 a , b 磋B , 如 果 属 性 a 比属 性 b重 要 , 则 有 5 19 ( · ; ) 一 5 19 ( b ) > 0 . 证 明 : 如 果属 性 a 比属 性 b 重要 , 由定 理 2 可 知 属 性 a 比 属 性 b 在 粗 糙边 界 的分 类 能 力强 , 即 所 以 , E (A 1 ) 七 E (A 2 ) . 由此 可 以导 出 : E , ( 叻> 百 2 (功> … > 石 月 (叻 . 定 理 5 如 果一 个 信 息 表 中 的两 个 实 例 子集 戈 式 c U 中 含 有 且 只 含 有 相 同 比 例 数 目 的决 策 类 , 则 两个 实 例 子集 的 并集戈 U不 具 有 与戈 式 相 同 的相对 信 息 墒 . 证 明 : 设 实 例 子 集尤 中 含 有 的 决 策 类 为 酬 刀’,. · 几 , 实 例 子 集 戈 中 含 有 的 决 策 类 为 酬“ ,一“ , 并 且有 捌 一鲁 一 lP , … , 鲁斜 二 , , 可 得 }D ;}, 1比 } , }侧 }=P ,比} , 戈 日不 中含 有 实例 总数 为 比卜因 } , 含有 的决策 类 D , 的数 目为 }侧卜}侧卜 p l比}+P ;比 } , 由此可 以得 出决策类 D , 占戈 u 不 的比 例 “ 哉 一 嚼剖 , 1 , 与 原 实例 子集、 , ; 中 的 相 同 . 同 理 可 以 证 明 其 余 的 决 策 类

·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 结论 本算 法 由于 自定 义 了新 的属性 重 要性 公式

Vol.27 No.6 鄢旭等：基于超立方体与信息熵的离散化方法 ·763· 因此，计算属性的复杂度由原来的O(4)降低 北京科技大学学报，2005,273：364 为现在的O(4Y++YP):同时对断点重要性 [3)王国胤.Rough集理论与知识获取.西安：西安交通大学出 版社，2003 进行了量化，因此对断点的选取更为合理，能够 [4)苗夺谦.Rough Set理论中连续属性的离散化方法.自动化 产生较小数目的断点集；引入分类信息熵作为约 学报，200L,27(3:296 束条件，保证了断点选取得方向性和可靠性，同 [5]Nguyen H S,Skowron A.Boolean reasoning for feature extrac- 时进一步起到了属性约简、属性值约简的作用， tion problems.In:10th International Symposium on Foundations 降低了离散算法的时间复杂度和空间复杂度， of Intelligent Systems.New York:Springer-Verlag,1997.116 [6]Nguyen S H,Skowron A.Quantization of real value attributes- rough set and boolean reasoning approach.Bull Int Rough Set 参考文献 Soc,1996(1):347 [1]Pawlak Z.Rough Set.Int J Comput Inf Sci,1982 (1):341 [7)孟庆生.信息论.西安：西安交通大学出版社，1986 [2]鄂旭，高学东，武森，等.信息表中不完备数据的填补方法 Discretization algorithm based on super-cube and information entropy EXU,GAO Xuedong",TAN Wendong",WANG Ying" 1)Department of Computer Science,Liaoning Institute of Technology,Jinzhou 121001,China 2)Management School,University of Science and Technology Beijing,Beijing 100083,China ABSTRACT Discretizing continuous attributes in a rough set were researched.Based on the concept of super-cube, all attributes of the information table in data space were globally discretized.By the consistent correlation of condi- tion attributes and decision attributes,important condition attributes were selected depending on their classifying ability in the rough set boundary zone,and furthermore,important breaking points were selected to discretize the in- formation table on a single attribute locally with the iterative constraints of information entropy.Illustration and ex- perimental results indicate that the algorithm combining the global and local discretization is effective and efficient. KEY WORDS rough set;discretization;super-cube;information entropy 表本冷茶冷李素条率者米条米*杂孝卷幸冷本为*米条年冬海奇为女★*染为*米激余孝章装条次餐女米中冷米条弹京备整个女*资*★路今率京食薄海冷★*米**米冷★率郑素余冷*冷★冷数章女 (上接第739页) Production mode optimization of a steelmaking workshop system LIU Oing",HUANG Xingwu,FU Pingyuan 1)Metallurgical and Ecological Engineering School,University of Science and Technology Beijing,Beijing 100083,China 2)Xinjiang Bayi Iron Steel Co Ltd.Urumchi 830022,China 3)Linfen Iron and Steel Co.Ltd.,TISCO Group,Lifen 041000,China ABSTRACT The problem about running mode optimization of a steelmaking workshop system,which is the most complicated subsystem in a steel manufacturing process system was discussed by applying the theory of metallurg- ical engineering.The level and logical relation of the running mode of a steelmaking workshop in the productive process were described and studied in combination with its applications in Chinese four BOF workshops with the technology of high efficiency continuous casting.Three effects of production mode optimization were summarized and illustrated in detail:(1)the layout of a workshop tending to rationality and briefness,(2)the buffer of working procedures tending to rationality and efficiency,and(3)the operation of working procedures tending to high effi- ciency and optimization.These conclusions are applied to the research of optimization and control in special steel- making process operation,and valuable results are acquired. KEY WORDS steelmaking workshop;ferrous metallurgy process engineering;production mode;process optimi- zation:mass flow

、勺 l 一 7 N o 2 一 鄂旭 等 基于 超立方 体 与信 息嫡 的离 散 化方 法 : 6 . 7 6 3 - 因 此 , 计算 属 性 的复 杂度 由原 来 的 O (l川}酬 2 ) 降低 为现 在 的口(团( 1艺1 2 +. 二 + {玖 } , ) ; 同时对 断 点重 要 性 进行 了量化 , 因 此对 断 点 的选取 更 为 合理 , 能够 产生 较小数 目的 断点集 ; 引入 分类 信息 嫡 作为 约 束条 件 , 保 证 了断点 选取 得 方 向性 和 可靠 性 , 同 时进 一 步起 到 了属 性 约简 、 属 性值 约 简 的作 用 , 降低 了离散算 法 的时 间复 杂度 和 空 间 复杂 度 . 参 考 文 献 f l ] P a w lak 2 . OR u g h S e t . I n t J C o 二 p u t I n f s e i , 19 8 2 ( l ) : 34 1 2[ ] 鄂旭 , 高学 东 , 武森 , 等 . 信 息表 中不完 备数据 的填 补方 法 北京 科技 大学 学报 , 2 0 0 5 , 2 7( 3 ) : 36 4 3[] 王 国溉 . oR u gh 集 理论 与知识 获取 . 西 安 : 西安 交通 大学 出 版 社 , 2 0 0 3 4[] 苗 夺谦 . oR gu h se t 理 论 中连 续 属性 的离散 化方 法 . 自动化 学报 , 2 00 1 , 2 7 ( 3 ) : 29 6 [5 1 N g u界n H S , S k o w or n A . B o o l e an 祀 a s o n in g of r fe a t u r e e xtr a e - t i o n P or b l e m s . I n : 10 ht I n t e l刀 a t i o n a l S y m P o s i um o n F o un dat i on s o f l n t e llig e n t s y s t e m s . N e w 丫b r ` : S P ir n g e -r Ve r l a g , 1 99 7 . 116 [6 ] N g ly e n S H , S k o w or n A . Q aun t i z at ion o f re a l v a lue a itr b u t e s - or u g h s e t an d b o o l e a n fe a s o n i n g ap pm ac h . a u u I n t OR u gh S e t S o c , 19 9 6 ( 1 ) : 34 7 7[ 」 孟庆生 . 信 息论 . 西 安 : 西安 交通 大学 出版社 , 19 86 D i s e re ti z at i o n a lg o r it h m b a s e d o n s uP e -r c u b e an d i n of rm a t i o n e n otr P y E X zj l只 GA 口 xu e do 心气TA N 确 n do gn ,气恻刃 G 五n g Z ) 1) D e P a rt m e n t o f C o mP ut e r s e i e n e e , L iao n i n g l n s t itU t e o f eT e hn o l o g又 Jinz ho u 12 1 00 1 , C h i n a 2 ) M a n a g e m e nt s e h o o l , nU iv e r s ity 0 1 ’ s e i e n e e an d eT e hn o l o g y B e ij i n g , B e ij i雌 10 0 0 8 3 , C h i n a A B S T R A C T D i s e re t i z i n g c o n t i n u o u s a t r i b ut e s i n a or u g h s e t w e re re s e 毗he d B a s e d o n ht e e o cn e Pt o f s uP e -r c ub e , a ll a t r lb ut e s o f ht e in fo mr at i o n abt l e i n d at s P a c e w e er g l o b a ll y d i s e er t i z e d . B y ht e e o n s i s te in e o 讹 l at i o n o f e o n di - t i o n a itr b ut e s an d d e e i s i o n 川itr b u t e s , im P o rt a l l t e o n d i ti o n a t r i b u t e s w e er s e l e e et d d e P e n d in g o n ht e i r e l a s s ify i n g ab i l i yt i n ht e or u g h s et b o u n d a yr z o n e , a n d fu rt h e mr o er , im P o rt a n t b er ak i n g P o int s w e代 s e l e e t e d ot d i s e er ti z e ht e i n - fo mr at ion t ab l e o n a s i n g l e at r i b ut e l o e a l ly w i ht ht e it e r at i v e e o n s tr a i n t s o f i n fo mr at i o n e n t or P y . Il l u s tr at i o n an d e x - P e ir m e n t a l er s u lt s i n d i c at e ht a t ht e a l g o ir t h m e o m b i n i n g ht e g l o b a l an d l o c a l d i s e er t i z at i o n 1 5 e fe e t i v e an d e if e i e n t . K E Y WO R D S r o u g h s e t : d i s; e er t i z a t i o n : s uP e -r e u b e : i n fo mr at i o n e nt or P y (上 接第 7 39 页 ) P or d u c it o n m o de o P t ixn i z at i o n o f a s et e lm a k i n g w o kr s h o P s y s t e m “ “ Qi n g , ), H。月刃 G ix 刀 g w: 。, ), F U p i刀 g夕u a n , , l ) M e at ll u 电 i e a l a dn E e o l o g i e a 1 E n g i r Le e ir gn S e h o o l , U n i v e r s ity o f s e i e n c e an d eT e h n o l o g y B e ij i n g , B e ij i n g l 0 0 0 83 , C h i n a 2) X inj i a n g B ay i rID n & S t e e l C o L t d . U rum e h i 8 3 00 2 2 , C h i n a 3) L i n fe n Ior n a n d S t e e l C o . L td , T I S C O G or uP , L ife n 04 1 00 0 , C h i n a A B S T R A C T T h e Por b l e m al ) o u t run n i n g m o d e o P t im i z at i o n o f a s t e e lm ak i n g w o rk s h o P s y s te m , w h i e h 1 5 ht e m o s t e o m P l i e at e d s u b s y s t e m i n a s t e e l m an u af e tUr i n g P or e e s s s y s t e m w a s d i s e u s s e d b y ap P ly in g ht e ht e o yr o f m e t a lin gr - i e a l e n g i n e e ir n g . T h e l e v e l ar 一d l o g i e a l er lat i o n o f ht e unr n i n g m o d e o f a s t e e lm a ik n g w o kr s h o P i n ht e Por du e t i v e P or e e s s w er d e s e r ib e d an d s l u d i e d i n c o m bi n at i o n w ith it s ap P li e at i o n s i n C h i n e s e fo ur B O F w o kr s ho P s w iht ht e te e hn o l o gy o f h i g h e if e i e n c y e o n t i n u o u s e a s t i n g . T h er e e fe c t s o f P or du e t i o n m o d e o P t im i z at i o n w e er s u n l n l ar i z e d an d i l l u s tr at e d i n d e t a i l : ( l ) ht e l盯o u t o f a w o kr s h o P t e n d i n g t o r a t i o n a liyt an d b ir e hf e s s , ( 2 ) ht e b u fe r o f w o kr i n g P or e e d u er s t e n d i n g t o art i o n a j i yt an d e if e i e n e y, an d ( 3 ) ht e o P e art i o n o f w o kr i n g orP e e d u er s t e n d i n g t o h ihg e if - e i e n e y an d o Pt im i z at i o n . hT e s; e e o n e fu s i o n s aer a P P li e d t o ht e er s e娥h o f o P tim i z at i o n an d e o n tDI I i n s P e e i a l s t e e l - m ak i n g Por e e s s o P e r at i o n , an (1 v a l u ab l e er s u l t s aer a e q u i er d . K E Y W O R D S st e e lm iak n g w o r k hs op : fe our s m e at ll u r g y P r o e e s s e n g i n e e r i n g : P or du e it o n m o d e : Por e e s s o P t im i - z at i o n ; m a s s fl o w