一種改進(jìn)的分辨矩陣構(gòu)造及求核算法

史君華， 劉樂(lè)群

（合肥師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，安徽合肥 230601）

文獻(xiàn)［1］提出了一種能處理模糊性和不確定性問(wèn)題的粗糙集合理論，其核心思想是在保持?jǐn)?shù)據(jù)分類(lèi)能力不變的前提下，通過(guò)對(duì)知識(shí)的化簡(jiǎn)，導(dǎo)出問(wèn)題的決策或分類(lèi)規(guī)則。目前粗糙集合理論被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)、專(zhuān)家系統(tǒng)、數(shù)據(jù)挖掘、模式識(shí)別等研究領(lǐng)域［2］。

約簡(jiǎn)是粗糙集理論研究的重要內(nèi)容之一，它包括屬性約簡(jiǎn)和屬性值約簡(jiǎn)，而求取核屬性通常是求解決策表約簡(jiǎn)的關(guān)鍵步驟。多年來(lái)，學(xué)者們提出了各種利用分辨矩陣求取核屬性的方法。文獻(xiàn)［3］提出了一種用分辨矩陣表示知識(shí)的經(jīng)典算法，該方法簡(jiǎn)單、易懂，但時(shí)間復(fù)雜度較高；文獻(xiàn)［4］提出了一種基于Skowron矩陣的簡(jiǎn)化的差別矩陣方法，該方法簡(jiǎn)化了矩陣元素的構(gòu)造；文獻(xiàn)［5］指出，當(dāng)決策表中存在不一致數(shù)據(jù)，文獻(xiàn)［4］中的算法可能存在錯(cuò)誤，故通過(guò)增加一個(gè)函數(shù)min｛｜d（xi）｜，｜d（xj）｜｝的計(jì)算，提高了算法的正確性，時(shí)間開(kāi)銷(xiāo)亦有所增加；文獻(xiàn)［6］提出了一種基于二進(jìn)制分辨矩陣的求核算法，為分辨矩陣及核屬性的求解開(kāi)辟了一條新的道路；另外，還有很多學(xué)者提出了各種分辨矩陣及求核算法的改進(jìn)算法［7－11］。

以上算法中，有些是時(shí)間性能不理想，有些是不能將算法應(yīng)用于不一致的決策表；另外發(fā)現(xiàn)，分辨矩陣中很多元素并不需要保存，分辨矩陣的構(gòu)造過(guò)程還可進(jìn)一步優(yōu)化。因此，本文提出一種能同時(shí)適用于一致和不一致系統(tǒng)的快速構(gòu)造矩陣并計(jì)算核屬性的優(yōu)化算法，其構(gòu)造方法簡(jiǎn)單，時(shí)間性能較好；并通過(guò)實(shí)例和實(shí)驗(yàn)說(shuō)明了算法的有效性。

1 粗糙集理論基本概念

別表示條件屬性集和決策屬性集是屬性值的集合，其中Vr表示r∈R的屬性值，f：U×R→V是信息函數(shù)。同時(shí)具有條件屬性和決策屬性的信息系統(tǒng)稱(chēng)為決策表（系統(tǒng)）。

定義3 令R為等價(jià)關(guān)系族，設(shè)且P≠?，則P中所有等價(jià)關(guān)系的交集稱(chēng)為P上的不可分辨關(guān)系，記作IND（P）。

定義4 設(shè)R是等價(jià)關(guān)系族，R∈R，若IND（R）＝IND（R－｛R｝），則稱(chēng)R是R中可省的，否則為不可省的。若R中每個(gè)關(guān)系都不可省，則稱(chēng)R是獨(dú)立的，否則為依賴(lài)的。

若用RED（P）表示P的所有約簡(jiǎn)的集合，則有下面關(guān)系成立。

定理1 等價(jià)關(guān)系族P的核等于P的所有約簡(jiǎn)的交集，則有

定義7 決策表中有關(guān)條件屬性集C和決策屬性集D的一個(gè)規(guī)則可以表示為α→β。其中，α是一個(gè)C－集合（稱(chēng)為規(guī)則的前提），β是一個(gè)D－集合（稱(chēng)為規(guī)則的結(jié)論），稱(chēng)α→β為一個(gè)CD－規(guī)則

定義1 設(shè)U為所討論對(duì)象的非空有限集合，稱(chēng)為論域；R為建立在U上的一個(gè)等價(jià)關(guān)系族集，稱(chēng)二元組AS＝（U，R）為近似空間。

定義2 設(shè)S＝（U，R，V，f）為一個(gè)信息系統(tǒng)，其中U是論域，R＝C∪D是屬性集合，C、D分（決策規(guī)則）。

定義8 決策表中的一個(gè)CD－規(guī)則α→β是一致的，當(dāng)且僅當(dāng)對(duì)任何CD－規(guī)則必蘊(yùn)含β＝β′。如果一個(gè)決策表中的所有決策規(guī)則都是一致的，則決策表是一致的，否則決策表是不一致的。

2 改進(jìn)的分辨矩陣構(gòu)造及求核思想

