董春游, 黃春楠

(1.黑龍江科技學(xué)院 研究生學(xué)院;2.黑龍江科技學(xué)院 信息網(wǎng)絡(luò)中心,哈爾濱 150027)

改進(jìn)的差別矩陣屬性約簡(jiǎn)方法

董春游1, 黃春楠2

(1.黑龍江科技學(xué)院 研究生學(xué)院;2.黑龍江科技學(xué)院 信息網(wǎng)絡(luò)中心,哈爾濱 150027)

針對(duì)目前屬性約簡(jiǎn)方法計(jì)算量過大、復(fù)雜度高的問題,在已有差別矩陣定義和求核方法的基礎(chǔ)上,根據(jù)二元決策表所特有的性質(zhì),提出一種新的差別矩陣的定義,將一個(gè)大的差別矩陣分化成兩個(gè)小矩陣。與建立一個(gè)差別矩陣的方法相比,改進(jìn)的差別矩陣方法減少了矩陣中元素的比較次數(shù)。數(shù)據(jù)分析表明,該方法在改進(jìn)差別矩陣定義的同時(shí)簡(jiǎn)化了計(jì)算過程,提高了運(yùn)算效率。

決策表;核;屬性約簡(jiǎn);差別矩陣;差別函數(shù)

0 引 言

隨著信息化時(shí)代的發(fā)展,人們?cè)诟鱾€(gè)領(lǐng)域獲取的信息急劇膨脹,這些數(shù)據(jù)的不確定性也更加顯著。如何從這些模糊的、不精確的、不完整的大量信息中獲取有價(jià)值的知識(shí)已經(jīng)對(duì)智能信息處理提出了嚴(yán)峻的挑戰(zhàn)。粗糙集理論應(yīng)運(yùn)而生,它不僅能夠處理復(fù)雜系統(tǒng)中的數(shù)據(jù)和信息,也可以處理模糊的和不精確的信息[1]。在粗糙集理論中,屬性約簡(jiǎn)是知識(shí)獲取的關(guān)鍵步驟,也是粗糙集理論和應(yīng)用研究的焦點(diǎn)問題之一[2]。

目前,已經(jīng)有很多屬性約簡(jiǎn)的方法[3-4]。其中, Hu提出的基于差別矩陣的求核方法是經(jīng)典的屬性約簡(jiǎn)方法之一。該方法減少了計(jì)算量,提高了求解核的效率。但在某些情況下不能正確得到核。于是有學(xué)者在此基礎(chǔ)上提出了新的差別矩陣[5-7],但計(jì)算量過大。文獻(xiàn)[1]提出的基于分體策略和差別矩陣的決策表屬性約簡(jiǎn)方法在糾正了 Hu方法錯(cuò)誤的同時(shí),有效的降低了計(jì)算復(fù)雜度。對(duì)于實(shí)際需求中比較大的決策表,這個(gè)方法還可以進(jìn)一步的改進(jìn),因此,筆者針對(duì)該問題進(jìn)行了研究。

1 粗糙集的基本理論

2 改進(jìn)的差別矩陣

波蘭科學(xué)家 A.Skowron于 1991年首次提出利用差別矩陣來表示知識(shí)。實(shí)踐證明這種方法在知識(shí)表達(dá)系統(tǒng)中求核和約簡(jiǎn)以及在其它概念的表示和計(jì)算等方面有很多優(yōu)點(diǎn),但是該方法在某些時(shí)候會(huì)產(chǎn)生錯(cuò)誤的結(jié)果。在文獻(xiàn)[1]中分析了 Skowron差別矩陣對(duì)不相容決策表求相對(duì)核及約簡(jiǎn)時(shí)可能會(huì)產(chǎn)生錯(cuò)誤結(jié)果的原因。Skowron差別矩陣沒有考慮到當(dāng)決策表的不相容度大于某一確定閾值后,可能會(huì)造成無法正確分類,因此需要忽略不相容對(duì)象組之間的差異。而不相容的樣本集本身對(duì)決策表的分類能力會(huì)產(chǎn)生一定的影響,若忽略其影響,則會(huì)使約簡(jiǎn)后的決策表無法完整地表達(dá)原始決策表的分類能力,因此在進(jìn)行屬性約簡(jiǎn)時(shí)有必要充分考慮不相容樣本集對(duì)決策表的分類能力。筆者正是基于以上原則提出了一種改進(jìn)的差別矩陣的方法。該方法的總體思想是首先應(yīng)用分體策略將不相容決策表中的對(duì)象分為兩部分:相容對(duì)象和不相容對(duì)象。然后根據(jù)不同的對(duì)象采取不同的比較方式分情況進(jìn)行討論,最后求得決策表的屬性約簡(jiǎn)。

