屬性依賴度的縱橫快速計算方法

呂 豐

(廣西大學 計算機與電子信息學院,南寧 530004)

0 引言

在處理高維數(shù)據(jù)時,特征選擇是一種十分重要的降維方法,它從原始特征空間中通過使用某種評價準則去選擇特征子集,屬于常見的數(shù)據(jù)預處理方式.特征選擇目前有很多種算法,包括最優(yōu)化算法、隨機搜索算法、啟發(fā)式算法等[1-4].而在決策信息系統(tǒng)中,根據(jù)特征或特征子集的依賴度來定義特征的重要度,從而根據(jù)特征重要度來選擇特征[5]158,是一種重要的啟發(fā)式算法.粗糙集理論是近幾十年來發(fā)展迅速的數(shù)據(jù)挖掘方法,已經大量地在各個領域中發(fā)揮巨大作用,研究者眾[6-9].而屬性約簡是粗糙集理論核心內容之一,為了獲得知識的屬性約簡,亦經常根據(jù)屬性重要性來設計啟發(fā)式約簡算法.屬性重要度與特征重要性,常常使用依賴度來定義,依賴度的計算速度,決定了特征選擇或屬性約簡的速度,所以,在海量數(shù)據(jù)集中如何快速計算特征(屬性)或特征集的依賴度,對于降低運算時間,提高運算效率具有十分重要的理論研究意義與應用價值.目前關于依賴度的計算,不少學者作了一些研究[10-12],提出了許多算法,大多算法的時間復雜度為O(|U|2×|C|2).而章夏杰等則提出了一種快速依賴度計算方法FDC[13]518,為依賴度的計算提供了一種新的思路,然而該算法仍存在不少重復無效的過程.本研究則提出一種改進算法,可以大大降低重復過程,減少運行時間,實例表明算法是可行有效的.

1 基礎知識

定義1.1[14]1(決策信息系統(tǒng),等價關系和等價類) 稱四元組DIS=(U,C∪D,V,f)為決策信息系統(tǒng),其中U={x1,x2,…，xn}為非空有限論域,C與D均為非空有限屬性集合.C為條件屬性集,D為決策屬性集,常見情形是只有一個決策屬性,C∩D=φ.V為屬性值的集合,Vij=vij表示第i個對象在第j個屬性下的取值.f:U×(C∪D)→V為信息函數(shù),表示xi∈U,aj∈C∪D,f(xi,aj)=vij∈V.那么在條件屬性子集B?C下的不可區(qū)分關系(等價關系)RB及所生成的等價類[x]RB分別為

RB={(x,y)∈U×U|?b∈B,f(x,b)=f(y,b)},

(1)

[x]RB={y∈U|(x,y)∈RB}.

(2)

(3)

(4)

定義1.3[14]14(相對正域) 給定決策信息系統(tǒng)DIS=(U,C∪D,V,f),屬性子集B?C,決策屬性D在U上的決策類為U/D={D1,D2,…,Dr},則D的B正域定義為

(5)

定義1.4[14]17(依賴度) 給定決策信息系統(tǒng)DIS=(U,C∪D,V,f),決策屬性D對條件屬性集C的依賴度定義為

(6)

其含義是D的相對于C的正域對象數(shù)占全體對象集中的百分比,0≤γC(D)≤1.當γC(D)=1時代表D完全依賴于C,可以由C的知識決定D的知識(由C的分類可以確定D的分類);當γC(D)=0時代表D完全與C無關;當0<γC(D)<1時代表D部分依賴于C.特別,決策屬性D相對于單個條件屬性α的依賴度為

(7)

2 依賴度計算

基于粗糙集屬性重要度的特征選擇因其方法直觀、有效而受到學者們重視,有許多學者采用了決策類對條件屬性子集(特征子集)的相對依賴度來進行屬性選擇,屬性(特征)重要度被定義為相對依賴度之差.此時,如何快速有效地計算依賴度就是一個十分重要而基礎的工作.

通常計算依賴度的算法如下.

計算時間主要消耗在Step 1到Step 4,既要計算條件類與決策類,還要計算每個決策類的條件屬性下近似,通常的算法時間復雜度為O(|U|2×|C|2).為了降低時間復雜度,提高運行速度,不少學者嘗試改進算法.新的一個算法是章夏杰等[13]518提出的FDC算法.

