信息系统的属性约简算法 【中文】概要课件

信息系统的属性约简算法

信息系统的特征选择算法信息系统的属性约简算法

信息系统的特征选择算法1输入算法输出↓↓↓信息系统或决策表约简REDUCT属性约简或降维↓属性子集输入算法输出↓↓↓信息系统约简属性约简↓属性子集2Preview1.信息系统是一个4元组即Preview1.信息系统是一个4元组即3No.OutlookTemperatureHumidityWindDecision1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo表1.一个信息系统的例子No.OutlookTemperatureHumidityW42.不可分辨关系（等价关系）给定信息系统，，称x和y关于R是不可分辨的，如果2.不可分辨关系（等价关系）给定信息系统5例题对表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是不可分辨的；……例题对表1所示信息系统，63.下近似和上近似给定信息系统，，X关于R的下近似和上近似分别定义为和3.下近似和上近似给定信息系统7信息系统的属性约简算法【中文】概要课件8例题对表1所示信息系统，设R={Outlook}，X={1,2,6,8,14}，计算X关于R的下近似和上近似。设R={Outlook,Temperature}，X={3,4,5,7,9,10,11,12,13}，计算X关于R的下近似和上近似。注：用知识R描述决策类的问题负类正类例题对表1所示信息系统，注：用知识R描述决策类的问题负类正类9解：(1)根据下近似的公式先计算样例x的R等价类，分别是：U1={1,2,8,9,11};U2={3,7,12,13};U3={4,5,6,10,14}.X={1,2,6,8,14}U1,

U2,U3均不包含于X，故X的R下近似为空集。注：说明仅用R来描述X(负类)是不够的解：(1)根据下近似的公式先计算样例x的R等价类，分别是：注10解：(1)根据上近似的公式因为U1,

