控制网

曾庆双 （1964-）

男，教授，博士生导师。研究方向为机器学习和故障诊断。
基金项目：国防科技预研基金项目（9140A17030207HT0150）




摘要：针对现实中含有数值型属性的决策系统的约简问题，提出了基于邻域粒化和遗传算法的约简方法。该方法采用基于邻域等价关系建立的粗糙集模型，用邻域等价关系度量粗糙集不可分辨关系，通过邻域信息粒子逼近论域空间。构造了遗传约简算法，论述了遗传算法适应度函数的选择，设计了自适应交叉概率，给出了算法的具体实现。对经典数据集和UCI数据库中4个数据库约简的结果证明了算法的有效性和可行性。

关键词：邻域；粗糙集；约简；遗传算法

Abstract: In order to reduce the practical decision system 
including numerical attributes, a reduction algorithm based on 
neighborhood granulation and genetic algorithm is proposed. In 
this algorithm, a rough set model is used based on neighborhood 
equivalence, the indiscernibility relation is measured by neighborhood 
relation, and the universe spaces is approximated by neighborhood 
information granules. The choice of fitness function and the adaptive 
across probability is discussed, and the reduction algorithm is presented
 as well. Furthermore, the dependency function is used to evaluate the 
significance of numerical attributes. The validity and feasibility of the
 algorithm are demonstrated by the results of experiments on a classical 
data set and four UCI machine learning databases.

Key words: Neighborhood; Rough set; Reduction; Genetic algorithm

    粗糙集理论是波兰数学家Pawlak于1982年提出的一种数据分析理论[1]，它作为一种刻划具有不完整性和不确定性信息的全新数学工具， 已经成为人工智能领域的一个新的学术热点。Pawlak粗糙集将研究对象的全体称为论域，采用等价关系将论域粒化为若干互斥的等价类，并定义了两个等价类的并集：下近似和上近似来逼近这一概念。但是，作为一种有效的粒度计算模型，Pawlak粗糙集建立在严格的等价关系和等价类基础上，只适合处理符号变量，但实际应用的数据库中普遍存在数值变量，这为粗糙集的应用带来了困难。在用粗集理论处理数值型数据时，一般采用离散化算法把数值型属性转化为符号型属性，这一转换不可避免的造成信息损失，计算处理结果在很大程度上依赖于离散化的效果。随后提出的可变精度粗糙集模型虽然给出了一个不一致性容忍的域值，将Pawlak粗糙集中正域求取的严格包含修正为绝大部分包含，但需要用户设定阈值，并将阈值以下的少量不一致样本当成一致样本进行处理也是不合理的，不能有效估计特征的分类能力[2]。

    1988年Lin提出了邻域模型的基本概念[3]。1998年姚一豫以及2002年吴伟志教授分别研究了邻域算子和邻域系统的基本性质[4,5]。邻域模型通过点的邻域来粒化论域，将邻域作为基本信息粒子。邻域粗糙集方法直观、易于理解，能够直接处理数值型属性，而无须对其进行离散化处理。因此，与经典粗糙集方法相比，该方法省去了离散化的过程，模型可以直接分析数值型数据，从而拓展了经典粗糙集理论的应用范围。

    知识约简问题是粗糙集理论的一个核心问题。所谓知识约简， 就是在保持知识库分类能力不变的条件下， 删除其中不相关或不重要的冗余知识，已经证明它是NP难问题[6]，计算量随属性个数呈指数级增长。现有的约简算法， 主要是从粗糙集的核出发， 采用启发式搜索的方法构造所含条件属性最少的约简， 即最小约简。但是这种算法并非对所有的知识表达系统都适用[7]， 而且随着问题规模的增大会越来越复杂。遗传算法，恰好由于它本身具有全局优化和隐含并行性等优点，因此很适合于这个问题的求解。

    遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖梯度信息，是一种有效的全局优化搜索算法，因此遗传算法具有很强的全局搜索能力，能够在较短时间内找到全局最优解[8]。将遗传算法和邻域粒化理论相结合，设计了一种基于邻域粒化的自适应遗传约简算法。该算法可直接处理数值型数据，降低约简时间，提高计算效率，并通过对交叉概率的自适应设计，保证算法的收敛性。

