遼寧石化職業(yè)技術學院 楊 迪
一種基于核值的R O U S T I D A算法
遼寧石化職業(yè)技術學院 楊 迪
無論是ROUSTISA算法還是其修正算法,都具有反應速度快、運算簡單、對于相似或相同決策處理能力較強等優(yōu)點。并且修正后的算法還可避免不相容決策,具有較好的實用價值。但是從屬性約簡的過程可知,并非任何一個數(shù)據(jù)對于決策的作用都一樣,在基于粗糙集的屬性約簡過程中,核值才是最有用的數(shù)據(jù),然而上述算法將所有數(shù)據(jù)同等對待,并未體現(xiàn)出核值的重要性。
核值;ROUSTIDA算法;可辨識矩陣
該算法是以可辨識矩陣為基礎,基本流程如下:
步驟一核值化:
步驟三:
步驟四決策表中對象獨立性的判斷:
步驟五如果信息還有遺失值,可用平均值等方法填充;
步驟六結束。
對于整個算法的實現(xiàn),通過實驗將更易于理解。算法實際上是要實現(xiàn)“將不完備的數(shù)據(jù)矩陣進行數(shù)據(jù)填補,最終得到一個完整的數(shù)據(jù)矩陣”這一功能。以下我將通過一個簡單的例子來逐步介紹該算法的實現(xiàn)過程。
程序實現(xiàn)過程如下:
第一步,程序要有一個輸入矩陣的過程。由外部輸入一個不完備的矩陣S1,假設輸入的數(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即可。假設我們選擇的是下述矩陣,如表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行是否不可分辨)。
如上例的辨析結果如如表8所示。
由此可見X1行與X2行為不可分辨關系,所以,我們將X1行與X2行中的空值元素替換為其對應的非空元素值,得S6’,進行了一次填補。填補結果如如表9所示:
表9 初次填補
表1 0 填補完成表
對S6’重復第三步內容,直到循環(huán)結束。如果循環(huán)結束后仍有“*”值存在,則可利用均值法或最大頻率法等來進行填補。
第四步:將初始矩陣S1中的缺失元素*替換填補為矩陣S7中對應位置的非空元素。至此,對不完備矩陣的填補結束。程序最終輸出一個完備的矩陣,如表10所示。
整個算法的實現(xiàn)就是通過上述過程來體現(xiàn)的。既證明了算法的優(yōu)勢,在保留原有數(shù)據(jù)的同時,有效的填補了缺失信息,避免了決策沖突;同時也發(fā)現(xiàn)對于程序設計所帶來的時間復雜度和空間復雜度較高,使得程序的運行效率偏低。
[1]饒晶晶.基于ROUSTIDA算法改進的RFID數(shù)據(jù)清洗技術[J].信息與電腦:理論版,2016 (8):93-94.
[2]關瑩,蘇貴斌,康熠華.一種改進的ROUSTIDA數(shù)據(jù)填補方法[J].軟件導刊,2016,15(11):12-14.
楊迪(1980—),男,滿族,遼寧錦州人,碩士,講師,主要從事應用數(shù)學及圖論的研究。