基于量化限制容差關(guān)系的數(shù)據(jù)填充算法研究

王旭仁 蘇紅莉,2 孟 飛 許祎娜

1(首都師范大學(xué)信息工程學(xué)院 北京 100048) 2(北京國網(wǎng)信通埃森哲信息技術(shù)有限公司 北京 100031)

0 引 言

粗糙集理論[1]目前不僅在數(shù)據(jù)挖掘、數(shù)據(jù)分析領(lǐng)域取得了巨大成功，還涉及到故障分析、知識獲取等領(lǐng)域[2]。這是一種描述不完整數(shù)據(jù)問題非常有用的數(shù)學(xué)方法，尤其是為數(shù)據(jù)挖掘和知識發(fā)現(xiàn)領(lǐng)域提供了不同于常規(guī)數(shù)據(jù)庫方法一種有效而新穎的理論[3]。如何有效、準(zhǔn)確地將粗糙集理論應(yīng)用于不完備信息系統(tǒng)是粗糙集領(lǐng)域的一個研究熱點[4]。

目前常用的ROUSTIDA算法基本思想就是使填充缺失數(shù)據(jù)后產(chǎn)生的分類規(guī)則的支持度應(yīng)該盡可能的高[5]。研究人員基于ROUSTIDA算法又提出了一些改進算法[6-7]。ROUSTIDA算法和改進的算法都是在基于容差關(guān)系模型的基礎(chǔ)上[8]，但在相似對象有屬性值沖突時，這些數(shù)據(jù)填充方法填充效果不理想。因此有學(xué)者提出基于量化容差關(guān)系模型的數(shù)據(jù)填充算法[9-11]。但當(dāng)兩個對象沒有明顯相似的屬性值時可能會被錯誤地判定為同一個容差類。

為了解決以上問題，本文結(jié)合了限制容差關(guān)系和量化容差關(guān)系的特點，提出了一種綜合量化容差關(guān)系和限制容差關(guān)系的數(shù)據(jù)填充方法VLTA。

1 ROUSTID容差關(guān)系算法

1.1 容差關(guān)系和ROUSTIDA算法描述

定義1令不完備信息系統(tǒng)I=(U,C∪D,V,f)，U={x1,x2,…,xn}是論域，C={ai|i=1,2,…,m}是條件屬性集，ai(xj)是樣本xj在屬性ai上的取值，D是決策屬性集。對任何缺少屬性值的子集B?A，容差關(guān)系T可以定義為如公式所示：

?x,y∈U(TB(x,y)??Cj∈B(Cj(x)=Cj(y)=*∨Cj(y)=*))

(1)

M(i,j)表示經(jīng)過擴充的分辨矩陣中第i行第j列的元素，則經(jīng)過擴充的分辨矩陣M定義為：

(2)

式中：i=1,2,…,m；j=1,2,…,n；“*”表示缺失值[12]。

定義2令不完備信息系統(tǒng)I=(U,C∪D,V,f)，C={ai|i=1,2,…,m}是條件屬性集，設(shè)xi∈U，則對象xi的缺失屬性集MASi，對象xi的無差別對象集NSi和信息系統(tǒng)S的缺失對象集MOS可分別定義為[11]：

MASi={ak|ak(xi)=*,k=1,2,…,m}

(3)

NSi={j|TB(xi,xj),i≠j,j=1,2,…,n}

(4)

MOS={i|MASi≠?,i=1,2,…,n}

(5)

ROUSTIDA算法步驟如下：

輸入：不完備信息系統(tǒng)I0=〈U0,C∪D,V,f0〉。

輸出：完備信息系統(tǒng)Ir=〈Ur,C∪D,V,fr〉。

步驟2

2) 產(chǎn)生Ir+1：

步驟3若信息系統(tǒng)中的數(shù)據(jù)仍然存在缺失，可以選取平均填充法或組合填充法進行填充。

步驟4計算結(jié)束。

1.2 ROUSTIDA算法不足

用一個實例說明ROUSTIDA算法的實施過程，不完備信息表如表1所示。x1、x2、x3是對象，a1、a2、a3、a4是四個取值范圍在0到3的屬性，“*”代表缺失的屬性值。

表1 不完備信息表

