基于粗糙集理論的不完備信息系統中知識約簡的研究

摘要：本文基于不完備信息系統，以知識獲取為目標，數學研究工具選擇粗糙集理論，對不完備信息系統中的各種拓展粗糙集模型進行了研討，重點是其中的知識約簡算法。

關鍵詞：不完備信息系統;粗糙集;知識約簡

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）18-0295-02

Abstract： In this paper， for the purpose of knowledge acquisition in incomplete information systems， various extended rough set models in incomplete information systems are studied with rough set theory as a mathematical tool， with emphasis on the knowledge reduction algorithm.

Key words： Incomplete Information System; Rough Set; Knowledge Reduction

隨著大數據時代的悄然而至，各行各業，各個領域，調查數據表明：決策的形成，相比較于經驗和直覺，更依賴于數據與分析。數據挖掘技術是數理統計分析應用的延伸和發展，假如人們利用數據庫的方式從被動的查詢變成主動發現知識的話，概率論和數理統計這一古老的學科可以從數據中歸納知識，而數據挖掘技術提供理論基礎[2]。數據挖掘（Data Mining），又稱數據庫中的知識發現（KDD），是目前最先進的數據資源分析技術，它可以從大量的數據中及時有效地提取隱含其中未知的、有用的、不一般的信息和知識，用以對決策活動進行支持[14]。粗糙集是數據挖掘中統計方法的一種，分類的意義是在已有數據集的基礎上學會一個分類函數或構造出一個分類模型，該模型或函數能夠把訓練集中的數據記錄映射到給定類別中的某一個，從而可以應用于數據預測。粗糙集（Rough Sets）理論是波蘭Pawlak Z教授在1982年提出的一種可以能夠有效定量分析并處理不精確、不一致、不完備信息在復雜系統中對象相似性約簡辦法，能比較客觀地形容和處理事件的不確定性[1]。粗糙集理論為空間數據的屬性剖析和知識發現開拓了一條新途徑，可用于空間數據庫屬性表的一致性分析、屬性的重要性、屬性依賴、屬性表簡化、最小決策和分類算法生成等。粗糙集理論與其他知識發現算法相結合可以在空間數據庫中數據不確定的情況下獲取多種知識[15]。

1 不完備信息系統

定義1 一個知識表達系統[3]，即信息系統S，可表達為二元組，即S=（U，AT）。當中，U表示對象的非空有限集合，稱之為論域;AT則表示所有屬性的集合。[?]a[∈]AT，Va表示屬性a的值域，即有a（x） [∈]Va（[?]x[∈]U），此處a（x）表示對象x在屬性a上的取值。在信息系統S中，若[?]x[∈]U，x在屬性a（a[∈]AT）上的取值未知，則稱信息系統S為一個不完備信息系統[10]。

在不完備信息系統中，根據粗糙集理論的研究成果來看，可將未知屬性值分為兩種，即遺漏型和缺席型。此處僅思考遺漏型未知屬性值，表明未知屬性值實際上是確實存在的，只是因為各種緣由，目前未能監測到該值，這種遺漏型未知屬性值可被記為a（x）=*。[9]

當數據集存在缺失值時，建模過程中就容易出現報錯的情況，缺失值分析是數據分析過程中重要的一步，包括缺失值檢測和缺失值處理。在R語言中，常用的缺失值分析函數如表1所示。

現在通過一個簡單的實例來演示這幾個函數的應用，要求檢驗出數據集score中的缺失值，并刪除score中含有缺失值的行。

2 算法思路描述

知識約簡是粗糙集重要研究內容，表示在原信息系統分類或決策能力保證不變條件下，將條件屬性中的冗余屬性和不相關的屬性刪除掉，使得決策表中知識表示可簡化而又不丟失決策表中重要信息。[15]通過屬性約簡能取得比原始屬性少得多的約簡集，產生更加簡潔知識的規則[3]。針對含有屬性空值的不完備信息系統，汪凌[5，10]等人提出：引入相容屬性矩陣與決策屬性矩陣[10]的概念，提出在相容關系下基于矩陣的不完備信息系統規則獲取算法，為大規模數據集的規則獲取提供了一種新的思路[5，10]。

