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

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

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

1 基礎(chǔ)理論

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

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

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

1)?x,y∈U, ΔA(x,y)≥0, 當(dāng)ΔA(x,y)=0時(shí), ?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)。

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

對(duì)于符號(hào)型的數(shù)據(jù)中,可定義:

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

定義2[15]將鄰域等價(jià)關(guān)系擴(kuò)展到符號(hào)型、連續(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)系滿足自反性,但不一定滿足對(duì)稱性和傳遞性,因?yàn)槿我鈱?duì)象與其自身是不可分辨的,所以任何等價(jià)關(guān)系均滿足自反性。在這里放寬了對(duì)稱性和傳遞性的限制,擴(kuò)展了應(yīng)用范圍。

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

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

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

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

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

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

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

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

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

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

性質(zhì)1 在不完備鄰域決策系統(tǒng)DS=(U,C,D,V)中,對(duì)象xi,xj∈U,xi(D)為對(duì)象xi在決策屬性D上的取值,xi(C0)為對(duì)象xi在符號(hào)型條件屬性C0上的取值,δxi(C1)為對(duì)象xi在連續(xù)型屬性C1上的鄰域。f:U×C∪D→V是一個(gè)信息函數(shù),它對(duì)一個(gè)對(duì)象的每一個(gè)屬性賦予一個(gè)信息值,即?a∈C∪D,x∈U,有f(x,a)∈Va。對(duì)含有缺失條件屬性值的對(duì)象判定:當(dāng)xi(D)=xj(D)時(shí),根據(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}為符號(hào)型屬性,下面通過表1的實(shí)例說明。

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

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

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

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

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

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

定理1 給定DS=(U,C,D,V)是不完備鄰域決策系統(tǒng),對(duì)象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,對(duì)于?a∈C-B,則屬性a相對(duì)于屬性集B的重要性計(jì)算方式為:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 增量式屬性約簡(jiǎn)方法

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

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

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

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

步驟1 初始化RED′=?。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)例分析

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

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

1)如果新增對(duì)象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},原屬性約簡(jiǎn)集RED可以區(qū)分新增對(duì)象v,屬性約簡(jiǎn)結(jié)果保持不變。

2)如果新增對(duì)象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},原屬性約簡(jiǎn)集RED可以區(qū)分新增對(duì)象v,屬性約簡(jiǎn)結(jié)果保持不變。

3)如果新增對(duì)象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)樾略鰧?duì)象v在條件屬性集C下的鄰域δC(v)等于在原屬性約簡(jiǎn)集RED下的鄰域δRED(v),所以原屬性約簡(jiǎn)集RED可以區(qū)分新增對(duì)象v,屬性約簡(jiǎn)結(jié)果保持不變。

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

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

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

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

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

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

為了進(jìn)一步驗(yàn)證本文算法的有效性,從UCI數(shù)據(jù)集中選取了Echocardiogram、Hepatitis、Automobile、Credit、Dermatology五個(gè)含有連續(xù)型數(shù)據(jù)和名義型數(shù)據(jù)的混合型不完備數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)測(cè)試和分析。五個(gè)真實(shí)數(shù)據(jù)集的相關(guān)信息描述如表3所示。實(shí)驗(yàn)的測(cè)試環(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)測(cè)試的過程中,將五組數(shù)據(jù)集中的每組數(shù)據(jù)集分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集兩部分。為驗(yàn)證本文算法的有效性和可行性,對(duì)每個(gè)數(shù)據(jù)集進(jìn)行四次實(shí)驗(yàn)測(cè)試和比較。在第一次實(shí)驗(yàn)過程中,取數(shù)據(jù)集的前60%部分作為訓(xùn)練數(shù)據(jù)集,其后10%的部分作為測(cè)試數(shù)據(jù)集;后面三次實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)集的規(guī)模以10%為幅度增長(zhǎng)。同時(shí),為了進(jìn)一步驗(yàn)證本文算法,將提出的增量式屬性約簡(jiǎn)算法和靜態(tài)約簡(jiǎn)算法進(jìn)行實(shí)驗(yàn)分析和對(duì)比。在實(shí)驗(yàn)過程中,若可變精度k=0.2和鄰域半徑δ=0.2時(shí),對(duì)屬性約簡(jiǎn)結(jié)果和算法的運(yùn)行時(shí)間進(jìn)行實(shí)驗(yàn)分析和對(duì)比。

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

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

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

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

7 結(jié)語

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