基于變精度粗糙集的不完備決策表屬性約簡

林春杰，張瑞玲，韓曉琴

1.洛陽師范學院 信息技術學院，河南 洛陽 471022 2.洛陽師范學院 教育科學學院，河南 洛陽 471022

基于變精度粗糙集的不完備決策表屬性約簡

林春杰1，張瑞玲1，韓曉琴2

1.洛陽師范學院 信息技術學院，河南 洛陽 471022 2.洛陽師范學院 教育科學學院，河南 洛陽 471022

1 引言

粗糙集理論[1]是一種無需先驗知識，能夠處理不精確、不確定、不完備數(shù)據的數(shù)學工具，是經典集合論的重要發(fā)展，在知識定義、知識約簡、規(guī)則發(fā)現(xiàn)等方面[2-5]，為知識獲取提供了一種嶄新的工具。然而經典粗糙集模型對噪聲敏感，其對數(shù)據的過擬合而降低了對對象的預測能力。為了克服這些局限性，Ziarko提出了變精度粗糙集[6]，變精度粗糙集通過引入閾值β，提高了其容錯性和抗噪能力，可以處理屬性間無函數(shù)依賴關系的數(shù)據分類問題。變精度粗糙集已經在一些領域得到成功應用[7-8]。

知識約簡是粗糙集理論的核心內容之一，一些學者從不同的角度出發(fā)給出了基于變精度粗糙集的約簡方法。文獻[9]提出了能夠保持所有決策的對象總數(shù)不變的β約簡方法，但產生的規(guī)則可能與原信息系統(tǒng)產生的規(guī)則不一致；文獻[10]提出不改變由對象所產生規(guī)則的決策結果的上（下）分布約簡方法。然而，以上算法都以完備決策表為研究對象，在實際應用中，信息的非完備現(xiàn)象是廣泛存在的。針對不完備信息系統(tǒng)，文獻[11]給出了一個不完備決策表中的變精度粗糙集模型和約簡算法，但約簡條件過于苛刻，沒有考慮閾值β對約簡的影響；文獻[12]提出了基于累積正區(qū)域的變精度粗糙集約簡算法，但算法時間復雜度是指數(shù)級的不適合于大數(shù)據集。文獻[13]在文獻[10]基礎上給出了β上（下）分布約簡方法，該算法在協(xié)調決策表中能夠得到約簡，然而在不協(xié)調決策表中往往得不到正確的約簡。

本文分析文獻[13]提出的變精度粗糙集算法的局限，給出基于相容關系的改進上（下）分布可辨識矩陣和約簡方法，并通過實例驗證了提出方法的有效性。

2 基本概念

如果A=C∪j5i0abt0b，其中C表示條件屬性，D表示決策屬性，則稱S=(U，C∪D)為決策表或決策信息系統(tǒng)。如果?a∈C，使得Va含有空值，用*表示空值，則稱S=(U，C∪D)為一個不完備決策表。

定義2[14]不完備決策表S=(U，C∪D)，對于P?C，由P確定的相容關系定義為SIM(P)={(x，y)∈U×U|?a∈P，f(x，a)=f(y，a)∨f(x，a)=*∨f(y，a)=*}，其中f(x，a)表示對象x在屬性a下的取值。

顯然，相容關系SIM(P)是自反、對稱的，但不一定傳遞。對于x∈U，P?C，對象x的相容類定義為SP(x)= {y∈U|(x，y)∈SIM(P)}，即在相容關系SIM(P)下與對象x不可區(qū)分的對象集合。

在不完備決策表中，通過相容關系將論域中的對象分成一系列的相容顆粒，這些相容顆粒一般不構成系統(tǒng)的劃分而是覆蓋，容易證明，對?x，y∈U，兩個對象的相容類間滿足以下性質：

（1）若(x，y)?SIM(P)，則SP(x)∩SP(y)=?未必成立；

（2）若(x，y)∈SIM(P)，則SP(x)=SP(y)未必成立。

