鄰域粗糙集模型的規則提取方法研究

姚 晟，徐 風，趙 鵬，汪 杰，陳 菊

1(安徽大學 計算機科學與技術學院，合肥 230601)

2(安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230601)

1 前 言

粗糙集理論[1]是波蘭學者Z.Pawlak 于1982年提出的一種新的處理模糊和不確定性知識的數學模型，其主要方法是通過上近似和下近似去刻畫不確定信息[2,3]，并且通過屬性約簡[4]消除冗余屬性，簡化數據結構，導出問題和分類的規則[5].目前，粗糙集理論已被成功地應用于機器學習[6]、神經網絡[7]、模式識別[8]和數據挖掘[9]等領域.經典粗糙集模型建立在等價關系的基礎上，只能處理符號型屬性，而在現實的很多信息系統中存在大量的數值型屬性，這使得經典粗糙集理論的運用具有一定的局限性.為了能讓經典粗糙集模型能在數值型數據上有著很好的運用，目前常用的方法是將數值型屬性經過離散化處理[10]，使其轉化成符號型屬性，但是這樣處理又會丟失數據中很多信息，因此數據離散化處理并不是一種很好的解決辦法.為了較好地解決此類問題，Lin等[11-13]利用距離去定義對象之間的相似性，提出鄰域關系代替等價關系，將經典粗糙集模型推廣為鄰域粗糙集模型.鄰域粗糙集模型最大的優勢在于可以直接處理數值型屬性的數據，因此比起經典粗糙集模型，鄰域粗糙集模型有著更加廣泛的適用范圍.

包含數值型屬性的信息系統被稱為鄰域信息系統[11].在鄰域信息系統中，由鄰域關系導出的鄰域類中對象間屬性值均不完全相同，這給信息系統的規則提取帶來很大麻煩，因此無法導出一個明確的決策規則.并且對于一個所給的規則前件，如果各屬性值與已知的信息系統的取值匹配不完全一致，則無法判定它的決策值.所以鄰域信息系統中的規則提取是一個很大的難題.

近年來，Zhu等[14]提出在鄰域信息系統中存在著大量的冗余對象，并指出信息系統中少部分對象就可以表達整個全域的信息，因此可以將這些少部分對象作為整個信息系統的決策規則，但是文中并未給出規則提取全面系統化的方法.本文在此基礎上，針對鄰域粗糙集模型中規則提取的問題，定義一種特殊的決策規則形式，給出規則誘導的方法，并且對于待決策的規則前件，給出其決策的判定方法.最后通過UCI數據集實驗驗證了本文所提方法在鄰域粗糙集規則提取方面具有一定的可行性和合理性.

2 基本理論

2.1 經典粗糙集模型

定義1.稱IS=(U，A，V，f)為信息系統，其中U為有限對象集合，A為屬性集，V為屬性的值域，f為屬性到屬性值域上的映射，即f(x，a)=v表示對象x在屬性a下的取值為v，可簡單表示為a(x)=v.

對于?B?A，記

RB={(x，y)ak(x)=ak(y)，?ak∈B}，

(1)

則RB是U上的等價關系，對象x的等價類定義為[x]B={y(x，y)∈RB}.因此由等價關系RB在U上產生的劃分為U/RB={[x]Bx∈U}.

定義2.對于?X?U，設

(2)

(3)

(4)

稱DIS=(U，A=C∪D，V，f)為決策信息系統，其中屬性集A由條件屬性集C和決策屬性集D組成.在決策信息系統中，決策規則是由一系列屬性和屬性值構成的基本單元組成[15]，可表示為∧(a，va)→∨(d，vd)，其中a∈C，d∈D，v∈V.若設φ=∧(a，va)，φ=∨(d，vd)，則決策規則也可簡單表示為：

φ→φ，

其中φ稱為決策規則的前件，φ稱為決策規則的后件，即根據前件所作出的決策.

定義3.對于決策信息系統DIS=(U，A=C∪D，V，f)，設決策屬性劃分為U/RD={D1，D2，…，Dm}，Dec(X)為對象集X的描述，則該決策信息系統導出的決策為Di的確定性規則可表示為[16]：

(5)

從定義3可以看出，決策類的下近似集中對象所描述的決策規則即為該決策的確定性規則.

2.2 鄰域粗糙集模型

定義4.設對象xi∈U且B?C為數值型屬性，則xi在B上的鄰域δB(xi)定義為[11]

δB(xi)={xjxj∈U，ΔB(xi，xj)≤δ}，

(6)

其中Δ為距離函數，δ為鄰域半徑.

