多決策形式背景快速規(guī)則提取算法

尚子豪,陳澤華

(太原理工大學 大數(shù)據(jù)學院,山西 太原 030024)

0 引言

形式概念分析理論是由德國Wille教授于1982年提出的一種基于形式背景進行數(shù)據(jù)分析和知識表示的數(shù)學工具[1],被廣泛用于規(guī)則提取方面的研究,并取得了豐富的成果[2-4]。

現(xiàn)實生活中,數(shù)據(jù)往往具有多粒度、多層次的結構[5-6],因此從多個角度、多個層次分析問題,可獲得對問題更加合理、更加滿意的求解結果。在規(guī)則提取中,過去的研究主要集中在決策屬性為單粒度下，對粒計算模型進行問題求解,從而潛在地丟失了復雜問題中多角度信息對問題求解的貢獻。構造多粒度決策來融合單粒度信息,并充分利用不同粒度之間的關系,可以得到具備更強表示能力的規(guī)則。

近年來,多粒度決策下的規(guī)則提取取得了一定的進步。文獻[7]提出了基于決策形式背景的非冗余決策規(guī)則提取算法,對比了在決策規(guī)則與粒度規(guī)則下的屬性約簡效率。文獻[8]研究了形式背景中粒度約簡與優(yōu)勢約簡之間的關系,提出了一種基于優(yōu)勢關系和布爾推理的粒度約簡算法。文獻[9]提出了分布屬性約簡概念和最大分布屬性約簡,結合可辨矩陣來計算屬性權值,解決了不一致決策形式背景下的屬性約簡問題。文獻[10]引入了決策蘊含正則基的概念,給出了一種決策形式背景下的規(guī)則推理算法。文獻[11]以一種基于圖論的新框架來研究形式概念分析中粒度約簡問題,提出了兩種形式概念分析中粒度約簡的啟發(fā)式算法,并驗證了在多決策形式背景下的規(guī)則提取具有較高效率。

多數(shù)基于形式背景的規(guī)則提取算法是先由形式背景生成形式概念,再由形式概念提取規(guī)則。大量文獻[12-15]表明,形式概念的生成是一個復雜的過程,而且根據(jù)形式概念進行規(guī)則提取存在冗余信息,其冗余體現(xiàn)在概念的內涵存在冗余屬性。本文以多決策形式背景為研究對象,定義并討論了形式向量及其性質,提出了一種多決策形式背景規(guī)則提取的形式向量算法。算法通過求取不同屬性粒度下的條件形式向量和決策形式向量來構建樹形拓撲圖有利于可視化形式向量的生成過程,并按照本文提出的定理計算樹形拓撲圖中不同深度下的條件形式向量與決策形式向量間的關系進而提取規(guī)則,本文算法適用于一致不一致決策形式背景，并通過理論證明、算例講解、對比實驗說明了所提算法的正確性、有效性與快速性。

定義1[16]形式背景可以用一個三元組T=(U,A,I)來表示,其中U表示非空有限對象集,A表示非空有限屬性集,I滿足I?U×A,表示形式背景的一種二元關系。對于?xi∈U,?a∈A,xiIa表示對象xi具有屬性a,否則表示xi不具有屬性a。

決策形式背景可以用一個五元組DT=(U,C,I,D,J)來表示,其中(U,C,I)和(U,D,J)分別為一個形式背景,U是對象的非空有限集合,C為條件屬性集,D為決策屬性集,且C∩D=φ。

定義2擴展關系IF。形式背景T=(U,A,I),xi∈U,對于?B?A,若對于?b∈B,均存在xiIb,則對象xi與屬性集合B滿足擴展關系IF,表示為xiIFB。

定義3形式向量。形式背景T=(U,A,I),其中,U={x1,x2,…,xm},|U|=m,對任意?B?A,其形式向量由一組長度為m的二進制數(shù)構成,表示為B(P),其中,|U|表示集合U中的元素個數(shù)。為方便敘述,用(U,A,I)表示形式背景T下的全部形式向量。那么,對于決策形式背景DT=(U,C,I,D,J),條件屬性生成的全體形式向量用(U,C,I)表示,決策屬性生成的全體形式向量用(U,D,J)表示,分別稱作條件形式向量和決策形式向量。其中:

P=(p1,…,pi,…,pm),

(1)

(2)

定義4形式子集。形式背景T=(U,A,I),對于?B?A,FB={xi|xiIFB,xi∈U},每一個形式向量B(P)對應一個形式子集FB。

性質1對于?B1,B2?A,若FB1∩FB2=φ,則B1(P)∩B2(P)=0,反之亦然。

證明假設FB1∩FB2=φ,根據(jù)定義4可知FB1={xi|xiIFB1,xi∈U},FB2?{xj|xjIFB1,xj∈U}。根據(jù)定義3,顯然有B1(P)∩B2(P)=0,即B1(P)∩B2(P)不覆蓋論域中任何元素。

定義5知識粒度K。形式背景T=(U,A,I),對于?B(P)∈(U,A,I),定義形式向量B(P)的知識粒度為:

K=|B|,

(3)

其中,|B|表示形式向量B(P)中的屬性個數(shù)。

定義6決策形式背景DT=(U,C,I,D,J)中,B1′∪B2′?C為條件屬性集合的子集,定義如下運算:若B1′∪B2′=B3′,則B3′(P)=B2′(P)∩B1′(P)。其中,B3′(P)稱為B1′(P)和B2′(P)的條件子向量,后者稱為B3′(P)的條件父向量。

在條件形式向量中,若B2′(P)是B1′(P)的條件子向量,則B1′(P)具有較少的條件屬性、更多的論域對象,其描述的知識更為具體;而B2′(P)具有較多的條件屬性、較少的論域對象,其描述的知識更為抽象。同時,根據(jù)定義6可以構建條件形式向量的樹形拓撲圖。

假設條件樹形拓撲圖的深度用l表示,則單屬性條件形式向量所在層的深度為l=1,其條件子向量所在層的深度l=2,以此類推。

定義7利用決策形式向量可以構建決策樹形拓撲圖,假設決策樹形拓撲圖的深度用l′表示,定義最大決策屬性粒度下的非零決策形式向量,所在層深度l′=1。比第一層決策形式向量屬性粒度少1的全部決策形式向量所在層深度l′=2,以此類推。

由于決策樹形拓撲圖中每一層決策形式向量的屬性粒度都比上一層的少1,故最后一層決策形式向量的屬性粒度是1。

說明由于0向量不具備辨識規(guī)則的能力,故后續(xù)圖中已略去0向量節(jié)點。

定理1設決策形式背景DT=(U,C,I,D,J),對于?Bx(P)∈(U,C,I)和?By(P)∈(U,D,J),若?p∈(By(P)-Bx(P)),滿足p≠-1,則形式向量Bx(P)和By(P)可以構成一條確定性規(guī)則,表示為Bx→By。

證明對于?Bx(P) ?(U,C,I)和?By(P) ?(U,D,J),若存在?p∈(By(P)-Bx(P)),滿足p≠-1;根據(jù)形式向量的定義可知,必然不存在Bx(P)中的1與By(P)中的0對應,即形式子集滿足關系FBx?FBy;另外,若Bx(P)≠0,則必然存在Bx(P)中的1與By(P)中的1對應,條件形式向量對應一組決策形式向量。條件形式向量可以辨識決策形式向量中的部分論域元素,進而構成一條確定性規(guī)則。

性質2決策形式背景DT=(U,C,I,D,J),若條件父向量可以確定一條規(guī)則,則與其相關的所有條件子向量都是冗余的。

