粗糙集預(yù)測(cè)算法的穩(wěn)定性分析

張曉霞，陳德剛

(1.華北電力大學(xué) 控制與計(jì)算機(jī)工程學(xué)院，北京 102206；2.華北電力大學(xué) 數(shù)理學(xué)院，北京 102206)

0 引言

粗糙集理論[1]作為數(shù)據(jù)分析及知識(shí)發(fā)現(xiàn)的重要工具一直備受關(guān)注,如今粗糙集已廣泛應(yīng)用于機(jī)器學(xué)習(xí)[2]、數(shù)據(jù)挖掘[3]、決策分析[4]、專家系統(tǒng)[5]、智能控制等領(lǐng)域[6-7].由于決策信息系統(tǒng)中通常包含重復(fù)樣本或不一致樣本集(相同條件屬性不同決策屬性)，因此由其誘導(dǎo)的決策規(guī)則具有不確定性，自然地規(guī)則的測(cè)量以及算法的設(shè)計(jì)就成了粗糙集理論急需解決的問(wèn)題之一.考慮到不一致決策信息系統(tǒng)的普遍性和重要性，文中主要考慮粗糙集預(yù)測(cè)算法的泛化能力.

目前，關(guān)于粗糙集的研究主要集中于構(gòu)造預(yù)測(cè)算法的學(xué)習(xí)準(zhǔn)則[8-10].Dai等[8]利用算法分類(lèi)一致率提出了一個(gè)新的粗糙集算法；Skowron[9]基于一致矩陣和布爾邏輯提出了誘導(dǎo)規(guī)則方法；Yasdi[10]基于粗糙集模型設(shè)計(jì)了提取規(guī)則算法.這些算法都有一個(gè)共同目標(biāo)：通過(guò)決策信息系統(tǒng)設(shè)計(jì)一個(gè)準(zhǔn)則，然后根據(jù)這個(gè)準(zhǔn)則預(yù)測(cè)新樣本的標(biāo)簽.然而這些方法卻沒(méi)有數(shù)值刻畫(huà)算法的預(yù)測(cè)能力，即度量學(xué)習(xí)準(zhǔn)則的算法的性能-泛化誤差.眾所周知，算法的穩(wěn)定性和泛化誤差分析是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中最基本的問(wèn)題，對(duì)該問(wèn)題目前已有很多研究[11-16]，其中最突出的就是算法的擾動(dòng)性分析[12]，用來(lái)測(cè)量訓(xùn)練集在微小變動(dòng)情況下輸出結(jié)果的變化.根據(jù)擾動(dòng)性可以建立魯棒性較好的系統(tǒng)，Bousquet等[13]基于擾動(dòng)性分析定義了算法的穩(wěn)定性，并且解釋了如何根據(jù)經(jīng)驗(yàn)誤差和留一誤差求得算法的泛化界.Wu等[14]利用留二法研究了學(xué)習(xí)算法的穩(wěn)定性，并且定義了幾種不同的留二法穩(wěn)定性并研究了這些穩(wěn)定性之間的關(guān)系.Rudin等[17]利用文獻(xiàn)[13]的結(jié)果分析了最大置信度最小支持度及調(diào)節(jié)置信度算法的泛化界，這兩種方法可以用來(lái)做序列事件預(yù)測(cè)及監(jiān)督學(xué)習(xí).基于這些考慮，本文利用算法穩(wěn)定性研究粗糙集預(yù)測(cè)算法的泛化界.

文中設(shè)計(jì)了置信度算法，該算法可以預(yù)測(cè)新樣本的標(biāo)簽，其原理就是尋找訓(xùn)練集中與新樣本相同的等價(jià)類(lèi)，然后分配與該等價(jià)類(lèi)置信度最高的標(biāo)簽給新樣本.首先定義了置信度函數(shù)，其次利用最小化算子定義了其損失函數(shù)，最后利用算法的穩(wěn)定性給出了置信度算法的泛化界.結(jié)果表明，泛化界主要與決策信息系統(tǒng)中樣本的數(shù)目及穩(wěn)定性參數(shù)有關(guān).對(duì)于大樣本機(jī)制的決策信息系統(tǒng)，樣本越多其誘導(dǎo)的決策規(guī)則越多，因此經(jīng)驗(yàn)誤差更逼近泛化誤差，同時(shí)上界也更小.

