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

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

0 引 言

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

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

為了解決以上問(wèn)題，本文結(jié)合了限制容差關(guān)系和量化容差關(guān)系的特點(diǎ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是決策屬性集。對(duì)任何缺少屬性值的子集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)過(guò)擴(kuò)充的分辨矩陣中第i行第j列的元素，則經(jīng)過(guò)擴(kuò)充的分辨矩陣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，則對(duì)象xi的缺失屬性集MASi，對(duì)象xi的無(wú)差別對(duì)象集NSi和信息系統(tǒng)S的缺失對(duì)象集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ù)仍然存在缺失，可以選取平均填充法或組合填充法進(jìn)行填充。

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

1.2 ROUSTIDA算法不足

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

表1 不完備信息表

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

1) 由于ROUSTIDA算法的模型原理簡(jiǎn)單，在無(wú)差別對(duì)象中屬性值存在填充沖突時(shí)，此方法填充效果不理想，就必須通過(guò)其他方法填充。

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

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

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

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

否則：

(6)

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

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

(7)

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

(8)

該算法的計(jì)算步驟如下所示：

輸入：不完備信息系統(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計(jì)算結(jié)束。

2.2 VTRIDA算法討論

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

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

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

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

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

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

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

定義4給出一個(gè)不完備信息系統(tǒng)I=(U,C∪D,V,f)，B?(C∪D)且滿足PB(x)={b|b∈B∧b(x)≠*}，那么限制容差關(guān)系L可以使用公式來(lái)表示[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 改進(jìn)算法的介紹

一個(gè)不完備信息系統(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計(jì)算結(jié)束。

4 結(jié)論分析

4.1 理論分析

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

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

表4 不完備信息表

表5 ROUSTIDA填充結(jié)果

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

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

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

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

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

4.2 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

通過(guò)圖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é) 語(yǔ)

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

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

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

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

本文下一步考慮決策屬性值對(duì)條件屬性值的概率分布的影響，對(duì)算法進(jìn)行改進(jìn)，使得新的數(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] 舒文豪. 面向動(dòng)態(tài)不完備數(shù)據(jù)的特征選擇模型與算法研究[D]. 北京交通大學(xué), 2015.

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

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

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

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

[8] 曹佳韻. 基于ROUSTIDA算法的不完整數(shù)據(jù)處理分析與實(shí)現(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é)報(bào)(自然科學(xué)版), 2013, 36(1):96-100.

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

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

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