基于屬性約簡的物聯網不完全數據填充算法

陳志奎，楊英達，張清辰，劉 旸

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

0 引言

物聯網數據的不完全性問題日益突出。所謂數據不完全性是指終端工作異常而引起的采集數據全部或部分屬性值缺失。數據不完全性給物聯網的數據融合、數據挖掘等帶來極大困難，嚴重阻礙物聯網數據的應用。因此對物聯網不完全數據進行填充是一個重要課題。

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

針對以上問題，本文提出一種基于屬性約簡的不完全數據填充方法。利用屬性約簡區分數據的重要屬性與非重要屬性，分別采用不同的填充技術對兩類屬性數據進行填充，其中重要屬性個數根據用戶需要設定。

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

基于相似度的方法用來定義相容關系，然后進行分類。但該方法將導致對象相似度值存在大量的零值，因此本文在其求概率乘積的基礎加以改進，定義相似度為概率之和。這樣做的優點是既能保證相似度乘積大的求和相似度也大，同時去掉了很多相似度值是零的非正常值的干擾。

1 相關理論和技術

1.1 粗糙集與粒計算

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

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

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

1.2 冪圖

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

圖1 冪圖

1.3 基于相似度的數據填充方法

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

Pa(x，y):

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

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

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

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

由上面定義可得對象相似度計算公式如下

n代表對象的屬性個數，即對象相似度等于每個屬性相同的概率之和。

2 基于屬性約簡的物聯網不完全數據填充算法

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

圖2 算法總體框架

2.1 改進的基于冪圖的重要屬性搜索算法

輸入:給定不完全信息系統和需要的屬性個數K

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

步驟:

(1)建立一個的搜索圖 G，把 C放在擴展節點表Search中，計算起始節點的知識粒度 g=GD(C)，令minGD=g。

(2)建立一個Searched的已擴展的節點表，初始值為空。

(3)令P=C。

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

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

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

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

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

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

(10)goto Loop。

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

圖3 基于冪圖的屬性約簡算法流程

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

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

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

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

(4)選擇Open表的第一個節點，即Xi，然后對集合的實體進行處理。

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

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

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

(8)goto Loop。

算法流程圖見圖4。

圖4 數據填充流程

3 實驗

采用智能家庭中的數據樣本［10］，應用本文提出的算法進行實例分析如下。

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

C={t，h，l，p，L};D={sensitivity}。詳細數據見表1。

表1 數字家庭數據

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

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

因為Similarity(Rm7，Rm4)的相似度最高，所以取Rm7的humi的值作為Rm4的填充值即缺失值是42。然后處理Rm3的屬性lumi的缺失值，此時計算 {Rm3，Rm4，Rm7，Rm8}中lumi的屬性值出現概率，選擇概率值最大的作為Rm3的缺失值。即Pmax=Plumi=170=2/3，所以對Rm3的lumi值填充為170。

圖5 重要屬性搜索

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

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

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

因為Rm5和Rm9、Rm10的相似度值相同，所以任取其中一個的power值來填充 Rm5的Power值，此處選擇Rm9，即缺失的power值填充值是32.7。

再對Rm5的屬性lumi的缺失值進行填充，此時出現的值只有一個，因此該值出現的概率Pmax=Plumi=180=1，所以該缺失值填180。

實驗分析表明，本算法可以快速的獲取重要屬性，通過實例中對缺失值的填充，體現了重要屬性和非重要屬性的區別，基于相似度的模式比單純的基于概率的方式對缺失值的填充更加合理，這是因為基于相似度的方法綜合考慮了其他屬性對缺失屬性的影響。同時，基于決策屬性劃分的方法把基于概率的填充方法的概率分布重新進行了劃分，使其更有意義 (同一決策類中的屬性相似的概率最大)。

4 結束語

大量終端設備在無人工監控狀態下工作，經常發生損壞，導致其采集的數據中含有大量不完全數據。數據的不完全性給物聯網的數據融合、數據挖掘等帶來極大困難，嚴重阻礙物聯網數據的應用。為此，本文提出一種基于屬性約簡的不完全數據填充方法，對缺失數據進行了填充。方法的核心由兩部分組成:第一是選擇重要屬性，第二是填充缺失值。在重要屬性選擇時采用了基于冪圖的搜索式算法，把重要屬性選擇問題轉化為圖搜索式問題，以直觀形象的方式展現了選擇K個重要屬性的過程。在數據填充時，首先利用決策屬性對U進行劃分，這樣能夠去掉不相關數據的干擾。基于相似度的重要屬性填充方法同時考慮了其他屬性對該屬性的影響，因此填充的值更加科學合理，對非重要屬性缺失值的處理采用的是簡單的概率方式填充，這種方法相對于其他方法將節省計算開銷。

［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和貝葉斯網絡的丟失數據填充算法［J］.計算機工程與應用，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).［胡立花，丁世飛，丁浩.基于啟發式的粗糙集屬性約簡算法 ［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).［黃治國，王端.基于粗糙集的數據約簡方法研究［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］.計算機工程與設計，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］.計算機工程與應用，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).［汪凌，吳杰，黃丹.基于相對可辨識矩陣的決策表屬性約簡算法 ［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］.計算機工程與應用，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］.計算機工程，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).［陳玉明，苗奪謙.基于冪圖的屬性約簡搜索式算法 ［J］.計算機學報，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.