基于屬性約簡(jiǎn)的物聯(lián)網(wǎng)不完全數(shù)據(jù)填充算法

陳志奎，楊英達(dá)，張清辰，劉 旸

(1.大連理工大學(xué)軟件學(xué)院，遼寧大連116621;2.西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶400715)

0 引言

物聯(lián)網(wǎng)數(shù)據(jù)的不完全性問題日益突出。所謂數(shù)據(jù)不完全性是指終端工作異常而引起的采集數(shù)據(jù)全部或部分屬性值缺失。數(shù)據(jù)不完全性給物聯(lián)網(wǎng)的數(shù)據(jù)融合、數(shù)據(jù)挖掘等帶來(lái)極大困難，嚴(yán)重阻礙物聯(lián)網(wǎng)數(shù)據(jù)的應(yīng)用。因此對(duì)物聯(lián)網(wǎng)不完全數(shù)據(jù)進(jìn)行填充是一個(gè)重要課題。

常用的不完全數(shù)據(jù)填充算法主要有基于決策樹的填充方法、基于馬氏距離的填充方法及基于EM和貝葉斯網(wǎng)絡(luò)的數(shù)據(jù)填充方法［1］等。傳統(tǒng)的數(shù)據(jù)填充算法對(duì)不完全數(shù)據(jù)的所有屬性采用相同的填充方法，沒有考慮到與用戶的交互性。在對(duì)物聯(lián)網(wǎng)的數(shù)據(jù)進(jìn)行融合與挖掘等應(yīng)用中，未必需要數(shù)據(jù)的全部屬性。因此傳統(tǒng)的數(shù)據(jù)填充算法在對(duì)物聯(lián)網(wǎng)不完全數(shù)據(jù)進(jìn)行填充時(shí)效率低下，不適合填充物聯(lián)網(wǎng)的不完全數(shù)據(jù)。

針對(duì)以上問題，本文提出一種基于屬性約簡(jiǎn)的不完全數(shù)據(jù)填充方法。利用屬性約簡(jiǎn)區(qū)分?jǐn)?shù)據(jù)的重要屬性與非重要屬性，分別采用不同的填充技術(shù)對(duì)兩類屬性數(shù)據(jù)進(jìn)行填充，其中重要屬性個(gè)數(shù)根據(jù)用戶需要設(shè)定。

常用的屬性約簡(jiǎn)方法包括基于啟發(fā)式算法的屬性約簡(jiǎn)算法［2-3］、基于決策表的屬性約簡(jiǎn)算法［4-6］以及基于相容矩陣［7-8］等屬性約簡(jiǎn)算法。其中，基于冪圖的屬性約簡(jiǎn)搜索算法［9］通過(guò)冪圖的方式求約簡(jiǎn)，把屬性約簡(jiǎn)的計(jì)算問題轉(zhuǎn)化為圖搜索式問題，以直觀形象的方式展現(xiàn)了屬性約簡(jiǎn)的過(guò)程，為屬性約簡(jiǎn)問題的求解提供了一條新的途徑。但是基于冪圖的方法只能求完全信息系統(tǒng)的屬性約簡(jiǎn)，因此本文給出了不完全信息系統(tǒng)劃分的定義，經(jīng)過(guò)轉(zhuǎn)換之后，可以把不完全信息系統(tǒng)看作是完全信息系統(tǒng)，進(jìn)而用基于冪圖的思想進(jìn)行屬性約簡(jiǎn)。

基于相似度的方法用來(lái)定義相容關(guān)系，然后進(jìn)行分類。但該方法將導(dǎo)致對(duì)象相似度值存在大量的零值，因此本文在其求概率乘積的基礎(chǔ)加以改進(jìn)，定義相似度為概率之和。這樣做的優(yōu)點(diǎn)是既能保證相似度乘積大的求和相似度也大，同時(shí)去掉了很多相似度值是零的非正常值的干擾。

1 相關(guān)理論和技術(shù)

1.1 粗糙集與粒計(jì)算

