变精度粗糙集的区域属性约简及其结构启发算法

摘 要：变精度粗糙集（VPRS）属性约简具有数据分析应用， 三支决策利于二分类模式识别。采用二分类情形与三支决策区域， 研究变精度粗糙集（VPRS）两类属性约简及其结构启发算法。首先，依托三支决策区域构建分类区域， 提出分类区域保持（CRP）约简与决策区域保持（DRP）约简， 得到对定性属性约简的量化扩张性， 设计基于核的结构启发算法；然后，研究两类区域约简的强弱关系， 设计由强至弱的结构启发算法， 得到二支决策拓展为三支决策的约简改进；最后，利用数据表实例与UCI数据集验证区域约简及其启发算法的有效性。本文揭示二分类VPRS属性约简的强弱关系与优化计算， 为多分类数据分析奠定基础。

关键词：变精度粗糙集；属性约简；三支决策；结构启发算法

中图分类号：TP18

文献标志码：A

文章编号：1001-9081（2016）11-2954-04

0 引言

粗糙集理论是人工智能热点之一， 能够有效处理不精确、不一致、不完整数据。经典定性粗糙集（PawlakRS）[1]具有过拟合局限， 而定量模型更能适应实际噪声环境。概率粗糙集是主流量化模型， 包括变精度粗糙集（Variable Precision Rough Set， VPRS）[2]、决策粗糙集（DecisionTheoretic Rough Set， DTRS）[3]等。其中， VPRS具有错误容忍机制与鲁棒性， 是一种常用定量模型， 文献[4]基于容差关系对其进行了研究。

属性约简是粗糙集理论的核心内容，主要应用于数据分析。模型区域是属性约简构建的基本路线， 其中的分类区域组建于决策区域。对定性PawlakRS，区域具有粒化单调性，因此属性约简主要保持分类正域与保持协调规则[1]。对定量粗糙集， 区域呈现粒化不确定性[5]， 定量属性约简成为难点。对定量VPRS， 文献[6]基于近似区域分布构建分布约简， 文献[7]提出约简增量算法处理动态数据， 文献[8]聚焦核并提出最小约简算法。

三支决策是二支决策的理性拓展， 是一种普适性的智能理论[9]， 特别适用于粗糙集及其属性约简。文献[10]建立三支决策空间探讨三支决策， 文献[11]基于三支分类区域建立三支决策约简。三支决策紧密联系具有正模式与负模式的二分类， 决策类的正域、负域、边界域对应接受、拒绝、不承诺决策， 成为三支决策区域。三支决策有利于二分类模式识别， 而二分类属性约简则是定量属性约简的有效切入点。对此， 文献[12]研究二分类DTRS的定量约简与层次约简， 并对定量与定性约简进行集成构建。

本文针对二分类VPRS并采用三支决策区域， 构建分类区域保持（ClassificationRegions Preservation， CRP）与决策区域保持（DecisionRegions Preservation， DRP）两类定量约简， 分析对PawlakRS定性约简的量化扩张性， 设计区域约简基于核的结构启发算法。进而， 研究DRP 约简与CRP约简的强弱关系， 设计由强至弱的结构启发算法， 分析二支决策展向三支决策的约简改进。最后， 依据数据表实例与UCI数据集验证两类区域约简及其关系与算法。

6 UCI数据实验

本章选用3个典型的二分类UCI数据集[12]实施数据实验。在表3中， Monks3数据集含432个测试对象， 其中的122个训练实例含5%的分类噪声；

Voting数据集具有缺损值， 需要错误容忍；SpectHeart数据集含22个属性元， 具有属性约简的宽泛搜索空间。这3个数据集分别具有噪声不精确、缺损不确定、属性代表性的特征， 适用于本文二分类VPRS属性约简及其定性退化约简的验证。

7 结语

本文针对二分类VPRS， 采用三支决策区域， 构建CRP与DRP两类属性约简， 得到强弱性、扩张性、改进性， 并利用双界结构设计区域约简的结构启发算法。CRP约简关联二支决策， DRP约简改进为三支决策， 后者等价于分布约简[6]。区别于文献[12]的集成构建， 本文主要聚焦定量与定性约简的扩张关系与近似逼近。研究结果揭示了二分类VPRS属性约简的强弱关系与优化计算， 保持了确定性与不确定性决策规则， 为多分类数据分析奠定基础。如何泛化拓展研究多分类量化扩张属性约简值得深入探讨， 包括针对VPRS与DTRS等定量模型。

参考文献：

[1] PAWLAK Z. Rough sets [J]. International Journal of Information and Computer Science， 1982， 11（5）： 341-356.

[2] ZIARKO W. Variable precision rough set model[J]. Journal of Computer and System Sciences， 1993， 46（1）： 39-59.

[3] YAO Y Y， ZHAO Y. Attribute reduction in decisiontheoretic rough set models [J]. Information Sciences， 2008， 178（17）： 3356-3373.

[4] 徐怡， 李龙澍. 基于（α，λ）联系度容差关系的变精度粗糙集模型[J]. 自动化学报， 2011， 37（3）： 303-308.（XU Y， LI L S. Variable precision rough set model based on （α，λ） connection degree tolerance relation[J]. Acta Automatica Sinica， 2011， 37（3）： 303-308.）

[5] ZHANG X Y， MIAO D Q. Quantitative/qualitative regionchange uncertainty/certainty in attribute reduction： comparative regionchange analyses based on granular computing[J]. Information Sciences， 2016， 334/335： 174-204.

[6] MI J S， WU W Z， ZHANG W X. Approaches to knowledge reduction based on variable precision rough set model [J]. Information Sciences， 2004， 159（3/4）： 255-272.

[7] CHEN D G， YANG Y Y， DONG Z. An incremental algorithm for attribute reduction with variable precision rough sets[J]. Applied Soft Computing， 2016， 45： 129-149.

[8] 陈昊， 杨俊安， 庄镇泉. 变精度粗糙集的属性核和最小属性约简算法[J]. 计算机学报， 2012， 35（5）： 1011-1017. （CHEN H， YANG J A， ZHUANG Z Q. The core of attributes and minimal attributes reduction in variable precision rough set[J]. Chinese Journal of Computers， 2012， 35（5）： 1011-1017.）

[9] YAO Y Y. An outline of a theory of threeway decisions[C]// Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing， LNCS 7413. Berlin： Springer， 2012： 1-17.

[10] HU B Q. Threeway decisions space and threeway decisions[J]. Information Sciences， 2014， 281： 21-52.

[11] CHEN Y M， ZENG Z Q， ZHU Q X， et al. Threeway decision reduction in neighborhood systems[J]. Applied Soft Computing， 2016， 38： 942-954.

[12] ZHANG X Y， MIAO D Q. Regionbased quantitative and hierarchical attribute reduction in the twocategory decision theoretic rough set model [J]. KnowledgeBased Systems， 2014， 71： 146-161.