橫向拆分形勢背景下的快速規(guī)則提取方法

溫云霞, 王俊紅，2

(1. 山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006; 2. 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室,山西 太原 030006)

?

橫向拆分形勢背景下的快速規(guī)則提取方法

溫云霞1, 王俊紅1，2

(1. 山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006; 2. 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室,山西 太原 030006)

概念格是進(jìn)行數(shù)據(jù)挖掘和規(guī)則提取的一種有效工具。目前已經(jīng)提出的概念格上的規(guī)則提取方法大多是針對整個(gè)形式背景，得到的規(guī)則數(shù)目較多，規(guī)則集規(guī)模較大，且這種規(guī)則結(jié)構(gòu)不便于兩個(gè)規(guī)則集的合并。針對這個(gè)問題，本文提出一種偽規(guī)則的概念，并給出漸近式獲取偽規(guī)則的方法;同時(shí)證明了通過偽規(guī)則集，用戶可以根據(jù)自己的興趣有選擇地從偽規(guī)則集合中產(chǎn)生出所需的蘊(yùn)含規(guī)則;提出了將兩個(gè)偽規(guī)則集進(jìn)行合并的方法，從而用戶可以通過拆分合并的思想來獲取規(guī)則集;最后通過實(shí)驗(yàn)分析驗(yàn)證了算法的有效性。

概念格; 形式背景; 子背景; 規(guī)則提取; 偽規(guī)則; 規(guī)則合并

中文引用格式：溫云霞, 王俊紅. 橫向拆分形勢背景下的快速規(guī)則提取方法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(4): 526-533.

英文引用格式：WEN Yunxia, WANG Junhong. Research on a fast method for extracting rules based on horizontal splitting[J]. CAAI Transactions on Intelligent Systems, 2016, 11(4): 526-533.

概念格[1-3]是數(shù)據(jù)分析和知識處理的一種有力工具，由Wille[1]在1982年提出。近年來獲得了飛速的發(fā)展，概念格理論[2]已經(jīng)被廣泛地應(yīng)用于軟件工程、知識工程、數(shù)據(jù)挖掘和信息檢索等領(lǐng)域。

在多源信息系統(tǒng)和數(shù)據(jù)分布式存儲與并行處理中，數(shù)據(jù)都是分別存儲和處理的。另一方面，在較大的形式背景下概念格構(gòu)造的復(fù)雜度很高，一個(gè)可行的方法是把形式背景拆分成多個(gè)子形式背景[4-5]，分別存儲和處理。這種方法的思想是在每個(gè)子形式背景上構(gòu)造概念格并通過子概念格的合并得到所需的概念格。概念格的分布式處理大大減少了概念格的構(gòu)造復(fù)雜度，但對子概念格上獲得的規(guī)則集之間的聯(lián)系，以及不通過子概念格合并直接利用規(guī)則集融合產(chǎn)生新規(guī)則的研究還較少。

概念格表明了概念之間的泛化和例化關(guān)系，這種層次關(guān)系有利于規(guī)則提取[6-10]。在概念格的規(guī)則提取方面學(xué)者們進(jìn)行了一定的研究，王志海等[6-7]提出了概念格上規(guī)則提取的一般算法和漸近式算法并研究了概念格與關(guān)聯(lián)規(guī)則發(fā)現(xiàn)。針對不同的形式背景有不同的規(guī)則提取方法，如李金海等[8]提出的在決策形式背景上的規(guī)則提取。還有一些提取規(guī)則的改進(jìn)方法，如梁吉業(yè)等[9]提出的基于概念格的規(guī)則產(chǎn)生集挖掘算法等。近來對概念格的研究也主要是圍繞概念格的約簡、縮小概念格的構(gòu)造和規(guī)則提取的復(fù)雜度[11-23]。但上述規(guī)則提取方法，一方面大都是針對一個(gè)形式背景，且得到的規(guī)則集數(shù)量較多、規(guī)模較大。而用戶有時(shí)可能只需要一部分感興趣的規(guī)則信息，而從規(guī)模較大的規(guī)則集中找出這些感興趣的規(guī)則信息也是一個(gè)難題。另一方面規(guī)則形式大都是文獻(xiàn)[6]和文獻(xiàn)[10]提出的規(guī)則形式，這種規(guī)則結(jié)構(gòu)不便于兩個(gè)規(guī)則集之間的合并研究。

