王映龍,曾 淇,錢文彬,2,舒文豪,黃錦濤

(1.江西農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院, 南昌 330045; 2.江西農(nóng)業(yè)大學(xué) 軟件學(xué)院, 南昌 330045;3.華東交通大學(xué) 信息工程學(xué)院,南昌 330013)(*通信作者電子郵箱qianwenbin1027@126.com)

0 引言

在大數(shù)據(jù)時代,信息系統(tǒng)中的數(shù)據(jù)隨著時間的變化而不斷更新。如何快速針對大量的動態(tài)數(shù)據(jù)中更新屬性約簡結(jié)果,已成為粒計(jì)算和知識發(fā)現(xiàn)領(lǐng)域的研究熱點(diǎn)[1-5]。針對動態(tài)數(shù)據(jù),不同的信息系統(tǒng)處理數(shù)據(jù)的方法是不一樣的,一些研究者對處理動態(tài)更新的數(shù)據(jù)集進(jìn)行了相關(guān)探索,并已取得許多有意義的成果[6-9]。針對信息系統(tǒng)中數(shù)據(jù)的動態(tài)更新,采用增量式計(jì)算屬性約簡方法成為一種可行的解決途徑。對于完備的信息系統(tǒng),文獻(xiàn)[3]中利用差別矩陣方法對屬性約簡進(jìn)行了增量式更新;文獻(xiàn)[6]中以信息粒度作為啟發(fā)信息設(shè)計(jì)了增量式計(jì)算屬性約簡方法;文獻(xiàn)[7]中為應(yīng)對動態(tài)變化的海量數(shù)據(jù),設(shè)計(jì)了兩種并行增量更新粗糙近似集的算法;文獻(xiàn)[8]中提出了基于二進(jìn)制差別矩陣和信息熵的動態(tài)約簡算法,有效縮小了算法的搜索空間；文獻(xiàn)[9]中結(jié)合變精度粗糙集模型,構(gòu)造出近似集增量式更新的矩陣算法。

在信息系統(tǒng)中,數(shù)據(jù)的激增難免會導(dǎo)致數(shù)據(jù)的丟失,對于信息系統(tǒng)中存在缺失值的問題,一般采用以下兩種方法:一是對缺失值進(jìn)行刪除、替換等處理,使不完備數(shù)據(jù)變成完備數(shù)據(jù)后再進(jìn)行屬性約簡;二是不對缺失值進(jìn)行預(yù)處理,直接采用能夠處理不完備數(shù)據(jù)集的計(jì)算模型進(jìn)行屬性約簡。當(dāng)前第二種方法運(yùn)用較廣泛,如文獻(xiàn)[10]中在融入一定程度誤差的分類思想下,對不完備信息系統(tǒng)提出基于限制容差關(guān)系的程度多粒度粗糙集, 結(jié)合容差粗糙集模型,提出二進(jìn)制區(qū)分矩陣的增量式屬性約簡方法。文獻(xiàn)[11]中介紹了三個矩陣在四種不同擴(kuò)展關(guān)系下的增量式更新方法。文獻(xiàn)[12]中設(shè)計(jì)了一種基于正向近似的通用特征選擇加速算法處理海量數(shù)據(jù)。除了經(jīng)典粗糙集探討的名義型變量,數(shù)值型變量廣泛存在于應(yīng)用領(lǐng)域,為解決大量數(shù)值型數(shù)據(jù)的更新問題,文獻(xiàn)[13]中針對連續(xù)型屬性的數(shù)據(jù)集,研究了基于鄰域粗糙集的特征子集增量式更新方法,通過分析新增對象對正域的影響,選擇性地動態(tài)更新,避免了重復(fù)操作。文獻(xiàn)[14]中從信息觀出發(fā),運(yùn)用條件熵的度量方法,設(shè)計(jì)了完備鄰域系統(tǒng)中增量式屬性約簡算法。