對象x2的屬性a2需要填充。根據(jù)定義2，x1、x3都是x2的無差別對象，但兩個對象中的a2屬性值不同，存在決策沖突，因此x2的a2屬性值不能通過ROUSTIDA算法填充。x3的缺失屬性不能通過ROUSTIDA算法填充，因為x3的無差別對象集NSi為空。因此從上面實例可以看出，ROUSTIDA算法存在以下不足：

1) 由于ROUSTIDA算法的模型原理簡單，在無差別對象中屬性值存在填充沖突時，此方法填充效果不理想，就必須通過其他方法填充。

解決的辦法之一是使用量化容差關(guān)系和相應(yīng)的算法進行處理。

2 量化容差關(guān)系和VTRIDA算法

2.1 量化容差關(guān)系和VTRIDA算法描述

當(dāng)xi=xj時，Pk(i,j)=1；

否則：

(6)

這樣對容差關(guān)系T(i,j)進行了量化，兩個對象xi、xj的容差關(guān)系可以用在所有條件屬性上相似的聯(lián)合概率來度量：

T(i,j)=∏ak∈CPk(i,j)

(7)

量化容差關(guān)系矩陣M定義為：

(8)

該算法的計算步驟如下所示：

輸入：不完備信息系統(tǒng)I0=〈U0,AT〉。

輸出：完備信息系統(tǒng)Ir=〈Ur,AT〉。

步驟2

1) 生成Ir+1。

(2) 當(dāng)i∈MOSr且?j′,s.t.T(i,j′)=maxT(i,j)則：

步驟3如果信息系統(tǒng)中的缺失值仍然存在，則需要使用其他算法填充數(shù)據(jù)，如平均值填充算法和組合填充算法。

步驟4計算結(jié)束。

2.2 VTRIDA算法討論

針對表1可得到量化容差關(guān)系矩陣，如表2所示。

表2 量化容差關(guān)系矩陣

填充后得到表1的完備信息表，如表3所示。

表3使用VTRIDA算法得到表1的完備信息表

3 基于量化限制容差關(guān)系的數(shù)據(jù)填充算法VLTA

本節(jié)在限制容差關(guān)系基礎(chǔ)上改進了量化容差關(guān)系的描述，提出一種新的數(shù)據(jù)填充算法。

3.1 限制容差關(guān)系

定義4給出一個不完備信息系統(tǒng)I=(U,C∪D,V,f)，B?(C∪D)且滿足PB(x)={b|b∈B∧b(x)≠*}，那么限制容差關(guān)系L可以使用公式來表示[13]：

?x,y∈U×U(LB(x,y)??b∈B(b(x)=b(y)=*)∨((PB(x)∩PB(y)≠?)∧?b∈B((b(x)≠*)∧(b(y)≠*)→(b(x)=b(y)))))

(9)

3.2 改進算法的介紹

一個不完備信息系統(tǒng)I=(U,C∪D,V,f)，B?(C∪D)，且PB(x)={b|b∈B∧b(x)≠*}，量化限制容差關(guān)系矩陣可以由公式描述：

(10)

式中：Pk(i,j)同式(6)。

(11)

輸入：不完備的信息系統(tǒng)I0=〈U0,C∪D〉。

輸出：完備的信息系統(tǒng)Ir=〈Ur,C∪D〉。

步驟2

2) 生成Ir+1：

步驟3如果信息系統(tǒng)中仍然存在缺失值，則需要使用其他算法填充數(shù)據(jù)，例如平均值填充算法和組合填充算法。

步驟4計算結(jié)束。

4 結(jié)論分析

4.1 理論分析

VLTA與ROUSTIDA、VTRIDA算法填充結(jié)果對比

一個不完備信息表如表4所示x1、x2、…、x6是6個對象，a1、a2、a3、a4是四個取值范圍在0到3之間的離散屬性，“*”代表缺失的屬性值。通過ROUSTIDA算法填充后的效果如表5所示，通過VTRIDA算法、VLTA算法填充后的效果分別如表6、表7所示。

表4 不完備信息表

表5 ROUSTIDA填充結(jié)果

表6 VTRIDA的填充結(jié)果

表7 VLTA的填充結(jié)果

