基于柔性邏輯的區分矩陣屬性約簡算法①

侯慧欣, 劉城霞

(北京信息科技大學 計算機學院,北京 100101)

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

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

1 基本概念

1.1 粗糙集

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

1.2 屬性約簡

在粗糙集信息系統中,設R是一個等價關系簇,,如果,則稱I在等價關系簇R中是不必要的. 否則稱I在等價關系簇R中是必要的. 若R中的每一個等價關系I都是必要的,則稱R是獨立的. 屬性約簡就是在知識庫分類能力保持不變的情況下,刪除冗余屬性.

(1)D是獨立的,

則稱D是B的一個約簡. 記為：. 其中所有的必要關系組成的集合,稱為B的核,記為：.即. 核是信息系統中的核心屬性集,是所有約簡的公共部分.

1.3 區分矩陣

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

2 算法原理

(1) 首先根據信息表S構造區分矩陣M,按照公式(1)規則構造矩陣.

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

(2) 根據區分矩陣構造區分函數,規則如下：

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

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

3 算法改進

3.1 改進原理

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

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

使用T范數來表示AND關系,S范數來表示OR關系,這是泛邏輯的數學基礎. 廣義相關性被定義為h和兩個僅由h控制的兩個函數,T生成元完整簇和S生成元完整簇.把它們應用到AND運算模型和OR運算模型,我們可以得到和：

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

將T生成元完整簇放入等價運算模型

(1) Zadeh等價：

(2) 概率等價：

(3) 中心等價：

(4) 最大等價：

使用柔性邏輯中的中心等價公式：

由于x,y的取值區間只能為[0,1],所以將公式轉化為：

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

3.2 實例說明

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

為了完整的研究算法,現引入一個覆蓋算法涉及到的全部步驟的氣象表,如表1. 表中數據后的小括號內容表示對應的離散化后的結果.

表1 氣象表

表中存在2個連續屬性,分別為a2和a3. 將a2劃分為 3個區間,分別為： [6,19),[19,28),[28,39],對應離散值為3,2,1. 將a3劃分為2個區間,分別為：[28,55),[55,82),對應離散值為2,1.

傳統的區分矩陣屬性約簡算法大致分為3步：

1) 首先根據信息系統S構造區分矩陣M(S);

2) 根據區分矩陣構造區分函數;

3) 計算區分函數,將合取范式轉化為析取范式.

改進的算法對代碼改動較小,只需在構造區分矩陣時將原來的不可分辨關系判斷條件改為柔性邏輯等價關系的判斷條件即可.

表2 改進前區分矩陣

表3 改進后區分矩陣

改進前后構造的區分矩陣結果略有不同. 分析這些不同,主要有以下兩種情況：

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

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

對改進前后的算法效率進行比較,發現： 改進后的算法效率與改進前的算法效率幾乎持平,甚至在數據量逐漸增多的情況下,改進后的算法效率要低于改進前的算法效率. 而且,改進后的算法效率在構建區分矩陣部分所消耗的時間遠大于改進前的算法. 由于機器限制,只比較了具有5個屬性的數據表在100～900,1000～7000條數據等不同情況下的運行時間. 實驗結果如表4和表5.

表4 千條以內數據算法效率對比

表5 千條以上數據算法效率對比

測試硬件環境： 聯想PC,1.90 GHZ,內存2.0 GB,測試軟件環境： Microsoft Windows7 旗艦版,編程語言：Java,開發環境： MyEclipse Professional 2014.

4 結論與展望

本文實現了基于區分矩陣的屬性約簡基礎算法,并實現了利用柔性邏輯對該算法的改進,將改進前后的算法進行了內容和效率兩方面的對比并得出結論.但是本文使用的柔性邏輯等價關系只針對等區間離散化方法,對于其他的離散化方法并不適用,因此今后的研究方向是利用柔性了邏輯對其他的離散化方法進行改進,將柔性邏輯和粗糙集理論做一個更好的統一.

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

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

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

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

5高錦標. 一種改進的區分矩陣屬性約簡算法及應用. 電腦知識與技術,2009,5(8)： 1876-1877.

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

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

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

9陶志,劉慶拯,李衛民. 一種基于改進區分矩陣的屬性約簡算法. 2007中國控制與決策學術年會論文集. 無錫,中國.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薛占熬. 柔性區間邏輯及推理研究[博士學位論文]. 西安：西北工業大學,2006. 1-19.

14劉城霞,何華燦. 廣義相關性基礎上的量化容差關系的改進. 北京郵電大學學報,2015,38(5)： 28-32,41.

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

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