粗糙集的Mallow’s Cp選擇算法*

楊貴軍，于 洋

天津財經(jīng)大學(xué) 統(tǒng)計學(xué)院，天津 300222

1 引言

由Pawlak提出的粗糙集是一種有效的機(jī)器學(xué)習(xí)特征提取方法[1]，能從數(shù)據(jù)中歸納出易于理解的分類規(guī)則以揭示數(shù)據(jù)背后蘊(yùn)藏的信息特征，不受限于數(shù)據(jù)分布，在經(jīng)濟(jì)[2-4]、文本挖掘[5-6]等多個領(lǐng)域有廣泛應(yīng)用。不同粗糙集構(gòu)造方法得到的粗糙規(guī)則一般不同，在實際應(yīng)用中，為了較好反映數(shù)據(jù)的真實關(guān)系，選擇優(yōu)良粗糙集至關(guān)重要。

通常，擇優(yōu)粗糙集的標(biāo)準(zhǔn)是其在新樣本上的泛化誤差。泛化誤差小的粗糙集為優(yōu)良粗糙集，在新樣本上具有強(qiáng)泛化能力。然而新樣本事先并不可知，無法計算泛化誤差，許多文獻(xiàn)以測試集上的誤判率或正確率作為泛化能力替代來評估粗糙集[7]。如Jaworski基于粗糙集分類規(guī)則的正確率與覆蓋率構(gòu)建了粗糙集的新評估指標(biāo)[8]。Cornelis等比較了多種基于模糊容差關(guān)系的粗糙集屬性約簡方法，并給出了具有高正確率的實證結(jié)果[9]。張維等組合集成學(xué)習(xí)與半監(jiān)督學(xué)習(xí)給出了新粗糙集屬性約簡方法，用正確率評估了新方法的效果[10]。劉偲等結(jié)合測試代價提出測試代價敏感的決策粗糙集正域約簡算法，并以分類正確率評估新算法的分類效果[11]。徐健鋒等提出基于混淆矩陣的多目標(biāo)優(yōu)化三支決策模型，新方法的準(zhǔn)確率更高[12]。

綜上所述，目前研究者大多以誤判率為粗糙集擇優(yōu)標(biāo)準(zhǔn)。然而，誤判率雖然計算簡單直觀，但其僅關(guān)注粗糙集在測試集中的分類準(zhǔn)確性，未考慮粗糙集的復(fù)雜度[13-14]。且誤判率并非總能真實反映出粗糙集的泛化能力，粗糙集在測試集中誤判率最低，在新樣本上的泛化能力并不總是最強(qiáng)。如本文第4章顯示，對于Breastcancer數(shù)據(jù)集，分別采用基于最大概率的粗糙集方法和基于貝葉斯的粗糙集方法構(gòu)造500對粗糙集，其中在測試集中最低誤判率的500個粗糙集，只有362個粗糙集在新樣本上泛化能力最強(qiáng)。特別是當(dāng)測試集中多個粗糙集之間的誤判率相差小時，采用誤判率標(biāo)準(zhǔn)不易選出在新樣本上泛化能力最強(qiáng)的粗糙集。

Mallow’s Cp準(zhǔn)則最早用于模型中的變量選擇。研究者如Hansen、張新雨等進(jìn)一步將其思想推廣應(yīng)用到模型選擇與模型平均等問題[15-16]。Mallow’s Cp準(zhǔn)則兼顧了模型的數(shù)據(jù)擬合度與模型復(fù)雜程度，能有效減小過擬合風(fēng)險。針對決策屬性為兩分類的數(shù)據(jù)集，本文引入粗糙集的Mallow’s Cp選擇算法。利用Logistic模型表示非線性粗糙集分類規(guī)則，Logistic模型的Cp值即為對應(yīng)粗糙集的Cp值，以Cp值為粗糙集的擇優(yōu)標(biāo)準(zhǔn)。Mallow’s Cp準(zhǔn)則在多個粗糙集的擇優(yōu)時兼顧粗糙規(guī)則的分類準(zhǔn)確性與復(fù)雜度，常選擇出強(qiáng)泛化能力的粗糙集。實驗結(jié)果顯示，當(dāng)多個粗糙集在測試集中誤判率差異小時，新算法常常選出強(qiáng)泛化能力的粗糙集。