定義1 IS=(U，A，V，f)是一個(gè)信息系統(tǒng)，其中U是論域，也就是研究對(duì)象的集合，A是屬性集合同時(shí)A≠Φ，屬性集A包含兩種屬性，分別是條件屬性和決策屬性，條件屬性集合用C表示，決策屬性集合用D表示，集合A、C、D之間滿足如下關(guān)系:A=C∪D且C∩D=Φ。V是U中的對(duì)象在屬性A下的取值集合，f是信息函數(shù)，用來(lái)把論域中的對(duì)象和屬性與取值做映射，即當(dāng)x∈U，a∈C時(shí)，用f(x，a)=* 表示f(x，a)的函數(shù)值是未知的。這種帶有未知函數(shù)值的信息系統(tǒng)叫做不完全信息系統(tǒng)，用IIS表示。

定義2 對(duì)于一個(gè)不完信息系統(tǒng)IIS=(U，A，V，f)， B C，DIV(B)定義了一個(gè)二元不可區(qū)分關(guān)系:a)=*)and(f(x，a)=*)≠(f(y，a)=Vya)}，×代表笛卡爾乘積。在DIV(B)中，對(duì)象在屬性a下的取值中，任何未知的值與已知的值不同，任意兩個(gè)未知的值也不同。那么U/DIV(B)構(gòu)成了論域U的一個(gè)劃分，也稱為U的一個(gè)知識(shí)粒。

定義3 設(shè) IIS=(U，A，V，f)是不完全信息系統(tǒng)，U/DIV(C)={U1，U2，…，Un}，C是條件屬性集，屬性集C的知識(shí)粒度定義是

1.2 冪圖

定義4 設(shè)Power(C)是條件屬性集合C冪集，給定有向圖G，Power(C)中的元素是圖G的頂點(diǎn)，圖G中的邊滿足下面條件: X，Y，Z∈Power(C)，如果|X|－1=|Y|=|Z|+1且(X∩Z) Y (X∪Z)，那么存在X到Y(jié)，Y到Z的有向邊，稱此有向圖G是C的冪圖。

圖1 冪圖

1.3 基于相似度的數(shù)據(jù)填充方法

定義5 給定IIS=(U，A，V，f)，x∈ U，且y∈ U;A=C∪D，a∈C;C是條件屬性，D是決策屬性。Va是屬性a的值域，那么實(shí)體x，y在屬性a下取值相同的概率定義如下:

Pa(x，y):

(1)1/|Va|，f(x，a)和 f(y，a)不同時(shí)為 *;

(2)1/|Va|2，f(x，a)和 f(y，a)同時(shí)為 *;

(3)1，f(x，a)=f(y，a);

(4)0，f(x，a)和f(y，a)都不為* 且不等;

由上面定義可得對(duì)象相似度計(jì)算公式如下

n代表對(duì)象的屬性個(gè)數(shù)，即對(duì)象相似度等于每個(gè)屬性相同的概率之和。

2 基于屬性約簡(jiǎn)的物聯(lián)網(wǎng)不完全數(shù)據(jù)填充算法

結(jié)合物聯(lián)網(wǎng)數(shù)據(jù)特點(diǎn)，本文提出一種基于屬性約簡(jiǎn)的物聯(lián)網(wǎng)不完全數(shù)據(jù)填充算法，算法首先利用改進(jìn)的基于冪圖的重要屬性搜索算法抽取數(shù)據(jù)的重要屬性，然后利用改進(jìn)的基于相似度的方法填充重要屬性中的缺失值，最后，算法利用基于概率的方法填充非重要屬性的缺失值。算法整體框架如圖2所示。

圖2 算法總體框架

2.1 改進(jìn)的基于冪圖的重要屬性搜索算法

輸入:給定不完全信息系統(tǒng)和需要的屬性個(gè)數(shù)K

輸出:K個(gè)屬性的屬性集RED(K)

步驟:

(1)建立一個(gè)的搜索圖 G，把 C放在擴(kuò)展節(jié)點(diǎn)表Search中，計(jì)算起始節(jié)點(diǎn)的知識(shí)粒度 g=GD(C)，令minGD=g。