上述研究針對不同的數(shù)據(jù)類型,分別在完備或不完備信息系統(tǒng)中設(shè)計(jì)了增量式更新方法,由于現(xiàn)實(shí)生活中同時存在大量的不完備、連續(xù)數(shù)值型、名義型數(shù)據(jù)的情況,現(xiàn)有的鄰域粗糙集增量式更新計(jì)算方法對上述情況討論較少。為此,本文針對決策信息系統(tǒng)中同時存在大量的不完備型、連續(xù)數(shù)值型、名義型混合數(shù)據(jù)的情況,研究如何有效處理動態(tài)的數(shù)據(jù),實(shí)現(xiàn)屬性約簡的增量式更新。首先,分析了對象增量式更新所引起的條件熵變化情況和更新機(jī)制;然后,結(jié)合可變精度的粗糙集概念,構(gòu)造了面向不完備鄰域決策系統(tǒng)的對象增量式更新屬性約簡算法,該算法能直接處理不完備的數(shù)值型和符號型混合數(shù)據(jù),最后,通過實(shí)例分析和實(shí)驗(yàn)比較驗(yàn)證了算法的有效性。

1 基礎(chǔ)理論

若給定一個決策信息系統(tǒng)DS=(U,C,D,V),其中U={x1,x2,…,xn}表示非空有限對象集合,稱為論域;C是條件屬性集合,D是決策屬性,C∩D=?,若D=?,則決策系統(tǒng)轉(zhuǎn)換為信息系統(tǒng)；V為屬性值域,對于?a∈C∪D,Va為屬性a的值域,xi(a)為對象xi在屬性a上的取值。

如果V中包含連續(xù)型和符號型等屬性類型的對象,則該系統(tǒng)稱為鄰域決策系統(tǒng)。在鄰域決策系統(tǒng)中,當(dāng)部分對象的屬性值缺失時,則該系統(tǒng)稱為不完備鄰域決策系統(tǒng),缺失值用“*”表示。

定義1[1]設(shè)DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對于?x∈U,定義x在A=C∪D上的鄰域信息粒子為NA(x)={y|y∈U,ΔA(x,y)≤δ,δ≥0},其中δ表示鄰域半徑,ΔA:U×U→R為U上的一個度量,滿足以下性質(zhì):

1)?x,y∈U, ΔA(x,y)≥0, 當(dāng)ΔA(x,y)=0時, ?ai∈A,ai(x)=ai(y);

2)?x,y∈U,ΔA(x,y)=ΔA(y,x);

3)?x,y,z∈U,ΔA(x,z)≤ΔA(x,y)+ΔA(y,z)。

對于連續(xù)型的數(shù)據(jù),采用歐氏距離度量:

對于符號型的數(shù)據(jù)中,可定義:

當(dāng)δ=0時,變?yōu)榻?jīng)典粗糙集模型。

定義2[15]將鄰域等價(jià)關(guān)系擴(kuò)展到符號型、連續(xù)型和缺失型等未知屬性共存下的不完備模糊系統(tǒng),可得到以下廣義鄰域關(guān)系:

R(x)={(x,y)∈U2:?a∈x∩f1(x)=f1(y),

a(x)∈δ(y,a)∪a(y)∈δ(x,a)∪a(x)=

*∪a(y)=*}

廣義鄰域關(guān)系滿足自反性,但不一定滿足對稱性和傳遞性,因?yàn)槿我鈱ο笈c其自身是不可分辨的,所以任何等價(jià)關(guān)系均滿足自反性。在這里放寬了對稱性和傳遞性的限制,擴(kuò)展了應(yīng)用范圍。

信息熵作為一種度量信息的不確定性的有效方法,實(shí)現(xiàn)對信息的量化度量。梁吉業(yè)等在文獻(xiàn)[16]給出了信息系統(tǒng)在經(jīng)典粗糙集計(jì)算模型下信息熵的統(tǒng)一表示:

定義3[16]設(shè)S=(U,B)是一個決策信息系統(tǒng),粒度K(B)=(SB(x1),SB(x2),…,SB(x|U|)),其中SB(xi)是對象xi在屬性B下的類,則B的信息熵為:

2 可變精度的屬性約簡計(jì)算模型

現(xiàn)有的文獻(xiàn)大多是針對完備的單一連續(xù)型數(shù)據(jù)對鄰域決策系統(tǒng)展開研究,本文提出的不完備可變精度的粗糙集計(jì)算方法,則結(jié)合了廣義鄰域下可變精度的粗糙集模型,能直接處理不完備的數(shù)值型和符號型混合數(shù)據(jù)。

定義4[17]DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),X和Y是U上的兩個非空子集,定義集合X關(guān)于集合Y的相對錯誤分類率:

定義5 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),B?C,決策屬性集合D={d1,d2,…,dn},0≤k<0.5,在可變精度k下,屬性集B相對于決策屬性D的上、下近似分別為:

決策屬性值di在可變精度k的上近似是:U中不小于k的分類對象劃分到di上鄰域信息粒子的集合,下近似是:U中不小于1-k的分類對象劃分到di上鄰域信息粒子的集合。根據(jù)多粒度粗糙集的思想,在可變精度不完備鄰域決策系統(tǒng)中,通過對鄰域粒度δ和可變精度k的控制來區(qū)分不同的信息。鄰域粒度δ越小,可變精度k取值越優(yōu),區(qū)分能力越強(qiáng)。

定義6 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對象x、y∈U,ΔA(x,y)為對象x、y在U上的一定度量,對象x、y在條件屬性C上的區(qū)分值ΔC(x,y)為:

分兩種情況:1)當(dāng)對象x、y的度量值ΔA(x,y)=0,或者小于等于鄰域半徑,則對象x、y在條件屬性C上的區(qū)分值ΔC(x,y)=1。 2)當(dāng)對象x、y的度量值為無窮大,或者大于鄰域半徑,則對象x、y在條件屬性C上的區(qū)分值ΔC(x,y)=0。

定義7 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對象x,y∈U,C是條件屬性集合,ΔA(x,y)為對象x、y在U上的一定度量,ΔC(x,y)為對象x、y在條件屬性C上的區(qū)分值,可變精度k為:

性質(zhì)1 在不完備鄰域決策系統(tǒng)DS=(U,C,D,V)中,對象xi,xj∈U,xi(D)為對象xi在決策屬性D上的取值,xi(C0)為對象xi在符號型條件屬性C0上的取值,δxi(C1)為對象xi在連續(xù)型屬性C1上的鄰域。f:U×C∪D→V是一個信息函數(shù),它對一個對象的每一個屬性賦予一個信息值,即?a∈C∪D,x∈U,有f(x,a)∈Va。對含有缺失條件屬性值的對象判定:當(dāng)xi(D)=xj(D)時,根據(jù)定義7判定,如果xi(C0)=xj(C0),δxi(C)=δxj(C),則f(xi,a)=f(xj,a)；否則f(xi,a)≠f(xj,a)。

實(shí)例分析 在不完備鄰域決策系統(tǒng)DS=(U,C,D,V)中,條件屬性集合為C={C1,C2,C3,C4},決策屬性集為D={d1,d2},{C1,C2,C3}為連續(xù)型數(shù)值屬性,{C4}為符號型屬性,下面通過表1的實(shí)例說明。

表1 不完備鄰域決策系統(tǒng)Tab. 1 Incomplete neighborhood decision system

令δ=0.1,k=0.2,因?yàn)閷ο髕1、x5的決策屬性D取值不同,連續(xù)型的屬性值都在鄰域范圍內(nèi),名義型屬性取值相同,也不能視為同一類;因?yàn)閗=0.2,兩個對象在C1、C2、C3、C4屬性中只能有一個屬性取值不同或不在同一鄰域,所以x1、x2屬于同一類,x1與x3、x4不屬于同一類。

針對存在不完備的數(shù)值型和符號型混合數(shù)據(jù)的系統(tǒng),本文結(jié)合可變精度的粗糙集模型,下面給出了基于條件熵的屬性約簡方法。

對于經(jīng)典粗糙集模型,定義3給出了在信息系統(tǒng)中信息熵的統(tǒng)一表示。本文在此基礎(chǔ)上對于鄰域粗糙集模型,給出了可變精度k下信息熵的定義與公式。

定義8 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對象xi在條件屬性C下的鄰域?yàn)棣腃(xi),k為可變精度，則在不完備鄰域決策系統(tǒng)中條件屬性C的信息熵為:

通過定義8的公式可以推出定理1決策屬性D關(guān)于條件屬性C的條件熵的計(jì)算公式。

定理1 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對象xi在條件屬性C下的鄰域?yàn)棣腃(xi),在決策屬性D下的鄰域?yàn)棣腄(xi)，則在不完備鄰域決策系統(tǒng)中決策屬性D關(guān)于條件屬性C的條件熵為:

定義10 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),B?C,對于?a∈C-B,則屬性a相對于屬性集B的重要性計(jì)算方式為:

3 屬性約簡的增量式更新機(jī)制

對象增加時,為有效利用原屬性約簡集結(jié)果,避免算法的重復(fù)計(jì)算,本章首先分析了在不完備鄰域決策系統(tǒng)中,新增對象v后條件熵的變化情況；然后結(jié)合可變精度粗糙集模型的概念,給出了針對不同情況下條件熵的計(jì)算公式。