文獻(xiàn)［4］指出，決策表中的不一致數(shù)據(jù)可能會(huì)影響最終核或約簡(jiǎn)求解的正確性，因此在本文提出的算法中，首先會(huì)檢查決策表中是否存在不一致數(shù)據(jù)，對(duì)不一致數(shù)據(jù)加以處理，并在此基礎(chǔ)上考慮提高算法的時(shí)間性能。

2.1 改進(jìn)的分辨矩陣

改進(jìn)的分辨矩陣只存儲(chǔ)三角矩陣，假設(shè)上三角（即j＞i）部分的每個(gè)元素Mij分為Mij1和Mij22項(xiàng)，Mij1負(fù)責(zé)條件屬性部分，Mij2負(fù)責(zé)決策屬性部分，具體構(gòu)造見(jiàn)定義9（其中，a為條件屬性，b為決策屬性，xi、xj為2個(gè)實(shí)例）。

定義9Mij1與Mij2的構(gòu)造如下：

由以上矩陣定義可得如下性質(zhì)。

性質(zhì)1 若Mij1＝0且Mij2＝0，則xi、xj為重復(fù)實(shí)例，可從原數(shù)據(jù)表刪去第i或j行而不影響求解。

性質(zhì)2 若Mij1＝0且Mij2＝1，則xi、xj為不一致實(shí)例，原數(shù)據(jù)表刪去第i和j行以保持一致性。

性質(zhì)3 若Mij1為非0的單個(gè)屬性且Mij2＝0，則該單個(gè)屬性為可約屬性，可不予考慮。

性質(zhì)4 若Mij1為非0的單個(gè)屬性且Mij2＝1，則該單個(gè)屬性為核屬性。

其中，性質(zhì)1、2、3很容易得到，本文對(duì)性質(zhì)4加以證明。

證明 用C和D分別代表某決策表的條件和決策屬性集，核集為CORE，xi、xj為任意2個(gè)實(shí)例。文獻(xiàn)［3］中經(jīng)典Skowron分辨矩陣構(gòu)造如下：

2.2 基于核和吸收率的分辨矩陣優(yōu)化構(gòu)造思想

本算法中基于核屬性和吸收率的分辨矩陣優(yōu)化構(gòu)造思想如下：首先按定義9構(gòu)造分辨矩陣，其中一旦有核屬性（Mij1為非0的單個(gè)屬性且Mij2＝1）產(chǎn)生，則在后續(xù)分辨矩陣的構(gòu)造過(guò)程中，先判斷在該核屬性上2個(gè)實(shí)例取值是否相等。若不等，則跳過(guò)該項(xiàng)分辨矩陣的構(gòu)造（或記標(biāo)記?）；若相等，則繼續(xù)按定義9構(gòu)造，另外在構(gòu)造分辨矩陣的過(guò)程中，不斷地充實(shí)核集，新產(chǎn)生的核對(duì)其后續(xù)分辨矩陣元素的構(gòu)造有同樣的優(yōu)化效果。

例1 假設(shè)一決策表數(shù)據(jù)，見(jiàn)表1所列（其中a、b、c、d、e為條件屬性；f為決策屬性）。

表1 決策表1

已構(gòu)造的部分分辨矩陣數(shù)據(jù)，見(jiàn)表2所列。

表2 已構(gòu)造的部分分辨矩陣

由于M13處分辨矩陣項(xiàng)元素為d1，據(jù)定義9中性質(zhì)4，d為核屬性，所以在求M14時(shí)，先判斷x1和x4在屬性d上取值情況。顯然，取值不等，因此可直接跳過(guò)M14去構(gòu)造M15，這就是吸收率在構(gòu)造分辨矩陣過(guò)程中的應(yīng)用。原因是：假設(shè)M14按正常方法計(jì)算，應(yīng)為abcde1，則在構(gòu)造分辨矩陣之后，如果后期計(jì)算屬性約簡(jiǎn)，由于d?abcde，所以也會(huì)刪去abcde。因此，將吸收率運(yùn)用到分辨矩陣的構(gòu)造過(guò)程中，不僅節(jié)省時(shí)間，而且減少了分辨矩陣包含的項(xiàng)，簡(jiǎn)化了后面的運(yùn)算，特別是當(dāng)核屬性出現(xiàn)得較早時(shí)，該算法能極大地優(yōu)化分辨矩陣的構(gòu)造。

2.3 改進(jìn)的分辨矩陣構(gòu)造及求核的優(yōu)化算法

基于上述思想，本文提出了一種改進(jìn)的分辨矩陣優(yōu)化構(gòu)造及求核算法，具體步驟如下。

本算法中，在構(gòu)造分辨矩陣每項(xiàng)元素時(shí)，都運(yùn)用核和吸收率作為優(yōu)化信息，加速矩陣后續(xù)項(xiàng)的構(gòu)造。首先看核集是否為空，若核集不為空，對(duì)于核集里的每個(gè)核屬性，先判斷2個(gè)實(shí)例在核屬性上取值是否相同，若在某個(gè)核屬性上取值不同，則可跳過(guò)該項(xiàng)分辨矩陣項(xiàng)元素的構(gòu)造（或記標(biāo)記?），否則按定義9繼續(xù)構(gòu)造該項(xiàng)分辨矩陣元素。另外，在構(gòu)造分辨矩陣的過(guò)程中亦不斷地充實(shí)核集，這與經(jīng)典算法相比，不僅可簡(jiǎn)化后續(xù)運(yùn)算，有更好的時(shí)間性能，而且大大減少分辨矩陣項(xiàng)元素所占有的空間。

