粗糙集理论及其应用

刘坤*1粗糙集理论及其应用*2主要内容￿￿ 粗糙集发展历程粗糙集的基本理论介绍 ￿￿ 粗糙集的属性约简算法研究 ￿￿ 粗糙集的扩展模型在文本分类中的应用现有工具简介*3粗糙集发展历程1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学 家，在研究信息系统逻辑特性的基础上，提出了粗糙集理 论的思想在最初的几年里，由于大多数研究论文是用波兰文发表 的，所以未引起国际计算机界的重视，研究地域仅限于东 欧各国1982年，Pawlak发表经典论文《Rough sets》，标志着 该理论正式诞生1991年，Pawlak的第一本关于粗糙集理论的专著 《Rough sets: theoretical aspects of reasoning about data》；*4粗糙集发展历程1992年，Slowinski主编的《Intelligence decision support: handbook of applications and advances of rough sets theory》的出版，奠定了粗糙集理论的基础，有 力地推动了国际粗糙集理论与应用的深入研究。

1992年，在波兰召开了第一届国际粗糙集理论研讨会，有 15篇论文发表在1993年第18卷的 《Foundation of computingand decision sciences》上1995年，Pawlak等人在《ACM Communications》上发表 “Rough sets”，极大地扩大了该理论的国际影响5粗糙集发展历程1996～1999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会2001～2002，中国分别在重庆、苏州召开第一、二届粗 糙集与软计算学术会议2003年，在重庆召开粗糙集与软计算国际研讨会2004年，在瑞典召开RSCTC国际会议（年会） 2005年，在加拿大召开RSFDGrC国际会议（年会）……*6主要内容￿￿ 粗糙集发展历程粗糙集的基本理论介绍 ￿￿ 粗糙集的属性约简算法研究 ￿￿ 粗糙集的扩展模型在文本分类中的应用现有工具简介*7粗糙集的基本理论介绍主要优点n除数据集之外，无需任何先验知识（或信息）n对不确定性的描述与处理相对客观n……【说明】：Bayes理论（先验分布 ）、证据理论（隶 属度函数）等都需要先验知识，具有很大的主观性。

8粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对特征更 准确的提取在数据准备过程中，利用粗糙集理论的数据约简特性， 对数据集进行降维操作在数据挖掘阶段，可将粗糙集理论用于分类规则的发 现在解释与评估过程中，粗糙集理论可用于对所得到的 结果进行统计评估9粗糙集理论的基本概念“知识”的定义n使用等价关系集R对离散表示的空间U进行划 分，知识就是R对U划分的结果知识库”的形式化定义n等价关系集R中所有可能的关系对U的划分n表示为：K = (U, R)*10粗糙集理论的基本概念“信息系统”的形式化定义nS = {U, A, V, f}，nU：对象的有限集nA：属性的有限集，A=CD，C是条件属性子集，D是决策属性子 集nV： ， Vp是属性P的域nf：U × A → V是总函数，使得对每个xi  U, q  A, 有f(xi, q)  Vq一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“ 对象”11粗糙集理论的基本概念设PA， xi, xj U, 定义二元关系INDP称为等价关系：称xi, xj在S中关于属性集P是等价的，当且仅当p(xi)=p(xj) 对所有的pP 成立，即xi, xj不能用P 中的属性加以区别。

12等价关系示例：factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno*13等价关系示例：可知， U = {1, 2, 3, 4, 5, 6} R = 2{ weather, road, time, accident } 若P = {weather, road}，则 [x] IND(P) = [x] IND{weather}  [x] INP{road}= { {1, 3, 6}, {2, 5}, {4} }{ {1, 2, 4}, {3, 5, 6}} = { {1}, {2}, {4}, {3, 6}, {5} }*14集合的上近似 k=1,2,.,m)}第4步. 将P转化为析取范式形式；第5步. 根据需要选择满意的属性组合.如需属性数最少，可直接选 择合取式中属性数最少的组合；如需规则最简或数据约简量最大，则需 先进行属性值约简.观看演示*24利用区分矩阵进行属性约简U/Aabcdeu110210u200121u320210u400222u511210实例：T=（U，A，V，f），A={a,b,c,d}∪{e} *25uu1u2u3u4u5u1u2ca, b, c, du3u4u5 a, c, da, da, c, da, da, b, d利用区分矩阵进行属性约简区分矩阵：*26利用区分矩阵进行属性约简由上述差别矩阵很容易得到核为：{c}区分函数fM(S)为：c∧(a∨d)，即(a∧c)∨(c∧d)得到两个约简{a, c}和{c, d} *27利用区分矩阵进行属性约简U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U5210根据得到的两个约简，可得两个约简后的新决策表：*28利用启发式搜索进行属性约简几个概念： 正区域：在信息系统S=(U, CD, V, f)中，设 D*= {X1,X2,…,Xm}，属性子集PC关于决策属性D 的“正区域”定义为： P关于D的正区域表示那些根据属性子集P就能 分入正确类别的所有对象。

