Using metarules to organize and group discovered association rules

對於小型資料集來說，Association Mining Algorithm 能輕易地找出項目之間的關係，並產生關聯規則供使用者解讀。但若要處理高維的資料集時，產生的大量關聯規則通常會讓使用者無褔消受，這是因為高維的資料集容易產生許多reduntdant rule，而reduntdant rule通常起因於規則之間的overlap及containment，必須加以刪除。本篇論文針對我們所找出來的discovered rules，加以組織、分群，減少discovered rules數量，並以metarule來幫助使用者了解discovered rules彼此間的關係，以求降低使用者解讀discovered rules時的負擔。

本篇論文提出的方法包含四個步驟：
1. Finding meatrules
所謂的metarules係由兩個所找出的association rules R1, R2組合而成的規則R1→R2. 同樣使用min_sup(=0)、min_conf(=70?) 來找出metarules, 用以表達discovered rules之間的關係．
2. Finding independent subgroups of rules
以圖形表示找出的discovered rules及metarules (以discovered rules 做為 node, metarules做為 edge)，從圖形中找出獨立不與其它subgroup連接的subgroup，即每一subgroup獨自表達特定的knowledge．
3. Reorganizing equivalent rules
兩個node: ri , rj 如果滿足以下條件，則表示此兩個association rules近乎相同，因此可以合併成一個node.
a. ri ∈ OUT(rj) and ri ∈ IN(rj), i.e. r
b. OUT(ri) \ {rj} = OUT(rj) \ {ri}
c. IN(ri) \ {rj} = IN(rj) \ {ri}
4. Pruning the discovered rules using metarules
刪除規則的基本原則是找出較為複雜的規則及較為明確的規則．complex relationship定義如下：兩條已知的association rules: ri , rj ，若 ri , rj 滿足equivalent relationship且ri 的前提為 rj 前提的子集，則rj 較ri複雜，此時我們刪除較複雜的且多餘的規則 rj ，因為ri 已經包含rj 的所要含括的知識。除了complex relationship之外，若rj ∈ OUT(ri) and rj ∈ IN(ri)，則我們可以說ri 較rj 更為明確。對於這種規則，因為它不一定會導致overfitting，而且也無特定的理由須將它刪除，所以作者認為交由使用者自行決定是否刪除較為恰當。

本篇論文使用7個資料集當作實驗對象，每一個資料集都減少一定比例的discovered rules。至於減少多少數量，使用者可自行設定confidence threshold來控制。實驗結果顯示愈低的confidence會產生愈多的metarules，愈多的metarules就愈容易滿足equivelent relationship，所以我們可以合併更多的discovered rules(node)以減少更多的node及metarules。如果我們認為兩條discovered rules所重疊資料要很多才算有關係的話，我們可以把metarules 的confidence threshold設高一點，如此會保留較多的discovered rules。

Data Mining and Knowledge Discovery, 2007, volume 14, pages 409-431