變精度下不完備混合數據的增量式屬性約簡方法

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

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

0 引言

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

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

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

1 基礎理論

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

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

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

1)?x,y∈U, ΔA(x,y)≥0, 當Δ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)。

對于連續型的數據,采用歐氏距離度量:

對于符號型的數據中,可定義:

當δ=0時,變為經典粗糙集模型。

定義2[15]將鄰域等價關系擴展到符號型、連續型和缺失型等未知屬性共存下的不完備模糊系統,可得到以下廣義鄰域關系:

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

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

*∪a(y)=*}

廣義鄰域關系滿足自反性,但不一定滿足對稱性和傳遞性,因為任意對象與其自身是不可分辨的,所以任何等價關系均滿足自反性。在這里放寬了對稱性和傳遞性的限制,擴展了應用范圍。

信息熵作為一種度量信息的不確定性的有效方法,實現對信息的量化度量。梁吉業等在文獻[16]給出了信息系統在經典粗糙集計算模型下信息熵的統一表示:

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

2 可變精度的屬性約簡計算模型

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

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

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

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

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

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

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

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

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

表1 不完備鄰域決策系統Tab. 1 Incomplete neighborhood decision system

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

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

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

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

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

定理1 給定DS=(U,C,D,V)是不完備鄰域決策系統,對象xi在條件屬性C下的鄰域為δC(xi),在決策屬性D下的鄰域為δD(xi)，則在不完備鄰域決策系統中決策屬性D關于條件屬性C的條件熵為:

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

3 屬性約簡的增量式更新機制

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

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

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

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

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

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

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

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

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

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

綜上所述,對于在系統中新增對象v后出現的4種情況均滿足:

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

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

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

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

4 增量式屬性約簡方法

4.1 不完備鄰域數據的增量式屬性約簡

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

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

輸出 屬性約簡結果RED′。

步驟1 初始化RED′=?。

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

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

4.2 算法復雜度分析和比較

算法表述中|U|代表系統中對象的個數,|C|代表條件屬性的個數,|RED|代表原約簡屬性個數。對于上述增量式屬性約簡算法的時間復雜度分析如下：

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

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

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

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

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

與基于正域約簡算法及基于啟發式約簡算法相比,本文提出的變精度不完備鄰域系統的增量式屬性約簡算法具有以下優點:

1)基于的正域屬性約簡算法及基于啟發式屬性約簡算法大多針對靜態的信息數據,如果用算法簡單重復進行屬性約簡,那勢必會導致時間消耗過高和大量占用系統空間資源,并造成無法實時更新系統數據的問題。本文提出的增量式屬性約簡算法可直接用于新增對象的屬性約簡,并能反向剔除冗余數據,有效減少了系統資源的消耗量。

2)基于正域屬性約簡算法及基于啟發式屬性約簡算法多數適用于離散型屬性約簡,且較難直接處理含有不完備型混合數據。而變精度不完備鄰域系統的增量式屬性約簡算法可直接處理含有不完備的離散型和連續型混合數據,并能通過調節可變精度,得到數據不同層次的信息粒度。

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

5 實例分析

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

表2 不完備鄰域決策系統Tab. 2 Incomplete neighborhood decision system

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

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

3)如果新增對象v={0.35,0.67,0.79,T,4},根據算法步驟2計算可得δRED(v)-δD(v)={x5},跳轉至步驟3計算δC(v)={x5,v},因為δC(v)=δRED(v),則跳轉至算法步驟6,輸出RED={C3,C4},算法結束。這屬于第三種情況:δB(v)={x5,v},δD(v)={v},因為新增對象v在條件屬性集C下的鄰域δC(v)等于在原屬性約簡集RED下的鄰域δRED(v),所以原屬性約簡集RED可以區分新增對象v,屬性約簡結果保持不變。

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

算法轉至步驟6,輸出屬性約簡結果。因此,按照以上算法步驟, 當δ=0.35,可變精度k=0.2時,不完備鄰域決策系統的新增對象后的屬性約簡為{C2,C4}。這屬于第三種情況:δB(v)={x5,v},δD(v)={v},因為新增對象v在條件屬性集C下的鄰域δC(v)不等于在原屬性約簡集RED下的鄰域δRED(v),原屬性約簡集RED不可以區分新增對象v,則需根據算法重新計算屬性約簡。

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

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

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

6 實驗分析和比較

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

表3 UCI數據集描述Tab. 3 Description of UCI data sets

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

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

表4 增量式與靜態屬性約簡算法在不同數據集上的實驗結果對比Tab. 4 Comparison of experimental results of incremental and static attribute reduction algorithms on different data sets

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

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

7 結語

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