針對上述問題，本文提出一種偽規(guī)則的概念，給出漸近式獲取偽規(guī)則的方法。同時(shí)說明了通過偽規(guī)則集，用戶可以得到原概念格上的蘊(yùn)含規(guī)則。偽規(guī)則集的規(guī)模相對較小，其結(jié)構(gòu)適于兩個(gè)規(guī)則集的合并。用戶可以根據(jù)自己的興趣有選擇地從偽規(guī)則集合中產(chǎn)生出所需的蘊(yùn)含規(guī)則。在偽規(guī)則集的基礎(chǔ)上，提出了將兩個(gè)偽規(guī)則集進(jìn)行合并的方法，通過此方法用戶可以直接利用偽規(guī)則集得到范圍更大的規(guī)則集。最后通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

1　基本定義

1.1概念格

表1　形式背景

圖1　L(U,{a,b,c,d,f,g,h,i},I)Fig.1　L(U,{a,b,c,d,f,g,h,i},I)

1.2規(guī)則提取

下面簡要介紹由文獻(xiàn)[6]提出的規(guī)則提取方法的主要依據(jù)定理，該方法的基本思想是依據(jù)其雙親節(jié)點(diǎn)即直接泛化的個(gè)數(shù)及形式來對格中每個(gè)節(jié)點(diǎn)生成其無冗余的所有規(guī)則。關(guān)于此方法的詳細(xì)描述可參考文獻(xiàn)[6]。

定理1[6]如果格中節(jié)點(diǎn)H=(X1,Y1)只有一個(gè)雙親節(jié)點(diǎn)M=(X2,Y2)，則H所產(chǎn)生的規(guī)則前件只能為單個(gè)描述符，且?p∈{Y1-Y2}，都存在一條無冗余規(guī)則p→Y1-p。

定理2[6]如果格中節(jié)點(diǎn)H=(X1,Y1)具有d個(gè)雙親節(jié)點(diǎn)M1(X2,Y2)，M2(X3,Y3)，…，Md(Xd,Yd)，則對于任意一個(gè)描述符p∈{Y1-(Y2∪Y3∪…∪Yd)}，都存在一條規(guī)則p→Y1-p。

定理3[6]若果格中節(jié)點(diǎn)H=(X1,Y1)具有兩個(gè)雙親節(jié)點(diǎn)M1(X2,Y2)和M2(X3,Y3)，則對于每個(gè)元素?p1∈{Y2-Y2∩Y3}和?p2∈{Y3-Y2∩Y3}，都存在一條規(guī)則p1p2→Y1-p1p2。

注：只有當(dāng)‖X′‖>k時(shí)，才可能有前件至多為k個(gè)描述符的規(guī)則，并且規(guī)則前件的描述符個(gè)數(shù)至多為其雙親節(jié)點(diǎn)的數(shù)目。除了前件為單個(gè)描述符的規(guī)則之外，其他規(guī)則的形式與數(shù)目僅僅依賴于其雙親節(jié)點(diǎn)。

例1對圖1用上述定理，獲得的蘊(yùn)含規(guī)則為b→a，g→a，d→abf，f→abd，bg→a，bh→ag，h→ag，c→agh，bc→agh，i→acgh。

1.3形式背景拆分思想

通過對形式背景的拆分，形成多個(gè)子背景，分別構(gòu)造概念格，然后再將子概念格合并是概念格分布處理的中心思想。

目前對形式背景的拆分有縱向和橫向之分，對應(yīng)的有兩種合并方法。橫向拆分是指對象域相同，屬性項(xiàng)不同的拆分?？v向拆分是指對象域不同，屬性項(xiàng)相同的拆分。本文將采用橫向拆分的方式。

2　偽規(guī)則及其漸近式提取

在一個(gè)形式背景上通過文獻(xiàn)[6]提出的方法以及其他的一些改進(jìn)方法所得到的規(guī)則數(shù)目較多，規(guī)模較大，其規(guī)則形式不便于兩個(gè)規(guī)則集之間的合并操作。因此，我們提出一種新的規(guī)則形式及其漸近式提取方法。其基本思想是對格中每個(gè)節(jié)點(diǎn)生成與其直接關(guān)系的父節(jié)點(diǎn)之間的一種關(guān)系，包括屬性集之間的關(guān)系和對象集之間的關(guān)系，并證明通過偽規(guī)則集可以推導(dǎo)出全部的蘊(yùn)含規(guī)則。

2.1偽規(guī)則基本定義

注：上述偽規(guī)則不是真正的蘊(yùn)含規(guī)則，是一種便于規(guī)則集合并和產(chǎn)生蘊(yùn)含規(guī)則的一種規(guī)則形式。