輸入:決策信息表.

輸出:決策屬性對條件屬性的依賴度.

步驟1:對決策表進行預處理,將決策類屬性轉換成整型,并賦予每個對象唯一編號,額外添加一個標記,默認值為0.

步驟2:讓每個對象xi(即編號為i的對象)與表中其余對象xj作比較,若xi的決策屬性大于xj,則比較xi與xj的條件屬性.若條件屬性完全相同,將xi與xj的標記改為1;若存在不同屬性值,則直接進入下一輪比較.

步驟3:遍歷決策表,統(tǒng)計標記為0的對象即可求出屬于正的對象數(shù),進而求得依賴度.

FDC算法通過直接尋找基于相對正域的對象來計算依賴度,而不需要預先求出相對正域,是一個較好的思路,章夏杰等表示此算法的時間復雜度為O(|U|2×|C|/2)[13]520,復雜度降低了.

3 縱橫依賴計算

在上述算法中,思路是將不屬于相對正域的對象標記為1,但存在不少重復進行比較的地方,首先是每一個對象都要重復地與其他對象就決策類大小進行遍歷性比較,其次是極有可能出現(xiàn)一個已經確定是不屬于相對正域的對象就決策類與條件屬性都被重復比較了多次,浪費了時間.本研究在此基礎上,進一步提出一個改進算法.

改進的策略如下:

1)按決策類對元素進行排序后,不必就每一對象重復地進行決策類大小比較;

2)如果一個對象已經確認不屬于相對正域,那么其他與其具有相同條件屬性的同類決策類中的元素也不屬于相對正域(橫向比較);

3)如果一個對象已經確認不屬于相對正域,就不必再將其與低階決策類中其他對象比較(縱向比較).

實現(xiàn)這個策略的算法如下,這個算法不妨暫稱為縱橫比較依賴度算法,簡稱縱橫依賴計算VHDC(Vertical and horizontal dependency calculation).在下面給出的VHDC算法中,為了便于編程,不僅給出框架,而且已經給出較為詳細算法結構.

輸入:決策信息表.

輸出:決策屬性對條件屬性的依賴度.

第一步(預處理):將決策表按照整型決策類順序從小到大排列,每個對象賦予唯一的ID號,同時增加一個標志列,初始值為0;記全體對象記錄數(shù)為M,增加一個內存變量N,記錄非正域對象數(shù),初始值為0;設決策類共有K類,內存變量k記錄第k決策類,初始值k=2,并記第k決策類有nk個對象.

第二步:如果k>K,轉第四步.否則,對按決策類順序排好的決策表中的第k類中的對象,與類別小于k的決策類中的對象進行比較操作(縱向比較),找出不屬于相對正域的對象,先令l=1(l變量用于決策類層數(shù)的循環(huán)).

第三步:如果k-l<1,轉第二步.否則,對第k決策類中每一個標志為0的對象xi,做如下操作:對k-l決策類中的對象的xj,比較它們的每一個條件屬性值,直到比較完k-l決策類中的所有對象;

如果所有條件屬性值相同,則可按如下操作進行.

1)如果xj的標志為1,則將xi的標志改為1,N=N+1,停止將第k決策類的對象xj繼續(xù)與其他低層決策類的對象比較(停止該對象的縱向比較);同時將第k決策類中其余標志為0的對象與xi比較,如果所有條件屬性相同,則將標志改為1,N=N+1,直到這一決策類比較完畢(橫向比較);然后令l=1,轉第三步,對下一個第k決策類中標志為0的對象xi進行比較;如果第k類中的對象已經比較完畢,則k=k+1,轉第二步進行高1階決策類的比較.

2)如果xj的標志為0,則有將xi,xj的標志賦值為1,同時N=N+2;對第k-1決策類的其他標志為0的對象,與xi相比,如果所有條件屬性相同,則將標志改為1,N=N+1;對第k決策類的其他標志為0的對象,與xi相比,如果所有條件屬性相同,則將標志改為1,N=N+1,l=l+1;轉第三步.

