一种改进的启发式最优相对属性约简算法

陶加云，李英顺，赵玉鑫

（1.沈阳工业大学信息科学与工程学院，辽宁沈阳110870；2.沈阳工业大学化工过程自动化学院，辽宁辽阳111003）

一种改进的启发式最优相对属性约简算法

陶加云1，李英顺2，赵玉鑫2

（1.沈阳工业大学信息科学与工程学院，辽宁沈阳110870；2.沈阳工业大学化工过程自动化学院，辽宁辽阳111003）

针对在传统的粗糙集理论相对属性约简算法中因需计算可区别矩阵和正区域而导致的约简效率低下这一问题，提出一种改进的启发式最优相对属性约简算法加以解决.通过引入属性集的相对分类能力的定义给出相对属性约简的判定条件，在此基础上导出的改进相对属性约简算法既能保证约简过后的条件属性是最优的，又能提高约简效率.实际算例结果以及对比实验体现了该算法的高效性.

粗糙集理论；改进最优相对属性约简；判定条件

粗糙集理论诞生于20世纪80年代初期，是一种能有效分析和处理不精确、不完整信息的数据分析工具[1].该理论在近十多年来日益受到国内外专家学者的重视，对其研究也在不断加深，并且已经成功运用在机器学习、人工智能与知识工程、故障诊断、信息系统决策支持等领域[2-4].约简是粗糙集理论的核心内容之一，是粗糙集理论能否成功运用到工程实践中的关键，其主要内容是在保持知识库分类能力不变的前提下导出决策规则.对决策系统属性集的约简称为属性约简，而寻求到所有约简后的属性已被证明是一个NP-hard问题[5].

高效的属性约简算法是粗糙集理论完成数据约简的基础和保障.文献[6]利用传统的基于可区别矩阵的相对属性约简算法对综合传动装置的故障数据进行约简，算例的结果中出现了两个约简值，虽然都能导出决策规则，但是可信度却受到影响，并且计算量大.文献[7]提出了一种改进的基于属性频率度的约简算法，该算法使得约简的计算量有所减少，但是不能保证求得的约简后的属性个数是最少的.在实际运用中所需要属性个数往往是越少越好，且计算量越小越好，这样便于得到精简的规则集，从而提高解决问题的效率.因此，文章通过引入属性集的相对分类能力的定义来给出相对属性约简的判定条件，在此基础上定义属性重要度，并将它作为改进的最优相对属性约简算法的启发式信息，以便于减小搜索空间，提高相对属性约简效率.实际算例结果证实了该算法不仅高效，而且能够保证约简后的属性个数是最少、最优的.

1 粗糙集基础理论

定义1 设四元组信息表达系统其中U代表包含所有对象的非空有限集，被称为论域；R代表属性集，R=( ) r1,r2,r3,…,rm= C⋃D,C⋂D≠∅,C代表条件属性集，U代表决策属性集；V=⋃r∈RVr，Vr代表属性r的值域；f∶U×R→V为一全函数，它赋予每一对象对应的每一属性一个信息值.此时，称上述信息表达系统S为决策表.

定义2设信息表达系统A为属性集R的一个子集，亦即A⊆R,定义一不可分辨关系ind(A),且：

定义3设S中的集合U上任意一个不可分辨关系和任意一个子集X,定义X关于Q的下、上近似集分别为：

定义4设P和T为定义在论域U上的两个等价关系簇，T的P正域记为POSP(T)，此时，

定义5设Ω和Θ为定义在论域U上的两个等价关系簇，设G⊆Ω,G为Ω的Θ约简当且仅当G为 Ω的 Θ独立子簇，并且满足 POSG(Θ)= POSΩ(Θ)时，就称Ω的Θ约简为相对约简.

2 基于粗糙集理论的改进最优相对属性约简算法

2.1 属性集相对分类能力的引入

粗糙集理论是在等价关系的基础上建立的，这些等价关系[8]对特定的数据空间进行划分.划分准则可以看作一种粗糙的知识，知识的粒度越大越粗糙，可用度相对而言也就越小，反之就越大.以下就等价关系分类能力这一观点，给出定义等价关系相对分类能力的表达方式.