定理4 由偽規(guī)則集可以推導(dǎo)出全部蘊(yùn)含規(guī)則。

證明通過上述定理1～3可知，對于一個(gè)子節(jié)點(diǎn)，根據(jù)其父節(jié)點(diǎn)的數(shù)量采取不同的方法來獲取蘊(yùn)含規(guī)則。上述提出的偽規(guī)則是子節(jié)點(diǎn)與其直接父節(jié)點(diǎn)之間的一個(gè)關(guān)系。對于一個(gè)子節(jié)點(diǎn)找到與其直接相關(guān)的父親節(jié)點(diǎn)對應(yīng)的偽規(guī)則，運(yùn)用定理1～3即可得到其對應(yīng)的全部蘊(yùn)含規(guī)則。

例如：圖1所示格結(jié)構(gòu)中獲得的偽規(guī)則g(123)→ab(5)和b(123)→ag(4)，由此偽規(guī)則可以得出子節(jié)點(diǎn)為abg，父親節(jié)點(diǎn)為ab和ag。則通過定理2和定理3可以得到如下的蘊(yùn)含規(guī)則：bg→a。

2.2偽規(guī)則的漸近式提取方法

采用基于對象的概念格漸近式構(gòu)造思想，對每個(gè)新生成的節(jié)點(diǎn)產(chǎn)生其對應(yīng)的偽規(guī)則。并對更新節(jié)點(diǎn)判斷其對應(yīng)的原偽規(guī)則是否已經(jīng)失效，如失效不再記錄。剩下的沒有變更的節(jié)點(diǎn)規(guī)則全部原樣進(jìn)行記錄。下面給出在已建好的格上提取規(guī)則的算法。該算法采用基于對象的漸近式構(gòu)造思想，函數(shù)generaterule(N=(X,Y))生成節(jié)點(diǎn)之間的偽規(guī)則。

算法

輸入已有的格L與規(guī)則集R，要追加的概念({x},f({x}))；

輸出更新后的格L′與規(guī)則集R。

BEGIN

R′←φ/*規(guī)則集合*/

FOR每個(gè)節(jié)點(diǎn)H=(X,X′)∈L

IFX′?f({x})THEN

把x加到X中,將節(jié)點(diǎn)H加入到Modify(記錄更新節(jié)點(diǎn))中

IFX′=f({x})THENcontinue;

ELSE

new=X′∩f({x}) /*生成新節(jié)點(diǎn)*/

IFnew?LTHEN;

新增節(jié)點(diǎn)N=(X∪x,new)并加入

Modify中,增加邊N→H;

FORModify中的每個(gè)節(jié)點(diǎn)M=(Xm,Ym)

IFYm?newTHEN加入邊M→N,

IFM是H的雙親THEN

刪去邊M→H;

ENDFOR

ENDFOR

FOR每個(gè)規(guī)則p→q∈R

IFN的任意子節(jié)點(diǎn)N′=(Xn,Yn)

都有Yn≠p∪qTHEN

R′=R′∪p→q/*記錄原來的規(guī)則*/

ENDFOR

R=R′/*記錄新的規(guī)則集*/

END

Functiongeneraterule(N=(X,Y))

BEGIN

FORN的每個(gè)父親節(jié)點(diǎn)F=(Xi,Yi)產(chǎn)生規(guī)則：Y/Yi(Xi)→Yi(Xi/X)

ENDFOR

END

3　偽規(guī)則集合并

概念格的構(gòu)造一直是影響其應(yīng)用的主要因素，文獻(xiàn)[4]和文獻(xiàn)[5]提出了拆分和合并的思想。將形式背景拆分成多個(gè)子形式背景，分別構(gòu)造概念格并對其進(jìn)行合并。但是，目前提出的合并都是針對子概念格的合并，而每個(gè)子概念格上都可以提取規(guī)則，因而可以將直接利用兩個(gè)規(guī)則集進(jìn)行合并，直接產(chǎn)生所需的規(guī)則信息。對于兩個(gè)子規(guī)則集直接進(jìn)行合并，相關(guān)研究還較少。下面提出通過偽規(guī)則集來實(shí)現(xiàn)兩個(gè)規(guī)則的合并。

