劉 斌, 倪志偉, 趙 敏

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

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

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

1 相關(guān)研究

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

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

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

原有的改進(jìn)的貪心算法描述如下[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個(gè)斷點(diǎn)[Cra,Cr+1a]。對(duì)于任意 Pra,如果[Cra,Cr+1a]?[min(a(xi),a(xj)),max(a(xi),a(xj))],則Pra((xi,xj))=1;否則 Pra((xi,xj))=0。

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

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

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

上面算法中,衡量斷點(diǎn)的重要性是以列的1的個(gè)數(shù)多少作為主要標(biāo)準(zhǔn)的,見表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。

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

2 新的改進(jìn)方案

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

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

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

其中,U|IND(B)={(X?U∧?x?y?b(b(x)=b(y)))}是不可分明關(guān)系B對(duì)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負(fù)域。

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

表2 信息表(二)

基于屬性重要性的貪心算法的改進(jìn)算法描述如下:

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

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

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

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

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

3 實(shí)例及結(jié)果

考察表3所列的信息表,選擇斷點(diǎn)分別為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*

這時(shí)在表4中出現(xiàn)在列中1的數(shù)目相等,斷點(diǎn)所在的列值為1的行的1的數(shù)目相加,和值也相等的情況,就需要引入屬性重要性概念并通過該方法確定選擇的下一個(gè)斷點(diǎn)。顯然,在表3中,令Q=決策屬性集=syggg00,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上的斷點(diǎn)P2a。

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

4 結(jié)束語

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

[1] 楊善林,倪志偉.機(jī)器學(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].計(jì)算機(jī)科學(xué),2000,27(12):89-94.

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

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

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

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

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