不完備決策信息系統(tǒng)的一種新的粒度約簡(jiǎn)算法

1粒度約簡(jiǎn)算法在大粒度粗糙的情況下，粒度約簡(jiǎn)是一個(gè)重要的問(wèn)題。在計(jì)算不影響目標(biāo)決策的前提下，粒度約簡(jiǎn)可以獲得一個(gè)無(wú)冗余粒度的粒度空間子集，并且更小的粒度空間可以降低對(duì)信息系統(tǒng)的處理的復(fù)雜性。為了簡(jiǎn)化決策信息系統(tǒng)的粒度，文獻(xiàn)[6]首次提出了采用大粒徑近似粒度的粒度約簡(jiǎn)化的啟動(dòng)算法。文獻(xiàn)[9-10]采用了基于波動(dòng)近似粒度的粒度約簡(jiǎn)化算法。文獻(xiàn)[11]根據(jù)大粒徑近似矩陣的粒度約簡(jiǎn)化方法提出了基于粒度矩陣的粒度約簡(jiǎn)化算法。由于上述粒度約簡(jiǎn)算法適用于不完整的決策信息系統(tǒng)，因此存在缺陷。這些算法沒(méi)有考慮不完整決策信息系統(tǒng)的屬性值的損失。數(shù)據(jù)集越完整，越有利于識(shí)別和提取規(guī)則，因此屬性值的損失是我們必須考慮的一個(gè)重要問(wèn)題。針對(duì)不完備決策信息系統(tǒng),本文給出了粒度上屬性值缺失率的定義,結(jié)合粒度重要度和粒度上屬性值缺失率定義了粒度組合重要度.然后,設(shè)計(jì)了新的基于粒度組合重要度的粒度約簡(jiǎn)算法,通過(guò)調(diào)節(jié)參數(shù),該算法在保證粒度約簡(jiǎn)率的同時(shí)能夠得到屬性值缺失率較低的約簡(jiǎn)結(jié)果.最后,通過(guò)實(shí)例分析和仿真實(shí)驗(yàn)說(shuō)明了本文所提算法的優(yōu)勢(shì)和有效性.2相關(guān)概念2.1屬性的集合屬性的集合定義1設(shè)S=(U,C∪D,V,f)是一個(gè)決策信息系統(tǒng),U為論域;設(shè)A=C∪D為有限屬性集合;C是條件屬性的集合,D是決策屬性的集合;V=定義2定義3設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),對(duì)于Xue020U,Bue020C,X的關(guān)于容差關(guān)系的下、上近似集合和邊界域分別定義為:式中,T定義4設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A定義5設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A定義6設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A2.2不完備決策信息系統(tǒng)在多粒度環(huán)境下,有些粒度對(duì)目標(biāo)決策來(lái)說(shuō)是冗余的,通過(guò)粒度約簡(jiǎn)去除這些冗余的粒度是一個(gè)關(guān)鍵問(wèn)題定義7設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A若定義8設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A3基于粒度組合的重要程度的粒度約為本節(jié),針對(duì)不完備決策信息系統(tǒng),首先給出粒度上屬性值缺失率的定義,然后結(jié)合粒度重要度3.1粒度重要度度量對(duì)于一個(gè)給定的決策信息系統(tǒng),在進(jìn)行粒度約簡(jiǎn)時(shí),對(duì)于目標(biāo)決策我們需要確定哪些粒度是重要的,以及重要度的大小.定義9在A中關(guān)于X是不重要的;在A中關(guān)于X是重要的.定理1由該定理可知,在樂(lè)觀多粒度粗糙集中,對(duì)象集合下近似中對(duì)象的個(gè)數(shù)與粒度空間的大小成正相關(guān).在悲觀多粒度粗糙集中,我們也可以得出類似的結(jié)論,對(duì)象集合下近似中對(duì)象的個(gè)數(shù)與粒度空間的大小成負(fù)相關(guān).因此,可以利用下近似中對(duì)象個(gè)數(shù)的變化來(lái)衡量粒度的重要性.定義10(1)(2)粒度重要度的值越大,說(shuō)明在已知粒度集A基于上述粒度重要度,文獻(xiàn)[11]提出了一種啟發(fā)式粒度約簡(jiǎn)算法,每次選取重要度最大的粒度加入約簡(jiǎn)集合,直到其下近似分布與原始粒度空間下近似分布一致.但如果面對(duì)的是不完備決策信息系統(tǒng),約簡(jiǎn)之后的信息系統(tǒng)完備度越高越利于準(zhǔn)確的對(duì)其進(jìn)行提取規(guī)則等處理.因此,在對(duì)不完備決策信息系統(tǒng)進(jìn)行粒度約簡(jiǎn)時(shí),考慮屬性值的缺失情況具有重要意義.3.2粒度組合重要度定義11設(shè)S=(U,C∪D,V,f)是不完備決策信息系統(tǒng),A={A式中,α+β=1.顯然,在計(jì)算粒度組合重要度時(shí)考慮了粒度上屬性值缺失率的影響.通過(guò)調(diào)節(jié)α和β的值可以改變Sig(A3.3基于粒度組合重要度的粒度約簡(jiǎn)算法粒度約簡(jiǎn)算法的基本過(guò)程如下:首先獲得一個(gè)原始粒度空間下不可除去的粒度集合(粒度約簡(jiǎn)核),然后以這個(gè)粒度集為起點(diǎn),以粒度組合重要度為啟發(fā),每次選擇當(dāng)前粒度空間下最為重要的粒度加入到約簡(jiǎn)粒度集中,直到其下近似分布與原始粒度空間下近似分布一致.由定義6和定理1可知,下近似分布的變化可以通過(guò)近似質(zhì)量的變化來(lái)體現(xiàn),算法中利用近似質(zhì)量來(lái)作為粒度選取的終止條件.求取決策類的下近似是粒度約簡(jiǎn)中的重要步驟,以樂(lè)觀多粒度粗糙集為例,首先給出多個(gè)粒空間下求對(duì)象集合下近似算法.算法1計(jì)算下近似的時(shí)間復(fù)雜度為算法2不完備決策信息系統(tǒng)中基于粒度組合重要度的粒度約簡(jiǎn)算法.該算法中步驟2、步驟3以及步驟4的時(shí)間復(fù)雜度為4粒度約簡(jiǎn)計(jì)算例1設(shè)一個(gè)不完備決策信息系統(tǒng)S如表1,其中x(1)以定義11中的粒度重要度為啟發(fā)進(jìn)行樂(lè)觀多粒度的粒度約簡(jiǎn),初始粒度約簡(jiǎn)集首先,求出核粒度,因?yàn)槿缓?以這個(gè)核粒度集RED°為起點(diǎn),通過(guò)定義10計(jì)算余下粒度的粒度重要度,(2)以粒度組合重要度為啟發(fā)進(jìn)行樂(lè)觀多粒度的粒度約簡(jiǎn).取α=β=0.5,初始粒度約簡(jiǎn)集首先,求出核粒度為RED°={A由上述計(jì)算可知,以粒度重要度為啟發(fā)得到的粒度約簡(jiǎn)結(jié)果為A(1)計(jì)算A(2)計(jì)算A5屬性值缺失率本文所提粒度約簡(jiǎn)算法是以粒度組合重要度為啟發(fā)來(lái)進(jìn)行粒度選取的,為了說(shuō)明本文所提算法在處理不完備決策信息系統(tǒng)時(shí)的有效性,將本文所提算法(算法2)與以粒度重要度選用UCI數(shù)據(jù)庫(kù)中3個(gè)數(shù)據(jù)集TeachingAssistantEvaluation,Zoo,MolecularBiology(下文簡(jiǎn)稱Teaching,Zoo,Molecular)進(jìn)行測(cè)試,數(shù)據(jù)集的具體信息見(jiàn)表2.為了模擬多粒度的場(chǎng)景,數(shù)據(jù)集Teaching,Zoo從第一個(gè)條件屬性開(kāi)始以每2個(gè)屬性為一個(gè)粒度,數(shù)據(jù)集Molecular從第一個(gè)條件屬性開(kāi)始以每4個(gè)屬性為一個(gè)粒度,若條件屬性個(gè)數(shù)不能剛好被劃分,則最后剩余的條件屬性構(gòu)成一個(gè)粒度.(1)算法2中參數(shù)設(shè)置為α=0.1,β=0.9,比較兩種算法對(duì)不同數(shù)據(jù)集進(jìn)行粒度約簡(jiǎn)后的屬性值缺失率和約簡(jiǎn)率.為了模擬數(shù)據(jù)集中不同的屬性值缺失率情況,相對(duì)于原始條件屬性值總數(shù),利用隨機(jī)函數(shù)將其中5%、10%、15%、20%屬性值設(shè)置為缺失值,本次實(shí)驗(yàn)對(duì)于每個(gè)不完備數(shù)據(jù)集實(shí)驗(yàn)100次,然后取平均值作為結(jié)果,實(shí)驗(yàn)結(jié)果如圖1.由實(shí)驗(yàn)所得可知,三個(gè)數(shù)據(jù)集不同的屬性值缺失率情況下,算法2粒度約簡(jiǎn)之后約簡(jiǎn)集上的屬性值缺失率均低于算法3.兩種算法約簡(jiǎn)后的粒度約簡(jiǎn)率如表3.由表3可知,在不同的屬性值缺失率情況下,對(duì)于數(shù)據(jù)集Teaching、Molecular,算法2的粒度約簡(jiǎn)率略微低于或等于算法3,對(duì)于數(shù)據(jù)集Zoo,算法2的粒度約簡(jiǎn)率略微高于或等于算法3.總體來(lái)看,算法2與算法3的粒度約簡(jiǎn)率非常接近.由上述實(shí)驗(yàn)可知,算法2在基本保證粒度約簡(jiǎn)率的同時(shí)能夠得到屬性值缺失率較低的粒度約簡(jiǎn)結(jié)果.(2)實(shí)驗(yàn)二:參數(shù)α、β的不同取值下,比較兩種算法約簡(jiǎn)后的屬性值缺失率和約簡(jiǎn)率.選用數(shù)據(jù)集Zoo進(jìn)行實(shí)驗(yàn),每次設(shè)置缺失10%的數(shù)據(jù),實(shí)驗(yàn)100次,然后取平均值.由表4可知,當(dāng)α=0.5,β=0.5時(shí),算法2粒度約簡(jiǎn)后的約簡(jiǎn)集上屬性值缺失率最低;當(dāng)α=0.9,β=0.1時(shí),算法2粒度約簡(jiǎn)能夠得到約簡(jiǎn)率等于算法3但屬性值缺失率低于算法3的約簡(jiǎn)結(jié)果.所以,通過(guò)調(diào)節(jié)參數(shù)α、β的取值,本文所提算法可以得到滿足不同需要的粒度約簡(jiǎn)結(jié)果.6粒度約簡(jiǎn)算法本文以不完備決策