Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 五）：粗糙集
发信站: 哈工大紫丁香 (2001年06月14日16:06:48 星期四), 站内信件

粗糙集方法
　
粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家Z. Pawlak在1
982年首先提出。知识工程研究中，一直存在着信息的含糊性（vagueness）等问题，含
糊性有三种，术语的模糊性，如高矮；数据的不确定性，如噪声引起的；知识自身的不
确定性，如规则的前后件间的依赖关系并不是完全可靠的。人工智能的基础理论之一－
经典逻辑不足以解决这些不确定性问题。为此，人们提出了一些解决方法，包括统计方
法、模糊集理论，以及Dempster-Shaffer证据理论，但这些方法都有一些内在缺陷或限
定范围；例如，基于统计的方法在理论上还令人难以信服，而模糊集方法则存在一个本
质问题即如何确定成员隶属度。相比之下，粗糙集方法则有几个优点：不需要预先知道
的额外信息，如统计中要求的先验概率和模糊集中要求的隶属度；算法简单、易于操作
。
随着KDD的兴起，粗糙集理论也受到KDD研究者的重视进而受到研究界的广为注意。粗糙
集和KDD关系密切，它为KDD提供了一种新的方法和工具。首先，KDD 研究的实施对象多
为关系型数据库。关系表可被看作为粗糙集理论中的决策表，这给粗糙集方法的应用带
来极大的方便。第二，现实世界中的规则有确定性的，也有不确定性的。从数据库中发
现不确定性的知识，为粗糙集方法提供了用武之地。第三，从数据中发现异常，排除知
识发现过程中的噪声干扰也是粗糙集方法的特长。第四，运用粗糙集方法得到的知识发
现算法有利于并行执行，这可极大地提高发现效率。对于大规模数据库中的知识发现来
说，这正是求之不得的。第五，KDD中采用的其它技术，如神经网络的方法，不能自动地
选择合适的属性集，而利用粗糙集方法进行预处理，去掉多余属性，可提高发现效率，
降低错误率。第六，粗糙集方法比模糊集方法或神经网络方法在得到的决策规则和推理
过程方面更易于被证实和检测。
粗糙集基本概念
粗糙集的研究主要基于分类。分类和概念（concept）同义，一种类别对应于一个概念（
类别一般表示为外延即集合，而概念常以内涵的形式表示如规则描述）。知识由概念组
成，如果某知识中含有不精确概念，则该知识不精确。粗糙集对不精确概念的描述方法
是：通过上近似概念和下近似概念这两个精确概念来表示。一个概念（或集合）的下近
似（lower approximation）概念（或集合）指的是，其下近似中的元素肯定属于该概念
；一个概念（或集合）的上近似（upper approximation）概念（或集合）指的是，其上
近似中的元素可能属于该概念。
信息系统（information system）：粗糙集把客观世界或对象世界抽象为一个信息系统
，也称属性－值系统。一个信息系统Ｓ是一个四元组Ｓ＝＜Ｕ，Ａ，Ｖ，ｆ＞。其中，
U是对象（或事例）的有限集合，U＝{x1,x2,...,xn}；A是属性的有限集合，A＝{A1,A2
,...Am}；V是属性的值域集，V＝{V1,V2,...,Vm}，其中Vi是属性Ai的值域。f是信息函
数（information function），ｆ：Ｕ×Ａ? Ｖ，f(xi,Aj)∈Vj。属性集A常常又划分为
两个集合C和D，A＝C∪D，C∩D＝? ，C表示条件属性集，D表示决策属性集。D一般只有
一个属性。
近似空间（approximation space）：近似空间是一个二元组＜Ｕ，Ｒ(Ｂ)＞，U同上，
B是A的属性子集，R(B)是U上的二元等价关系，R(B) = {(x1,x2)|f(x1,b)=f(x2,b)，fo
r any b in B}。R(B)也称无区别关系（indiscernibility relation）。R(B)把U划分为
k个等价类X1,X2,...,Xk，记R*(B) = {X1,X2,...,Xk}。若无特别指明，后文中的R(B)有
时将简称为R，R*(B)简称为R*。对任意的x1,x2∈Xi，有(x1,x2)∈R；对任意的x1∈Xi,
 x2∈Xj, i1 j，有(x1,x2)? not∈ R。对于归纳或分类学习，要学习的概念一般根据决