1 預(yù)備知識(shí)

1.1 粗糙集

設(shè)S=(U,C,D=j5i0abt0b)是一個(gè)決策信息系統(tǒng)，其中U={x1,x2,…,xn}為非空有限論域，C={c1,c2,…,cn}為非空有限條件屬性集(特征)，D=j5i0abt0b是決策屬性(標(biāo)簽).設(shè)Vc和Vd是特征c∈C和d的值域，記C(x)=(c1(x),c2(x),…,cn(x))∈Vc和D(x)∈VD分別為x關(guān)于特征C和決策屬性D的值域.每個(gè)樣本x可用條件屬性和決策屬性表示，即x:(C(x),D(x))∈Z=VC×VD，則決策信息系統(tǒng)可表示為

對(duì)任意的B?C，定義不可區(qū)分關(guān)系

則由INd(B)誘導(dǎo)的x的等價(jià)類(lèi)為

[x]B={y∈U|c(x)=c(y),?c∈B}.

對(duì)任意的X?U，定義X的B下近似集和B上近似集分別為

論域U關(guān)于IND(C)的劃分為U/IND(C)={Φ1,Φ2,…,Φp}，其中Φj(j=1,2,…,p)是x關(guān)于IND(C)的等價(jià)類(lèi),U/IND(D)={Ψ1,Ψ2,…,Ψr}是U關(guān)于IND(D)的劃分，Ψj(j=1,2,…,r)稱為決策類(lèi).每個(gè)決策類(lèi)的上下近似可以用來(lái)誘導(dǎo)決策規(guī)則.

決策規(guī)則[18-19]在粗糙集中可以表示為

C(x)→D(x)，

其中

C(x)和D(x)分別稱為規(guī)則C(x)→D(x)的前件和結(jié)論.規(guī)則C(x)→D(x)的置信度定義為

其中#(·)表示集合所含元素的個(gè)數(shù).若fS,0(C(x),D(x))=1，則決策規(guī)則C(x)→D(x)是確定性規(guī)則；否則是不確定的.

1.2 穩(wěn)定性

如文獻(xiàn)[5]所述，訓(xùn)練集通常表示為

其中xi∈X稱為輸入，yi∈Y稱為xi的輸出，X×Y獨(dú)立同分布于未知分布D.

l(f,z)=c(f(x),y).

算法的泛化是定義在訓(xùn)練集S上的隨機(jī)變量，即

由于分布D未知，所以借助經(jīng)驗(yàn)誤差Remp(A,S)和留一誤差Rloo(A,S)來(lái)近似R(A,S)，即

其中Si={z1,z2,…,zi-1,zi+1,…,zm}.

給定帶有m個(gè)樣本的訓(xùn)練集S，PS[·]表示S關(guān)于Dm的概率，ES[·]為S關(guān)于Dm的期望.同樣地，Px[·]和Es[·]分別為樣本x關(guān)于D的概率和期望.

2 粗糙集預(yù)測(cè)的穩(wěn)定性

粗糙集預(yù)測(cè)旨在從決策信息系統(tǒng)中學(xué)習(xí)規(guī)則從而對(duì)新樣本預(yù)測(cè)標(biāo)簽.本節(jié)主要介紹如何基于粗糙集的置信度預(yù)測(cè)算法，并利用算法穩(wěn)定性[5]刻畫(huà)其泛化能力.

2.1 穩(wěn)定性