通過表5可以發(fā)現(xiàn)x1和x5的一些屬性值不能通過使用ROUSTIDA填充，在此條件下，丟失的數(shù)據(jù)必須使用其他方法處理。

所有丟失的數(shù)據(jù)都可以通過使用VTRIDA、VLTA填充完整，填充結(jié)果如表6、表7所示。兩種算法對表4中的對象x2、…、x6的填充結(jié)果一致。而對象x1(0,*,*,*)，算法VTRIDA使用對象x5(*,2,0,2)進行填充，因為在算法VTRIDA下，根據(jù)式(6)和式(7)的定義，x1和x5的相似概率最大：

這說明VTRIDA算法中，對容差關(guān)系的量化T(i,j)定義不合理，使得屬性值完全不同的兩個對象(例如表4中的x1和x5)具有最高相似度而進行填充，填充的準(zhǔn)確性令人質(zhì)疑。

4.2 實驗分析

將本文提出的VLTA算法部署到基于Spark大數(shù)據(jù)處理平臺，通過算法調(diào)用實現(xiàn)對數(shù)據(jù)的補齊工作。

補齊的數(shù)據(jù)來自公交車和出租車上安裝的采集器，在數(shù)據(jù)采集過程中采集頻率為15秒/次，數(shù)據(jù)量有500 GB。對從公交車和出租車采集的交通數(shù)據(jù)22個屬性里，選取7個相關(guān)性比較強的屬性進行數(shù)據(jù)補齊工作，分別為收集時間、GPS經(jīng)度、GPS緯度、轉(zhuǎn)速、儀表盤速度和瞬時耗油量。其中儀表盤速度和瞬時耗油缺失情況最嚴(yán)重。

為了VLTA與ROUSTIDA、VTRIDA填充結(jié)果對比檢驗準(zhǔn)確性，在原始數(shù)據(jù)中選取沒有丟失的數(shù)據(jù)集，首先通過隨機數(shù)據(jù)生成器生成一組隨機數(shù)，在隨機數(shù)對應(yīng)的位置挖去屬性值造成數(shù)據(jù)缺失的現(xiàn)象，生成不完備信息系統(tǒng)。

在實驗中，處理數(shù)據(jù)缺失率分別為5%和10%。把數(shù)據(jù)填充算法：ROUSTIDA、VTRIDA和VLTA分別應(yīng)用于填充相同的不完備信息系統(tǒng)，平均值填充算法用于填充算法填充后剩余的缺失值。填補正確率使用正確填充的數(shù)據(jù)量和總?cè)笔У臄?shù)據(jù)量的比值來確定。填充正確率的實驗結(jié)果如表8和表9所示。

表8 交通數(shù)據(jù)缺失率為5%實驗填充結(jié)果對比

表9 交通數(shù)據(jù)缺失率為10%實驗填充結(jié)果對比

在不同數(shù)據(jù)集中，分別用三種算法進行填充，數(shù)據(jù)填充準(zhǔn)確率如圖1、圖2所示。

圖1 數(shù)據(jù)缺失率為5%時三種算法的填充準(zhǔn)確率對比

圖2 數(shù)據(jù)缺失率為10%時三種算法的填充準(zhǔn)確率對比

觀察表8發(fā)現(xiàn)，在交通數(shù)據(jù)缺失率為5%時，出租車缺失數(shù)據(jù)填充的正確率最高為90.2%，此時對于同一數(shù)據(jù)集，數(shù)據(jù)填充正確率相比于ROUSTIDA算法提高2.5%，相比于VTRIDA算法提高2%。公交車缺失數(shù)據(jù)填充的正確率最高為85.6%，在同一數(shù)據(jù)集中，數(shù)據(jù)填充正確率相比于ROUSTIDA算法提高2.3%，相比于VTRIDA算法提高0.5%。

通過表9發(fā)現(xiàn)，在交通數(shù)據(jù)缺失率為10%時，出租車缺失數(shù)據(jù)填充的正確率最高為90.1%，此時對于同一數(shù)據(jù)集，數(shù)據(jù)填充正確率相比于ROUSTIDA算法提高2%，相比于VTRIDA算法提高0.9%。公交車缺失數(shù)據(jù)填充的正確率最高為84.3%，在同一數(shù)據(jù)集中，數(shù)據(jù)填充正確率相比于ROUSTIDA算法提高2.1%，相比于VTRIDA算法提高0.6%。