策属性集D来划分，每个概念是R(D)上的一个等价类，共有#(R*(D))个概念。
下近似，上近似: 对任意一个概念（或集合）O，B是U的一个子集，对其作如下定义：O
的下近似定义为：，[x]R(B)表示x在R(B)上的等价类。O的上近似定义为：。
约简或归约子（reduct）：设有两个属性集B1,B2，B1是B2的真子集，如果R(B1) = R(B
2)，则称B2可归约为B1。如果属性集B不可进一步归约，则称B是U的一个约简或归约子。
核（core）：U的所有约简的交集称为核。核可能为空。
属性依赖度： 设有两个属性集P和Q，则P对Q的依赖度定义为：其中，表示集合X在属性
集上的下近似。
属性重要度（attributes significance）：设属性集Bí C，C是条件属性集，D是决策
属性集，则属性依赖度定义为：，表明从C中去除B后对分类决策的影响程度。
极大属性集与极小极大规则转换模型
约简是粗糙集中一个非常重要的概念。针对约简，我们提出了极大属性集的概念。约简
即极小属性集，去掉约简中的任何一个属性，都将使得该属性集对应的规则覆盖反例，
即导致规则与例子的不一致。而对于极大属性集，向它加入任何一个不属于它的属性，
则会使得该属性集对应的规则覆盖更少的正例。我们称约简对应的规则为极小规则，极
大属性集对应的规则为极大规则。极大规则学习方法相对于极小规则学习具有以下几个
优点：⑴可以发现尽可能多的与类或概念相关的特征；⑵可以避免仅用最小特征集来区
分概念而导致忽视其他同等重要的特征；⑶当有效的相关特征较多时，可以改进预测精
度；⑷在数据稀疏情况下极小原则容易造成过分泛化。
基于极小规则和极大规则的概念，我们又提出了极小极大规则转换模型。在该模型中，
极小规则和极大规则能相互生成。一般来说，极小和极大规则都不是唯一的；另外，我
们常常希望获得的极小规则具有尽可能的简洁形式（即极小属性集尽可能的小），这也
是机器学习中很多归纳学习方法所追求的目标之一。由于在生成规则时要使用启发式的
属性选择方法进行搜索，而各种选择方法都是一种偏向（bias），有各自的特点和适用
范围。极小极大模型为融合或综合各种偏向提供了一种解决方案。通过使用该模型，我
们能获得相当好的简化规则，另外在处理不同特点的数据时都能获得较好的结果。
连续属性离散化
机器学习学习中很多方法要求属性是离散的（discrete），特别是粗糙集方法只能处理
离散的属性，而实际中很多属性是连续值的（continuous）。因此有必要对连续属性进
行离散化。离散属性也称符号的（symbolic）、或名称的（nominal）、或类别的（cat
egorical）；连续属性也称实数的（real）、或有序的（ordered）、或数值的（numer
ical）。
连续属性离散化的方法有很多种，我们认为可以从三个不同的角度对其进行分门别类。
①是否自动离散化：完全由人手工离散化，完全由机器自动离散化，机器辅助人离散化
。一般地，离散化是指机器自动离散化。②是否与分类或决策类别有关：一是考虑分类
类别；另一是不考虑分类类别，这种方法可用于非监督学习或概念聚类学习，不过当用
于带有类别标记的分类学习时效果肯定不会好于上面的方法。不考虑类别的离散化方法
一般有这样几种：等宽区间法（equal-width-intervals）、等频区间法（equal-frequ
ency-intervals）和最大熵法（maximum entropy）。③从与类别有关的离散化策略上来
分：划分法（splitting）和归并法（merging），具体见下面小节。
划分法的思路是，初始把整个属性取值范围作为一个离散属性值（它与该段区间对应）
，然后对该区间进行划分，一般是一分为二，即把一个区间分为两个相邻的区间，每个
区间对应一个离散的属性值，该划分可以一直进行下去，直到满足某种停机条件，如该
区间上所有的类别都是同一类。划分法又分动态型和静态型（或预处理型）；而归并法
只有静态型。动态划分主要与决策树有关，它是一边生成决策树，一边进行连续值区间
的划分；具体说，决策树法在选择属性-值时，对于连续属性，它要寻找一个划分点（c
ut-point），该点把该属性的连续区间划分为两个区间；由于属性-值的选择是随着树的
生成而动态变化的，因此该离散化方法属于动态划分法。
归并法的思路是，初始把整个属性值区间当作一个离散的属性值，然后逐个反复合并相
邻的属性值（即连续值区间），直到满足某种停机条件。归并法的实现有两个影响要素
。一是如何判断是否该归并相邻区间，二是最终的停机判断。
判断相邻区间归并的方法有两种：一是基于c 2统计意义的判断方法ChiMerge；另一是我
们提出的基于值差别度量的判断VDMerge（Value-Difference-Metric Based Merging)，
值差别度量原本用于求离散属性值间的距离，但反过来却可用于连续属性的离散化上。
停机判断是：不存在满足上述归并条件的相邻区间（但如果区间数超过了用户给定的最
大离散属性值数则还继续归并）。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]