給定決策信息系統(tǒng)S={x1=(C(x1),D(x1)),…,xm=(C(xm),D(xm))}.假設(shè)每條規(guī)則在S中至少出現(xiàn)2次，即樣本中每個(gè)樣本都存在與其具有相同條件和決策屬性的其他樣本.事實(shí)上該假設(shè)在大樣本機(jī)制下是普遍的，當(dāng)樣本數(shù)m相對(duì)大時(shí)，每個(gè)樣本都會(huì)重復(fù)出現(xiàn)多次，這也是粗糙集理論獨(dú)特于其他理論之處.

粗糙集預(yù)測(cè)的主要任務(wù)是構(gòu)造分類(lèi)器，這里采用置信度測(cè)量規(guī)則C(x)→D(x)的可信度，則基于置信度的分類(lèi)器構(gòu)造如下：

(1)

gfS,0(x)主要用來(lái)尋找前件為C(x)且置信度最高的規(guī)則的后件，即

若|gfS,0(x)|>1，則滿足最大置信度的標(biāo)簽不唯一，此時(shí)隨機(jī)選一個(gè)作為x的標(biāo)簽，該算法稱為基于粗糙集的置信度預(yù)測(cè)算法.

公式(1)表明：如果新樣本x與訓(xùn)練集中某一樣本y具有相同的特征值，則x的決策值是以C(y)為前件且置信度最大的規(guī)則的后件，并不一定與y的結(jié)論相同;若x與訓(xùn)練集中任一樣本的特征值都不同，則置信度為0,任意的標(biāo)簽都可賦給x.

2.2 置信度預(yù)測(cè)算法的損失函數(shù)

為了討論算法的穩(wěn)定性，首先定義損失函數(shù).給定一個(gè)帶標(biāo)簽的樣本x:=(C(x),D(x))，決策規(guī)則C(x)→D(x)的置信度f(wàn)S,0的損失函數(shù)l(fS,0,C(x)→D(x))定義為

l(fS,0,C(x)→D(x))=min{1,1-Ω},

其中

稱該損失函數(shù)為最小邊界損失函數(shù).

當(dāng)間隔Ω≤0時(shí)，l(fS,0,C(x)→D(x))=1;若Ω>0時(shí)，損失值就是其間隔值的補(bǔ)償值，即1-Ω.關(guān)于損失函數(shù)l的經(jīng)驗(yàn)誤差為

泛化誤差是損失函數(shù)的期望，即

下面考慮用經(jīng)驗(yàn)誤差近似估計(jì)泛化誤差，即盡可能地最小化

|TrueErr(fS,0)-EmpErr(fS,0)|，

該問(wèn)題可以轉(zhuǎn)化為:對(duì)任意的ε>0，最小化

PS[|TrueErr(fS,0)-EmpErr(fS,0)|>ε].

為方便討論，首先引入以下記號(hào)：

·移除第i個(gè)對(duì)象，Si={x1,…,xi-1,xi+1,…,xn};

由于假設(shè)每條規(guī)則至少在訓(xùn)練集中出現(xiàn)2次，所以當(dāng)移除或替換某個(gè)樣本后，規(guī)則數(shù)目不會(huì)減少，但置信度會(huì)變化，因此留一法的邊界損失為

粗糙預(yù)測(cè)算法的穩(wěn)定性基于多維隨機(jī)函數(shù)的一階差分建立，下面定理1對(duì)隨機(jī)變量的方差[20]給出了上界，定理2是指數(shù)界[21].

則

粗糙預(yù)測(cè)算法的穩(wěn)定性基于多維隨機(jī)函數(shù)的一階差分建立.

2.3 置信度預(yù)測(cè)算法的穩(wěn)定性及泛化界

類(lèi)似于文獻(xiàn)[13]中定理17，下面討論置信度算法的穩(wěn)定性.算法穩(wěn)定性的概念最早提出于20世紀(jì)70年代，主要用來(lái)測(cè)量算法在訓(xùn)練集有微小變動(dòng)(移除或刪除一個(gè)元素)時(shí)算法的泛化能力.類(lèi)似于文獻(xiàn)[13]中定義15，下面給出置信度算法強(qiáng)穩(wěn)定性的概念.