(2)建立一個(gè)Searched的已擴(kuò)展的節(jié)點(diǎn)表，初始值為空。

(3)令P=C。

(4)Loop:如果Search為空，則退出循環(huán)。

(5)選擇Search表的第一個(gè)節(jié)點(diǎn)，把它從該表移除并放到Searched表中，稱此節(jié)點(diǎn)為n。

(6)按照冪圖擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成后繼結(jié)點(diǎn)的臨時(shí)集合TEMP，把這些成員作為后繼結(jié)點(diǎn)添加入冪圖G中。

(7)令P∈TEMP，如果|P|＜K，break。

(8)對(duì)沒有在G中出現(xiàn)過(guò)的TEMP成員，設(shè)置一個(gè)指向n的指針，計(jì)算TEMP中屬性集合的粒度，如果存在P∈TEMP，GD(P)=minGD(TEMP)， 把 大 于 minGD(TEMP)的加入到Searched表，其他的加入Search表。

(9)按某個(gè)啟發(fā)式或者任意方式重排Search表。

(10)goto Loop。

(11)比較Search表中獲取的包含K個(gè)屬性的屬性集粒度的大小，選擇小粒度的屬性集使其等于RED(K)。算法流程見圖3。

圖3 基于冪圖的屬性約簡(jiǎn)算法流程

2.2 基于相似度的重要屬性填充

(1)對(duì)U用決策屬性D進(jìn)行劃分，得到U/D={X1，X2，…，Xn}。

(2)把U/D放到Open表中。

(3)loop:如果Open表為空，則退出循環(huán)。

(4)選擇Open表的第一個(gè)節(jié)點(diǎn)，即Xi，然后對(duì)集合的實(shí)體進(jìn)行處理。

(5)如果Xi中的實(shí)體x的屬性a屬于RED(K)，則采用基于相似度的方法對(duì)不完全屬性值進(jìn)行填充。

(6)如果Xi中的實(shí)體x的屬性a不屬于RED(K)，則采用在Xi中實(shí)體的a屬性值中出現(xiàn)概率最大的進(jìn)行不完全屬性值的填充。

(7)處理完Xi中的所有實(shí)體后，把處理后的Xi從Open表移除，移到Closed表中。

(8)goto Loop。

算法流程圖見圖4。

圖4 數(shù)據(jù)填充流程

3 實(shí)驗(yàn)

采用智能家庭中的數(shù)據(jù)樣本［10］，應(yīng)用本文提出的算法進(jìn)行實(shí)例分析如下。

設(shè)IIS=(U，A，V，f)，A=C∪ D，U={Rm1，Rm2，…， Rm10}， C= {temp， humi， lumi， power，location}，C中的條件屬性可簡(jiǎn)寫為

C={t，h，l，p，L};D={sensitivity}。詳細(xì)數(shù)據(jù)見表1。

表1 數(shù)字家庭數(shù)據(jù)

設(shè)要獲取的重要屬性個(gè)數(shù)是3個(gè)，那么算法的執(zhí)行首先采用基于冪圖的搜索式算法，圖3展示的是搜索的過(guò)程，其采用的是廣度優(yōu)先搜索。大括號(hào)中包含的是屬性，小括號(hào)中的值是該節(jié)點(diǎn)屬性集合的粒度值。紅色框標(biāo)注的是每一層不在進(jìn)行搜索的節(jié)點(diǎn)，通過(guò)2.1算法的第八步去掉了冪圖中重復(fù)的邊，即虛線連接的上層與下層的邊在處理時(shí)不需要重復(fù)計(jì)算。因此搜索完全部包含3個(gè)元素的節(jié)點(diǎn)即找到了所有符合要求的保留三個(gè)屬性同時(shí)粒度最小的3個(gè)屬性。在圖5中可以看出，{t，h，p}、{t，l，p}、{h，l，p}三個(gè)節(jié)點(diǎn)都是符合要求的屬性組合，可以任取其中一個(gè)或者基于某種啟發(fā)式算法選擇一個(gè)做為重要屬性，在本例中選擇第一個(gè)做為重要屬性，即RED(3)={t，h，p}。然后基于決策屬性對(duì)U進(jìn)行劃分即:U/D={{Rm1，Rm2，Rm6}， {Rm3，Rm4，Rm7，Rm8}， {Rm5，Rm9，Rm10}}。然后對(duì)每一個(gè)劃分中的元素進(jìn)行處理。因?yàn)榧蟵Rm1，Rm2，Rm6}中不包含未知屬性值，所以不用做任何處理。繼續(xù)處理集合 {Rm3，Rm4，Rm7，Rm8}，此時(shí)Rm3和Rm4含有未知屬性。首先處理重要屬性的缺失值，即屬性humi的值，此時(shí)由對(duì)象相似度公式計(jì)算相似度

