信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件

信息系統(tǒng)的屬性約簡(jiǎn)算法

信息系統(tǒng)的特征選擇算法信息系統(tǒng)的屬性約簡(jiǎn)算法

信息系統(tǒng)的特征選擇算法1輸入算法輸出↓↓↓信息系統(tǒng)或決策表約簡(jiǎn)REDUCT屬性約簡(jiǎn)或降維↓屬性子集輸入算法輸出↓↓↓信息系統(tǒng)約簡(jiǎn)屬性約簡(jiǎn)↓屬性子集2Preview1.信息系統(tǒng)是一個(gè)4元組即Preview1.信息系統(tǒng)是一個(gè)4元組即3No.OutlookTemperatureHumidityWindDecision1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo表1.一個(gè)信息系統(tǒng)的例子No.OutlookTemperatureHumidityW42.不可分辨關(guān)系（等價(jià)關(guān)系）給定信息系統(tǒng)，，稱x和y關(guān)于R是不可分辨的，如果2.不可分辨關(guān)系（等價(jià)關(guān)系）給定信息系統(tǒng)5例題對(duì)表1所示信息系統(tǒng)，若R={Outlook}，則樣例1,2,8,9,11關(guān)于等價(jià)關(guān)系（或知識(shí)）Outlook是不可分辨的，因?yàn)樗鼈冊(cè)趯傩設(shè)utlook上的取值是相同的。類似地，樣例3,7,12,13關(guān)于Outlook是不可分辨的；樣例4,5,6,10,14關(guān)于Outlook是不可分辨的。若R={Outlook,Temperature}，則樣例1,2關(guān)于R是不可分辨的；樣例3,13是不可分辨的；樣例4,10,14是不可分辨的；……例題對(duì)表1所示信息系統(tǒng)，63.下近似和上近似給定信息系統(tǒng)，，X關(guān)于R的下近似和上近似分別定義為和3.下近似和上近似給定信息系統(tǒng)7信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件8例題對(duì)表1所示信息系統(tǒng)，設(shè)R={Outlook}，X={1,2,6,8,14}，計(jì)算X關(guān)于R的下近似和上近似。設(shè)R={Outlook,Temperature}，X={3,4,5,7,9,10,11,12,13}，計(jì)算X關(guān)于R的下近似和上近似。注：用知識(shí)R描述決策類的問(wèn)題負(fù)類正類例題對(duì)表1所示信息系統(tǒng)，注：用知識(shí)R描述決策類的問(wèn)題負(fù)類正類9解：(1)根據(jù)下近似的公式先計(jì)算樣例x的R等價(jià)類，分別是：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下近似為空集。注：說(shuō)明僅用R來(lái)描述X(負(fù)類)是不夠的解：(1)根據(jù)下近似的公式先計(jì)算樣例x的R等價(jià)類，分別是：注10解：(1)根據(jù)上近似的公式因?yàn)閁1,

