粗糙集_计算机科学术语 - 线报百科mbji.cn

粗糙集

计算机科学术语

粗糙集理论，是继概率论、模糊集、证据理论之后的又一个处理不确定性的数学工具。作为一种较新的软计算方法，粗糙集近年来越来越受到重视，其有效性已在许多科学与工程领域的成功应用中得到证实，是当前国际上人工智能理论及其应用领域中的研究热点之一。1982年，波兰数学家Z.Pawlak发表了经典论文Rough Sets，意味着粗糙集理论的诞生。

引言

在自然科学、社会科学和工程技术的很多领域中，都不同程度地涉及到对不确定因素和对不完备信息的处理。从实际系统中采集到的数据常常包含着噪声，不够精确甚至不完整。采用纯数学上的假设来消除或回避这种不确定性，效果往往不理想。反之，如果正视它对这些信息进行合适地处理，常常有助于相关实际系统问题的解决。

多年来，研究人员一直在努力寻找科学地处理不完整性和不确定性的有效途径。模糊集和基于概率方法的证据理论是处理不确定信息的两种方法，已应用于一些实际领域。但这些方法有时需要一些数据的附加信息或先验知识，如模糊隶属函数、基本概率指派函数和有关统计概率分布等，而这些信息有时并不容易得到。

1982年波兰学者Z. Paw lak 提出了粗糙集理论——它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确，不一致（inconsistent）、不完整（incomplete）等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。

粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来（近似）刻画。

该理论与其他处理不确定和不精确问题理论的最显著的区别是：它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比较客观的，由于这个理论未能包含处理不精确或不确定原始数据的机制，所以这个理论与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性.

