基于糾纏關(guān)系的變精度優(yōu)勢關(guān)系粗糙集模型

劉力凱 李建林 劉金林

1(南京信息職業(yè)技術(shù)學(xué)院 江蘇 南京 210023) 2(揚州大學(xué) 江蘇 揚州 225002)

0 引 言

隨著社會的發(fā)展與科技的進(jìn)步，信息已從TB量級躍升至PB量級。數(shù)據(jù)中高效的知識發(fā)現(xiàn)需要突破傳統(tǒng)數(shù)據(jù)挖掘僅能獲取單粒度知識、表達(dá)力弱、知識黑箱和效率低下等問題的局限。針對多源異構(gòu)、海量動態(tài)的復(fù)雜數(shù)據(jù)，通過復(fù)雜問題的多粒度思維模式，運用不確定性知識發(fā)現(xiàn)的粗糙集近似逼近理論，構(gòu)建多粒度粗糙集知識發(fā)現(xiàn)模型，建立漸進(jìn)式粗糙集知識發(fā)現(xiàn)方法對于大量需求分析研究顯得十分重要。

在該背景下，本文以優(yōu)勢關(guān)系粗糙集為理論工具，借助優(yōu)勢關(guān)系粗糙集從知識本身發(fā)現(xiàn)規(guī)律、規(guī)則的可解釋性和以確定的方法研究不確定性問題等特點，將數(shù)據(jù)轉(zhuǎn)化為優(yōu)勢粗糙集決策表，采用對象?；乃枷雽⒂嬎銓ο罅；瑥亩奖銛?shù)據(jù)處理，并從中提取有效信息。

粗糙集理論[1](Rough Set Theory)由Pawlak教授于1982年提出，作為一種刻畫不完全、不確定的數(shù)學(xué)工具，其依據(jù)統(tǒng)計和推理從數(shù)據(jù)自身發(fā)現(xiàn)知識，不需依賴任何先驗知識，能有效地處理不精確、不一致和不完整等各類信息，以精確的手段處理不精確的問題，從中發(fā)現(xiàn)隱含知識，揭示潛在規(guī)律。優(yōu)勢關(guān)系粗糙集[2](Dominance-based Rough Set Approach，DRSA)由Greco等[3]提出，可以認(rèn)為經(jīng)典粗糙集屬于其特例。作為一種數(shù)據(jù)挖掘工具，優(yōu)勢關(guān)系粗糙集同樣根據(jù)統(tǒng)計和推理從數(shù)據(jù)本身推導(dǎo)知識，同時能有效處理屬性間的偏序關(guān)系，能很好地處理不一致和不完備信息[4-5]。

針對優(yōu)勢關(guān)系模型中下近似求解過于嚴(yán)格，同時上近似求解過于寬松的現(xiàn)象，可變精度優(yōu)勢粗糙集[6](Variable Consistency Model of DRSA，VC-DRSA)使用DOMLEM算法[7]解決了問題，算法生成if-then類型知識規(guī)則[8]，利于領(lǐng)域?qū)＜覍λ@知識進(jìn)行理解和分析，并能解決規(guī)則沖突問題，其有效應(yīng)用于決策分類[9]，已在屬性約簡[10-11]、多指標(biāo)排序[12]、疾病風(fēng)險評估[13]、評價方法研究[14-15]、航空顧客行為預(yù)測[16]、故障診斷研究[17]和移動用戶換機(jī)預(yù)測[18]等諸多領(lǐng)域?qū)嵤┝藦V泛的應(yīng)用[19]。

