李飏

摘要：屬性約簡(jiǎn)是粗糙集的核心內(nèi)容，該文分析了基于差別函數(shù)的決策表屬性約簡(jiǎn)存在的優(yōu)缺點(diǎn)，在他人提出的改進(jìn)的基于差別函數(shù)的決策表屬性約簡(jiǎn)算法的基礎(chǔ)上，進(jìn)一步對(duì)約簡(jiǎn)結(jié)果處理，通過(guò)對(duì)其平均信息熵的大小衡量，選擇具有巨大信息量的約簡(jiǎn)作為最后的單一約簡(jiǎn)。

關(guān)鍵詞：屬性約簡(jiǎn)；粗糙集；差別函數(shù)；平均信息熵

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）22-5348-02

1 概述

粗糙集理論是一種關(guān)于數(shù)據(jù)分析和推理的理論，它不需要任何預(yù)備的或額外的有關(guān)數(shù)據(jù)信息，能夠有效地分析和處理不完備、不一致、不精確的數(shù)據(jù)。屬性約簡(jiǎn)是指在保持知識(shí)分類能力不變的條件下，刪除其中不必要的、不重要的或不相關(guān)的屬性。

2 基于差別函數(shù)的決策表屬性約簡(jiǎn)算法

2.1屬性約簡(jiǎn)的概念

對(duì)于決策表而言，屬性約簡(jiǎn)的定義為：設(shè)子集[R?C]，若[R]為[C]的[D]約簡(jiǎn)，當(dāng)且僅當(dāng)[R]滿足[POSR（D）=POSC（D）]而且不存在[R′?R]使得[POSR′（D）=POSC（D）]，記[R∈REDC（D）]，其中[REDC（D）]表示[C]的全體[D]約簡(jiǎn)組成的集合。由此可見(jiàn)，決策表的屬性約簡(jiǎn)是保證正域不變的最小屬性集合。[C]的[D]核[COREC（D）=?REDC（D）]，或[C]的[D]核為[C]中全體必要屬性的集合。

2.2 基于差別函數(shù)的屬性約簡(jiǎn)

2.3 優(yōu)缺點(diǎn)分析

基于差別函數(shù)的決策表屬性約簡(jiǎn)算法可以得到該決策表所有可能的屬性約簡(jiǎn)結(jié)果，實(shí)際上是將對(duì)屬性組合情況的搜索演變?yōu)檫壿嫻降幕?jiǎn)，從而簡(jiǎn)化問(wèn)題。但是，由于求差別矩陣需要將每個(gè)對(duì)象與其他的所有對(duì)象比較，當(dāng)決策表的論域?qū)ο蠛芏鄷r(shí)，該算法的邏輯轉(zhuǎn)換運(yùn)算代價(jià)很大，計(jì)算過(guò)程麻煩，復(fù)雜度逐漸增大，求取約簡(jiǎn)所需的時(shí)間也越來(lái)越多。

此外，該方法一般只適用于完備相容的決策表，即在決策表不相容的情況下可能導(dǎo)致錯(cuò)誤的計(jì)算結(jié)果。

2.4屬性約簡(jiǎn)算法的改進(jìn)

利用任何一個(gè)相對(duì)約簡(jiǎn)一定包含相對(duì)核這一特性來(lái)簡(jiǎn)化和降低計(jì)算代價(jià)。于是提出了改進(jìn)的基于差別函數(shù)的決策表屬性約簡(jiǎn)算法。首先將相對(duì)[D]核中的條件屬性從差別矩陣中取出，同時(shí)將差別矩陣中包含相對(duì)[D]核屬性的元素置為0（[?]和[-]同樣置為0），從而得到一個(gè)新矩陣，稱為決策表的分明矩陣。對(duì)分明矩陣計(jì)算得到析取范式邏輯表達(dá)式，最有將所有核屬性重新加到析取范式中的每個(gè)合取項(xiàng)，得到?jīng)Q策表的所有屬性約簡(jiǎn)。

3 基于差別函數(shù)的屬性約簡(jiǎn)進(jìn)一步改進(jìn)

不管是基于差別函數(shù)的決策表屬性約簡(jiǎn)算法還是改進(jìn)的基于差別函數(shù)的決策表屬性約簡(jiǎn)算法，最后的結(jié)果都是求得所有約簡(jiǎn)。這對(duì)信息系統(tǒng)的理論分析和實(shí)際計(jì)算都是有用處的，但是在實(shí)際應(yīng)用時(shí)只需要一種約簡(jiǎn)，而且該約簡(jiǎn)具有的信息量要求最大。

具體思路為：基于分明矩陣得到析取范式，然后計(jì)算各合取項(xiàng)的平均信息熵，選擇平均信息熵最小的與核屬性組成最終的約簡(jiǎn)結(jié)果。

4 結(jié)論

屬性約簡(jiǎn)是粗糙集的重要內(nèi)容，屬性約簡(jiǎn)也是各方面研究的基礎(chǔ)環(huán)節(jié)，具有重要意義，該文首先介紹了基于差別函數(shù)的屬性約簡(jiǎn)以及他人的改進(jìn)算法，在此基礎(chǔ)上，提出了進(jìn)一步對(duì)約簡(jiǎn)結(jié)果處理的方法。

參考文獻(xiàn)：

[1] Pawlak Z. Rough sets： Theoretical Aspects of Reasoning about Data， Kluwer Academic Publishers， Boston， 1991.

[2] 苗奪謙， 李道國(guó). 粗糙集理論、算法與應(yīng)用[J]. 北京：清華大學(xué)出版社， 2008.

[3] 苗奪謙， 胡桂榮. 知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J]. 計(jì)算機(jī)研究與發(fā)展， 1999，36（6）：681-684.