2 預(yù)備知識

2.1 Pawlak粗糙集

定義1[17（]信息系統(tǒng)）假設(shè)S=(U,A,V,f)為一個信息系統(tǒng)，其中U={u1,u2,…,un}為樣本的非空有限集合，即論域；X={x1,x2,…,xk}為k維條件屬性，Y 為決策屬性，A=X?Y為屬性全體(X?Y=?)；屬性值的集合記為；f:U×A→V是信息函數(shù)，為每個樣本的每個屬性賦予一個信息值，即：?a∈A,u∈U,f(u,a)∈Va。

定義2[18（]粗糙集）定義R為U上的等價關(guān)系，以U R={[u]R|u∈U}表示R的所有等價類構(gòu)成的集合，其中[u]R表示樣本u關(guān)于R的等價類，則?B?U,B的上下近似集定義為：

2.2 粗糙集構(gòu)造方法

采用不同粗糙集構(gòu)造方法，得到不同的粗糙集，分析結(jié)果往往有差異。擇優(yōu)準(zhǔn)則是為了選擇出在新樣本上強(qiáng)泛化能力的粗糙集。目前，粗糙集構(gòu)造方法主要有基于最大概率的粗糙集方法和基于貝葉斯的粗糙集方法[19]。本文研究二分類問題，決策屬性Y取值為0或1。為簡化敘述，記一類取值為c，則另一類取值為1-c(c=0,1。)

方法1[19（]基于最大概率的粗糙集方法）該方法通過比較第i(i=1,2,…,n)個樣本ui的條件屬性Xi={xi1,xi2,…,xik}在第c類和第1-c類上的概率大小來判斷分類，第c(c=0,1)類上的概率公式為：

方法2[19（]基于貝葉斯的粗糙集方法）該方法通過比較本屬于1-c(或c)類的第i(i=1,2,…,n)個樣本ui的條件屬性 Xi={xi1,xi2,…,xik},被判為c(或1-c)類的誤判平均損失大小來判斷分類。將條件屬性為xi1,xi2,…,xik時屬于1-c(c=0,1)類的第 i(i=1,2,…,n)個樣本ui判為c類的誤判損失記為λ(yi=c|xi1,xi2,…,xik)≥0，則將ui誤判為c類的誤判平均損失為：

若αc≤α1-c，則將樣本ui判為第c類，分類規(guī)則為：

兩種方法構(gòu)造的粗糙集分類規(guī)則并不總是一致，兩者的誤判率也往往不一樣。

2.3 基于誤判率的粗糙集擇優(yōu)

記兩種方法得到的粗糙集分別為B1和B2，則對應(yīng)的誤判率為粗糙集Bh分類錯誤的樣本數(shù)占樣本總數(shù)的比例，記為E(Bh;U)(h=1,2)[7]。誤判率準(zhǔn)則選擇的較優(yōu)粗糙集Bh滿足：

誤判率關(guān)注粗糙集的分類準(zhǔn)確性，利用粗糙集分類誤判率反映粗糙集的優(yōu)良性，僅考慮粗糙集的分類結(jié)果，未考慮粗糙集的復(fù)雜程度，容易出現(xiàn)過擬合問題，導(dǎo)致在測試集上誤判率低的粗糙集不一定具有強(qiáng)泛化能力。

3 粗糙集的Mallow’s Cp擇優(yōu)

