基于量化規則格的關聯規則漸進更新
2007-01-01 00:00:00李云蔡俊杰劉宗田陳崚李拓
計算機應用研究 2007年5期
摘要：提出一種基于量化規則格的規則更新算法，重點討論了在新增格節點的過程中規則更新的思想，實現在格的漸增生成過程中，相應的關聯規則也得到漸進更新。最后給出簡單實例說明規則更新算法的正確性。
關鍵詞：概念格;關聯規則;量化規則格;規則更新
中圖分類號：TP311文獻標志碼：A
文章編號：1001－3695(2007)05－0027－04
自Wille R教授[1]提出形式概念分析以來，形式概念分析中的核心數據結構——概念格受到了普遍關注。其主要集中在對概念格構造和概念格的應用兩個方面。由于能適應動態數據處理要求，漸進式構造概念格表現出較強的生命力。其中由Godin等人提出的漸進構造概念格的算法[2]（稱為Godin算法）處理動態數據庫是比較高效的。后來發展出的AddIntent算法[3]，在Godin算法的基礎上加以改進，使構格效率得到提高。
利用概念格提取關聯規則是概念格應用得最成功的一個方面[4]。頻繁封閉項集是頻繁項集的子集，且直接對應于概念格的節點概念。人們提出了用頻繁封閉項集來提取規則的一些算法，如CLOSE[5]、CHARM[6]等，但均不適合處理動態數據庫。Petko Valtchev等人[7]提出了利用概念格來漸進獲取頻繁封閉項集的方法，但它不能隨數據庫的漸增而方便地實現規則的漸增更新。Yves Bastide 等人[8]提出了最小無冗余規則，但仍是采用CLOSE算法來提取。本文通過更改概念格結構形成頻繁封閉項集格，并采用不同的方法獲得格節點所對應的同交易項集中的最小項集集合(Set of the Least ITemsets，SLIT)，來提取最小無冗余規則[9～11]，但也不能方便地實現對規則的漸進更新。目前，利用概念格來提取關聯規則，是對構格和提取規則兩個過程分別進行處理的。目前的構格算法，對于動態數據庫能高效地構造出概念格，但其規則產生并不高效。當數據庫更新后，雖然格可以更新構造，但規則需要重新掃描整個格來重新生成，即無法實現規則的漸進更新。本文針對最小無冗余規則，提出了利用量化規則格實現在格動態更新的同時，對規則的漸進更新。
1最小無冗余關聯規則和量化規則格的基本概念
1．1關聯規則的基本概念
2基于量化規則格的關聯規則漸增更新的基本思想
目前在以概念格為背景的規則更新算法中，多數算法是把構格過程和關聯規則提取過程分開處理的，先產生概念格，然后在概念格的基礎上掃描產生關聯規則。在此過程中，每次都需要重新掃描生成新的規則集合，對以前規則集合沒有再利用。本文提出一種在量化規則格構格過程中的規則產生算法。該算法在構造量化規則格的同時，實現了對已有規則集合再利用，可以動態產生新的規則。
利用概念格提取最小無冗余規則的關鍵是找出每個節點的項集所對應的頻繁封閉項集中的SLIT[11]，且量化規則格中的關聯規則更新與格節點本身以及直接父子節點有關。
關聯規則的漸增更新可分為兩個部分：
（1）對已有規則的不變再利用，即已經存在的規則不變化。
（2）對已有規則的更新再利用。該更新操作包括規則刪除、增加和修改。
量化規則格中產生的SLIT是為了更方便地產生規則集合。每一個格節點的SLIT都對應了該節點所對應的精確規則和近似規則，SLIT的變化將直接影響到規則的變化。為了便于規則產生計算，本文使用規則前件集合和規則后件集合來描述一條規則，即AB，A稱為前件集合，B稱為后件集合。根據量化規則格的漸增構造過程，當原概念格中每增加一個格節點，該節點所對應的SLIT將重新計算，因此它所對應的規則將重新產生。而該新增節點將影響到直接父節點以及子節點的SLIT，即每次新增格節點，那么將最多影響三個格節點所對應的規則。下面分兩種情況討論節點SLIT的變化：
（1）增加節點連線
定理1當增加節點間連線時，子節點的精確規則不可能減少。
根據量化規則格的構格過程，增加節點連線時，分兩種情況：①新增節點和產生子節點的父子關系形成;②新增節點與其父節點的關系形成。在這兩種情況中，SLIT的變化又分兩種情況：① SLIT項集個數增加情況。如圖1所示，當{abcde}節點新增一個父節點{ade}時，它的SLIT個數發生變化。
② SLIT項集個數不變，元素變化情況。如圖2所示，當{abcde}節點新增一個父節點{abe}時SLIT的變化過程。
（2）刪除節點連線
命題1在概念格L中存在格節點(A，B)和(C，D)，新增加節點(E，F)。若(A，B)＜(C，D)，即BD為直接父子關系，(E，F)＜(C，D)為直接父子關系。當(A，B)＜(E，F)時，（A，B）節點所對應的精確規則不變；近似規則的前件集合不變，新后件集合為原后件集合的子集。
證明命題1所列舉的情況對應構格算法中新增一個節點打破了原概念格中的父子關系時的情況。這時，SLIT的重新計算只在(A，B)和(E，F)之間進行。對于(A，B)還是保留原SLIT（參考文獻[11]），因此(A，B)的SLIT沒有變化的話，所對應的精確規則也是不會變化的。近似規則取決于(A，B)所對應的直接子節點的內涵，而FD，因此新后件集合為原后件集合的子集。
推論1當刪除節點連線時，子節點的精確規則不可能增加。
證明略。
在量化規則構造過程中，只有新增節點需調整節點之間已有的關系。若新增節點沒有改變原格中兩個節點之間的直接父子關系，則只需進行增加連線處理。若新增節點改變原格中直接父子關系，則還需進行刪除連線處理，而增加或刪除連線都會影響節點所對應SLIT，從而影響節點所對應的規則。
在圖3中，4＃節點的SLIT需要發生改變，因此它所對應的精確規則和近似規則都需要改變。根據定理，4＃所對應的規則應該進行刪除操作或修改操作。3＃節點所對應的SLIT沒有發生改變，但該子節點發生變化，新增加的5＃節點是原4＃節點的子集。其近似規則的計算根據命題1得出。
在圖3中，5＃為新增節點，對應了3＃和4＃之間的連線刪除操作，同時增加了3＃和5＃的連線增加操作。此時對于3＃節點，原近似規則為{[c][fh]}，現近似規則為{[c][f]}，重新產生的規則后件集合為原規則后件集合的子集。
3基于量化規則格的規則產生算法描述及示例
3．1基于量化規則格的規則產生算法描述
基于量化規則格的規則漸增更新算法思想是利用量化規則格的構造算法，在每個節點SLIT形成的同時，產生相應的關聯規則，即SLIT的變化也將導致關聯規則的變化。
由于只有發生節點間父子關系的調整，節點的SLIT才可能發生變化，而節點之間的變化只有增加連線和刪除連線兩種情形。在量化規則格的形成過程中[12]分別用兩個子程序add_line(Icd，Ipt，SLIT)和del_line(Icd，Ipt，SLIT)來實現增加連線和刪除連線的處理。為了在SLIT更新時更新相應的規則，本文對關聯規則（精確規則和近似規則）采用規則前件和規則后件來表示。例如：AB，A稱為規則前件，B稱為規則后件。基于文獻[11]中的思想，量化精確規則的前件由SLIT表示，后件則由本身的內涵與SLIT的差集構成；量化近似規則的前件由SLIT表示，后件則由子節點的內涵與SLIT的差集來表示。因此，利用量化規則格實現規則的漸增更新只要在這兩個子程序中增加一些對規則的處理即可。
在add_line(Icd，Ipt，SLIT)中增加了五個基本功能模塊。其意義為：getAntecedentsE()返回精確規則的前件、getConsequentsE()返回精確規則的后件、getAntecedentsA()返回近似規則的前件、getConsequentsA()返回近似規則的后件、getConsequentsA().getFirst()返回近似規則后件所對應的子節點內涵。
在add_line(Icd，Ipt，SLIT)函數中，當節點間產生連線后，子節點(Icd)的SLIT發生變化，則近似規則和精確規則也需要計算；而Icd節點的近似規則隨父節點的增加，需要重新計算；對于每一個新增節點，其SLIT必然為空，因此對應的所有規則可以直接追加即可。
下面的算法中斜體字的部分用于處理SLIT，正體字的部分用來處理規則。
PROCEDURE add_line(Icd:子節點項集，Ipt:父節點項集，SLIT:子節點對應的最小項集集合)
SLIT_new= Φ
SLIT_keep=Φ
Diff=Icd－Ipt
FOR SLIT中的每個項集Item DO
Temp = Item∩Diff
IF Temp ≠Φ THEN SLIT_keep = SLIT_keep∪{ Item } ENDIF
ENDFOR
SLIT_updt=SLIT \\ SLIT_keep
IF SLIT_updt為空 THEN//處理新增節點的精確規則
FOR Diff 中得每個元素Elem DO
SLIT_new = SLIT_new∪{Elem}
增加Icd的精確規則[SLIT_new][Intent(Icd)－SLIT_new]
//增加新增節點的近似規則
FOR Icd節點所對應的children節點Icd_child DO
增加Icd的近似規則[SLIT_new][Intent(Icd_child)－SLIT_new]
ENDFOR
ENDFOR
ELSE
FOR SLIT_updt的每個項集Item1 DO
FOR Diff中的每個元素Elem DO
itemnew= Item1∪Elem
IF SLIT_keep≠Φ且SLIT_keep的每個項集Item2itemnew THEN
SLIT_new = SLIT_new∪{ itemnew}
/*處理新增節點的child節點的規則變化，由前面推論可知，增加連線規則不會減少*/
更新Icd的精確規則為
[getAntecedentE(Item1)∪{itemnew}][getConsequentE(Item1)－{itemnew}]
更新Icd的近似規則為
[getAntecedentA(Item1)∪{itemnew}][getConsequentA(Item1)－{itemnew}]
ENDIF
ENDFOR
ENDFOR
ENDIF
SLIT= SLIT_new∪SLIT_keep
RETURN
在進行刪除連線的操作后，調用del_line(Icd，Ipt，SLIT)函數對SLIT進行更新?？紤]到Icd子節點的SLIT可能發生了變化，即需要更新Icd節點的精確規則和近似規則；而Ipt節點減少了一個子節點，因此其對應的近似規則也需要更新。
PROCEDURE del_line(Icd:子節點項集，Ipt:父節點項集，SLIT:子節點對應的最小項集集合)
SLIT_new= Φ
Diff=Icd－Ipt
FOR SLIT中的每個項集Item，按|Item|升序 DO
IF | Diff |=1 THEN SLIT_new = SLIT_new∪{ Item－Diff }
ELSE
Temp= Item∩Diff
Itemnew=Item
IF | Temp |=1 且TempDiff_other THEN
Itemnew = Item –Temp
//更新新增節點的子節點Icd的近似規則和精確規則
FOR Icd的所有近似規則i DO
IF getAntecedentsA(i).Contains(Temp) THEN
更新近似規則[getAntecedentsA(i)－Temp][getConsequentsA(i)+Temp]
更新精確規則[getAntecedentsE(i)－Temp][getConsequentsE(i)+Temp]
ENDIF
ENDFOR
ENDIF
IF SLIT_new中的每個項集Item1itemnew THEN
SLIT_new = SLIT_new∪{ itemnew }
ENDIF
ENDIF
ENDFOR
SLIT= SLIT_new
//更新Ipt節點的近似規則
newItem=Intent(Icd)－Intent(Ipt)
FOR Ipt所有的近似規則i DO
IF getConsequentsA(i).getFirst().equal(Intent(Icd)) THEN
更新近似規則為[getAntecedentsA(i)][getConsequentsA(i)+newItem]
ENDIF
ENDFOR
RETURN
3．2示例描述
表1所示的是一示例形式背景，其對應的量化規則格如圖4所示。
圖中11#節點為加入事務后的新增節點，它所對應的精確規則和近似規則需要增加。相關的父子節點所對應的精確規則和近似規則需要進行相應的計算，需更新的規則如表3所示。
4結束語
在量化規則格的構造基礎上，引入規則的漸增生成，即隨著事務對象的不斷插入，相應節點的規則能動態產生。從整體上來說，要比先構造概念格，再提取規則的算法，更能有效地利用已存在規則。目前，本文提出的算法能隨著事務對象的新增而使規則動態更新，但在事務刪除的情況下，尚不能解決。因此下一步工作將如何實現在事務刪除情況下能對已存在規則再次利用，實現在事務集動態變化情況下，高效地提取出相關規則。
參考文獻：
［1］GANTER B， WILLE R. Formal concept analysis:mathematical foundations[M]. Berlin: Springer－Verlag，1999.
[2]GODIN R， MISSAOUI R， ALAOUI H. Incremental concept formation algorithms based on galois (concept) lattices[J].Computatio－nal Intelligence，1995，11(2): 246－267.
[3]MERWE D van der，OBIEDKOV S，KOURIE D. AddIntent：a new incremental algorithm for constructing concept lattice:proc. of the Second International Conference on Formal Concept Analysis(ICFCA2004)[C].Sydney:[s.n.]，2004:372－385.
[4]謝志鵬，劉宗田.概念格與關聯規則發現[J].計算機研究與發展，2000，37(12): 1415－1421.
[5]PASQUIER N，BASTIDE Y，et al.Efficient mining of association rules Using closed itemset lattices[J].Information Systems，1999，24(1):25－46.
[6]ZAKI M J， HSIAO C J. CHARM:an efficient algorithm for closed association rule mining，technical report 99－10[R].[S.l.]:Rensselaer Polytechnic， 1999.
[7]VALTCHEV P，MISSAOUI R，GODIN R，et al.Generating frequent itemsets incrementally: two novel approaches based on galois lattice theory[J].Journal of Experimental and Theoretical Artificial Intelligence，2002，14(2－3):115－142.
[8]BASTIDE Y， PASQUIER N，et al. Mining minimal non－redundant association rules using frequent closed itemsets:Lecture Notes in Computer Science[C].[S.l.]:[s.n.]，2000:972－986.
[9]LI Yun， LIU Zongtian，CHENG Wei，et al. Extracting minimal non－redundant implication rules by using quantized closed itemset lattice:proceedings of the 16th International Conf. on Soft Engineering and Knowledge Engineering(SEKE’04)[C].Banff:[s.n.]，2004:402－405.
[10]LI Yun， LIU Zongtian，CHENG Wei，et al.Extracting minimal non－redundant approximate rules based on quantitative closed itemset lattice[J].Journal of Fudan:Nature Science， 2004，43(5):801－804.
[11]LI Yun， LIU Zongtian，CHENG Wei，et al.Extracting minimal non－redundant associate rules from QCIL:proceedings of the 4th Internatio－nal Conf. on Computer and Information Technology(CIT’04)[C].Wuhan:[s.n.]，2004:986－991.
[12]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large database:proceedings of the ACM SIGMOD Conference on Management of Date[C].New York:ACM press，1993:207－216.
[13]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules:proceedings of the 20th International Conference on very Large database[C].Santiago Chile:[s.n.]，1994:487－499.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
