基于屬性重要性的貪心算法的改進算法

劉 斌, 倪志偉, 趙 敏

(合肥工業(yè)大學(xué)管理學(xué)院,安徽合肥 230009)

從數(shù)據(jù)庫中發(fā)現(xiàn)知識(Knowledge Discovery In Database,簡稱KDD)或稱為數(shù)據(jù)挖掘(Data Mining,簡稱 DM)[1]的技術(shù)自20世紀80年代末提出以來,得到了廣泛重視和迅猛發(fā)展。許多數(shù)據(jù)挖掘算法的模型要求被挖掘的數(shù)據(jù)必須是離散型的,但是現(xiàn)實中很多的數(shù)據(jù)是連續(xù)型的,所以,必須先對連續(xù)型數(shù)據(jù)進行離散處理。對數(shù)據(jù)進行離散不僅滿足了挖掘算法的需要,還可減少各個屬性所對應(yīng)的數(shù)據(jù)值的數(shù)目,從而提高挖掘系統(tǒng)的挖掘效率以及所得知識的可理解性。

粗糙集理論[2]是一種處理不完備不精確信息的知識獲取工具,廣泛應(yīng)用于數(shù)據(jù)挖掘、知識提取、模式識別、專家預(yù)測等多個領(lǐng)域。粗糙集[3,4]在應(yīng)用中一般要求信息系統(tǒng)中的屬性值必須是離散型的表達形式,連續(xù)屬性的離散化[5-7]是粗糙集數(shù)據(jù)預(yù)處理過程中的一個重要環(huán)節(jié)。

1 相關(guān)研究

S=〈U,R,V,f〉,R=C∪j5i0abt0b是屬性集合,子集C和j5i0abt0b分別稱為條件屬性集和決策屬性集,U={,…,}是有限的對象集合,即論域。設(shè)決策種類的個數(shù)為r(d)。屬性a的值域Va上的一個斷點可以記為(a,c),其中,a∈R;c為實數(shù)集。在值域上的任意一個斷點集合{(a,c1a),(a,c2a),…,(a,ckaa)}定義了Va上的一個分類Pa,即

因此,任意的P=∪Pa定義了一個新的決策表Sp=〈U,R,Vp,fp〉,fp(xa)=i?f(xa)∈[cia,ci+1a],對于 x ∈U,i,j∈{0,…,Ka},即經(jīng)過離散化之后,原來的信息系統(tǒng)被一個新的信息系統(tǒng)所代替。

布爾邏輯和粗糙集理論相結(jié)合的離散化算法[8]是粗糙集理論中的離散化算法在思想上的重大突破,是讓其中一個斷點或幾個斷點去區(qū)分2個實例的不同的不可分辨關(guān)系,此種算法的思想是首先在保持信息系統(tǒng)的不可分辨關(guān)系不變的前提下,盡量以最少數(shù)目的斷點集能夠把所有實例間的分辨關(guān)系區(qū)分開。為了求得最小數(shù)目的斷點集,改進的貪心算法1每次取重要性最高的斷點[9]。斷點的重要性是以各列中1的數(shù)目來衡量的,1的個數(shù)多,則斷點的重要性高。當有2列1的個數(shù)相同時,把斷點所在的列值為1的行的1的數(shù)目相加,和值越小,則說明斷點重要性越高。

原有的改進的貪心算法描述如下[1,9]:

(1)根據(jù)原來的信息系統(tǒng)S構(gòu)造新的信息系統(tǒng)S*。構(gòu)造新的信息表 S*算法如下:U*={(xi,xj)∈U ×U|d(xi)≠d(xj)};R*={Pra|a∈C},Pra是屬性a的第r個斷點[Cra,Cr+1a]。對于任意 Pra,如果[Cra,Cr+1a]?[min(a(xi),a(xj)),max(a(xi),a(xj))],則Pra((xi,xj))=1;否則 Pra((xi,xj))=0。

(2)初始化斷點集CUT=?。

(3)選取所有列中1的個數(shù)最多的斷點加入到CUT中,去掉此斷點所在的列和在此斷點上值為1的行;當有1個以上的斷點的1的個數(shù)相同時,把列對應(yīng)的斷點所在的列值為1的對應(yīng)的行的1的數(shù)目相加,取和最小的斷點。

(4)如果信息系統(tǒng)S*中的元素不為空,則轉(zhuǎn)第(3)步;否則停止。此時CUT即是得到的斷點集。

上面算法中,衡量斷點的重要性是以列的1的個數(shù)多少作為主要標準的,見表1所列。

表1 信息表(一)

P3a所在的列值為1的行的1的數(shù)目相加為(3+3+6+3+2+2)=19;P2b所在的列值為1的行的1的數(shù)目相加為(3+6+3+4+1+2)=17,因此可以優(yōu)先取 P2b。

但是當列中1的數(shù)目相等,斷點所在的列值為1的行的1的數(shù)目相加,和值也相等的情況下,沒有提出解決的辦法。

2 新的改進方案

為了區(qū)分存在上述情況下的斷點重要性,首先引入以下概念。

定義1 對每個概念X(樣例子集)和不分明關(guān)系B,包含于X中的最大可定義集和包含X的最小可定義集,都是根據(jù)B確定的,前者稱為X的下近似集(記為B-(X)),后者稱為X的上近似集(記為B-(X))。

