《基于区分能力大小的启发式约简算法的研究》由会员分享，可在线阅读，更多相关《基于区分能力大小的启发式约简算法的研究（8页珍藏版）》请在金锄头文库上搜索。
1、第 29 卷? 第 3 期 2006 年 3 月计 ? ? 算? 机 ? ? 学? 报 CHINESE JOURNAL OF COMPUTERSVol. 29 No. 3 M ar. 2006 ?收稿日期: 2005?01 ?20; 修改稿收到日期: 2005 ?11?30. 陈堂敏, 男, 1962 年生, 硕士, 副教授, 高级工程师, 主要从事仪器仪表和故障监测装置的开发研制和教学工作. E ?mail: 8511 gdqy. edu. cn.基于区分能力大小的启发式约简算法的研究陈堂敏( 中山大学软件所? 广州? 510300)( 广东轻工职业技术学院机电系? 广州? 510300)摘
2、? 要? 通过对徐燕等提出的能有效处理噪音的基于区分能力大小的启发式约简算法的研究, 认为所提出的对知 识进行量化、 证明量化的合理性、 给出的算法和实例证明的过程中还有一些不完善的地方, 需要进行修正. 该文提出了修正方法, 并通过实例证明了修正后的算法对知识进行量化、 证明量化的合理性、 以知识量为启发函数的约简修正是正确的.关键词? 知识量; 数据挖掘; 约简; 算法; 修正中图法分类号TP18Research of the Heuristic Reduced Algorithm Based on the Separating CapacityCHEN T ang?Min(Sof twa
3、re School, Sun Yat?Sen University , Guangzhou ? 510300)(Electro?mechanical Department, Guangdong L ight Industry Technical College, Guangzhou? 510300)Abstract?We studied the heuristic reduced algorithm based on the separating capacity, proposed in paper 1, and it is useful to deal with the noise. We
4、 think we can improve something not soprefect, just as the knowledge quantification, the proof of the quantifying rationality, the algo? rithm they proposed and the process proved by example. We proposed some methods to improve theirs, and we also used example to prove them. We proved that the knowl
5、edge quantification af?ter the improvement is correct. We proved that the proof of the quantifying rationality after the improvement is correct.We proved the reduced improved algorithm referring the knowledge quantity as the heuristic function and the process proved by example are correct.Keywords?k
6、nowledge quantity; data digging; reduction; algorithm; improvement1 ? 引 ? 言文献 1 提出了一种能有效处理噪音的基于区 分能力大小的启发式约简算法, 该算法基于粗集理论中知识是区分事物的能力的观点, 对知识进行量化, 证明了量化的合理性, 并以量化后的区分能力作为启发式信息, 指导约简, 提高了约简效率. 另外, 用这种启发式信息, 提出了一种解决噪音问题的方法. 但该文在对知识进行量化、 证明量化的合理性、 给出的算法和实例证明的过程中还有一些不完 善的地方, 需要进行研究, 加以明确. 本文在对基于 区分能力大小的启
7、发式约简算法进行研究的基础上, 对该约简算法的证明和实例应用提出了修正 意见.2 ? 知识量性质证明的研究与改进2 ? 1? 粗集理论的基本概念 有关粗集理论中概念的精确定义可以参看文献 2, 3 , 以下对用到的部分概念进行简单的描述.设 u 是一个论域, P, Q 是 u 上的等价关系簇,如果 P, Q 在u 上导出的所有等价类相同, 则 P 与Q具有相同的区分能力, 或者说 P 与 Q 是等价的.设 u 是一个论域, P 为定义在 u 上的一个等价关系簇, 一个关系 R ? P 如果 P - R 与 P 具有相 同的区分能力, 则称关系 R 在 P 中是不必要的( 多余的); 否则, 称
8、 R 在 P 中是必要的, 不必要的关系在等价关系簇中是多余的, 如果将它去掉, 不会改变等价关系簇的区分能力. 设 u 是一个论域, P, Q 为定义在u 上的一个等价关系簇, Q ? P, 如果 Q 与 P 具有相同的区分能力, 并且 Q 中没有多余的关系, 则称 Q 是 P 的一个 约简.约简不是唯一的, 其中包含关系最少的约简为最小约简, 最小约简是应用中大家较感兴趣的约简,但已证明最小约简的计算是 NP?难问题. 2 ?2? 知识量性质的研究与修正在粗集理论中, 一个重要的概念就是可区分关系, 设 u 是一个论域, P, Q 是 u 上的等价关系簇, 如 果 P, Q在 u 上导出的
9、所有等价类相同, 则 P 与 Q具有相同的区分能力, 或者说 P 与 Q 是等价的; 否则, P 与Q 是可区分的, 将知识与区分事物的能力对应起来, 即在论域中所有元素, 如果两两间都能被 区分, 那么就具有较多的知识; 如果在论域中所有元素只能划分为同一个等价类, 不能将任何一个元素与其它元素区分开来, 这时具有的知识为最少, 基于 这种观点, 以下将区分事物的能力当作知识量, 给出一个表达式对知识进行度量.以下针对信息表进行探讨.定义 1 1. ? 信息表某属性集合 P 将论域 u 分 成m 个等价类, 每个等价类有元素数目分别为 n1,n2, , nm, 那么该属性具有的知识量记为 W
10、u, p=W( n1, n2, , nm), 表达式 W ( n1, n2, , nm) 中的参 数个数为等价类的个数, 它满足:! W(n)= 0(对于任意的自然数 n); W(n1, , ni, , nj, , nm) = W ( n1, ,nj, , ni, , nm); # W( n1, n2, , nm) = W (n1, n2+ + nm) +W( n2, n3, , nm);W(n1, n2+ n3)= W( n1, n2)+ W(n1, n3) .我们对以上的定义进行说明: 如果某知识不能区分论域 u 中的任何元素, 即该知识将论域 u 分成一个等价类, 该知识对于 u 来说,
11、 它的区分能力为 0, 即 W(n) = 0. 如果某属性集合 P 将论域u 分成m 个等价类,每个等价类有元素数目分别为 n1, n2, , nm, 对于等价类不同的排列顺序, 同一个属性集合应具有相同的区分能力, 所以有W ( n1, , ni, , nj, , nm) =W(n1, , nj, , ni, , nm), 但要注意两个属性具 有相同的知识量并不能断定这两个属性集合是同一个属性集合.如果某属性集合 P 将论域 u 分成 m 个等价类, 每个等价类有元素数目分别为 n1, n2, , nm, 则属性P 能将n1从 u 中其它元素中区分开来, 也能将剩余的元素分成 m- 1 个等
12、价类, 每个等价类有元素数目 分别为 n2, n3, , nm, 所以应有 W( n1, n2, , nm)=W(n1, n2+ + nm)+ W(n2, n3, , nm).如果某属性集合 P 将论域 u 分成 2 个等价类 u1和 u2, 每个等价类有元素数目分别为 n1, n2+ n3,那么该属性能够将 u1中的元素与 u2中 n2个元素区分开, 也能够将 u1中的元素与 u2中另外 n3个元素区 分开, 即 W( n1, n2+ n3)= W(n1, n2)+ W(n1, n3) .上述定义的知识量是根据粗集理论认为知识是区分事物的能力而得到的, 我们可以得到以下 性质.定理 1. ?
13、 如果某属性集合将论域 u 分成 m 个等价类, 每个等价类有元素分别为 n1, n2, , nm, 那 么该属性集合具有的知识量 W ( n1, n2, , nm) =W(1, 1) %Wn= 0; ?= 0; n= 1.1. 计算属性集合 P 的知识量 W ;2. 分别计算 P 中每个属性的知识量, 求出知识量最大的属性, 记为 pn. 该属性的知识量为 ?;3. Q ) Q pn , P ) P- pn , Wn) W - ?;4. 如果 Wn/ W ?n+ 1, W - ?n ? , 继续进行. n= 1+ 1= 2. 文献 1 中分别计算的 4 个属性相对于 Q 的知识量如表 3.表
14、 3? 4 个属性的相对知识量属性分成的等价类的个数相对 Q 的知识量Make _ model69 power30 comp44 mileage58而实际在求相对于 Q 的相对知识量时, power被分成了 5 个等价类, 即 n1= 4, n2= 1, n3= 1, n4= 3, n5= 1, 则相对知识量= n1( n2+ n3+ n4+ n5) +n2(n3+ n4+ n5) + n3( n4+ n5) + n4n5- 32= 36- 32= 4, 而不是表 3 中的 0.所以分别计算的 4 个属性相对于 Q 的知识量如表 4.表 4? 4 个属性的相对知识量( 修正后)属性分成的等价类
15、的个数相对 Q 的知识量Make _ model69 power54 comp44 mileage58因为 Make _model 的相对知识量 ?2= 9 为最大, ?) ?+ ?2= 41. 转到 # .#( 所 以 将 Make _model 加入 Q 中, Q = weight, Make _model; P = power, comp, mile?age, W2= W- ?= 42- 41= 1. (W2/ W= 1/ 41= 0?0244 ? , 程序继续.(n= 2+ 1= 3.分别计算的 3 个属性相对于 Q 的知识量如表 54853 期陈堂敏: 基于区分能力大小的启发式约简算
16、法的研究所示.表 5? 3个属性的相对知识量属性分成的等价类的个数相对 Q 的知识量power71comp60mileage60因为 power 的相对知识量 ?3= 1 为最大, ? )?+ ?3= 42. 转到# .#+将 power 加入 Q 中, Q= weight, Make _model, power; P= comp, mileage , W3= W- ?=42- 42= 0. +W3/ W= 0/ 41= 0 ? , 程序终止. 集合Make _model, weight, power为所求的约简.文献 1 给出的噪音消除方法的举例如下:如果在实际采集数据时产生了误差, 得到的数据在元素 3 的 comp 数据出现了误差得到值为light, 这时知识量的计算变化如表 6 所示.表 6? 出现误差时的相对知识量计算属性知识量相对于weight 的知识量相对于Make _ model, weight的知识量Make _ mode