U2,U3和X均有非空交集，故X的R上近似为全集(论域)。(2)可类似求解解：(1)根据上近似的公式因为U1,U2,U3和X均有非空114.Q-P正域给定信息系统，Q的P正域定义为说明：若Q为决策属性子集(一般决策属性是单属性)，P为条件属性子集，则Q-P正域描述的是用知识R可以完全描述决策类。4.Q-P正域给定信息系统12Q-P边界域Q-P负域Q-P边界域Q-P负域13Q依赖P的依赖度条件属性a∈P相对于决策属性Q的重要度Q依赖P的依赖度条件属性a∈P相对于决策属性Q的重要度14例题对表1所示信息系统,设P={Outlook},Q={Decision},计算信息系统的Q-P正域。解：首先求论域关于决策属性Q的划分，得X1={1,2,6,8,14},X2={3,4,5,7,9,10,11,12,13}负类正类下面分别求X1和X2关于P的下近似和。根据下近似的定义得，而例题对表1所示信息系统,设P={Outlook},Q={D15从而故这说明对于信息系统U，只要条件属性Outlook的值等于Overcast，则可断定该样例为负类。从而故这说明对于信息系统U，只要条件属性Outlook的值等165.属性集的独立性给定信息系统，如果对于任意的下式成立则称属性p为P中不必要的（或冗余的），否则称p为P中不必要的。如果P中任意属性都是必要的，则称P是独立的。5.属性集的独立性给定信息系统176.属性约简给定信息系统，对任意的，若P'满足如下条件则称P'是P的约简6.属性约简给定信息系统187.属性的核给定信息系统，P中所有必要属性构成的集合称为P的核，记为CORE(P)7.属性的核给定信息系统19属性约简算法信息系统的盲目删除属性约简算法基于Pawlak属性重要度的属性约简算法基于Skowron差别矩阵的属性约简算法基于信息熵的属性约简算法

属性约简算法20属性约简算法分类依据有无启发式1、盲目法2、启发式算法依据属性获取途径1、删除法2、添加法例如：盲目删除属性约简算法例如：基于Pawlak属性重要度的属性约简算法，基于差别矩阵的属性约简算法，基于信息熵的属性约简算法等例如：盲目删除属性约简算法例如：基于属性重要度的属性约简算法，基于信息熵的属性约简算法等我们常用的大多是启发式的添加算法属性约简算法分类依据有无启发式依据属性获取途径例如：盲目删除21信息系统的盲目删除属性约简算法信息系统的盲目删除属性约简算法22信息系统的盲目删除属性约简算法

思想：从属性全集中逐个删除，直到满足约简条件。信息系统的盲目删除属性约简算法思想：从属性全集中逐个删除23基于Pawlak属性重要度的属性约简算法属性重要度度量了属性对信息系统的分类能力基于Pawlak属性重要度的属性约简算法属性重要度度量了属性24基于Pawlak属性重要度的属性约简算法1、构造思想基于Pawlak属性重要度的属性约简算法1、构造思想25基于Pawlak属性重要度的属性约简算法2、具体步骤基于Pawlak属性重要度的属性约简算法2、具体步骤26基于Pawlak属性重要度的属性约简算法2、具体步骤思想：从核开始逐个添加，直到满足约简条件。基于Pawlak属性重要度的属性约简算法2、具体步骤思想：从27快速计算属性约简算法[QianShen]快速计算属性约简算法[QianShen]28核等于差别矩阵中所有简单属性（单个属性）元素的集合。基于Skowron差别矩阵的属性约简算法核等于差别矩阵中所有简单属性（单个属性）元素的集合29信息系统的属性约简算法【中文】概要课件30信息系统的属性约简算法【中文】概要课件31信息系统的属性约简算法【中文】概要课件32基于Skowron差别矩阵的属性约简算法具体步骤：思想：从差别矩阵求核，从包含核的属性集中找约简。基于Skowron差别矩阵的属性约简算法具体步骤：思想：从差33差别函数差别函数34信息系统的属性约简算法【中文】概要课件35基于差别函数的信息系统属性约简算法基于差别函数的信息系统属性约简算法36信息系统的属性约简算法【中文】概要课件37基于信息熵的属性约简算法当集合中都是正例或都是负例时，熵的值为0。当正负例各占一半时，熵的值最大为1。即熵越大，样例集越混乱。基本概念对于二类分类问题，是在样例集合S中正类的比例，是在S中负类的比例。

分类信息熵：

熵函数曲线基于信息熵的属性约简算法当集合中都是正例或都是负例时，熵的值38基于信息熵的属性约简算法什么是信息熵？

信息熵是衡量样例集类别混乱程度的指标。

*信息熵度量了信息源提供的平均信息量的大小信息熵也反映了属性集合的分类能力*互信息度量了一个信息源从另一个信息源获取的信息量的大小基于信息熵的属性约简算法什么是信息熵？39知识的信息熵与互信息粗糙集理论把知识定义为关于论域的各种划分模式，那么在论域中任取一个对象，它落入哪个子块？这具有随机性。把粗糙集意义下的知识看成随机变量知识的信息熵与互信息粗糙集理论把知识定义为关于论域的各种划分401.知识的概率分布设U是论域，P，Q是两个等价关系，设P和Q在U上导出的划分为1.知识的概率分布设U是论域，P，Q是两个等价关系，设P和Q41(1)P,Q在U的子集的概率分布为(1)P,Q在U的子集的概率分布为42(2)P,Q的联合概率分布为(2)P,Q的联合概率分布为432.知识的信息熵与互信息定义（知识P的信息熵H(P)）定义（知识Q相对于P的条件熵H(Q|P)）2.知识的信息熵与互信息定义（知识P的信息熵H(P)）44定义（知识P与Q的互信息I(P;Q)）

I(P;Q)=H(Q)-H(Q|P)信息熵度量了信息源提供的平均信息量的大小互信息度量了一个信息源从另一个信息源获取的信息量的大小定义（知识P与Q的互信息I(P;Q)）45基于信息熵的属性约简算法1.构造思想：基于信息熵的属性约简算法1.构造思想：46基于信息熵的属性约简算法2.具体步骤：基于信息熵的属性约简算法2.具体步骤：47基于信息熵的属性约简算法基于信息熵的属性约简算法48谢谢！谢谢！49信息系统的属性约简算法

信息系统的特征选择算法信息系统的属性约简算法

信息系统的特征选择算法50输入算法输出↓↓↓信息系统或决策表约简REDUCT属性约简或降维↓属性子集输入算法输出↓↓↓信息系统约简属性约简↓属性子集51Preview1.信息系统是一个4元组即Preview1.信息系统是一个4元组即52No.OutlookTemperatureHumidityWindDecision1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo表1.一个信息系统的例子No.OutlookTemperatureHumidityW532.不可分辨关系（等价关系）给定信息系统，，称x和y关于R是不可分辨的，如果2.不可分辨关系（等价关系）给定信息系统54例题对表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是不可分辨的；……例题对表1所示信息系统，553.下近似和上近似给定信息系统，，X关于R的下近似和上近似分别定义为和3.下近似和上近似给定信息系统56信息系统的属性约简算法【中文】概要课件57例题对表1所示信息系统，设R={Outlook}，X={1,2,6,8,14}，计算X关于R的下近似和上近似。设R={Outlook,Temperature}，X={3,4,5,7,9,10,11,12,13}，计算X关于R的下近似和上近似。注：用知识R描述决策类的问题负类正类例题对表1所示信息系统，注：用知识R描述决策类的问题负类正类58解：(1)根据下近似的公式先计算样例x的R等价类，分别是：U1={1,2,8,9,11};U2={3,7,12,13};U3={4,5,6,10,14}.X={1,2,6,8,14}U1,

U2,U3均不包含于X，故X的R下近似为空集。注：说明仅用R来描述X(负类)是不够的解：(1)根据下近似的公式先计算样例x的R等价类，分别是：注59解：(1)根据上近似的公式因为U1,

U2,U3和X均有非空交集，故X的R上近似为全集(论域)。(2)可类似求解解：(1)根据上近似的公式因为U1,U2,U3和X均有非空604.Q-P正域给定信息系统，Q的P正域定义为说明：若Q为决策属性子集(一般决策属性是单属性)，P为条件属性子集，则Q-P正域描述的是用知识R可以完全描述决策类。4.Q-P正域给定信息系统61Q-P边界域Q-P负域Q-P边界域Q-P负域62Q依赖P的依赖度条件属性a∈P相对于决策属性Q的重要度Q依赖P的依赖度条件属性a∈P相对于决策属性Q的重要度63例题对表1所示信息系统,设P={Outlook},Q={Decision},计算信息系统的Q-P正域。解：首先求论域关于决策属性Q的划分，得X1={1,2,6,8,14},X2={3,4,5,7,9,10,11,12,13}负类正类下面分别求X1和X2关于P的下近似和。根据下近似的定义得，而例题对表1所示信息系统,设P={Outlook},Q={D64从而故这说明对于信息系统U，只要条件属性Outlook的值等于Overcast，则可断定该样例为负类。从而故这说明对于信息系统U，只要条件属性Outlook的值等655.属性集的独立性给定信息系统，如果对于任意的下式成立则称属性p为P中不必要的（或冗余的），否则称p为P中不必要的。如果P中任意属性都是必要的，则称P是独立的。5.属性集的独立性给定信息系统666.属性约简给定信息系统，对任意的，若P'满足如下条件则称P'是P的约简6.属性约简给定信息系统677.属性的核给定信息系统，P中所有必要属性构成的集合称为P的核，记为CORE(P)7.属性的核给定信息系统68属性约简算法信息系统的盲目删除属性约简算法基于Pawlak属性重要度的属性约简算法基于Skowron差别矩阵的属性约简算法基于信息熵的属性约简算法

属性约简算法69属性约简算法分类依据有无启发式1、盲目法2、启发式算法依据属性获取途径1、删除法2、添加法例如：盲目删除属性约简算法例如：基于Pawlak属性重要度的属性约简算法，基于差别矩阵的属性约简算法，基于信息熵的属性约简算法等例如：盲目删除属性约简算法例如：基于属性重要度的属性约简算法，基于信息熵的属性约简算法等我们常用的大多是启发式的添加算法属性约简算法分类依据有无启发式依据属性获取途径例如：盲目删除70信息系统的盲目删除属性约简算法信息系统的盲目删除属性约简算法71信息系统的盲目删除属性约简算法

思想：从属性全集中逐个删除，直到满足约简条件。信息系统的盲目删除属性约简算法思想：从属性全集中逐个删除72基于Pawlak属性重要度的属性约简算法属性重要度度量了属性对信息系统的分类能力基于Pawlak属性重要度的属性约简算法属性重要度度量了属性73基于Pawlak属性重要度的属性约简算法1、构造思想基于Pawlak属性重要度的属性约简算法1、构造思想74基于Pawlak属性重要度的属性约简算法2、具体步骤基于Pawlak属性重要度的属性约简算法2、具体步骤75基于Pawlak属性重要度的属性约简算法2、具体步骤思想：从核开始逐个添加，直到满足约简条件。基于Pawlak属性重要度的属性约简算法2、具体步骤思想：从76快速计算属性约简算法[QianShen]快速计算属性约简算法[QianShen]77核等于差别矩阵中所有简单属性（单个属性）元素的集合。基于Skowron差别矩阵的属性约简算法核等于差别矩阵中所有简单属性（单个属性）元素的集合78信息系统的属性约简算法【中文】概要课件79信息系统的属性约简算法【中文】概要课件80信息系统的属性约简算法【中文】概要课件81基于Skowron差别矩阵的属性约简算法具体步骤：思想：从差别矩阵求核，从包含核的属性集中找约简。基于Skowron差别矩阵的属性约简算法具体步骤：思想：从差82差别函数差别函数83信息系统的属性约简算法【中文】概要课件84基于差别函数的信息系统属性约简算法基于差别函数的信息系统属性约简算法85信息系统的属性约简算法【中文】概要课件86基于信息熵的属性约简算法当集合中都是正例或都是负例时，熵的值为0。当正负例各占一半时，熵的值最大为1。即熵越大，样例集越混乱。基本概念对于二类分类问题