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

溫云霞, 王俊紅，2

(1. 山西大學 計算機與信息技術學院,山西 太原 030006; 2. 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)

?

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

溫云霞1, 王俊紅1，2

(1. 山西大學 計算機與信息技術學院,山西 太原 030006; 2. 計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)

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

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

中文引用格式：溫云霞, 王俊紅. 橫向拆分形勢背景下的快速規則提取方法[J]. 智能系統學報， 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]是數據分析和知識處理的一種有力工具，由Wille[1]在1982年提出。近年來獲得了飛速的發展，概念格理論[2]已經被廣泛地應用于軟件工程、知識工程、數據挖掘和信息檢索等領域。

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

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

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

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規則提取

下面簡要介紹由文獻[6]提出的規則提取方法的主要依據定理，該方法的基本思想是依據其雙親節點即直接泛化的個數及形式來對格中每個節點生成其無冗余的所有規則。關于此方法的詳細描述可參考文獻[6]。

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

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

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

注：只有當‖X′‖>k時，才可能有前件至多為k個描述符的規則，并且規則前件的描述符個數至多為其雙親節點的數目。除了前件為單個描述符的規則之外，其他規則的形式與數目僅僅依賴于其雙親節點。

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

1.3形式背景拆分思想

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

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

2　偽規則及其漸近式提取

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

2.1偽規則基本定義

注：上述偽規則不是真正的蘊含規則，是一種便于規則集合并和產生蘊含規則的一種規則形式。

定理4 由偽規則集可以推導出全部蘊含規則。

證明通過上述定理1～3可知，對于一個子節點，根據其父節點的數量采取不同的方法來獲取蘊含規則。上述提出的偽規則是子節點與其直接父節點之間的一個關系。對于一個子節點找到與其直接相關的父親節點對應的偽規則，運用定理1～3即可得到其對應的全部蘊含規則。

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

2.2偽規則的漸近式提取方法

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

算法

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

輸出更新后的格L′與規則集R。

BEGIN

R′←φ/*規則集合*/

FOR每個節點H=(X,X′)∈L

IFX′?f({x})THEN

把x加到X中,將節點H加入到Modify(記錄更新節點)中

IFX′=f({x})THENcontinue;

ELSE

new=X′∩f({x}) /*生成新節點*/

IFnew?LTHEN;

新增節點N=(X∪x,new)并加入

Modify中,增加邊N→H;

FORModify中的每個節點M=(Xm,Ym)

IFYm?newTHEN加入邊M→N,

IFM是H的雙親THEN

刪去邊M→H;

ENDFOR

ENDFOR

FOR每個規則p→q∈R

IFN的任意子節點N′=(Xn,Yn)

都有Yn≠p∪qTHEN

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

ENDFOR

R=R′/*記錄新的規則集*/

END

Functiongeneraterule(N=(X,Y))

BEGIN

FORN的每個父親節點F=(Xi,Yi)產生規則：Y/Yi(Xi)→Yi(Xi/X)

ENDFOR

END

3　偽規則集合并

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

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

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

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

證明因為節點C={(O1∪O2),B}對象集包含于節點C′={(O3∪O4),D}對象集，則節點C同樣具有節點C′的屬性，同時C的子節點也具有節點C′的屬性，因此節點C及其子節點的屬性變為{BD,ABD}，則規則更新為A→BD。

實際操作中每次都記錄更新節點(O1∪O2)，以便后續合并處理重復的問題。

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

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

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

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

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

證明因為如果兩規則的父節點與父節點的交集是空集，那么前者對應的子節點與后者父節點的交集也一定是空集，則記錄ABD/AB→AB，ABD/D→D記錄新節點φ。

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

例2給定的形式背景如表1所示。圖2和圖3是對形式背景橫向拆分每3個屬性為一個子形式背景所對應的概念格。在圖2上提取的偽規則集R1為：b(1235)→a(4)，c(34)→a(125)，c(3)→ab(125)，b(3)→ac(4)，abc(3)→abc(3)。圖3對應的偽規則集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)

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

1)與規則b(1235)→a(4)進行運算有12345∩1234=1234，對應的屬性集為ag。則得到(1234,ag)是新生成的節點，產生的規則為g(1234)→a(5)，因為與節點(1235,ab)沒有包含關系，因此依然記錄規則b(1235)→a(4)。

2)與規則c(34)→a(125)進行運算得到的節點與(1)相同，同時記錄規則c(34)→ag(12)。

3)與規則b(3)→ac(4)進行運算，34?1234，更新規則b(3)→acg(4)，記錄更新節點(34,acg)。

4)與規則c(3)→ab(125)進行運算，因為節點3?1234，所以更新原來的規則cg(3)→ab(125)，記錄更新節點(3,abcg)。

5)與規則abc(3)→abc(3)，3?1234，不產生新的節點，依然作為結尾節點，更新輔助規則abcg(3)→abcg(3)。

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

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

將R2中的規則按照上述的步驟加入R1，得到的規則集為：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)。由此偽規則集最終可以產生例1中的蘊含規則集。

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

4　實驗結果及分析

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

圖5　隨機數據集上兩種方法的執行時間Fig.5　Execution time of two methods on random data set

圖6　Mushroom數據集上兩種方法的執行時間Fig.6　Execution time of two methods on Mushroom data set

圖7　Spect數據集上兩種方法的執行時間Fig.7　Execution time of two methods on Spect data set

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

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

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

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

在隨機數據集上兩種方法的執行時間及概念數如表2所示。

表2　隨機數據集上兩種生成規則方法時間對比

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

從圖5～8中可以看出，本文算法執行時間低于文獻[6]中的算法，且具有穩定性。在獲取蘊含規則時間花銷方面有一定的優勢。

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

表3　隨機數據集上蘊含規則與偽規則數的對比

表4　Spect數據集上蘊含規則與偽規則數的對比

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

6　結論

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

[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]胡可云, 陸玉昌, 石純一. 概念格及其應用進展[J]. 清華大學學報: 自然科學版, 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]. 電子學報, 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]. 電子學報, 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]王志海, 胡可云, 胡學鋼, 等. 概念格上規則提取的一般算法與漸近式算法[J]. 計算機學報, 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]謝志鵬, 劉宗田. 概念格與關聯規則發現[J]. 計算機研究與發展, 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]. 數學的實踐與認識, 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]梁吉業, 王俊紅. 基于概念格的規則產生集挖掘算法[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]. 計算機學報, 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]. 中國科學 E輯: 信息科學, 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]. 計算機研究與發展, 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]胡可云, 陸玉昌, 石純一. 基于概念格的分類和關聯規則的集成挖掘方法[J]. 軟件學報, 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年生，碩士研究生，主要研究方向為概念格與數據挖掘。

王俊紅，女，1979年生，副教授，博士，碩士生導師，主要研究方向為粒計算、概念格與數據挖掘。

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

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160808.0830.016.html

2016-06-02. 網絡出版日期：2016-08-08.

國家自然科學基金項目(612022018,61303008).

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

TP18

A

1673-4785(2016)04-0526-08