圖1? 不完備信息決策系統大數據集的規則獲取方法

不完備信息決策系統DS=，條件屬性集合是C，決策屬性集合是D，相容屬性矩陣與決策矩陣的生成是執行整個算法的基礎[10，13]。首先，生成屬性的|U|×|U|階相容屬性矩陣或決策屬性矩陣，需要比較|U|×（|U|-1）/2次，時間復雜度為O（|U|2）。然后，從這兩個屬性矩陣中提取一階決策規則時，需要按位去比較兩個矩陣相應位置上的元素值，時間復雜度為O（|U|2）。最后，從一階相容矩陣兩兩相交求二階相容矩陣，需要計算次數為2|C|-1，二階相容矩陣的時間復雜度是O（2|C|）[10，13]，每個條件屬性相容矩陣都要跟決策屬性矩陣進行兩兩相交的運算，時間復雜度為O（|U|2）。計算量的增長相對于對象個數是多項式級的，相對于屬性個數是指數級模式[10，13]。本算法的優勢是將復雜的提取過程轉變成對簡單0，1矩陣的操作，而不是對象集的處理，減少了矩陣計算量，大大提高了算法的效率。

3 結束語

此算法通過計算相容屬性矩陣與決策屬性矩陣，在提取規則時減少了矩陣生成的比較次數，降低了矩陣的占用空間，通過比較向量大小可快速求出全部決策規則集，大大提高了規則獲取效率。[10]

參考文獻：

[1] Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[2] 羅森林，馬俊，潘麗敏.數據挖掘理論與技術[M].北京：電子工業出版社，2013.

[3] 董威.粗糙集理論及其數據挖掘應用[M].沈陽：東北大學出版社，2009.

[4] 張良均，謝佳標，楊坦，肖剛.R語言與數據挖掘[M].北京：機械工業出版社，2016.

[5] 汪凌.基于粗糙集的不確定信息知識發現及在城市交通管理中的應用研究[D].西南交通大學博士論文，2011.6.

[6] Pang-Ning Tan，Michael Steinbach，Vipin Kumar.Introduction to Data Mining[M].北京：人民郵電出版社，2006.

[7] 王添，姜麟，米允龍.海量數據下不完備信息系統的知識約簡算法[J].計算機技術與發展，2015 （1）：137-142.

[8] 李長清，張燕蘭.不完備信息系統下基于分辨率的屬性約簡算法[J].海南師范大學學報（自然科學版），2015（12）：359-361.

[9] 馬興斌，鞠恒榮，楊習貝，宋晶晶.不完備信息系統中多重代價決策粗糙集[J].南京大學學報（自然科學），2015 （3）：335-342.

[10] 汪凌.不完備決策系統規則獲取的相容矩陣算法[J].計算機工程與應用，2015，51（1）：130-133.

[11] 莫京蘭，朱廣生，呂躍進.廣義不完備序值信息系統中的知識約簡[J].小型微型計算機系統，2015（12）：2736-2739.

[12] 張福炎，孫志揮.大學計算機信息技術教程（第6版）[M]..南京大學出版社，2013.

[13] 汪凌. 基于相容矩陣計算的不完備決策系統規則獲取算法. 第六屆ABB杯全國自動化系統工程師論文大賽論文集，2013（11）.

[14] 袁鴻燕.基于數據挖掘與知識發現在決策模型中的應用研究[J].電腦知識與技術，2013 （12）：8212-8214.

[15] 丁衛平，陳森博，王杰華，管致錦. 基于云計算的多層量子精英屬性協同約簡算法[J].四川大學學報（工程科學版），2015 （11）：97-103.

【通聯編輯：王力】