以上性質表明，在相容關系下不可區(qū)分的兩個對象的相容類可能是不同的；相應地，在相容關系下可區(qū)分的兩個對象的相容類可能相容的對象。因此，不能僅用這兩個對象的相容類是否屬于同一決策類來區(qū)分這兩個對象的相對可辨識性。

定義3[13]不完備決策表S=(U，C∪D)，非空集合X?U，0≤β＜0.5，對P?C，關于β的上（下）近似定義為：

3 不完備決策表屬性約簡方法

文獻[13]根據文獻[10]給出了一個不完備信息系統(tǒng)下，基于變精度粗糙集的β上（下）分布約簡方法。但該算法在不協(xié)調決策表中（如表1），往往得不到正確的約簡。

表1 一個不完備不協(xié)調的決策表

根據文獻[13]定義的可辨識矩陣，得到表1的0.3下分布約簡為{a2，a4}。但是所以{a2，a4}不是系統(tǒng)的下分布協(xié)調集，即不是0.3下分布約簡。同理，得到0.3上分布約簡{a2,a4}，但是，然而，，因此{a2，a4}也不是0.3上分布約簡。

導致約簡不正確的原因，是在基于相容關系的不完備信息系統(tǒng)中，認為缺省值的取值是任意的，導致一個對象可能屬于多個相容類，所以在同一相容類內的對象的決策類不一定都相同，也就是說即使兩個對象屬于同一決策類，也可能是相對可辨識的。下面給出不完備信息系統(tǒng)中，β上（下）分布約簡的判定定理和改進的可辨識矩陣。

證明同定理1。

根據定理1和定理2得到的改進β上（下）分布可辨識矩陣定義如下：

定義4不完備決策表S=(U，C∪D)中，β上（下）分布可辨識屬性集定義為：

由上述定義可知，當兩個對象的決策類不同時，可以通過兩個對象取值不相同的屬性區(qū)分；如果兩個對象的決策類相同，當兩個對象的相容類中包含與它們決策類不同的對象時，通過兩個對象取值不相同的屬性區(qū)分；其他情況對應的矩陣元素為?。而且當β=0時，擴展β上（下）分布可辨識矩陣退化為完備決策表β上（下）分布可辨識矩陣。

表2 上分布可辨識矩陣

定理3改進的上（下）分布可辨識矩陣具有如下性質：

（2）主對角線上的元素都是?(l=1，2)；

證明由定義4，性質（1）、（2）、（3）顯然成立。

根據定義4定義的可辨識矩陣導出β上（下）可辨識公式，從可辨識公式的最小析取范式可以得到不完備決策表的一組約簡，可以證明，得到的約簡是所有β上（下）分布約簡的集合[10]。

下面給出不完備決策表中基于變精度粗糙集的屬性約簡算法。

算法1變精度粗糙集上（下）分布約簡算法

輸入：不完備決策表S=(U，C∪D)；

輸出：C的上（下）分布約簡集。

步驟1計算決策表S中所有元素的相容類；

步驟2根據定義4，計算上（下）分布可辨識矩陣；

步驟3通過上（下）分布可辨識矩陣得到上分布分辨公式，并計算極小析取范式；

步驟4輸出約簡結果，算法結束。

4 實例分析

利用改進β上（下）可辨識矩陣約簡決策表1，取β=0.35。

同理得到所有的0.35上分布可辨識屬性集，并生成上分布可辨識矩陣，如表2所示。

因此得到可辨識公式(a2∨a4)∧(a2∨a3∨a4)∧(a1∨a2∨a4)∧(a3)∧(a4)∧(a3∨a4)，通過計算最小析取范式得到不完備決策表的0.35上分布約簡{a3，a4}；同理可以得到不完備決策表的0.35下分布約簡{a4}。

5 結束語

針對現(xiàn)有的不完備決策表中基于變精度粗糙集屬性約簡算法的缺陷，給出了基于相容關系的β上（下）分布約簡的判定定理和改進的β上（下）分布可辨識矩陣；通過實例驗證了算法的有效性?；诳杀孀R矩陣的約簡算法雖然能得到最小約簡，但由于計算過程中需要存儲可辨識矩陣和計算最小析取范式，面對大量的數(shù)據時，時間和空間復雜度較高。因此，在不完備信息系統(tǒng)下找到一個高效的變精度粗糙集啟發(fā)式約簡算法是下一步需要研究的問題。