2.1 差別矩陣定義

如上所述,基于分體策略的屬性約簡(jiǎn)方法可以在盡可能的保持原始決策表分類能力不變的前提下對(duì)決策表進(jìn)行屬性約簡(jiǎn),因此很多學(xué)者在約簡(jiǎn)決策表時(shí)均是基于這一思想,只是不同的學(xué)者有各自不同的方法[5-7]。例如:文獻(xiàn) [1]中建立的基于分體策略的差別矩陣充分考慮了不相容樣本集對(duì)決策表分類能力的影響,而且在一定程度上也提高了運(yùn)算效率,但若遇到不相容對(duì)象較少而絕大多數(shù)是相容對(duì)象的情況、或是決策表比較大,對(duì)象非常多等情況,這種方法在運(yùn)算效率上就會(huì)受到影響。而文獻(xiàn)[8]中提出的方法在給出差別矩陣的定義時(shí)僅考慮了相容對(duì)象之間的比較和相容對(duì)象與不相容對(duì)象之間的比較,忽略了相容與不相容對(duì)象之間當(dāng)決策屬性相等時(shí)兩個(gè)對(duì)象的比較,雖然約簡(jiǎn)后的結(jié)果是一樣的,卻增加了矩陣規(guī)模。因此筆者在文獻(xiàn)[1]的基于分體策略的差別矩陣定義基礎(chǔ)上,結(jié)合二元矩陣所特有的性質(zhì),提出了一種新的改進(jìn)的基于分體策略的差別矩陣定義。

定義 5 改進(jìn)的基于分體策略的差別矩陣

由基于分體策略的差別矩陣定義[1]可以發(fā)現(xiàn):當(dāng)兩個(gè)樣本都屬于不相容決策表時(shí),或兩個(gè)樣本都在相容決策表中,而且其決策屬性相同時(shí),這兩個(gè)樣本比較的結(jié)果都是?。因此,定義 5建立的差別矩陣忽略了以上比較,簡(jiǎn)化了矩陣的規(guī)模。

2.2 差別矩陣的屬性約簡(jiǎn)

根據(jù)定義 5建立差別矩陣時(shí),首先將決策表中的對(duì)象按其相容性分為兩部分:完全相容子表U1和完全不相容子表U2,然后針對(duì)兩個(gè)子表分別建立差別矩陣。

第一個(gè)差別矩陣的構(gòu)造方法為:將U1中的對(duì)象作為差別矩陣的行,再將U2中的對(duì)象作為差別矩陣的列,根據(jù)式(1)依次計(jì)算出差別矩陣中的元素。需要注意的是:建立矩陣時(shí)比較的是兩個(gè)對(duì)象的條件屬性,因此每一組不相容對(duì)象組中只保留一個(gè)對(duì)象即可,忽略其余對(duì)象不會(huì)影響差別矩陣的完整性。

第二個(gè)差別矩陣比較U1中的對(duì)象。根據(jù)定義5按決策屬性的不同將U1中的對(duì)象分為兩類U11和U12,U11為差別矩陣的行,U12為差別矩陣的列,構(gòu)造矩陣。再根據(jù)式(2)計(jì)算出第二個(gè)矩陣的元素。