粗糙集是一种较有前途的处理不确定性的方法，相信今后将会在更多的领域中得到应用. 但是，粗糙集理论还处在继续发展之中，正如粗糙集理论的创立人Z. Paw lak 所指出的那样，尚有一些理论上的问题需要解决，诸如用于不精确推理的粗糙逻辑（Rough logic) 方法，粗糙集理论与非标准分析（Nonstandard analysis) 和非参数化统计（Nonparametric statistics）等之间的关系等等. 将粗糙集与其它软计算方法（如模糊集，人工神经网络，遗传算法等）相综合，发挥出各自的优点，可望设计出具有较高的机器智商（M IQ) 的混合智能系统(Hybrid Intelligent System），这是一个值得努力的方向.

历史与发展

在20世纪70 年代，波兰学者Z. Paw lak 和一些波兰科学院，波兰华沙大学的逻辑学家们，一起从事关于信息系统逻辑特性的研究。粗糙集理论就是在这些研究的基础上产生的. 1982年，Z. Paw lak 发表了经典论文Rough Sets，宣告了粗糙集理论的诞生. 此后，粗糙集理论引起了许多数学家，逻辑学家和计算机研究人员的兴趣，他们在粗糙集的理论和应用方面作了大量的研究工作.1991 年Z. Paw lak 的专著和1992 年应用专集的出版，对这一段时期理论和实践工作的成果作了较好的总结，同时促进了粗糙集在各个领域的应用. 此后召开的与粗糙集有关的国际会议进一步推动了粗糙集的发展. 越来越多的科技人员开始了解并准备从事该领域的研究. 目前，粗糙集已成为人工智能领域中一个较新的学术热点，在机器学习，知识获取，决策分析，过程控制等许多领域得到了广泛的应用.

基本概念

知识

“知识”这个概念在不同的范畴内有多种不同的含义。在粗糙集理论中，“知识”被认为是一种分类能力。人们的行为是基于分辨现实的或抽象的对象的能力，如在远古时代，人们为了生存必须能分辨出什么可以食用，什么不可以食用；医生给病人诊断，必须辨别出患者得的是哪一种病。这些根据事物的特征差别将其分门别类的能力均可以看作是某种“知识”。

不可分辨关系

分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系（indiscernibility relation）. 假定只用两种黑白颜色把空间中的物体分割两类，{黑色物体},{白色物体},那么同为黑色的两个物体就是不可分辨的，因为描述它们特征属性的信息相同，都是黑色.

如果再引入方，圆的属性，又可以将物体进一步分割为四类： {黑色方物体},{黑色圆物体},{白色方物体},{白色圆物体}. 这时，如果两个同为黑色方物体，则它们还是不可分辨的. 不可分辨关系是一种等效关系（equivalence relationship），两个白色圆物体间的不可分辨关系可以理解为它们在白，圆两种属性下存在等效关系.

基本集

基本集（elementary set）定义为由论域中相互间不可分辨的对象组成的集合，是组成论域知识的颗粒. 不可分辨关系这一概念在粗糙集理论中十分重要，它深刻地揭示出知识的颗粒状结构，是定义其它概念的基础. 知识可认为是一族等效关系，它将论域分割成一系列的等效类。

集合

粗糙集理论延拓了经典的集合论，把用于分类的知识嵌入集合内，作为集合组成的一部分. 一个对象a 是否属于集合X 需根据现有的知识来判断，可分为三种情况：

⑴ 对象a 肯定属于集合X ;

⑵ 对象a 肯定不属于集X ;

⑶ 对象a 可能属于也可能不属于集合X 。

集合的划分密切依赖于我们所掌握的关于论域的知识，是相对的而不是绝对的.给定一个有限的非空集合U 称为论域，I 为U 中的一族等效关系，即关于U 的知识，则二元对 K = (U,I) 称为一个近似空间（approximation space）. 设x 为U 中的一个对象，X为U 的一个子集，I (x) 表示所有与x 不可分辨的对象所组成的集合，换句话说，是由x 决定的等效类，即I (x) 中的每个对象都与x 有相同的特征属性（attribute）。

实例

下面用一个具体的实例说明粗糙集的概念. 在粗糙集中使用信息表（information table）描述论域中的数据集合. 根据学科领域的不同，它们可能代表医疗，金融，军事，过程控制等方面的数据. 信息表的形式和大家所熟悉的关系数据库中的关系数据模型很相似，是一张二维表格，如下表所示：

集合O 的下逼近（即正区）为 I *(O) = PO S (O) = {刘保，赵凯}

集合O 的负区为 N EG (O) = {李得}

集合O 的边界区为 BND (O) = {王治，马丽}

集合O 的上逼近为 I 3 (O) = PO S (O) + BND (O) = {刘保，赵凯，王治，马丽}

根据表1，可以归纳出下面几条规则，揭示了教育程度与是否能找到好工作之间的关系.

RULE 1: IF （教育程度= 大学） OR （教育程度= 博士） THEN （可以找到好工作）

RULE 2: IF （教育程度= 小学） THEN （找不到好工作）

RULE 3: IF （教育程度= 高中） THEN （可能找到好工作）

从这个简单的例子中，我们还可以体会到粗糙集理论在数据分析，寻找规律方面的作用.

特点

粗糙集方法的简单实用性是令人惊奇的，它能在创立后的不长时间内得到迅速应用是因为具有以下特点：

(1) 它能处理各种数据，包括不完整（incomplete）的数据以及拥有众多变量的数据；

(2) 它能处理数据的不精确性和模棱两可（ambiguity），包括确定性和非确定性的情况；

(3) 它能求得知识的最小表达（reduct）和知识的各种不同颗粒（granularity）层次；

(4) 它能从数据中揭示出概念简单，易于操作的模式（pattern） ;

(5) 它能产生精确而又易于检查和证实的规则，特别适于智能控制中规则的自动生成。

应用

粗糙集理论是一门实用性很强的学科，从诞生到现在虽然只有十几年的时间，但已经在不少领域取得了丰硕的成果，如近似推理，数字逻辑分析和化简，建立预测模型，决策支持，控制算法获取，机器学习算法和模式识别等等。粗糙集能有效地处理下列问题：

1.不确定或不精确知识的表达；

2.经验学习并从经验中获取知识；

3.不一致信息的分析；

4.根据不确定，不完整的知识进行推理；

5.在保留信息的前提下进行数据化简；

6.识别并评估数据之间的依赖关系。

神经网络样本化简

人工神经网络具有并行处理，高度容错和泛化能力强的特点，适合应用在预测，复杂对象建模和控制等场合. 但是当神经网络规模较大，样本较多时，训练时间过于漫长，这个固有缺点是制约神经网络进一步实用化的一个主要因素. 虽然各种提高训练速度的算法不断出现，问题远未彻底解决。化简训练样本集，消除冗余数据是另一条提高训练速度的途径。

控制算法获取

实际系统中有很多复杂对象难于建立严格的数学模型，这样传统的基于数学模型的控制方法就难以奏效. 模糊控制模拟人的模糊推理和决策过程，将操作人员的控制经验总结为一系列语言控制规则，具有鲁棒性和简单性的特点，在工业控制等领域发展较快. 但是有些复杂对象的控制规则难以人工提取，这样就在一定程度上限制了模糊控制的应用.

粗糙集理论处理这些数据，分析操作人员在何种条件下采取何种控制策略，总结出一系列控制规则：

规则1 IF Condit ion 1 满足 THEN 采取decision 1

规则2 IF Condit ion 2 满足 THEN 采取decision 2

规则3 IF Condit ion 3 满足 THEN 采取decision 3

这种根据观测数据获得控制策略的方法通常被称为从范例中学习（learning from examples). 粗糙控制（rough control) 与模糊控制都是基于知识，基于规则的控制，但粗糙控制更加简单迅速，实现容易（因为粗糙控制有时可省却模糊化及去模糊化步骤）；另一个优点在于控制算法可以完全来自数据本身，所以从软件工程的角度看，其决策和推理过程与模糊（或神经网络）控制相比可以很容易被检验和证实（validate). 有研究指出在特别要求控制器结构与算法简单的场合，更适合采取粗糙控制。

