粗糙集理论及其应用

《粗糙集理论及其应用》由会员分享，可在线阅读，更多相关《粗糙集理论及其应用（51页珍藏版）》请在装配图网上搜索。

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

2、ts: theoretical aspects of reasoning about data；2021-9-244粗糙集发展历程 1992年，Slowinski主编的Intelligence decision support: handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。 1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的 Foundation of computingand decision scienc

3、es上。 1995年，Pawlak等人在ACM Communications上发表“Rough sets”，极大地扩大了该理论的国际影响。2021-9-245粗糙集发展历程 19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。 20012002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。 2003年，在重庆召开粗糙集与软计算国际研讨会。 2004年，在瑞典召开RSCTC国际会议（年会） 。 2005年，在加拿大召开RSFDGrC国际会议（年会）。 2021-9-246主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙

4、集的扩展模型 在文本分类中的应用 现有工具简介2021-9-247粗糙集的基本理论介绍粗糙集的基本理论介绍 主要优点主要优点n除数据集之外，无需任何先验知识（或信息）n对不确定性的描述与处理相对客观n【说明】：Bayes理论（先验分布 ）、证据理论（隶属度函数）等都需要先验知识，具有很大的主观性。2021-9-248粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用 在数据预处理过程中，粗糙集理论可以用于对特征更对特征更准确的提取准确的提取 在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。对数据集进行降维操作。 在数据挖掘阶段，可将粗糙集理论用于分类规则的发用于分类

5、规则的发现。现。 在解释与评估过程中，粗糙集理论可用于对所得到的对所得到的结果进行统计评估结果进行统计评估。2021-9-249粗糙集理论的基本概念粗糙集理论的基本概念“知识知识”的定义n使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库知识库”的形式化定义n等价关系集R中所有可能的关系对U的划分n表示为：K = (U, R)2021-9-2410粗糙集理论的基本概念粗糙集理论的基本概念“信息系统信息系统”的形式化定义的形式化定义nS = U, A, V, f，nU：对象的有限集nA：属性的有限集，A=CD，C是条件属性子集，D是决策属性子集nV： ， Vp是属性P