通過圖1和圖2可發(fā)現(xiàn)，在數(shù)據(jù)缺失率為5%和10%的不完備信息系統(tǒng)中，在不同數(shù)據(jù)集下VTLA算法填充結(jié)果的準(zhǔn)確率高于ROUSTIDA算法和VTRIDA算法。

由此可發(fā)現(xiàn)，VTLA算法可以作為數(shù)據(jù)填充的一種工具，并為數(shù)據(jù)挖掘工作之前的數(shù)據(jù)預(yù)處理提供支撐工作。

5 結(jié) 語

本文分析了ROUSTIDA算法和VTRIDA算法的特點，提出了基于量化限制容差關(guān)系的數(shù)據(jù)填充算法VLTA，優(yōu)勢在于解決以下問題：

(1) ROUSTIDA算法在對數(shù)據(jù)補齊時，如果容差對象相同的屬性值存在沖突，則算法無法對當(dāng)前對象的缺失值進行補齊，當(dāng)填充對象無差別對象集為空時，無法對缺失值進行補齊。

(2) VTRIDA算法對容差關(guān)系的量化定義過于機械，以至于屬性值沒有任何相同的兩個對象也有可能是容差對象。

實驗發(fā)現(xiàn)，VLTA算法在數(shù)據(jù)缺失率不同的不完備信息系統(tǒng)中，數(shù)據(jù)填充準(zhǔn)確度高于ROUSTIDA算法和VTRIDA算法。

本文下一步考慮決策屬性值對條件屬性值的概率分布的影響，對算法進行改進，使得新的數(shù)據(jù)填充算法更精確、更科學(xué)、填充后的數(shù)據(jù)更完整。

[1] Pawlak Z. Rough sets[J]. International Journal of Computer & Information Sciences, 1982, 11(5):341-356.

[2] Pawlak Z, Grzymala-Busse J W, Slowinski R, et al. Rough sets[J].Communications of the ACM,1995,38(11):88-95.

[3] 舒文豪. 面向動態(tài)不完備數(shù)據(jù)的特征選擇模型與算法研究[D]. 北京交通大學(xué), 2015.

[4] 張亞萍,陳得寶,侯俊欽,等. 樸素貝葉斯分類算法的改進及應(yīng)用[J].計算機工程與應(yīng)用,2011,47(15):134-137.

[5] 陳家俊, 蘇守寶, 金萍. 一種對象完備度優(yōu)先填補的決策樹規(guī)則提取算法[J]. 計算機應(yīng)用與軟件, 2014,31(5):264-267,294.

[6] 丁春榮, 李龍澍. 基于相似關(guān)系向量的改進ROUSTIDA算法[J]. 計算機工程與應(yīng)用, 2014, 50(13):133-136.

[7] 田樹新.一種基于改進的ROUSTIDA算法的數(shù)據(jù)補齊方法[J].海軍工程大學(xué)學(xué)報,2011,23(5):11-15.

[8] 曹佳韻. 基于ROUSTIDA算法的不完整數(shù)據(jù)處理分析與實現(xiàn)[D]. 東華大學(xué), 2013.

[9] Ding Chun-rong, Li Long-shu. Completing data algorithm based on similarity relation vector[J]. Application Research of Computers, 2013,30(2):383-385.

[10] 王金山, 王磊.基于一種新的量化容差關(guān)系的變精度粗糙集模型[J]. 東華理工大學(xué)學(xué)報(自然科學(xué)版), 2013, 36(1):96-100.

[11] 劉城霞, 何華燦. 廣義相關(guān)性基礎(chǔ)上的量化容差關(guān)系的改進[J]. 北京郵電大學(xué)學(xué)報, 2015, 38(5):28-32.

[12] 武森, 馮小東, 單志廣. 基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補方法[J]. 計算機學(xué)報, 2012, 35(8):1726-1738.

[13] 郭嗣琮, 徐麗, 鄭愛紅. 限制容差關(guān)系的不完備可變粗糙集[J]. 遼寧工程技術(shù)大學(xué)學(xué)報, 2014(7):988-991.