數(shù)據(jù)不一致性可由數(shù)據(jù)邊界的猶豫性和數(shù)據(jù)采集過程中的人為錯誤、數(shù)據(jù)缺失等因素造成。在實際應(yīng)用中，不一致對象的存在限制了更多的對象進(jìn)入粗糙集下近似，不利于決策規(guī)則的提取。傳統(tǒng)優(yōu)勢關(guān)系粗糙集在處理不一致對象時往往有一定的局限性。Greco等[6]研究了一種基于包含度的變精度優(yōu)勢關(guān)系粗糙集方法模型，但是它不能有效地處理由于異常數(shù)據(jù)帶來的不一致性。針對這種情況的不足，Inuiguchi等[20]研究了一種基于支持度的變精度優(yōu)勢關(guān)系粗糙集(Variable-Precision DRSA, VP-DRSA)方法模型，但它不能有效地利用邊緣對象的信息。為了使決策表提供的有益信息得到充分利用，包含更多的數(shù)據(jù)對象信息，需要對模型處理不一致對象的能力來做進(jìn)一步研究。

本文在分析已有優(yōu)勢關(guān)系粗糙集方法模型處理不一致信息局限性的前提下，研究了一種基于糾纏關(guān)系的優(yōu)勢關(guān)系粗糙集方法模型，其通過優(yōu)勢關(guān)系將屬性相似、功能近似的對象進(jìn)行整合，構(gòu)建復(fù)雜的對象實體，并通過數(shù)據(jù)實驗驗證了該模型對于消除不一致對象影響的有效性。

1 優(yōu)勢關(guān)系粗糙集理論

為了便于敘述, 引入一些關(guān)于優(yōu)勢關(guān)系粗糙集方法模型的基本理論[2-3,21]。

定義1決策表信息系統(tǒng)。設(shè)S為決策表信息系統(tǒng)，S=，其中U為該系統(tǒng)的論域，Q為屬性集合，Q=C∪D，條件屬性集合為C，決策屬性集合為D，D≠?，C∩D=?，屬性值的集合為V=q∈QVq，Vq為屬性q∈Q的屬性值域，f:U×Q→V為信息函數(shù)，f(x,q)∈Vq，(x,q)∈U×Q。

定義2優(yōu)勢關(guān)系。令≥代表論域U中的弱偏好關(guān)系，則x≥qy表示x在條件屬性q上至少與y一樣好，即x不差于y。優(yōu)勢關(guān)系定義為DP:P?C,?x,y∈U,xDPy。如果q∈P，則x≥qy。

定義3上并集和下并集。將論域U通過決策屬性D劃分為集合Cl，有Cl={Clt,t∈T}，T={1,2，…,n}，則?x∈U，x僅能屬于某個分類Clt,Clt∈Cl。上并集的定義為：

(1)

對任意r,s∈T,如果r>s,可知Clr集合內(nèi)的元素均優(yōu)于Cls集合內(nèi)的元素。下并集的定義為：

(2)

對任意r,s∈T,如果r

定義4優(yōu)勢集和劣勢集。對于任意P?C,x∈U,y∈U,優(yōu)勢集的定義為:

(3)

劣勢集的定義為：

(4)

定義5上下并集的下近似、上近似和邊界域。上并集下近似的定義為：

(5)

上并集上近似的定義為：

(6)

上并集的邊界域的定義為：

(7)

下并集下近似的定義為：

(8)

下并集上近似的定義為：

(9)

下并集邊界域的定義為:

(10)

定義6VC-DRSA模型的可變精度上下近似?？勺兙鹊纳喜⒓陆贫x為:

(11)

可變精度的下并集下近似定義為:

(12)

式中：l為變精度參數(shù)，由人為設(shè)定。

定義7VP-DRSA模型的可變精度上下近似。可變精度的上并集下近似定義為:

(13)

可變精度的下并集下近似定義為:

(14)

定義8近似精度和近似分類質(zhì)量。上并集近似精度定義為:

(15)

下并集近似精度定義為:

(16)

近似分類質(zhì)量定義為:

(17)

2 糾纏關(guān)系變精度優(yōu)勢關(guān)系粗糙集