上述提到誤判率擇優(yōu)粗糙集時可能出現(xiàn)過擬合問題，從而選擇的粗糙集并非總是具有強(qiáng)泛化能力，針對該問題，本文引入同時考慮分類精度與粗糙集復(fù)雜度的Mallow’s Cp準(zhǔn)則，以期減少過擬合情況，擇優(yōu)出強(qiáng)泛化能力的粗糙集。為將Mallow’s Cp準(zhǔn)則用于粗糙集擇優(yōu)，需要利用Logistic模型將非線性的粗糙集分類規(guī)則表達(dá)為線性形式。此時，基于粗糙集分類規(guī)則，Logistic模型與粗糙集一一對應(yīng)。計算Logistic模型的Cp值，最小Cp值的Logistic模型最優(yōu)，其對應(yīng)的粗糙集為所選擇的最優(yōu)粗糙集。其中，Logistic模型的因變量為決策屬性yi，解釋變量由粗糙集的分類規(guī)則定義，為避免共線性問題，僅選取判為c類的分類規(guī)則，記為第一類。

定義3（解釋變量）設(shè)由數(shù)據(jù)得到的第一類粗糙集分類規(guī)則共有m個，為：則相應(yīng)Logistic模型的解釋變量定義為：

其中，zij為由第j個分類規(guī)則所定義的解釋變量，是判斷第i個觀測是否符合分類規(guī)則rj的條件(x1,x2,…,xk)=(xj1,xj2,…,xjk)的示性函數(shù)，i=1,2,…,n(n為觀測個數(shù))，j=1,2,…,m(m為新變量個數(shù))。

定義 4（Logistic模型） 以Zi=(zi1,zi2,…,zim)為解釋變量，yi為因變量構(gòu)建的Logistic模型定義為：

Logistic模型與粗糙集存在一一對應(yīng)關(guān)系，本文認(rèn)為最優(yōu)Logistic模型對應(yīng)的粗糙集為最優(yōu)粗糙集。

定義5（Cp值）記兩種不同的粗糙集分別為B1和B2，第一類粗糙集分類規(guī)則個數(shù)分別為m1和m2個，對應(yīng)Logistic模型的殘差平方和分別為sse1和sse2，則Cp值定義為：

其中，以兩種粗糙集構(gòu)造方法得到的第一類粗糙集分類規(guī)則組成規(guī)則全集，并剔除重復(fù)規(guī)則，設(shè)共有m1+m2-p個（p為m1和m2個規(guī)則中重復(fù)的規(guī)則個數(shù)），為對應(yīng)Logistic模型的方差σ2的最大似然估計，h=1,2。

這里，Mallow’s Cp準(zhǔn)則將兩種粗糙集構(gòu)造方法得到的第一類粗糙集分類規(guī)則看作是兩個規(guī)則子集，將兩個規(guī)則子集匯總并剔除重復(fù)規(guī)則后的規(guī)則視為規(guī)則全集，選擇的是在同一規(guī)則全集下兼顧精度與復(fù)雜程度的最優(yōu)規(guī)則子集。Cp值分為兩部分，第一部分依據(jù)規(guī)則子集與規(guī)則全集的相對解釋程度考察粗糙集的準(zhǔn)確度，第二部分依據(jù)規(guī)則子集個數(shù)的函數(shù)考察粗糙集的復(fù)雜程度。當(dāng)兩個規(guī)則子集的準(zhǔn)確度相差較大時，第一部分起決定作用。準(zhǔn)確度高的規(guī)則子集對應(yīng)第一部分值較小，對應(yīng)Cp值較小。當(dāng)兩個規(guī)則子集的準(zhǔn)確度相近時第一部分值相差較小，此時選擇結(jié)果主要取決于第二部分。規(guī)則個數(shù)較少的子集復(fù)雜度較低，對應(yīng)第二部分函數(shù)值較大，對應(yīng)Cp值較小。Mallow’s Cp準(zhǔn)則兼顧粗糙集的準(zhǔn)確度與復(fù)雜程度。滿足Cp(Bh;U)=min(Cp(B1;U),Cp(B2;U))的Logistic模型更優(yōu)，滿足Cp(Bh;U)=min(|Cp(B1;U)-(m1+1)|,|Cp(B2;U)-(m2+1)|)的粗糙集Bh也更優(yōu)。選擇模型應(yīng)考慮選擇Cp值最小或是與mh+1最接近的模型[20]。在實際應(yīng)用中，研究者通常以Cp值最小的模型為最優(yōu)模型，如Olejnik等[20]、張新雨等[16]。本文認(rèn)為，最小Cp值對應(yīng)的Logistic模型最優(yōu)，相應(yīng)的粗糙集為所選擇的最優(yōu)粗糙集。Mallow’s Cp準(zhǔn)則計算簡單，在所有可能的規(guī)則子集中進(jìn)行選擇，是最優(yōu)規(guī)則子集的有效選擇方法。下文模擬結(jié)果顯示，粗糙集的Mallow’s Cp選擇算法能夠很好地選擇出較優(yōu)的粗糙集。