6、的域nf：U A V是总函数，使得 对每个xi U, q A, 有f(xi, q) Vq一个关系数据库可看作一个信息系统，其一个关系数据库可看作一个信息系统，其“列列”为为“属性属性”，“行行”为为“对象对象”。PApVV 2021-9-2411粗糙集理论的基本概念粗糙集理论的基本概念 设PA， xi, xj U, 定义二元关系INDP称为等价关系等价关系： 称xi, xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP 成立，即xi, xj不能用P 中的属性加以区别。)()(,|),()(jijixpxpPpUUxxPIND2021-9-2412等价关系示例：factw

7、eatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno2021-9-2413等价关系示例：可知，U = 1, 2, 3, 4, 5, 6R = 2 weather, road, time, accident 若P = weather, road，则x IND(P) = x INDweather x INProad = 1, 3, 6, 2, 5, 4 1, 2, 4, 3, 5, 6 = 1,

8、 2, 4, 3, 6, 5 2021-9-2414集合的上近似集合的上近似 & & 下近似下近似 在信息系统S = U, A, V, f中，设XU是个体全域上的子集，PA，则X的下和上近似集及边界区域分别为：:/XYPUYXP:/XYPUYXPXPXPXBndP)( X是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集； X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。BndP(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。PP2021-9-2415集合的上、下近似概念示意图 XAprA XAprAX2021-9-2416上、下近似关系举例上、下

9、近似关系举例： X1 = u | Flu(u) = yes = u2, u3, u6, u7 RX1 = u2, u3 = u2, u3, u6, u7, u5, u8X2 = u | Flu(u) = no = u1, u4, u5, u8RX2 = u1, u4 = u1, u4, u5, u8, u6, u7X2RU Headache Temp. Flu U1 Yes Normal No U2 Yes High Yes U3 Yes Very-high Yes U4 No Normal No U5 N N No o o H H Hi i ig g gh h h N N No o o U6

10、 No Very-high Yes U7 N N No o o H H Hi i ig g gh h h Y Y Ye e es s s U8 No Very-high No 由R = Headache, Temp. 划分出来的等价类有:u1, u2, u3, u4, u5, u7, u6, u8.X1R2021-9-2417近似精度近似精度 & & 分类质量分类质量 设S = U, A, V, f为一信息系统，且XU， PA，则S上X的近似精度近似精度为：)()()()()(XPcardXPcardXXXPPP 注：card(X) 表示集合X中元素个数 设S为一信息系统，PA，且令=X1,X

11、2, , Xn是U的一个分类（子集族），其中XiU，则的P-下近似和 P-上近似分别表示为：,21nXPXPXPP,21nXPXPXPP2021-9-2418近似精度近似精度 & & 分类质量分类质量由属性子集PA确定的分类的分类质量分类质量为 ：)()()(1UcardXPcardiniP 分类质量分类质量表示通过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。 2021-9-2419属性约简属性约简 & “& “核核” 属性约简属性约简(Attribute Reduction)：在一个信息系统S中，设是S上的一个分类，经约简后的最小属性子集

12、具有同原始属性集相同的分类质量，即存在RPQ，使得R() =P() ，称之为属性集属性集P P的的 - -约简约简，记作REDU(P) 。 所有-约简的交集称为 - -核核，即CORE(P) = REDU(P)，核是信息系统中一系列最重要的属性之一。 【说明】：【说明】：在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属性约简及核的概念为提取系统中重要属性及其值提供了有力的属性约简及核的概念为提取系统中重要属性及其值提供了有力的数学工具数学工具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。 2021-9-242

13、0主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型 在文本分类中的应用 现有工具简介2021-9-2421利用区分矩阵进行属性约简区分矩阵区分矩阵（discernibilitydiscernibility matrix matrix）：）：在信息系统T= (U, CD, V, f)中，C为条件属性，D为决策属性，设对象全集U按决策属性D被分成不相交的类族，即X1,X2,Xm，则S中C的区分矩阵M(C)= mi,jnxn定义为：, , 1, , ( , )( ,) : ( , )( ,), ,iji jijijijijx xDmx xDcC f c xf

14、 c xcC f c xf c xx xD 的同一等价类的不同等价类，对 的不同等价类其中，1 i j n。 2021-9-2422利用区分矩阵进行属性约简 令M是决策表T的可辨识矩阵，A=a1,a2,.,an,是T中所有条件属性的集合.S是M中所有属性组合的集合，且S中不包含重复项.令S中包含有s个属性组合，每个属性组合表示为Bi，其公式化描述为: BiS, BjS, BiBj (i,j=1,2,.,s). 令Card(Bi)=m，则Bi中每个条件属性表示为 bi,k Bi (k=1,2,.,m) 令C0是M中的核属性集，则有C0 A.2021-9-2423利用区分矩阵进行属性约简算法步骤算

15、法步骤： 第1步. 将核属性列入属性约简后得到的属性集合，即red=C0； 第2步. 在可辨识矩阵中找出所有不包含核属性的属性组合S，即 第3步. 将属性组合S与red表示为合取范式的形式，即 P=red bi,k :(i=1,2,.,s;k=1,2,.,m)第4步. 将P转化为析取范式形式；第5步. 根据需要选择满意的属性组合.如需属性数最少，可直接选择合取式中属性数最少的组合；如需规则最简或数据约简量最大，则需先进行属性值约简.观看演示观看演示, 2 , 1,:siredBBSii2021-9-2424利用区分矩阵进行属性约简U/Aabcdeu110210u200121u320210u40

16、0222u511210实例：T=（U，A，V，f），A=a,b,c,de 2021-9-2425uu1u2u3u4u5u1 u2 ca, b, c, du3 u4 u5 a, c, da, da, c, da, da, b, d利用区分矩阵进行属性约简区分矩阵：2021-9-2426利用区分矩阵进行属性约简 由上述差别矩阵很容易得到核为： c 区分函数fM(S)为：c(ad)，即 (ac)(cd) 得到两个约简 a, c和c, d 2021-9-2427利用区分矩阵进行属性约简UAaceu1120u2011u3220u4022u5120UAcdeu1210u2121u3210u4222U521

17、0根据得到的两个约简，可得两个约简后的新决策表：2021-9-2428利用启发式搜索进行属性约简几个概念：正区域：正区域：在信息系统S=(U, CD, V, f)中，设D*= X1,X2,Xm，属性子集PC关于决策属性D的“正区域”定义为： :)(*DXXBDPOSP P关于D的正区域表示那些根据属性子集P就能分入正确类别的所有对象。2021-9-2429利用启发式搜索进行属性约简相关程度：相关程度： 条件属性子集PC与决策属性D的相关程度（也称依依赖程度赖程度）定义为：)()(),(UcardDPOScardDPkP 显然，0 k(P, D) 1。k(P, D)为计算条件属性子集P与决策属性

18、D之间的相关程度提供了非常有力的手段。2021-9-2430利用启发式搜索进行属性约简有效值：有效值： 一个属性pPC的有效值(significant value)定义为：),(),(),(DpPKDPkDPpSGF)()()(UcardDPOScardDPOScardpPP【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。 2021-9-2431利用启发式搜索进行属性约简性质1： 若M N C，则POS M （D） POSN （D）性质2： M N C ，X U，则对任意x U，若x POS M （D） ，则x POSN （D）. 2021-9-243

19、2利用启发式搜索进行属性约简算法步骤算法步骤： 第1步. a A: 计算邻域关系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 ,将red U ak 赋给red ， 返回第3步； 否则，返回red，结束。观看演示观看演示)()(),(DKDKDredaSIGredaredii2021-9-2433主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型

20、 在文本分类中的应用 现有工具简介2021-9-2434经典粗糙集存在的问题经典粗糙集理论的主要存在的问题是：1)对原始数据本身的模糊性缺乏相应的处理力；2)对于粗糙集的边界区域的刻画过于简单；3)对属性为连续数值的情况缺乏好的解决办法。2021-9-2435可变精度粗糙集模型 W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界区域和负区域。下面扼要地介绍其思想： 一般地，集合X包含于Y并未反映出集合X的元素属于集合Y的“多少”。为此，VPRS定义了它的量度： C(X, Y)=1card(XY)/card(X) 当car