兩個(gè)對應(yīng)概念格上的偽規(guī)則集合并的主要思想是通過偽規(guī)則中包含的概念屬性和對象信息，運(yùn)用一定的合并原理來生成新的規(guī)則。在合并的過程中產(chǎn)生新的節(jié)點(diǎn)概念信息，記錄新生概念信息。因此規(guī)則合并后也就得到了合并后的一個(gè)概念格的結(jié)構(gòu)。合并規(guī)則依據(jù)的是概念格橫向合并的思想，根據(jù)合并時(shí)新規(guī)則產(chǎn)生的信息來判斷是否是新生成的規(guī)則，比較與原規(guī)則之間的關(guān)系來判斷是否要更改原規(guī)則。因格中的節(jié)點(diǎn)在規(guī)則中既可以是前件也可以是后件，因此合并時(shí)只考慮其作為后件的情況，避免重復(fù)規(guī)則。

例如給定兩個(gè)偽規(guī)則A(O1)→B(O2)和C(O3)→D(O4)，則有如下合并規(guī)則：

定理5(O1∪O2)?(O3∪O4)，則更新原有規(guī)則：A→BD。

證明因?yàn)楣?jié)點(diǎn)C={(O1∪O2),B}對象集包含于節(jié)點(diǎn)C′={(O3∪O4),D}對象集，則節(jié)點(diǎn)C同樣具有節(jié)點(diǎn)C′的屬性，同時(shí)C的子節(jié)點(diǎn)也具有節(jié)點(diǎn)C′的屬性，因此節(jié)點(diǎn)C及其子節(jié)點(diǎn)的屬性變?yōu)閧BD,ABD}，則規(guī)則更新為A→BD。

實(shí)際操作中每次都記錄更新節(jié)點(diǎn)(O1∪O2)，以便后續(xù)合并處理重復(fù)的問題。

定理6 若有O1?(O3∪O4)，O2?(O3∪O4)，則更新原有規(guī)則：AD→B。

證明因?yàn)楣?jié)點(diǎn)C={O1,(A∪B)}對象集包含于節(jié)點(diǎn)C′={(O3∪O4),D}，而O2?(O3∪O4)即說明節(jié)點(diǎn)C的父親節(jié)點(diǎn)的對象集并不包含于節(jié)點(diǎn)C′。因此只將C的屬性變?yōu)閧A∪D∪B}，其父親節(jié)點(diǎn)的屬性不變，則原規(guī)則更新為AD→B。記錄更新節(jié)點(diǎn)O1

定理7 (O1∪O2)∩(O3∪O4)≠φ，則生成new=(O1∪O2)∩(O3∪O4)，是(O1∪O2)和(O3∪O4)與的子集，如果new在原概念格節(jié)點(diǎn)集中不存在，且(O3∪O4)與(O1∪O2)的所有子節(jié)點(diǎn)的交集都不是new，則生的規(guī)則有：BD/B→B，BD/D→D。

證明兩個(gè)概念節(jié)點(diǎn)C={(O1∪O2),B}和C′={(O3∪O4),D}產(chǎn)生的新節(jié)點(diǎn)new={(O1∪O2)∩(O3∪O4),(B∪D)}是兩個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)當(dāng)原概念格節(jié)點(diǎn)中不存在此節(jié)點(diǎn)，因此依據(jù)偽規(guī)則生成方法，可以生成BD/B→B，BD/D→D。且(O3∪O4)與(O1∪O2)的所有子節(jié)點(diǎn)的交集都不是new，保證生成正確的規(guī)則。記錄new。

定理8(O1∪O2)∩(O3∪O4)=φ，如果φ在原概念格節(jié)點(diǎn)集中不存在，則直接生成前者子節(jié)點(diǎn)與新節(jié)點(diǎn)之間的規(guī)則。

證明因?yàn)槿绻麅梢?guī)則的父節(jié)點(diǎn)與父節(jié)點(diǎn)的交集是空集，那么前者對應(yīng)的子節(jié)點(diǎn)與后者父節(jié)點(diǎn)的交集也一定是空集，則記錄ABD/AB→AB，ABD/D→D記錄新節(jié)點(diǎn)φ。

注：在每個(gè)規(guī)則集中增加一個(gè)輔助規(guī)則，即內(nèi)涵最大的節(jié)點(diǎn)自身生成一個(gè)輔助規(guī)則：Y→Y，保證在規(guī)則合并時(shí)可以訪問到概念格中的每個(gè)節(jié)點(diǎn)。在合并的過程中會產(chǎn)生新的概念節(jié)點(diǎn)，也要對這些新產(chǎn)生的概念節(jié)點(diǎn)判斷它們之間是否可以產(chǎn)生偽規(guī)則。同時(shí)判斷更新節(jié)點(diǎn)與新生節(jié)點(diǎn)之間是否產(chǎn)生新的規(guī)則，可以防止重復(fù)地生成規(guī)則。

