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

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

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

信息系統(tǒng)的特征選擇算法1輸入算法輸出↓↓↓信息系統(tǒng)或決策表約簡REDUCT屬性約簡或降維↓屬性子集輸入算法輸出↓↓↓信息系統(tǒng)約簡屬性約簡↓屬性子集2Preview1.信息系統(tǒng)是一個4元組即Preview1.信息系統(tǒng)是一個4元組即3No.OutlookTemperatureHumidityWindDecision1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo表1.一個信息系統(tǒng)的例子No.OutlookTemperatureHumidityW42.不可分辨關系（等價關系）給定信息系統(tǒng)，，稱x和y關于R是不可分辨的，如果2.不可分辨關系（等價關系）給定信息系統(tǒng)5例題對表1所示信息系統(tǒng)，若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所示信息系統(tǒng)，63.下近似和上近似給定信息系統(tǒng)，，X關于R的下近似和上近似分別定義為和3.下近似和上近似給定信息系統(tǒng)7信息系統(tǒng)的屬性約簡算法【中文】概要課件8例題對表1所示信息系統(tǒng)，設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所示信息系統(tǒng)，注：用知識R描述決策類的問題負類正類9解：(1)根據(jù)下近似的公式先計算樣例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)根據(jù)下近似的公式先計算樣例x的R等價類，分別是：注10解：(1)根據(jù)上近似的公式因為U1,

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

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

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

分類信息熵：

熵函數(shù)曲線基于信息熵的屬性約簡算法當集合中都是正例或都是負例時，熵的值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的聯(lián)合概率分布為(2)P,Q的聯(lián)合概率分布為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.構(gòu)造思想：基于信息熵的屬性約簡算法1.構(gòu)造思想：46基于信息熵的屬性約簡算法2.具體步驟：基于信息熵的屬性約簡算法2.具體步驟：47基于信息熵的屬性約簡算法基于信息熵的屬性約簡算法48謝謝！謝謝！49信息系統(tǒng)的屬性約簡算法

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

信息系統(tǒng)的特征選擇算法50輸入算法輸出↓↓↓信息系統(tǒng)或決策表約簡REDUCT屬性約簡或降維↓屬性子集輸入算法輸出↓↓↓信息系統(tǒng)約簡屬性約簡↓屬性子集51Preview1.信息系統(tǒng)是一個4元組即Preview1.信息系統(tǒng)是一個4元組即52No.OutlookTemperatureHumidityWindDecision1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo表1.一個信息系統(tǒng)的例子No.OutlookTemperatureHumidityW532.不可分辨關系（等價關系）給定信息系統(tǒng)，，稱x和y關于R是不可分辨的，如果2.不可分辨關系（等價關系）給定信息系統(tǒng)54例題對表1所示信息系統(tǒng)，若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所示信息系統(tǒng)，553.下近似和上近似給定信息系統(tǒng)，，X關于R的下近似和上近似分別定義為和3.下近似和上近似給定信息系統(tǒng)56信息系統(tǒng)的屬性約簡算法【中文】概要課件57例題對表1所示信息系統(tǒng)，設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所示信息系統(tǒng)，注：用知識R描述決策類的問題負類正類58解：(1)根據(jù)下近似的公式先計算樣例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)根據(jù)下近似的公式先計算樣例x的R等價類，分別是：注59解：(1)根據(jù)上近似的公式因為U1,

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

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

思想：從屬性全集中逐個刪除，直到滿足約簡條件。信息系統(tǒng)的盲目刪除屬性約簡算法思想：從屬性全集中逐個刪除72基于Pawlak屬性重要度的屬性約簡算法屬性重要度度量了屬性對信息系統(tǒng)的分類能力基于Pawlak屬性重要度的屬性約簡算法屬性重要度度量了屬性73基于Pawlak屬性重要度的屬性約簡算法1、構(gòu)造思想基于Pawlak屬性重要度的屬性約簡算法1、構(gòu)造思想74基于Pawlak屬性重要度的屬性約簡算法2、具體步驟基于Pawlak屬性重要度的屬性約簡算法2、具體步驟75基于Pawlak屬性重要度的屬性約簡算法2、具體步驟思想：從核開始逐個添加，直到滿足約簡條件。基于Pawlak屬性重要度的屬性約簡算法2、具體步驟思想：從76快速計算屬性約簡算法[QianShen]快速計算屬性約簡算法[QianShen]77核等于差別矩陣中所有簡單屬性（單個屬性）元素的集合?；赟kowron差別矩陣的屬性約簡算法核等于差別矩陣中所有簡單屬性（單個屬性）元素的集合78信息系統(tǒng)的屬性約簡算法【中文】概要課件79信息系統(tǒng)的屬性約簡算法【中文】概要課件80信息系統(tǒng)的屬性約簡算法【中文】概要課件81基于Skowron差別矩陣的屬性約簡算法具體步驟：思想：從差別矩陣求核，從包含核的屬性集中找約簡?；赟kowron差別矩陣的屬性約簡算法具體步驟：思想：從差82差別函數(shù)差別函數(shù)83信息系統(tǒng)的屬性約簡算法【中文】概要課件84基于差別函數(shù)的信息系統(tǒng)屬性約簡算法基于差別函數(shù)的信息系統(tǒng)屬性約簡算法85信息系統(tǒng)的屬性約簡算法【中文】概要課件86基于信息熵的屬性約簡算法當集合中都是正例或都是負例時，熵的值為0。當正負例各占一半時，熵的值最大為1。即熵越大，樣例集越混亂?；靖拍顚τ诙惙诸悊栴}