新增對象v在屬性集B?C上的鄰域δB(v)及其決策類δD(v),其條件熵的變化有4種情況,如圖1所示。

圖1 條件熵的增量式更新機(jī)制Fig. 1 Incremental update mechanism of conditional entropy

1)新增對象v在屬性集B上的鄰域只有其自身無其他對象,且新增對象v的決策類是系統(tǒng)中沒有的;

2)新增對象v在屬性集B上的鄰域只有其自身無其他對象,且新增對象v的決策類是系統(tǒng)中已有的;

3)新增對象v在屬性集B上的鄰域還有其他對象,且新增對象v的決策類是系統(tǒng)中沒有的;

4)新增對象v在屬性集B上的鄰域還有其他對象,且新增對象v的決策類是系統(tǒng)中已有的。

對于上述1)～2)兩種情況,可以利用定理2中的公式得到新的條件熵。

對于上述3)和4)兩種情況,可以利用定理3中的公式得到新的條件熵。

2|δB(v)-δD(v)|)

綜上所述,對于在系統(tǒng)中新增對象v后出現(xiàn)的4種情況均滿足:

2|δB(x)-δD(x)|)

所以由此可得出定理4,該定理滿足不完備鄰域決策系統(tǒng)中對象增量式更新的情況。

2|δB(v)-δD(v)|)

證明 根據(jù)定理2和定理3,顯然同理可證得。

4 增量式屬性約簡方法

4.1 不完備鄰域數(shù)據(jù)的增量式屬性約簡

根據(jù)以上分析,算法的具體描述如下。

輸入 不完備鄰域決策系統(tǒng)DS=(U,C,D,V)的約簡集RED及其條件熵,鄰域半徑δ,可變精度k,新增對象v。

輸出 屬性約簡結(jié)果RED′。

步驟1 初始化RED′=?。

步驟2 分別計(jì)算約簡集RED下對象v的鄰域δRED(v)和對象v的決策類鄰域δD(v),如果δRED(v)-δD(v)≠?,跳轉(zhuǎn)至步驟3；否則跳轉(zhuǎn)至步驟6。

步驟4 計(jì)算新增對象v和δRED(v)-δD(v)所得對象在條件屬性集{C-RED}下的屬性約簡為RED1,令RED′=RED∪RED1。

4.2 算法復(fù)雜度分析和比較

算法表述中|U|代表系統(tǒng)中對象的個數(shù),|C|代表?xiàng)l件屬性的個數(shù),|RED|代表原約簡屬性個數(shù)。對于上述增量式屬性約簡算法的時間復(fù)雜度分析如下：

步驟1 初始化RED′=?的時間復(fù)雜度為O(1)。

步驟2 計(jì)算約簡集RED下對象v的鄰域δRED(v)的時間復(fù)雜度為O(|U||RED|),計(jì)算對象v的決策類鄰域δD(v)的時間復(fù)雜度為O(|U|),所以步驟2的時間復(fù)雜度為O(|U||RED|)。

步驟3 計(jì)算條件屬性集C下對象v的鄰域δC(v)的時間復(fù)雜度為O(|U||C|),所以步驟3的時間復(fù)雜度為O(|U||C|)。

步驟4 計(jì)算新增對象v和δRED(v)-δD(v)所得對象在條件屬性集{C-RED}下的屬性約簡為RED1,設(shè)δRED(v)-δD(v)所得對象為m個,則m個對象計(jì)算δRED(xi)-δD(xi)的時間復(fù)雜度為O(m(|C-RED|)),最壞情況下所得屬性約簡RED1=C-RED,計(jì)算約簡集RED1的時間復(fù)雜度為O(m(|C-RED|2)),最壞情況下當(dāng)m=|U|時,該步的時間復(fù)雜度為O((|U|+1)(|C-RED|2),所以步驟4最壞的時間復(fù)雜度為O((|U|+1)(|C-RED|2)。

4.3 與基于正域約簡算法及啟發(fā)式約簡算法比較

與基于正域約簡算法及基于啟發(fā)式約簡算法相比,本文提出的變精度不完備鄰域系統(tǒng)的增量式屬性約簡算法具有以下優(yōu)點(diǎn):

1)基于的正域?qū)傩约s簡算法及基于啟發(fā)式屬性約簡算法大多針對靜態(tài)的信息數(shù)據(jù),如果用算法簡單重復(fù)進(jìn)行屬性約簡,那勢必會導(dǎo)致時間消耗過高和大量占用系統(tǒng)空間資源,并造成無法實(shí)時更新系統(tǒng)數(shù)據(jù)的問題。本文提出的增量式屬性約簡算法可直接用于新增對象的屬性約簡,并能反向剔除冗余數(shù)據(jù),有效減少了系統(tǒng)資源的消耗量。