如果存在條件屬性值不相同,則比較下一個k-1決策類的xj,轉第三步.

第四步:輸出依賴度γ=(M-N)/M.

算法分析:第一步,需要對全體對象按決策類大小進行排序,通常的排序算法其時間復雜度為O(|U|×ln|U|).排序盡管也花了一定的時間,但為后面的計算節(jié)省了大量重復計算的時間.第二、三步,采用按排序后決策類的對象來進行比較,本算法能夠避免了很多重復的計算,首先是省去了對每個對象,都要遍歷對象集去進行決策類的比較;其次如果第k決策類某個對象與第k-1決策類的某個標志為1的對象在各個條件屬性下屬性值相同,那么第k決策類這個對象就不必繼續(xù)與其他更低決策類的對象進行比較了;此外,算法中還設計了同層決策類有相同條件屬性值時,不必再與其他對象比較的環(huán)節(jié),這也避免了很多重復計算.最壞情況下,是第k決策類的所有對象xi與第k-1、k-2、……、2類的所有對象xj都需要進行條件屬性值的比較(一般不會出現(xiàn)),最好的情況是第k決策類的所有對象xi只須與第k-1決策類的對象進行條件屬性比較.因此盡管此時最壞情況下的時間復雜度[為O(|U|2×|C|/2)]與FDC算法相同,但因減少了第四步的遍歷、整體比較中減少大量重復的比較,故整體上比FDC算法提高了運算效率.

4 算例

下面以一個算例來說明具體的算法過程與優(yōu)劣比較.數(shù)據(jù)表(見表1)中a、b、c為條件屬性,D為決策屬性,決策類共有4個.

表1 有4個決策類的一種快速縱橫依賴計算原始表

如表2所示,根據(jù)FDC的算法,對原始表進行預處理,決策類改為整型1,2,3,4,并增加一個標志列,初始標志值全為0.而根據(jù)本研究提出的VHDC算法,預處理后按決策類順序排列對象,如表3所示,其中對象編號為方便計算,仍按大小順序編號.

表2 FDC算法中預處理后的結果

為方便比較,現(xiàn)以表3的數(shù)據(jù)形式,分別按FDC和VHDC算法分析其具體的計算過程.

表3 VHDC算法預處理后的結果

1)FDC算法.

其算法的第二步,對所有決策類大于1的對象,都需要與比其決策類小的所有對象,進行條件屬性的比較.

第1、2、3個對象:因決策類為1,沒有比1更低的決策類,故不需要遍歷對象集.其標志仍為0.

第4、5個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11,以比較每個對象的決策類是否小于2,是則進行條件屬性值比較,否則不進行.該對象決策類別為2,還需要對決策類別為1的3個對象,對所有條件屬性分別進行比較,因不全相同,所以標志仍為0.決策類大小的比較共有(M-1)次;條件屬性值的比較共有3*n1次.

第6個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11,該對象決策類別為2,還需要對決策類別為1的3個對象,進行條件屬性值比較,發(fā)現(xiàn)與第1決策類第2個對象的條件屬性全相同,所以將這兩個對象的標志均改為1.決策類大小的比較共(M-1)次;條件屬性值的比較共3*n1次;改標志值共2次.

第7個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11,該對象決策類別為3,還需要對決策類別為1的3個對象,及決策類別為2的3個對象,進行條件屬性值比較.沒有條件屬性全相同的對象,所以標志仍為0.決策類大小的比較共(M-1)次;條件屬性值的比較共(3*n1+3*n2)次.

第8個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11.該對象決策類別為3,還需要對決策類別為1的3個對象,及決策類別為2的3個對象,進行條件屬性值比較.首先發(fā)現(xiàn)與第1決策類的第2個對象所有條件屬性值相同,所以先將這兩個對象的標志改為1;然后又發(fā)現(xiàn)與第2決策類第6個對象的條件屬性值全相同,所以又將這兩個對象的標志均改為1.本來第8個對象的標志已經是1了,還要再改為1,說明有些重復.決策類大小的比較共(M-1)次;條件屬性值的比較共(3*n1+3*n2)次;改標志共4次.

