不完备信息系统决策【毕业论文】.doc

1、毕业论文 文客久久 本科 毕业设计 (论文 ) 题 目： 不完备信息系统决策 学 院： 学生姓名： 专 业： 信息与计算科学 班 级： 指导教师： 起 止 日期： 毕业论文 文客久久 摘 要 不完备信息系统是信息处理的一个重要研究方向 .所谓的不完备系统是指在系统中缺失数据 (空值 )我们不考虑不合适的值作为缺省值的情况 ，这个问题可以通过添加一个特别的标记去表示这个属性域的值 从不完备信息系统的知识发现方面考虑一些问题 在完备信息系统中，通过等价关系可以将论域划分给定一个概念，利用粗糙集理论得 到一对近似值概念一个不完备信息表可以表示为一个完备信息表的子系每一个完备信息表可以通过等价关系将论

2、域划分属于这概念领域中的每一个可能的对象可以计算的在粗糙集理论决策中，推导出了一个用概率替代条件概率的决策规则最后，根据这概率把论域划分成三个部分在本文中我们介绍了粗糙集理论，决策粗糙集粗糙集模型和不完备信息系统结合决策粗糙集来处理不完备信息系统为不完备信息系统提供了新的方法用例子说明新方法的使用 关键词： 不完备信息系统；粗糙集理论决策；概率； 隶属度 毕业论文 文客久久 Abstract Incomplete information system is an important research field in dealing with information. By an incomp

3、lete system we mean a system with missing data (null values). We do not consider the case of null value meaning inapplicable value. This problem may be solved by adding a special symbol denoting inapplicable value to the attribute domains. The problem of knowledge discovering from incomplete informa

4、tion systems is considered. In complete information system, the universe is partitioned with equivalence relation. Given a concept we get a pair of approximation of the concept using rough set theory. An incomplete information table can be expressed as a family of complete information tables. The un

5、iverse is partitioned by equivalence relation for each of complete information table. The probability of each object in universe belonging to the concept can be calculated. A decision rule is derived using the probability instead of conditional probability in decision-theoretic rough sets. At last,

6、the universe is divided into three regions according to the probability. In the paper, we introduce the rough set theory, decision-theoretic rough set and incomplete information system. Incomplete information system is dealt by using decision-theoretic rough set which gives out a new method in incom

7、plete information system. At last, we use example to show the use of the new method. Keywords: Incomplete information system; Decision-theoretic rough sets; Probability; Membership degree 毕业论文 文客久久 目 录 摘 要 .I ABSTRACT . II 1 前言 . 2 2 粗糙集理论介绍 . 3 2.1 上下近似集 . 3 2.2 决策粗糙集模型 . 3 3 不完备信息表和它的扩展 . 5 3.1 属于

8、概念对象的概率 . 7 3.2 新方法的一个例子 . 9 4 小结 . 12 参考文献 . 12 致 谢 . 14 毕业论文 文客久久 不完备信息系统决策 摘要 ： 在完备信息系统中，通过等价关系可以将论域划分给定一个概念，利用粗糙集理论得到一对近似值概念一个不完备信息表可以表示为一个完备信息表的子系每一个完备信息表可以通过等价关系将论域划分每个对象属于概念的一个可能性是可以计算的本文在粗糙集理论决策中，推导出了一个用概率替 代条件概率的决策规则最后，根据这概率把论域划分成三个部分这样就在不完备系统中导出了决策 关键词 ： 不完备信息系统；决策粗糙集理论；概率； 隶属度 Decision Ma

9、king in Incomplete Information System Hu Jinxiao Abstract ： In complete information system, the universe is partitioned with equivalence relation. Given a concept we get a pair of approximation of the concept using rough set theory. An incomplete information table can be expressed as a family of com

10、plete information tables. The universe is partitioned by equivalence relation for each of complete information table. The probability of each object in universe belonging to the concept can be calculated. A decision rule is derived using the probability instead of conditional probability in decision

11、-theoretic rough sets. At last, the universe is divided into three regions according to the probability. Thus, a decision is derived from incomplete information. Keywords: Incomplete information system; Decision-theoretic rough sets; Probability; Membership degree 毕业论文 文客久久 1 前言 1982 年 ， 波兰数学家 Pawla