從定義4可以看出，對象的鄰域大小由Δ距離函數和鄰域半徑共同決定.目前Δ距離函數廣泛采用的是閔可夫斯基(Minkowski)距離[17]，對象xi，xj間的閔可夫斯基距離定義為

(7)

其中A={a1，a2，…，an}.

此外，閔可夫斯基距離有三種常用的特殊形式，分別為當p取值為1、2和∞時的情形.當p=1時，即

(8)

此距離又稱為絕對值距離；

當p=2時，即

(9)

此距離又稱為歐氏距離；

當p=∞時，即

(10)

此距離又稱為切比雪夫距離.

定義5.設鄰域決策信息系統為NDIS=(U，A=C∪D，f)，C，D分別為條件屬性和決策屬性，對于?X?U在鄰域關系B?C的下近似集和上近似集以及邊界域分別定義為[11]

(11)

(12)

(13)

從定義5可以看出，當鄰域半徑選取為0時，鄰域粗糙集模型就轉化為經典粗糙集模型.

3 鄰域粗糙集模型規則提取與判別

3.1 鄰域粗糙集模型的規則提取

由于鄰域粗糙集模型中屬性的類型為數值型，無法運用屬性與屬性值的形式去描述決策規則，因此本文定義了一種新的決策規則形式來描述鄰域決策系統中的規則.

定義6.對于鄰域決策信息系統NDIS=(U，A=C∪D，V，f)，C為條件屬性集且均為數值型屬性，D為決策屬性集.定義鄰域決策信息系統中導出決策規則形式為：

Φ→d.

(14)

其中，Φ?U為對象子集，稱為決策規則的前件，d為決策值，稱為決策規則的后件.

定義6中定義的決策規則是通過一個對象集的整體作出相應決策的形式來描述，這種表達方式相對于經典粗糙集模型中的形式顯得較為復雜，但是由于數值型屬性的取值為數值，存在大量相近的數據，采用傳統方法導出規則將會產生大量冗余，因此這樣定義的形式相比較具有一定的合理性.

對于決策信息系統中確定性規則的提取，經典粗糙集理論通過對決策類求取下近似的方法來得到[3]，即通過下近似對象集描述的決策規則為確定性規則.同樣地，本文也運用類似方法來導出鄰域決策信息系統的確定性決策規則.

定義7.在鄰域決策信息系統NDIS=(U，A=C∪D，V，f)中，決策屬性值域VD={d1，d2，…，dm}，其對應決策類為D1，D2，…，Dm，則信息系統中蘊含的確定性決策規則為：

(15)

如果我們將決策規則前件中集合的基數大小稱為決策規則的規模，從定義7中可以看出，決策規則前件是由決策類基于條件屬性的下近似集構成的，那么下近似集的大小將直接決定決策規則的規模.而在鄰域粗糙集模型中，選取相同的距離函數，鄰域半徑的大小將直接影響到下近似集的大小，結合定義4和定義5可以得到，隨著鄰域半徑的增大，近似對象的下近似集將隨之減小[18].因此在導出決策規則中，選取過于小的鄰域半徑使得下近似集過大，則這樣得到的決策規則的規模就很大，而鄰域半徑選取過大雖然能使決策規則的規模變小，但是過小導出的決策規則在決策的精確度方面就可能會很低，因此我們需要選取一個合適的鄰域半徑，使得決策規則的規模較小且決策的精確度較高.我們稱這個鄰域半徑為最優鄰域半徑，選取最優鄰域半徑導出的決策規則稱為最優的決策規則.

3.2 鄰域粗糙集模型的決策判定

由于本文定義的決策規則前件是由對象集表示的，并沒有給出對應屬性具體的取值，因此對于一個待決策的規則前件，一般情況下很難直接判斷出它的決策.為了解決此類問題，本文這里給出一個通過距離判別的方法來對規則決策進行判定.

Δ(X，G)=(X-μ)Ω(X-μ)T.

(16)

馬哈拉諾比斯距離簡稱馬氏距離，是描述一個n維向量與一組m個n維向量距離遠近的公式，因此我們可以將這個公式引入到鄰域粗糙集模型中，將鄰域信息系統中每個對象在條件屬性下取值的序列看成一個向量，然后根據馬氏距離可以得到一個對象與一個對象集之間的距離.

(17)

從定義9可以看出，對于一個待決策的規則前件，其決策值取決于所給前件與已知規則前件距離的遠近，最終的決策選取為規則前件最近的決策值.在經典粗糙集模型誘導的決策中，當決策規則前件相同時，對應的決策值是相同的[15-16]，這就相當于本文這里距離為0時的情形，因而本文所提出的決策判別方法為傳統方法的推廣.