證明設B1(P),B2(P),B3(P)∈(U,C,I),其中,B3(P)是B1(P)和B2(P)的條件子向量,By(P)∈(U,D,J),且存在規(guī)則rule1=B1→By。根據(jù)定理1可知,FB1?FBy;同時,由定義4和定義6可知FB3=FB1∩FB2,則FB3?FB1,進而可知FB3?FBy。此時,若B3(P)=0,則B3(P)不具備規(guī)則辨識能力,B3(P)是冗余的;若B3(P)≠0,則B3(P)與By(P)可構成一條確定性規(guī)則rule2,由于FB3?FB1,則rule2所覆蓋的論域對象是rule1所覆蓋論域對象的子集,rule2是冗余規(guī)則,所以B3(P)是冗余的。

定義8啟發(fā)式算子Rel。決策形式背景DT=(U,C,I,D,J),設Bx(P)∈(U,C,I),By(P)∈(U,D,J),且有Bx→By,則可定義條件形式向量Bx(P)的Rel值為:

(4)

它反映了條件形式向量能夠正確識別決策形式向量中論域元素的個數(shù)。

性質3決策形式背景DT=(U,C,I,D,J),設B1(P),B2(P)∈(U,C,I),By(P)∈(U,D,J),且有B1→By,B2→By。若:

Rel(B1(P))>Rel(B2(P)),

(5)

s.t.K(B1(P))=K(B2(P)),

(6)

則條件形式向量B1(P)的規(guī)則辨識能力強于條件形式向量B2(P)。

證明根據(jù)定義8,若Rel(B1(P))>Rel(B2(P)),則B1(P)比B2(P)擁有更多的非零元素。即B1(P)可以覆蓋更多的論域元素,因此B1(P)的規(guī)則辨識能力更強。

1 多決策形式背景規(guī)則提取的形式向量算法

1.1 算法描述

基于形式向量的性質,提出一種多決策形式背景的最簡規(guī)則提取算法,其算法步驟如表1所示。

1.2 復雜性分析

對于決策形式背景DT=(U,C,I,D,J),本文算法的核心在于求取形式向量,除第一層單屬性條件形式向量外,其余各層條件形式向量按照定義6層層計算而得,因此在最壞的情況下生成全部條件形式向量所需要的時間復雜度為O(2|C|-|C|-1)。同理,生成全部決策形式向量所需要的時間復雜度為O(2|D|-1)。因此本文算法的總時間復雜度為O((2|C|-|C|-1)·(2|D|-1))。

根據(jù)性質2可知,當一個條件形式向量可以進行規(guī)則提取時,其所有的條件子向量都是冗余的,因此該條件形式向量可以被刪除,與其相關的條件子向量將不存在,也不再進行規(guī)則獲取,這在條件樹形拓撲圖中體現(xiàn)為剪枝,從而大幅度降低了生成形式向量和規(guī)則提取的時間開銷。對于決策形式向量,當高粒度的決策形式向量已經無法獲取新的規(guī)則時,算法會根據(jù)定義7生成粒度減1的新一層決策形式向量,并重新遍歷全部的條件形式向量與新一層的決策形式向量來獲取規(guī)則。所以當決策父向量已經用于提取規(guī)則后,其所有的決策子向量也不是冗余的,因此剪枝的思想不會體現(xiàn)在決策樹形拓撲圖中。在實際應用中,條件形式向量的剪枝操作使得算法避免了大量的冗余計算,因此本算法的時間復雜度遠小于O((2|C|-|C|-1)·(2|D|-1))。

表1 多決策形式背景規(guī)則提取的算法步驟

算法的時間復雜度與屬性的數(shù)量密切相關,當屬性個數(shù)非常多時,算法的時間開銷會呈指數(shù)上升使得計算速度很慢。因此本文算法只適合處理屬性個數(shù)較少的小規(guī)模數(shù)據(jù)集。

2 實驗與分析

2.1 實例分析

例3 利用本文算法對文獻[17]中算例進行規(guī)則提取,多決策形式背景DT=(U,C,I,D,J),如表2所示,其中U={x1,x2,x3,x4,x5},C={a,b,c,d,e,f},D={d1,d2,d3}。

初始化參數(shù):l=1,l′=1,old-vectors=φ,Un=φ。