第9個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11.該對象決策類別為3,還需要對決策類別為1的3個對象,及決策類別為2的3個對象,進行條件屬性值比較.沒有條件屬性全相同的對象,所以標志仍為0.決策類大小的比較共(M-1)次,條件屬性值的比較共(3*n1+3*n2)次.

第10個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11,該對象決策類別為4,還需要對決策類別為1、2、3的共9個對象,進行條件屬性值比較.首先發(fā)現(xiàn)與第3決策類的第7個對象所有條件屬性值相同,所以先將這兩個對象的標志改為1;然后又發(fā)現(xiàn)與第3決策類第9個對象的條件屬性值全相同,所以又將這兩個對象的標志均改為1.本來第10個對象的標志已經是1了,還要再改為1,說明有些重復.決策類大小的比較共(M-1)次;條件屬性值的比較共(3*n1+3*n2+3*n3)次;改標志共4次.

第11個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11.該對象決策類別為4,還需要對決策類別為1、2、3的共9個對象,進行條件屬性值比較.結果沒有發(fā)現(xiàn)與其條件屬性值全相同者,決策類大小的比較共(M-1)次;條件屬性值的比較共(3*n1+3*n2+3*n3)次.

第12個對象:需要遍歷對象集一遍,次數(shù)為(M-1),此例為11.該對象決策類別為4,還需要對決策類別為1、2、3的共9個對象,進行條件屬性值比較.首先發(fā)現(xiàn)與第3決策類的第7個對象所有條件屬性值相同,所以先將這兩個對象的標志改為1;然后又發(fā)現(xiàn)與第3決策類第9個對象的條件屬性值全相同,所以又將這兩個對象的標志均改為1.本來第7、9個對象的標志已經是1了,還要再改為1,說明有些重復.決策類大小的比較共(M-1)次;條件屬性值的比較共(3*n2+3*n2+3*n3)次;改標志共4次.

FDC算法總體的算法是,對任一固定對象,先遍歷所有對象與其比較，判斷其他對象的決策類是否比其小,若否,則轉下一個對象;若是,則還需要比較它們在每一個條件屬性上的取值是否相同,如果相同,則無論原來被比較的對象標志是否為1,都要重新將其置為1.這樣,在本例中,其第二步總的比較次數(shù)是

|U|*(|U|-1)+n2*n1*|C|+n3*(n2+n1)*|C|+n4*(n3+n2+n1)*|C|=294,

(8)

同時標志被改動次數(shù)為9次(實際非正域個數(shù)為7).

2)VHDC算法

由上可見,FDC算法中存在大量重復計算的現(xiàn)象,影響了其效率.作為對照,現(xiàn)在來看看由本研究提出的改進算法VHDC算法,此時的計算進程:

第1、2、3個對象:因決策類為1,沒有比1更低的決策類,故不需要遍歷對象集.其標志仍為1.這一步與FDC算法一樣.

第4、5個對象:該對象決策類別為2,不需要遍歷論域,只需要對決策類別為1的3個對象,進行條件屬性值比較,因不全相同,所以標志仍為0.比較條件屬性值共3*n1次,因已經對決策類排好序了,此時不需要比較決策類,下同.FDC需要遍歷對象集一遍,才能判斷對象是否屬于第幾類.

第6個對象:該對象決策類別為2,不需要遍歷論域,只需要對決策類別為1的3個對象,進行條件屬性值比較,發(fā)現(xiàn)與第1決策類第2個對象的條件屬性全相同,所以將這兩個對象的標志均改為1.同時,非相對正域對象數(shù)N=0+2=2.同時在第1類對象中繼續(xù)遍歷檢查是否還有與該對象條件屬性全相同者,在第2決策類對象中往后繼續(xù)遍歷檢查是否還有與該對象條件屬性全同者,當前情形沒有.比較條件屬性值共小于[3*n1+3*(n2-1)]次.FDC需要遍歷對象集一遍,VHDC僅需要依次遍歷第2、1決策類的對象.

第7個對象:該對象決策類別為3,先按順序對決策類別為2的3個對象進行比較,發(fā)現(xiàn)沒有與其條件屬性值全同者,故再與第1決策類的對象進行比較,仍沒有條件屬性全相同的對象,所以標志仍為0.比較條件屬性值,比較次數(shù)為(3*n1+3*n2).FDC需要遍歷對象集一遍,VHDC僅需要依次遍歷第2、1決策類的對象.

