粗糙集理论介绍解析

粗糙集理论介绍问题的提出：知识的含糊性术语的模糊性，如高矮数据的不确定性，如噪声知识自身的不确定性，如规则的前后件间的依赖关系不完全可靠不完备性，数据缺失由此，提出了包括概率与统计、证据理论：理论上还难以令人信服，不能处理模糊和不完整的数据模糊集合理论：能处理模糊类数据，但要提供隶属函数（先验知识）粗糙集理论：能处理具有不精确性和不确定性的知识等各种理论和方法模糊集和基于概率方法，有时需要一些数据的附加信息或先验知识,如模糊隶属函数,基本概率指派函数和有关统计概率分布等,而这些信息有时并不容易得到粗糙集无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的粗糙集理论的历史20世纪70年代,波兰数学家Z.Pawlak和一些波兰科学院,波兰华沙大学的逻辑学家们,一起从事关于信息系统逻辑特性的研究.1982.Z.Pawlak发表论文“RoughSet”.宣告RS的诞生1991.Z.Pawlak出版著作“RoughSets:TheoreticalAspectsofReasoningaboutData”1992.召开首次国际研讨会,应用专集.之后得到飞速发展,在数据挖掘,模式识别,粗糙逻辑等方面取得较大进展.粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来(近似)刻画。粗糙集理论的基本观点Outline：粗糙集理论的基本概念粗糙集理论的应用（规则挖掘和属性约简）其他基本概念1信息系统，决策表2知识3等价关系，不可分辨关系与基本集4下、上近似正区域，负区域，边界域5粗糙度6粗糙隶属函数基本概念（1）信息系统信息系统是四元组(U,Q,V,f).其中U是对象集合Q是属性集合（包括条件属性C和决策属性D)，V是属性的值域f是一种映射，反应对象集合之间的值返回UA1A2A3A41001021021311104021151210信息系统实例：其中U＝{1，2，3，4，5}；Q＝{A1,A2,A3,A4};V=VA1∪VA2∪VA3∪VA4＝{0,1,2}f，将对象属性映射到它的值域基本概念（2）：知识RS中，知识被认为是一种分类能力。人们的行为是基于分辨现实的或抽象的对象的能力。那些根据事务的特征差别将其分门别类的能力都可以看作是某种“知识”。论域中相互间不可分辨的对象组成的集合。是组成知识的颗粒（granule）。知识是有粒度的.粒度越小,能精确表达的概念越多.粒度的形式表示:不可分辨关系/等价类.粒度是知识的最小单位。返回基本概念（3）不可分辨关系与基本集不可分辨关系IND(P)/等价关系：分类过程中，相差不大的个体被归于同一类，他们的关系就是不可区分关系。对于任何一个属性集合P，不可分辨关系用IND表示，定义如下：IND(P)＝{(x,y)U×U:f(x,a)=f(y,a),aP}不可分辨关系就是U上的等价关系基本集：由论域中相互间不可区分的对象组成的集合，是组成论域知识的颗粒。例1一玩具积木的集合如下表描述（表1）取不同的属性组合,可得不同的等价关系（粒度)为：IND（R1）＝{{x1,x3,x7},{x2,x4},{x5,x6,x8}}IND（R1,R2）＝{{x1},{x2},{x3,x7},{x4},{x5},{x6},{x8}}R1(颜色)R2(形状)R3(体积)X1红圆形小X2蓝方形大X3红三角形小X4蓝三角形小X5黄圆形小X6黄方形小X7红三角形大X8黄三角形大返回基本概念（4）集合的上近似、下近似和边界区一个对象a是否属于集合X根据现有知识来判断，可分为三种情况：1）a肯定属于集合X2)a可能属于也可能不属于集合X3)a肯定不属于集合X返回LetU为论域（非空对象集合），I为U中的一组等价关系，Then•集合X关于I的下近似（Lowerapproximation）是由那些根据现有知识判断肯定属于X的对象所组成的最大集合，有时也称为X的正区（positiveregion），记做POS（X）•集合X关于I的上近似（Upperapproximation）是由所有与X相交非空的等效类I（x）的并集，是那些可能属于X的对象组成的最小集合。UX如果上下近似是相等的,则这是一个精确集合,否则它是一个粗糙集,其中下近似称为该概念的正区域,上下近似的差称为边界。上近似以外的区域称为负区域（Negativeregion），记为NEG（x）。soR1(颜色)R2(形状)R3(体积)classX1红圆形小1X2蓝方形大1X3红三角形小1X4蓝三角形小1X5黄圆形小2X6黄方形小2X7红三角形大2X8黄三角形大2等价类IND(R1)={{x1,x3,x7},{x2,x4},{x5,x6,x8}}X={X1,X2,X3,X4}例2：（表2）Then，thereare:I*(x)={x2，x4}I*(x)={x1，x3，x7，x2，x4}回回回24近似的示意图假定有一个信息系统,有两个属性.属性一有5个值,属性二有6个值.现在有一个要近似的集合(X),在图中用红色的圆表示.仅使用第一个属性进行划分的情形.正区域为空.蓝色区域为负区域.使用两个属性进行划分的情况加入第二个属性负区域正区域(下近似)边界区域上近似综合表示返回基本概念（5）粗糙度下近似、上近似及边界区等概念称为可分辨区，刻化了一个边界含糊(vague)集合的逼近特性。粗糙程度按右边公式计算。式中|＃|表示集合的基数或势，对有限集合表示集合中所包含的元素个数。例2的粗糙度＝2/5返回基本概念（6）粗糙隶属函数（Roughmembershipfunction)含糊集合没有清晰的边界，即，根据论域中现有知识无法判定某些元素是否属于该集合。在RS中，不确定（uncertainty）这个概念是针对元素隶属于集合的程度而言。例2中，I为属性{R1}上构成的等价关系时，x1对集合Ｘ的粗糙隶属函数为：2/3粗糙度与粗糙隶属函数vague（粗糙度）：用来描述集合，指集合的边界不清楚uncertainty（粗糙隶属函数）：描述元素，指某个元素是否属于某集合是不确定的。返回粗糙集理论的基本概念粗糙集理论的应用（规则挖掘和属性约简）其他粗糙集的应用粗糙集在数据挖掘中的应用基于粗糙集的数据约简返回是一种刻划不完整性和不确定性的数学工具，能有效地分析不精确，不一致，不完整等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律1.粗糙集在数据挖掘中的应用粗糙集理论的的数学基础：假定所研究的每一个对象都涉及到一些信息（数据、知识），如果对象由相同的信息描述，那么它们就是相似的或不可区分的。粗糙集对不精确概念的描述是通过上、下近似这两个精确概念来表示的。Example例3含6个流感病例的表（表4－3）病例头疼肌肉疼体温流感P1否是高是P2是否高是P3是是很高是P4否是正常否P5是否高否p6否是很高是Step1.寻找不可分辨关系：“头疼”：{p2,p3,p5},{p1,p4,p6}“肌肉痛”：{p1,p3,p4,p6},{p2,p5}“体温”：{p1,p2,p5},{p3,p6},{p4}“头疼＋肌肉痛”：{p1,p4,p6},{p2,p5},{p3}“头疼＋体温”：{p1},{p2,p5},{p3},{p4},{p6}“肌肉痛＋体温”：{p1},{p2,p5},{p3,p6},{p4}“头疼＋肌肉痛＋体温”：{p1},{p2,p5},{p3},{p4},{p6}Step2.针对各个属性下的初等集合寻找下近似和上近似。以“头疼＋肌肉痛＋体温”为例，设集合X为患流感的人的集合，I为3个属性构成的一个等效关系：{p1},{p2,p5},{p3},{p4},{p6}，则X={P1,P2,P3,P6}I={{p1},{p2,p5},{p3},{p4},{p6}}集合X的下近似为I*(X)=POS(X)={p1,p3,p6}集合X的上近似为I*(X)＝{p1,p2,p3,p5,p6}集合X的负区为NEG(X)={p4}集合X的边界区为BND(X)={p2,p5}Step3.获取规则根据上面的分析可得出关于属性“头疼＋肌肉痛＋体温”的规则：下近似得到的：RULE1：IF（头疼＝否）and（肌肉痛＝是)and(体温＝高）THEN患有流感RULE2：IF（头疼＝是）and（肌肉痛＝是)and(体温＝很高）THEN患有流感RULE3：IF（头疼＝否）and（肌肉痛＝是)and(体温＝很高）THEN患有流感负区得到的：RULE4：IF（头疼＝否）and（肌肉痛＝是)and(体温＝正常）THEN没患流感边界区得到的：RULE5：IF（头疼＝是）and（肌肉痛＝否)and(体温＝高）THEN可能以“肌肉痛＋体温”为例：X={P1,P2,P3,P6}I={{p1},{p2,p5},{p3,p6},{p4}}可以处理不完整的数据的体现RULE1：IF（肌肉痛＝是)and(体温＝高）THEN患有流感RULE2：IF（肌肉痛＝是)and(体温＝很高）THEN患有流感RULE3：IF（肌肉痛＝是)and(体温＝正常）THEN没患流感RULE4：IF（肌肉痛＝否)and(体温＝高）THEN可能返回2.基于粗糙集的数据约简不可分辨关系近似集（下近似和上近似）属性的依赖度属性的重要性冗余属性属性约简返回属性的依赖度利用两个属性集合D、C之间的相互依赖程度，确定在决策属性D之下的条件属性集合C的重要性即，决策属性集合D对条件属性集合C的依赖程度用如下定义来表示：POSc(D)是属性集C在U/IND(D)中的正区域。example|||)(|)(UDPOSDCC例4.属性依赖度的计算UA1A2A3A4A5100100210211311100402111512101610100712211800211令C＝{A1,A2},D={A5}依据属性A1、A2，可得到U/IND（D）：{{1,8},{2,6},{3},{4},{5,7}}正区域为：{4},{5,7}So，POSC(D)＝POS{A1,A2}({A5})＝{4,5,7}γQ(P)=3/8=0.375返回属性的重要性不同属性对于决定条件属性和决策属性之间的依赖关系起着不同的作用属性a加入C，对于分类U/IND(D)的重要程度定义为：SGF(a,C,D)=γC(D)-γC-{a}(D)有属性a的依赖度没有属性a的依赖度例5.属性的重要性计算UA1A2A3A4A5100100210211311100402111512101610100712211800211表4令C＝{A1,A2},D={A5}有POSC(D)＝{4,5,7}γC(D)=3/8=0.375ifa＝A1，thenγC-{a}(D)＝γ{A2}(D)=3/8ifa＝A2，thenγC-{a}(D)＝γ{A1}(D)=0SO,SGF(A1,C,D)=0SGF(A2,C,D)=3/8说明属性A2比属性A1更重要返回冗余属性对于属性集D和R，属性a属于R，如果POSR(D)=POSR-{a}(D)，ORSGF(a,R,P)=0则a在属性集R中是冗余的(如例5中的A1），否则a在R中对于D是不可缺少的。实际应用中存在的问题不可分辨关系对问题的限制太过于严格，对问题的描述过于单调离散化问题难以优化对于规模小，且属性本身具有明确的逻辑意义的数据会有较好的数据分析效果。对于大规模，特征又是连续值的数据，一定要离散化之后用粗糙集方法，很难得到十分满意的结果。粗糙集知识发现系统~roughsetRSES系统:基于粗糙集理论的方法分析数据的工具集，波兰华沙大学LERS系统:基于粗糙集的实例学习系统,美国Kansas大学开发ROSE系统:实现了Pawlak的基本粗糙集模型和可变精度粗糙集模型,波兰Poznan工业大学计算机科