l=1時,求取單屬性條件形式向量并存入l(U,C,I),接著根據(jù)定義7求取第一層決策形式向量,由表2知不存在決策全屬性下的決策形式向量,故求取決策屬性粒度為2下的所有決策形式向量并

表2 多決策形式背景

除了重復生成的條件形式向量外,已用于規(guī)則提取的條件形式向量用虛線節(jié)點表示,根據(jù)剪枝的思想,這些節(jié)點不再用以生成下一層條件形式向量。

l=2時,根據(jù)定義6生成第2層條件形式向量并存入l(U,C,I)。同理,對于C,I)和判斷其是否滿足定理1。l=2時存在3個條件形式向量滿足規(guī)則提取條件,分別為ab(10100),ad(00100),af(10100),其對應的K、Rel值以及規(guī)則提取過程如表4所示。陰影部分表示重復識別的規(guī)則,不計入規(guī)則集。因此,l=2時可得確定性規(guī)則Rule3={a,b→d1,d2}。更新old-vectors={c(00100),e(00010),ab(10100)},Un={x1,x3,x4},l(U,C,I)=l(U,C,I)-old-vectors,因為Un≠U,需要繼續(xù)計算。

圖1 條件形式向量拓撲圖Fig.1 Topological diagram of conditional formal vectors

表3 l=1,l′=1的計算過程

表4 l=2,l′=1的計算過程

同理,繼續(xù)計算l=3時,生成第3層條件形式向量,圖1中虛線邊構成的節(jié)點表示重復生成的節(jié)點因此自動略去。此時不存在條件形式向量滿足定理1,因此l=3時不可得決策規(guī)則。

由圖1可知,此時l=3時不存在兩個條件形式向量用來生成不為零向量的條件子向量,因此條件樹形拓撲圖構建完畢。

更新決策樹形拓撲圖的深度l′=2,l ′(U,D,J)=φ,并根據(jù)定義7生成第2層決策形式向量存入l ′(U,D,J),如圖2所示。按照條件樹形拓撲圖的深度從低到高,重新遍歷各深度下l(U,C,I)中的條件形式向量是否滿足定理1中的規(guī)則提取條件,當l=1,2,3時,均沒有滿足規(guī)則提取條件的條件形式向量,因此無法產生新的決策規(guī)則。此時論域中對象未被完全覆蓋,但由于決策形式向量的屬性粒度是1,所以決策樹形拓撲圖無法繼續(xù)生成新的一層決策形式向量,因此決策樹形拓撲圖構建完畢,算法結束。

本文算法所提取規(guī)則均為確定性規(guī)則,當多個論域對象出現(xiàn)條件屬性完全一致但決策屬性不同的情況時(即不一致對象),算法會通過逐漸降低決策屬性粒度并查詢這些論域對象是否具有公共的決策屬性,進而得到對應的確定性規(guī)則。若決策樹形拓撲圖構建完畢后仍有論域對象未被覆蓋,例如本算例當中的論域對象x2和x5,二者條件屬性完全一致但不具有任何公共的決策屬性,因此不存在規(guī)則能夠提取。綜上,多決策形式背景DT的規(guī)則集為Rule1～Rule3。

傳統(tǒng)的運用形式概念分析進行規(guī)則提取需要構造條件概念格與決策概念格的Hasse圖,再利用概念間的關系進而提取規(guī)則。但提取出的規(guī)則大多具有冗余屬性并且規(guī)則長度較長,因此仍需進行去冗余操作。文獻[17]中算法對此進行了改進,結合辨識矩陣對概念做了進一步的屬性約簡,并得到了非冗余且長度更短的規(guī)則。形式向量與概念的相似之處體現(xiàn)在都蘊含對象和屬性特征這兩個內容,不同的是形式向量中包含的是全部論域對象以及每個對象是否具備當前的屬性特征,因此可以根據(jù)定理1直接推導條件形式向量與決策形式向量的包含關系,進而得到決策規(guī)則,既不需要屬性約簡也簡化了規(guī)則提取過程。本文算法在構造樹形拓撲圖時,無論是條件形式向量還是決策形式向量都從最簡知識粒度下出發(fā)進行層層計算進而提取規(guī)則,因此提取到的規(guī)則為最簡規(guī)則。同時,與文獻[17]中算法相比,本文算法不需要對論域中一致對象與不一致對象進行分類,對任意能進行規(guī)則提取的不一致對象,算法輸出規(guī)則可以完成覆蓋。