根據(jù)定理 1和差別函數(shù)的性質(zhì) 2可知,兩個(gè)差別矩陣中所有單個(gè)屬性元素組成的集合就是決策表的相對(duì)核。根據(jù)定理 2和差別矩陣的性質(zhì) 1及 3可知,差別矩陣所對(duì)應(yīng)的合取范式經(jīng)過邏輯運(yùn)算轉(zhuǎn)化后得到的極小析取范式中的每個(gè)Lk都是該決策表的一個(gè)屬性約簡(jiǎn)。但在求核后會(huì)發(fā)現(xiàn)如果合取表達(dá)式比較復(fù)雜,計(jì)算過程會(huì)非常繁瑣,因此可以利用合取析取邏輯運(yùn)算特點(diǎn)對(duì)方法做進(jìn)一步改進(jìn),進(jìn)而求出決策表的屬性約簡(jiǎn)。具體步驟為:

(1)根據(jù)定理 1和差別函數(shù)的性質(zhì) 2得到?jīng)Q策表的相對(duì)核。

(2)將差別矩陣中包含相對(duì)核屬性的元素的值修改為0。

(3)根據(jù)定理 2將矩陣中剩余元素的合取表達(dá)式轉(zhuǎn)化為析取范式,最終得到?jīng)Q策表的屬性約簡(jiǎn)。

3 實(shí)例分析

以某礦區(qū)突出點(diǎn)瓦斯參數(shù)統(tǒng)計(jì)表中的一組檢驗(yàn)瓦斯突出的數(shù)據(jù)(表 1)為例。對(duì)表 1中具有連續(xù)型的屬性值離散化,再對(duì)其應(yīng)用文中提出的改進(jìn)的差別矩陣屬性約簡(jiǎn)方法進(jìn)行屬性約簡(jiǎn)。為了凸顯屬性約簡(jiǎn)的過程和效果,只取原表中的部分?jǐn)?shù)據(jù)進(jìn)行處理。其中,共有 10個(gè)對(duì)象和 5個(gè)屬性,C={a,b,c, d}為條件屬性,e為決策屬性。a為標(biāo)高,m;b為突出強(qiáng)度,t;c為瓦斯量,m3/t;d為瓦斯壓力,MPa。e值為 1時(shí)表示突出,0表示壓出。對(duì)表 1進(jìn)行離散化處理后得到表2。

表1 某煤礦瓦斯突出參數(shù)決策表Table 1 Decision table of coa lm ine outburst parameters

表2 離散化后的決策表Table 2 D iscretized decision table

根據(jù)文獻(xiàn)[1]建立的差別矩陣為

根據(jù)定理 1和性質(zhì) 2可得決策表的相對(duì)核為K(C)={b,c}。計(jì)算相對(duì)約簡(jiǎn)前,先將兩個(gè)差別矩陣中所有包含相對(duì)核屬性元素的值都改為“0”。最后這兩個(gè)矩陣只包含兩個(gè)取值為非“0”的元素,而且都是{a,d},將非“0”元素轉(zhuǎn)化為邏輯公式并最終化簡(jiǎn)得:L′∨(Λ)=a∨d,將核屬性加入到各合取項(xiàng)中得到的結(jié)果為:(a∧b∧c)∨(b∧c∧d)。

從實(shí)例中可以發(fā)現(xiàn):文獻(xiàn)[1]和[8]的方法所得到的核和約簡(jiǎn)與文中得到的結(jié)論相同,這也驗(yàn)證了三種方法都可以得到正確的結(jié)果。但對(duì)比三個(gè)差別矩陣,可以發(fā)現(xiàn)文獻(xiàn)[1]共做了 21次比較,文獻(xiàn)[8]做了 36次比較,而根據(jù)文中建立的差別矩陣僅做了16次比較。這是因?yàn)楦鶕?jù)文獻(xiàn)[1]建立的矩陣將所有可比較的樣本都一一進(jìn)行了比較,根據(jù)文獻(xiàn)[8]提出的矩陣進(jìn)行比較時(shí)將相容樣本集中的每個(gè)樣本都和不相容樣本集中的每個(gè)樣本進(jìn)行了一次比較。而文中提出的矩陣則忽略了決策屬性相同的相容樣本之間的比較,這樣就減少了矩陣中?的數(shù)量。文中給出的實(shí)例僅有 10個(gè)樣本,就減少了 5次比較次數(shù),而現(xiàn)實(shí)數(shù)據(jù)的樣本可能多達(dá)幾千個(gè),若依照文中提出的方法會(huì)大量減少比較次數(shù)。因此,文中的方法更能提高運(yùn)算效率。

