基于属性一致度的属性约简算法

达列雄　邓方安　刘杰

摘要：在属性一致度的概念和性质基础之上，提出一种基于属性一致度的属性约简算法。利用一致度构造属性间模糊相似矩阵，并用模糊聚类分析方法对属性重要性作了分类，从而得到动态属性分类图，得到了与粗糙集属性约简方法完全一致的结果。最后，用实例表明算法的有效性。

关键词：属性一致度；属性约简；模糊聚类分析

中图分类号：TP182 文献标识码：A

1引言

粗糙集在处理不精确、不相容、不完备数据中具有明显的优势。粗糙集理论在模式识别、决策分析、数据分析处理、机器学习以及数据库中知识发现等多个领域得到了广泛应用。在当前的粗糙集理论中，知识约简算法主要有三种：一种是按定义求解，而按照这种方法计算所有的约简已被证明是NP一完全问题，无法实际中得到应用。另一种是1991年分辨矩阵求解，而这种方法在求解过程中，需要两个不同决策对象的所有属性值进行逐一比较，这样会产生海量矩阵元素，既占用非常大的存储空问，且时空性能又差。近年来，很多学者对此方法作了大量改进，但还是存在一定的缺陷。2008年孟庆全，金传山等从传统的属性依赖度概念出发，对属性集和属性集依赖度两个概念进行了扩展，提出了独立于定义求解分辨矩阵法之外的新方法，即通过属性依赖度求解属性约简和知识核的新方法。而第三种属性约简算法基本都是基于属性重要性为主的一种算法，这类方法通常都会遇到如下两个问题：

第一，属性的重要性没有统一的定义，使得约简结果存在一定的差别，甚至会使约简结果出现相互矛盾的情况；

第二，在约简属性得重要性相等的情况下，其相对约简很难确定。

属性相似度反映着粒度的相似程度，也反映着属性之问的相似关系。为了解决以上存在的问题，夏克文博士从属性相似度出发，提出了一种基于属性相似度的属性约简算法，该算法不仅计算简便，同时还能区分不同约简的优劣性，克服传统的粗糙集属性约简算法存在的缺点。

文献虽然给出了一种基于属性相似度的属性约简算法，但该文只考虑了决策属性与条件属性之间的相似度问题。本文将定义条件属性之间相似度及条件属性与决策属性问的一致度，利用一致度构造属性问的模糊相似矩阵，并用模糊聚类分析方法对属性重要性做出分类，从而得到属性的动态分类图，得到了与粗糙集属性约简方法完全一致的结果。

2属性一致度的概念与性质

定义1 在一个信息系统（U，C，D）中，U为论域，即U={x₁，x₂，…，x_n}，C为条件属性集，P，Q∈U，D为决策属性集，定义属性问的一致度（consistent degree）如下：

上述公式（1）对于条件属性集C中的任意属性与决策属性问的一致度计算也适用。

条件属性子集P∈C与D为决策属性集的一致性σ（P，D）也可类似定义。

命题1在一个信息系统（U，C，D）中，U为论域，即U={x₁，x₂，…，x_n}，C为条件属性集，且P，Q∈C，D为决策属性集，属性的一致度具有如下性质：

3一种基于属性一致度的属性约简算法

1）依据信息表，计算属性的一致度。

2）依据属性一致度，构造属性问关系模糊相似矩阵。

3）依据属性问关系模糊相似矩阵，进行模糊聚类分析。

4）依据聚类分析求属性约简，并确定核。

根据基于属性一致度的属性约简算法，通过表1样本信息表，先给出对象集的按各个属性的等价分类。按照定义1可得：

根据以上3.2给出的属性问的一致度，可以构造属性问模糊相似矩阵：因为R²≥R，因此R不是模糊等价矩阵。容易求得模糊相似矩阵R的传递闭包

这是一个模糊等价矩阵，求t（R）=R^*的水平截集，得到动态分类：

通过上面的例子，可以看出，条件属性c₂，c₃与决策属性D的一致度偏低，它们是必要属性，构成约简的核，c₁，c₄与决策属性D的一致度高，在属性约简时，可以把条件属性集中与决策属性D一致度高的条件属性约去，构成最简属性约简。

不难看出，{c₁，c₂，c₃），{c₄，c₂，c₃）是信息表1的两个约简，由于σ（c₁，D）=0.8，

σ（c₄，D）=1.0，因此{c₄，c₂，c₃}是比{c₁，c₂，c₃}更好的约简，这与属性分类动态聚类图是一致的。

4结束语

本文主要针对信息系统中的属性相似度与属性的约简，对条件属性之间的相似度、条件属性与决策属性间的一致度进行定义，在此基础之上，提出了一种基于属性一致度的属性约简算法。并根据给出的属性一致度的基本性质，采用模糊聚类分析方法，对属性重要性作了分类，得到了与粗糙集属性约简方法一致的结果，表明了算法的有效性。