[1]Pawlak Z，Skowron A.Rudiments of rough sets[J].Information Sciences，2007，177：3-27.

[2]苗奪謙，王玨.粗糙集理論中概念與運算的信息表示[J].軟件學報，1999，10（2）：113-116.

[3]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學報，2002，25（7）：759-766.

[4]Li T，Ruan D，Geert W，et al.A rough sets based characteristic relation approach for dynamic attribute generalization in data mining[J].Knowledge-Based Systems，2007，20（5）：485-494.

[5]Liu D，Li T，Ruan D，et al.Incremental learning optimization on knowledge discovery in dynamic business intelligent systems[J].Journal of Global Optimization，2011，51（2）：325-344.

[6]Ziarko W.Variable precision rough set model[J].Journal of Computer and System Sciences，1993，46：39-59.

[7]Beynon M J.Introduction and elucidation of the quality of sagaeity in the extended variable precision rough sets model[J]. Electronic Notes in Theoretical Computer Seience，2003，82（4）：l-10.

[8]Griffiths B，Beynon M J.Expositing stages of VPRS analysis in an expert system：application with bank credit tratings[J]. Expert Systems with Applications，2005，29：879-888.

[9]Beynon M J.Reducts within the variable precision rough sets model：a further investigation[J].European Journal of Operational Research，2001，134：592-605.

[10]Mi J，Wu W，Zhang W.Approaches to knowledge reduction based on variable precision rough set model[J].Information Sciences，2004，159：255-272.

[11]張宏宇，梁吉業(yè).不完備信息系統(tǒng)下的變精度粗糙集模型及其知識約簡算法[J].計算機科學，2003，30（4）：153-155.

[12]Sun S，Zheng R，Wu Q，et al.VPRS-based knowledge discovery approachinincompleteinformationsystem[J].Journalof Computers，2010，5（1）：110-116.

[13]趙亞娣，魏立力.基于變精度粗糙集的不完備信息系統(tǒng)知識約簡[J].計算機工程與應用，2009，45（13）：65-67.

[14]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences，1998，112：39-49.

LIN Chunjie1,ZHANG Ruiling1,HAN Xiaoqin2

1.Institute of Information Technology,Luoyang Normal College,Luoyang,Henan 471022,China
2.Institute of Educational Scientific,Luoyang Normal College,Luoyang,Henan 471022,China

In view of the limitations of the attribute reduction algorithm based on variable precision rough set in tolerance relation,the judgment theorems and discernibility matrixes with respect toβupper（lower）distribution reductions are presented。The method forβupper（lower）distribution reduction in incomplete decision table is also presented.At last,the experiment demonstrates the effectiveness of the proposed method.

variable precision rough set;incomplete decision table;attribute reduction;tolerance relation

針對現(xiàn)有的在相容關系下基于變精度粗糙集約簡算法的局限，給出了β上（下）分布約簡的判定方法和改進的β上（下）分布可辨識矩陣定義，并給出求解基于變精度粗糙集的不完備決策表約簡算法；最后通過實例驗證了算法的有效性。

變精度粗糙集；不完備決策表；屬性約簡；相容關系

A

TP18

10.3778/j.issn.1002-8331.1110-0661

LIN Chunjie,ZHANG Ruiling,HAN Xiaoqin.Attribute reduction based on variable precision rough set in incomplete decision table.Computer Engineering and Applications,2013,49（13）：118-120.

國家自然科學基金（No.10802068）；河南省重大科技攻關項目（No.102102310058）。

林春杰（1981—），男，講師，CCF會員，研究領域：粗糙集，概念格；張瑞玲（1964—），女，教授，研究領域：粗糙集，概念格；韓曉琴（1981—），女，講師，研究領域:數(shù)據挖掘。E-mail：lynclcj@126.com

2011-11-04

2012-04-09

1002-8331（2013）13-0118-03