工程科学学报，第38卷，第3期：425-431,2016年3月 Chinese Journal of Engineering,Vol.38,No.3:425-431,March 2016 D0l:10.13374/j.issn2095-9389.2016.03.018:http://journals.ustb.edu.cn 一种基于粗糙集属性度量的集成分类器 王永生12》，郑雪峰1,2》 1)北京科技大学计算机与通信工程学院，北京1000832)北京科技大学材料领域知识工程北京市重点实验室，北京100083 ☒通信作者，E-mail:binetbee@l63.com 摘要为了准确度量属性的重要性，从基于粗糙集的属性度量视角，提出一种基于混合度量机制的属性评价方法，该方法 从不同的信息粒度分析属性的重要性.在混合度量机制中，根据数据分布特点引入参数权重因子。在此基础上，构造一种基 于粗糙集属性度量机制的集成分类器.通过实验结果和比较分析表明，所提出的方法能有效地降低数据的属性维度，相比较 于单一属性度量准则，分类器具有更好的分类性能 关键词数据挖掘：属性：度量：分类器：粗糙集理论 分类号TP18 An ensemble classifier based on attribute measurement of rough sets WANG Yong-sheng.2》,ZHENG Xue-feng2》 1)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Beijing Key Laboratory of Knowledge Engineering for Materials Science,University of Science and Technology Beijing 100083,China Corresponding author,E-mail:binetbee@163.com ABSTRACT From the viewpoint of the attribute measurement of rough sets,a new attribute measurement based on the hybrid metric mechanism was provided to accurately evaluate the significance of attributes.This proposed attribute measurement analyzes the signifi- cance of attributes from different levels of information granularity.In addition,a parameter weighting factor was introduced to the attribute measurement according to the characteristics of data distribution.On this basis,an ensemble classifier was constructed based on the proposed attribute measurement mechanism in rough sets.Experimental results and comparative analysis show that the proposed method can effectively reduce the attribute dimension of data.Compared with the single attribute measurement,the proposed method has a better classification performance KEY WORDS data mining:attributes;measurement:classifiers:rough set theory 近年来，属性约简（特征选择）作为数据挖掘与机简算法在处理高维复杂数据和有效提高分类器的分类 器学习领域中重要的降维技术，得到越来越多研究人 性能和计算效率有待进一步研究5.为此，相关研究 员的关注，已成为一个重要的研究课题.属性约简是 工作引起广大研究者们的关注. 指在保持某种区分能力不变情况下从原始属性集中选 现有的特征选择方法主要分为2种：Wrapper方法 取属性子集的过程·.有效的属性约简可较好地去除 和Filter方法.Wrapper方法依赖于具体的学习算 数据中不相关和冗余的属性，从而能有效提高分类器 法来选择满足条件的属性子集；而Filter方法独立于 的计算效率和分类性能。当前，已许多学者提出基于 学习算法，利用属性评估准则来选择属性子集.基于 不同粗糙集模型的属性约简方法2.现有的属性约 粗糙集的属性约简方法作为一种重要的Filter特征选 收稿日期：2015-08-03 基金项目：国家自然科学基金项目(61163025)：材料领域知识工程北京市重点实验室（北京科技大学）2012年度阶梯计划资助项目 (Z121101002812005)
工程科学学报，第 38 卷，第 3 期: 425--431，2016 年 3 月 Chinese Journal of Engineering，Vol． 38，No． 3: 425--431，March 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 03． 018; http: / /journals． ustb． edu． cn 一种基于粗糙集属性度量的集成分类器 王永生1，2) ，郑雪峰1，2) 1) 北京科技大学计算机与通信工程学院，北京 100083 2) 北京科技大学材料领域知识工程北京市重点实验室，北京 100083 通信作者，E-mail: bjnetbee@ 163． com 摘 要 为了准确度量属性的重要性，从基于粗糙集的属性度量视角，提出一种基于混合度量机制的属性评价方法，该方法 从不同的信息粒度分析属性的重要性． 在混合度量机制中，根据数据分布特点引入参数权重因子． 在此基础上，构造一种基 于粗糙集属性度量机制的集成分类器． 通过实验结果和比较分析表明，所提出的方法能有效地降低数据的属性维度，相比较 于单一属性度量准则，分类器具有更好的分类性能． 关键词 数据挖掘; 属性; 度量; 分类器; 粗糙集理论 分类号 TP18 An ensemble classifier based on attribute measurement of rough sets WANG Yong-sheng1，2) ，ZHENG Xue-feng1，2) 1) School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Beijing Key Laboratory of Knowledge Engineering for Materials Science，University of Science and Technology Beijing 100083，China Corresponding author，E-mail: bjnetbee@ 163． com ABSTＲACT From the viewpoint of the attribute measurement of rough sets，a new attribute measurement based on the hybrid metric mechanism was provided to accurately evaluate the significance of attributes． This proposed attribute measurement analyzes the significance of attributes from different levels of information granularity． In addition，a parameter weighting factor was introduced to the attribute measurement according to the characteristics of data distribution． On this basis，an ensemble classifier was constructed based on the proposed attribute measurement mechanism in rough sets． Experimental results and comparative analysis show that the proposed method can effectively reduce the attribute dimension of data． Compared with the single attribute measurement，the proposed method has a better classification performance． KEY WOＲDS data mining; attributes; measurement; classifiers; rough set theory 收稿日期: 2015--08--03 基金项目: 国家自然科学基金项目( 61163025 ) ; 材料领域知识工程北京市重点实验室( 北 京 科 技 大学) 2012 年度阶梯计划资助项目 ( Z121101002812005) 近年来，属性约简( 特征选择) 作为数据挖掘与机 器学习领域中重要的降维技术，得到越来越多研究人 员的关注，已成为一个重要的研究课题． 属性约简是 指在保持某种区分能力不变情况下从原始属性集中选 取属性子集的过程［1］． 有效的属性约简可较好地去除 数据中不相关和冗余的属性，从而能有效提高分类器 的计算效率和分类性能． 当前，已许多学者提出基于 不同粗糙集模型的属性约简方法［2--4］． 现有的属性约 简算法在处理高维复杂数据和有效提高分类器的分类 性能和计算效率有待进一步研究［5--7］． 为此，相关研究 工作引起广大研究者们的关注． 现有的特征选择方法主要分为 2 种: Wrapper 方法 和 Filter 方法［8--9］． Wrapper 方法依赖于具体的学习算 法来选择满足条件的属性子集; 而 Filter 方法独立于 学习算法，利用属性评估准则来选择属性子集． 基于 粗糙集的属性约简方法作为一种重要的 Filter 特征选
·426· 工程科学学报，第38卷，第3期 择方法0，由于无需数据以外的信息和计算效率优 1.1基于正区域模型的属性度量 势，受到大量研究者们的关注.随着对属性约简方法 基于正区域模型的属性度量是从数据的正样本视 进行不断研究和探讨，研究者们力求求解出最优的属 角对属性进行度量，主要度量数据中一致性对象对属 性子集来提高分类器的分类性能，即在属性约简过程 性的影响，是一种确定性的信息度量方法.该方法是 中，求解出一组最优的属性评价准则.针对基于粗糙 由Pawlak和Skowron提出)，主要是通过数据中对象 集的属性约简研究，国内外研究人员已经设计了多种 的一致性来评价属性的重要性，即通过每个属性下正 不同的属性评价准则对数据中的属性进行度量研究， 区域中样本个数进行评价，以解决数据中正样本较大 且取得一些显著成果.根据不同的属性度量定义，不 且分类数较少的情况，其本质是根据属性对数据中正 同的属性度量准则被给出。常见的属性度量准则有基 样本的区分能力进行属性评估，重要的属性应能计算 于正区域的属性度量四、基于差别矩阵的属性度 出数据中更多的同类正样本，有效减少不一致样本对 量圆以及基于信息熵的属性度量的.目前，针对这3 分类的影响 种单一属性度量方法，研究者们提出许多不同的属性 定义1五元组S=(U,C,D,V,)是一个决策表 约简算法.针对单一属性度量的不足，研究人员Qian 其中：U为对象的非空有限集合，称为论域：C为非空 等的提出基于混合优化的属性度量方法，有效提高规 的条件属性集合；D为非空的决策属性集合：A=CUD 则获取的效率。目前，大多数算法主要还是使用单一 为属性的非空有限集合：V=U'。,V.表示属性a的值 属性度量准则下评估属性的重要度 域f:U×A→V是一个信息函数，即对Hx∈U,a∈A,有 由于高维数据中样本的分布较复杂，单一属性度 f(x,a)∈V 量准则往往无法准确评价属性在数据样本中的重要性 定义2在决策表S=(U,C,D,V,)中，设U/D= 优劣.另外，在分类器分类时，单一属性度量准则计算 {D,D2,…,D}表示由决策属性集D对论域U的划 出的属性约简结果可能造成分类性能和普适性的效果 分，U/C={C,C2,…,Cm}表示由条件属性集C对论 不理想.由于不同的属性度量准则往往是从不同的侧 域U的划分，则称C.(D)=U{C1CCD}(i=1,2, 面反映属性的重要性，它们之间存在一定的互补性， ,k)为D在U上关于C的下近似集，称C(D)= 因此可利用多准则属性度量机制对属性的重要性进行 U{CICnD≠}(i=1,2,,k)为D在U上关于C 评估.目前已有学者借助属性融合方法实现属性的重 的上近似集，称POSe(D)=C.(D,)为D的C正 要性度量a,但其设计思路往往是在不同的属性层次 区域 上对属性进行度量，它是一种“分层递阶”的度量方 定义3在决策表S=(U,C,D,V,)中，记rc(D)= 式，即先利用某种度量方法对属性的重要性进行评价 和排序，再利用另一种属性度量方法对属性序列进行 三1C.(D)1八U川条件属性集C关于决策属性集D 度量.若先前的属性度量方法不合理时，会使得后续 的近似质量，若rc(D)=1,则称决策表为相容的，否则 的属性度量方法失效，进而不能从根本上提高算法的 称决策表不是相容的 分类性能.为此，本文提出一种基于混合度量方法的 注：决策表是相容的实质是由条件属性集C对论 属性度量机制，通过属性的信息融合方法综合了不同 域U的划分是由决策属性集D对论域U的划分的加 度量准则的属性度量信息，该机制可广泛应用于各种 细，也就是说对任一个C,∈U/C,总存在一个D:∈U/D 决策分析问题.在混合属性度量机制中引入参数权 使得C,二D. 重.在此基础上，构造一种基于粗糙集的混合属性度 定义4在决策表S=(U,C,D,V,)中，R为任意 量机制的集成分类器.通过实验测试和结果分析来验 条件属性子集，一个条件属性a∈C-R(RCC)对于 证提出机制的有效性和可行性。结果表明该属性度量 决策属性的重要度Sig(a,R,D)定义为 机制比单一属性度量准则具有更高的分类精度 Sig(a,R,D）=rual-「g 1属性度量方法 其中rR=IPOS（D)I/八UI. 定义5在决策表S=(U,C,D,V,月中，若VBC 从基于粗糙集的不同属性度量准则可见，由于数 C,POS.(D)=POSc(D)且B是相对于D是独立的，则 据的分布特点不同，不同的属性度量准则和计算方法 称B是C的相对于D的属性约简 直接影响到属性约简的结果.基于粗糙集的属性约简 1.2基于信息熵模型的属性度量 方法是一种独立于分类器的分类学习算法，它直接由 基于正区域的属性度量主要是通过数据中一致性 数据本身和属性度量准则得到，不需要任何其他先验 对象度量属性的重要性，而当数据中不一致对象较多 信息，且计算效率较高.下面将分别从信息的确定性 时该属性度量准则将不太理想，需要从信息的不确定 度量和不确定性信息分析属性度量方法的特点. 性度量来分析属性的重要性.在信息的不确定性度量
工程科学学报，第 38 卷，第 3 期 择方法［10--11］，由于无需数据以外的信息和计算效率优 势，受到大量研究者们的关注． 随着对属性约简方法 进行不断研究和探讨，研究者们力求求解出最优的属 性子集来提高分类器的分类性能，即在属性约简过程 中，求解出一组最优的属性评价准则． 针对基于粗糙 集的属性约简研究，国内外研究人员已经设计了多种 不同的属性评价准则对数据中的属性进行度量研究， 且取得一些显著成果． 根据不同的属性度量定义，不 同的属性度量准则被给出． 常见的属性度量准则有基 于正区 域 的 属 性 度 量［12］、基 于 差 别 矩 阵 的 属 性 度 量［13］以及基于信息熵的属性度量［14］． 目前，针对这 3 种单一属性度量方法，研究者们提出许多不同的属性 约简算法． 针对单一属性度量的不足，研究人员 Qian 等［15］提出基于混合优化的属性度量方法，有效提高规 则获取的效率． 目前，大多数算法主要还是使用单一 属性度量准则下评估属性的重要度． 由于高维数据中样本的分布较复杂，单一属性度 量准则往往无法准确评价属性在数据样本中的重要性 优劣． 另外，在分类器分类时，单一属性度量准则计算 出的属性约简结果可能造成分类性能和普适性的效果 不理想． 由于不同的属性度量准则往往是从不同的侧 面反映属性的重要性，它们之间存在一定的互补性， 因此可利用多准则属性度量机制对属性的重要性进行 评估． 目前已有学者借助属性融合方法实现属性的重 要性度量［16］，但其设计思路往往是在不同的属性层次 上对属性进行度量，它是一种“分层递阶”的度量方 式，即先利用某种度量方法对属性的重要性进行评价 和排序，再利用另一种属性度量方法对属性序列进行 度量． 若先前的属性度量方法不合理时，会使得后续 的属性度量方法失效，进而不能从根本上提高算法的 分类性能． 为此，本文提出一种基于混合度量方法的 属性度量机制，通过属性的信息融合方法综合了不同 度量准则的属性度量信息，该机制可广泛应用于各种 决策分析问题． 在混合属性度量机制中引入参数权 重． 在此基础上，构造一种基于粗糙集的混合属性度 量机制的集成分类器． 通过实验测试和结果分析来验 证提出机制的有效性和可行性． 结果表明该属性度量 机制比单一属性度量准则具有更高的分类精度． 1 属性度量方法 从基于粗糙集的不同属性度量准则可见，由于数 据的分布特点不同，不同的属性度量准则和计算方法 直接影响到属性约简的结果． 基于粗糙集的属性约简 方法是一种独立于分类器的分类学习算法，它直接由 数据本身和属性度量准则得到，不需要任何其他先验 信息，且计算效率较高． 下面将分别从信息的确定性 度量和不确定性信息分析属性度量方法的特点． 1. 1 基于正区域模型的属性度量 基于正区域模型的属性度量是从数据的正样本视 角对属性进行度量，主要度量数据中一致性对象对属 性的影响，是一种确定性的信息度量方法． 该方法是 由 Pawlak 和 Skowron 提出［1］，主要是通过数据中对象 的一致性来评价属性的重要性，即通过每个属性下正 区域中样本个数进行评价，以解决数据中正样本较大 且分类数较少的情况，其本质是根据属性对数据中正 样本的区分能力进行属性评估，重要的属性应能计算 出数据中更多的同类正样本，有效减少不一致样本对 分类的影响． 定义 1 五元组 S = ( U，C，D，V，f) 是一个决策表． 其中: U 为对象的非空有限集合，称为论域; C 为非空 的条件属性集合; D 为非空的决策属性集合; A = C∪D 为属性的非空有限集合; V = ∪a∈A Va，Va 表示属性 a 的值 域; f: U × A→V 是一个信息函数，即对x∈U，a∈A，有 f( x，a) ∈Va ． 定义 2 在决策表 S = ( U，C，D，V，f) 中，设 U/D = { D1，D2，…，Dk } 表示由决策属性集 D 对论域 U 的划 分，U/C = { C1，C2，…，Cm } 表示由条件属性集 C 对论 域 U 的划分，则称 C － ( Di ) = ∪{ Cj | CjDi} ( i = 1，2， …，k) 为 Di 在 U 上关于 C 的下近似集，称 C + ( Di ) = ∪{ Cj | Cj∩Di≠} ( i = 1，2，…，k) 为 Di 在 U 上关于 C 的上近似集，称 POSC ( D) = ∪Di ∈U/D C － ( Di ) 为 D 的 C 正 区域． 定义3 在决策表 S = ( U，C，D，V，f) 中，记 rC ( D) = ∑ k i = 1 | C － ( Di ) | / | U | 条件属性集 C 关于决策属性集 D 的近似质量，若 rC ( D) = 1，则称决策表为相容的，否则 称决策表不是相容的． 注: 决策表是相容的实质是由条件属性集 C 对论 域 U 的划分是由决策属性集 D 对论域 U 的划分的加 细，也就是说对任一个 Cj∈U/C，总存在一个 Di∈U/D 使得 CjDi ． 定义 4 在决策表 S = ( U，C，D，V，f) 中，Ｒ 为任意 条件属性子集，一个条件属性 a∈C － Ｒ ( ＲC) 对于 决策属性的重要度 Sig( a，Ｒ，D) 定义为 Sig( a，Ｒ，D) = rＲ∪{ a} － rＲ ． 其中 rＲ = | POSＲ ( D) | / | U| ． 定义 5 在决策表 S = ( U，C，D，V，f) 中，若B C，POSB ( D) = POSC ( D) 且 B 是相对于 D 是独立的，则 称 B 是 C 的相对于 D 的属性约简． 1. 2 基于信息熵模型的属性度量 基于正区域的属性度量主要是通过数据中一致性 对象度量属性的重要性，而当数据中不一致对象较多 时该属性度量准则将不太理想，需要从信息的不确定 性度量来分析属性的重要性． 在信息的不确定性度量 ·426·
王永生等：一种基于粗糙集属性度量的集成分类器 ·427 中基于信息熵的属性度量是一种经典的属性度量方 度上可抑制不同属性度量准则在该数据集上的各自缺 法，它最早是由科学家香农提出的信息熵定义，解决了 陷，最终做到优势互补.为此本文提出一种基于多准 数据中对不确定性信息的量化度量问题.当数据中不 则的属性度量机制，混合属性度量机制如图1所示. 致样本多时，该度量准则能有效地度量数据的不确 条件属性集 定信息量.根据不确定信息的大小来评价属性的重要 性，对信息的不确定性度量更精确。下面给基于正区 域模型度量中重要的相关知识. 权重调节因子 定义6在决策表S=(0,C,D,V,)中，可认为U 上任一属性集合（知识，等价关系簇）是定义在论域U 上的子集组成的代数上的一个随机变量，其概率分布 正区域度量 信息嫡度量 可以通过如下方法确定 C [c:p]= C, C lp(C)p(C3) …p(C)J 度量属性重要性 Dn=[0 D, D lp(D,)p(D,)…p(D)J 图1基于粗糙集的混合属性度量机制 Fig.I Hybrid measurement mechanism of attributes based on rough 其中p(C)=ICI/八U1,j=1,2,…,m;p(D)=IDI/ sets 1U川，i=1,2,…,k. 定义7在决策表S=(U,C,D,V,中，若属性子 定义10根据信息的确定性度量和不确定性度 集QCC,U/Q={X,X2,…,X},则属性子集Q对应 量，通过信息融合方法构造混合属性度量准则，可设置 的熵H(Q)为 出如下公式的属性度量准则： E(c)=an(c)+(1-a)(1-fn(c)) HQ)=- n(x)p(x) 式中，(c)表示在基于正区域的度量准则下对属性c: 定义8在决策表S=(U,C,D,V,)中，决策属性 信息度量值，f(c:）表示在基于信息熵的度量准则下 集D(U/D={D,D,…,D})相对于条件属性集 对属性c,信息度量值，α和1-α分别表示这两种不同 C(U/C={C,C2,…,C})的条件熵H(D1C)定义为 的度量准则的权重参数.下面给出该属性度量准则单 调性的证明分析. H(DIC)= 会pc)ApIc)Diep(DIC). 定理1在决策表S=(U,C,D,V,)中，对于B, 其中p(DIC,)=IDnC:I/IC,l. CB2,则属性度量准则E(B,)≤E(B,)成立. 定义9在决策表S=(U,C,D,,)中，若HBC 证明：当参数α给出确定的值，根据定义10可知， C,H(DIB)=H(DIC)且B相对于D是独立的，则称B 只需证明(B)≤(B2),且H(B,)≥fa(B2).假设 是C的相对于D的属性约简. 对于属性子集B,其对于决策表的划分U/B,={B, 本文的研究目标是设法将上述两种不同的属性度 B,…,B},对于属性子集B2,其对于决策表的划分 量方法进行信息融合，从而实现求解出更有效的属性 U/B2={B,B,,B},对于决策属性D,其对于决策 约简结果，用以提高其在数据挖掘与机器学习中的分 表的划分U/D={D,D2,,D},因为B二B2,对于任 类性能. 意的1≤i≤m,1≤j≤n,则BCB,使得POSg(D)C 2基于粗糙集的混合属性度量机制 POSg,(D),即有rB.≤rB,所以可证得p(B,)≤p(B2) 成立 通过对上述两种不同属性度量准则的分析可知， 另外，对于任意的1≤2≤k,B=(B∩D,)U(B 不同的属性度量准则各有优势，当对数据中样本的分 n(U-D),B=(BnD)U(Bn(U-D)),则有 布较复杂时，此时对于属性约简而言，可尝试引入多 准则的混合属性度量机制来综合平均属性的重要性。 H(DIB,)=- P)三DD.) 将这两种度量方法融合的理论依据是基于正区域的属 性度量主要是从对象的一致性分类对属性度量，考察 =- 含名2， IBI 属性对确定性信息的度量，基于信息熵的属性度量主 要是对象的不一致性分类对属性度量，考察属性对不 会慨客nnnU- ID.OB:I 确定性信息的度量.为了更好地能够综合利用各种属 ID.∩Bl 性度量准则，可引入参数权重调节因子，进而从一定程 g1(gnD)1+1(En(0-D,)T
王永生等: 一种基于粗糙集属性度量的集成分类器 中基于信息熵的属性度量是一种经典的属性度量方 法，它最早是由科学家香农提出的信息熵定义，解决了 数据中对不确定性信息的量化度量问题． 当数据中不 一致样本多时，该度量准则能有效地度量数据的不确 定信息量． 根据不确定信息的大小来评价属性的重要 性，对信息的不确定性度量更精确． 下面给基于正区 域模型度量中重要的相关知识． 定义 6 在决策表 S = ( U，C，D，V，f) 中，可认为 U 上任一属性集合( 知识，等价关系簇) 是定义在论域 U 上的子集组成的代数上的一个随机变量，其概率分布 可以通过如下方法确定． ［C: p］= C1 C2 … Cm p( C1 ) p( C2 ) … p( Cm [ ] ) ， ［D: p］= D1 D2 … Dk p( D1 ) p( D2 ) … p( Dk [ ] ) ． 其中 p( Cj ) = | Cj | / | U | ，j = 1，2，…，m; p( Di ) = | Di | / | U| ，i = 1，2，…，k． 定义 7 在决策表 S = ( U，C，D，V，f) 中，若属性子 集 QC，U/Q = { X1，X2，…，Xv } ，则属性子集 Q 对应 的熵 H( Q) 为 H( Q) = － ∑ v i = 1 p( Xi ) lg p( Xi ) ． 定义 8 在决策表 S = ( U，C，D，V，f) 中，决策属性 集 D ( U/D = { D1，D2，…，Dk } ) 相 对 于 条 件 属 性 集 C ( U/C = { C1，C2，…，Cm } ) 的条件熵 H( D| C) 定义为 H( D| C) = － ∑ m i = 1 p( Ci ) ∑ k j = 1 p( Dj | Ci ) lg p( Dj | Ci ) ． 其中 p( Dj | Ci ) = | Dj∩Ci | / | Ci | ． 定义 9 在决策表 S = ( U，C，D，V，f) 中，若B C，H( D| B) = H( D| C) 且 B 相对于 D 是独立的，则称 B 是 C 的相对于 D 的属性约简． 本文的研究目标是设法将上述两种不同的属性度 量方法进行信息融合，从而实现求解出更有效的属性 约简结果，用以提高其在数据挖掘与机器学习中的分 类性能． 2 基于粗糙集的混合属性度量机制 通过对上述两种不同属性度量准则的分析可知， 不同的属性度量准则各有优势，当对数据中样本的分 布较复杂时，此时对于属性约简而言，可尝试引入多 准则的混合属性度量机制来综合平均属性的重要性． 将这两种度量方法融合的理论依据是基于正区域的属 性度量主要是从对象的一致性分类对属性度量，考察 属性对确定性信息的度量，基于信息熵的属性度量主 要是对象的不一致性分类对属性度量，考察属性对不 确定性信息的度量． 为了更好地能够综合利用各种属 性度量准则，可引入参数权重调节因子，进而从一定程 度上可抑制不同属性度量准则在该数据集上的各自缺 陷，最终做到优势互补． 为此本文提出一种基于多准 则的属性度量机制，混合属性度量机制如图 1 所示． 图 1 基于粗糙集的混合属性度量机制 Fig． 1 Hybrid measurement mechanism of attributes based on rough sets 定义 10 根据信息的确定性度量和不确定性度 量，通过信息融合方法构造混合属性度量准则，可设置 出如下公式的属性度量准则: E( ci ) = αfP ( ci ) + ( 1 － α) ( 1 － fH ( ci ) ) ． 式中，fP ( ci ) 表示在基于正区域的度量准则下对属性 ci 信息度量值，fH ( ci ) 表示在基于信息熵的度量准则下 对属性 ci 信息度量值，α 和 1 － α 分别表示这两种不同 的度量准则的权重参数． 下面给出该属性度量准则单 调性的证明分析． 定理 1 在决策表 S = ( U，C，D，V，f) 中，对于 B1 B2，则属性度量准则 E( B1 ) ≤E( B2 ) 成立． 证明: 当参数 α 给出确定的值，根据定义 10 可知， 只需证明 fP ( B1 ) ≤fP ( B2 ) ，且 fH ( B1 ) ≥fH ( B2 ) ． 假设 对于属性子集 B1，其对于决策表的划分 U/B1 = { B1 1， B2 1，…，Bm 1 } ，对于属性子集 B2，其对于决策表的划分 U/B2 = { B1 2，B2 2，…，Bm 2 } ，对于决策属性 D，其对于决策 表的划分 U/D = { D1，D2，…，Dk } ，因为 B1B2，对于任 意的 1≤i≤m，1≤j≤n，则 Bi 1Bj 2，使得 POSB1 ( D) POSB2 ( D) ，即有 rB1 ≤rB2 ，所以可证得 fP ( B1 ) ≤fP ( B2 ) 成立． 另外，对于任意的 1≤z≤k，Bi 1 = ( Bi 1 ∩Dz ) ∪( Bi 1 ∩( U － Dz ) ) ，Bj 2 = ( Bj 2∩Dz ) ∪( Bj 2∩( U － Dz ) ) ，则有 H( D|B1 ) = － ∑ m i = 1 P( Bi 1 ) ∑ k z = 1 P( Dz |Bi 1 ) lg P( Dz |Bi 1 ) = － ∑ m i = 1 | Bi 1 | | U| ∑ k z = 1 | Dz∩Bi 1 | | Bi 1 | lg | Dz∩Bi 1 | | Bi 1 | = － ∑ m i = 1 | Bi 1 | | U| ∑ k z = 1 | Dz∩Bi 1 | | ( Bi 1∩Dz ) | + | Bi 1∩( U － Dz ) | · lg | Dz∩Bi 1 | | ( Bi 1∩Dz ) | + | ( Bi 1∩( U － Dz ) | ． ·427·
·428· 工程科学学报，第38卷，第3期 对于属性子集B2,同理可知 通过信息融合和先验知识来设置调节不同的权重参 数，改变不同的参数组合，利用算法1可获得多个不 H(DIB,)=- ∑P()∑P(D.IB)gP(D.IB)= 同的属性约简结果，由于基于混合属性度量机制下 的属性约简，在考虑分类能力的前提下，较好地综合 三™名nPn0-T ID.OBI 了单一属性度量准则的优势.直观分析上，当多个约 简结果的差异性越大时，用它们构建集成分类器时 ID.∩B,I 产生的互补信息将越多，集成分类器的分类精度就 1(BD)1+1(B(U-D)I 越高.在集成分类器上可以利用投票原则将不同约 又因为1BI≤IBI,所以有IB,nDI≤IB∩D.I且I 简求得的分类结果进行表决，最终利用多个约简结 n(U-D.)I≤1Bn(U-D.)I成立，因此可得H(DI 果之间互补信息达到组合分类的目的.图2为基于 B)≥H(DIB2),即有f(B)≥f(B2). 粗糙集属性度量的集成分类器流程图： 综述所示可得证：属性度量准则E(B)≤E(B2) 决策表S=(U,CD.Vf) 成立，证毕. 数据集 通过上述证明可知，所提出的属性度量准则满足 单调性.这为评估属性的重要性提供理论基础. 定义11对属性重要性计算采用渐进式判定方 约简 法，可采用如下公式计算在属性子集B下，当加入属 性c,时信息的变化量（属性的重要程度）： C- 分类器 Sig(e;,B,D)=E(e,}UB)-E(B). 在基于混合属性度量机制中，可根据数据中样本 集成投票 投票原则 的分布情况，通过不断调节权重因子参数，分别对基于 正区域和信息熵的属性度量准则设置相应的权重参 数.由此可见，基于混合性度量机制可从不同的度量 分类精度 分类结果 视角对属性进行综合分析，通过构造的度量机制公式 获得不同的特征约简结果.下面给出基于混合性度量 图2集成分类器的流程图 Fig.2 Flow chart of the ensemble classifier 机制的属性约简算法 算法1基于混合属性度量准则的属性约简 下面给出图2中对应的基于混合属性度量机制的 算法. 集成分类器算法. 输入：决策表S=(U,C,D,V,),权重因子参数 算法2基于混合属性度量机制的集成分类器 0≤a≤1： 算法 输出：属性约简结果Red. 输入：决策表S=(U,C,D,V,),不同的权重因子 Stepl Red=☑：/初始化 参数a,(a,∈D,1],1≤i≤n),每次变化0.05 Step2对Hc:∈C,根据定义l0分别计算每个属 输出：数据的分类精度： 性的信息度量值E(c); Stepl利用算法1计算不同权重因子参数a,(1 Step3根据属性度量值E(c,),选择最大的属性 ≤i≤n)下，得到不同的属性约简结果（R,R2,…, c并入属性约简结果Red中，即有Red=RedU{c,}; Rn-1Rn）; Step4根据定义ll,对于Hc.∈C-{c,},计算 Step2利用属性约简结果(R,R2,…,R.-1,R）, Sig(c,Red,D),并选择最大的属性c,其中Sig(c, 计算其在数据中分类目标，得到分类结果为(C,C2, Red,D)=maxSig(c.,Red,D),Red Reduic,} …,C-1Cn）: Step3根据多数投票原则得到对象的最终分类 Step5如果属性度量准则E({c,}URed)> 精度： E(Red),则转至Step4,否则转至Step6: Step4计算总分类精度，算法结束. Step6输出属性约简结果Red,算法结束： 从图2中集成分类器算法可以看出，基于混合属 3基于粗糙集属性度量的集成分类器 性度量机制的集成分类器算法利用并行计算方法，从 而由单次约简和分类的时间即可得到最终结果，可使 根据提出的基于粗糙集的混合属性度量机制， 得算法2的计算复杂度大大降低
工程科学学报，第 38 卷，第 3 期 对于属性子集 B2，同理可知 H( D|B2 ) = － ∑ n j = 1 P( Bj 2 ) ∑ k z = 1 P( Dz |Bj 2 ) lg P( Dz |Bj 2 ) = － ∑ m j = 1 | Bj 2 | | U| ∑ k z = 1 | Dz∩Bj 2 | | ( Bj 2∩Dz ) | + | Bj 2∩( U － Dz ) | · lg | Dz∩Bj 2 | | ( Bj 2∩Dz ) | + | ( Bj 2∩( U － Dz ) | ． 又因为| Bj 2 | ≤| Bi 1 | ，所以有| Bj 2∩Dz | ≤ | Bi 1∩Dz | 且 | Bj 2 ∩( U － Dz ) | ≤| Bi 1∩( U － Dz ) | 成立，因此可得 H( D | B1 ) ≥H( D| B2 ) ，即有 fH ( B1 ) ≥fH ( B2 ) ． 综述所示可得证: 属性度量准则 E( B1 ) ≤E( B2 ) 成立，证毕． 通过上述证明可知，所提出的属性度量准则满足 单调性． 这为评估属性的重要性提供理论基础． 定义 11 对属性重要性计算采用渐进式判定方 法，可采用如下公式计算在属性子集 B 下，当加入属 性 ci 时信息的变化量( 属性的重要程度) : Sig( ci，B，D) = E( { ci} ∪B) － E( B) ． 在基于混合属性度量机制中，可根据数据中样本 的分布情况，通过不断调节权重因子参数，分别对基于 正区域和信息熵的属性度量准则设置相应的权重参 数． 由此可见，基于混合性度量机制可从不同的度量 视角对属性进行综合分析，通过构造的度量机制公式 获得不同的特征约简结果． 下面给出基于混合性度量 机制的属性约简算法． 算法 1 基于混合属性度量准则的属性约简 算法． 输入: 决策表 S = ( U，C，D，V，f) ，权重因子参数 0≤α≤1; 输出: 属性约简结果 Ｒed． Step1 Ｒed = ; / /初始化 Step2 对ci∈C，根据定义 10 分别计算每个属 性的信息度量值 E( ci ) ; Step3 根据属性度量值 E( ci ) ，选择最大的属性 cj 并入属性约简结果 Ｒed 中，即有 Ｒed = Ｒed∪{ ci} ; Step4 根据定义 11，对 于ck ∈C － { cj} ，计 算 Sig( ck，Ｒed，D) ，并选择最大的 属 性 cv，其 中 Sig ( cv， Ｒed，D) = max cw∈C Sig( cw，Ｒed，D) ，Ｒed = Ｒed∪{ cv} ; Step5 如 果 属 性 度 量 准 则 E ( { cv } ∪ Ｒed ) ＞ E( Ｒed) ，则转至 Step4，否则转至 Step6; Step6 输出属性约简结果 Ｒed，算法结束; 3 基于粗糙集属性度量的集成分类器 根据提出的基于粗糙集的混合属 性 度 量 机 制， 通过信息融合和先验知识来设置调节不同的权重参 数，改变不同的参数组合，利用算法 1 可获得多个不 同的属性约简结果，由于基于混合属性度量机制下 的属性约简，在考虑分类能力的前提下，较好地综合 了单一属性度量准则的优势． 直观分析上，当多个约 简结果的差异性越大时，用它们构建集成分类器时 产生的互补信息将越多，集成分类器的分类精度就 越高． 在集成分类器上可以利用投票原则将不同约 简求得的分类结果进行表决，最终利用多个约简结 果之间互补信息达到组合分类的目的． 图 2 为基于 粗糙集属性度量的集成分类器流程图: 图 2 集成分类器的流程图 Fig． 2 Flow chart of the ensemble classifier 下面给出图 2 中对应的基于混合属性度量机制的 集成分类器算法． 算法 2 基于混合属性度量机制的集成分类器 算法． 输入: 决策表 S = ( U，C，D，V，f) ，不同的权重因子 参数 αi ( αi∈［0，1］，1≤i≤n) ，每次变化 0. 05; 输出: 数据的分类精度; Step1 利用算法 1 计算不同权重因子参数 αi ( 1 ≤i≤n) 下，得 到 不 同 的 属 性 约 简 结 果 ( Ｒ1，Ｒ2，…， Ｒn － 1，Ｒn ) ; Step2 利用属性约简结果( Ｒ1，Ｒ2，…，Ｒn － 1，Ｒn ) ， 计算其在数据中分类目标，得到分类结果为( C1，C2， …，Cn － 1，Cn ) ; Step3 根据多数投票原则得到对象的最终分类 精度; Step4 计算总分类精度，算法结束． 从图 2 中集成分类器算法可以看出，基于混合属 性度量机制的集成分类器算法利用并行计算方法，从 而由单次约简和分类的时间即可得到最终结果，可使 得算法 2 的计算复杂度大大降低． ·428·
王水生等：一种基于粗糙集属性度量的集成分类器 ·429 表24类不同算法的属性约简结果比较 4实验比较和性能分析 Table 2 Attribute reduction results of four different algorithms 为了验证本文集成分类器的有效性和可行性，将 数据集 本文的算法算法PAR算法DAR算法IAR 本文的约简算法与文献07-19]中属性约简算法在属 Wdbe 5.5 6.0 7.0 6.0 性约简结果和分类精度上进行实验比较和性能分析， Vehicle 12.6 14.0 13.0 10.0 并把文献7-19]中算法分别记为算法PAR(基于正 Liver disorder 11.4 12.0 14.0 11.0 区域的属性度量)、算法DAR(基于区分性的属性度 Waveform 8.7 10.0 10.0 7.0 量)和算法IAR(基于信息熵的属性度量).数据集来 Chess 5.2 5.0 6.0 6.0 自UCI机器学习数据库中的真实数据集，数据集情况 Mushroom 4.3 4.0 5.0 4.0 如表1所示.其中，属性约简算法的运行环境为Core 平均长度 7.95 8.50 9.16 7.33 (TM)Duo CPU P8700,2.53GHz,RAM4G,采用C++ 语言编程实现 实现了对数据进行降维的目的.基于信息熵的属性约 表1UCI数据集情况 简算法IAR进行降维后的属性维度相对较低，其算法 Table 1 Description of UCI Data sets 可能约简了部分重要属性，从而将丢失部分重要属性 数据集 对象数 条件属性数 决策属性数 信息，其算法的分类性能将受影响。基于正区域的属 Wdbe 569 31 2 性约简算法PAR从样本的一致性角度对属性进行度 Vehicle 846 出 4 量，算法在一致性数据集约简效果较好，如数据集 Liver disorder 1260 6 3 Wdbc和Mushroom就验证了这一点，这2个数据集中 一致性对象较多，特别是Mushroom数据集不存在不一 Waveform 5000 21 3 2 致性样本.基于区分性的属性约简算法DAR在不同 Chess 3196 36 数据集上平均属性约简结果的长度最大，因为其约简 Mushroom 8124 22 2 结果含有一定的冗余属性，即DAR算法的属性约简结 为便于实验的计算和分析，对于离散型数据，采用 果往往是不完备的 基于距离的离散化算法对连续型数据做离散化处理. 为了进一步验证集成分类器的分类精度和泛化能 集成分类器的选取20组权重参数（权重参数初始值为 力，采用十折交叉验证的方式对这4类约简算法的属 0,每次变化值0.05)用于计算属性约简结果，最后求 性约简结果在C4.5分类器进行分类测试，来评价算法 解其平均约简长度.表2中给出4类算法的属性约简 的约简质量.表3显示这4类算法的分类精度的结果比 结果比较 较.另外，为分析混合属性度量方法的优势，以数据集 从表2中可以看出，4类不同的属性约简算法都 Wdbc和Liver disorder为例进行性能分析，如图3所示. 表34类不同算法的分类精度结果比较 Table 3 Classification performance results of four different algorithms 数据集 本文的方法 算法PAR 算法DAR 算法IAR Wdbe 89.16±1.53 86.41±1.06 83.85±2.53 81.75±2.23 Vehicle 81.70±2.35 82.05±2.51 78.94±2.11 78.94±2.61 Liver disorder 76.25±2.98 75.38±2.06 74.37±3.14 72.14±3.15 Waveform 89.42±3.13 89.50±2.84 89.80±2.76 86.56±2.70 Chess 82.96±1.59 80.97±1.95 81.38±2.61 80.34±2.66 Mushroom 100.0±0.00 100.0±0.0 99.37±0.75 98.91±0.32 平均精度 86.58 85.72 84.61 83.11 从表3中可以看出，本文所提出的集成分类器方 同度量准则的侧重点，使得约简结果中属性存在互补 法整体性能要好于其他3类算法.算法DAR求解属 性，每次能选出重要的属性作为候选属性，有效提高了 性约简结果中由于存在冗余属性在一定程度上影响分 集成分类器的分类精度.综述分析可知本文属性约简 类性能.算法AR虽然约简结果中个数较少，但是以 算法通过设置多种组合参数构造了基于粗糙集的属性 牺牲分类能力为代价，从而导致分类精度较低.本文 度量集成分类器，使得约简结果具有互补性和差异性， 的多准则混合属性度量下的属性约简由于充分考虑不 是一种相对有效的数据分类算法
王永生等: 一种基于粗糙集属性度量的集成分类器 4 实验比较和性能分析 为了验证本文集成分类器的有效性和可行性，将 本文的约简算法与文献［17--19］中属性约简算法在属 性约简结果和分类精度上进行实验比较和性能分析， 并把文献［17--19］中算法分别记为算法 PAＲ ( 基于正 区域的属性度量) 、算法 DAＲ ( 基于区分性的属性度 量) 和算法 IAＲ( 基于信息熵的属性度量) ． 数据集来 自 UCI 机器学习数据库中的真实数据集，数据集情况 如表 1 所示． 其中，属性约简算法的运行环境为 Core ( TM) Duo CPU P8700，2. 53 GHz，ＲAM 4G，采用 C + + 语言编程实现． 表 1 UCI 数据集情况 Table 1 Description of UCI Data sets 数据集 对象数 条件属性数 决策属性数 Wdbc 569 31 2 Vehicle 846 18 4 Liver disorder 1260 6 3 Waveform 5000 21 3 Chess 3196 36 2 Mushroom 8124 22 2 为便于实验的计算和分析，对于离散型数据，采用 基于距离的离散化算法对连续型数据做离散化处理． 集成分类器的选取 20 组权重参数( 权重参数初始值为 0，每次变化值 0. 05) 用于计算属性约简结果，最后求 解其平均约简长度． 表 2 中给出 4 类算法的属性约简 结果比较． 从表 2 中可以看出，4 类不同的属性约简算法都 表 2 4 类不同算法的属性约简结果比较 Table 2 Attribute reduction results of four different algorithms 数据集 本文的算法 算法 PAＲ 算法 DAＲ 算法 IAＲ Wdbc 5. 5 6. 0 7. 0 6. 0 Vehicle 12. 6 14. 0 13. 0 10. 0 Liver disorder 11. 4 12. 0 14. 0 11. 0 Waveform 8. 7 10. 0 10. 0 7. 0 Chess 5. 2 5. 0 6. 0 6. 0 Mushroom 4. 3 4. 0 5. 0 4. 0 平均长度 7. 95 8. 50 9. 16 7. 33 实现了对数据进行降维的目的． 基于信息熵的属性约 简算法 IAＲ 进行降维后的属性维度相对较低，其算法 可能约简了部分重要属性，从而将丢失部分重要属性 信息，其算法的分类性能将受影响． 基于正区域的属 性约简算法 PAＲ 从样本的一致性角度对属性进行度 量，算法 在 一 致 性 数 据 集 约 简 效 果 较 好，如 数 据 集 Wdbc和 Mushroom 就验证了这一点，这 2 个数据集中 一致性对象较多，特别是 Mushroom 数据集不存在不一 致性样本． 基于区分性的属性约简算法 DAＲ 在不同 数据集上平均属性约简结果的长度最大，因为其约简 结果含有一定的冗余属性，即 DAＲ 算法的属性约简结 果往往是不完备的． 为了进一步验证集成分类器的分类精度和泛化能 力，采用十折交叉验证的方式对这 4 类约简算法的属 性约简结果在 C4. 5 分类器进行分类测试，来评价算法 的约简质量． 表3 显示这4 类算法的分类精度的结果比 较． 另外，为分析混合属性度量方法的优势，以数据集 Wdbc 和 Liver disorder 为例进行性能分析，如图3 所示． 表 3 4 类不同算法的分类精度结果比较 Table 3 Classification performance results of four different algorithms 数据集 本文的方法 算法 PAＲ 算法 DAＲ 算法 IAＲ Wdbc 89. 16 ± 1. 53 86. 41 ± 1. 06 83. 85 ± 2. 53 81. 75 ± 2. 23 Vehicle 81. 70 ± 2. 35 82. 05 ± 2. 51 78. 94 ± 2. 11 78. 94 ± 2. 61 Liver disorder 76. 25 ± 2. 98 75. 38 ± 2. 06 74. 37 ± 3. 14 72. 14 ± 3. 15 Waveform 89. 42 ± 3. 13 89. 50 ± 2. 84 89. 80 ± 2. 76 86. 56 ± 2. 70 Chess 82. 96 ± 1. 59 80. 97 ± 1. 95 81. 38 ± 2. 61 80. 34 ± 2. 66 Mushroom 100. 0 ± 0. 00 100. 0 ± 0. 0 99. 37 ± 0. 75 98. 91 ± 0. 32 平均精度 86. 58 85. 72 84. 61 83. 11 从表 3 中可以看出，本文所提出的集成分类器方 法整体性能要好于其他 3 类算法． 算法 DAＲ 求解属 性约简结果中由于存在冗余属性在一定程度上影响分 类性能． 算法 IAＲ 虽然约简结果中个数较少，但是以 牺牲分类能力为代价，从而导致分类精度较低． 本文 的多准则混合属性度量下的属性约简由于充分考虑不 同度量准则的侧重点，使得约简结果中属性存在互补 性，每次能选出重要的属性作为候选属性，有效提高了 集成分类器的分类精度． 综述分析可知本文属性约简 算法通过设置多种组合参数构造了基于粗糙集的属性 度量集成分类器，使得约简结果具有互补性和差异性， 是一种相对有效的数据分类算法． ·429·