一種改進(jìn)的ROUSTIDA數(shù)據(jù)填補(bǔ)方法

關(guān)瑩蘇貴斌康熠華

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

關(guān)鍵詞關(guān)鍵詞：不完備數(shù)據(jù)分析方法；可辨識(shí)矩陣；序數(shù)屬性；粗糙集

DOIDOI：10.11907/rjdk.162011

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011001203

基金項(xiàng)目基金項(xiàng)目：

作者簡(jiǎn)介作者簡(jiǎn)介：關(guān)瑩（1993-），女，遼寧丹東人，內(nèi)蒙古師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院碩士研究生，研究方向?yàn)檐浖こ?、?shù)據(jù)挖掘；蘇貴斌（1968-），男，黑龍江望奎人，內(nèi)蒙古師范大學(xué)網(wǎng)絡(luò)技術(shù)學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)檐浖こ?、?shù)據(jù)挖掘；康熠華（1992-），女，內(nèi)蒙古呼和浩特人，內(nèi)蒙古師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院碩士研究生，研究方向?yàn)檐浖こ?、?shù)據(jù)挖掘。

0 引言

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

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

1 ROUSTIDA算法

1.1 理論基礎(chǔ)

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

1.2 ROUSTIDA算法描述

ROUSTIDA算法步驟如下：

當(dāng)計(jì)算到S1后，算法滿足結(jié)束條件，不再往下計(jì)算。因此S1為使用ROUSTIDA算法填充后的最終結(jié)果。此時(shí)信息系統(tǒng)中仍有部分缺失值沒有被填充，且按照原算法采用平均值或最高頻率值來(lái)進(jìn)行填充會(huì)產(chǎn)生很大的誤差，因此本文提出了改進(jìn)方案。

2 改進(jìn)的ROUSTIDA算法

2.1 算法描述

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

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

對(duì)表1實(shí)施改進(jìn)后的ROUSITIDA算法結(jié)果如表3所示。

改進(jìn)后的算法針對(duì)原算法不能處理的幾種情況，分別提出了相應(yīng)的解決策略，使得最終得到的信息系統(tǒng)更加完備化，填補(bǔ)的屬性值更加準(zhǔn)確。該算法主要針對(duì)具有序數(shù)屬性的信息系統(tǒng)，考慮到了各屬性值之間的相似性，擴(kuò)充了原算法的適用范圍，彌補(bǔ)了采用最多出現(xiàn)值或平均值填補(bǔ)缺失值帶來(lái)的誤差。

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

[2] 王國(guó)胤.Rough集理論與知識(shí)獲取[M].西安：西安交通大學(xué)出版社，2001：4697.

[3] 田樹新，吳曉平，王紅霞.一種基于改進(jìn)的ROUSTIDA算法的數(shù)據(jù)補(bǔ)齊方法[J].海軍工程大學(xué)學(xué)報(bào)，2011，23（5）：1115.

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

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

（責(zé)任編輯：孫 娟）