综合属性选择和删除的属性约简方法

杨成东，邓廷权

(1.临沂大学信息学院，山东临沂 276005;2.哈尔滨工程大学理学院，黑龙江 哈尔滨 150001)

属性约简利用粗糙集［1-2］等理论，旨在保持信息系统决策能力不变的条件下，去除冗余属性，从而减少数据的冗余度，是机器学习和人工智能最重要的研究方向之一.属性约简方法有很多，譬如基于依赖度的属性约简方法［3］、基于互信息的属性约简方法［4-5］、基于模糊粗糙集的属性约简方法［6-8］等.Skowron于1992年提出了辨识矩阵和辨识函数的概念［9］，利用辨识矩阵和辨识函数实现了属性约简，并得到了广泛的研究［10］.然而，基于辨识矩阵的属性约简方法，存在不能得到约简的可能性，仍具有冗余性.

1 基础知识

给定决策系统 S=(U，C∩D，V，f)，其辨识矩阵定义为

式中:M(x，y)定义为

显然，矩阵M中元素M(x，y)是由处于不同决策类中的对象x和y属性值不同的属性组成.

辨识函数f(M)定义为

式中:∨和∧是2个基本的二值逻辑运算:析取和合取.辨识函数是一个布尔表达式，通过等价的逻辑计算，将其化成若干个小合取式的析取式，那么每个小合取式就是一个约简.一般地，约简不是惟一的，决策系统的所有约简用REDC(D)表示.

辨识矩阵和辨识函数有如下性质:

1)核是辨识矩阵中所有单个元素组成的集合;

2)辨识函数f(M)的极小析取范式中的所有合取式是属性集C的所有约简.

辨识矩阵和辨识函数方法能够求出所有约简，因此具有十分重要的理论意义.然而利用该方法求出的所有约简仍是一个NP-hard问题，特别是在大规模数据集中几乎无法求出约简，其速度非常慢，而实际中通常只需要一个约简.

2 辨识矩阵属性约简方法及其缺点

作为经典辨识矩阵算法，基于属性频率的辨识矩阵快速属性约简算法利用频率作为衡量属性重要程度的依据，具有重要的实用价值.在辨识矩阵中出现频率最高的属性是较为重要的，优先选择该属性.基于辨识矩阵属性频率的快速属性约简算法如下:

算法1 基于辨识矩阵属性频率的属性约简算法:

该算法中的时间复杂度分为关键2步:一是对属性进行选择有2个循环，时间复杂度为O(|C|2);另一个是计算单个属性的频率，时间复杂度为O(|U|).因此总的时间复杂度为:O(|U||C|2).

例1 给定关于大豆质量的决策系统S=(U，C∪D，V，f)如表1，其中 C={a，b，c，d，e}是条件属性，D是决策属性.

表1 决策系统Table 1 A decision system

通过计算，该信息系统有2个约简，REDC(D)={{b，c}}.可以验证该系统是协调决策系统，见表1.而利用算法1，求得的结果是{b，d，c}，显然{b，d，c}∉REDC(D)，仍包含了冗余属性{d}.该例说明经典算法不能有效计算约简，仍具有一定的冗余性.本文提出一种新的属性约简方法来解决该问题.

3 结合属性选择和删除的属性约简方法

首先证明算法1得到的属性约简没有损失信息，即其依赖度相同.

定理1 给定决策系统S=(U，C∪D，V，f)，经过算法1后，得到red，那么

证明 反证法.假设γred(D)≠γC(D)，那么，γred(D)＜γC(D)，因此，存在 x∈PosC(D)，使得 x∉Posred(D)，那么，存在 y∈［x］red，使得 M(x，y)≠Ø.然而这与算法1矛盾，因为经过算法1运算后，M是一个空矩阵，因此假设不成立.

例1说明了经典算法得到的red还具有一定冗余性，而定理1说明了经典算法得到的red与原始决策系统具有相同的分辨能力.因此，本文提出能有效避免冗余的辨识矩阵属性约简快速算法.

算法2 结合属性选择和删除的属性约简快速算法:

算法2比算法1多了一个循环O(|U||C|)，由于这2个循环是并列的，那么总的时间复杂度为O(|U||C|2)+O(|U||C|)=O(|U||C|2)，因此算法2与算法1具有相同的时间复杂度，本文提出的算法的时间复杂度不会增加.

下面证明算法2选择的属性子集是约简，既保持了信息，又有效地消除了冗余信息.

定理2 给定决策系统S=(U，C∪D，V，f)，经过算法2后，得到red，那么red是约简.

证明 类似于定理1的证明，可以得到

另一方面，采用反证法证明red是独立的.假设red不是独立的，那么存在a∈red，满足

那么这样的属性a在14)～19)的循环中被删除了，即 a∉red.

因此，假设不成立，red是独立的.所以，red是约简.

例2 继续使用例1，利用算法2，可以得到约简red={b，c}.因此，与基于辨识矩阵属性约简方法相比，该方法能够有效地获得约简.

4 实验与分析

用6个UCI标准数据集来验证本文提出的方法的实用性和有效性，如表2所示.表3对经典方法选择的属性序列和本文提出的方法选择的属性序列进行了比较.利用经典方法得到的6个数据集中，Heart、Lymph、Soybean 有 3 个不是约简.而本文方法得到的都是约简，有效地解决了经典方法得不到约简的问题.

表2 UCI标准数据集Table 2 UCI standard datasets

表3 与经典方法的比较Table 3 Comparison of UCI standard datasets and the classical approaches

从选择属性个数来看，与原始数据集对比，经典算法和本文提出的方法都大大减少平均属性个数.进一步地，本文算法的平均属性个数为8.5，比经典算法减少了1.3个.因此，本文提出的方法能够获得更为精简的集约数据集，进一步降低了数据集的冗余性.

5 结束语

本文提出了结合属性选择和删除的属性约简方法，该方法能够彻底解决经典算法产生的冗余，得到有效的约简，解决了经典算法不能得到约简的问题.通过6个UCI标准数据集，实例分析表明，提出的方法选择的平均属性个数比经典算法减少了1.3个，显示了其有效性和实用性.

［1］张文修，吴伟志，梁吉业，等.粗糙集理论与方法［M］.北京:科学出版社，2001:5-7.

［2］PAWLAK Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11(5):341-356.

［3］蒋云良，杨章显，刘勇.不协调信息系统快速属性分布约简方法［J］.自动化学报，2012，38(3):382-388.

JIANG Yunliang，YANG Zhangxian，LIU Yong.Quick distribution reduction algorithm in inconsistent information system［J］.Acta Automatica Sinica，2012，38(3):382-388.

［4］XU F，MIAO D，WEI L.Fuzzy-rough attribute via mutual information with an application to cancer classification［J］.Computers and Mathematics with Applications，2009，57(6):1010-1017.

［5］BHATT R，GOPAL M.On fuzzy-rough sets approach to feature selection［J］.Pattern Recognition Letters，2004，26(7):965-975.

［6］胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简［J］.软件学报，2008，19(3):640-649.

HU Qinghua，YU Daren，XIE Zongxia.Numerical attribute reduction based on neighborhood granulation and rough approximation［J］.Journal of Software，2008，19(3):640-649.

［7］TSANG E C C，CHEN D G，YEUNG D S，et al.Attribute reduction using fuzzy rough sets［J］.IEEE Transactions on Fuzzy Systems，2008，16(5):1130-1141.

［8］张志飞，苗夺谦.基于粗糙集的文本分类特征选择算法［J］.智能系统学报，2009，4(5):453-457.

ZHANG Zhifei，MIAO Duoqian.Feature selection for text categorization based on rough set［J］.CAAI Transactions on Intelligent Systems，2009，4(5):453-457.

［9］SKOWRON A，RAUSZER C.The discernibility matrices and functions in information systems［M］//Intelligent Decision Support，Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht:Kluwer Academic Publishers，1992:331-362.

［10］常犁云，王国胤，吴渝.一种基于Rough Set理论的属性约简及规则提取方法［J］.软件学报，1999，10(11):1206-1211.

CHANG Liyun，WANG Guoyin，WU Yu.An approach for attribute reduction and rule generation based on rough set theory［J］.Journal of Software，1999，10(11):1206-1211.