呂 豐

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院,南寧 530004)

0 引言

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

1 基礎(chǔ)知識(shí)

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

(6)

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

(7)

2 依賴度計(jì)算

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

通常計(jì)算依賴度的算法如下.

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

輸入:決策信息表.

輸出:決策屬性對(duì)條件屬性的依賴度.

步驟1:對(duì)決策表進(jìn)行預(yù)處理,將決策類屬性轉(zhuǎn)換成整型,并賦予每個(gè)對(duì)象唯一編號(hào),額外添加一個(gè)標(biāo)記,默認(rèn)值為0.

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

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

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

3 縱橫依賴計(jì)算

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

改進(jìn)的策略如下:

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

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

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

實(shí)現(xiàn)這個(gè)策略的算法如下,這個(gè)算法不妨?xí)悍Q為縱橫比較依賴度算法,簡(jiǎn)稱縱橫依賴計(jì)算VHDC(Vertical and horizontal dependency calculation).在下面給出的VHDC算法中,為了便于編程,不僅給出框架,而且已經(jīng)給出較為詳細(xì)算法結(jié)構(gòu).

輸入:決策信息表.

輸出:決策屬性對(duì)條件屬性的依賴度.

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

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

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

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

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

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

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

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

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

4 算例

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

表1 有4個(gè)決策類的一種快速縱橫依賴計(jì)算原始表

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

表2 FDC算法中預(yù)處理后的結(jié)果

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

表3 VHDC算法預(yù)處理后的結(jié)果

1)FDC算法.

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

第1、2、3個(gè)對(duì)象:因決策類為1,沒有比1更低的決策類,故不需要遍歷對(duì)象集.其標(biāo)志仍為0.

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

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

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

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

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

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

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

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

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

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

(8)

同時(shí)標(biāo)志被改動(dòng)次數(shù)為9次(實(shí)際非正域個(gè)數(shù)為7).

2)VHDC算法

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

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

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

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

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

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

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

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

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

第12個(gè)對(duì)象:因其標(biāo)志已經(jīng)為1,不必再進(jìn)行任何比較.而FDC仍需要遍歷對(duì)象集一遍.

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

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

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

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

5 結(jié)論

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