粗糙集理论及其应用.ppt

1、2020/6/19,1,粗糙集理论及其应用,2020/6/19,2,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究粗糙集的扩展模型在文本分类中的应用现有工具简介,2020/6/19,3,粗糙集发展历程,1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。1982年，Pawlak发表经典论文Roughsets，标志着该理论正式诞生。1991年，Pawlak的第一本关于粗糙集理论的专著Roughsets:t

2、heoreticalaspectsofreasoningaboutdata；,2020/6/19,4,粗糙集发展历程,1992年，Slowinski主编的Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的Foundationofcomputinganddecisionsciences上。1995年，Pawlak等人在ACMCo

3、mmunications上发表“Roughsets”，极大地扩大了该理论的国际影响。,2020/6/19,5,粗糙集发展历程,19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。20012002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（年会）。2005年，在加拿大召开RSFDGrC国际会议（年会）。,2020/6/19,6,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究粗糙集的扩展模型在文本分类中的应用现有工具简介,2020/6/1

4、9,7,粗糙集的基本理论介绍,主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观【说明】：Bayes理论（先验分布）、证据理论（隶属度函数）等都需要先验知识，具有很大的主观性。,2020/6/19,8,粗糙集理论在知识发现中的作用,在数据预处理过程中，粗糙集理论可以用于对特征更准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。,2020/6/19,9,粗糙集理论的基本概念,“知识”的定义使用等价关系集R对离散表示的空间U进行

5、划分，知识就是R对U划分的结果。“知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R),2020/6/19,10,粗糙集理论的基本概念,“信息系统”的形式化定义S=U,A,V,f，U：对象的有限集A：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集V：，Vp是属性P的域f：UAV是总函数，使得对每个xiU,qA,有f(xi,q)Vq一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“对象”。,2020/6/19,11,粗糙集理论的基本概念,设PA，xi,xjU,定义二元关系INDP称为等价关系：称xi,xj在S中关于属性集P是等价的，当且仅当p

6、(xi)=p(xj)对所有的pP成立，即xi,xj不能用P中的属性加以区别。,2020/6/19,12,等价关系示例：,2020/6/19,13,等价关系示例：,可知，U=1,2,3,4,5,6R=2weather,road,time,accident若P=weather,road，则xIND(P)=xINDweatherxINProad=1,3,6,2,5,41,2,4,3,5,6=1,2,4,3,6,5,2020/6/19,14,集合的上近似k=1,2,.,m)第4步.将P转化为析取范式形式；第5步.根据需要选择满意的属性组合.如需属性数最少，可直接选择合取式中属性数最少的组合；如需规则最

7、简或数据约简量最大，则需先进行属性值约简.观看演示,2020/6/19,24,利用区分矩阵进行属性约简,实例：T=（U，A，V，f），A=a,b,c,de,2020/6/19,25,a,c,d,a,d,a,c,d,a,d,a,b,d,利用区分矩阵进行属性约简,区分矩阵：,2020/6/19,26,利用区分矩阵进行属性约简,由上述差别矩阵很容易得到核为：c区分函数fM(S)为：c(ad)，即(ac)(cd)得到两个约简a,c和c,d,2020/6/19,27,利用区分矩阵进行属性约简,根据得到的两个约简，可得两个约简后的新决策表：,2020/6/19,28,利用启发式搜索进行属性约简,几个概念：

8、正区域：在信息系统S=(U,CD,V,f)中，设D*=X1,X2,Xm，属性子集PC关于决策属性D的“正区域”定义为：,P关于D的正区域表示那些根据属性子集P就能分入正确类别的所有对象。,2020/6/19,29,利用启发式搜索进行属性约简,相关程度：条件属性子集PC与决策属性D的相关程度（也称依赖程度）定义为：,显然，0k(P,D)1。k(P,D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。,2020/6/19,30,利用启发式搜索进行属性约简,有效值：一个属性pPC的有效值(significantvalue)定义为：,【说明】：属性p的有效值越大，说明其对条件属性与

9、决策属性之间的影响越大，即其重要性也越大。,2020/6/19,31,利用启发式搜索进行属性约简,性质1：若MNC，则POSM（D）POSN（D）性质2：MNC，XU，则对任意xU，若xPOSM（D），则xPOSN（D）.,2020/6/19,32,利用启发式搜索进行属性约简,算法步骤：第1步.aA:计算邻域关系a;第2步.将赋给red；第3步.对任意aiA-red，计算/此处定义K(D)=0第4步.选择ak，其满足:SIG(ak,red,D)=maxi(SIG(ai,red,D)）第5步.如果SIG(ak,red,D)0,将redUak赋给red，返回第3步；否则，返回red，结束。观看演示

10、,2020/6/19,33,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究粗糙集的扩展模型在文本分类中的应用现有工具简介,2020/6/19,34,经典粗糙集存在的问题,经典粗糙集理论的主要存在的问题是：1)对原始数据本身的模糊性缺乏相应的处理力；2)对于粗糙集的边界区域的刻画过于简单；3)对属性为连续数值的情况缺乏好的解决办法。,2020/6/19,35,可变精度粗糙集模型,W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界区域和负区域。下面扼要地介绍其思想：一般地，集合X包含于Y并未反映出集合X

