采用局部粗糙集模型的決策規(guī)則提取

張曉萍，李偉康, 李進金,2

(1. 華僑大學 數(shù)學科學學院，福建 泉州 362021; 2. 閩南師范大學 數(shù)學與統(tǒng)計學院，福建 漳州 363000)

經(jīng)典粗糙集理論由波蘭學者Pawlak[1]首次提出,該理論可處理不確定、不精確、不一致的不完全數(shù)據(jù)信息.雖然經(jīng)典粗糙集理論不需要數(shù)據(jù)的先驗信息，但仍具有一定的局限性[2-3]:需建立在等價關系基礎上、在大數(shù)據(jù)背景下計算效率低、屬性約簡的過擬合.

為滿足數(shù)據(jù)處理的要求,許多學者對經(jīng)典粗糙集理論進行一系列推廣,如一般關系下的粗糙集、變精度粗糙集[4-5]、局部粗糙集[3]、決策理論粗糙集[6]等,變精度粗糙集是在經(jīng)典粗糙集的基礎上,引入?yún)?shù)β(0≤β<0.5),即允許一定的錯誤分類率發(fā)生[7-8].當β=0時,經(jīng)典粗糙集就是變精度粗糙集的特例.局部粗糙集理論可以更好地應用于大數(shù)據(jù)處理,在計算上、下近似時,無需考慮論域中的所有對象,只需考慮樣本中的對象,提高了數(shù)據(jù)處理的效率.文獻[6]引入決策風險,作出的決策規(guī)則需使決策風險最小.目前，粗糙集理論及其推廣已廣泛地應用于模式識別[9-10]、知識發(fā)現(xiàn)[9,11-12]、規(guī)則提取[9,13]和決策管理等領域.

概念逼近與屬性約簡是研究粗糙集的兩個關鍵因素[3],對給出的新樣本做有效的概念逼近可以更加客觀地觀察新樣本,通過屬性約簡、對象與屬性值之間的關系，可以對決策信息系統(tǒng)進行有效的決策規(guī)則提取.決策規(guī)則提取往往出現(xiàn)在決策信息系統(tǒng)數(shù)據(jù)的處理中.利用粗糙集理論進行決策規(guī)則提取時，一般會有兩類決策規(guī)則:確定性和可能性決策規(guī)則[14-16].基于此，文中對基于局部粗糙集模型下的決策規(guī)則提取進行研究.

1 基礎知識

假設U是一非空有限集合,稱為論域,R?U×U是U上一等價關系，則K=(U,R)稱為近似空間.x∈U的等價類記為[x]R,若[x]R=[y]R,則稱對象x與y在等價關系R上是不可區(qū)分的.

定義1[3]給出一個近似空間K=(U,R)及U的任意非空子集X,X的下近似和上近似分別為

2 局部粗糙集

在數(shù)據(jù)處理過程中,為了計算給定的每個樣本X的上、下近似,需要考慮給定數(shù)據(jù)集的所有對象，在大數(shù)據(jù)背景下,要花費較多的時間和精力.因此，為了提高數(shù)據(jù)處理的效率,文獻[3]結(jié)合經(jīng)典粗糙集和決策理論粗糙集提出局部粗糙集.

定義3[3]設(U,R)為一近似空間,R?U×U為U上一二元關系,D是定義2U×2U上的包容度函數(shù),則U上的任一非空子集X的α-下近似和β-上近似分別為

表1 某公司面試人員的基本信息表Tab.1 Basic information table of interviewers of company

由例1可知：在局部粗糙集與經(jīng)典粗糙集中,給出論域的任一子集,調(diào)整參數(shù)值可使子集的上、下近似更加接近該子集,即應用局部粗糙集理論可以對集合做更有效的概念逼近,數(shù)據(jù)處理更加精確.

3 局部粗糙集模型中的決策規(guī)則提取

3.1 規(guī)則提取[14]

用∧與∨分別表示邏輯連接詞“和”與“或”.在決策信息系統(tǒng)S=(U,C∪j5i0abt0b)中，C為條件屬性，d為決策屬性.任何屬性值對(a,v)稱為A原子，a∈A?C,v∈Va,Va為對象在屬性a下的取值．任何A原子或者不同的A原子的∧稱為A描述．若t是A描述，則出現(xiàn)在t中的屬性記為A(t)，A(t)={a|(a,v)∈t}，具有描述t的對象集稱為t的支持，用‖t‖表示，‖t‖={x∈U|a(x)=v,?(a,v)∈t}，則易得‖t∩s‖=‖t‖∩‖s‖,‖t∪s‖=‖t‖∪‖s‖.

對于A?C，記DES(A)={t|t是一個A描述且‖t‖≠?}，若對任何的t∈DES(A)，有A(t)=A，則稱t是一個滿的A描述，記FDES(A)={t|t∈DES(A)且A(t)=A}.

