Mining Customer Value From Association Rules to Direct Marketing

對於傳統的行銷方法而言，企業在決定行銷對象時，大多無特定目標發送廣告訊息。但事實上願意回應的消費者總是很少，造成企業在行銷資源上的浪費及顧客的反感。所以近年來，「Direct marketing for profit optimization」成為企業最想應用data mining技術解決的問題之一，它同時也是ACM在1998年所舉辦的KDD-CUP競賽問題。

一般而言，企業必須在考慮每份廣告的行銷成本之下，找出潛在傾向回應的消費者，進而只針對該消費族群行銷，並使得企業獲得的利益最大化。然而，它通常會面臨「imbalanced data」及「inverse correlation」的挑戰。在一般的狀況下，付諸回應行動的消費者佔整體行銷名單的比例非常少(在KDD-CUP-98 dataset中只佔5%)，而大部分的data mining演算法卻是偏好學習資料整體的行為規則，所以要學習在稀少類別的規則是較困難的。另一方面，愈是可能回應的消費者，通常對企業貢獻的利益則愈少，所以若只想對願意回應的消費者行銷，成效相當有限。

以往的研究工作大多先預估顧客願意回應的機率，然後在較可能回應的顧客名單之中，再找出貢獻較大的族群做為行銷對象。他們的缺失在於顧客的貢獻在先前預測回應機率的步驟被忽略，尤其是當inverse correlation現象存在的時候，潛在較大貢獻的族群更是越容易被剔除。所以本篇論文使用focus association rule一次學習顧客回應及其貢獻這兩種行為，作法分成三個步驟。

我們取50%作為learning set，50%作為validation set。再從learning set中取出70%作為building set，30%作為testing set for turning minsup, maxsup

1. Rule Generating

我們在回應名單的資料集中，尋找大於使用者自訂minimum support的frequent item(稱為focus item)，而且此focus item的出現次數必須低於在非回應名單資料集中的maximum support。然後再從回應名單資料集中找由focus item組成的frequent itemset做為"respond rule"。因為我們只從回應名單資料集中找frequent itemset，所以能解決「imbalanced data」問題。除此之外，我們可設定較低的minimum support以避免刪除profitable rules，同時也可設定maximum support來決定所要刪除的focus item數量，以控制演算法的效能及資料維度(可解決high demensionality問題)

2. Model Building

計算每條respond rule在building set中的平均獲利，並決定規則Cover record的順序: Average Profit > Generality > Simplicity > Totality of order

3. Model Pruning

預估每條respond rule在預測的testing error (pessimistic estimation)，進而計算出每條respond rule預估的期望獲利。然後把建立由respond rule組成的covering tree，以bottom-up的方式，刪除期望獲利較低且較specific的規則

本篇論文最後產生的平均獲利高於KDD-Cup-1998第一名41%，也高於2001年之前所發表的三篇論文，傳送的mail數量也是最低。檢視TOP 10的規則，我們發現高獲利的規則不一定擁有較高的support及confidence，代表這些規則不一定是經常出現或是能準確地判斷顧客是否respond。最後，作者認為結果會有這麼顯著的提升是因為association rule克服了inverse correlation，並且擁有global search及不用預測顧客回應機率的優點。

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

Lazy Associative Classification

這篇paper主要是介紹了一個新的associative classification的作法。一般來說，associative classifier會比decision tree classifier的準確率要來得高。因為decision tree classifier 是用greedy(local) search的方法，選出目前擁有最高information gain的attribute，加進tree裡面形成新的split node，對於此node的子樹來說，皆為該attribute與其他所剩下的attribute中，挑選擁有最高information gain的attribute來繼續splitting，直到所有的instance屬於同一個class或是此node已低於某特定的minimum support threshold等等。decision tree classifier的特點是快速且容易明瞭，缺點為local search的情況下容易忽略了important rules。association rule classifier可以解決此問題，透過global search的方式，可以產生large number of rules。但是該優點正也是缺點所在，產生了大規模的rule set，許多的rule在分類的過程中甚至幾乎沒有用到，整體效率不彰。
因此本篇作者提出了lazy associative classification的觀念，相比於一般的 (eager) associative classification，lazy associative classifier並不是對於所有的 training data皆產生了rule set，而是demand-driven basis，也就是只針對testing instance所擁有的feature去產生association rules，如此可以保證所產生的association rules一定至少跟testing data有若干關係，不至於發生在測試的過程中，只用到少數association rules的情形。
對於lazy associative classification，為了一開始就記錄test instance所包含的feature set，會用到比一般associative classification更多的workload，此問題在paper中也提到了可以用caching的方式解決。另一個問題是只針對test instance產生的association rule，代表的就是要犧牲部分的generalization和影響classification若干的accuracy。
最後實驗證實，lazy association classification可以降低10%的error rate，相比於一般的association classification；而若是跟decision tree classification相比，更可以減少近20%的error rate。



Proceedings of the Sixth International Conference on Data Mining 2006 (IEEE)

Adaptive-Support Association Rule Mining for Recommender Systems

一般來說，我們在使用Association Rule Mining Algorithm時，例如Apriori，我們必須事先設定minimum support threshold。 但如何選擇適當的值卻不是那麼直覺，常常只能依靠暴力法來解決。此外，也因為沒有對規則有所限制，所以任何的frequent itemset都會產生規則，使得執行時間大幅增加。

上述以market basket analysis為精神的演算法不適用於推薦系統。因為推薦系統常對特定使用者進行推薦商品的動作，所以不須產生所有的frequent itemset。此外推薦系統必須考慮執行效率，特別是要online運作的規則。所以在這篇論文中，作者根據前人的CBA-RG演算法精神加以修改成適合應用於推薦系統的演算法－ASARM。ASARM不須事先指定minimum support threshold，而是指定想要產生規則數的範圍，並且自動地調整minimum support值。所以ASARM不僅省去指定minimum support的困擾，還可以透過指定產生的規則數的方式來控制執行效率。除此之外，ASARM一次只產生特定使用者或特定商品的規則，以避免產生不相關的規則。

論文中除了提出ASARM演算法之外，在進行推薦工作時，作者先產生user association及article association的規則，並把兩者合併使用，使得能提升執行效率卻又不降低準確度。而實驗部分也探討各個參數對precision、recall、accuracy的影響，並觀察到一些現象加以分析。最後再與Billsus和Pazzani在1998年所提出的方法做比較，證明作者所提出的方法在accuracy方面優於Billsus和Pazzani的方法。

PDF檔案連結

Data Mining and Knowledge Discovery, Vol. 6, No. 1 / January, pp.83-105, 2002

Mining Risk Patterns in Medical Data

Association Rule 傳統上是為了所謂Basket Data所創造出來的規則，每筆資料並無所謂的類別。 因為有規則產生，很自然的可以應用在資料分類上，但是如何處理不同類別所找出的規則？過去有研究試過利用統計檢定（如Chi-square）來篩選這些規則，通常最後則以分類的結果來評估篩選方法的好壞。這篇選自KDD2005的論文，則是利用統計上常用的Relative Risk來篩選optimal risk patterns。Relative Risk本身沒有anti-monotone 的特性，但是在特殊情況下是有anti-monotone的特性，這也是這篇論文最主要的貢獻，但是篇幅關係，作者並未詳列在論文。本篇論文是Industry/Education Track所以較Research Track的內容較淺顯易懂。