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

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

關(guān)鍵詞：不完備信息系統(tǒng);粗糙集;知識約簡

中圖分類號：TP393? ? ? ? 文獻標(biāo)識碼：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

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

1 不完備信息系統(tǒng)

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

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

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

現(xiàn)在通過一個簡單的實例來演示這幾個函數(shù)的應(yīng)用，要求檢驗出數(shù)據(jù)集score中的缺失值，并刪除score中含有缺失值的行。

2 算法思路描述

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

圖1? 不完備信息決策系統(tǒng)大數(shù)據(jù)集的規(guī)則獲取方法

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

3 結(jié)束語

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

參考文獻：

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

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

[3] 董威.粗糙集理論及其數(shù)據(jù)挖掘應(yīng)用[M].沈陽：東北大學(xué)出版社，2009.

[4] 張良均，謝佳標(biāo)，楊坦，肖剛.R語言與數(shù)據(jù)挖掘[M].北京：機械工業(yè)出版社，2016.

[5] 汪凌.基于粗糙集的不確定信息知識發(fā)現(xiàn)及在城市交通管理中的應(yīng)用研究[D].西南交通大學(xué)博士論文，2011.6.

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

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

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

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

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

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

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

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

[14] 袁鴻燕.基于數(shù)據(jù)挖掘與知識發(fā)現(xiàn)在決策模型中的應(yīng)用研究[J].電腦知識與技術(shù)，2013 （12）：8212-8214.

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

【通聯(lián)編輯：王力】