2)基于正域?qū)傩约s簡算法及基于啟發(fā)式屬性約簡算法多數(shù)適用于離散型屬性約簡,且較難直接處理含有不完備型混合數(shù)據(jù)。而變精度不完備鄰域系統(tǒng)的增量式屬性約簡算法可直接處理含有不完備的離散型和連續(xù)型混合數(shù)據(jù),并能通過調(diào)節(jié)可變精度,得到數(shù)據(jù)不同層次的信息粒度。

3)變精度不完備鄰域系統(tǒng)的增量式屬性約簡算法是對基于條件熵啟發(fā)式約簡算法的進(jìn)一步擴(kuò)展,本文的屬性約簡算法改進(jìn)了經(jīng)典的條件熵公式,先對新增對象的鄰域進(jìn)行計(jì)算和分析,根據(jù)具體的情況再選擇性地進(jìn)行公式計(jì)算,有效減少了計(jì)算量。

5 實(shí)例分析

以表2中的不完備鄰域決策系統(tǒng)為例，分析本文算法的有效性。設(shè)條件屬性集為{C1,C2,C3,C4}, 決策屬性為{D}。設(shè)置鄰域半徑δ=0.35,即兩對象之間的鄰域半徑小于等于0.35;可變精度k=0.2,即兩個對象在條件屬性集中只能有一個屬性取值不同或不在同一鄰域中;已知該鄰域決策系統(tǒng)的一個約簡集RED={C3,C4}。

表2 不完備鄰域決策系統(tǒng)Tab. 2 Incomplete neighborhood decision system

1)如果新增對象v={0.93,*,0.90,T,4},根據(jù)算法步驟2計(jì)算得δRED(v)-δD(v)=?,則跳轉(zhuǎn)至算法步驟6,輸出RED={C3,C4},算法結(jié)束。這屬于第一種情況:δRED(v)={v},δD(v)={v},原屬性約簡集RED可以區(qū)分新增對象v,屬性約簡結(jié)果保持不變。

2)如果新增對象v={0.95,0.02,0.89,*,3},根據(jù)算法步驟2計(jì)算得δRED(v)-δD(v)=?,則跳轉(zhuǎn)至算法步驟6,輸出RED={C3,C4},算法結(jié)束。這屬于第二種情況:δRED(v)={v},δD(v)={x4,x6,v},原屬性約簡集RED可以區(qū)分新增對象v,屬性約簡結(jié)果保持不變。

3)如果新增對象v={0.35,0.67,0.79,T,4},根據(jù)算法步驟2計(jì)算可得δRED(v)-δD(v)={x5},跳轉(zhuǎn)至步驟3計(jì)算δC(v)={x5,v},因?yàn)棣腃(v)=δRED(v),則跳轉(zhuǎn)至算法步驟6,輸出RED={C3,C4},算法結(jié)束。這屬于第三種情況:δB(v)={x5,v},δD(v)={v},因?yàn)樾略鰧ο髒在條件屬性集C下的鄰域δC(v)等于在原屬性約簡集RED下的鄰域δRED(v),所以原屬性約簡集RED可以區(qū)分新增對象v,屬性約簡結(jié)果保持不變。

然后根據(jù)算法步驟4,計(jì)算新增對象v和δRED(v)-δD(v)所得對象{x1,x4,x5}在條件屬性集{C-RED}下的屬性約簡結(jié)果為RED1={C1}和RED1={C2},令RED′=RED∪RED1,得到新的約簡集{C1,C3,C4}和{C2,C3,C4}。

算法轉(zhuǎn)至步驟6,輸出屬性約簡結(jié)果。因此,按照以上算法步驟, 當(dāng)δ=0.35,可變精度k=0.2時,不完備鄰域決策系統(tǒng)的新增對象后的屬性約簡為{C2,C4}。這屬于第三種情況:δB(v)={x5,v},δD(v)={v},因?yàn)樾略鰧ο髒在條件屬性集C下的鄰域δC(v)不等于在原屬性約簡集RED下的鄰域δRED(v),原屬性約簡集RED不可以區(qū)分新增對象v,則需根據(jù)算法重新計(jì)算屬性約簡。

