基于變精度粗糙集的不完備決策表屬性約簡(jiǎn)

林春杰，張瑞玲，韓曉琴

1.洛陽師范學(xué)院 信息技術(shù)學(xué)院，河南 洛陽 471022 2.洛陽師范學(xué)院 教育科學(xué)學(xué)院，河南 洛陽 471022

基于變精度粗糙集的不完備決策表屬性約簡(jiǎn)

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

1.洛陽師范學(xué)院 信息技術(shù)學(xué)院，河南 洛陽 471022 2.洛陽師范學(xué)院 教育科學(xué)學(xué)院，河南 洛陽 471022

1 引言

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

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

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

2 基本概念

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

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

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

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

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

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

以上性質(zhì)表明，在相容關(guān)系下不可區(qū)分的兩個(gè)對(duì)象的相容類可能是不同的；相應(yīng)地，在相容關(guān)系下可區(qū)分的兩個(gè)對(duì)象的相容類可能相容的對(duì)象。因此，不能僅用這兩個(gè)對(duì)象的相容類是否屬于同一決策類來區(qū)分這兩個(gè)對(duì)象的相對(duì)可辨識(shí)性。

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

3 不完備決策表屬性約簡(jiǎn)方法

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

表1 一個(gè)不完備不協(xié)調(diào)的決策表

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

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

證明同定理1。

根據(jù)定理1和定理2得到的改進(jìn)β上（下）分布可辨識(shí)矩陣定義如下：

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

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

表2 上分布可辨識(shí)矩陣

定理3改進(jìn)的上（下）分布可辨識(shí)矩陣具有如下性質(zhì)：

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

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

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

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

算法1變精度粗糙集上（下）分布約簡(jiǎn)算法

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

輸出：C的上（下）分布約簡(jiǎn)集。

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

步驟2根據(jù)定義4，計(jì)算上（下）分布可辨識(shí)矩陣；

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

步驟4輸出約簡(jiǎn)結(jié)果，算法結(jié)束。

4 實(shí)例分析

利用改進(jìn)β上（下）可辨識(shí)矩陣約簡(jiǎn)決策表1，取β=0.35。

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

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

5 結(jié)束語

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

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

[2]苗奪謙，王玨.粗糙集理論中概念與運(yùn)算的信息表示[J].軟件學(xué)報(bào)，1999，10（2）：113-116.

[3]王國(guó)胤，于洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào)，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)下的變精度粗糙集模型及其知識(shí)約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué)，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)知識(shí)約簡(jiǎn)[J].計(jì)算機(jī)工程與應(yīng)用，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

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

變精度粗糙集；不完備決策表；屬性約簡(jiǎn)；相容關(guā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.

國(guó)家自然科學(xué)基金（No.10802068）；河南省重大科技攻關(guān)項(xiàng)目（No.102102310058）。

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

2011-11-04

2012-04-09

1002-8331（2013）13-0118-03