算法1粗糙集的Mallow’s Cp選擇算法

步驟1給定待選的兩組粗糙集分類規(guī)則，針對一組分類規(guī)則，從中選取第一類的規(guī)則，定義新變量并賦值，記為類似地，另一組分類規(guī)則定義的新變量記為，其 中 ，i=1,2,…,n，m1、m2為新變量個數(shù)。將兩組分類規(guī)則定義的新變量匯總，去掉重復(fù)的變量，變量全集記為

步驟2將分別作為Logistic模型的解釋變量，決策屬性yi作為Logistic模型的因變量，構(gòu)建Logistic模型，分別記為模型1、2和3。計算模型1和2的殘差平方和sse1、sse2以及模型3中方差的最大似然估計，依據(jù)公式計算模型1和2的Cp值。

步驟3比較所有粗糙集的Cp值，選擇Cp值最小的Logistic模型。該Logistic模型所對應(yīng)的粗糙集為最終選擇的最優(yōu)粗糙集。

在算法1中，步驟1選取第一類規(guī)則的時間復(fù)雜度為O(1)，定義并賦值新變量z1i和z2i的時間復(fù)雜度分別為O(m1×n)和O(m2×n)，匯總得到變量 z3i的時間復(fù)雜度為O(1)；步驟2的時間復(fù)雜度為O(1)；步驟3的時間復(fù)雜度為O(1)。因此算法1的時間復(fù)雜度取決于新變量個數(shù)m1和m2，為O(m1×n)和O(m2×n)中的較大值。

4 實驗及結(jié)果分析

本章選用規(guī)模大小和屬性個數(shù)各異的4個UCI數(shù)據(jù)集進(jìn)行實驗，驗證粗糙集的Mallow’s Cp選擇算法的有效性。實驗環(huán)境為Intel?CoreTMi7-3770 CPU，4 GB內(nèi)存，64位Windows 7操作系統(tǒng)的PC機(jī)，實驗平臺為R。主要考察數(shù)據(jù)集的分類問題，其中將數(shù)據(jù)集Abalone的非兩分類決策屬性，以9為界限合并為兩分類（1表示決策屬性值大于9，0表示決策屬性值不大于9）。對每個數(shù)據(jù)集，從中隨機(jī)抽取80%的數(shù)據(jù)作為訓(xùn)練集與測試集，用于粗糙集的構(gòu)建與選擇；剩余20%記為預(yù)留數(shù)據(jù)集，作為“新樣本”，以粗糙集在預(yù)留數(shù)據(jù)集上的誤判率為其泛化能力的考量指標(biāo)。若所選粗糙集在預(yù)留數(shù)據(jù)集上的誤判率最低，則認(rèn)為擇優(yōu)算法選擇了“正確”的粗糙集，否則，認(rèn)為選擇“錯誤”。共進(jìn)行100次5折交叉驗證，各數(shù)據(jù)集的具體信息見表1。針對4個數(shù)據(jù)集，表1第2列至第4列對應(yīng)給出了訓(xùn)練集、測試集與預(yù)留數(shù)據(jù)集的容量，第5列給出條件屬性的個數(shù)。