U2,U3和X均有非空交集，故X的R上近似為全集(論域)。(2)可類似求解解：(1)根據(jù)上近似的公式因?yàn)閁1,U2,U3和X均有非空114.Q-P正域給定信息系統(tǒng)，Q的P正域定義為說(shuō)明：若Q為決策屬性子集(一般決策屬性是單屬性)，P為條件屬性子集，則Q-P正域描述的是用知識(shí)R可以完全描述決策類。4.Q-P正域給定信息系統(tǒng)12Q-P邊界域Q-P負(fù)域Q-P邊界域Q-P負(fù)域13Q依賴P的依賴度條件屬性a∈P相對(duì)于決策屬性Q的重要度Q依賴P的依賴度條件屬性a∈P相對(duì)于決策屬性Q的重要度14例題對(duì)表1所示信息系統(tǒng),設(shè)P={Outlook},Q={Decision},計(jì)算信息系統(tǒng)的Q-P正域。解：首先求論域關(guān)于決策屬性Q的劃分，得X1={1,2,6,8,14},X2={3,4,5,7,9,10,11,12,13}負(fù)類正類下面分別求X1和X2關(guān)于P的下近似和。根據(jù)下近似的定義得，而例題對(duì)表1所示信息系統(tǒng),設(shè)P={Outlook},Q={D15從而故這說(shuō)明對(duì)于信息系統(tǒng)U，只要條件屬性O(shè)utlook的值等于Overcast，則可斷定該樣例為負(fù)類。從而故這說(shuō)明對(duì)于信息系統(tǒng)U，只要條件屬性O(shè)utlook的值等165.屬性集的獨(dú)立性給定信息系統(tǒng)，如果對(duì)于任意的下式成立則稱屬性p為P中不必要的（或冗余的），否則稱p為P中不必要的。如果P中任意屬性都是必要的，則稱P是獨(dú)立的。5.屬性集的獨(dú)立性給定信息系統(tǒng)176.屬性約簡(jiǎn)給定信息系統(tǒng)，對(duì)任意的，若P'滿足如下條件則稱P'是P的約簡(jiǎn)6.屬性約簡(jiǎn)給定信息系統(tǒng)187.屬性的核給定信息系統(tǒng)，P中所有必要屬性構(gòu)成的集合稱為P的核，記為CORE(P)7.屬性的核給定信息系統(tǒng)19屬性約簡(jiǎn)算法信息系統(tǒng)的盲目刪除屬性約簡(jiǎn)算法基于Pawlak屬性重要度的屬性約簡(jiǎn)算法基于Skowron差別矩陣的屬性約簡(jiǎn)算法基于信息熵的屬性約簡(jiǎn)算法

屬性約簡(jiǎn)算法20屬性約簡(jiǎn)算法分類依據(jù)有無(wú)啟發(fā)式1、盲目法2、啟發(fā)式算法依據(jù)屬性獲取途徑1、刪除法2、添加法例如：盲目刪除屬性約簡(jiǎn)算法例如：基于Pawlak屬性重要度的屬性約簡(jiǎn)算法，基于差別矩陣的屬性約簡(jiǎn)算法，基于信息熵的屬性約簡(jiǎn)算法等例如：盲目刪除屬性約簡(jiǎn)算法例如：基于屬性重要度的屬性約簡(jiǎn)算法，基于信息熵的屬性約簡(jiǎn)算法等我們常用的大多是啟發(fā)式的添加算法屬性約簡(jiǎn)算法分類依據(jù)有無(wú)啟發(fā)式依據(jù)屬性獲取途徑例如：盲目刪除21信息系統(tǒng)的盲目刪除屬性約簡(jiǎn)算法信息系統(tǒng)的盲目刪除屬性約簡(jiǎn)算法22信息系統(tǒng)的盲目刪除屬性約簡(jiǎn)算法

思想：從屬性全集中逐個(gè)刪除，直到滿足約簡(jiǎn)條件。信息系統(tǒng)的盲目刪除屬性約簡(jiǎn)算法思想：從屬性全集中逐個(gè)刪除23基于Pawlak屬性重要度的屬性約簡(jiǎn)算法屬性重要度度量了屬性對(duì)信息系統(tǒng)的分類能力基于Pawlak屬性重要度的屬性約簡(jiǎn)算法屬性重要度度量了屬性24基于Pawlak屬性重要度的屬性約簡(jiǎn)算法1、構(gòu)造思想基于Pawlak屬性重要度的屬性約簡(jiǎn)算法1、構(gòu)造思想25基于Pawlak屬性重要度的屬性約簡(jiǎn)算法2、具體步驟基于Pawlak屬性重要度的屬性約簡(jiǎn)算法2、具體步驟26基于Pawlak屬性重要度的屬性約簡(jiǎn)算法2、具體步驟思想：從核開(kāi)始逐個(gè)添加，直到滿足約簡(jiǎn)條件?；赑awlak屬性重要度的屬性約簡(jiǎn)算法2、具體步驟思想：從27快速計(jì)算屬性約簡(jiǎn)算法[QianShen]快速計(jì)算屬性約簡(jiǎn)算法[QianShen]28核等于差別矩陣中所有簡(jiǎn)單屬性（單個(gè)屬性）元素的集合。基于Skowron差別矩陣的屬性約簡(jiǎn)算法核等于差別矩陣中所有簡(jiǎn)單屬性（單個(gè)屬性）元素的集合29信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件30信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件31信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件32基于Skowron差別矩陣的屬性約簡(jiǎn)算法具體步驟：思想：從差別矩陣求核，從包含核的屬性集中找約簡(jiǎn)?；赟kowron差別矩陣的屬性約簡(jiǎn)算法具體步驟：思想：從差33差別函數(shù)差別函數(shù)34信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件35基于差別函數(shù)的信息系統(tǒng)屬性約簡(jiǎn)算法基于差別函數(shù)的信息系統(tǒng)屬性約簡(jiǎn)算法36信息系統(tǒng)的屬性約簡(jiǎn)算法-【中文】概要課件37基于信息熵的屬性約簡(jiǎn)算法當(dāng)集合中都是正例或都是負(fù)例時(shí)，熵的值為0。當(dāng)正負(fù)例各占一半時(shí)，熵的值最大為1。即熵越大，樣例集越混亂?；靖拍顚?duì)于二類分類問(wèn)題，是在樣例集合S中正類的比例，是在S中負(fù)類的比例。

分類信息熵：

熵函數(shù)曲線基于信息熵的屬性約簡(jiǎn)算法當(dāng)集合中都是正例或都是負(fù)例時(shí)，熵的值38基于信息熵的屬性約簡(jiǎn)算法什么是信息熵？

信息熵是衡量樣例集類別混亂程度的指標(biāo)。

*信息熵度量了信息源提供的平均信息量的大小信息熵也反映了屬性集合的分類能力*互信息度量了一個(gè)信息源從另一個(gè)信息源獲取的信息量的大小基于信息熵的屬性約簡(jiǎn)算法什么是信息熵？39知識(shí)的信息熵與互信息粗糙集理論把知識(shí)定義為關(guān)于論域的各種劃分模式，那么在論域中任取一個(gè)對(duì)象，它落入哪個(gè)子塊？這具有隨機(jī)性。把粗糙集意義下的知識(shí)看成隨機(jī)變量知識(shí)的信息熵與互信息粗糙集理論把知識(shí)定義為關(guān)于論域的各種劃分401.知識(shí)的概率分布設(shè)U是論域，P，Q是兩個(gè)等價(jià)關(guān)系，設(shè)P和Q在U上導(dǎo)出的劃分為1.知識(shí)的概率分布設(shè)U是論域，P，Q是兩個(gè)等價(jià)關(guān)系，設(shè)P和Q41(1)P,Q在U的子集的概率分布為(1)P,Q在U的子集的概率分布為42(2)P,Q的聯(lián)合概率分布為(2)P,Q的聯(lián)合概率分布為432.知識(shí)的信息熵與互信息定義（知識(shí)P的信息熵H(P)）定義（知識(shí)Q相對(duì)于P的條件熵H(Q|P)）2.知識(shí)的信息熵與互信息定義（知識(shí)P的信息熵H(P)）44定義（知識(shí)P與Q的互信息I(P;Q)）

I(P;Q