一種改進的ROUSTIDA數據填補方法

關瑩蘇貴斌康熠華

摘 要：針對數據稀疏度大的信息系統提出了一種基于序數屬性相似度的不完備數據分析方法。通過采用差值替代等值的方式改進可辨識矩陣，從而實現填補稀疏度較大的信息系統的目的。彌補了原算法對于某些缺失值不能填充的情況，改善了其它改進方法對于序數屬性處理不準確的缺點，并通過實驗證明了改進后的方法可以更精確更有效地填充缺失值。

關鍵詞關鍵詞：不完備數據分析方法；可辨識矩陣；序數屬性；粗糙集

DOIDOI：10.11907/rjdk.162011

中圖分類號：TP301

文獻標識碼：A 文章編號文章編號：16727800（2016）011001203

基金項目基金項目：

作者簡介作者簡介：關瑩（1993-），女，遼寧丹東人，內蒙古師范大學計算機與信息工程學院碩士研究生，研究方向為軟件工程、數據挖掘；蘇貴斌（1968-），男，黑龍江望奎人，內蒙古師范大學網絡技術學院副教授、碩士生導師，研究方向為軟件工程、數據挖掘；康熠華（1992-），女，內蒙古呼和浩特人，內蒙古師范大學計算機與信息工程學院碩士研究生，研究方向為軟件工程、數據挖掘。

0 引言

計算機與網絡信息技術的飛速發展，使得各領域的數據和信息急劇增加。在數據與信息系統不確定性日益顯著，且采集到的數據往往包含著噪聲甚至不完整的情況下，粗糙集理論應運而生。粗糙集理論是波蘭數學家Z.Pawlak[1]于1982年提出的一種數據分析理論，作為一種研究不精確、不確定性知識的數學工具，粗糙集理論越來越受到重視。經過30多年的發展，該理論已經得到廣泛應用，成為人工智能領域的研究熱點。它的優點是無需提供除問題所需處理的數據集合之外的任何先驗信息。

基于粗糙集理論的ROUSTIDA算法是一種處理不完備信息系統缺失值的常用算法，它利用可辨識矩陣找到與有缺失值的對象相似度最高的對象的屬性值進行填充[2]。該算法的基本思想是：遺失數據值的填充應該使完備化后的信息系統產生的分類規則具有盡可能高的支持度，產生的規則盡可能集中[3]。由于算法本身具有一些缺陷，因此本文對該算法進行了改進，提出了一種面向序數屬性信息系統的不完備數據方法，使得填充結果更準確、更有效。

1 ROUSTIDA算法

1.1 理論基礎

定義1：令信息系統為S=，A={ai|i=1，…，m}是屬性集，U={x1，x2，…，xn}是論域，ai（xj）是樣本xj在屬性ai上的取值。M （i， j）表示經過擴充的可辨識矩陣中第i行j列的元素，則經過擴充的可辨識矩陣M定義為[45]

1.2 ROUSTIDA算法描述

ROUSTIDA算法步驟如下：

當計算到S1后，算法滿足結束條件，不再往下計算。因此S1為使用ROUSTIDA算法填充后的最終結果。此時信息系統中仍有部分缺失值沒有被填充，且按照原算法采用平均值或最高頻率值來進行填充會產生很大的誤差，因此本文提出了改進方案。

2 改進的ROUSTIDA算法

2.1 算法描述