2.2 實驗測試

通過幾組數(shù)據(jù)集來進行實驗測試。本文共選用10組數(shù)據(jù)集如表5所示,其中數(shù)據(jù)集S1和S2分別來自文獻[9]和文獻[16]。S3,S4和S5利用文獻[16]中的方法將S1分別以40倍,100倍和250倍連接起來。S6,S7和S8將S1先分別按照文獻[16]中的方法水平先合并3,4,5次,再以40倍,50倍和70倍連接起來。S9和S10將S2先水平合并2次,再以80倍和120倍連接起來。然后,分別應用本文的算法(算法1),文獻[9]的算法(算法2),文獻[8]的算法(算法3)對數(shù)據(jù)集進行測試,記錄各算法的程序運行時間,實驗運行時間對比結果如表6所示,其中時間精確到0.01秒。

圖2 決策形式向量拓撲圖Fig.2 The topological diagramof decision formal vectors

Table 5 Data sets

實驗分析:數(shù)據(jù)集S1和S2均為一致數(shù)據(jù)集,S3-S10數(shù)據(jù)集由S1和S2生成。利用三種算法分別對S1和S2進行規(guī)則提取,算法2和算法3在提取規(guī)則后進行了去冗余操作得到了與算法1相同規(guī)則數(shù)目與長度的規(guī)則。此時由表6可以看出,相比于算法2、算法3,對于相同的數(shù)據(jù)集,算法1在規(guī)則獲取過程中的耗時較短,有明顯的時間優(yōu)勢,可以在更短的時間內達到獲取最簡規(guī)則的目的,因此本文的算法運行效率更高。算法2的時間復雜度為O(2|A|+|U|2|A|+|U||A|),算法3的時間復雜度為O(2|A|+|U|2|A|),就時間復雜度而言,算法1在提取規(guī)則的過程中不涉及|U|這一項,論域對象只在被所提取的規(guī)則完全覆蓋時作為算法1的結束條件,因此幾乎不占用時間開銷。另外,算法1的優(yōu)勢主要體現(xiàn)在以決策形式背景為研究對象,在利用條件形式向量與決策形式向量間的關系進行規(guī)則提取的過程中,樹形拓撲圖的剪枝操作使得算法1減少了大量冗余計算,在減少了時間開銷的同時也減少了空間開銷。

表6 算法運行時間對比

3 結論

本文以多決策形式背景為研究對象,定義并討論了形式向量及其性質,提出了一種多決策形式背景規(guī)則提取的形式向量算法。算法通過求取形式向量樹形拓撲圖中不同深度下的條件形式向量和決策形式向量,并計算二者間的關系是否滿足本文所提到的定理來提取規(guī)則。算法通過理論證明、算例講解、對比實驗說明了本算法的正確性、有效性與快速性。本算法有以下特點:1)定義了形式向量,提出了一種新的知識表示方法,相較于現(xiàn)行的概念格方法,避免了概念生成所帶來的煩瑣運算,同時也省去了去除規(guī)則中冗余屬性的過程。2)利用條件形式向量和決策形式向量之間的關系,判斷是否滿足文中定理來進行規(guī)則提取,簡化了規(guī)則的判定過程。3)按照條件屬性粒度從低到高,決策屬性粒度從高到低的順序獲取形式向量并進行規(guī)則提取,使得提取的規(guī)則均為最簡規(guī)則,并能對不一致數(shù)據(jù)提取規(guī)則。4)基于形式向量可以構建樹形拓撲圖,實現(xiàn)了規(guī)則提取過程的可視化。5)該算法適用于一致不一致多決策形式背景。