例2給定的形式背景如表1所示。圖2和圖3是對形式背景橫向拆分每3個(gè)屬性為一個(gè)子形式背景所對應(yīng)的概念格。在圖2上提取的偽規(guī)則集R1為：b(1235)→a(4)，c(34)→a(125)，c(3)→ab(125)，b(3)→ac(4)，abc(3)→abc(3)。圖3對應(yīng)的偽規(guī)則集R2為：h(234)→g(1)，i(4)→gh(23)，ghi(4)→ghi(4)。

圖2　子概念格L(U,{a,b,c },l)Fig.2　Sub-concept lattice L(U,{a,b,c },I)

圖3　子概念格L(U,{g,h,i},I)Fig.3　Sub-concept lattice L(U,{g,h,i},I)

合并過程如下：首先判斷要加入的偽規(guī)則對應(yīng)的節(jié)點(diǎn)信息是否已經(jīng)存在，若存在不做任何操作。否則加入偽規(guī)則h(234)→g(1)到偽規(guī)則集R1上，遍歷R1對應(yīng)的所有概念節(jié)點(diǎn)信息，更新(1234,g)的屬性信息為(1234,ag)。

1)與規(guī)則b(1235)→a(4)進(jìn)行運(yùn)算有12345∩1234=1234，對應(yīng)的屬性集為ag。則得到(1234,ag)是新生成的節(jié)點(diǎn)，產(chǎn)生的規(guī)則為g(1234)→a(5)，因?yàn)榕c節(jié)點(diǎn)(1235,ab)沒有包含關(guān)系，因此依然記錄規(guī)則b(1235)→a(4)。

2)與規(guī)則c(34)→a(125)進(jìn)行運(yùn)算得到的節(jié)點(diǎn)與(1)相同，同時(shí)記錄規(guī)則c(34)→ag(12)。

3)與規(guī)則b(3)→ac(4)進(jìn)行運(yùn)算，34?1234，更新規(guī)則b(3)→acg(4)，記錄更新節(jié)點(diǎn)(34,acg)。

4)與規(guī)則c(3)→ab(125)進(jìn)行運(yùn)算，因?yàn)楣?jié)點(diǎn)3?1234，所以更新原來的規(guī)則cg(3)→ab(125)，記錄更新節(jié)點(diǎn)(3,abcg)。

5)與規(guī)則abc(3)→abc(3)，3?1234，不產(chǎn)生新的節(jié)點(diǎn)，依然作為結(jié)尾節(jié)點(diǎn)，更新輔助規(guī)則abcg(3)→abcg(3)。

最后生成更新節(jié)點(diǎn)與新生節(jié)點(diǎn)之間的規(guī)則，以及新生節(jié)點(diǎn)與新生節(jié)點(diǎn)之間的規(guī)則，生成的規(guī)則如下：c(34)→ag(12)，(b)中已經(jīng)記錄則不再記錄。

加入h(234)→g(1)后得到的規(guī)則為：g(1234)→a(5)，b(1235)→a(4)，c(34)→ag(12)，b(3)→acg(4)，abcg(3)→abcg(3)，cg(3)→ab(125)。將此偽規(guī)則集記錄為R1，用于下次插入規(guī)則。

將R2中的規(guī)則按照上述的步驟加入R1，得到的規(guī)則集為：b(1235)→a(4)，g(1234)→a(5)，b(123)→ag(4)，g(123)→ab(5)，h(23)→abg(1)，c(34)→agh(2)，b(3)→acgh(4)，h(234)→ag(1)，b(23)→agh(4)，i(4)→acgh(3)，c(3)→abgh(2)，i(φ)→abcgh(3)，b(φ)→acghi(4)。由此偽規(guī)則集最終可以產(chǎn)生例1中的蘊(yùn)含規(guī)則集。

圖4　L(U,{a,b,c,g,h,i},I) Fig.4　L(U,{a,b,c,g,h,i},I)

4　實(shí)驗(yàn)結(jié)果及分析

