基于互信息的屬性約簡改進(jìn)算法

朱 琦劉遵仁李書達(dá)

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,青島 266071)

粗糙集是波蘭數(shù)學(xué)家Pawlack于1982年提出的一種數(shù)學(xué)思想,用來對不確定性知識進(jìn)行分類[1-2],廣泛地用于機(jī)器學(xué)習(xí)、決策分析、數(shù)據(jù)挖掘等眾多領(lǐng)域[3],并在相關(guān)研究中衍生出決策粗糙集、模糊粗糙集、鄰域粗糙集等不同方向,擴(kuò)展了粗糙集理論的應(yīng)用場景[4-7]。屬性約簡是粗糙集理論的核心思想,在保持原始信息系統(tǒng)、知識庫或決策表分類能力不變的情況下,用以刪除知識表達(dá)系統(tǒng)中的冗余或不重要的知識,簡化原有系統(tǒng),并從中提取出相關(guān)知識和有用知識。基于互信息的屬性約簡算法將傳統(tǒng)的屬性重要度算法作為度量標(biāo)準(zhǔn)對條件屬性進(jìn)行篩選,但此算法不能保證得到?jīng)Q策表的最小屬性約簡[8-10]。針對于傳統(tǒng)屬性約簡算法的缺陷,相關(guān)研究提出了許多改進(jìn)算法,一定程度上提高了傳統(tǒng)算法的效率和準(zhǔn)確性,但仍有不足之處[11-12]。如,考慮到單個(gè)屬性與其它屬性間依賴關(guān)系的改進(jìn)屬性重要度算法,每次計(jì)算條件屬性時(shí)都要對其它所有的條件屬性進(jìn)行判斷,增加了算法的時(shí)間復(fù)雜度[13];文獻(xiàn)[14]對傳統(tǒng)算法中重要度定義算法做出相關(guān)改進(jìn),但并不能判斷出哪一個(gè)屬性重要度更高;針對決策類粗糙集提出的局部視角方法并不適用于所有的決策類屬性約簡[15];文獻(xiàn)[16]提出決策規(guī)則的強(qiáng)規(guī)則和弱規(guī)則,生成非冗余規(guī)則,保留必要規(guī)則,刪除不必要屬性,但時(shí)間復(fù)雜度偏高;可變正區(qū)域的約簡方法在屬性約簡時(shí)允許一定的程度變化,但泛化能力有待提高[17]。傳統(tǒng)的粗糙集屬性約簡算法依然存在計(jì)算精度較差、準(zhǔn)確率較低等問題,影響了粗糙集理論的適用范圍和應(yīng)用場景。借鑒已有研究成果,本文針對算法精度較差的問題,引入條件熵,將單個(gè)屬性的重要度加入判斷條件中;針對決策問題,引入了權(quán)重,用以度量互信息和當(dāng)前條件熵之間的權(quán)重大小;在多個(gè)相關(guān)的數(shù)據(jù)集上測試本文算法可行性,并利用兩種不同的分類器驗(yàn)證其準(zhǔn)確性。

1 粗糙集理論概述

定義1正域[18-19]。知識Q相對于知識P的正域?yàn)?或稱其為知識Q的P-正域,記為posP(Q)。

定義2知識的相對約簡[18]。給定一個(gè)知識庫K ＝(U,S)和知識庫上的兩個(gè)等價(jià)關(guān)系P,Q?S,對任意的G?P,若G滿足以下條件:

(1)G是Q獨(dú)立的,即G是P的Q獨(dú)立子族;

(2)posG(Q)＝posP(Q);

則稱G是P的一個(gè)Q約簡,或稱為G是P相對于Q的一個(gè)約簡,記為G∈REDQ(P)。其中,G∈REDQ(P)表示P的全體Q約簡組成的集合。

定義3知識P的信息熵H(P)[20]。給定知識P概率分布,則稱為知識P的信息熵,簡記為H(P)。

定義4知識Q相對于知識P的條件熵H(Q|P)。給定知識P和Q以及各自的概率分布和條件分布,則為知識Q相對于知識P的條件熵,簡記為H(Q|P)[21]。

定義5知識P與Q的互信息I(P;Q)。給定知識P和Q以及各自的概率分布和條件概率分布,則可得到信息熵和條件熵,稱I(P;Q)＝H(Q)－H(Q|P)為知識P與Q的互信息,簡記為I(P;Q)[21]。

2 改進(jìn)的基于互信息的屬性約簡算法

2.1 屬性重要度的定義

傳統(tǒng)的屬性約簡算法,屬性重要度計(jì)算公式為

計(jì)算時(shí)只考慮所選擇的條件屬性加入核屬性集之后相對于決策屬性的互信息,這種思想在加入當(dāng)前條件屬性計(jì)算后所得互信息相同時(shí),并不能有效地判斷加入哪一個(gè)條件屬性可以得到最優(yōu)的決策規(guī)則。絕大多數(shù)情況下傳統(tǒng)算法可以得到?jīng)Q策表的一個(gè)屬性約簡,但不能保證得到?jīng)Q策表的最小屬性約簡。