ROUSTIDA算法本身具有一些局限性。在算法的步驟2中，當有缺失屬性的對象與任何對象都不相似，或與多個對象都相似且與之相似對象的相應屬性值互不相等時，ROUSTIDA算法無法進行填充。并且，其對產生的噪聲數據沒有分辨能力，易受到噪聲數據的干擾從而影響填充效果。在算法填充完成之前要對可擴充辨識矩陣、遺失對象集和遺失屬性集進行多次更新，因此產生了大量的過渡數據，增加了算法的時間復雜度。本文提出的改進方法主要集中在以下兩個方面：（1）根據序數屬性之間的相似度進行改進。傳統的ROUSTIDA算法忽略了序數屬性之間的相似度，只有兩個對象的各個屬性完全相同才能進行填充。那么當對象的屬性為序數屬性時，屬性級別越多，滿足原算法條件的對象越少，也就越難以填充。實際上，在評分系統中，大部分屬性級別數目為5，有的甚至為10，此時原算法的填充效率將大大降低?？梢钥紤]，在尋找無差別對象時，適當放寬標準，使各屬性級別的差值保持小于等于1（此差值根據信息系統實際情況進行改變），最后用總差值最小，也即最相似的對象的相應屬性值進行填充。并且原始的ROUSTIDA算法以及現有改進方法都沒有考慮到序數屬性各級別之間的關系，序數屬性的屬性值之間也有一定的相似性，屬性值越相近，兩個對象就越相似。為了使用改進算法，重新定義可辨識矩陣M。定義3：令信息系統為S=，A={ai|i=1，…，m}是屬性集，U={x1，x2，…，xn}是論域，ai（xj）是樣本xj在屬性ai上的取值。M （i， j）表示經過擴充的可辨識矩陣中第i行j列的元素，則經過擴充的可辨識矩陣M定義為：M（i，j）={ak|ak∈A∧|ak（xi）-ak（xj）|>1∧ak（xi）≠*∧ak（xj）≠*}其中，i，j=1，…，n；“*”表示缺失值。（2）針對原算法步驟2不能處理的情況進行改進。改進后的算法考慮找出與目標對象屬性最相似的對象屬性值進行填充。分別計算NS中的各個對象與目標對象屬性值的總差值，總差值越小，對象之間的相似度越高。為了使用改進算法，作以下補充定義：定義4：令信息系統為S=，A={ai|i=1，…，m}是屬性集，對任意xi，定義Ni={p|ap（xi）≠*，i=1...n}為對象xi屬性不為空的集合。Nij={p|ap（xi）≠*∧ap（xj）≠*，i，j=1...n}為對象xi和xj屬性都不為空的集合。定義5：令信息系統為S=，A={ai|i=1，…，m}是屬性集，定義dj=∑p∈Ni|ap（xj）-ap（xi）|為用戶xj與xi屬性值的總差值。改進的ROUSTIDA算法如下：改進后的可辨識矩陣M：

2.2 實驗分析

對表1實施改進后的ROUSITIDA算法結果如表3所示。

改進后的算法針對原算法不能處理的幾種情況，分別提出了相應的解決策略，使得最終得到的信息系統更加完備化，填補的屬性值更加準確。該算法主要針對具有序數屬性的信息系統，考慮到了各屬性值之間的相似性，擴充了原算法的適用范圍，彌補了采用最多出現值或平均值填補缺失值帶來的誤差。

3 結語

本文對基于粗糙集的不完備數據分析方法（ROUSTIDA）進行了改進，在計算可辨識矩陣M時采用差值代替等值的方式，拓寬了對無差別對象的選擇，大大提高了算法的填充效率，同時也具備一定的噪聲數據分辨能力。實驗證明，改進后的算法對于具有序數屬性的信息系統有很好的填充能力。

參考文獻：

[1] PAWLAK Z.Rough sets[J].International Journal of Computer Information Science，1982（11）：341356.

[2] 王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社，2001：4697.

[3] 田樹新，吳曉平，王紅霞.一種基于改進的ROUSTIDA算法的數據補齊方法[J].海軍工程大學學報，2011，23（5）：1115.

[4] 丁春榮，李龍澍.基于相似關系向量的改進ROUSTIDA算法[J].計算機工程與應用，2014，50（13）：133136.

[5] 段鵬，莊紅林，何磊，等.不完備數據分析方法（ROUSTIDA）的改進算法[J].計算機工程與設計，2009，30（7）：16811684.

（責任編輯：孫 娟）