遼寧石化職業(yè)技術(shù)學(xué)院 楊 迪

一種基于核值的R O U S T I D A算法

遼寧石化職業(yè)技術(shù)學(xué)院 楊 迪

無(wú)論是ROUSTISA算法還是其修正算法，都具有反應(yīng)速度快、運(yùn)算簡(jiǎn)單、對(duì)于相似或相同決策處理能力較強(qiáng)等優(yōu)點(diǎn)。并且修正后的算法還可避免不相容決策，具有較好的實(shí)用價(jià)值。但是從屬性約簡(jiǎn)的過(guò)程可知，并非任何一個(gè)數(shù)據(jù)對(duì)于決策的作用都一樣，在基于粗糙集的屬性約簡(jiǎn)過(guò)程中，核值才是最有用的數(shù)據(jù)，然而上述算法將所有數(shù)據(jù)同等對(duì)待，并未體現(xiàn)出核值的重要性。

核值；ROUSTIDA算法；可辨識(shí)矩陣

一、基于核值的ROUSTIDA算法

該算法是以可辨識(shí)矩陣為基礎(chǔ)，基本流程如下：

步驟一核值化：

步驟三：

步驟四決策表中對(duì)象獨(dú)立性的判斷：

步驟五如果信息還有遺失值，可用平均值等方法填充；

步驟六結(jié)束。

二、基于核值的ROUSTIDA算法實(shí)現(xiàn)過(guò)程

對(duì)于整個(gè)算法的實(shí)現(xiàn)，通過(guò)實(shí)驗(yàn)將更易于理解。算法實(shí)際上是要實(shí)現(xiàn)“將不完備的數(shù)據(jù)矩陣進(jìn)行數(shù)據(jù)填補(bǔ)，最終得到一個(gè)完整的數(shù)據(jù)矩陣”這一功能。以下我將通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)逐步介紹該算法的實(shí)現(xiàn)過(guò)程。

程序?qū)崿F(xiàn)過(guò)程如下：

第一步，程序要有一個(gè)輸入矩陣的過(guò)程。由外部輸入一個(gè)不完備的矩陣S1，假設(shè)輸入的數(shù)據(jù)如表1所示：（*表示為缺失的數(shù)據(jù)）

表1 初始矩陣

表2 待補(bǔ)矩陣

第二步，要分析、處理數(shù)據(jù)，目的是要按照要求，將不完備信息系統(tǒng)分離成其極大完備子系統(tǒng)和待補(bǔ)系統(tǒng)。

首先要得到一個(gè)待補(bǔ)矩陣S2（即保留所有空值*所在的行和列的數(shù)據(jù),其余的數(shù)據(jù)均用*來(lái)表示），和一個(gè)去掉空值*所在的行和列后所得的分析矩陣S3，劃掉的數(shù)據(jù)用*表示，S3就是用來(lái)確定極大完備矩陣的。

仍以上面的矩陣為例，所得的S2和S3如表2所示：

表3 分析矩陣

表4 改寫(xiě)分析矩陣

為方便對(duì)S3求秩，也可將S3寫(xiě)成下面的形式，如表4所示。

得到了S2和S3之后，開(kāi)始對(duì)S3進(jìn)行分析，求S3的秩（即看S3是幾階的），將其化為階梯矩陣，得到S3’。

如上例分析，所得的S3’的矩陣如表5所示。

表5 階梯矩陣

表6 核值矩陣

即所得的矩陣為2階矩陣。據(jù)此，對(duì)S3求得極大完備矩陣S4。我們只需隨機(jī)選擇其中的一個(gè)極大完備矩陣作為核值矩陣S5即可。假設(shè)我們選擇的是下述矩陣，如表6所示。

然后，將S5與S2合并，得到一個(gè)新的矩陣S6。

表7 合并矩陣

表8 辨析表

至此，我們便得到了一個(gè)新的不完備信息系統(tǒng)，而此信息系統(tǒng)就是基于核值的信息系統(tǒng)。接下來(lái)將以此信息系統(tǒng)為填補(bǔ)對(duì)象，來(lái)進(jìn)行后續(xù)的操作。

第三步：填補(bǔ)數(shù)據(jù)。

對(duì)所得矩陣S6中的缺失項(xiàng)進(jìn)行填補(bǔ)（通過(guò)循環(huán)比較S6中的任意兩行i和j,看i行與j行是否不可分辨）。

如上例的辨析結(jié)果如如表8所示。

由此可見(jiàn)X1行與X2行為不可分辨關(guān)系，所以，我們將X1行與X2行中的空值元素替換為其對(duì)應(yīng)的非空元素值，得S6’，進(jìn)行了一次填補(bǔ)。填補(bǔ)結(jié)果如如表9所示：

表9 初次填補(bǔ)

表1 0 填補(bǔ)完成表

對(duì)S6’重復(fù)第三步內(nèi)容，直到循環(huán)結(jié)束。如果循環(huán)結(jié)束后仍有“*”值存在，則可利用均值法或最大頻率法等來(lái)進(jìn)行填補(bǔ)。

第四步：將初始矩陣S1中的缺失元素*替換填補(bǔ)為矩陣S7中對(duì)應(yīng)位置的非空元素。至此，對(duì)不完備矩陣的填補(bǔ)結(jié)束。程序最終輸出一個(gè)完備的矩陣，如表10所示。

整個(gè)算法的實(shí)現(xiàn)就是通過(guò)上述過(guò)程來(lái)體現(xiàn)的。既證明了算法的優(yōu)勢(shì)，在保留原有數(shù)據(jù)的同時(shí)，有效的填補(bǔ)了缺失信息，避免了決策沖突；同時(shí)也發(fā)現(xiàn)對(duì)于程序設(shè)計(jì)所帶來(lái)的時(shí)間復(fù)雜度和空間復(fù)雜度較高，使得程序的運(yùn)行效率偏低。

[1]饒晶晶．基于ROUSTIDA算法改進(jìn)的RFID數(shù)據(jù)清洗技術(shù)[J]．信息與電腦：理論版,2016 (8)：93-94．

[2]關(guān)瑩,蘇貴斌,康熠華．一種改進(jìn)的ROUSTIDA數(shù)據(jù)填補(bǔ)方法[J]．軟件導(dǎo)刊,2016,15(11)：12-14．

楊迪（1980—），男，滿族，遼寧錦州人，碩士，講師，主要從事應(yīng)用數(shù)學(xué)及圖論的研究。