傳統(tǒng)優(yōu)勢關(guān)系粗糙集中，如果需建立兩個樣本之間的優(yōu)勢關(guān)系，必須要保證某個樣本在所有屬性上比另一個樣本好或者差。但這種關(guān)系過于嚴(yán)苛，忽略了在某些屬性上好而另一些屬性上差的樣本。另一方面，雖然進(jìn)入優(yōu)勢集或劣勢集的樣本之間統(tǒng)計意義一樣，但好一點點的樣本和好一個數(shù)量級的樣本同樣進(jìn)入當(dāng)前樣本的優(yōu)勢集合，它們與當(dāng)前樣本的聯(lián)系和所帶來的有效信息卻大不一樣。

2.1 VC-DRSA模型的分析

如表1所示，這是一張包含學(xué)號、數(shù)學(xué)成績、文學(xué)成績和通過情況的學(xué)生評價決策表，其構(gòu)成一個不一致決策表信息系統(tǒng)，其中包含不一致對象信息。

表1 學(xué)生評價決策表

求解求解圖1 模型下近似求解

2.2 VP-DRSA模型的分析

通過多組實驗及調(diào)整一致性水平l發(fā)現(xiàn)，VC-DRSA對于處理邊緣猶豫數(shù)據(jù)較好而處理樣本異常點時存在不足。而VP-DRSA對于處理樣本異常點較好而邊緣猶豫數(shù)據(jù)存在不足。

2.3 EVC-DRSA模型

針對VC-DRSA和VP-DRSA模型對于異常點和邊緣猶豫數(shù)據(jù)處理的不足，本文提出了一種基于糾纏關(guān)系的變精度優(yōu)勢關(guān)系粗糙集(Entangled Variable Consistency Model of DRSA, EVC-DRSA)。為了充分考慮這些不能進(jìn)入優(yōu)勢集或劣勢集的樣本帶來的影響，同時對不同優(yōu)劣數(shù)量級的樣本加以區(qū)分利用，本節(jié)從粒計算的角度提出了一種數(shù)據(jù)糾纏關(guān)系，并以此為基礎(chǔ)提出一種基于糾纏關(guān)系的變精度EVC-DRSA模型。

在傳統(tǒng)優(yōu)勢關(guān)系粗糙集中，嚴(yán)格具有優(yōu)勢關(guān)系的樣本，才可相互進(jìn)入優(yōu)勢集或劣勢集，見式(3)和式(4)。但這種關(guān)系過于嚴(yán)苛，當(dāng)存在不一致數(shù)據(jù)時，忽略了在某些屬性上好而在另一些屬性上差的樣本，這些樣本間則不能建立聯(lián)系，從而影響了上、下近似的求解精度。另一方面，進(jìn)入優(yōu)勢集或劣勢集的樣本雖然在統(tǒng)計上一樣，都增加了優(yōu)勢集或劣勢集對象的個數(shù)，但實際上它們是有區(qū)別的。以優(yōu)勢集為例，好一點點的樣本和好一個數(shù)量級的樣本同時進(jìn)入當(dāng)前樣本的優(yōu)勢集合，在統(tǒng)計上它們是一樣的，但實際上與當(dāng)前樣本的聯(lián)系緊密度卻大不一樣。

為了充分考慮不一致信息帶來的影響，本文提出了一種數(shù)據(jù)糾纏關(guān)系，以兩個屬性的數(shù)據(jù)為例，數(shù)據(jù)間的糾纏關(guān)系如圖2所示。

圖2 數(shù)據(jù)的糾纏關(guān)系演示

圖2中有四個二維數(shù)據(jù)樣本d1、d2、d3和d4，坐標(biāo)值越大代表此樣本在相應(yīng)屬性上表現(xiàn)越好。通過觀察可知，d3在attr2屬性上比d1好，即d3≥attr2d1,d3在attr1屬性上比d1差,即d1≥attr1d3，則d3和d1無法確定優(yōu)勢關(guān)系。同樣，d2≥attr1d3，d3≥attr2d2，d3和d2也無法確定優(yōu)勢關(guān)系。此時，對于樣本d3而言，d1和d2進(jìn)入了d3的不確定域。

定義9元素的不確定域。對于x∈U，定義x的不確定域Sx為：

Sx=U-D+(x)-D-(x)

(18)

