改進(jìn)的屬性頻率約簡(jiǎn)算法

改進(jìn)的屬性頻率約簡(jiǎn)算法

0屬性約簡(jiǎn)算法厚集理論是波蘭哲學(xué)家j.pawlak在1982年提出的一種智能決策分析數(shù)學(xué)工具。它是研究不完整,不確定知識(shí)和數(shù)據(jù)的表達(dá)、學(xué)習(xí)、歸納的理論方法。粗糙集目前主要被廣泛地應(yīng)用與數(shù)據(jù)挖掘、人工智能、模式識(shí)別、網(wǎng)頁(yè)分類(lèi)、故障診斷和專(zhuān)家系統(tǒng)等領(lǐng)域。屬性約簡(jiǎn)是粗糙集理論中重要的核心內(nèi)容之一。屬性約簡(jiǎn)主要目的是保持知識(shí)庫(kù)分類(lèi)能力不變的條件下,刪除其中不相關(guān)或不重要的屬性,從而簡(jiǎn)化原有的系統(tǒng)。雖然Wond等已經(jīng)證明找出一個(gè)決策表的所有約簡(jiǎn)和最小約簡(jiǎn)是NP-hard問(wèn)題,但是利用啟發(fā)式信息減小搜索空間,還是能得到一個(gè)相對(duì)最優(yōu)的約簡(jiǎn)。以基于可辨識(shí)矩陣的屬性頻率約簡(jiǎn)算法為基礎(chǔ),引入強(qiáng)等價(jià)集概念,以屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多,其重要性越大為啟發(fā)式信息。提出一種新的有效的屬性約簡(jiǎn)算法,該算法可以處理當(dāng)屬性頻率相同時(shí),對(duì)決策表的屬性約簡(jiǎn)可以高效準(zhǔn)確的進(jìn)行。1相關(guān)概念和證明1.1aa,vb,av形式上,四元組S=(U,A,V,f)是一個(gè)知識(shí)表達(dá)系統(tǒng),其中U為對(duì)象的非空有限集合,稱(chēng)為論域;A為屬性的非空有限集合;V=a∈∪AVa,Va是屬性a的值域;f為U×A※V是一個(gè)信息函數(shù),它為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值,即對(duì)于所有的a∈A,x∈X,f(x,a)∈Va。知識(shí)表達(dá)系統(tǒng)也稱(chēng)為智能系統(tǒng)。通常也用S=(U,A)來(lái)代替S=(U,A,V,f)。1.2q作為約簡(jiǎn)的定義在信息系統(tǒng)S中,對(duì)于PC,則P在S的不可分辨關(guān)系IND(P)定義為:定義1:設(shè)Q?P,如果Q是獨(dú)立的,并且IND(Q)=IND(P),則稱(chēng)Q是P的一個(gè)約簡(jiǎn)。P中所有必要關(guān)系的集合稱(chēng)為P的核,用CORE(P)來(lái)表示。其中:i,j=1,2,…,n。1.4區(qū)分矩陣中其它項(xiàng)的交為空設(shè)a∈A,如果存在某一集合B?[a],則稱(chēng)集合B是屬于a的強(qiáng)等價(jià)集。定理2:A的子集B?A是強(qiáng)等價(jià)集的充分必要條件是:B被區(qū)分矩陣中2個(gè)或2個(gè)以上項(xiàng)同時(shí)包含,且B與區(qū)分矩陣中其它項(xiàng)的交為空。定理3:如果C是一個(gè)約簡(jiǎn),B是強(qiáng)等價(jià)集,且{a,b}∈B,則{a,b}不包含于C。此定理可用反證法證明,證明過(guò)程如下:證明:假定C是一個(gè)約簡(jiǎn),且有{a,b}?C因?yàn)閧a,b}∈B且B是強(qiáng)等價(jià)集,所以有Dis({a})=Dis(),于是有Dis(C-{a})=Dis(a)即IND(C-{a})=IND(C),這與C是一個(gè)約簡(jiǎn)相矛盾,因此應(yīng)有{a,b}不包含于C?？梢?jiàn),任何一個(gè)約簡(jiǎn)最多只能包含強(qiáng)等價(jià)集中的一個(gè)屬性,簡(jiǎn)而言之,強(qiáng)等價(jià)集中的屬性是可以約簡(jiǎn)的。2基于可識(shí)別矩陣屬性頻率的約簡(jiǎn)化算法2.1基于價(jià)值分析的屬性區(qū)分胡可云博士提出關(guān)于屬性頻率有兩種重要的啟發(fā)式思想:(1)屬性在可辨識(shí)矩陣中出現(xiàn)的次數(shù)越多,該屬性的重要性越大;(2)在可辨識(shí)矩陣中屬性項(xiàng)越短,屬性的重要性越大。由思想(2)可知:在可辨識(shí)矩陣中,可能會(huì)有一些只有1個(gè)屬性的屬性項(xiàng),則這個(gè)惟一的屬性一定是核屬性,可直接把它加入到約簡(jiǎn)集中。提出一種新的計(jì)算屬性頻率的函數(shù):在文獻(xiàn)中,算法的缺陷在于不能很好地解決出現(xiàn)2個(gè)屬性頻率相同時(shí)的情況。針對(duì)這個(gè)問(wèn)題,這里引入強(qiáng)等價(jià)集概念對(duì)屬性進(jìn)行區(qū)分。定理2表明強(qiáng)等價(jià)集中的屬性對(duì)分類(lèi)具有相同的重要性。利用定理3判斷,當(dāng)屬性頻率相同時(shí)是否有屬性包含在強(qiáng)等價(jià)集中,可以保留出現(xiàn)在強(qiáng)等價(jià)集中的某個(gè)屬性去掉其他屬性。2.2屬性頻率約簡(jiǎn)的使用,在一般輸入:決策表S=(U,C∪D,V,f),其中C={a1,a2,…,an};輸出:決策表的約簡(jiǎn)集Red。(1)把決策表S轉(zhuǎn)化成相應(yīng)的可辨識(shí)矩陣M,并初始化候選約簡(jiǎn)集合Red=?,令counterai=0;(2)將可辨識(shí)矩陣中屬性組合數(shù)為1的條件屬性(核屬性)直接加到約簡(jiǎn)集Red中,去掉含有核屬性的屬性項(xiàng);(3)利用屬性頻率函數(shù)g(ai)對(duì)剩余屬性項(xiàng)中的各屬性計(jì)算屬性頻率。判斷是否有屬性頻率相同的屬性,有則轉(zhuǎn)(4),否轉(zhuǎn)(5);(4)對(duì)有相同屬性頻率的屬性用定理2判斷是否為強(qiáng)等價(jià)集,若是則在可辨識(shí)矩陣M中保留強(qiáng)等價(jià)集中任一屬性去除其他屬性。否則轉(zhuǎn)(5);(5)找出屬性頻率最高的屬性記作a1則Red=Red∪{a1},去掉可辨識(shí)矩陣中含有屬性a1的屬性組合;(6)判斷可辨識(shí)矩陣是否為?,是結(jié)束,否則轉(zhuǎn)(3)。顯然,該算法給處理具有相同屬性頻率的決策表屬性約簡(jiǎn)提供了較好的方法。大量數(shù)據(jù)表明遇到出現(xiàn)相同屬性頻率的情況非常多,所以該算法的實(shí)用性很廣泛。與文獻(xiàn)的算法相比,改進(jìn)的基于屬性頻率的算法的實(shí)現(xiàn)對(duì)條件屬性的更優(yōu)的約簡(jiǎn),其計(jì)算的主要時(shí)間花費(fèi)在計(jì)算g(ai)上,為O(|C||U|2),而原算法的時(shí)間復(fù)雜度亦為O(|C||U|2),可見(jiàn)新的算法在保持計(jì)算的時(shí)間復(fù)雜度不變的前提下,得到更精確的約簡(jiǎn)結(jié)果。3強(qiáng)等價(jià)集的建立表1是一個(gè)信息系統(tǒng)。應(yīng)用這里改進(jìn)算法對(duì)該信息系統(tǒng)進(jìn)行屬性約簡(jiǎn)。式(2)為可辨識(shí)矩陣:式(3)為去掉核屬性后的可辨識(shí)矩陣:表1變換成對(duì)應(yīng)的可辨識(shí)矩陣,得式(1)所對(duì)應(yīng)的可辨識(shí)矩陣。式(2)是在式(1)的基礎(chǔ)上由算法第(2)步得到P為核屬性直接加入到約簡(jiǎn)Red中后,去掉含有P的屬性項(xiàng)得到化簡(jiǎn)后的新可辨識(shí)矩陣;在新的可辨識(shí)矩陣中可以得出屬性B,M頻率一樣,g(B)=g(M)=12.33,{B,M}有可能是強(qiáng)等價(jià)集,此時(shí)再利用定理1求出原辨識(shí)矩陣的強(qiáng)等價(jià)集為{B,M},根據(jù)強(qiáng)等價(jià)集的定理2在可辨識(shí)矩陣中可以去掉M保留B,最后得到的約簡(jiǎn)合{P,B}。再去掉含有B的屬性項(xiàng),此時(shí)可辨識(shí)矩陣為則算法結(jié)束。而按照文獻(xiàn)中的算法得到的約簡(jiǎn)集合{P,B,M},又由定理2中關(guān)于強(qiáng)等價(jià)集的性質(zhì)中可知,含在強(qiáng)等價(jià)集中的屬性是可以約簡(jiǎn)的,所以{P,B,M}是最后的約簡(jiǎn)結(jié)果。實(shí)例證明新算法可以實(shí)現(xiàn)更加有精確的數(shù)據(jù)屬性約簡(jiǎn)。4屬性約簡(jiǎn)的存儲(chǔ)及約簡(jiǎn)劃分由于現(xiàn)實(shí)信息系統(tǒng)的數(shù)據(jù)復(fù)雜度很高,出現(xiàn)相同頻率屬性的幾率很大,所以在基于粗糙集屬性頻率的約簡(jiǎn)算法的基礎(chǔ)上,引入強(qiáng)等價(jià)集概念,較好地解決了出現(xiàn)相同屬性頻率時(shí)屬性約簡(jiǎn)的問(wèn)題,具有一定的實(shí)際意義和應(yīng)用價(jià)值。與原算法相比,在保持計(jì)算速度保持不變的前提下實(shí)現(xiàn)了對(duì)信息系統(tǒng)更為精確的屬性約簡(jiǎn)。IND(P)={(x,y)∈U2|a∈P,a(x)=a(y)}IND(P)把對(duì)象集U劃為k個(gè)等價(jià)類(lèi),記為U/P={X1,X2,…,Xk}。定理1:簇集P的核等于P的所有約簡(jiǎn)的交集。即CORE(P)=∩RED(P)。1.3屬性axj令決策表系統(tǒng)