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

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

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

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

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

核值；ROUSTIDA算法；可辨識矩陣

一、基于核值的ROUSTIDA算法

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

步驟一核值化：

步驟三：

步驟四決策表中對象獨立性的判斷：

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

步驟六結(jié)束。

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

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

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

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

表1 初始矩陣

表2 待補矩陣

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

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

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

表3 分析矩陣

表4 改寫分析矩陣

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

得到了S2和S3之后，開始對S3進行分析，求S3的秩（即看S3是幾階的），將其化為階梯矩陣，得到S3’。

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

表5 階梯矩陣

表6 核值矩陣

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

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

表7 合并矩陣

表8 辨析表

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

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

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

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

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

表9 初次填補

表1 0 填補完成表

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

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

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

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

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

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