侯慧欣, 劉城霞

(北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院,北京 100101)

粗糙集理論最早由波蘭數(shù)學(xué)家華沙理工大學(xué)教授Z.Pawlak于1982年提出,是一種處理不精確、不一致、不完整等數(shù)據(jù)的數(shù)學(xué)工具,同時(shí)對(duì)處理非常復(fù)雜的系統(tǒng)非常有效. 屬性約簡是粗糙集理論研究的核心內(nèi)容之一,其中基于區(qū)分矩陣的方法是現(xiàn)有的一種具有代表性的屬性約簡算法,很多屬性約簡及其拓展的工作都以此為基礎(chǔ)[1-4]. 目前,對(duì)現(xiàn)有算法的改進(jìn)大多是提高算法的效率,如文獻(xiàn)[5-8],或擴(kuò)大其應(yīng)用范圍如文獻(xiàn)[9-11],而此次實(shí)現(xiàn)的改進(jìn)則是針對(duì)數(shù)據(jù)而言. 由于現(xiàn)有的算法都只用于處理離散數(shù)據(jù),對(duì)于連續(xù)數(shù)據(jù)需要先進(jìn)行離散化處理. 而本次實(shí)現(xiàn)的改進(jìn)則取締了離散化這一步驟,可以對(duì)離散數(shù)據(jù)和連續(xù)數(shù)據(jù)統(tǒng)一進(jìn)行處理.

泛邏輯是本世紀(jì)初由何華燦教授提出. 它基于二值邏輯,多值邏輯和模糊邏輯,并可以有效地處理人工智能中不精確、不完整和連續(xù)的數(shù)據(jù),不完備和模糊數(shù)據(jù). 它可以被認(rèn)為是一種柔性邏輯. 粗糙集理論和泛邏輯都可以用來處理不精確和不確定問題,因此結(jié)合兩個(gè)理論來取得更好的效果是可行和方便的[12].

1 基本概念

1.1 粗糙集

定義1[13]. 一個(gè)信息表可以描述為,其中U是論域,：C是條件屬性集,d是決策屬性.是屬性的值域,其中,Va是屬性a的值域.是信息決策函數(shù). 當(dāng)時(shí),該信息表是一個(gè)決策信息表.

1.2 屬性約簡

在粗糙集信息系統(tǒng)中,設(shè)R是一個(gè)等價(jià)關(guān)系簇,,如果,則稱I在等價(jià)關(guān)系簇R中是不必要的. 否則稱I在等價(jià)關(guān)系簇R中是必要的. 若R中的每一個(gè)等價(jià)關(guān)系I都是必要的,則稱R是獨(dú)立的. 屬性約簡就是在知識(shí)庫分類能力保持不變的情況下,刪除冗余屬性.

(1)D是獨(dú)立的,

則稱D是B的一個(gè)約簡. 記為：. 其中所有的必要關(guān)系組成的集合,稱為B的核,記為：.即. 核是信息系統(tǒng)中的核心屬性集,是所有約簡的公共部分.

1.3 區(qū)分矩陣

定義5[5]. 設(shè)為一個(gè)決策表,其中C為條件屬性集,D為決策屬性集,決策表S的區(qū)分矩陣被定義為,其中

2 算法原理

(1) 首先根據(jù)信息表S構(gòu)造區(qū)分矩陣M,按照公式(1)規(guī)則構(gòu)造矩陣.

構(gòu)造區(qū)分矩陣時(shí),需要將信息表中所有數(shù)據(jù)一一進(jìn)行對(duì)比,在此以第條數(shù)據(jù)舉例說明具體構(gòu)造過程：首先判斷第條數(shù)據(jù)決策屬性值是否相同,若相同,即則將值記為空; 若決策屬性值不同,即,此時(shí)從第一個(gè)條件屬性開始比較這兩條數(shù)據(jù)的所有條件屬性,若兩條數(shù)據(jù)的條件屬性ak相等,則不作處理; 若兩條數(shù)據(jù)的條件屬性ak不相等,則將ak屬性添加到值中. 由于每兩條數(shù)據(jù)只需要單向比較一次即可,所以結(jié)合矩陣的特點(diǎn),我們可以知道最后得到的區(qū)分矩陣是一個(gè)主對(duì)角線上元素為空的上三角矩陣或下三角矩陣.

(2) 根據(jù)區(qū)分矩陣構(gòu)造區(qū)分函數(shù),規(guī)則如下：