Table 1 Basic information of data sets表1 數(shù)據(jù)集的基本信息

對每個數(shù)據(jù)集，分別采用基于最大概率的粗糙集方法和基于貝葉斯的粗糙集方法，會得到兩類不同的粗糙集分類規(guī)則。本研究采用粗糙集的Mallow’s Cp選擇算法可從中選擇出預(yù)測準(zhǔn)確度更高的一類規(guī)則。每次模擬時，對數(shù)據(jù)分別采用兩種方法構(gòu)建粗糙集分類規(guī)則，利用第一類的規(guī)則定義兩組解釋變量，以決策屬性為因變量擬合兩個Logistic模型，以所有變量匯總并剔除重復(fù)后的變量擬合的Logistic模型為全模型，計算相應(yīng)的Cp值。4個數(shù)據(jù)集的實驗分別重復(fù)500次的結(jié)果如表2所示。表2第2至5列給出了分別采用誤判率準(zhǔn)則與Mallow’s Cp準(zhǔn)則選擇粗糙集的正確次數(shù)與錯誤次數(shù)，第6列給出了兩種準(zhǔn)則均選擇正確的次數(shù)，第7列給出了Mallow’s Cp準(zhǔn)則選擇正確粗糙集而誤判率準(zhǔn)則未選擇正確粗糙集的次數(shù)，第8列給出了誤判率準(zhǔn)則選擇正確而Mallow’s Cp準(zhǔn)則選擇錯誤的次數(shù)。由表2可知，在500次重復(fù)過程中兩種準(zhǔn)則同時選擇正確的次數(shù)都很多，除數(shù)據(jù)集Haberman外，正確率均超過72%。此外，對4個數(shù)據(jù)集，Mallow’s Cp準(zhǔn)則選擇正確而誤判率準(zhǔn)則選擇錯誤的情況分別出現(xiàn)了69、113、91和68次，誤判率準(zhǔn)則選擇正確而Mallow’s Cp準(zhǔn)則選擇錯誤的次數(shù)則分別為32、3、57和11次。后者的次數(shù)遠(yuǎn)小于前者，幾乎均不超過Mallow’s Cp準(zhǔn)則更好次數(shù)的一半，且在500次實驗中占比均不超過11%。說明誤判率準(zhǔn)則更好的情況出現(xiàn)概率較少，多數(shù)情況下Mallow’s Cp準(zhǔn)則的擇優(yōu)效果更好。出現(xiàn)誤判率準(zhǔn)則更好情況的主要原因是在兩個粗糙集的分類精度相差較小但復(fù)雜度相差較大的情況下，若此時精度稍高的粗糙集對應(yīng)的復(fù)雜度較高，則Mallow’s Cp準(zhǔn)則傾向于選擇精度稍低且復(fù)雜度低的粗糙集，而誤判率準(zhǔn)則傾向于選擇精度稍高的粗糙集，從而出現(xiàn)誤判率準(zhǔn)則選擇正確而Mallow’s Cp準(zhǔn)則選擇錯誤的情況。綜上所述，Mallow’s Cp準(zhǔn)則適用于粗糙集選擇，相對誤判率準(zhǔn)則擇優(yōu)正確概率更大，擇優(yōu)效果更好。

Table 2 Comparison of 4 data sets(500 times)表2 4個數(shù)據(jù)集的對比情況（500次）