定義2 給定知識表達系統(tǒng) S=〈U,R,V,f〉,對于每個子集X ?U和不分明關(guān)系B,X的上近似集和下近似集分別可以由B得基本集定義如下:

其中,U|IND(B)={(X?U∧?x?y?b(b(x)=b(y)))}是不可分明關(guān)系B對U的劃分,也是論域U的B基本集的結(jié)合。

定義3 集合BNB(X)=B-(X)B-(X)稱為X的B邊界;POSB(X)=B-(X)稱為X的B正域;NEGB(X)=UB-(X)稱為X的B負域。

當在列中1的數(shù)目相等,斷點所在的列值為1的行的1的數(shù)目相加,和值也相等的情況下,改進的貪心算法無法選擇較為重要的斷點,見表2所列[10]。為了解決此類問題,本文提出了基于屬性重要性的貪心算法。

表2 信息表(二)

基于屬性重要性的貪心算法的改進算法描述如下:

(1)根據(jù)原來的信息系統(tǒng)S構(gòu)造新的信息系統(tǒng)S*。

(2)初始化斷點集CUT=?。

(3)選取所有列中1的個數(shù)最多的斷點加入到CUT中,去掉此斷點所在的列和在此斷點上值為1的行;當有1個以上的斷點的1的個數(shù)相同時,把列對應(yīng)的斷點所在的列值為1的對應(yīng)的行的1的數(shù)目相加,取和最小的斷點;當在列中1的數(shù)目相等,斷點所在的列值為1的行的1的數(shù)目相加,和值也相等的情況下,引入屬性重要性概念,根據(jù)屬性重要程度選擇相應(yīng)屬性的斷點。判斷屬性重要性的計算方式如下[1]:

則屬性a的重要性為rC(D)-rC{a}。

(4)如果信息系統(tǒng)S*中的元素不為空,則轉(zhuǎn)第(3)步;否則停止。此時 CUT即是得到的斷點集。

3 實例及結(jié)果

考察表3所列的信息表,選擇斷點分別為P1a=[0.5,1.2],P2a=[1.2,2.6],P3a=[2.6,3.2],P1b=[0.6,2.3],P2b=[2.3,3.5]。由S構(gòu)造新的信息表S*,見表4所列。

表3 信息表(三)

表4 信息表S*

這時在表4中出現(xiàn)在列中1的數(shù)目相等,斷點所在的列值為1的行的1的數(shù)目相加,和值也相等的情況,就需要引入屬性重要性概念并通過該方法確定選擇的下一個斷點。顯然,在表3中,令Q=決策屬性集=j5i0abt0b,P=條件屬性全集={a,b},且

則有:

屬性a的重要性為:rC(Q)-rC{a}=1-0.2=0.8;屬性b的重要性為:rC(Q)-rC=1-0.6=0.4。屬性a的重要性大于屬性b,所以優(yōu)先選擇屬性a上的斷點P2a。

實驗結(jié)果表明,這種基于屬性重要性的貪心算法在分析斷點對決策類的區(qū)分能力上遠遠強于貪心算法,在貪心算法無法做出斷點判斷的情況下,能夠有效地區(qū)分斷點,進而得到最小的斷點集。而與文獻[9]的改進方法相比,雖然時間復(fù)雜度上要大一些,但是考慮的情況比較全面,在前者無法做出識別的情況下,完成斷點的判斷。

4 結(jié)束語

本文針對改進的貪心算法面對斷點重要性考慮不全面,提出了一種新的粗糙集離散化的處理方法,即基于屬性重要性的貪心算法,先通過分析斷點對決策類的區(qū)分能力,在區(qū)分能力相同的情況下采用屬性重要優(yōu)先算法,逐一將斷點加入到斷點集中,求得最小斷點集,從而完成對信息表的離散化。

[1] 楊善林,倪志偉.機器學(xué)習(xí)與智能決策支持系統(tǒng)[M].北京:科學(xué)出版社,2004:331-332.

[2] Pawlak Z.Rough set[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.

[3] 張文修.粗糙集理論與方法[M].北京:科學(xué)出版社,2003:32-36.

[4] Nguyen S H,Nguyen H S.Some efficient algorithms for roug h set methods[C]//Proceedings of the Conference of Information Processing and Management of Uncertainty in Knowledge Based Systems,Granada,Spain,1996:34-37.

[5] 侯利娟,王國胤.粗糙集論中的離散化問題[J].計算機科學(xué),2000,27(12):89-94.

[6] 苗奪謙.Rough Set理論中連續(xù)屬性的離散化方法[J].自動化學(xué)報,2001,27(3):296-302.

[7] 于金龍,李曉紅,孫立新.連續(xù)屬性的整體離散化[J].哈爾濱工業(yè)大學(xué)學(xué)報,2000,32(3):48-53.

[8] 王國胤.Rough集理論與知識獲取[M].西安:西安交通大學(xué)出版社,2001:99-112.

[9] 寧 偉,趙明清.關(guān)于決策表離散化貪心算法的進一步改進[J].計算機工程與應(yīng)用,2007,43(3):173-178.

[10] 何亞群,胡壽松.粗糙集中連續(xù)屬性離散化的一種新方法[J].南京航空航天大學(xué)學(xué)報,2003,35(2):213-215.