然后根據(jù)算法步驟4,計(jì)算新增的對象v和δRED(v)-δD(v)所得對象{x7}在條件屬性集{C-RED}下的屬性約簡結(jié)果為RED1={C1},令RED′=RED∪RED1,得到新的約簡集{C1,C3,C4};

算法轉(zhuǎn)至步驟6,輸出屬性約簡結(jié)果。因此,按照以上算法步驟, 當(dāng)δ=0.35,可變精度k=0.2時,不完備鄰域決策系統(tǒng)的新增對象后的屬性約簡為{C1,C3,C4}。此情況屬于屬性約簡更新的第四種情況,則有δB(v)={x3,x6,x7,v},δD(v)={x4,x6,v},原屬性約簡集RED不可以區(qū)分新增對象v,則需根據(jù)算法重新計(jì)算屬性約簡。

通過上述實(shí)例分析,本文算法的最壞時間復(fù)雜度為O((|U|+1)(|C-RED|2)。若采用靜態(tài)的基于條件熵的屬性約簡算法分析不完備鄰域決策系統(tǒng),則算法在增加對象后的時間復(fù)雜度為O(|U+1|2|C|3),可見增量式方法能夠有效地降低算法的時間復(fù)雜度。在存儲空間上,計(jì)算表2不完備鄰域決策系統(tǒng)中數(shù)據(jù),本文算法需42個存儲空間,若采用差別矩陣方法則需196個空間用于存儲鄰域矩陣元素,本文算法占用的空間相對較少。因此,本文算法在計(jì)算效率和存儲空間上較好,且能處理完備的數(shù)值型和符號型混合數(shù)據(jù),具有較好的擴(kuò)展性。

6 實(shí)驗(yàn)分析和比較

為了進(jìn)一步驗(yàn)證本文算法的有效性,從UCI數(shù)據(jù)集中選取了Echocardiogram、Hepatitis、Automobile、Credit、Dermatology五個含有連續(xù)型數(shù)據(jù)和名義型數(shù)據(jù)的混合型不完備數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測試和分析。五個真實(shí)數(shù)據(jù)集的相關(guān)信息描述如表3所示。實(shí)驗(yàn)的測試環(huán)境為:CPU Intel Core i5-4590s (3.0 GHz),內(nèi)存8.0 GB,操作系統(tǒng)為Windows 10,算法編程語言是Python 3.5, 采用的集成開發(fā)環(huán)境為Anaconda 2.6, 采用的開發(fā)工具為PyCharm。

表3 UCI數(shù)據(jù)集描述Tab. 3 Description of UCI data sets

在實(shí)驗(yàn)測試的過程中,將五組數(shù)據(jù)集中的每組數(shù)據(jù)集分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集兩部分。為驗(yàn)證本文算法的有效性和可行性,對每個數(shù)據(jù)集進(jìn)行四次實(shí)驗(yàn)測試和比較。在第一次實(shí)驗(yàn)過程中,取數(shù)據(jù)集的前60%部分作為訓(xùn)練數(shù)據(jù)集,其后10%的部分作為測試數(shù)據(jù)集;后面三次實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)集的規(guī)模以10%為幅度增長。同時,為了進(jìn)一步驗(yàn)證本文算法,將提出的增量式屬性約簡算法和靜態(tài)約簡算法進(jìn)行實(shí)驗(yàn)分析和對比。在實(shí)驗(yàn)過程中,若可變精度k=0.2和鄰域半徑δ=0.2時,對屬性約簡結(jié)果和算法的運(yùn)行時間進(jìn)行實(shí)驗(yàn)分析和對比。