定義1置信度算法關(guān)于邊界損失函數(shù)l具有強(qiáng)穩(wěn)定性β，如果對(duì)任意的有

其中∞范數(shù)對(duì)所有規(guī)則適用.

定義1可以誘導(dǎo)得到置信度算法的一致穩(wěn)定性.根據(jù)文獻(xiàn)[13]，置信度的點(diǎn)對(duì)假設(shè)穩(wěn)定性定義如下：

定義2置信度算法關(guān)于邊界損失函數(shù)l具有點(diǎn)對(duì)假設(shè)穩(wěn)定性β，如果對(duì)任意的k∈{1,2,…,m}有

當(dāng)改變某個(gè)樣本時(shí)，訓(xùn)練集中可能會(huì)新增一條規(guī)則，因此點(diǎn)對(duì)假設(shè)穩(wěn)定性考慮了平均邊界損失.

引理1若置信度算法關(guān)于邊界損失函數(shù)l具有強(qiáng)穩(wěn)定性β，則其具有一致穩(wěn)定性.

證明

其中

其中第一個(gè)不等式利用絕對(duì)值的三角不等式，第二個(gè)不等式利用強(qiáng)穩(wěn)定性的定義. 】

下面利用點(diǎn)對(duì)假設(shè)穩(wěn)定性給出了置信度算法的泛化界，其證明類(lèi)似于文獻(xiàn)[13]的定理11.

定理3設(shè)S是一個(gè)含有m(m≥2)個(gè)元素的決策信息系統(tǒng)，置信度算法關(guān)于邊界損失函數(shù)l具有點(diǎn)對(duì)假設(shè)穩(wěn)定性β，則對(duì)任意的δ∈(0,1)，以下結(jié)果至少以概率1-β成立：

定理3表明置信度算法的泛化界由樣本數(shù)m和穩(wěn)定性參數(shù)β控制：樣本數(shù)越多，參數(shù)β越小，泛化界越小.事實(shí)上當(dāng)樣本數(shù)增多時(shí)，算法的學(xué)習(xí)能力也會(huì)增強(qiáng)，同時(shí)樣本數(shù)增多會(huì)給新樣本提供更多參考，因此增加樣本數(shù)從而提高算法泛化能力的估計(jì)是很容易理解的.同樣地，當(dāng)穩(wěn)定性參數(shù)β減小時(shí)，改變訓(xùn)練集中的某個(gè)樣本，邊界損失的平均值改變很小，充分說(shuō)明改變樣本對(duì)算法的影響不大，反應(yīng)了算法良好的穩(wěn)定性.因此β越小，對(duì)算法的泛化界的估計(jì)越精確.

下面計(jì)算定理3中點(diǎn)對(duì)假設(shè)穩(wěn)定性的β的具體值.首先引入下列符號(hào)：

#k([z]C)表示等價(jià)類(lèi)[z]C的樣本個(gè)數(shù)，其中z∈Sk,[z]C表示刪除第k個(gè)樣本之后論域Sk生成的等價(jià)類(lèi)，即[z]C∈Sk;

因此

表示除規(guī)則C(x)→D(x)之外，在S上生成的所有決策規(guī)則C(x)→D(y)的最高置信度與Sk上生成的所有決策規(guī)則C(x)→D(y)的最高置信度的差.

定理4設(shè)S是一個(gè)含有m(m≥2)個(gè)元素的決策信息系統(tǒng)，由S生成的規(guī)則集為

則對(duì)任意規(guī)則C(x)→D(x)∈AS,有

(2)|fS,0(C(x),D(x))-

fSk,0(C(x),D(x))|≤

證明(1)C(x)表示x的特征值，#(C(x))表示與x具有相同特征的樣本數(shù)目，因此

刪除第k個(gè)樣本，則xk要么屬于[x]C要么不屬于,所以

首先計(jì)算