元素x的不確定域為論域中不能進(jìn)入元素x優(yōu)勢集和劣勢集的對象集合，即無法與元素x確定明確的優(yōu)劣關(guān)系的對象集合，Sx中的元素在某些屬性上比x好，其他屬性比x差。

對于圖2中的數(shù)據(jù)，由于d1和d2均進(jìn)入了d3的不確定域，d1和d2在d3的不確定域中地位相等，因此當(dāng)d3作為觀察樣本時，導(dǎo)致了d1和d2在某種程度上的不明朗，從d3的角度無法推斷出d1和d2之間的直接關(guān)系，則約定d1和d2是相互糾纏的。另一種情況，不存在觀察樣本使得d1和d4同時進(jìn)入該樣本的不確定域，因此d1和d4不存在數(shù)據(jù)糾纏關(guān)系。在實際中，具有數(shù)據(jù)糾纏關(guān)系的樣本點之間聯(lián)系更加緊密。

一般的，對于數(shù)據(jù)樣本x和y，如果存在觀察樣本q，使得x和y均進(jìn)入了q的不確定域，則稱x和y是外部不可分辨的，從而定義x和y具有數(shù)據(jù)糾纏關(guān)系。論域U上和x具有數(shù)據(jù)糾纏關(guān)系的元素構(gòu)成的集合，定義為x的糾纏域。

定義10元素的糾纏域。對于x∈U，定義x的糾纏域Qx為：

Qx={y∈U:Sx∩Sy≠?}∪x′

(19)

元素x的糾纏域為論域中對象的不確定域與x的不確定域有交疊的元素集合。x′為x的克隆對象，其意義是x與其本身是糾纏的。對于?x∈U，約定當(dāng)所有Sx∩Sy=?,x≠y時，Qx∈U=U，因為不存在特殊的非克隆對象對任意x有特殊的作用，即約定整個論域中的元素都糾纏在一起。元素x糾纏域中的所有元素與x的關(guān)系均不明朗。以表1學(xué)生評價決策表為例，S1和S3的糾纏域分別如圖3(a)和圖3(b)的框內(nèi)所示。

(a) 對象S1的糾纏域 (b) 對象S3的糾纏域圖3 對象糾纏域

在圖3(a)中，QS1={S1,S2,S3,S4,S5,S6}，其構(gòu)成S1的糾纏域。因為存在觀察樣本S7或S8，使得S1與QS1內(nèi)任何元素都同時進(jìn)入S7或S8的不確定域，導(dǎo)致外部不可分辨關(guān)系發(fā)生，所以S1與QS1內(nèi)任何元素都具有數(shù)據(jù)糾纏關(guān)系。

(20)

(21)

由于上下近似的互補性，進(jìn)一步可以得到：

(22)

(23)

(24)

(25)

(26)

(27)

求解糾纏關(guān)系的變精度DRSA模型的上、下近似集過程可以看作是一個粒度計算[22-23]過程，它將信息按其特征和性能劃分為不同的粒度，元素的糾纏域和非糾纏域可以看作是不同的粒劃分，受元素所處環(huán)境不同導(dǎo)致糾纏域不同，相當(dāng)于?；某潭炔煌２煌氐牟煌m纏域可以看作不同的粒層次。

定義12近似分類質(zhì)量。決策表信息系統(tǒng)近似分類質(zhì)量定義為：

(28)

令P=C，l取最合適值，如圖4所示，可知VC-DRSA的一致水平l=0.75時效果最好。如圖5所示，EVC-DRSA的一致水平l=0.75時效果最好，VP-DRSA的一致水平l=0.75時效果最好。

圖4 VC-DRSA一致水平參數(shù)l取值實驗

圖5 EVC-DRSA一致水平參數(shù)l取值實驗

圖6 EVC-DRSA模型求解結(jié)果

3 評價標(biāo)準(zhǔn)和實驗結(jié)果