决策支持系统

面对大量的信息以及各种不确定因素，要作出科学，合理的决策是非常困难的.决策支持系统是一组协助制定决策的工具，其重要特征就是能够执行IF THEN 规则进行判断分析. 粗糙集理论可以在分析以往大量经验数据的基础上找到这些规则，基于粗糙集的决策支持系统在这方面弥补了常规决策方法的不足，允许决策对象中存在一些不太明确，不太完整的属性，并经过推理得出基本上肯定的结论。

下面举一个例子，说明粗糙集理论可以根据以往的病例归纳出诊断规则，帮助医生作出判断。下表描述了八个病人的症状. 从下表中可以归纳出以下几条确定的规则：

1. IF （体温正常） THEN （没感冒）

⒉ IF （头痛） AND （体温高） THEN （感冒）

⒊ IF （头痛） AND （体温很高） THEN （感冒）

还有几条可能的规则：

⒋ IF （头不痛） THEN （可能没感冒）

⒌ IF （体温高） THEN （可能感冒了）

⒍ IF （体温很高） THEN （可能感冒了）

病人5 和病人7，病人6 和病人8，症状相同，但是一个感冒另一个却没感冒，这种情况称为不一致（inconsistent）. 粗糙集就是靠这种IF THEN 规则的形式表示数据中蕴含的知识.

希腊工业发展银行ETEVA 用粗糙集理论协助制订信贷政策，从大量实例中抽取出的规则条理清晰，得到了金融专家的好评.

从数据库中知识发现

现代社会中，随着信息产业的迅速发展，大量来自金融，医疗，科研等不同领域的信息被存储在数据库中. 这些浩如烟海的数据间隐含着许多有价值的但鲜为人知的相关性，例如股票的价格和一些经济指数有什么关系；手术前病人的病理指标可能与手术是否成功存在某种联系；满足何种条件的夜空会出现彗星等天文现象等等. 由于数据库的庞大，人工处理这些数据几乎是不可能的，于是出现了一个新的研究方向—数据库中的知识发现（Knowledge Discovery in Databases,KDD），也叫做数据库（信息）发掘（Mining），它是目前国际上人工智能领域中研究较为活跃的分支.粗糙集是其中的一种重要的研究方法，它采用的信息表与关系数据库中的关系数据模型很相似，这样就便于将基于粗糙集的算法嵌入数据库管理系统中. 粗糙集引入核（core），化简（reduct）等有力的概念与方法，从数据中导出用IF THEN 规则形式描述的知识，这些精练的知识更便于存储和使用。

其它