的上界.根據(jù)置信度算法，樣本x在Sk誘導(dǎo)的規(guī)則C(x)→gfSk,0(x)的置信度超過(guò)C(x)→gfS,0(x)的置信度，即

因此

同理，x在S上誘導(dǎo)的規(guī)則C(x)→gfS,0(x)的置信度超過(guò)C(x)→gSk,0(x)的置信度，即

從而

因此

(2)當(dāng)xk從S中刪除后,

i)若xk∈[x]C∩[x]D，則

因此

由于假設(shè)每條規(guī)則至少出現(xiàn)2次，因此

易得

從而

ii)若xk∈[x]C∧Ck?[x]C∩[x]D，則

因此

iii)若xk?[x]C，則

fS,0(C(x),D(x))-fSk,0(C(x),D(x))=0.

從而

定理4給出了置信度算法強(qiáng)穩(wěn)定性的β值，定理4(2)刻畫(huà)了同一條規(guī)則在刪除樣本前后置信度的變化.結(jié)果表明置信度算法的強(qiáng)穩(wěn)定性參數(shù)與等價(jià)類(lèi)的大小有關(guān)，等價(jià)類(lèi)越粗，穩(wěn)定性參數(shù)越小.

推論1根據(jù)引理1和定理3，對(duì)任意的C(x)→D(x)∈AS，有

證明利用定理4和三角不等式易得. 】

推論1刻畫(huà)了置信度算法的一致穩(wěn)定性，且其穩(wěn)定性參數(shù)與等價(jià)類(lèi)大小有關(guān).

引理2設(shè)S是一個(gè)含有m(m≥2)個(gè)元素的決策信息系統(tǒng)，對(duì)任意的等價(jià)類(lèi)[x]C∈S/C，有

其中pC(x)是樣本x取特征值C(x)的概率.

由于等價(jià)類(lèi)[x]C服從二項(xiàng)分布，即#([x]C)～B(m,pC(x))，引理2的證明可參考文獻(xiàn)[22].

定理5設(shè)S是一個(gè)含有m(m≥2)個(gè)元素的決策信息系統(tǒng)，置信度算法滿足點(diǎn)對(duì)假設(shè)穩(wěn)定性β，由系統(tǒng)生成的規(guī)則集為

則對(duì)任意的γ>0及δ>0，不等式

TrueErr(fS,0)≤EmpErr(fS,0)+β1,

至少以概率1-δ成立,其中

證明由于推論1對(duì)所有規(guī)則都通用，根據(jù)引理2，對(duì)規(guī)則C(xk)→D(xk)，有

對(duì)任意的xk∈S,pmin≤pC(xk)，根據(jù)引理2，對(duì)任意的1≤k≤m有

因此

應(yīng)用上述參數(shù)β于定理4中可得定理5. 】

定理5刻畫(huà)了點(diǎn)對(duì)假設(shè)穩(wěn)定性下置信度算法的泛化界.結(jié)果表明置信度算法的泛化界由數(shù)據(jù)的粒度及樣本數(shù)決定，大樣本機(jī)制下?；酱?，置信度算法的經(jīng)驗(yàn)誤差越接近其泛化誤差.

3 結(jié)束語(yǔ)

粗糙集預(yù)測(cè)是粗糙集理論中不確定性學(xué)習(xí)的關(guān)鍵問(wèn)題，其下近似誘導(dǎo)確定性規(guī)則而上近似誘導(dǎo)不確定規(guī)則.通常確定性規(guī)則的前件具有唯一的結(jié)論，而不確定性規(guī)則的結(jié)論不唯一，這也是粗糙集理論與其他學(xué)習(xí)理論的不同之處，即粗糙集理論可以處理這種不確定和不一致決策信息系統(tǒng).文中采用置信度算法度量這種不確定規(guī)則，并且利用穩(wěn)定性理論刻畫(huà)了置信度算法的泛化能力.結(jié)果表明置信度算法的泛化能力與決策信息系統(tǒng)的樣本數(shù)目及穩(wěn)定性參數(shù)有關(guān)，樣本越多，穩(wěn)定性參數(shù)越小，則泛化能力越強(qiáng).