進(jìn)一步考察兩個粗糙集在測試集的誤判率之差小于3%的情況，結(jié)果見表3。由表3可知，對4個數(shù)據(jù)集而言，兩個粗糙集間的Mallow’s Cp準(zhǔn)則相對差異大，容易選擇出正確的粗糙集。而兩個粗糙集在測試集的誤判率之差小的情況較為普遍，分別達(dá)到471、282、160和192次，其中兩種準(zhǔn)則同時選擇正確的次數(shù)分別為304、143、45和108次，Mallow’s Cp準(zhǔn)則選擇正確的次數(shù)分別達(dá)到373、254、83和139次，且出現(xiàn)69、111、38和31次Mallow’s Cp準(zhǔn)則比誤判率準(zhǔn)則好的情況，明顯高于誤判率準(zhǔn)則比Mallow’s Cp準(zhǔn)則好的次數(shù)32、3、22和8次，此時Mallow’s Cp準(zhǔn)則優(yōu)于誤判率準(zhǔn)則，選擇出具有強(qiáng)泛化能力的粗糙集的頻率更高。Mallow’s Cp準(zhǔn)則可以代替誤判率準(zhǔn)則擇優(yōu)粗糙集，是粗糙集擇優(yōu)的較好準(zhǔn)則。

Fig.1 Average precision of two criterions in process of repeating 500 times(Abalone）圖1 重復(fù)500次過程中兩種準(zhǔn)則的平均正確率（Abalone）

Fig.2 Average precision of two criterions in process of repeating 500 times(Breastcancer）圖2 重復(fù)500次過程中兩種準(zhǔn)則的平均正確率（Breastcancer）

Fig.3 Average precision of two criterions in process of repeating 500 times(Haberman）圖3 重復(fù)500次過程中兩種準(zhǔn)則的平均正確率（Haberman）

Table 3 Comparison of 4 data sets(when the difference of misclassification rates in test sets is small)表3 4個數(shù)據(jù)集的對比情況（在測試集的誤判率差異小時）

針對4個數(shù)據(jù)集，從進(jìn)行1次至重復(fù)500次的過程中誤判率準(zhǔn)則和Mallow’s Cp準(zhǔn)則選擇粗糙集的平均正確率的變化過程分別如圖1～圖4所示。每幅圖的橫坐標(biāo)為重復(fù)次數(shù)，縱坐標(biāo)為選擇的平均正確率，虛線代表誤判率準(zhǔn)則的結(jié)果，實線代表Mallow’s Cp準(zhǔn)則的結(jié)果。

Fig.4 Average precision of two criterions in process of repeating 500 times(Ionosphere）圖4 重復(fù)500次過程中兩種準(zhǔn)則的平均正確率（Ionosphere）

圖1～圖4顯示，在不同重復(fù)次數(shù)下，除數(shù)據(jù)集Haberman外，Mallow’s Cp準(zhǔn)則和誤判率準(zhǔn)則選擇粗糙集的平均正確率幾乎都在70%以上。隨著重復(fù)次數(shù)的增多，兩種準(zhǔn)則的平均正確率均趨于穩(wěn)定。對4個數(shù)據(jù)集，誤判率準(zhǔn)則的平均正確率分別穩(wěn)定在74%、73%、56%及77%左右，Mallow’s Cp準(zhǔn)則的平均正確率分別穩(wěn)定在81%、95%、64%及89%左右，均高于誤判率準(zhǔn)則。整個動態(tài)過程中，Mallow’s Cp準(zhǔn)則的平均正確率普遍高于誤判率準(zhǔn)則，采用Mallow’s Cp準(zhǔn)則更可能正確選擇出泛化能力強(qiáng)的粗糙集。

5 結(jié)束語

實際問題中，粗糙集的泛化能力是評估粗糙集的關(guān)鍵，相應(yīng)的粗糙集擇優(yōu)算法至關(guān)重要。本文引入Mallow’s Cp準(zhǔn)則，構(gòu)建粗糙集的Mallow’s Cp選擇算法。新算法兼顧了粗糙集的分類正確概率與模型復(fù)雜度，能選擇出具有強(qiáng)泛化能力的粗糙集，為粗糙集擇優(yōu)提供了新思路。實驗分析結(jié)果顯示，Mallow’s Cp準(zhǔn)則與誤判率準(zhǔn)則選擇強(qiáng)泛化能力的粗糙集的頻率都較高。對誤判率差異小的粗糙集，Mallow’s Cp準(zhǔn)則選出泛化能力強(qiáng)的粗糙集的頻率更高。