粗糙集理论整理

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


多年来,研究人员一直在努力寻找科学地处理不完整性和不确定性的有效途径。模糊集和基于概率方法的证据理论是处理不确定信息的两种方法,已应用于一些实际领域。但这些方法有时需要一些数据的附加信息或先验知识,如模糊隶属函数、基本概率指派函数和有关统计概率分布等,而这些信息有时并不容易得到。
1982年波兰学者Z. Paw lak 提出了粗糙集理论——它是一种刻画不完整性和不确定性的数学工具,能有效地分析不精确,不一致(inconsistent)、不完整(incomplete) 等各种不完备的信息,还可以对数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律。

基本概念

知识

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

不可分辨关系

分类过程中,相差不大的个体被归于同一类,它们的关系就是不可分辨关系(indiscernibility relation). 假定只用两种黑白颜色把空间中的物体分割两类,{黑色物体},{白色物体},那么同为黑色的两个物体就是不可分辨的,因为描述它们特征属性的信息相同,都是黑色.
如果再引入方,圆的属性,又可以将物体进一步分割为四类: {黑色方物体},{黑色圆物体},{白色方物体},{白色圆物体}. 这时,如果两个同为黑色方物体,则它们还是不可分辨的. 不可分辨关系是一种等效关系(equivalence relationship),两个白色圆物体间的不可分辨关系可以理解为它们在白,圆两种属性下存在等效关系.

基本集

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

集合

粗糙集理论延拓了经典的集合论,把用于分类的知识嵌入集合内,作为集合组成的一部分. 一个对象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) 描述论域中的数据集合. 根据学科领域的不同,它们可能代表医疗,金融,军事,过程控制等方面的数据. 信息表的形式和大家所熟悉的关系数据库中的关系数据模型很相似,是一张二维表格,如下表所示:

姓名 教育程度 是否找到了好工作

王治|高中|否
马丽|高中|是
李得|小学|否
刘保|大学|是
赵凯|博士|是
表格的数据描述了一些人的教育程度以及是否找到了较好工作,旨在说明两者之间的关系. 其中王治,马丽,赵凯等称为对象(objects),一行描述一个对象. 表中的列描述对象的属性. 粗糙集理论中有两种属性: 条件属性(condition attribute) 和决策属性(decision attribute). 本例中”教育程度”为条件属性;”是否找到了好工作”为决策属性。
设O 表示找到了好工作的人的集合,则O = {马丽,刘保,赵凯},设I 表示属性”教育 程度”所构成的一个等效关系,根据教育程度的不同,该论域被分割为四个等效类: {王治,马丽},{李得},{刘保},{赵凯}. 王治和马丽在 同一个等效类中,他们都为高中文化程度,是 不可分辨的. 则:
集合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) 它能产生精确而又易于检查和证实的规则,特别适于智能控制中规则的自动生成

决策支持系统

面对大量的信息以及各种不确定因素,要作出科学,合理的决策是非常困难的.决策支持系统是一组协助制定决策的工具,其重要特征就是能够执行IF THEN 规则进行判断分析. 粗糙集理论可以在分析以往大量经验数据的基础上找到这些规则,基于粗糙集的决策支持系统在这方面弥补了常规决策方法的不足,允许决策对象中存在一些不太明确,不太完整的属性,并经过推理得出基本上肯定的结论。[7]
下面举一个例子,说明粗糙集理论可以根据以往的病例归纳出诊断规则,帮助医生作出判断。下表描述了八个病人的症状. 从下表中可以归纳出以下几条确定的规则:

病人编号 病理症状诊断结果
是否头痛 体温 是否感冒
病人1 正常
病人2
病人3 很高
病人4 正常
病人5
病人6 很高
病人7
病人8 很高

1.IF (体温正常) THEN (没感冒)
2.IF (头痛) AND (体温高) THEN (感冒)
3.IF (头痛) AND (体温很高) THEN (感冒)

还有几条可能的规则:

4.IF (头不痛) THEN (可能没感冒)
5.IF (体温高) THEN (可能感冒了)
6.IF (体温很高) THEN (可能感冒了)

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

参考资料

  1. 粗糙集
  2. 模糊集合
  3. 论域
  4. 粗糙集的概念和一些例子