為了驗證EVC-DRSA模型的有效性，我們設(shè)計了如下的對比實驗。由于在數(shù)據(jù)集特性未知情況下，認(rèn)為由異常點造成的數(shù)據(jù)不一致性比猶豫數(shù)據(jù)造成的數(shù)據(jù)不一致性更加難以容忍，因此分別測試VP-DRSA模型和EVC-DRSA模型的下并集分類從屬正確率，使用VC-DOMLEM規(guī)則提取算法提取決策規(guī)則，選用ERA、ESL、ELV和SWD這4個數(shù)據(jù)集[24]。其中ESL數(shù)據(jù)集不一致性程度較高，ERA、ELV和SWD數(shù)據(jù)集不一致性極高，很好地符合了不一致信息系統(tǒng)決策規(guī)則的分析提取要求。

根據(jù)定義1可知ERA、ESL、ELV和SWD這4個數(shù)據(jù)集分別構(gòu)成4個決策表信息系統(tǒng)，其中每個信息系統(tǒng)的條件屬性集合C都由多個元素qx構(gòu)成。對于論域U中的每一條記錄d，將它們按照決策屬性D對論域U的劃分進(jìn)行優(yōu)勢排序,在最理想的預(yù)期下，di和di+1應(yīng)該有嚴(yán)格的優(yōu)勢關(guān)系，即對于?q∈C,一定有di≥qdi+1或di+1≥qdi，且這種關(guān)系在?q上保持一致。在實際數(shù)據(jù)集中，由于各種原因總會造成不一致信息的存在，造成數(shù)據(jù)之間并不存在嚴(yán)格的優(yōu)勢關(guān)系，di≥qdi+1或di+1≥qdi將被打破，此時結(jié)合定義9，總會存在某個元素x，使得x的不確定域Sx≠?，從而可以建立數(shù)據(jù)間的糾纏關(guān)系，并通過定義10求解出x的糾纏域。

為了達(dá)到實驗結(jié)果的客觀要求，本文采用5重交叉驗證法，隨機(jī)將數(shù)據(jù)平均分成5份執(zhí)行5次循環(huán)，在第i次循環(huán)中取其中第i份(1≤i≤5)作為測試集合，剩下的4份作為學(xué)習(xí)集合，取最高的實驗結(jié)果作為最終實驗結(jié)果，以下并集分類從屬正確率(DPCC)作為衡量。VP-DRSA模型的一致水平設(shè)為0.75。EVC-DRSA模型的一致水平設(shè)為0.75。測試結(jié)果如表2所示。

表2 模型EVC-DRSA有效性測試(%)

由表2可知，在LEV、SWD數(shù)據(jù)集上EVC-DRSA下并集分類從屬正確率與VP-DRSA相等，ESL和ERA數(shù)據(jù)集效果較好，驗證了EVC-DRSA模型的有效性。

4 結(jié) 語

數(shù)據(jù)中有大量不一致數(shù)據(jù)存在，現(xiàn)有的變精度DRSA模型對處理異常點和邊緣猶豫數(shù)據(jù)帶來的不一致性存在局限性。本文通過優(yōu)勢關(guān)系設(shè)計了一種基于糾纏關(guān)系的DRSA模型。其將屬性相似、功能近似的對象進(jìn)行整合，構(gòu)建復(fù)雜的對象實體，充分考慮了不能進(jìn)入優(yōu)勢集和劣勢集元素對當(dāng)前樣本的影響，同時建立糾纏域區(qū)分了不同元素對求解下近似的影響，將僅在統(tǒng)計上對求解產(chǎn)生影響，但實際聯(lián)系不緊密的元素排除，從而去除該部分包含的不一致對象，達(dá)到不一致對象消除的目的。在今后研究中，可建立基于數(shù)據(jù)驅(qū)動的自主式動態(tài)學(xué)習(xí)方法，以減弱先驗知識在知識獲取中的依賴，例如變精度DRSA模型一致水平參數(shù)的確定需要對其進(jìn)行遍歷實驗。因此，如何通過數(shù)據(jù)本身確定參數(shù)的取值，從而簡化實驗過程、強化不一致信息在處理中的適應(yīng)性，顯得十分重要。