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

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

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

中圖分類號(hào)：TP393? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

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

2 算法思路描述

知識(shí)約簡(jiǎn)是粗糙集重要研究?jī)?nèi)容，表示在原信息系統(tǒng)分類或決策能力保證不變條件下，將條件屬性中的冗余屬性和不相關(guān)的屬性刪除掉，使得決策表中知識(shí)表示可簡(jiǎn)化而又不丟失決策表中重要信息。[15]通過(guò)屬性約簡(jiǎn)能取得比原始屬性少得多的約簡(jiǎn)集，產(chǎn)生更加簡(jiǎn)潔知識(shí)的規(guī)則[3]。針對(duì)含有屬性空值的不完備信息系統(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í)行整個(gè)算法的基礎(chǔ)[10，13]。首先，生成屬性的|U|×|U|階相容屬性矩陣或決策屬性矩陣，需要比較|U|×（|U|-1）/2次，時(shí)間復(fù)雜度為O（|U|2）。然后，從這兩個(gè)屬性矩陣中提取一階決策規(guī)則時(shí)，需要按位去比較兩個(gè)矩陣相應(yīng)位置上的元素值，時(shí)間復(fù)雜度為O（|U|2）。最后，從一階相容矩陣兩兩相交求二階相容矩陣，需要計(jì)算次數(shù)為2|C|-1，二階相容矩陣的時(shí)間復(fù)雜度是O（2|C|）[10，13]，每個(gè)條件屬性相容矩陣都要跟決策屬性矩陣進(jìn)行兩兩相交的運(yùn)算，時(shí)間復(fù)雜度為O（|U|2）。計(jì)算量的增長(zhǎng)相對(duì)于對(duì)象個(gè)數(shù)是多項(xiàng)式級(jí)的，相對(duì)于屬性個(gè)數(shù)是指數(shù)級(jí)模式[10，13]。本算法的優(yōu)勢(shì)是將復(fù)雜的提取過(guò)程轉(zhuǎn)變成對(duì)簡(jiǎn)單0，1矩陣的操作，而不是對(duì)象集的處理，減少了矩陣計(jì)算量，大大提高了算法的效率。

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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].沈陽(yáng)：東北大學(xué)出版社，2009.

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

[5] 汪凌.基于粗糙集的不確定信息知識(shí)發(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)的知識(shí)約簡(jiǎn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015 （1）：137-142.

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

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

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

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

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

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

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

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

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