由表4可知,本文提出的增量式屬性約簡和靜態(tài)的屬性約簡方法相比,當(dāng)數(shù)據(jù)集的數(shù)據(jù)量相同時,五個數(shù)據(jù)集的屬性約簡結(jié)果相同。但當(dāng)數(shù)據(jù)量不同時,每個數(shù)據(jù)集得到的屬性約簡的結(jié)果可能存在差異,如對于Echocardiogram和Hepatitis數(shù)據(jù)集來說,在四種不同規(guī)模的數(shù)據(jù)量下,雖然約簡后的屬性個數(shù)相同,但約簡后的屬性子集不完全一致。在Autos數(shù)據(jù)集下,在四種不同規(guī)模的數(shù)據(jù)集下,約簡后的屬性個數(shù)和約簡后的屬性子集相同。對于Credit和Dermatology數(shù)據(jù)集來說,當(dāng)數(shù)據(jù)量為70%和80%時,約簡后的屬性個數(shù)和約簡后的屬性子集相同。同時,當(dāng)數(shù)據(jù)量相同時,屬性約簡的效果與數(shù)據(jù)集相關(guān),例如,當(dāng)數(shù)據(jù)量為100%時,Echocardiogram、Hepatitis、Autos、Credit和Dermatology數(shù)據(jù)集原屬性個數(shù)分別由12、19、25、17和34個約簡至6、7、10、11和13個,分別占原屬性個數(shù)的50.0%、36.8%、40.0%、64.7%和38.2%。由此可知,本文的約簡算法能有效剔除數(shù)據(jù)中的冗余屬性。

表4 增量式與靜態(tài)屬性約簡算法在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對比Tab. 4 Comparison of experimental results of incremental and static attribute reduction algorithms on different data sets

由實(shí)驗(yàn)結(jié)果可知,從算法的執(zhí)行時間上來看,由于本文算法每次僅需處理新增的10%數(shù)據(jù)量,而靜態(tài)的約簡算法需對新增數(shù)據(jù)量的數(shù)據(jù)集進(jìn)行重新計(jì)算,如Echocardiogram數(shù)據(jù)集,在不同數(shù)據(jù)量下,本文算法執(zhí)行時間變化不大,平均耗時為2.98 s,而靜態(tài)的約簡算法執(zhí)行時間隨數(shù)據(jù)量的增多而明顯增長,平均耗時為284.91 s。通過UCI數(shù)據(jù)集中五個真實(shí)的混合型數(shù)據(jù)集的實(shí)驗(yàn)比較和分析,增量式算法在五個數(shù)據(jù)集的平均耗時分別為2.99 s、3.13 s、9.70 s、274.19 s和50.87 s,靜態(tài)算法的平均耗時分別為284.92 s、302.76 s、1 062.23 s、3 510.79 s和667.85 s,由此可知,在執(zhí)行時間方面,增量式屬性約簡算法要顯著好于靜態(tài)的約簡算法。同時通過實(shí)驗(yàn)發(fā)現(xiàn),算法的執(zhí)行時間與數(shù)據(jù)集的實(shí)例個數(shù)、屬性個數(shù)和屬性值類型的分布直接相關(guān)。如Echocardiogram、Hepatitis數(shù)據(jù)集的實(shí)例個數(shù)較少,屬性約簡消耗的時間也較少;而Credit數(shù)據(jù)集的實(shí)例個數(shù)較多,使得屬性約簡花費(fèi)的時間也較多。

綜上所述,通過表4的實(shí)驗(yàn)結(jié)果可知,屬性約簡的結(jié)果與數(shù)據(jù)集的數(shù)據(jù)量大小相關(guān)，屬性約簡所耗費(fèi)的計(jì)算時間隨數(shù)據(jù)量的增大而增多；同時,屬性約簡的時間與數(shù)據(jù)集的特征個數(shù)相關(guān)。由此可知,本文算法可在保持原屬性約簡結(jié)果相同的前提下,顯著地縮短屬性約簡的計(jì)算時間,提高算法的運(yùn)行效率。本文的研究結(jié)果為大規(guī)模不完備混合數(shù)據(jù)的處理和分析提供了一種可借鑒的方法。

7 結(jié)語

針對存在混合型數(shù)據(jù)集的不完備鄰域決策系統(tǒng)中對象增量式屬性約簡問題,本文首先分析了對象增量式更新所引起的條件熵變化情況,然后結(jié)合可變精度的粗糙集概念,構(gòu)造了面向不完備鄰域決策系統(tǒng)的對象增量式更新屬性約簡算法,通過實(shí)例分析和實(shí)驗(yàn)比較可知,該方法能對不完備的數(shù)值型和名義型混合數(shù)據(jù)進(jìn)行屬性約簡,可顯著縮短算法的運(yùn)行時間。由于本文主要是研究對象增加后的屬性約簡增量更新,下一步將在不完備鄰域決策系統(tǒng)中考慮屬性增加后屬性約簡的更新問題。