张清华, 艾志华, 张金镇

(重庆邮电大学 计算智能重庆市重点实验室， 重庆 400065)

粗糙集是由Pawlak教授于1982年提出的一种处理不精确、不一致、不完全信息和知识的重要数学工具[1]，已经被广泛应用于机器学习、知识发现、数据挖掘、决策支持与分析等[2-3]。但是Pawlak粗糙集只适用于处理离散型数据，对于实际应用中普遍存在的数值型或混合型数据，需要将其离散化，从而不可避免地带来了信息损失[4]，从而影响分类效果。为解决这一问题，Pawlak粗糙集被扩展到邻域粗糙集[5]和模糊粗糙集[6-7]。实际上，邻域粗糙集提供了一种构造数据空间的近似方法[8]。从拓扑学的角度，证明了邻域空间比数据空间的概念更一般化[9]，这表明将原始数据空间转化为邻域空间有助于数据的泛化[10]，因此邻域粗糙集模型被广泛应用于分类学习[11-12]与特征选择[13-15]中。为了构造邻域空间，可以通过邻域粗糙集构造邻域覆盖，在邻域覆盖中，每个邻域中的样本都是同种类别的，因此邻域覆盖提供了一个从邻域层次去表示数据分布[16]的方法。并且，为了更精确地表示数据分布，邻域覆盖约简算法通过集合包含关系剔除冗余的邻域[17]。

由于邻域中所有样本都是同种类别的，所以每个邻域都对应一个分类规则。因此，文献[17]提出了基于邻域覆盖约简的规则学习方法(NCR)，该方法通过邻域覆盖约简过滤掉冗余的邻域得到分类规则，进而根据离测试样本最近的邻域来匹配规则对测试样本分类。由于NCR方法简单、有效，被广泛应用于数据分类中，但该方法对邻域的约简过于严格，易受到噪声样本影响，从而在覆盖中仍然存在一些冗余的邻域，对规则提取带来较高的复杂度。……