12、k 9提出了粗糙集理论，是传统集合论的一个延伸，具有研究智能系统不充分和不完备信息的特点 其主要思想是基于知 识的分类观点， 在近似空 间(知 识库 )中研究如何在保 持分类能力不变的前提下， 通 过知识约简，从中发现隐含的知识，揭示 潜在的规律， 并且不需要先 验规则， 避 开了个人偏好带来的影响经过 20 多年的发展，粗糙集理论在人工智能领域已经有了非常成功的应用， 例如，机器学习、 市 场分析、医疗数据分析、 金融 、语音识别、图像处理、传感数据分析及新合成材料设计等 在古典的粗糙集模型中，论域根据等价关系被划分成三个部分这三个部分分别为正域，负域和边界域即正域是肯定属于概念的一部分，负

13、域则是概念之外部分，边界域则不能 肯定是否属于概念在决策粗糙集理论中 14,15，一些在边界域中的等价类，可以根据属于概念的条件概率，移到正域或者负域然而，在没有等价关系的不完备信息系统中，我们不能那样做 不完备信息系统是指属性值缺失（空值） Pawlak 的粗糙集模型可能被推广到非等价关系，适用到不完备信息系统的推理和知识获取 2,3近 10 年，许多研究者在研究不完备系统 1,4-8,10-13 在本文中，假定在不完备信息系统，任何对象属性只有一个值，如果不知道它的确切值，但它的值肯定是已知值中的一个在这种假定下，一个不完备 信息表可以表示为一个完备信息表的子系，叫做不完备表 3的扩展由于

14、每个不完备表的扩展是完备的，我们可以用Pawlak 的粗糙集处理在本文中，在每个不完备表的扩展中，用等价关系可以计算出一个对象隶属度然后我们可以得到所有对象的总隶属度最后，我们可以做出决策，这些对象该放入哪个部分。这方法跟 DTRS 相似，我们把论域划分成三个部分，即，正域，负域和边界域 毕业论文 文客久久 2 粗糙集理论介绍 2.1 上下近似集 粗糙集理论的核心内容是上下近似集的定义在代数粗糙集模型中，通过等价类关系的包含关系给出了上、下近似集的定义 ，并在此基础上定义了正域，负域和边界设 U 表示论域 ,是一个有限的非空集合 R U U表示论域上的等价关系，而论域可以通过该等价关系划分成互

15、不相交的子集，即可以形成论域上的一个划分 /UR 如果论域中的两个对象 在同一个等价类中，则这两个对象是不可区分的设 X 是论域 U 的一个子集，则 X 的下近似集 ()aprX 和上近似集 ()aprX 可以表示为： ( ) | , Ra p r X x x U x X ； ( ) | , Ra p r X x x U x X 根据 X 的上下近似集的定义，可以将论域划分成 3 个互不相交的部分，正域 ()POS X ，负域 ()NEGX 和边界域 ()BNDX ，分别定义为： ( ) ( )POS X apr X ； ( ) ( )N EG X U apr X； ( ) ( ) ( )B

16、N D X a p r X a p r X 对于正域中的每一个对象 x ，肯定包含于概念 X ，从而可以导出确定性的规则，但是在边界域中的对象 x ，我们却不能确定它是否属于概念 X 而且，通过以上公式，我们可以导出上近似集和正域，边界域的关系： ( ) ( ) ( )a p r X P O S X B N D X ，也就是上近似集包含了确定的和可能属于概念 X 的对象所以，对于 ()x apr X ，其中的有些对象 x 有可能属于概念 X ，可以推测出所有的可能性规则 2.2 决策粗糙集模型 在 Pawlak 粗糙集模型中，只有那些能完全包含于某个概念的等价类才能被确定属于决策概念，而对于包

