溫 馨,閆心怡,陳澤華+
1.太原理工大學(xué) 大數(shù)據(jù)學(xué)院,太原 030024
2.太原理工大學(xué) 電氣與動(dòng)力工程學(xué)院,太原 030024
規(guī)則提取是數(shù)據(jù)挖掘的研究熱點(diǎn)。粗糙集理論[1]與概念格理論[2]是數(shù)據(jù)處理與知識(shí)發(fā)現(xiàn)[3-6]的重要工具。近年來,眾多學(xué)者致力于兩種理論的研究并提出了不少?zèng)Q策規(guī)則提取算法[7-15],文獻(xiàn)[7]將決策信息系統(tǒng)分層粒化,在不同的粒度空間下求取粒關(guān)系矩陣,并從中獲取啟發(fā)式信息去除冗余屬性,設(shè)定終止條件實(shí)現(xiàn)決策規(guī)則的挖掘,但當(dāng)冗余屬性較多或者樣本集較大時(shí),規(guī)則約簡(jiǎn)難度增加;文獻(xiàn)[8]提出了一種從決策形式背景生成概念,進(jìn)而推導(dǎo)無(wú)冗余規(guī)則的算法,該算法在一定程度上降低了算法復(fù)雜度,在某些情況下,獲取的決策規(guī)則仍然存在冗余屬性;文獻(xiàn)[11]主要研究決策形式背景的規(guī)則獲取和屬性約簡(jiǎn)問題,基于面向?qū)ο蟾拍詈兔嫦驅(qū)傩愿拍睿岢隽嗣嫦驅(qū)ο鬀Q策規(guī)則和面向?qū)傩詻Q策規(guī)則的概念,并利用條件概念格與決策概念格外延集合的等價(jià)類關(guān)系進(jìn)行決策規(guī)則提??;文獻(xiàn)[13]為解決傳統(tǒng)的決策規(guī)則只能判斷對(duì)象是否具有某種決策屬性,以及無(wú)法準(zhǔn)確判斷決策知識(shí)的內(nèi)在性質(zhì)的問題,提出含有多個(gè)決策屬性且決策屬性取值為多值的序決策形式背景及其序決策概念格,并實(shí)現(xiàn)了基于規(guī)則不變的屬性約簡(jiǎn);文獻(xiàn)[14]利用正向尺化與反向尺化實(shí)現(xiàn)信息系統(tǒng)與形式背景之間的相互轉(zhuǎn)化,定義了多粒度標(biāo)記形式背景,并實(shí)現(xiàn)了多粒度標(biāo)記決策形式背景的規(guī)則提??;文獻(xiàn)[15]提出介粒度標(biāo)記形式背景的概念,之后基于此,給出多粒度標(biāo)記決策形式背景的介粒度知識(shí)發(fā)現(xiàn)方法,得到粗細(xì)介粒度標(biāo)記形式背景之間的決策蘊(yùn)涵誘導(dǎo)關(guān)系。
本文針對(duì)決策信息系統(tǒng),基于形式概念分析理論,將決策信息系統(tǒng)通過轉(zhuǎn)化為決策形式背景進(jìn)行決策規(guī)則提取,并提出一種基于中心概念的最簡(jiǎn)規(guī)則提取算法,該方法的提出將概念生成的過程與規(guī)則提取進(jìn)行有效融合。不必生成所有概念,即決策規(guī)則提取完畢時(shí)概念生成過程也將結(jié)束。該算法避免了傳統(tǒng)基于決策形式背景的決策規(guī)則提取算法[7,10-11]需要同時(shí)生成條件形式概念及決策形式概念的計(jì)算復(fù)雜性。決策規(guī)則的提取是本文研究的重點(diǎn),而概念的生成僅是一個(gè)條件,沒有絕對(duì)必要將所有概念全部生成。理論分析和實(shí)驗(yàn)證明體現(xiàn)出本文方法的有效性。
定義1[1](決策信息系統(tǒng))設(shè)DIS={U,C?D,V,f}是信息系統(tǒng),其中U為對(duì)象集,C為條件屬性,D為決策屬性,用V表示屬性集C?D的值域;f:U×(C?D)→V是信息函數(shù),它指定U中每個(gè)對(duì)象的屬性值。若C?D=?,則稱該信息系統(tǒng)為決策信息系統(tǒng),也稱為決策表。
定義2[1](等價(jià)類)在決策信息系統(tǒng)DIS中,?B?(C?D),定義等價(jià)關(guān)系ind(B)={(x,y)∈U×U|?b∈B,f(x,b)=f(y,b)},其中ind(B) 為屬性子集B導(dǎo)出的劃分,而產(chǎn)生的等價(jià)類記作[x]ind(B)或[x]B。
定義3[2](形式背景)形式背景可以用一個(gè)三元組T=(U,A,I)來表示,其中U表示非空有限對(duì)象集,稱為論域;A表示非空有限屬性集;I滿足I?U×A,表示形式背景的一種二元關(guān)系,(u,a)∈I(其中u∈U,a∈A)表示對(duì)象u擁有屬性a,否則(u,a)?I表示u沒有屬性a。在形式背景T=(U,A,I)中,令2U、2A分別為對(duì)象集U和屬性集A的冪集,對(duì)于任意對(duì)象集合X(X?U)和任意屬性集合B(B?A),Wille 定義了兩個(gè)映射X↑:2U→2A和B↓:2A→2U[2]:
定義4[2](形式概念)三元組T=(U,A,I)為一個(gè)形式背景,令X?U,B?A,若X↑=B且B↓=X,則稱二元組(X,B)為一個(gè)形式概念,其中X被稱為這個(gè)概念的外延,B被稱為這個(gè)概念的內(nèi)涵。為方便敘述,可將形式背景T下的所有概念存入L(T)中。記L(T)中的兩個(gè)概念為(X1,B1)、(X2,B2),若滿足條件X1?X2(或B2?B1)時(shí),則稱概念(X1,B1) 是(X2,B2) 的子概念,概念(X2,B2)是(X1,B1)的父概念??啥xL(T)中的任意兩個(gè)概念間的邏輯運(yùn)算:
為了便于理解上述邏輯運(yùn)算過程,下面將通過具體實(shí)例(例1)來詳細(xì)說明:
例1如表1 所示,形式背景T=(U,A,I),其中U={x1,x2,x3,x4},A={a1,a2,a3,a4}。
Table 1 Formal context表1 形式背景
其中概念(124,a1)與(14,a1a3)為表1 所示的形式背景中可求得的兩個(gè)概念。
針對(duì)式(3)而言有:
針對(duì)式(4)而言有:
定義5[8](決策形式背景)五元組S=(U,A,I,D,J)為一個(gè)決策形式背景,其中(U,A,I)和(U,D,J)為形式背景,U為對(duì)象集,A為條件屬性集,D為決策屬性集。
定義6[16](協(xié)調(diào)決策表)在決策信息系統(tǒng)DIS中,如果ind(C)?ind(D),則稱S為協(xié)調(diào)決策表,否則稱為不協(xié)調(diào)決策表。本文討論的是協(xié)調(diào)決策表。
中心概念是本文提出的定義,也是本文的核心內(nèi)容,本文所做的工作都將圍繞中心概念展開。中心概念同時(shí)考慮了條件屬性與決策屬性之間知識(shí)的關(guān)聯(lián)性,且具有豐富的知識(shí)內(nèi)涵。
定義7(外延)任一決策信息系統(tǒng)S可轉(zhuǎn)化成決策形式背景T=(U,A,I,D,J),記Z=A?D,對(duì)于?Z′?Z,有以下關(guān)系:
定義8(綜合概念)在一個(gè)決策形式背景S=(U,A,I,D,J)中,對(duì)于一個(gè)概念(X,B),其中X?U,B=C?d(C?A,d∈D) 且滿足C≠?,d≠?,同時(shí)X↑=B,B↓=X,此時(shí)稱(X,B)為綜合概念。
定義9(中心概念)對(duì)于一個(gè)綜合概念(X,B),其中B=C?d且滿足C↓?d↓,此時(shí)稱(X,B)為一個(gè)中心概念,中心概念包含了綜合概念中最簡(jiǎn)單的邏輯關(guān)系,直接蘊(yùn)含了決策信息系統(tǒng)中的規(guī)則信息。
定理1在決策形式背景S=(U,A,I,D,J)中(X,B)為一個(gè)中心概念,若?(X,B)∈L(T),此時(shí)可以確定一條決策規(guī)則記C→d。對(duì)于決策規(guī)則C→d,C={c1,c2,…,cn},若?ck∈{c1,c2,…,cn}s.t.{C-ck}↓?X,則稱決策規(guī)則C→d中存在冗余屬性ck。
定理2若(X,B)為一個(gè)中心概念,其中B=C?d,C={c1,c2,…,cn}且有決策規(guī)則C→d,?ci∈C,c′={c-ci},如果滿足c′↓?X,則稱決策規(guī)則C→d為最簡(jiǎn)決策規(guī)則。
證明反證法。若?ci∈C,c′={c-ci},如果滿足c′↓?X,C→d不是最簡(jiǎn)決策規(guī)則,則?cj∈C={c1,c2,…,cn}使得{C-cj}↓?X,顯然與前提相矛盾,故C→d為最簡(jiǎn)規(guī)則。
本文針對(duì)決策信息系統(tǒng)規(guī)則抽取的問題提出了一種新的概念——中心概念,中心概念是概念,但內(nèi)涵更加豐富。內(nèi)涵中不僅包含決策信息系統(tǒng)中的條件屬性C,也包含了決策屬性d,同時(shí)這兩種屬性之間存在一種邏輯關(guān)系即C↓?d↓,而這種關(guān)系成為進(jìn)行規(guī)則提取的充要條件。故一個(gè)中心概念不單滿足概念定義,且其內(nèi)涵中內(nèi)部屬性之間體現(xiàn)了決策規(guī)則。
中心概念體現(xiàn)出條件屬性與決策屬性之間的蘊(yùn)含關(guān)系,本文提出了基于中心概念的決策信息系統(tǒng)最簡(jiǎn)規(guī)則提取算法(記作算法1),其具體算法流程描述如下所示:
算法1基于中心概念的最簡(jiǎn)規(guī)則提取算法
輸入:決策信息系統(tǒng)DIS=(U,C?D,V,f)。
輸出:最簡(jiǎn)決策規(guī)則。
步驟1對(duì)完備決策表DIS進(jìn)行預(yù)處理,將其轉(zhuǎn)換成決策形式背景S=(U,A,I,D,J),記Z=A?d。
步驟2初始化n=1,Rules=?,Concept=?,Exten=?,Del=?。//Exten為外延集合,Del為被剔除概念的集合
步驟3對(duì)于z∈Z,計(jì)算n=1 次的形式概念(z↓,z↓↑),并將第一次求得的概念存入Concept。
步驟4依次判斷第n層時(shí)的概念(X,B),若C?B,d∈B,C↓?d↓且X?Exten,則Rules=Rules?{C→d},Exten=Exten?X,同時(shí)對(duì)提取完規(guī)則的概念(X,B)進(jìn)行標(biāo)記并存入Del中。
步驟5對(duì)概念集Concept進(jìn)行更新:Concept=Concept-Del。
步驟6判斷Exten是否等于U:若相等,則轉(zhuǎn)至步驟9;否則,轉(zhuǎn)至步驟7。
步驟7此時(shí)n=n+1,對(duì)當(dāng)前Concept中的所有概念按照式(3)進(jìn)行兩兩相交邏輯運(yùn)算,并記錄新產(chǎn)生的概念。
步驟8將新產(chǎn)生的概念重復(fù)步驟4~6,若Exten與U相等,則轉(zhuǎn)至步驟9;否則,轉(zhuǎn)至步驟7。
步驟9輸出Rules中的最簡(jiǎn)決策規(guī)則。
算法1 主要分為兩部分:第一步將輸入的決策信息系統(tǒng)轉(zhuǎn)化成決策形式背景,決策屬性也參與第一層形式概念的生成,根據(jù)定義9 選擇滿足條件的中心概念,并由定理1 進(jìn)行決策規(guī)則的提取;第二步判斷Exten中的元素是否覆蓋整個(gè)論域,若沒有覆蓋,則在下一層概念生成之前將前一層的中心概念剔除,剩余概念集作為基概念再參與下一層的生成運(yùn)算,然后重復(fù)第一步中的規(guī)則提取過程,否則重復(fù)第二步繼續(xù)提取規(guī)則,直到Exten中的元素覆蓋整個(gè)論域。
在完備決策信息系統(tǒng)DIS=(U,C?D,V,f) 中將DIS轉(zhuǎn)化成決策形式背景S=(U,A,I,D,J),對(duì)于?u∈U,?p∈A?D在決策形式背景S中滿足(u,p)∈I的屬性值共有|U||A+D|個(gè)。求概念每一層的時(shí)間復(fù)雜度的基數(shù)為O(|U|2|A+D|2),共有l(wèi)b(|U||A+D|)層。假設(shè)算法共產(chǎn)生N條決策規(guī)則即N個(gè)中心概念,而該算法生成概念的過程中要剔除提取完規(guī)則的中心概念,其復(fù)雜度為O(N-1)。并且如果Exten已經(jīng)覆蓋整個(gè)論域,算法執(zhí)行完畢,但實(shí)際上有可能并沒有將所有的概念全部生成出來。故整個(gè)算法的復(fù)雜度要小于等于O(|U||A+D|)+O(|U|2|A+D|2lb(|U||A+D|))+O(N-1)。
下面通過實(shí)例來詳細(xì)說明算法1 的執(zhí)行流程。
例2決策信息系統(tǒng)DIS=(U,C?D,V,f),其中論域U={x1,x2,…,x8},條件屬性集C={a,b,c},決策屬性集D=j5i0abt0b。如表2 所示。
Table 2 Decision information system表2 決策信息系統(tǒng)
將表2 的決策信息系統(tǒng)轉(zhuǎn)化為決策形式背景S=(U,A,I,D,J),如表3 所示。
Table 3 Decision formal context表3 決策形式背景
對(duì)于?z∈Z,由(z↓,z↓↑)可求取第一層概念(其中外延元素簡(jiǎn)寫為數(shù)字,例如概念(x1x3x7,a1) 簡(jiǎn)寫為(137,a1)):(137,a1),(24,a2),(568,a3),(15,b0c0),(3478,b2),(26,b1d3),(278,c1),(13456,c0),(58,a3d1),(14,c0d2),(2367,d3)。從第一層概念中選取滿足定義9 的中心概念并進(jìn)行規(guī)則提取,如表4 所示,其中(26,b1d3)滿足條件,此時(shí)可進(jìn)行決策規(guī)則提取,此時(shí)Exten中的元素為{2,6},沒有覆蓋整個(gè)論域元素,因此需計(jì)算下一層概念。
Table 4 Rule list of the first layer of central concept表4 第一層中心概念的規(guī)則列表
生成第二層概念時(shí),其所需的概念是將(26,b1d3)從第一層剔除后得到的概念(137,a1),(24,a2),(568,a3),(15,b0c0),(3478,b2),(278,c1),(13456,c0),(58,a3d1),(14,c0d2),(2367,d3)。對(duì)上述概念進(jìn)行相交運(yùn)算可得到第二層概念(1,a1b0c0d2),(37,a1b2d3),(5,a3b0c0d1),(13,a1c0),(4,a2b2c0d2),(8,a3b2c1d1),(7,a1b2c1d3),(2,a2b1c1d3),(78,b2c1),(56,a3c0),(34,b2c0),(6,a3b1c0d3),(27,c1d3),(36,c0d3)。從 第二層中選取滿足定義9 的中心概念并進(jìn)行規(guī)則提取,如表5 所示,其中(1,a1b0c0d2),(5,a3b0c0d1),(37,a1b2d3),(4,a2b2c0d2),(8,a3b2c1d1)這5 個(gè)概念滿足條件,此時(shí)可進(jìn)行規(guī)則提取,此時(shí)在Exten集合中可添加元素集{1,3,4,5,7,8},故此時(shí)Exten={1,2,3,4,5,6,7,8}。至此,Exten中的元素覆蓋整個(gè)論域,規(guī)則提取完畢。
Table 5 Rule list of the second layer of central concept表5 第二層中心概念的規(guī)則列表
下面將分析算法產(chǎn)生的規(guī)則中是否存在冗余屬性:
(1)對(duì)于規(guī)則b1→d3,根據(jù)定義7,?↓={1,2,3,4,5,6,7,8}?{2,3,6,7},故規(guī)則b1→d3不存在冗余屬性。
(2)對(duì)于規(guī)則a1b0c0→d2,根據(jù)定義7,故屬性c0為冗余屬性,因此規(guī)則a1b0c0→d2可化簡(jiǎn)為a1b0→d2。
(3)對(duì)于規(guī)則a3b0c0→d1,根據(jù)定義7,(a3b0)↓={5}?{5,8},,故屬性c0為冗余屬性,因此規(guī)則a3b0c0→d1可化簡(jiǎn)為a3b0→d1。
(4)對(duì)于規(guī)則a1b2→d3,根據(jù)定義7,{2,3,6,7},,故規(guī)則a1b2→d3不存在冗余屬性。
(5)對(duì)于規(guī)則a2b2c0→d2,根據(jù)定義7,(a2b2)↓={4}?{1,4},因此規(guī)則a2b2c0→d2可化簡(jiǎn)為a2b2→d2。
(6)對(duì)于規(guī)則a3b2c1→d1,根據(jù)定義7,(a3b2)↓={8}?{5,8},因此規(guī)則a3b2c1→d1可化簡(jiǎn)為a3b2→d1。
本文算法實(shí)現(xiàn)了在生成概念的同時(shí)能夠進(jìn)行決策規(guī)則提取,直到外延集合可覆蓋整個(gè)論域?yàn)橹埂T诖诉^程中可能不需要生成所有概念就可將全部決策規(guī)則提取完畢。生成下一層概念時(shí)需剔除上一層概念中的中心概念,這樣可減少冗余概念的生成,同時(shí)降低了算法復(fù)雜性。本算法所生成的中心概念能夠直觀體現(xiàn)出決策規(guī)則,相較傳統(tǒng)方法中生成的單一形式概念涵蓋的內(nèi)容更加豐富。如圖1 所示,圖中圓圈為例2 中的全體概念,其中L1~L12淺灰色標(biāo)注的概念為無(wú)法進(jìn)行規(guī)則提取的一般概念(不包括決策內(nèi)涵的概念),L13~L26的深灰色圓圈為內(nèi)涵中既包括條件屬性又包括決策屬性的綜合概念,其中用網(wǎng)狀節(jié)點(diǎn)標(biāo)注的概念是決策規(guī)則的中心概念,而用黑色標(biāo)注的則為實(shí)際進(jìn)行規(guī)則提取過程中無(wú)需生成的概念。6 個(gè)網(wǎng)狀中心概念可代表生成的6 條決策規(guī)則。
圖2 為表2 按照傳統(tǒng)方法需分別得到條件形式概念與決策形式概念的Hasse 圖,黑色虛線相連的概念體現(xiàn)出了條件概念與決策概念之間的包含關(guān)系,紅色實(shí)線則體現(xiàn)出得到的決策規(guī)則。
從圖1 可以看出,本文提出的綜合概念、中心概念以及所要提取的決策規(guī)則都可以在一張Hasse圖中清晰地表現(xiàn)出來,概念節(jié)點(diǎn)能夠體現(xiàn)出條件與決策知識(shí)的關(guān)聯(lián)性。符合人類綜合考慮處理問題的特性。針對(duì)傳統(tǒng)基于決策形式背景規(guī)則提取的方法,其構(gòu)造出的Hasse圖所描述的相關(guān)信息則會(huì)復(fù)雜很多。
Fig.1 Hasse diagram of formal decision context圖1 決策形式背景概念Hasse圖
Fig.2 Hasse diagram of conditional concept and decision concept and their relationship圖2 條件概念與決策概念及其關(guān)系Hasse圖
通過選取以下8 組UCI 數(shù)據(jù)集來測(cè)試該算法的正確性以及有效性。利用Rosetta 軟件對(duì)數(shù)據(jù)集進(jìn)行離散化處理。然后,分別應(yīng)用本文算法、文獻(xiàn)[7]中的算法、文獻(xiàn)[8]中的算法和文獻(xiàn)[9]中的算法對(duì)數(shù)據(jù)集進(jìn)行測(cè)試,以上算法均將數(shù)據(jù)集作為輸入,提取到的所有規(guī)則作為輸出,記錄各算法所得到的約簡(jiǎn)規(guī)則個(gè)數(shù)和規(guī)則長(zhǎng)度。其中對(duì)于文獻(xiàn)[8]中的算法需要先將決策信息系統(tǒng)轉(zhuǎn)化為決策形式背景來處理。最終實(shí)驗(yàn)對(duì)比結(jié)果如表6~表8 所示。
正確識(shí)別率[17]是由獲取的規(guī)則集對(duì)每個(gè)數(shù)據(jù)集進(jìn)行整體識(shí)別的正確概率。具體過程:每個(gè)數(shù)據(jù)集中各隨機(jī)選取50%作為訓(xùn)練樣本,分別應(yīng)用各算法對(duì)訓(xùn)練樣本進(jìn)行規(guī)則獲取并記錄各自的規(guī)則集,然后利用獲取到的規(guī)則集對(duì)各數(shù)據(jù)集整體進(jìn)行識(shí)別。
實(shí)驗(yàn)分析:由上表能夠看出,該算法在相同數(shù)據(jù)集上較其他算法而言,所提取到的決策規(guī)則個(gè)數(shù)更少,同時(shí)規(guī)則長(zhǎng)度較其他算法更短,對(duì)于識(shí)別率,本文算法與文獻(xiàn)[7]中的算法相當(dāng),略高于文獻(xiàn)[8]、文獻(xiàn)[9]中的算法。這可說明該算法所得到的規(guī)則集具有更強(qiáng)的表示能力,本文算法所得到的中心概念所涵蓋的知識(shí)更加豐富,其不僅體現(xiàn)出了條件屬性與決策屬性之間的邏輯關(guān)系,同時(shí)中心概念還是形式概念與決策規(guī)則緊密結(jié)合的綜合體。
Table 6 Comparison of rule number表6 規(guī)則個(gè)數(shù)對(duì)比
Table 7 Comparison of rule length表7 規(guī)則長(zhǎng)度對(duì)比
Table 8 Comparison of recognition rate表8 識(shí)別率對(duì)比
本文將決策信息系統(tǒng)作為研究對(duì)象,將決策信息系統(tǒng)轉(zhuǎn)化成決策形式背景,決策形式背景中的決策屬性參與概念的生成,內(nèi)涵中包含決策屬性的概念被定義為綜合概念,其中滿足C↓?d↓的綜合概念被定義為中心概念。中心概念蘊(yùn)含了決策信息系統(tǒng)中最簡(jiǎn)規(guī)則的關(guān)鍵信息。并且包含中心概念的Hasse圖具有更加豐富且明確的意義。因此,一個(gè)決策信息系統(tǒng)的規(guī)則提取過程將轉(zhuǎn)化為中心概念的生成以及選擇的過程。此時(shí)中心概念具有豐富的研究意義。最后通過實(shí)驗(yàn)分析與對(duì)比說明該算法的正確性與有效性。本文算法有以下特點(diǎn):(1)提出的中心概念直接蘊(yùn)含了最簡(jiǎn)決策規(guī)則,較經(jīng)典形式概念所表達(dá)的知識(shí)更加豐富。(2)該算法相較于其他算法來說具有較高的識(shí)別率且所提取到的規(guī)則具有較強(qiáng)的表示能力。并且針對(duì)協(xié)調(diào)決策信息系統(tǒng)而言,通過求取中心概念提取的決策規(guī)則具有完備性,能夠覆蓋信息系統(tǒng)中所有非冗余規(guī)則。文獻(xiàn)[18]將粒計(jì)算與概念格相結(jié)合,提出了粒概念,從認(rèn)知計(jì)算的角度研究了基于粒計(jì)算的認(rèn)知概念學(xué)習(xí)。所有經(jīng)典形式概念能通過粒概念全部求得,同時(shí)這種求取概念的方法將極大降低計(jì)算復(fù)雜性。在今后工作當(dāng)中可嘗試通過將粒概念與中心概念相結(jié)合,進(jìn)一步優(yōu)化本文算法。同時(shí),可將本文算法拓展到不協(xié)調(diào)不完備決策信息系統(tǒng)的知識(shí)獲取中,今后也可將其應(yīng)用于語(yǔ)義表示及其推理,信息檢索及智能推薦,以上相關(guān)研究正在進(jìn)行中。