多決策形式背景快速規則提取算法

尚子豪,陳澤華

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

0 引言

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

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

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

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

定義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的二進制數構成,表示為B(P),其中,|U|表示集合U中的元素個數。為方便敘述,用(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=φ,根據定義4可知FB1={xi|xiIFB1,xi∈U},FB2?{xj|xjIFB1,xj∈U}。根據定義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)中的屬性個數。

定義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)具有較多的條件屬性、較少的論域對象,其描述的知識更為抽象。同時,根據定義6可以構建條件形式向量的樹形拓撲圖。

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

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

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

說明由于0向量不具備辨識規則的能力,故后續圖中已略去0向量節點。

定理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)可以構成一條確定性規則,表示為Bx→By。

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

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

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

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

(4)

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

性質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)的規則辨識能力強于條件形式向量B2(P)。

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

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

1.1 算法描述

基于形式向量的性質,提出一種多決策形式背景的最簡規則提取算法,其算法步驟如表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))。

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

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

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

2 實驗與分析

2.1 實例分析

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

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

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

表2 多決策形式背景

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

l=2時,根據定義6生成第2層條件形式向量并存入l(U,C,I)。同理,對于C,I)和判斷其是否滿足定理1。l=2時存在3個條件形式向量滿足規則提取條件,分別為ab(10100),ad(00100),af(10100),其對應的K、Rel值以及規則提取過程如表4所示。陰影部分表示重復識別的規則,不計入規則集。因此,l=2時可得確定性規則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,需要繼續計算。

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

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

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

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

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

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

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

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

2.2 實驗測試

通過幾組數據集來進行實驗測試。本文共選用10組數據集如表5所示,其中數據集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)對數據集進行測試,記錄各算法的程序運行時間,實驗運行時間對比結果如表6所示,其中時間精確到0.01秒。

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

Table 5 Data sets

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

表6 算法運行時間對比

3 結論

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