[工学]信息系统的属性约简算法-【中文】.ppt

信息系统的属性约简算法信息系统的特征选择算法 Preview 属性约简算法 信息系统的盲目删除属性约简算法 基于Pawlak属性重要度的属性约简算法 基于Skowron差别矩阵的属性约简算法 基于信息熵的属性约简算法 属性约简算法分类 依据有无启发式 1、盲目法 2、启发式算法 信息系统的盲目删除属性约简算法 信息系统的盲目删除属性约简算法 基于Pawlak属性重要度的属性约简算法 属性重要度度量了属性对信息系统的分类能力 基于Pawlak属性重要度的属性约简算法 1、构造思想 基于Pawlak属性重要度的属性约简算法 2、具体步骤 基于Pawlak属性重要度的属性约简算法 基于Skowron差别矩阵的属性约简算法 差别函数 基于差别函数的信息系统属性约简算法 基于信息熵的属性约简算法 基本概念 对于二类分类问题， 是在样例集合S中正类的比例， 是 在S中负类的比例。 分类信息熵： 熵函数曲线 基于信息熵的属性约简算法 什么是信息熵？ 信息熵是衡量样例集类别混乱程度的指标。 * 信息熵度量了信息源提供的平均信息量的大小 信息熵也反映了属性集合的分类能力 * 互信息度量了一个信息源从另一个信息源 获取的信息量的大小 知识的信息熵与互信息 粗糙集理论把知识定义为关于论域的各种划分模式，那么在论域中任取一个对象，它落入哪个子块？这具有随机性。 把粗糙集意义下的知识看成随机变量 1.知识的概率分布 设U是论域，P，Q是两个等价关系，设P和Q在U上导出的划分为 (1) P,Q在U的子集的概率分布为 (2) P,Q的联合概率分布为 2.知识的信息熵与互信息 定义（知识P的信息熵H(P)） 定义（知识Q相对于P的条件熵H(Q|P)） 定义（知识P与Q的互信息I(P;Q)） I(P;Q)=H(Q)-H(Q|P) 信息熵度量了信息源提供的平均信息量的大小 互信息度量了一个信息源从另一个信息源获取的信息量的大小 基于信息熵的属性约简算法 基于信息熵的属性约简算法 谢 谢！ 当集合中都是正例或都是负例时，熵的值为0。当正负例各占一半时，熵的值最大为1。即熵越大，样例集越混乱。 * * 输入 算法 输出 ↓ ↓ ↓ 信息系统 或决策表 约简 REDUCT 属性约简 或降维 ↓ 属性子集 1. 信息系统是一个4元组 即 No Strong High Mild Rain 14 Yes Weak Normal Hot Overcast 13 Yes Strong High Mild Overcast 12 Yes Strong Normal Mild Sunny 11 Yes Weak Normal Mild Rain 10 Yes Weak Normal Cool Sunny 9 No Weak High Mild Sunny 8 Yes Strong Normal Cool Overcast 7 No Strong Normal Cool Rain 6 Yes Weak Normal Cool Rain 5 Yes Weak High Mild Rain 4 Yes Weak High Hot Overcast 3 No Strong High Hot Sunny 2 No Weak High Hot Sunny 1 Decision Wind Humidity Temperature Outlook No. 表1. 一个信息系统的例子 2. 不可分辨关系（等价关系） 给定信息系统 ， ， 称x和y关于R是不可分辨的，如果 例题 对表1所示信息系统， 若R={Outlook}，则样例1, 2, 8, 9, 11关于等价关系（或知识）Outlook是不可分辨的，因为它们在属性Outlook上的取值是相同的。类似地，样例3, 7, 12, 13关于Outlook是不可分辨的；样例4, 5, 6, 10, 14关于Outlook是不可分辨的。 若R={Outlook, Temperature}，则样例1, 2关于R是不可分辨的；样例3, 13是不可分辨的；样例4, 10, 14是不可分辨的；…… 3. 下近似和上近似 给定信息系统 ， ， X关于R的下近似和上近似分别定义为 和 例题 对表1所示信息系统， 设R=