基于量化限制容差關系的數據填充算法研究

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

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

0 引 言

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

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

為了解決以上問題，本文結合了限制容差關系和量化容差關系的特點，提出了一種綜合量化容差關系和限制容差關系的數據填充方法VLTA。

1 ROUSTID容差關系算法

1.1 容差關系和ROUSTIDA算法描述

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

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

(1)

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

(2)

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

定義2令不完備信息系統I=(U,C∪D,V,f)，C={ai|i=1,2,…,m}是條件屬性集，設xi∈U，則對象xi的缺失屬性集MASi，對象xi的無差別對象集NSi和信息系統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算法步驟如下：

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

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

步驟2

2) 產生Ir+1：

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

步驟4計算結束。

1.2 ROUSTIDA算法不足

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

表1 不完備信息表

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

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

解決的辦法之一是使用量化容差關系和相應的算法進行處理。

2 量化容差關系和VTRIDA算法

2.1 量化容差關系和VTRIDA算法描述

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

否則：

(6)

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

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

(7)

量化容差關系矩陣M定義為：

(8)

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

輸入：不完備信息系統I0=〈U0,AT〉。

輸出：完備信息系統Ir=〈Ur,AT〉。

步驟2

1) 生成Ir+1。

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

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

步驟4計算結束。

2.2 VTRIDA算法討論

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

表2 量化容差關系矩陣

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

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

3 基于量化限制容差關系的數據填充算法VLTA

本節在限制容差關系基礎上改進了量化容差關系的描述，提出一種新的數據填充算法。

3.1 限制容差關系

定義4給出一個不完備信息系統I=(U,C∪D,V,f)，B?(C∪D)且滿足PB(x)={b|b∈B∧b(x)≠*}，那么限制容差關系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 改進算法的介紹

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

(10)

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

(11)

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

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

步驟2

2) 生成Ir+1：

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

步驟4計算結束。

4 結論分析

4.1 理論分析

VLTA與ROUSTIDA、VTRIDA算法填充結果對比

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

表4 不完備信息表

表5 ROUSTIDA填充結果

表6 VTRIDA的填充結果

表7 VLTA的填充結果

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

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

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

4.2 實驗分析

將本文提出的VLTA算法部署到基于Spark大數據處理平臺，通過算法調用實現對數據的補齊工作。

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

為了VLTA與ROUSTIDA、VTRIDA填充結果對比檢驗準確性，在原始數據中選取沒有丟失的數據集，首先通過隨機數據生成器生成一組隨機數，在隨機數對應的位置挖去屬性值造成數據缺失的現象，生成不完備信息系統。

在實驗中，處理數據缺失率分別為5%和10%。把數據填充算法：ROUSTIDA、VTRIDA和VLTA分別應用于填充相同的不完備信息系統，平均值填充算法用于填充算法填充后剩余的缺失值。填補正確率使用正確填充的數據量和總缺失的數據量的比值來確定。填充正確率的實驗結果如表8和表9所示。

表8 交通數據缺失率為5%實驗填充結果對比

表9 交通數據缺失率為10%實驗填充結果對比

在不同數據集中，分別用三種算法進行填充，數據填充準確率如圖1、圖2所示。

圖1 數據缺失率為5%時三種算法的填充準確率對比

圖2 數據缺失率為10%時三種算法的填充準確率對比

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

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

通過圖1和圖2可發現，在數據缺失率為5%和10%的不完備信息系統中，在不同數據集下VTLA算法填充結果的準確率高于ROUSTIDA算法和VTRIDA算法。

由此可發現，VTLA算法可以作為數據填充的一種工具，并為數據挖掘工作之前的數據預處理提供支撐工作。

5 結 語

本文分析了ROUSTIDA算法和VTRIDA算法的特點，提出了基于量化限制容差關系的數據填充算法VLTA，優勢在于解決以下問題：

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

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

實驗發現，VLTA算法在數據缺失率不同的不完備信息系統中，數據填充準確度高于ROUSTIDA算法和VTRIDA算法。

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

[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] 舒文豪. 面向動態不完備數據的特征選擇模型與算法研究[D]. 北京交通大學, 2015.

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

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

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

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

[8] 曹佳韻. 基于ROUSTIDA算法的不完整數據處理分析與實現[D]. 東華大學, 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] 王金山, 王磊.基于一種新的量化容差關系的變精度粗糙集模型[J]. 東華理工大學學報(自然科學版), 2013, 36(1):96-100.

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

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

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