本文提出了一種新的結(jié)合互信息和條件熵的度量方法,相比于傳統(tǒng)算法,在計(jì)算屬性重要度時(shí)加入了對條件屬性本身?xiàng)l件熵的度量[22];考慮到每一個(gè)條件屬性自身的信息熵對屬性重要度的影響,選取自身信息量少的屬性加入核屬性集,從而得到相對最優(yōu)的決策規(guī)則。

設(shè)決策信息表DT＝(U,C∪D,V,f),C是條件屬性集,D是決策屬性集,且有核屬性集B∈C,對于任意非核屬性c i∈CB的基于信息熵的重要性Sig(c i,B,D)定義為:在核屬性集中和加入某個(gè)非核屬性后的條件熵與該屬性自身的信息量之比的差值

由Sig(c i,B,D)定義可知,屬性重要度隨著作為基數(shù)的屬性自身的信息量H(c i)的增大而減小,因?yàn)楫?dāng)H(c i)大時(shí),屬性c i會有更多的不同值,從而導(dǎo)致最終的決策包含更多的規(guī)則,若要得到最優(yōu)決策規(guī)則,應(yīng)取H(c i)最小值(如若需要查看更多的決策信息而不求獲得最優(yōu)決策規(guī)則時(shí),可選H(c i)最大值,需要注意的是,若決策表信息量很大時(shí),所得決策規(guī)則會非常龐大)。相比之前的核屬性,添加屬性c i后,Sig(c i,B,D)越大,對決策屬性的影響越大,屬性c i就越重要。

2.2 算法執(zhí)行過程

本文算法是基于互信息的決策表屬性約簡思想求得屬性的相對約簡。首先判斷決策表是否相容,若不相容,需進(jìn)行處理,具體方法見文獻(xiàn)[23]。繼而得到?jīng)Q策表的差別矩陣,由差別矩陣可以快速分析出決策表的核屬性,之后進(jìn)行非核屬性的屬性約簡:每次從非核屬性集中選取Sig(c i,B,D)值最大的屬性加入和屬性集,同時(shí)分析是否滿足I(B,D)＝I(C,D),滿足則輸出當(dāng)前約簡B,否則繼續(xù)從剩余非核屬性集中選取屬性重復(fù)上述計(jì)算,直到滿足I(B,D)＝I(C,D)的條件,結(jié)束計(jì)算。

Step1計(jì)算DT 中條件屬性C和決策屬性D的互信息:I(C,D)＝H(D)－H(D|C);

Step2計(jì)算C相對于D的核Core(B);

Step3計(jì)算I(B,D)＝H(D)－H(D|B),若I(B,D)＝I(C,D),則跳轉(zhuǎn)到Step 5,否則執(zhí)行Step 4;

Step4對于所有的c i∈CB,計(jì)算式(2),求得maxSig(c i,B,D),令B ＝B∪{c i},轉(zhuǎn)到Step 3;

Step5輸出B即為所求,算法結(jié)束。

3 實(shí)例分析與實(shí)驗(yàn)測試

3.1 實(shí)例分析

為驗(yàn)證算法的有效性,選用氣象狀況實(shí)例表,見表1。其中,條件屬性集C＝{a1(Outlook),a2(Temperature),a3(Humidity),a4(Windy)},決策屬性D＝{N,P}表示分類。將屬性值用英文首字母代替:a1＝{sunny(S),overcast(O),rain(R)},a2＝{hot(H),mild(M),cool(C)},a3＝{high(H),normal(N)},a4＝{false(F),true(T)}。

表1 決策表

Step1求矩陣M s(14×14),長度為1的元素包含的屬性即為核屬性,M s包含的核屬性為B ＝{a1,a4};

Step2計(jì)算I(C,D)＝H(D)－H(D|C)＝0.94－0＝0.94;

Step3計(jì)算I(B,D)＝H(D)－H(D|B)＝0.94－0.34＝0.60≠I(C,D),則繼續(xù)計(jì)算;

Step4計(jì)算式(2),取α＝0.9,Sig(c i,B,D)＝α[H(D|B)－H(D|B∪{c i})]－(1－α)H(c i)＝0.9×(0.34－0)－0.1×1.5566＝0.150,Sig(c i,B,D)＝α[H(D|B)－H(D|B∪{c i})]－(1－α)H(c i)＝0.9×(0.34－0)－0.1×1＝0.206;Sig(c3,B,D)＞Sig(c2,B,D),令B ＝B∪{c i}＝{a1,a3,a4};

Step5再次計(jì)算I(C,D)＝H(D)－H(D|C)＝0.94－0＝0.94＝I(C,D),輸出B ＝{a1,a3,a4}即為所求。