上述規(guī)則合并方法我們已在Windows7環(huán)境下用MATLAB2013實(shí)現(xiàn)，并在UCI上的具有單值(二值)或可轉(zhuǎn)換為單值，可數(shù)量化的Spect數(shù)據(jù)集、Mushroom數(shù)據(jù)集、Nursery數(shù)據(jù)集，和隨機(jī)生成的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。在Mushshroom數(shù)據(jù)集上隨機(jī)選定前10個(gè)屬性和前180個(gè)對象，每30個(gè)對象為一組。在Spect數(shù)據(jù)集上隨機(jī)選定前6個(gè)屬性和前120個(gè)對象，每30個(gè)對象為一組。在Nursery數(shù)據(jù)集上隨機(jī)選定前8個(gè)屬性，前120個(gè)對象，每30個(gè)對象為一組。在隨機(jī)生成的數(shù)據(jù)集上選定屬性個(gè)數(shù)為15個(gè)，每個(gè)對象有5個(gè)屬性，同樣30個(gè)對象為一組。每次遞增一組對象。對Mushroom數(shù)據(jù)集屬性平均拆分為5份，每兩個(gè)屬性為一個(gè)拆分。同樣對隨機(jī)生成的數(shù)據(jù)集屬性平均拆分成5份，每3個(gè)屬性為一個(gè)拆分。對Spect數(shù)據(jù)集屬性平分為3份，每2個(gè)屬性為一個(gè)拆分。對Nursery數(shù)據(jù)集屬性平分為4份，每2個(gè)屬性為一個(gè)拆分。在這4個(gè)數(shù)據(jù)集上進(jìn)行了測試并和文獻(xiàn)[6]算法進(jìn)行了對比，在4個(gè)測試集上兩種方法的執(zhí)行時(shí)間結(jié)果如下圖5～8所示，兩種方法獲取規(guī)則數(shù)目的比較結(jié)果如圖9～12。

圖5　隨機(jī)數(shù)據(jù)集上兩種方法的執(zhí)行時(shí)間Fig.5　Execution time of two methods on random data set

圖6　Mushroom數(shù)據(jù)集上兩種方法的執(zhí)行時(shí)間Fig.6　Execution time of two methods on Mushroom data set

圖7　Spect數(shù)據(jù)集上兩種方法的執(zhí)行時(shí)間Fig.7　Execution time of two methods on Spect data set

圖9　隨機(jī)數(shù)據(jù)集上兩種方法獲取的規(guī)則數(shù)目Fig.9　The number of rules obtained by two methods on random data set

圖10　Mushroom數(shù)據(jù)集上兩種方法獲取的規(guī)則數(shù)目Fig.10　The number of rules obtained by two methods on Mushroom data set

圖11　Spect數(shù)據(jù)集上兩種方法獲取的規(guī)則數(shù)目Fig.11　The number of rules obtained by two methods on Spect data set

圖12　Nursery數(shù)據(jù)集上兩種方法獲取的規(guī)則數(shù)目Fig.12　The number of rules obtained by two methods on Nursery data set

在隨機(jī)數(shù)據(jù)集上兩種方法的執(zhí)行時(shí)間及概念數(shù)如表2所示。

表2　隨機(jī)數(shù)據(jù)集上兩種生成規(guī)則方法時(shí)間對比

從表2中可以看出，利用偽規(guī)則集生成蘊(yùn)含規(guī)則的方法所用時(shí)間較直接構(gòu)造概念格生成蘊(yùn)含規(guī)則明顯減少。且時(shí)間的增長基本呈線性。在這個(gè)過程中避免了概念格的合并，降低了構(gòu)造概念格的時(shí)間復(fù)雜度對規(guī)則獲取的制約。

從圖5～8中可以看出，本文算法執(zhí)行時(shí)間低于文獻(xiàn)[6]中的算法，且具有穩(wěn)定性。在獲取蘊(yùn)含規(guī)則時(shí)間花銷方面有一定的優(yōu)勢。

從圖9～12中可以看出，本文算法所獲取的偽規(guī)則的數(shù)目遠(yuǎn)小于文獻(xiàn)[6]中算法所獲取的規(guī)則數(shù)目，得到的偽規(guī)則集的規(guī)模較小，用戶可以根據(jù)所需靈活地通過偽規(guī)則生成部分和全部的蘊(yùn)含規(guī)則。在隨機(jī)數(shù)據(jù)集以及Spect數(shù)據(jù)集上，獲取的概念數(shù)與規(guī)則數(shù)對比如表3所示。

表3　隨機(jī)數(shù)據(jù)集上蘊(yùn)含規(guī)則與偽規(guī)則數(shù)的對比

表4　Spect數(shù)據(jù)集上蘊(yùn)含規(guī)則與偽規(guī)則數(shù)的對比