例2繼例1，取A={學位,性別},t1=(學位,本科)，則‖t‖={x1,x5,x6}，此時，A(t)={學位},A(t)≠A，故t1不是滿的A描述；取t2=(學位,本科)∧(性別,男)，則‖t2‖={x1,x6}，此時，A(t2)={學位,性別},A(t2)=A，則t2是一個滿的A描述．

以下討論都建立在t是一個滿的A描述的基礎上，即t∈FDES(A)．

3.2 局部粗糙集的決策規(guī)則提取

在每個決策信息系統(tǒng)S=(U,C∪j5i0abt0b)中都可以產(chǎn)生決策規(guī)則,合理的決策規(guī)則對新樣本的決策具有重要的參考作用,這不僅要求數(shù)據(jù)具有真實性和有效性,也要求在分析數(shù)據(jù)時提取合理的決策規(guī)則.

定理1對于決策信息系統(tǒng)S=(U,C∪j5i0abt0b),s=(d,w)，w∈Vd，t∈FDES(C)，且0≤β<α≤1，則

1)D(‖s‖|‖t‖)≥α，當且僅當|{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}|≥α|‖t‖|;

2)D(‖s‖|‖t‖)>β，當且僅當|{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}|>β|‖t‖|.

|{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}|≥α|‖t‖|.

“?”充分性.w∈?(t)={d(x)|x∈‖t‖},則‖t‖∩‖s‖≠?,即D(‖s‖|‖t‖)>0.又因為

|{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}|≥α|‖t‖|，

2) 當0<β時,證明同1).

當β=0時,D(‖s‖|‖t‖)>0，當且僅當|{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}|>0.

“?”必要性.當D(‖s‖|‖t‖)>0時,‖t‖∩‖s‖≠?,存在x∈‖t‖∩‖s‖,使d(x)=w,故w∈?(t)={d(x)|x∈‖t‖}.同時，有{x∈U|d(x)=w∈?(t),?a∈C,(a,a(x))∈t}≠?.

“?”充分性顯然可見.

證畢.

定理2決策信息系統(tǒng)S=(U,C∪j5i0abt0b)中,s=(d,w)，w∈Vd，t∈FDES(C)，且0≤β<α≤1，則

證明：由定理1即可證明.

對于X?U,A?C,基于局部粗糙集模型，推廣可得

表2 某同學瀏覽的房子的基本信息表Tab.2 Basic information table of house browsed by student

例3某同學去旅游前打算預定房子,他查看了10間房子,依次標記為x1～x10,并且將價格、環(huán)境、結(jié)構(gòu)作為評價指標,即屬性集C={價格,環(huán)境,結(jié)構(gòu)}.該同學將此次瀏覽的信息制成表格,并給出“是否預定”的初步?jīng)Q策,如表2所示.

取α=0.6,s=(是否預定,是),則‖s‖={x2,x4,x6,x7,x9},能夠做α-確定的決策情況如下.

1) 考慮A=C={價格,環(huán)境,結(jié)構(gòu)}，有t=(價格,低)∧(環(huán)境,優(yōu))∧(結(jié)構(gòu),良)，決策t→s的確定性因子Cer(t→s)=1；t=(價格,過高)∧(環(huán)境,優(yōu))∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,高)∧(環(huán)境,良)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,低)∧(環(huán)境,良)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,低)∧(環(huán)境,良)∧(結(jié)構(gòu),良)，決策t→s的確定性因子Cer(t→s)=1.

2) 考慮A?C={價格,環(huán)境}或者{環(huán)境,結(jié)構(gòu)}或者{價格,結(jié)構(gòu)}，那么，有t=(價格,低)∧(環(huán)境,優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,過高)∧(環(huán)境,優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,低)∧(環(huán)境,良)，決策t→s的確定性因子Cer(t→s)=1；t=(環(huán)境,良)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=0.67；t=(價格,過高)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,低)∧(結(jié)構(gòu),良)，決策t→s的確定性因子Cer(t→s)=1；t=(價格,高)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1；t=(價格,低)∧(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=1.

3) 考慮A?C={價格}或者{環(huán)境}或者{結(jié)構(gòu)}，那么，有t=(價格,低)，決策t→s的確定性因子Cer(t→s)=1；t=(價格,過高)，決策t→s的確定性因子Cer(t→s)=1；t=(結(jié)構(gòu),優(yōu))，決策t→s的確定性因子Cer(t→s)=0.6.

4 結(jié)束語

在經(jīng)典粗糙集模型的決策規(guī)則提取中,確定因子Cer(t→s)=1的規(guī)則稱為確定性規(guī)則,結(jié)合局部粗糙集模型給出的規(guī)則提取公式，引入?yún)?shù)值α,α∈(0,1],使規(guī)則提取公式的泛化能力更強,適用性更廣.當α=1時，即普通的決策規(guī)則提取情況.在今后的工作中,將進一步比較局部粗糙集模型與其他粗糙集模型的決策規(guī)則,以及多個粗糙集模型的結(jié)合決策規(guī)則提取.