下一步將討論基于其他類(lèi)型粗糙集的預(yù)測(cè)算法的泛化能力.

:

[1] PAWLAK Z.Rough sets[J].InternationalJournalofComputerandInformationSciences,1982,11(5):341.

[2] ZHANG J B,WONG J S,PAN Y.et al.A comparison of parallel large-scale knowledge acquisition using rough set theory on different map reduce runtime systems[J].InternationalJournalofApproximateReasoning,2014,55(3):896.

[3] CHEN H,LI T,LUO C,et al.A decision-theoretic rough set approach for dynamic data mining[J].IEEETransactionsonFuzzySystems,2015,23(6):1958.

[4] HUANG C H.Medical reasoning with rough-set influence diagrams[J].JournalofComputationalBiologyAJournalofComputationalMolecularCellBiology,2015,22(8):752.

[5] HUANG M J,ZHANG Y B,LUO J H,et al.Evaluation of economics journals based on reduction algorithm of rough set and grey correlation[J].JournalofManagement&Sustainability,2015,5(1):140.

[6] BAI C,SARKIS J.Green supplier development:analytical evaluation using rough set theory[J].JournalofCleanerProduction,2010,18(12):1200.

[7] TAN Z,LIWEI J U,CHEN Z,et al.An environmental economic dispatch optimization model based on rough set theory and chaotic local search strategy differential evolution algorithm[J].PowerSystemTechnology,2014,38(5):1339.

[8] DAI J H,TIAN H W,WANG W T,et al.Decision rule mining using classification consistency rate[J].Knowledge-BasedSystems,2013,43:95.

[9] SKOWRON A.Extracting laws from decision tables:a rough set approach[J].ComputationalIntelligence,1995,11(2):371.

[10] YASDI R..Learning classification rules from database in the context of knowledge acquisition and representation[J].IEEETransactionsonKnowledgeandDataEngineering,1991,3(3):292.

[11] ALON N,BEN D S,CESA B N,et al.Scale-sensitive dimensions,uniform convergence,and learnability[J].JournaloftheACM,1997,44(4):615.

[12] BONNANS J F,SHAPIRO A.Optimization problems with perturbation,a guided tour[J].SIAMReview,1998,40(2):228.

[13] BOUSQUET O,ELISSEEFF A.Stability and generalization[J].JournalofMachineLearningResearch,2002,2:499.

[14] WU J,YU X,ZHU L,et al.Leave-two-out stability of ontology learning algorithm[J].ChaosSolitons&Fractals,2016,89:322.

[15] DEVROYE L,WAGNER T.Distribution-free performance bounds for potential function rules[J].IEEETransactionsonInformationTheory,1979,25(5):601.

[16] VAPNIK V N.EstimationofDependencesBasedonEmpiricalData[M].New York:Springer,1982:186.

[17] RRDIN C,LETHAM B,MADIGAN D.A learning theory framework for sequential event prediction and association rules[J].JournalofMachineLearningResearch,2013,14:3441.

[18] KRYSZKIEWICZ M.Comparative study of alternative types of knowledge reduction in inconsistent systems[J].InternationalJournalofIntelligentSystems,2001,16(1):105.

[19] KRYSZKIEWICZ M.Rules in incomplete information systems[J].InformationSciences,1999,113:271.

[20] STEELE J M.An Efron-Stein inequality for nonsymmetric statistics[J].AnnalsofStatistics,1986,14(2):753.

[21] MCDIARMID C.OntheMethodofBoundedDifferences[M].Surveys in Combinatorics.Cambridge:Cambridge University Press,1989:148.

[22] GRZEGORZ A R.Asymptotic factorial powers expansions for binomial and negative binomial reciprocals[J].ProceedingsoftheAmericanMathematicalSociety,2004,132(1):261.