1  邻域粒化及粗糙逼近

    Pawlak粗糙集以等价类和划分为基础，论域被等价关系分割为互不相交的若干子集，如图1所示，容易造成部分样本具有相同的特征但决策却不相同。对于被数值描述的分类问题，如图2所示，很难得到取值完全相同的样本。此时通过适当放宽属性值相等的条件，改为属性值相近的假设，使得属性值相近的样本具有相同的决策，否则决策是不一致的，就是邻域粗糙集的基本思想。从图1、图2可以看出，Pawlak粗糙集是邻域粗糙集的特例，当定义邻域大小时，邻域关系即退化为等价关系，邻域粒子退化为等价类，相应的，邻域粗糙集退化为Pawlak粗糙集[9]。

    定义1. 设是非空度量空间，，，称点集为以为中心，以为半径的闭球，又称为的邻域。

    论域中所有对象的邻域形成了论域的粒化，邻域粒子族是构成论域空间的基本要素。
 

                                        图1   Pawlak粗糙集
 

                                            图2   邻域粗糙集

    设为一信息系统，其中U是对象的非空有限集合，称为论域；A是属性集合；V是属性值域；f是的映射，为U中各对象的属性指定唯一值。如果，，其中C，D分别表示条件属性集和决策属性集，那么该信息系统称为决策系统。

    定义2. 给定邻域决策系统，D将U划分为N个等价类：，生成U上的邻域关系NB，那么决策D关于B的邻域下近似和上近似分别为：
   
   
 
    决策的边界定义为

    决策D的下近似也称为决策正域，正域的大小反映了分类问题在给定属性空间中的可分离程度。正域越大，表明各类的重叠区域即边界越少。这类分类问题可以用下面的定义描述。

    定义3. 给定一个邻域决策系统，，决策属性D对条件属性的依赖度为
     （1）

    依赖度表示在条件属性C下能够确切划入决策在U/D的对象占论域中总对象数的比率，表达了决策属性对条件属性的依赖程度。需要指出的是，邻域粒化不能区分线性还是非线性可分问题，邻域大小只是反映了样本之间的距离。度量数据的可分性时，如果依赖度为1，则是可分的，并不去考虑是线性可分还是非线性可分。

    系统中的部分属性对某个分类问题可能是冗余的或者是无关的，这些属性不会引起分类边界的变化，但是它们的存在，可能会导致模型过拟合、学习速度变慢、分类器变复杂。如果从系统中去掉一个属性a，系统的正域不变，各类的可区分性不变，可以视属性a是冗余的，相反，如果删除a后决策属性D对剩余条件属性的依赖度变小，则表明a属性不能被删除，否则影响系统的可区分性。

    定义4. 给定一个邻域决策系统，，，如果B满足下面两个条件，则称B是A的一个相对约简：

    （1）充分条件： 

    （2）必要条件：，。

    第一个条件确保属性B能形成和全部属性A相同大小的分类正域，因此其保留了充分的分类信息。第二个条件确保B中的任何一个属性都是必要的，在约简中不存在多余的属性。

    同样，对给定决策系统，属性的重要性可以如下定义：
      （2）                    

2  基于邻域模型的核属性计算

    给定一个邻域决策系统，C中所有D必要的原始属性构成的集合，称为D的C核，简称核，记为COREC(D)。

    这是核的一个很朴素的定义，核还可以理解为A所有约简的交集，因此一个决策系统不一定存在核，如果存在核，核将包含于任一个约简中。核是所有约简的基础，计算一个决策系统的约简一般先从获得核开始。

    定理1：给定一个邻域决策系统，属性 ，如果，则a是核属性。

    证明：根据核属性定义可证。

    根据定理1，基于属性的重要度，设计了邻域模型的核属性计算算法，描述见算法1。

    算法1：邻域模型核属性算法

    输入：和

    输出：核属性CORE

    1：

    2：For each   

    3：计算

    4：If   

    5：

    6：End if

    7：End for