(3) 刪除包含關(guān)系： 將所有析取表達(dá)式合取得到的合取范式通常都很復(fù)雜,甚至含有大量重復(fù)內(nèi)容. 在這種情況下若是直接將合取范式轉(zhuǎn)化為析取范式需要花費(fèi)大量的時(shí)間和空間,且十分不必要. 根據(jù)離散定律中冪等律和吸收律特點(diǎn),我們可以簡化合取范式的內(nèi)容,有效地減少后續(xù)工作的工作量. 冪等律：,吸收律：拓展為包含關(guān)系可以將相等或較大的一項(xiàng)析取范式刪掉,且對(duì)最后結(jié)果沒有影響. 證明過程參見定理1的證明. 所以,我們可以在求出區(qū)分矩陣之后先將包含關(guān)系刪除,再對(duì)簡化后的區(qū)分矩陣進(jìn)行后續(xù)操作. 這一方法可以有效降低系統(tǒng)開銷,縮短程序運(yùn)行時(shí)間,提高算法運(yùn)行效率.

將合取范式轉(zhuǎn)化為析取范式,即將L轉(zhuǎn)化為析取范式L',. 通過離散定律分配律可以將合取范式轉(zhuǎn)化為析取范式,最終得到結(jié)果一個(gè)或多個(gè)約簡集以及所有約簡集的交集——核.

3 算法改進(jìn)

3.1 改進(jìn)原理

由于原始的算法只能用于處理離散的數(shù)據(jù),然而現(xiàn)實(shí)生活中我們收集的數(shù)據(jù)大部分都是既包含連續(xù)數(shù)據(jù)又包含離散數(shù)據(jù). 因此對(duì)于這些數(shù)據(jù),我們需要先進(jìn)行離散化處理再進(jìn)行屬性約簡. 然而在使用等區(qū)間離散化方法時(shí)經(jīng)常會(huì)出現(xiàn)以下問題： 兩個(gè)邊界值的數(shù)值非常接近,但它們離散化后屬于不同區(qū)域,因此它們會(huì)被置于不同的等價(jià)集中. 這顯然是不合理的,這是人為的離散化帶來的錯(cuò)誤. 但是如果使用柔性邏輯等價(jià)關(guān)系就可以避免這種錯(cuò)誤. 因?yàn)榈葏^(qū)間離散化方法是將該屬性劃分為一定的區(qū)間數(shù),每個(gè)區(qū)間距離相同,將位于同一區(qū)間的數(shù)據(jù)離散化為同一結(jié)果. 因此這種離散化方法對(duì)于邊界值的處理會(huì)產(chǎn)生錯(cuò)誤,比如說位于不同區(qū)間但數(shù)值十分相近的兩個(gè)數(shù)值,很明顯這兩個(gè)數(shù)值應(yīng)當(dāng)離散化為相同的結(jié)果,但是對(duì)于等區(qū)間離散化方法而言,對(duì)于這一類數(shù)據(jù)的處理就會(huì)發(fā)生錯(cuò)誤. 而使用柔性邏輯等價(jià)關(guān)系時(shí),使用的是中心等價(jià)公式：此時(shí)判斷x和y離散化結(jié)果是否相同時(shí),判斷條件不是這兩個(gè)數(shù)值是否位于同一區(qū)間,而是這兩個(gè)數(shù)值的差距是否超過固定的區(qū)間距離. 這樣就可以避免邊界值由于等區(qū)間離散化方法而產(chǎn)生的錯(cuò)誤. 本文只討論了最簡單的離散化方法(等區(qū)間離散),如果連續(xù)屬性具有不同的特征,并且使用不同的離散化方法來使數(shù)據(jù)離散,我們也可以調(diào)整參數(shù),使用不同的等價(jià)公式來處理這些連續(xù)數(shù)據(jù). 如果零級(jí)泛邏輯不足以覆蓋使用,我們也可以引入自相關(guān)參數(shù)k以獲得更大的柔性.

改進(jìn)算法利用了柔性邏輯中的中心等價(jià)公式. 在柔性邏輯理論中,定義了一組連續(xù)而靈活的運(yùn)算符集,以表示廣義相關(guān)性和廣義自相關(guān)性[14]. 在本文中,我們只考慮廣義相關(guān)性[15],而廣義相關(guān)性可以被量化為廣義相關(guān)系數(shù),一般用h表示,h在[0,1]中連續(xù)取值.

使用T范數(shù)來表示AND關(guān)系,S范數(shù)來表示OR關(guān)系,這是泛邏輯的數(shù)學(xué)基礎(chǔ). 廣義相關(guān)性被定義為h和兩個(gè)僅由h控制的兩個(gè)函數(shù),T生成元完整簇和S生成元完整簇.把它們應(yīng)用到AND運(yùn)算模型和OR運(yùn)算模型,我們可以得到和：

將T生成元完整簇放入蘊(yùn)含運(yùn)算模型中,我們可以得到：

將T生成元完整簇放入等價(jià)運(yùn)算模型

(1) Zadeh等價(jià)：

(2) 概率等價(jià)：

(3) 中心等價(jià)：

(4) 最大等價(jià)：

使用柔性邏輯中的中心等價(jià)公式：