定义6给定一相容决策系统，则条件属性集C相对于决策属性集D的分类能力记为M(U,C/D),且

性质1：给定相容决策系统∀R⊆C,则POSC(U,D)=POSR(U,D)成立的充要条件为

设R⊆C,r∈R,结合上述定义6及其性质可推导出属性集R是条件属性集C关于决策属性集D的一个相对约简的充要条件是：

由上述性质可得：

POSC(U,D)=POSR-{r}(U,D)

这与R是条件属性集C关于决策属性集D的一个约简矛盾.因此，得证：对于∀r∈R,有：

POSC(U,D)=POSR(U,D)

上述证明的充要条件即为相对属性约简的判定条件，是最优属性约简算法的基础.

2.2 改进最优属性约简算法描述

在传统的启发式相对属性约简算法的基础上引入了相对分类能力和属性重要度的定义，既可在一定的程度上减小计算量，又能保证约简过后的属性集是最精简的.算法的主要内容如下：

输出：相容决策系统DS的一个最优相对属性约简集.

对算法中出现的部分符号的说明：

（Ⅰ）Red：算法的输出结果；

（Ⅱ） Div||Red：论域U的划分，亦即

（Ⅲ）Div：论域U的划分；

（Ⅳ）SGF(a,S,D)：属性重要度.

步骤3：设属性a∈S,S为C中的某一属性集，S⊆C, U1=U，将a按SGF(a,S,D)升序排列，并将排列结果记为

步骤4：Fork=1;k＜|c|+1;k++；

步骤5：令Div={U1}，其中U1=U；

步骤6：对于属性集Red,从后往前对每个属性a进行判断，看它们是否可省，具体说明如下：

步骤7：输出最终的Red.

2.3 算法的时间复杂度分析

首先给出并证明如下性质：

证明：任意的且∀x,y∈P,有f(x ,S⋃T)=f(y ,S⋃T),因此又有 f(x,S)= f(y,S)和 f(x,T)=f(y,T),即存在 Si⋂Tj使得P⊆Si⋂Tj.又知，有 f(x,Si⋃Tj)=f(y,Si⋃Tj),因此可得出P=Si⋂Tj.同理，对于任意的Si⋂Tj,存在使得 Si⋂Tj=P.综上可得证

由上述改进最优属性约简算法可知，其步骤1-5的时间复杂度为O(|C ||U|2)，又由如上性质可以求得步骤6的时间复杂度为O(|C ||U|2)，因此，改进最优相对属性约简算法的总的时间复杂度为：

O(|C ||U|2).

3 实验结果及分析

本文以客户关系管理情况评价表的相关数据为例来对算法进行分析.选择30个比较典型的评价数据来作为样本数据，建立如表1所示的客户评价数据表.其中，条件属性C={c1,c2,c3,c4,c5}={产品能力认知，管理水平评价，服务质量，客户情感，责任感表现} ，决策属性D为客户满意度.条件属性值1-5分别代表“差”“一般”“好”“很好”“最好”，决策属性值A-C分别代表“高”“较高”和“一般”.

表1 客户评价数据表

选用机器学习数据库中的客户评价数据集，分别利用改进最优相对属性约简算法和传统的启发式相对属性约简算法对表1中的数据进行了25次实验，本文所提算法的约简结果如表2所示.

表2 文章所提算法的约简结果

传统的启发式相对属性约简结果如表3所示.

表3 传统的启发式相对属性约简结果

实验结果比较情况如表4所示.

表4 实验结果比较情况

从表4中的数据可以明显看出，采用改进最优相对属性约简算法比统的启发式相对属性约简算法在快4.7s的同时，约简集较之也减少了一个.