3  遗传约简算法

    遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。由美国Holland J教授提出。其主要特点是，群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。遗传约简算法是决策问题中寻找最小约简的一种方法。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。结合自适应遗传算法及最小相对约简问题的特点与要求，本文提出的自适应遗传算法主要运算过程如图3所示，其中G和M分别表示当前进化代数和进化终止代数。
 

                                    图3   自适应遗传算法

3.1  编码方法

    由于遗传算法不能直接处理解空间的解数据，必须通过编码将它们表示成遗传空间的基因型串结构数据。本文使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}组成，其中每一位对应一个条件属性，若某位取值为1，则表示选择其对应的条件属性，若某位取值为0，则表示不选择其对应的条件属性。染色体的长度为条件属性的个数，每一个染色体个体对应了条件属性空间中的一个属性子集，即属性选取的一个可能解。

3.2 适应度函数的确定

    适应度函数是对个体位串的适应性进行评价的惟一确定性指标，所以适应度函数的形式直接决定着群体的进化行为。按照知识约简问题的实际要求，我们定义适应度函数如下[10]：
        （4）

    其中，f(x)为目标函数，card(x)为染色体中1的个数，即染色体所含条件属性的个数，n为染色体的长度，即条件属性的个数；为罚因子；P(x)为罚函数，为x所含条件属性对决策属性D的依赖度，是预设的阈值。通过这三部分构造的适应度函数，可以在保持决策属性对整体条件属性依赖度不变的情况下，获得知识约简问题的最佳搜索效果。

3.3 选择运算

    预设一个种群规模为m，长度为n的由0、1表示的染色体作为初始种群，为加快算法的收敛，将核中所含的属性加入到初始种群中。选择操作采用适应度比例选择方法，通过轮盘赌的方式实现。对于给定规模m的群体， 个体的适应度为，其被选择次数的期待值为：
       （5）

    gj反映了父代种群中个体生存的期望数目。将gj四舍五入得到个体xj被选择的次数，从而由种群G1成为G2。为保证某一代的最优解不被破坏，采用最优个体保护法，取每一代中适应度最大的个体不进行遗传操作，而是直接复制到下一代的种群中，这样每一代的最优个体的特征呈单调递增的趋势。

3.4 交叉运算

    按照预先设定的概率Pc随机选择对染色体，对每一对染色体的每一位按相同的概率进行交叉。设染色体编码为 ，，则操作描述为：
    ：，   （6）

    其中，x是在[0，1]上取值的均匀分布的随机变量。

    从群体进化过程来看，交叉概率应该随进化过程逐渐减小，最终趋于某一稳定值，以免对算法后期的稳定性造成冲击而影响算法的收敛性。本文选择交叉概率公式为：
       （7）

    其中，G为进化代数，为常数。

3.5 变异运算

    对于给定的变异概率Pm，随机选择个染色体，随机改变某位的编码来实现变异操作。设选定的染色体为，操作描述为：
    ：  （8）

    其中，x是在[0，1]上取值均匀分布的随机变量。

4  遗传约简算法实现

    随机产生m个长度为n的二进制串组成初始种群X，对于核中的属性，其对应位取1，并在整个进化过程中保持不变，其它对应位随机取0或者1，这样可以加快算法的收敛。在进化过程中，对最优个体进行保护，取每代中适应度最大的个体直接复制到下一代，其它个体以轮盘赌的方式生成交配池，并且采用自适应的交叉概率，加快进化速度，保证算法收敛，详细描述见算法2。

    算法2.邻域粒化模型遗传约简算法

    输入：，和X

    输出：约简red

    1：

    2：For each   

    3：计算决策属性对所含条件属性的依赖度

    4：计算

    5：End for

    6：

    7：计算以轮盘赌方式进行选择操作

    8：计算，按（6）式进行交叉操作

    9：根据，按（8）式进行变异操作，核属性位不发生变异

    10：IF连续t代最优个体适应度不再提高，或者达到最大进化代数，则终止计算，输出red

    11：Else   go to step 2