利用傳統(tǒng)判別函數(shù)式(1)計(jì)算得到B＝{a1,a2,a4}或B＝{a1,a3,a4},都可作為結(jié)果,因?yàn)閭鹘y(tǒng)判別函數(shù)在計(jì)算屬性重要度時(shí)沒有加入對條件屬性本身?xiàng)l件熵的度量,在加入某個(gè)屬性后得到的互信息相同時(shí),算法即終止,無法作出進(jìn)一步的判斷。這就存在局限性,尤其是在面對數(shù)據(jù)集中的兩個(gè)屬性相近,或數(shù)據(jù)集龐大屬性較多時(shí),很難給出確切的屬性約簡,導(dǎo)致結(jié)果不夠準(zhǔn)確。而改進(jìn)算法將B ＝{a1,a3,a4}做為最終的約簡結(jié)果。因?yàn)楦倪M(jìn)算法在計(jì)算中加入了對單個(gè)屬性自身?xiàng)l件熵的考量,在兩個(gè)或多個(gè)條件屬性加入計(jì)算時(shí),可區(qū)分兩個(gè)屬性重要度大小,從而得出更精準(zhǔn)的屬性約簡結(jié)果,獲得更精簡的決策規(guī)則。

3.2 實(shí)驗(yàn)測試

3.2.1 UCI數(shù)據(jù)集測試 在Intel Core(TM)i5－8500T CPU 和8GB內(nèi)存PC計(jì)算機(jī)上,window10環(huán)境下運(yùn)行Python 3.7進(jìn)行實(shí)驗(yàn)測試。從UCI數(shù)據(jù)集中選取了6個(gè)數(shù)據(jù)集,驗(yàn)證算法的可行性。分別比較傳統(tǒng)的CEBARKCC算法(記為算法A)和本文改進(jìn)算法(記為算法B,α＝0.9)的約簡結(jié)果和時(shí)間,時(shí)間取每個(gè)數(shù)據(jù)集執(zhí)行10次的平均值。實(shí)驗(yàn)結(jié)果見表2。

表2 兩種算法對數(shù)據(jù)集的測試結(jié)果

由實(shí)驗(yàn)結(jié)果可知,改進(jìn)算法可以得到相對決策規(guī)則更少的正確的屬性約簡,且時(shí)間消耗與原算法接近,時(shí)間消耗稍多出來的部分是對H(c i)的計(jì)算,本文算法具有可行性。

3.2.2 選用分類器測試 為了驗(yàn)證改進(jìn)算法約簡出的屬性集合的有效性,在兩種不同的分類器Knn算法和決策樹算法中分別驗(yàn)證。對CEBARKCC算法約簡的屬性集(算法A)、改進(jìn)算法(算法B)約簡的屬性集進(jìn)行分類精度驗(yàn)證,數(shù)據(jù)為100次測試結(jié)果取均值,結(jié)果見表3。

表3中兩種分類器關(guān)于兩種不同算法屬性約簡分類精度的折線圖如圖1、圖2所示。算法B與算法A時(shí)間復(fù)雜度相同(算法B需計(jì)算H(c i),兩算法最壞情況下均為O(n2)),但算法B能得到更優(yōu)的屬性約簡規(guī)則。值得注意的是α的取值,以上測試均在α＝0.9時(shí)測得,在同一個(gè)數(shù)據(jù)集上,微調(diào)α?xí)顾惴˙較算法A 有1%～5%左右的精度提升。當(dāng)H(c i)被賦予的權(quán)重過高時(shí),將導(dǎo)致不同的屬性約簡,數(shù)據(jù)的條件屬性越多時(shí)差異會越大。考慮到用H(c i)信息熵當(dāng)作參考數(shù)據(jù),經(jīng)測試一般取0.8≤α＜1比較適合。

表3 兩種算法在不同分類器下對數(shù)據(jù)集測試結(jié)果

圖1 兩種算法在Knn分類器下的精度折線圖

圖2 兩種算法在Tree分類器下的精度折線圖

數(shù)據(jù)集屬性數(shù)量過小或數(shù)據(jù)差別不大時(shí),兩種算法精確率大致相當(dāng)。但在Robotnavigation數(shù)據(jù)集上,算法B在兩種分類器上精度都有明顯提升,因?yàn)楫?dāng)數(shù)據(jù)量較大時(shí),數(shù)據(jù)的差異性也會增加,相較于算法A,算法B加入了對每個(gè)屬性條件熵的判別,于是得到了更加精準(zhǔn)的屬性約簡結(jié)果和更高的準(zhǔn)確率。在實(shí)際應(yīng)用中,數(shù)據(jù)集均包含大量數(shù)據(jù),算法B便有更加明顯的實(shí)際性能提升。因此,本文改進(jìn)的屬性約簡算法可用于knn分類器和決策樹分類器中,分類結(jié)果相對準(zhǔn)確,具有可行性。

4 結(jié)論

本文從信息論的角度分析決策表屬性約簡問題,結(jié)合條件屬性本身的互信息,提出了改進(jìn)的屬性約簡算法。在保證時(shí)間復(fù)雜度不增加的情況下,本文改進(jìn)算法相較于傳統(tǒng)算法得到了更好的約簡結(jié)果,在約簡精度上有明顯提升。通過對UCI數(shù)據(jù)集和分類器的測試,驗(yàn)證了改進(jìn)算法的有效性。如何在不增加額外計(jì)算量的情況下得到更好的屬性約簡結(jié)果是今后有待解決的問題。