從表3和表4中可以看出，當(dāng)概念數(shù)量較多時(shí)，所獲得的偽規(guī)則集的數(shù)量明顯小于所獲取的蘊(yùn)含規(guī)則集的數(shù)量。在規(guī)模較小的 偽規(guī)則中，用戶能夠更好地選取感興趣的屬性并生成全部的蘊(yùn)含規(guī)則。

6　結(jié)論

本文在橫向拆分的形式背景下，對基于概念格的規(guī)則提取進(jìn)行了研究。1)首先提出了偽規(guī)則的概念，并給出了偽規(guī)則的漸近式提取方法，證明了通過偽規(guī)則集可以生成全部的蘊(yùn)含規(guī)則；2)本文基于偽規(guī)則形式，給出了偽規(guī)則合并的法則及快速規(guī)則獲取方法，通過理論推理和實(shí)驗(yàn)驗(yàn)證說明了本文方法的有效性；3)本文所提的規(guī)則獲取方法主要是針對于橫向拆分的形式背景，但是對形式背景的拆分有多種拆分方式，對于不同的拆分方式下的規(guī)則獲取是進(jìn)一步需要研究的工作。

[1]GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin Heidelberg: Springer-Verlag, 1999.

[2]WILLE R. Restructuring lattice theory: an approach based on Hierarchies of concepts[M]//RIVAL I. Ordered Sets. Netherlands: Springer, 1982: 445-470.

[3]胡可云, 陸玉昌, 石純一. 概念格及其應(yīng)用進(jìn)展[J]. 清華大學(xué)學(xué)報(bào): 自然科學(xué)版, 2000, 40(9): 77-81.

HU Keyun, LU Yuchang, SHI Chunyi. Advances in concept lattice and its application[J]. Journal of Tsinghua university: science & technology, 2004, 40(9): 77-81.

[4]李云, 劉宗田, 陳崚, 等. 多概念格的橫向合并算法[J]. 電子學(xué)報(bào), 2004, 32(11): 1849-1854.

LI Yun, LIU Zongtian, CHEN Ling, et al. Horizontal union algorithm of multiple concept lattices[J]. Acta electronica sinica, 2004, 32(11): 1849-1854.

[5]智慧來, 智東杰, 劉宗田. 概念格合并原理與算法[J]. 電子學(xué)報(bào), 2010, 38(2): 455-459.

ZHI Huilai, ZHI Dongjie, LIU Zongtian. Theory and algorithm of concept lattice union[J]. Acta electronica sinica, 2010, 38(2): 455-459.

[6]王志海, 胡可云, 胡學(xué)鋼, 等. 概念格上規(guī)則提取的一般算法與漸近式算法[J]. 計(jì)算機(jī)學(xué)報(bào), 1999, 22(1): 66-70.

WANG Zhihai, HU Keyun, HU Xuegang, et al. General and incremental algorithms of rule extraction based on Concept lattice[J]. Chinese journal of computers, 1999, 22(1): 66-70.