5  算例

    某型旋转机械设备[11]常有转子不平衡、转子不对中、油膜振荡、喘振和碰撞五种故障，由历史振动波形测量数据可建立如表1所示的原始故障诊断决策表。在表1中，包含20个故障样本；7个故障特征属性：C1表示0.01~0.40f、C2表示0.41~0.50f、C3表示0.51~0.99f、C4表示1f、C5表示2f、C6表示3~5f、C7表示5f；5种故障类型：F1为不平衡、F2为不对中、F3为油膜振荡、F4为喘振、F5为碰撞。

                     表1   故障诊断决策表

    U      C1         C2        C3        C4        C5        C6        C7      D

    X1    0.1109    0.0060    0.1145    0.9612    0.0323    0.0504    0.0243    F1

    X2    0.1063    0.1464    0.1177    0.9560    0.0061    0.0446    0.0505    F1

    X3    0.0455    0.0643    0.0927    0.7393    0.0645    0.2117    0.0014    F1

    X4    0.0461    0.0229    0.0850    0.5890    0.0798    0.2980    0.0319    F1

    X5    0.1305    0.1077    0.1389    0.2096    0.4240    0.1203    0.0767    F2

    X6    0.0875    0.0095    0.1287    0.5120    0.3437    0.0010    0.1309    F2

    X7    0.1462    0.0124    0.0788    0.2828    0.5551    0.0313    0.1263    F2

    X8    0.0968    0.0320    0.0600    0.5011    0.3414    0.1319    0.0502    F2

    X9    0.3467    0.2398    0.0829    0.2610    0.1152    0.1250    0.0586    F3

    X10   0.0251    0.2192    0.0776    0.2307    0.0503    0.1087    0.1233    F3

    X11   0.3952    0.5224    0.1090    0.1985    0.0640    0.1036    0.0865    F3

    X12   0.2115    0.2110    0.0209    0.3587    0.0751    0.0266    0.0661    F3

    X13   0.0572    0.2167    0.0332    0.5933    0.0876    0.1395    0.0696    F4

    X14   0.0847    0.2787    0.0518    0.2452    0.1443    0.0845    0.3499    F4

    X15   0.0738    0.3300    0.0317    0.3837    0.0705    0.0511    0.2287    F4

    X16   0.3560    0.3027    0.0861    0.1889    0.0914    0.1307    0.2771    F4

    X17   0.1422    0.0438    0.0327    0.8313    0.0838    0.1313    0.0637    F5

    X18   0.0911    0.0637    0.0620    0.5326    0.0208    0.0615    0.0840    F5

    X19   0.0821    0.1161    0.1175    0.4476    0.1481    0.3588    0.0973    F5

    X20   0.1491    0.1093    0.0942    0.3806    0.0536    0.3499    0.1699    F5

    根据邻域粒化模型和遗传算法，在无需离散化，无需其它先验知识的情况下，可以正确的求得决策系统的最小约简。表2是利用本遗传算法求解最小约简的一个计算结果。计算中各参数取值为：m=30，Pm=0.03，=15，=2，=0.9， ，。结果中显示了每一代的最优个体、最优个体适应度、当前群体总适应度和进化代数。在本例中第5代就出现最优个体，求得最小约简为{C2，C4，C7}，核属性为C7。相对于文献[10，12]，本文无需对数据进行预处理，直接快速求出最小约简，并且采用自适应交叉概率，具有更好的收敛性。

                      表2   遗传算法结果

        最优个体    适应度    群体适应度    进化代数

         1001101    0.7008    14.3671          1

         1101001    0.7008    17.6711          2

         1011001    0.7008    17.9321          3

         1011001    0.7008    16.0659          4

         0101001    0.9344    16.4312          5

         0101001    0.9344    16.2942          6

         0101001    0.9344    14.0870          7

         0101001    0.9344    9.7942           8

         0101001    0.9344    7.0915           9

         0101001    0.9344    10.8893          10


    为检验算法求出的相对约简的有效性，选用了美国加州大学Irvine分校（UCI）建立的机器学习数据库“Credit”、“German”、“Vote”和“Wine”。利用支持向量机（SVM）分类器作为评价函数，将数据样本分为训练集和测试集，分别用原始数据和约简后的数据来训练支持向量机，然后用预测精度来评价约简质量，实验中遗传算法仍采用前面的参数，“Vote”数据库对应的SVM采用linear核函数，其它采用spline函数，实验结果如表3所示。

                         表3   约简结果

            数据    样本    属性    原始预测精度    约简预测精度

           Credit    690     15        82.63           81.44

           German    1000    19        66.46           71.72

             Vote    435     16        95.40           93.07

             Wine    178     13        89.79           96.89


    约简后的预测精度和原始数据预测精度相比，“Credit”和“Vote”有所下降，原因是由于在复杂条件下，遗传算法获得的约简受到进化代数的限制，结果不是最优的，另外数据中的噪声也会造成预测精度的下降。预测精度提高是因为原始数据中冗余属性影响了决策，约简后降低了对决策的影响，提高了预测精度。