4 結(jié)束語

在粗糙集理論中,求核及相對(duì)約簡(jiǎn)的計(jì)算都是非常關(guān)鍵的步驟[9-10]?；谇叭说难芯?文中對(duì)核屬性本質(zhì)及約簡(jiǎn)過程進(jìn)行分析,提出了新的差別矩陣的定義和屬性約簡(jiǎn)的方法,建立了一種更簡(jiǎn)潔的差別矩陣,有效的降低了計(jì)算代價(jià)。

[1] 苗奪謙,李道國(guó).粗糙集理論、方法與應(yīng)用[M].北京:清華大學(xué)出版社,2008.

[2] 楊 明,孫志輝.改進(jìn)的差別矩陣及其求核方法[J].復(fù)旦學(xué)報(bào):自然版,2004,43(5):865-868.

[3] 夏克文,沈鈞毅,李昌彪.樣本信息處理中一種屬性約簡(jiǎn)方法的研究[J].西安交通大學(xué)學(xué)報(bào),2005,39(6):558-561.

[4] 王宗軍,李紅俠,鄧曉嵐.粗糙集理論研究的最新進(jìn)展及發(fā)展趨勢(shì)[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版,2006, 28(1):43-48,52.

[5] 梁吉業(yè),李德玉.信息系統(tǒng)中的不確定性與知識(shí)獲取[M].北京:科學(xué)出版社,2005.

[6] 周江衛(wèi),馮博琴,劉 洋.粗糙集高效遺傳約簡(jiǎn)算法[J].西安交通大學(xué)學(xué)報(bào),2007,41(4):444-447.

[7] 王 剛.基于粗糙集的數(shù)據(jù)約簡(jiǎn)算法研究與應(yīng)用[D].合肥:合肥工業(yè)大學(xué),2007.

[8] 張振琳,黃 明.改進(jìn)的差別矩陣及其求核方法[J].大連交通大學(xué)學(xué)報(bào),2008,29(4):79-82.

[9] 張文修,梁 怡,吳偉志.信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M].北京:科學(xué)出版社,2003.

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

[11] 劉志民.基于最大外權(quán)重的一種啟發(fā)式屬性約簡(jiǎn)算法[J].河北工程大學(xué)學(xué)報(bào):自然科學(xué)版,2008,25(3):110-112.

Improved method of discernibility matrix and attributes reduction

DONG Chunyou1,HUANG Chunnan2
(1.Graduate School,Heilongjiang Institute of Science and Technology; 2.Information Network Center,Heilongjiang Institute of Science and Technology,Harbin 150027,China)

W ith a view to eliminating too much calculation and greater complexity due to current method of attribute reduction,this paper proposes a new definition of discernibilitymatrix,based on discernibilitymatrix and the method of computing core,and according to the special quality of binary decision table.The improved method of forming discernibilitymatrix involves changing a complexmatrix into two simple ones and gives fewer times of elements comparison than only one matrix.The analysis of the given data shows that the method improves the definition of discernibility matrix with accompanying simplification of the algorithm and enhancement of calculation efficiency.

decision table;core;attributes reduction;discernibilitymatrix;discernibility function

TP301.6

A

1671-0118(2010)02-0155-04

2010-02-14

董春游(1962-),男,吉林省長(zhǎng)春人,教授,博士,研究方向:人工智能與決策支持系統(tǒng),E-mail:chunyou_dong@163.com。

(編輯王 冬)