2.4 實(shí)例

以決策表1為例討論本文提出的算法性能，并與Skowron經(jīng)典算法比較。對(duì)于Skowron經(jīng)典算法，構(gòu)造的分辨矩陣見(jiàn)表3所列。

表3 決策表1構(gòu)造的Skowron分辨矩陣

本文提出的改進(jìn)的分辨矩陣構(gòu)造，見(jiàn)表4所列。顯然，c、d為核屬性，在構(gòu)造分辨矩陣的過(guò)程中，括號(hào)內(nèi)為利用本文算法中吸收率優(yōu)化構(gòu)造的分辨矩陣項(xiàng)元素，括號(hào)外為不利用吸收率，僅利用定義9構(gòu)造的分辨矩陣項(xiàng)元素。

表4 本文算法構(gòu)造的分辨矩陣

與表3比較，本文提出的算法，矩陣內(nèi)的有效元素已明顯減少，因而可大大簡(jiǎn)化后續(xù)運(yùn)算；且在構(gòu)造分辨矩陣的過(guò)程中，核屬性出現(xiàn)得越早，越能減少構(gòu)造分辨矩陣所花費(fèi)的時(shí)空開(kāi)銷(xiāo)。

2.5 實(shí)驗(yàn)結(jié)果及分析

本次實(shí)驗(yàn)以2.34 GHz、1 G內(nèi)存為硬件環(huán)境，以win XP、JDK6.1為軟件開(kāi)發(fā)環(huán)境。使用了UCI國(guó)際機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的6個(gè)數(shù)據(jù)集，比較并分析了本算法的性能，實(shí)驗(yàn)結(jié)果見(jiàn)表5所列。從表5可以看出，本文算法對(duì)于核屬性存在的決策系統(tǒng)、時(shí)間性能的改進(jìn)較明顯，原因在于構(gòu)造分辨矩陣的同時(shí)對(duì)包含核屬性的項(xiàng)運(yùn)用吸收率，因此比經(jīng)典算法執(zhí)行速度加快。但若核為空，該算法的時(shí)間性能可能會(huì)與經(jīng)典算法相差不大。設(shè)一個(gè)決策系統(tǒng)實(shí)例個(gè)數(shù)為｜U｜，條件屬性個(gè)數(shù)為｜C｜，本文提出算法的時(shí)間復(fù)雜度的上限為O（｜C｜×｜U｜2），實(shí)際上通常遠(yuǎn)遠(yuǎn)小于該上限。

表5 與經(jīng)典算法的時(shí)間性能比較

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

本文在對(duì)粗集理論中利用構(gòu)造矩陣求解核屬性算法研究的基礎(chǔ)上，提出一種基于核屬性和吸收率優(yōu)化的決策表矩陣求核改進(jìn)算法，通過(guò)原理及實(shí)驗(yàn)論證，該方法簡(jiǎn)單、有效，但空間性能仍需改進(jìn)，使之能適用于更大規(guī)模的數(shù)據(jù)集。

［1］ Pawlak Z.Rough sets［J］.International Journal of Computer and Information Sciences，1982，11（5）：341－356.

［2］ 楊 勇，朱曉鐘，李 廉.直覺(jué)模糊粗糙集的公理化［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（4）：590－592.

［3］ Skowron A，Rauszer C.The discernibility matrices and functions in information systems［C］／／Intelligent Decision Support：Handbook of Applications and Advances of the Rough Sets Theory，1992：331－362.

［4］ Hu Xiaohua，Cercone N.Learning in relational databases：a rough set approach［J］.Computational Intelligence，1995，11（2）：323－338.

［5］ 葉東毅，陳昭炯.一個(gè)新的差別矩陣及其求核方法［J］.電子學(xué)報(bào)，2002，30（7）：1086－1088.

［6］ 支天云，苗奪謙.二進(jìn)制可辨矩陣的變換及高效屬性約簡(jiǎn)算法的構(gòu)造［J］.計(jì)算機(jī)科學(xué)，2002，29（2）：140－142.

［7］ 王國(guó)胤，于 洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25（7）：759－766.

［8］ 徐章艷，楊炳儒，宋 威.一個(gè)基于差別矩陣的快速求核算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006（6）：4－6.

［9］ 汪小燕.一種改進(jìn)的差別矩陣及其求核方法［J］.安徽工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，26（1）：86－95.

［10］ 汪小燕，王 浩.基于二進(jìn)制可辨矩陣的知識(shí)粒度研究及應(yīng)用［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（10）：91－93.

［11］ 徐章艷，楊炳儒，宋 威，等.幾種不同屬性約簡(jiǎn)的比較研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2008，5（5）：848－853.