由于x,y的取值區(qū)間只能為[0,1],所以將公式轉(zhuǎn)化為：

與改進(jìn)前的算法相比較,改進(jìn)后算法只是將構(gòu)造區(qū)分矩陣的條件由公式(1)改為公式(10).公式(10)主要描述了構(gòu)造區(qū)分矩陣的規(guī)則,規(guī)則如下： 首先判斷Xi和Xi的決策屬性值是否相同,若相同則將該矩陣的i行j列置空,若其決策屬性值不同,則依次計(jì)算的結(jié)果,將該結(jié)果與參數(shù)進(jìn)行比較,若該結(jié)果小于等于,則將該屬性加入到該項(xiàng)中,若大于,則不將該屬性加入該項(xiàng). 公式(1)與公式(10)的區(qū)別在于： 在判斷條件屬性是否加入該項(xiàng)時(shí),公式(1)是對(duì)離散化后的結(jié)果直接進(jìn)行判斷,等于或不等關(guān)系. 而公式(10)則直接將離散數(shù)據(jù)或連續(xù)數(shù)據(jù)根據(jù)中心等價(jià)公式進(jìn)行計(jì)算,再將計(jì)算結(jié)果與值進(jìn)行比較. 其實(shí)這兩種判斷條件直接體現(xiàn)出了不可分辨關(guān)系和柔性邏輯等價(jià)關(guān)系的區(qū)別.

3.2 實(shí)例說明

在實(shí)現(xiàn)區(qū)分矩陣屬性約簡算法時(shí),通常需要先將原始數(shù)據(jù)離散化,再對(duì)離散數(shù)值進(jìn)行屬性約簡. 現(xiàn)在提出一種利用柔性邏輯等價(jià)關(guān)系替代原本的不可分辨關(guān)系,省略離散化這一過程. 這一改進(jìn)使用公式(8),只針對(duì)等區(qū)間離散化這一方法進(jìn)行改進(jìn).

為了完整的研究算法,現(xiàn)引入一個(gè)覆蓋算法涉及到的全部步驟的氣象表,如表1. 表中數(shù)據(jù)后的小括號(hào)內(nèi)容表示對(duì)應(yīng)的離散化后的結(jié)果.

表1 氣象表

表中存在2個(gè)連續(xù)屬性,分別為a2和a3. 將a2劃分為 3個(gè)區(qū)間,分別為： [6,19),[19,28),[28,39],對(duì)應(yīng)離散值為3,2,1. 將a3劃分為2個(gè)區(qū)間,分別為：[28,55),[55,82),對(duì)應(yīng)離散值為2,1.

傳統(tǒng)的區(qū)分矩陣屬性約簡算法大致分為3步：

1) 首先根據(jù)信息系統(tǒng)S構(gòu)造區(qū)分矩陣M(S);

2) 根據(jù)區(qū)分矩陣構(gòu)造區(qū)分函數(shù);

3) 計(jì)算區(qū)分函數(shù),將合取范式轉(zhuǎn)化為析取范式.

改進(jìn)的算法對(duì)代碼改動(dòng)較小,只需在構(gòu)造區(qū)分矩陣時(shí)將原來的不可分辨關(guān)系判斷條件改為柔性邏輯等價(jià)關(guān)系的判斷條件即可.

表2 改進(jìn)前區(qū)分矩陣

表3 改進(jìn)后區(qū)分矩陣

改進(jìn)前后構(gòu)造的區(qū)分矩陣結(jié)果略有不同. 分析這些不同,主要有以下兩種情況：

1) 改進(jìn)后的矩陣某一項(xiàng)增加了某一屬性： 如X6,9改進(jìn)前的內(nèi)容為a1a4,改進(jìn)后為a1a3a4. 針對(duì)a3屬性進(jìn)行分析,濕度52%和28.5%離散化后均為2.所以改進(jìn)前區(qū)分矩陣該項(xiàng)的內(nèi)容中并不包括a3屬性. 但是52%和28.5%均屬于邊界值,雖然同屬一個(gè)區(qū)間,但實(shí)際差距還是很大的. 因此改進(jìn)后的算法更合理.

2) 改進(jìn)后的矩陣某一項(xiàng)刪除了某一屬性. 如X1,4改進(jìn)前的內(nèi)容為a1a2,改進(jìn)后為a1. 針對(duì)a2屬性進(jìn)行分析,溫度32和25離散化后分別為1和2.所以改進(jìn)前區(qū)分矩陣該項(xiàng)的內(nèi)容中包括a3屬性. 但是32和25均屬于邊界值,雖然屬于不同區(qū)間,但實(shí)際差距不大的.因此改進(jìn)后的算法更合理.