4 實驗分析

為了驗證本文所提出的方法具有一定可行性和合理性，本實驗從UCI 機器學習數據庫獲取了7個數據集進行實驗分析和評估.經過整理后數據集描述如表1所述：

表1 UCI數據集Table 1 UCI data sets

本文實驗環節主要分為兩部分，第一部分為驗證性實驗，即對表1中的每個數據集隨機選取三分之二作為訓練集進行規則提取，然后再將剩余的三分之一作為測試集對這些規則進行測試，通過測試集決策的精確度來驗證本文提出方法的可行性.第二部分實驗主要探究隨著鄰域半徑變化，決策規則的精確度和決策規則的規模的變化，并給出最優鄰域半徑的選取問題.

為了消除數據集屬性量綱的影響，在進行實驗前所有數據集都經過了標準化處理，本實驗選用是極差標準化變換[17]，并且距離函數選取為歐氏距離.根據定義4可以看出，鄰域半徑的選取和數據集屬性的個數有著很直接的關系，這對最優鄰域半徑的統一帶來了不便，為了解決這一問題，本實驗采用文獻[14，18]中關于鄰域半徑的表示，即：

δ=min(Δ)+w·[max(Δ)-min(Δ)]

(18)

其中min(Δ)，max(Δ)分別表示數據集中所有對象之間距離的最小值和最大值，w為比例系數，滿足0≤w≤1.當w=0時，δ=min(Δ)，當w=1時，δ=max(Δ)，這樣就可以通過w的選取來決定鄰域半徑的大小.

圖1展示的是各個數據集在第一部分實驗的結果.在不同w取值下，通過訓練集誘導出決策規則，然后對測試集中每個對象進行決策判別，并與真實決策進行比對，我們將測試集中決策正確的對象數目與總測試數目的比值作為對應w值下決策規則的精確度，為了避免偶然性，我們將實驗反復進行7次.圖中每條曲線代表每次的實驗結果.

觀察圖1可以發現，測試集決策規則的精確度在w值的[0，0.2]區間上能夠達到較高的水平，由于決策規則的精確度反映了決策規則整體對決策判別的正確率，所以運用本文方法導出的決策規則來進行決策判別，其決策結果具有較高的精確度，說明在鄰域決策信息系統的規則提取中，這種決策規則形式是可行的.由于鄰域決策信息系統中的屬性值是連續的，傳統的方法很難進行規則提取，因而本文的這種形式的規則不失為一種有效的方法.

由于實驗的第一部分驗證了方法的可行性，那么實驗的第二部分將對每個數據集進行規則提取，并計算其精確度和決策規則的規模，具體結果如圖2所示.這里的精確度為訓練集和測試集均為整個數據集的計算結果，數據集決策規則規模為每個規則的規模之和.

觀察圖2可以發現，隨著w值的逐漸增大，即鄰域半徑的逐漸增大，其鄰域決策信息系統的決策規則精確度一開始穩定在較高的值，然后逐漸減小至0，說明對于w值選取不宜過大，通過這7個數據集的實驗結果可以發現，w取值在[0，0.2]區間內決策規則精確度幾乎達到最高，因此在本文提出的規則提取方法中，對于鄰域半徑的選取，其w值應取[0，0.2]為宜.同時，對于圖2中展示的實驗結果，隨著w值的逐漸增大，決策規則的規模是逐漸減小的，規模的減小意味著決策規則前件所包含的對象越少.由于在定義8所示的規則判定中，需要進行矩陣運算，因而更小規模的規則具有更高的判別效率.因此綜合規則精確度和規則的規模，我們需要選取一個精確度又高且規模又小的w值，這個w值正是我們要找的最優鄰域半徑對應w值，可以看出，本實驗得出的最優鄰域半徑對應的w值為0.2.

圖1 各數據集第一部分實驗結果Fig.1 Experimental results of the first part of each data set

圖2 各數據集第二部分實驗結果Fig.2 Experimental results of the second part of each data set

表2 wdbc數據集部分結果Table 2 Partial results on wdbc data sets

但是，在實際的需求中，有時往往可能需要盡可能縮小決策規則的規模，以達到進一步簡化決策規則的效果.或者是追求高精確度的情形，這時我們可以根據要求靈活的選取w值的大小.表2和表3所示的是數據集wdbc和magic在不同的w值下決策規則規模和規則精確度結果.表中的規模值為數據集每個決策規則的規模值之和.

從表2-3可以看出，對于盡量縮小規模，數據集wdbc的w值可以選擇0.25，數據集magic可以選擇0.2，這樣使得決策精確度不會太低且大幅度減少了規則前件中對象的數量，從而提高了決策判別效率.