结果分析：由表2可以更直观地看出“服务质量”和“客服情感”都对“客户满意度”有重大影响，两者不可或缺，因此，这已是最精简的最优属性集.通过表2能够更快地完成数据分析，表明企业需要把“服务质量”和“客服情感”放在重要地位，体现了该算法在决策信息系统上的优点和适用性.由表3可以看出，传统的启发式相对属性约简算法得到的约简集中含有“产品认知能力”这一属性，然而从数据可以看出，该属性并不对客户满意度产生多少影响，换句话说，得到的相对属性约简集不是最优的.由表4可以看出，本文所提算法能够保证约简效率高于传统算法，体现了该算法约简效率高的优点.

4 结语

为保证相对属性约简的最优性和高效性，在导出相对属性约简判定条件的基础上定义了属性重要度，提出了一种启发式最优相对属性约简算法.该算法克服了传统的相对属性约简算法需要计算可区别矩阵、正区域以及析取合取计算量大的问题.实验证明，算法能够在相对较小的时间内完成相对属性约简，挖掘出有效信息，从而更好地反映知识表达系统的特性.

[1]PAWLAKZ.Roughsets[J].InternationalJournalofComputerand InformationSciences,1982,11（11）:341-356.

[2]裴小兵.粗糙集的知识约简研究[D].武汉：华中科技大学，2006. [3]成新文，陈国超，李琦.关于粗糙集的理论及应用研究[J].煤炭技术，2010（10）:198-200.

[4]WONGSKM,ZIARKOW.Onoptimaldecisionrulesindecision table[J].BulletinofPolishAcademyofSciences,1985,33（11-12）: 693-696.

[5]柳炽伟，景玉军，郭美华.基于故障树的DCT故障诊断专家系统的研究[J].机床与液压，2014,42（1）:169-172.

[6]李英顺，姜双双，佟维妍，等.基于RST及FTA的综合传动装置故障诊断专家系统的应用研究[J].组合机床与自动化加工技术，2014（4）:60-63.

[7]夏侯振宇，段隆振，衷尔英，等.一种改进的粗糙集约简算法及其应用[J].江西科学，2008,26（3）:379-382.

[8]李玉龙，张亚光，毕聪聪.一种基于改进遗传算法的粗糙集属性约简算法[J].计算机与数字工程，2014（10）:1831-1834.

【编校：王露】

AnImprovedHeuristicOptimalRelativeAttributeReductionAlgorithm

TAOJiayun1,LIYingshun2,ZHAOYuxin2
（1.SchoolofInformationScienceandEngineering,ShenyangUniversityofTechnology,Shenyang,Liaoning110870,China;2.School ofChemicalProcessandAutomation,ShenyangUniversityofTechnology,Liaoyang,Liaoning111003,China）

Animprovedheuristicoptimalrelativeattributereductionalgorithmwasputforwardtosolvetheproblem whichhadlowreductionefficiencycausedbytheneedofcalculatedistinguishablematrixandpositiveregionintherela⁃tiveattributereductionalgorithmbasedonroughsettheory.Thedecisiveconditionofrelativeattributereductionwasgiv⁃enbyintroducingthedefinitionofrelativeclassificationabilityinattributeset.Theimprovedrelativeattributereduction algorithmofwhichwasexportedbythemethodasabovenotonlycanguaranteetheconditionalattributesarebest,butal⁃socanimprovethereductionefficiency.Theresultsofthepracticalexamplesandthecomparisonexperimentsshowhigh efficiencyofthisalgorithm.

roughsettheory;improvedoptimalrelativeattributereduction;decisivecondition

TP18

A

1671-5365(2015)12-0032-04

陶加云，李英顺，赵玉鑫.一种改进的启发式最优相对属性约简算法[J].宜宾学院学报,2015,15(12):32-35. TAOJY,LIYS,ZHAOYX.AnImprovedHeuristicOptimalRelativeAttributeReductionAlgorithm[J].JournalofYibinUniver⁃sity,2015,15(12):32-35.

2015-07-15修回：2015-08-19

辽宁省自然科学基金项目（2014020115）；辽宁省教育厅科学技术研究项目（L2012031）

陶加云（1991-），男，硕士研究生，研究方向为人工智能与数据挖掘

时间：2015-08-2021:37

http://www.cnki.net/kcms/detail/51.1630.z.20150820.2137.001.html