29利用启发式搜索进行属性约简相关程度：条件属性子集PC与决策属性D的相关程度（也称依 赖程度）定义为：显然，0  k(P, D)  1k(P, D)为计算条件属性子集 P与决策属性D之间的相关程度提供了非常有力的手段 30利用启发式搜索进行属性约简有效值：一个属性pPC的有效值(significant value)定义为：【说明】：属性p的有效值越大，说明其对条件属性与决 策属性之间的影响越大，即其重要性也越大 *31利用启发式搜索进行属性约简性质1：若M ⊆N ⊆ C，则POS M （D） ⊆ POSN （D） 性质2：M ⊆N ⊆ C ，X ⊆U，则对任意x ∈ U，若x ∈ POS M （D） ，则x ∈ POSN （D）. *32利用启发式搜索进行属性约简算法步骤：第1步. ∀a ∈ A: 计算邻域关系Νa ;第2步. 将∅ 赋给red ；第3步. 对任意ai∈A-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，结束。

观看演示*33主要内容￿￿ 粗糙集发展历程粗糙集的基本理论介绍 ￿￿ 粗糙集的属性约简算法研究 ￿￿ 粗糙集的扩展模型在文本分类中的应用现有工具简介*34经典粗糙集存在的问题经典粗糙集理论的主要存在的问题是： 1)对原始数据本身的模糊性缺乏相应的处理 力； 2)对于粗糙集的边界区域的刻画过于简单； 3)对属性为连续数值的情况缺乏好的解决办 法35可变精度粗糙集模型W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了 错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界 区域和负区域下面扼要地介绍其思想： 一般地，集合X包含于Y并未反映出集合X的元素属于集合Y的“多 少”为此，VPRS定义了它的量度：C(X, Y)=1–card(XY)/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时有XY如此，可事先给定一错误分 类率(0<0.5)，基于上述定义，我们有XY，当且仅当C(X,Y)。

36可变精度粗糙集模型在此基础上，设U为论域且R为U上的等价关系，U/R=A={X1, X2, …,Ak }，这样，可定义集合X的-下近似为RX =Xi (C(Xi, X), i=1, 2, …, k)，并且RX称为集合X的-正区域，集合X的-上近似为RX =Xi (C(Xi, X)<1–, i=1, 2, …, k)， 这样，-边界区域就定义为：BNRX =Xi (

38邻域模型作为一种有效的粒度计算模型，Pawlak 粗糙集定义在 经典的等价关系和等价类基础上，只适合于处理名义型变 量，对于现实应用中广泛存在的数值型数据却不能直接处 理在金融、医疗、科研和工程应用领域数值型变量无处 不在，如振动分析中的频谱信号，变压器状态分析中的温 度、电流、电压信号等，研究人员在引入粗糙集等机器学 习方法来处理该类数据时，往往采用离散化算法把数值型 属性转化为符号型属性这一转换不可避免地带来了信息 损失，计算处理的结果很大程度上取决于离散化的效果39邻域模型为解决上述问题，有人提出了邻域粗糙集模 型该模型以实数空间中的每一个点形成一个δ 邻域，δ邻域族构成了描述空间中任一概念的基 本信息粒子对于空间中的任一子集，通过基本 邻域信息粒子进行逼近，并由此提出了邻域信息 系统和邻域决策表模型40主要内容￿￿ 粗糙集发展历程粗糙集的基本理论介绍 ￿￿ 粗糙集的属性约简算法研究 ￿￿ 粗糙集的扩展模型在文本分类中的应用现有工具简介*41基于粗糙集的文本分类利用可变精度粗糙集模型中的分类质量构造新的特征词权重计算公式这种加权方法,相对于广 泛使用的逆文本频率加权方法,大大改进了文本样 本在整个空间中的分布,使得类内距离减少,类间 距离增大,在理论上将提高样本的可分性。

42逆文本频率加权SparkJones提出的逆文本频率加权方法 是目前广泛采用的一种对于训练样本集k 个文本U={x1,x2,…,xk},l 个特征词T={T1,T2,…,Tl },加权公式为:*43逆文本频率加权n表示训练文本中出现第j个特征词的文本数,N代表所有训练文本的个数第j个特征词的权重为 log(N/n),表示的是特征词在越多的文本中出现, 其对分类的区分性越差,其重要度则越小如果此 特征词在所有的文本中都出现了,则其加权值0 特征词的重要性正比于词频,反比于训练文本中出 现该特征词的文本频率44粗糙集加权类比于逆文本频率权重计算公式,。