通過本實驗，證明了本文所提出的決策規則形式具有一定的可行性和合理性，應用于鄰域決策信息系統的決策提取是合適的.并且通過實驗給出了規則提取中鄰域半徑的選取范圍以及最優鄰域半徑的取值，這個取值具有一定的通用性，可以為實際應用提供參考.

表3 magic數據集部分結果Table 3 Partial results on magic data sets

5 結 語

本文針對目前鄰域粗糙集模型中關于規則提取的問題，提出一種特殊形式的決策規則，該決策規則利用對象集作為規則的前件，并給出規則的誘導方法，并且對于待決策的規則前件，通過對已知規則的前件進行距離判別，然后得到對應的決策.UCI數據集的實驗結果表明，導出的決策規則對于決策的判別具有較高的準確性，并且決策規則的規模程度也比較小.因此可以看出，本文提出的決策規則提取方法具有一定的可行性和合理性.在接下來的工作中需要進一步探究混合數據類型信息系統的決策規則誘導方法.

：

[1] Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11(5)： 341-356.

[2] Jia Xiu-yin，Shang Lin，Zhou Bing，et al.Generalized attribute reduct in rough set theory[J].Knowledge-Based Systems，2016，91：204-218.

[3] Zhang Wen-xiu，Wu Wei-zhi，Liang Ji-ye，et al.Rough set theory and method[M].Beijing：Science Press，2001.

[4] Teng Shu-hua，Lu Min，Yang A-feng.Efficient attribute reduction from the viewpoint of discernibility[J].Information Sciences，2016，326(C)：297-314.

[5] Huo Lei，Wang Zhi-liang，Automation S O.Rough set based rules extraction method for smart home[J].Modern Electronics Technique，2016.

[6] Shen Kao-yi，Tzeng G H.Contextual improvement planning by fuzzy-rough machine learning： a novel bipolar approach for business analytics[J].International Journal of Fuzzy Systems，2016,18(6):1-16.

[7] Salama M A，Hassanien A E，Mostafa A.The prediction of virus mutation using neural networks and rough set techniques[J].Eurasip Journal on Bioinformatics & Systems Biology，2016，2016(1)：1-11.

[8] Shao Y E，Chiu C C.Applying emerging soft computing approaches to control chart pattern recognition for an SPC-EPC process[J].Neuro Computing，2016，201(92)：19-28.

[9] Chen Li-fen，Tsai C T.Data mining framework based on rough set theory to improve location selection decisions： A case study of a restaurant chain[J].Tourism Management，2016，53：197-206.

[10] Bermanis A，Salhov M，Wolf G.Measure-based diffusion grid construction and high-dimensional data discretization[J].Applied & Computational Harmonic Analysis，2015，40(2)：207-228.

[11] Lin T Y，Neighborhood systems and approximation in database and knowledge base systems[C].Proceedings of the Fourth International Symposium on Methodologies of Intelligent Systems，Poster Session，1989：75-86.

[12] Lin T Y.Granular and nearest neighborhoods： rough set approach[J].Studies in Fuzziness & Soft Computing,2001,70(15)：125-142.

[13] Lin T Y.Granular computing on binary relations I：data mining and neighourhood systems[C].Rough Sets in Knowledge Discovery，1998：107-121.

[14] Zhu Peng-fei，Hu Qing-hua.Rule extraction from support vector machines based on consistent region covering reduction[J].Knowledge-Based Systems，2013，42(2)：1-8.

[15] Wang Yong-sheng，Zheng Xue-feng，Suo Yan-feng.A dynamic rule extraction based on information granularity model for complete data[C].IEEE International Conference on Granular Computing，IEEE,2014：329-333.

[16] She Yan-hong，Li Jin-hai，Yang Hai-long.A local approach to rule induction in multi-scale decision tables[J].Knowledge-Based Systems，2015，89(C)：398-410.

[17] Gao Hui-xuan.Applied multivariate statistical analysis[M].Beijing：Beijing University Press，2005：218-228.

[18] Hu Qing-hua，Yu Da-ren，Xie Zong-xia.Neighborhood classifiers[J].Expert Systems with Applications An International Journal，2008，34(2)：866-876.

[19] Brereton R G ，Lloyd G R.Re-evaluating the role of the Mahalanobis distance measure[J].Journal of Chemometrics，2016，30(4)：134-143.

附中文參考文獻：

[3] 張文修，吳偉志，梁吉業，等.粗糙集理論與方法[M].北京：科學出版社，2001.

[17] 高惠璇.應用多元統計分析[M].北京：北京大學出版社，2005.