Similarity(Rm3，Rm4)=0+1/2+0=1/2

Similarity(Rm7，Rm4)=0+1/2+1=3/2

Similarity(Rm8，Rm4)=0+1/2+0=1/2

因?yàn)镾imilarity(Rm7，Rm4)的相似度最高，所以取Rm7的humi的值作為Rm4的填充值即缺失值是42。然后處理Rm3的屬性lumi的缺失值，此時(shí)計(jì)算 {Rm3，Rm4，Rm7，Rm8}中l(wèi)umi的屬性值出現(xiàn)概率，選擇概率值最大的作為Rm3的缺失值。即Pmax=Plumi=170=2/3，所以對(duì)Rm3的lumi值填充為170。

圖5 重要屬性搜索

處理完后處理集合 {Rm5，Rm9，Rm10}。首先處理重要屬性power的缺失值。由相似度計(jì)算公式計(jì)算Rm5和Rm9、Rm10的相似度

Similarity(Rm5，Rm9)=0+1+1=2

Similarity(Rm5，Rm10)=1+0+1=2

因?yàn)镽m5和Rm9、Rm10的相似度值相同，所以任取其中一個(gè)的power值來(lái)填充 Rm5的Power值，此處選擇Rm9，即缺失的power值填充值是32.7。

再對(duì)Rm5的屬性lumi的缺失值進(jìn)行填充，此時(shí)出現(xiàn)的值只有一個(gè)，因此該值出現(xiàn)的概率Pmax=Plumi=180=1，所以該缺失值填180。

實(shí)驗(yàn)分析表明，本算法可以快速的獲取重要屬性，通過(guò)實(shí)例中對(duì)缺失值的填充，體現(xiàn)了重要屬性和非重要屬性的區(qū)別，基于相似度的模式比單純的基于概率的方式對(duì)缺失值的填充更加合理，這是因?yàn)榛谙嗨贫鹊姆椒ňC合考慮了其他屬性對(duì)缺失屬性的影響。同時(shí)，基于決策屬性劃分的方法把基于概率的填充方法的概率分布重新進(jìn)行了劃分，使其更有意義 (同一決策類中的屬性相似的概率最大)。

4 結(jié)束語(yǔ)

大量終端設(shè)備在無(wú)人工監(jiān)控狀態(tài)下工作，經(jīng)常發(fā)生損壞，導(dǎo)致其采集的數(shù)據(jù)中含有大量不完全數(shù)據(jù)。數(shù)據(jù)的不完全性給物聯(lián)網(wǎng)的數(shù)據(jù)融合、數(shù)據(jù)挖掘等帶來(lái)極大困難，嚴(yán)重阻礙物聯(lián)網(wǎng)數(shù)據(jù)的應(yīng)用。為此，本文提出一種基于屬性約簡(jiǎn)的不完全數(shù)據(jù)填充方法，對(duì)缺失數(shù)據(jù)進(jìn)行了填充。方法的核心由兩部分組成:第一是選擇重要屬性，第二是填充缺失值。在重要屬性選擇時(shí)采用了基于冪圖的搜索式算法，把重要屬性選擇問題轉(zhuǎn)化為圖搜索式問題，以直觀形象的方式展現(xiàn)了選擇K個(gè)重要屬性的過(guò)程。在數(shù)據(jù)填充時(shí)，首先利用決策屬性對(duì)U進(jìn)行劃分，這樣能夠去掉不相關(guān)數(shù)據(jù)的干擾?；谙嗨贫鹊闹匾獙傩蕴畛浞椒ㄍ瑫r(shí)考慮了其他屬性對(duì)該屬性的影響，因此填充的值更加科學(xué)合理，對(duì)非重要屬性缺失值的處理采用的是簡(jiǎn)單的概率方式填充，這種方法相對(duì)于其他方法將節(jié)省計(jì)算開銷。