[7]謝志鵬, 劉宗田. 概念格與關(guān)聯(lián)規(guī)則發(fā)現(xiàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2000, 37(12): 1415-1421.

XIE Zhipeng, LIU Zongtian. Concept lattice and association rule discovery[J]. Journal of computer research & development, 2000, 37(12): 1415-1421.

[8]李金海, 呂躍進(jìn). 基于概念格的決策形式背景屬性約簡及規(guī)則提取[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識, 2009, 39(7): 182-188.

LI Jinhai, LV Yuejin. Attribute reduction and rules extraction in decision formal context based on concept lattice[J]. Mathematics in practice and theory, 2009, 39(7): 182-188.

[9]梁吉業(yè), 王俊紅. 基于概念格的規(guī)則產(chǎn)生集挖掘算法[J]. 計(jì)算機(jī)研究與展, 2004, 41(8): 1339-1344.

LIANG Jiye, WANG Junhong. An algorithm for extracting rule-generating sets based on Concept lattice[J]. Journal of computer research and development, 2004, 41(8): 1339-1344.

[10]GODIN R, MISSAOUI R. An incremental concept formation approach for learning from databases[J]. Theoretical computer science, 1994, 133(2): 387-419.

[11]李進(jìn)金, 張燕蘭, 吳偉志, 等. 形式背景與協(xié)調(diào)決策形式背景屬性約簡與概念格生成[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(8): 1768-1774.

LI Jinjin, ZHANG Yanlan, WU Weizhi, et al. Attribute reduction for formal context and consistent decision formal context and Concept lattice generation[J]. Chinese journal of computers, 2014, 37(8): 1768-1774.

[12]MA Jianmin, LEUNG Y, ZHANG Wenxiu. Attribute reductions in object-oriented concept lattices[J]. International journal of machine learning and cybernetics, 2014, 5(5): 789-813.

[13]LI Jinhai, MEI Changlin, WANG Junhong, et al. Rule-preserved object compression in Formal decision contexts using concept lattices[J]. Knowledge-based systems, 2014, 71: 435-445.

[14]CORNEJO M E, MEDINA J, RAMíREZ-POUSSA E. Attribute reduction in multi-adjoint concept lattices[J]. Information sciences, 2015, 294: 41-56.

[15]TAN Anhui, LI Jinjin, LIN Guoping. Connections between covering-based rough sets and concept lattices[J]. International journal of approximate reasoning, 2015, 56(Part A): 43-58.

[16]張文修, 魏玲, 祁建軍. 概念格的屬性約簡理論與方法[J]. 中國科學(xué) E輯: 信息科學(xué), 2005, 35(6): 628-639.

ZHANG Wenxiu, WEI Ling, QI Jianjun. Attribute reduction theory and approach to concept lattice[J]. Science in China series F: information sciences, 2005, 48(6): 713-726.

[17]張磊, 張宏莉, 殷麗華, 等. 概念格的屬性漸減原理與算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(2): 248-259.

ZHANG Lei, ZHANG Hongli, YIN Lihua, et al. Theory and algorithms of attribute decrement for Concept lattice[J]. Journal of computer research and development, 2013, 50(2): 248-259.

[18]胡可云, 陸玉昌, 石純一. 基于概念格的分類和關(guān)聯(lián)規(guī)則的集成挖掘方法[J]. 軟件學(xué)報(bào), 2000, 11(11): 1478-1484.

HU Keyun, LU Yuchang, SHI Chunyi. An integrated mining approach for classification and association rule based on Concept lattice[J]. Journal of software, 2000, 11(11): 1478-1484.

[19]MAO Hua. Characterization and reduction of concept lattices through matroid theory[J]. Information sciences, 2014, 281: 338-354.

[20]YANG Yafeng. Parallel construction of variable precision concept lattice in fuzzy formal context[J]. AASRI Procedia, 2013, 5: 214-219.

[21]DíAZ-MORENO J C, MEDINA J. Using concept lattice theory to obtain the set of Solutions of multi-adjoint relation equations[J]. Information sciences, 2014, 266: 218-225.

[22]ISHIGURE H, MUTOH A, MATSUI T, et al. Concept lattice reduction using attribute inference[C]//Proceedings of the IEEE 4th Global Conference on Consumer Electronics. Osaka: IEEE, 2015: 108-111.

[23]CHEN Jinkun, LI Jinjin, LIN Yaojin, et al. Relations of reduction between covering generalized rough sets and Concept lattices[J]. Information sciences, 2015, 304: 16-27.

溫云霞，女，1986年生，碩士研究生，主要研究方向?yàn)楦拍罡衽c數(shù)據(jù)挖掘。

王俊紅，女，1979年生，副教授，博士，碩士生導(dǎo)師，主要研究方向?yàn)榱Ｓ?jì)算、概念格與數(shù)據(jù)挖掘。

Research on a fast method for extracting rules based on horizontal splitting

WEN Yunxia1, WANG Junhong1，2

(1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Taiyuan 030006, China)

The concept lattice is a valid tool for data mining and rule extraction. The methods of extracting rules from the concept lattice are based mainly on the whole formal context, but this results in a large number of rules and rule sets, and it is difficult to combine the rule sets subsets with the original structure. In this paper, the concept of a pseudo rule set and its incremental determination method is given; users can get the needed implication rules from the pseudo rule set, according to their interests. A method of combining two pseudo rule sets is then given. Users may therefore get their rule sets by dividing or combining these sets. The effectiveness of this method is proven through experiment analysis.

concept lattice; formal context; subcontext; extracting rules; pseudo rule; combination of the rule set

10.11992/tis.201606008

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.016.html

2016-06-02. 網(wǎng)絡(luò)出版日期：2016-08-08.

國家自然科學(xué)基金項(xiàng)目(612022018,61303008).

王俊紅. E-mail:wjhwjh@sxu.edu.cn.

TP18

A

1673-4785(2016)04-0526-08