信息系统的属性约简

粗糙集的几种属性约简算法分析

分类:默认栏目

2006.6.16 10:32 作者：万富 | 评论：0 | 阅读：1628

陈淑 珍，基于粗集的几种属性约简算法分析，武 汉 工业学院学报，Vol.2 4No.3，Sep .20 05

1.1 利用差别矩阵求最小约简

差别 矩 阵 (Discernibility Matrix)是由波兰华沙大学的著名数学家Skowron[21 提出来的，利用这个工具，可以将存在于复杂的信息系统中的全部不可区分关系表达出来。利用 差 别 矩阵求取最小约简的一个前提是:在数据表的预处理阶段要先对不相容的记录进行处理，即差别矩阵不处理不相容记录。预处理的方法如将冲突的记录数除以记录总数，得到一个粗糙度的量度，该量度可以作为数据表的一个特征。

通过 差 别 矩阵可以很方便地求取核属性，以核属性为出发点，再求取差别函数的最小析取范式，则求析取范式的运算就可以得到很大的简化。而最后得到的每个析取分量对应着一个约简。因此，一定可以得到最小约简。

但该 算 法 的缺陷十分明显:首先，当论域的对象与属性的规模较大时，差别矩阵将占有大量的存储空间口(n的二次方);其次，差别函数的化简本身就是一个NP一hard问题，因此只要数据集稍大一点，就不具备可操作性。

1.2 基于属性依赖度约简算法

求取 所 有 约简是一个NP一hard问题，因此运用启发信息来简化计算以找出最优或次优约简显然是一种可取的方法。

许多 启 发 式约简算法的基本步骤都是:由信息系统或决策表的核为起始点，然后根据属性重要性的某种测度，依次选择最重要的属性加人核中，直到满足终止条件。便得到信息系统或决策表的一个约简(更确切的说，是包含约简的一个属性集)。

一个 信 息 系统中的所有属性对于决策来说并不是同等重要的，在粗集理论中，属性重要性可通过相依度来体现。

决策 属 性 D对于属性R(R属于C)的相依度y(R,D)定义为[3]:显然 有 ，O <,y(R,D), l,y(R,D)给出了决策D对属性R之间相依性的一种测度。它反映了属性R对于决策D的重要程度。在已知条件R的前提下，一个属性R对于决策D的重要度SGF(a,R,D)可以定义为如下的差值:SGF = (a ,R,D)=y(R+{a},D)一y(R,D),SG F= ( a,R,D)反映了把属性a加到R后，R

页眉内容

来源于网络 问题重述：

随着科技的发展，社会的进步，智能体的出现也为学科的研究打开了一个新的局面。本题针对智能体的决策提出了问题，考虑到不同对象，不同的属性对智能体的影响，如何在不影响公平的情况下，科学地排除一些属性因素，得到属性约简的若干模式，通过这些模式对数据进行系统的约简。同时考虑到删减的属性个数越多越好的情况下，如何给出相对应的数学模型和算法，并通过附件所给数据进行求解验证。进一步，当各种属性重要程度不一的时或者在属性取值范围D是②，③，④时讨论数学模型以及算法的拓展性。并且，若考虑到智能体的私下操作，该如何改进模型，才能更好的为智能体提供技术支持。最后，针对生活学习，从实际出发，进行对模型的讨论分析。

基本假设：

1.假设题目所给数据真实可靠；

2.假设每个对象在决策时知道其他人在该属性上所对应的数据，且他们必须同时做出抉择；

3.假设对每个对象来说他放弃或者留下该属性是等可能的；

4.假设每个属性的重要程度相同，互不影响；

5.假设我们所评估的对象在这个问题里并没有一个具有约束力的协议；

符号说明：

1. 我们用来描述评价体系的五元组 UADf（）;

2. U表示一组需要评价的对象的集合；

3. A表示一组用于评价U中对象的属性，属性之间相互独立；D代表A中属性的取值范围，在本题中，所有属性的取值范围是一样的；

4. 函数fUAD：，即对于每一个对象，每一个属性，给定D中的某个值；

5. 符号是求和评价规则，即对于每一个对象，把与之对应的每个属性值求和。

6. 参与博弈的智能体用123{}XUUUUU，，，，表示，相应的属性用123{}YAAAAA，，，来表示，第i个智能体的第j个的可能的决策用123{}ijYAaaaa，，，（这里a的下标1,2,3y，代表对应的属性123YAAAA，，，）并且，这里的1,2,3),(iaiy的值只有0,1，其中:0代表该智能体向决策者提建议去掉iA，1代表该智能体向决策者提建议保留iA.

开题报告

信息与计算科学

信息系统中基于证据理论的属性约简

一、 综述本课题国内外研究动态, 说明选题的依据和意义

波兰学者Pawlak[1]于1982年提出的粗糙集(Rough Set, RS)理论[2,3,4]是一种刻画不完整性和不确定性的数学工具, 能有效分析和处理不精确、不一致、不完整等各种不完备信息, 并从中发现隐含的知识, 揭示潜在的规律. 粗糙集理论是一种新的处理模糊和不确定知识的数学工具, 其主要思想是, 在保持信统的分类能力不变的前提下, 通过知识约简, 导出问题的决策规则[5,6]或分类规则. 近20年来, 粗糙集论己经在理论和应用上取得了长足的发展, 特别是由于20世纪90年代在知识发现等领域得到了成功的应用而受到国际学术界广泛关注,

基于Rough集方法的知识发现与知识约简被许多专家所研究. 目前, 它正在被广泛应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域. 知识约简是粗糙集理论的核心内容之一. 对一个信息系统(,,)UAF来说, 知识库中属性并不是同等重要的, 甚至其中某些属性是冗余的. 所谓知识约简就是在知识库分类能力不变的条件下, 删除其中不重要或不相关的属性特别是, 当信息系统中的数据是随机采集时, 其冗余性更为普遍.

约简是粗糙集用于数据分析的重要概念, 是粗糙集理论的核心内容. 所谓属性约简, 就是在保持知识库分类不变的条件下, 删除其中不重要的知识. 属性约简作为数据挖掘的一个重要过程, 主要是为决策提供帮助的. 现实中, 数据库中的各种决策表是非常复杂的, 比如说：不相容、不完备、模糊、值连续等.

D-S证据理论是人工智能中表示不确定性的一种重要理论, 也是专家系统重要研究范畴.由于专家系统针对特定的专业领域, 对问题的求解不仅依赖于特定领域确定的理论知识, 而且更多地依赖于专家的经验和常识. 现实世界中客观事物或现象常常存在着不确定性, 导致了人们对各认识领域中的信息和知识的认识大多是不精确的, 这就要求专家系统中的知识的表示和处理模式能够反映出这种不确定性. 由于研究领域的不同, 对不确定性量度方法也不同, 因而提出了多种不确定推理理论与方法, 例如主观Bayes方法、确定性理论、粗集理论和证据理论等方法; 与主观Bayes方法相比, 具有较大的灵活性. 它将概率论中的单点附值扩展为集合附值, 弱化了相应的公理系统, 即满足比概率更弱的要求, 可看作一种广义概 1 率论. 就具体推理方法而言, 对未知的表示也更接近人的思维习惯; 对信任函数的更新是通过合成规则来实现, 这样有利于各种信息的融合; 其规则式表现形式、透明的推理过程, 都适合机器的实现, 因此在许多领域得到广泛应用.

粗糙集的研究对象是一个数据集，数据集一般被保存为数据表格形式，即数据库或信息系统。信息系统的形式是由研究对象和属性值关系构成的二维数据表，类似于基础数学中的关系数据库。信息系统实现了粗糙集模型的知识表示。

定义2.1.1[46] 设(,,,)SUAVf为一个数据库，即信息系统，也称为知识表示系统。其中12{,}UUxxx为一个非空的有限对象集，12{,,}AAaaa是属性的有限非空集合，aVV，aA，aV为属性a的值域；定义信息函数:UVcafA .

例如表2.1.1是一个信息系统，其中12345{,,,,}Uxxxxx，

1234{,,,}Aaaaa，123aaaVVV={0,1}，4aV={0,1,2}.

表2.1.1 信息系统

U 1a 2a 3a 4a

1x 1 1 1 1

2x 1 0 1 2

3x 0 0 1 0

4x 0 0 1 0

5x 1 0 0 2

定义2.1.2[46] 对于aA，xU，(,)afxaV，对于PA，定义：{(,):(,)(,),}IxyUUfxqfyqqP，

IU称为上的不可分辨关系。

(1)若(,)xyI，则称：xy和是不可分辨的。

(2)不可分辨关系是等价关系，具有：

自反性：xIx；

对称性：xIyyIx； 传递性：,xIyyIzxIz ．

(3) I是U上的一个等价关系，[]{,}IxyyUxIy，

12{[]}{,}IkUIxxUXXX，12,kXXX称为U关于I的一个划分。

(4)PI,1,2III, 112{,}kUIXXX,212{,}lUIYYY,

12{,1,2,1,2}ijUIIXYikjl,()IPindPIP，

则称：()indPU是上的一个等价关系，称为P上的不可区分关系。

()[][]indPIIPxx称为P的基本知识。