21、d(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)。2021-9-2436可变精度粗糙集模型在此基础上，设U为论域且R为U上的等价关系，U/R=A=X1, X2, , Ak ，这样，可定义集合X的-下近似下近似为 RX =Xi (C(Xi, X), i=1, 2, , k)， 并且RX称为集合X的-正区域正区域，集合X的-上近似上近似为 RX =Xi (C(Xi, X)1, i

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

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

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

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

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

27、类重要程度来集中体现整体的权重的,充分体现了特征词对于各个分类的重要信息。2021-9-2446主要内容 粗糙集发展历程 粗糙集的基本理论介绍 粗糙集的属性约简算法研究 粗糙集的扩展模型 在文本分类中的应用 现有工具简介2021-9-2447粗糙集的实验系统 在过去几年中，建立了不少基于粗糙集的KDD系统，其中最有代表性的有ROSE2、R-OSETTA等。2021-9-2448粗糙集的实验系统1 1ROSE2ROSE2 波兰Poznan科技大学基于粗糙集开发了ROSE(Rough Set data Explorer), 用于决策分析。 它是Rough Das & Rough Class系统的新版，其中RoughDas执行信息系统数据分析任务，RoughClass支持新对象的分类，这两个系统已经在许多实际领域中得到应用。观看演示观看演示2021-9-2449粗糙集的实验系统2.ROSETTA2.ROSETTA RosettaRosetta是由挪威科技大学Aleksander hrn开发的一个基于Rough集理论框架的表格逻辑数据分析工具包，包括了计算核和图形用户界面。设计实现了对数据挖掘和知识获取。该软件最大的特点就是开源，我们可以轻易的下载到其核心源码以供我们进一步研究。观看演示观看演示2021-9-2450参考资料1、http:/