對(duì)改進(jìn)前后的算法效率進(jìn)行比較,發(fā)現(xiàn)： 改進(jìn)后的算法效率與改進(jìn)前的算法效率幾乎持平,甚至在數(shù)據(jù)量逐漸增多的情況下,改進(jìn)后的算法效率要低于改進(jìn)前的算法效率. 而且,改進(jìn)后的算法效率在構(gòu)建區(qū)分矩陣部分所消耗的時(shí)間遠(yuǎn)大于改進(jìn)前的算法. 由于機(jī)器限制,只比較了具有5個(gè)屬性的數(shù)據(jù)表在100～900,1000～7000條數(shù)據(jù)等不同情況下的運(yùn)行時(shí)間. 實(shí)驗(yàn)結(jié)果如表4和表5.

表4 千條以內(nèi)數(shù)據(jù)算法效率對(duì)比

表5 千條以上數(shù)據(jù)算法效率對(duì)比

測試硬件環(huán)境： 聯(lián)想PC,1.90 GHZ,內(nèi)存2.0 GB,測試軟件環(huán)境： Microsoft Windows7 旗艦版,編程語言：Java,開發(fā)環(huán)境： MyEclipse Professional 2014.

4 結(jié)論與展望

本文實(shí)現(xiàn)了基于區(qū)分矩陣的屬性約簡基礎(chǔ)算法,并實(shí)現(xiàn)了利用柔性邏輯對(duì)該算法的改進(jìn),將改進(jìn)前后的算法進(jìn)行了內(nèi)容和效率兩方面的對(duì)比并得出結(jié)論.但是本文使用的柔性邏輯等價(jià)關(guān)系只針對(duì)等區(qū)間離散化方法,對(duì)于其他的離散化方法并不適用,因此今后的研究方向是利用柔性了邏輯對(duì)其他的離散化方法進(jìn)行改進(jìn),將柔性邏輯和粗糙集理論做一個(gè)更好的統(tǒng)一.

1張文修,吳偉志,梁吉業(yè),等. 粗糙集理論與方法. 北京： 科學(xué)出版社,2001.

2王丹,吳孟達(dá),劉銀山. 屬性約簡的一種簡單算法. 模糊系統(tǒng)與數(shù)學(xué),2004,18(S)： 254-257.

3陶志,許寶棟,汪定偉. 一種基于分明矩陣的啟發(fā)式知識(shí)約簡方法. 系統(tǒng)工程與電子技術(shù),2005,27(4)： 734-736.

4孫士保,秦克云. 基于包含度的決策表屬性約簡算法的研究. 計(jì)算機(jī)工程與應(yīng)用,2006,(3)： 19-21.

5高錦標(biāo). 一種改進(jìn)的區(qū)分矩陣屬性約簡算法及應(yīng)用. 電腦知識(shí)與技術(shù),2009,5(8)： 1876-1877.

6史君華,胡學(xué)鋼. 一種基于粗集的決策表屬性值約簡改進(jìn)算法. 合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,31(1)： 36-39.

7葉東毅. Jelonek屬性約簡算法的一個(gè)改進(jìn). 電子學(xué)報(bào),2000,28(12)： 81-82. [doi： 10.3321/j.issn：0372-2112.2000.12.023]

8劉文軍,谷云東,馮艷賓,等. 基于可辨識(shí)矩陣和邏輯運(yùn)算的屬性約簡算法的改進(jìn). 模式識(shí)別與人工智能,2004,17(1)： 119-123.

9陶志,劉慶拯,李衛(wèi)民. 一種基于改進(jìn)區(qū)分矩陣的屬性約簡算法. 2007中國控制與決策學(xué)術(shù)年會(huì)論文集. 無錫,中國.2007. 83-85.

10葛浩,李龍澍,楊傳健. 新的可分辨矩陣及其約簡方法. 控制與決策,2010,25(12)： 1891-1895,1900.

11Liu CX,He HC,Zhu ML. The study of new indiscernible relation based on flexible logic in complete information system. 2015 8th International Symposium on Computational Intelligence and Design. Hangzhou,China. 2015. 222-227.

12Pawlak Z. Rough sets. International Journal of Computer &Information Sciences,1982,11(5)： 341-356.

13薛占熬. 柔性區(qū)間邏輯及推理研究[博士學(xué)位論文]. 西安：西北工業(yè)大學(xué),2006. 1-19.

14劉城霞,何華燦. 廣義相關(guān)性基礎(chǔ)上的量化容差關(guān)系的改進(jìn). 北京郵電大學(xué)學(xué)報(bào),2015,38(5)： 28-32,41.

15胡彧,李智玲,李春偉. 一種基于區(qū)分矩陣的屬性約簡算法. 計(jì)算機(jī)應(yīng)用,2006,26(S)： 80-82.

16蔡衛(wèi)東,李凡,徐章艷,等. 基于修正差別矩陣的高效屬性約簡算法. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,35(9)：110-113.