［1］LI Hong，EMMMANUEL Amani，LIPing，et al.Imputation algorithm of missing values bas-ed on EM and Bayesian network ［J］.Computer Engineering and Application，2012，46(5):123-125(in Chinese).［李宏，阿瑪尼，李平，等.基于EM和貝葉斯網(wǎng)絡(luò)的丟失數(shù)據(jù)填充算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(5):123-125.］

［2］HU Lihua，DING Shifei，DING Hao.Research on heuristic attributes reduction algorithm of rough sets［J］.Computer Engineering and Design，2011，32(4):1438-1440(in Chinese).［胡立花，丁世飛，丁浩.基于啟發(fā)式的粗糙集屬性約簡(jiǎn)算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2011，32(4):1438-1440.］

［3］HUANG Zhiguo，WANG Duan.Study on data reduction algorithm based on rough set［J］.Computer Engneering and Design，2009，30(18)，4284-4287(in Chinese).［黃治國(guó)，王端.基于粗糙集的數(shù)據(jù)約簡(jiǎn)方法研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(18):4284-4287.］

［4］CHEN fengjuan.Methods for calculating core attributes of inconsistence decision table ［J］.Computer Engineering and Design，2012，33(3):1187-1191(in Chinese).［陳鳳娟.不相容決策表求核方法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33(3):1187-1191.］

［5］GE Hao，YANG Chuanjian，LI Longshu.Ef-ficient algorithm for computing core attri-butes［J］.Computer Engineering and Application，2012，46(26):138-141(in Chinese).［葛浩，楊傳健，李龍澍.一種高效的核屬性求解方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(26):138-141.］

［6］WANG Ling，WU Jie，HUANG Dan.Attribute reduction algorithm for decision table based on relative discernibility matrix ［J］.Computer Engineering and Design，2012，31(11):2536-2538(in Chinese).［汪凌，吳杰，黃丹.基于相對(duì)可辨識(shí)矩陣的決策表屬性約簡(jiǎn)算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(11):2536-2538.］

［7］RUAN Shen，XU Zhangyan，WANG Wei，et al.Improved tolerance matrix attribute reduction algorithm ［J］.Computer Engineering and Application，2011，47(32):49-51(in Chinese).［阮慎，徐章艷，王煒，等.改進(jìn)的相容矩陣屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(32):49-51.］

［8］HAN Zhidong，WANG Zhiliang，GAO Jing，et al.Improved attribute reduction algorithm based on tolerance matrix［J］.Computer Engineering，2010，36(20):25-27(in Chinese).［韓志東，王志良，高靜，等.基于相容矩陣的改進(jìn)屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)工程，2010，36(20):25-27.］

［9］CHEN Yuming，MIAO Duoqian.Searching algorithm for attributes reduction based on power gragh［J］.Chinese Journal of Computers，2009，32(8):1486-1492(in Chinese).［陳玉明，苗奪謙.基于冪圖的屬性約簡(jiǎn)搜索式算法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32(8):1486-1492.］

［10］LIU Yang，CHEN Zhikui，WANG Haozhe，et al.An architecture of data pro-cessing using deluge computing in internet of things［C］//Dalian，China:IEEE Internatio-nal Conferences on Internet of Things，and Cyber，Physical and Social Computing.2011:692-697.