6  结论与展望

    本文基于邻域关系的概念，以论域空间中任意对象的邻域形成论域空间的粒化，扩展了经典粗糙集的应用范围。利用遗传算法，提出了一种基于遗传算法的数值型属性约简方法。由于遗传算法本身具有全局优化的特点，所以可以解决现有算法难以解决的问题。通过实验分析表明，这种算法是求解数值型属性知识约简问题的一种行之有效的方法。但是由于遗传算法计算量比较大，耗时长，基于邻域粗糙集模型的海量数据快速约简是下一步的研究方向。另外邻域算子的选择及对系统性能的影响也需要进一步的深入探讨。

参考文献

[1] Pawlak Zdzislaw. Rough Sets [J]. International Journal 
of Computer and Information Sciences，1982，11(5): 341-356.

[2] Xia Zhao, Minghu Ha, Aiquan Zhang. Variable Precision Rough 
Set Model in Incomplete Ordered Decision System [C]. Innovative 
Computing Information and Control，2008 ICICIC ’08. 3rd International 
Conference，2008，498-498.

[3] T. Y. Lin, Q. Liu, K J Huang. Rough Sets Neighborhood Systems and 
Approximation [C]. In: Fifth International Symposium on Methodologies 
of Intelligent Systems. Selected Papers 1990.

[4] Y. Y. Yao. Relational Interpretations of Neighborhood Operators
 and Rough Set Approximation Operators [J]. Information Sciences，1998，111: 239-259.

[5] W. Z. Wu, W. X. Zhang. Neighborhood Operator Systems and 
Approximations [J]. Inf. Sci. 2002，144(1-4): 201-217.

[6] Skowron A, Rauszer C. The Discernibility Matrices and Functions in 
Information Systems [M]. In: Slowiński R, ed. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory，1991:  331-362.

[7] Wang J, Miao D Q. Analysis on Attribute Reduct ion Strategies of
 Rough Set [J]. Journal of Computer Science and Techno logy，1998，13 (2): 189-192.

[8] Forrest S. Genetic Algorithms[C]. Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo，CA: Morgan Kaufmann Publishers，1993:  35-42.

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

[10] 陶志，许宝栋，汪定伟，李冉. 基于遗传算法的粗糙集知识约简方法[J]. 系统工程， 2003，21(4): 116 -122.

[11] 齐继阳，竺长安. 设备故障智能诊断方法的研究[J]. 仪器仪表学报，2006，27 (10) : 1270-1275.

[12] 张超，马存宝，宋东，许家栋. 基于粗糙决策树模型的复杂设备智能故障诊断 [J]. 兵工学报，2008，29 (9): 3211-8211.