17、含度介于 0 与 1 之间的所有对象集合都被划分到边界域但是，在涉及到的实际问题论域中，由于某些外部条件的存在，条件等价类一般是部分包含于决策毕业论文 文客久久 类因此，在实际问题的操作中，采取定量的概率包含关系来度量对象集合对于决策概念的隶属度（条件概率）是非常有必要的基于这种概率思想，提出了一系列概率粗糙集模型 设 12 , ,., s 是具有 s 个状态的集合， maaaA , 21 是由 m 个可能决策行为构成的集合， x 是论域对象 )|( xP j 表示一个对象在描述 x 下处于状态 j 的条件概率，在接下来的讨论中，我们假定条件概率 )|( xP j 是已知的 令 )|( jia

18、 表示状态为 j 时采取决策 ia 的风险代价假定一个对象的描述为 x ，对于这个对象实施了决策 ia ，由于 )|( xP j 是在给定描述 x 下处于状态 j 的概率，因此对象在给定描述 x 下采取决策 ia 的期望风险可由全概率公式得： )|()|()|( 1 xPaxaR jsj jii 这个 )|( xaR i 也称为条件风险对于给定的描述 x ， )(x 为决策规则，可以看作是对象描述 x 的一个函数，即对每个 x 都对应着某一个决策 )(x ， maa ,1 令 R 是一个已知的总体决策规则下的总体期望风险由于 )|)( xxR 是在描述 x 下取决策 )(x 的条件风险率，因此

19、期望风险： |xR R x x P x ， 其中 |x R x x是针对整个知识表示系统很显然，如果对于一个决策规则 )(x 中每个x 而言，其条件风险率 )|)( xxR 越小，那么总体风险就会有一个最小值因此，贝叶斯决策过程可以表述如下：对于每个对象 x ，计算由公式 )|()|()|(1 xPaxaR jsj jii 给出的条件风险 )|( xaR i ， mi ,2,1 ，选取其中一个使条件风险达到最小的决策作为最佳决策行为，如果两个或两个以上的决策使条件风险 )|( xaR i 达到最小， 则根据实际情况选择其中之一 毕业论文 文客久久 3 不完备信息表和它的扩展 让我们粗略地回顾下

20、不完备信息系统 2我们用 ( , , )U AT d f表示一个信息系统IS（ ） ，当 12 , ,., nU x x x 是一个非空有限对象的集合，称为领域， 12 , ,., mAT a a a 是一个非空有限集合的属性，例如对于任何 a AT ， :aaf U V ，此时 aV 称为 a 的领域 当信息系统中一些属性的精确值不可知的，即缺失或者部分已知，这样的一个系统称为不完备信息系统 ()IIS ，并不会跟 ( , , )T U AT d f 所表示的混淆这样的情况，可以通过一个信息系统的基础集合表示，属性值函数 af 被定义为 U 到 aV 的幂集 ()aPV 的映射，一个不确定的

21、属性应该采用什么值，但是可接受值的集合是可以明确规定的例如，缺失值 ()ax可以表示为所有可能的属性值的集合，即 ()aax V ；如果部分已知，例如，如果我们知道 ()ax不是 , abc V ，那么 ()ax 的值被规定为 , aV bc 在表 1 中，让我们看一个例子 3 表 1. 不完备信息系统典例 U a b c d 1x 1 1 1 1 2x 1 1 1 3x 2 1 1 1 4x 1 2 1 5x 1 1 2 6x 2 2 2 2 7x 1 1 1 2 1 2 7 , ,., U x x x ， ,abc是条件属性， d 是决策属性 表示可能的属性值在这个例子中， 的值可能是 1

22、 或者 2 这个表可以表示为表 2： 表 2. 从表 1 得到的另一种不完备信息系统的表现形式 U a b c d 1x 1 1 1 1 毕业论文 文客久久 2x 1 1 , 2 1 1 3x 2 1 1 1 4x 1 2 1 , 2 1 5x 1 , 2 1 1 2 6x 2 2 2 2 7x 1 1 1 2 定义 1. 令 ( , , )T U AT d f 为一个不完备信息决策表完备表 ( , , )T U AT d f称为 T 的一个扩展，当且仅当对于任何 a AT ，并且 xU ， ()aaf x V 意味着( ) ( )aaf x f x 这里 T 有很多扩展用表 1 作为例子，在

23、表 3 中我们列出了所有它的扩展，就是完备系统表 18TT 表 3. 不完备信息系统表 1 的扩展 U a b c d U a b c d U a b c d 1x 1 1 1 1 1x 1 1 1 1 1x 1 1 1 1 2x 1 1 1 1 2x 1 1 1 1 2x 1 1 1 1 3x 2 1 1 1 3x 2 1 1 1 3x 2 1 1 1 4x 1 2 1 1 4x 1 2 1 1 4x 1 2 2 1 5x 1 1 1 2 5x 2 1 1 2 5x 1 1 1 2 6x 2 2 2 2 6x 2 2 2 2 6x 2 2 2 2 7x 1 1 1 2 7x 1 1 1 2

24、7x 1 1 1 2 1T 2T 3T U a b c d U a b c d U a b c d 1x 1 1 1 1 1x 1 1 1 1 1x 1 1 1 1 2x 1 2 1 1 2x 1 2 1 1 2x 1 1 1 1 3x 2 1 1 1 3x 2 1 1 1 3x 2 1 1 1 4x 1 2 1 1 4x 1 2 2 1 4x 1 2 2 1 5x 1 1 1 2 5x 1 1 1 2 5x 2 1 1 2 6x 2 2 2 2 6x 2 2 2 2 6x 2 2 2 2 7x 1 1 1 2 7x 1 1 1 2 7x 1 1 1 2 4T 5T 6T U a b c d U a b c d 1x 1 1 1 1 1x 1 1 1 1