第8個對象:該對象決策類別為3,先按順序對第2決策類的3個對象進行比較,發(fā)現(xiàn)第2決策類最后一個對象即第6個對象與其條件屬性值全同者,而第6個對象的標志已經為1,故只須將這第8個對象的標志改為1,同時,非相對正域對象數(shù)N=N+1=2+1=3;然后再橫向比較:第2決策類已經到最后一個,不用再繼續(xù),第3決策類再與第9個對象比較,沒有條件屬性全相同的對象,所以標志不改.此時,不再與第1決策類比較.比較條件屬性值,共比較次數(shù)為(3*n2+1).FDC需要遍歷對象集一遍,且重復更改了第2個對象的標志;VHDC僅需要依序遍歷第3、2決策類的對象,且統(tǒng)計了到目前為止的非相對正域對象數(shù)N.

第9個對象:該對象決策類別為3,先按順序對決策類別為2的3個對象進行比較,發(fā)現(xiàn)沒有與其條件屬性值全同者,故再與第1決策類的對象進行比較,仍沒有條件屬性全相同的對象,所以標志仍為0.比較條件屬性值次數(shù)為(3*n1+3*n2).FDC需要遍歷對象集一遍,VHDC僅需要依序遍歷第2、1決策類的對象.

第10個對象:該對象決策類別為4,先按順序對第3決策類的對象進行比較,發(fā)現(xiàn)第3決策類最后一個對象即第9個對象與其條件屬性值全同者,故將這兩個對象的標志改為1,同時,非相對正域對象數(shù)N=N+2=3+2=5;然后再橫向比較:第3決策類第7個對象也與其條件屬性值全同,將第7個對象標志改為1,N=N+1=5+1=6;第4決策類第12個對象也與其條件屬性值全同,故將第12個對象標志改為1,N=N+1=6+1=7.此時,不再與第2、1決策類比較.比較條件屬性次數(shù)為(3*n3+3*n4).FDC需要遍歷對象集一遍,且重復更改了上述幾個對象的標志;VHDC僅需要依序遍歷第4、3決策類的對象,且統(tǒng)計了到目前為止的非相對正域對象數(shù)N.

第11個對象:決策類別為4,先與第3決策類對象進行比較,無條件屬性值全同,再與第2決策類對象進行比較,同樣無條件屬性值全同,故再與第1決策類對象比較,仍無全同者,比較完畢,標志仍為0(沒有改動).比較條件屬性次數(shù)為[3*n3+3*(n2+n1)].這種情形比較條件屬性次數(shù)與FDC算法一樣,但不必進行決策類別的遍歷性比較.

第12個對象:因其標志已經為1,不必再進行任何比較.而FDC仍需要遍歷對象集一遍.

通過比較,可以發(fā)現(xiàn)VHDC算法比FDC算法減少了很多不必要的重復比較.此例中,關鍵一步VHDC比較的次數(shù)只有163,遠小于FDC的294次.

執(zhí)行VHDC算法第二、三步后的結果與執(zhí)行FDC算法第二步后的結果相同,參見表4.

表4 執(zhí)行VHDC算法與FDC算法后的結果

此例中,加上預處理與計算依賴度均需要遍歷對象集,FDC最終計算次數(shù)是12+294+12=318次.而VHDC預處理計算次數(shù)為12*log212=43,計算依賴度不需要額外的遍歷,其最終計算次數(shù)是43+163=206次,效率提高了35%.當數(shù)據(jù)規(guī)模很大時,其優(yōu)勢將更顯突出.

5 結論

依賴度的計算在特征選擇、屬性約簡等方面有重要的應用,研究快速依賴度算法具有十分重要的實際意義.本研究提出的縱橫依賴計算算法,進一步降低了時間復雜性,提高了運算效率,為特征選擇及屬性約簡提供了一種新的快速計算途徑.實例表明,其效率是高的、可行的.下一步將結合屬性重要性及單屬性依賴度研究更高效的算法.