学文网摘要：粗糙集理论是一种研究不精确、不确定性、处理不完备知识的数学工具，目前被广泛应用于人工智能、模式识别、机器学习、决策支持和数据挖掘等领域。该文通过介绍粗糙集理论及特点，叙述了粗糙集理论在各领域的应用发展情况，并且展望了其未来发展趋势。
关键词：粗糙集；属性约简；粗糙集应用；数据挖掘
中***分类号：TP18文献标识码：A文章编号：1009-3044(2008)28-0172-03
Rough Set Theory and Its Application Research
WEI Liang
(Electronics and Information School, Tongji University, Shanghai 201804, China)
Abstract: Rough set theory is a math theory which processes non-accurate, uncertain and incomplete knowledge. Currently, it has already been applied successfully in the area of Artificial Intelligence, Pattern Recognition, Machine Learning, Decision Analyzing and Data Mining etc. This paper introduces the rough set theory and its characteristics, reviews the development of this theory in different fields, and suggests evolutional trend in the coming future.
Key words: rough set; attribute reduction; rough set application; data mining
1 引言
波兰数学家Pawlak于1982年提出的粗糙集理论是一种新的处理模糊和不确定性知识的数学工具[1]。其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。粗糙集理论能有效地分析和处理不精确、不一致和不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。以粗糙集理论为基本框架的知识发现过程的研究，越来越引起人们的关注，特别是将粗糙集理论与机器学习、模式识别、数据库理论等相结合，并融合其它有效的数学工具与方法的研究，显示出基于粗糙集理论的多种软计算方法相结合算法在知识发现和优化过程中的强大的优越性，为知识发现的理论基础提供了一定的依据。目前粗糙集理论已成为人工智能领域中一个较新的学术热点，引起了越来越多科研人员的关注。
2 粗糙集理论的基本概念
设U是非空有限论域，R是U上的二元等价关系，R称为不可分辨关系，序对A=(U,R)称为近似空间。?坌(x,y)∈U×U，若(x,y)∈R，则称对象x与y在近似空间A中是不可分辨 的。U/R是U上由R生成的等价类全体，它构成了U的一个划分。可以证明，U上划分可以 与U上的二元等价关系之间建立一一对应。U/R中的集合称为基本集或原子集。若将U中的 集合称为概念或表示知识，则A=(U,R)称为知识库，原子集表示基本概念或知识模块。任意有限的基本集的并和空集均称为可定义集，否则称为不可定义的。可定义集也称为精确集，它可以在知识库中被精确地定义或描述，可表示已知的知识。可以验证所有可定义集全体可构成 U上的一个拓扑。
令知识库K=(U,R)，集合X?哿U，R是一个等价关系：
■
分别称RX为X的R下近似（Lower Approximation）和RX为X的R上近似（Upper Approximation）。称集合BNR(X)=RX-RX为X的R边界域；POSR(X)RX为X的R正域； NEGR(X)=U-RX为X的R负域。下近似RX包含了所有使用知识R可确切分类到概念X的元素。上近似RX则包含了所有那些可能是属于概念X的元素。概念的边界区域BNR(X)由不能肯定分类到这个概念X或其补集X中的所有元素组成。关系如***1所示。
刻画粗糙集的方法有以下两种：一种是用表示近似精度的数值表示粗糙集的数字特征；数字特征表示粗糙集边界域的相对大小，但没有说明边界域的结构。另一种是用粗糙集的拓扑分类表示粗糙集的拓扑特征。拓扑特征给出边界域的结构信息，但没有给出边界域大小的信息。
由等价关系R定义的集合X的近似精度如下：
■
其中X≠Ф，|X|表示集合X的基数，显然，0≤αR(X)≤1。定义PR(X)=1-αR(X)，称PR(X)为X的R粗糙度。粗糙度反映了利用知识R近似表示X的不完全程度。
设X是一个R粗糙集， 称X是R粗糙可定义的，当且仅当RX≠Ф且RX≠U；称X是R内不可定义的，当且仅当RX=Ф且RX≠U；称X是R外不可定义的，当且仅当RX≠Ф且RX=U；称X是R全不可定义的，当且仅当RX=Ф且RX=U。如果X是R粗糙可定义的，则意味着我们可以确定U中的某些元素属于X或X；如果X是R内不可定义的，则意味着我们可以确定U中的某些元素是否属于X，但不能确定U中任一元素是否属于X；如果X是R外不可定义的，则意味着我们可以确定U中的某些元素是否属于X，但不能确定U中任一元素是否属于X；如果X是R全不可定义的，则意味着我们不能确定U中的任一元素是否属于X或X。
粗糙集的数字特征（近似精度）和拓扑特征之间有一定的联系：
若集合是内不可定义的或全不可定义的，则其近似精度为0；
若集合是外不可定义的或全不可定义的，则其补集的近似精度为0。
实际应用时，应综合考虑边界域的两种信息。
3 属性约简
属性约简是粗糙集理论中的一个核心部分，同时也是粗糙集理论中最重要的概念之一。自粗糙集理论被提出后，研究学者在属性约简方面提出了许多算法，这些属性约简算法最终可以归结为三类：基于约简定义的Pawlak属性约简算法[2]；基于差别矩阵的属性约简算法；基于启发式信息的属性约简算法。然而，到目前为止，还没有一个公认的、高效的最佳属性约简算法，另一方面，科学家在理论上证明求取处理对象的所有属性约简、所有最小约简是一个NP完全问题。
3.1 几种典型的约简算法
3.1.1 基本算法
基本算法首先在已有数据的基础上构造差别矩阵。然后在差别矩阵的基础上得到差别函数。对此得到的差别函数进行化简，使之成为析取范式。最后得到的每个主蕴含式均为约简。该算法可以求出所有的约简。然而，由于对大数据集的差别函数的约简是一个非常困难几乎不可能的问题，因此，此算法只适合于非常小的数据集。
3.1.2 基于差别矩阵的启发式算法
Skowron提出差别矩阵，并且提出差别矩阵可用于属性约简。在此基础上，利用差别矩阵得到了许多启发式约简算法。这些算法的共同点都是先得到差别矩阵，由差别矩阵求出属性核，在此基础上根据如信息熵、属性频率等启发式规则往属性核加入属性，直到满足条件为止。
3.1.3 遗传算法
己经有不少用遗传算法计算约简的算法。各种算法的不同之处主要在适应度函数的不同。Bjorvand和Komorowski提出了具有代表性的遗传算法。每个位串代表差别矩阵的一项，即两个对象的属性集口某位为1时表示该属性存在，否则不存在。这样每个位串是一个约简的候选。定义适应度函数如下：
转载请注明出处学文网 » 粗糙集理论及其应用与发展研究