11、的元素属于集合Y的“多少”。为此，VPRS定义了它的量度：C(X,Y)=1card(XY)/card(X)当card(x)0，C(X,Y)=0当card(x)=0。C(X,Y)表示把集合X归类于集合Y的误分类度，即有C(X,Y)100%的元素归类错误。显然，C(X,Y)=0时有XY。如此，可事先给定一错误分类率(00.5)，基于上述定义，我们有XY，当且仅当C(X,Y)。,2020/6/19,36,可变精度粗糙集模型,在此基础上，设U为论域且R为U上的等价关系，U/R=A=X1,X2,Ak，这样，可定义集合X的-下近似为RX=Xi(C(Xi,X),i=1,2,k)，并且RX称为集合X的-正区域

12、，集合X的-上近似为RX=Xi(C(Xi,X)1,i=1,2,k)，这样，-边界区域就定义为：BNRX=Xi(C(Xi,X)1)；-负区域为：NEGRX=Xi(C(Xi,X)1)。以此类推，我们还可以定义-依赖、-约简等与传统粗糙集模型相对应的概念。,2020/6/19,37,相似模型,在数据中存在缺失的属性值的时候（在数据库中很普遍），等价关系无法处理这种情形。为扩展粗糙集的能力，有许多作者提出了用相似关系来代替等价关系作为粗糙集的基础。在使用相似关系代替粗糙集的等价关系后，最重要的变化就是相似类不再形成对集合的划分了，它们之间是相互重叠的。类似于等价类，可以定义相似集，即所有和某各元素x在

13、属性集合B上相似的集合SIMb(x)。值得注意的是SIMb(x)中的元素不一定属于同一决策类，因此还需要定义相似决策类，即相似集对应的决策类集合。,2020/6/19,38,邻域模型,作为一种有效的粒度计算模型，Pawlak粗糙集定义在经典的等价关系和等价类基础上，只适合于处理名义型变量，对于现实应用中广泛存在的数值型数据却不能直接处理。在金融、医疗、科研和工程应用领域数值型变量无处不在，如振动分析中的频谱信号，变压器状态分析中的温度、电流、电压信号等，研究人员在引入粗糙集等机器学习方法来处理该类数据时，往往采用离散化算法把数值型属性转化为符号型属性。这一转换不可避免地带来了信息损失，计算处理

14、的结果很大程度上取决于离散化的效果。,2020/6/19,39,邻域模型,为解决上述问题，有人提出了邻域粗糙集模型。该模型以实数空间中的每一个点形成一个邻域，邻域族构成了描述空间中任一概念的基本信息粒子。对于空间中的任一子集，通过基本邻域信息粒子进行逼近，并由此提出了邻域信息系统和邻域决策表模型。,2020/6/19,40,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究粗糙集的扩展模型在文本分类中的应用现有工具简介,2020/6/19,41,基于粗糙集的文本分类,利用可变精度粗糙集模型中的分类质量构造新的特征词权重计算公式。这种加权方法,相对于广泛使用的逆文本频率加权方法

15、,大大改进了文本样本在整个空间中的分布,使得类内距离减少,类间距离增大,在理论上将提高样本的可分性。,2020/6/19,42,逆文本频率加权,SparkJones提出的逆文本频率加权方法是目前广泛采用的一种。对于训练样本集k个文本U=x1,x2,xk,l个特征词T=T1,T2,Tl,加权公式为:,2020/6/19,43,逆文本频率加权,n表示训练文本中出现第j个特征词的文本数,N代表所有训练文本的个数。第j个特征词的权重为log(N/n),表示的是特征词在越多的文本中出现,其对分类的区分性越差,其重要度则越小。如果此特征词在所有的文本中都出现了,则其加权值0。特征词的重要性正比于词频,反比

16、于训练文本中出现该特征词的文本频率。,2020/6/19,44,粗糙集加权,类比于逆文本频率权重计算公式,我们可以构造基于可变精度粗糙集模型的加权公式:wij表示第j个特征词在第i篇文本中的权重,Tfij表示第j个特征词在第i篇文本中的出现频率,即特征词的局部权重;j(U)为此特征词在整个语料库中对分类的重要程度,即全局权重,2020/6/19,45,粗糙集加权与逆文本频率加权的对比,逆文本频率加权方法刻画的只是特征词在整个训练样本集的分布重要程度,是从整体的分类角度考虑的。而基于粗糙集模型的加权,将分类决策引入到特征词权重中,先计算特征词的划分与各类决策划分的一致程度,再求和计算特征词与整体

17、决策的一致程度。这是从特征词对各类的分类重要程度来集中体现整体的权重的,充分体现了特征词对于各个分类的重要信息。,2020/6/19,46,主要内容,粗糙集发展历程粗糙集的基本理论介绍粗糙集的属性约简算法研究粗糙集的扩展模型在文本分类中的应用现有工具简介,2020/6/19,47,粗糙集的实验系统,在过去几年中，建立了不少基于粗糙集的KDD系统，其中最有代表性的有ROSE2、R-OSETTA等。,2020/6/19,48,粗糙集的实验系统,1ROSE2波兰Poznan科技大学基于粗糙集开发了ROSE(RoughSetdataExplorer),用于决策分析。它是RoughDas&RoughClass系统的新版，其中Rou