文|光大科技大數據部 魏樂 盧格潤
1 關聯規則1.1 關聯規則基本概念1.2 Apriori算法基本思路2 關聯分類2.1 CBA關聯分類算法思路2.2 CBA算法實現總結關聯規則（Association Rules）由Agrawal等人在1993年的文獻中提及，並逐漸流行起來，主要用於發掘大量數據中項的相關關係。這種利用頻繁項集挖掘潛在關係的技術對於貨架擺放、購物推薦、捆綁銷售和新聞推薦等都很有應用價值。但在實際應用中，人們可能更願意關注由關聯規則理論挖掘出的頻繁項集，常將其用作基礎數據處理，再集成其他算法從而解決實際問題，比如說數據挖掘中常見的分類問題。關聯分類（Associative Classification）是基於關聯規則進行分類的一種集成挖掘算法，包括CMAR（Classfication based on Multiple Class - Association Rules)算法、CAEP（通過聚集模式顯露分類）、CBA（Classification Based on Associations）關聯分類算法等。其中CBA算法因為其簡單、易實現、準確率較高，被廣泛應用於各個領域。
1 關聯規則
1.1 關聯規則基本概念[1]
根據關聯規則的定義：
關聯規則是形如 的蘊涵式，其中， 和分別稱為關聯規則的前件(antecedent或left-hand-side, LHS)和後件(consequent或right-hand-side, RHS) 。其中，關聯規則 ，存在支持度和信任度。
可以看出，所謂關聯規則是和之間存在的某種關係。為了明確這種關係，進一步引入如下概念：
設 ={,,...,}是所有項目的集合，為數據事務庫，其中每個事務T是項的集合，滿足。每個事務具有唯一標識符，稱為TID。設A是由項目構成的集合，即項集。事務T包含項集A。如果項集A中包含k個項目，則稱其為k項集。
項集就是項的集合。例如啤酒和尿布組成一個集合{啤酒、尿布}，其中啤酒和尿布為項，{啤酒、尿布}為項集，而且是2項集。
項集中的項X、Y同時發生的概率稱之為關聯規則的支持度。
項集中項X發生的情況下，則Y發生的概率為關聯規則的置信度。
回到 的蘊涵式，，，如果事務資料庫中由的事務包含，則稱關聯規則 的支持度為，關聯規則的信任度為 .舉例來說：
、 支持度和置信度為：>> （50%，100%); >> （50%，50%)給定最小支持度閾值minSup和最小置信度閾值minConf。如果項集的支持度大於等於minSup，則稱其為頻繁項集。同時，項集的置信度大於等於minConf，則為強關聯規則。假設本例中最小支持度閾值minSup為，最小置信度閾值minConf為。可以看到上例中，{ }是頻繁項集，但是只有 >> 為強關聯規則。
1.2 Apriori算法基本思路
關聯規則的挖掘可以分為兩步，第一步找到頻繁項集，第二步從頻繁項集中再找出滿足最小置信度的強關聯規則。整體來看，第二步比較簡單，主要算力都耗費在第一步上，如果採用統計方法，需要將所有K項集統計一遍，費時耗力。Agrawal等人於1994年發表的Apriori算法，利用了頻繁項集的先驗知識來壓縮搜索空間，成為較為有效和有影響力的經典算法之一。
頻繁項集反單調性：頻繁項集的所有非空子集都是頻繁的。即，非頻繁項集的超集一定是非頻繁的。
利用該性質，可以先對項集進行剪枝，這樣對於非頻繁項集的超級就都不用計算其支持度，減少了計算量。所以利用Apriori算法計算頻繁項集可以分為兩步：
連接步：將 和 自連接，產生候選k項集。剪枝步： 是 的超集， 中項集可以是也可以不是頻繁的，根據反單調性對 進行剪枝,得到包含所有頻繁k項集的 。為了更好的說明以上步驟，可以參看如下示例：
給定最小支持度閾值minSup為，候選項集 中 支持度只有20%，所以剪除，得到頻繁1項集 。對 做自連接，產生候選2項集 。繼續進行迭代，分別得到頻繁2項集 和候選3項集 ， 不滿足最小支持度閾值剪除。則得到的最終結果為頻繁1項集 和頻繁2項集 。
2 關聯分類
關聯分類是分類數據挖掘技術中的重要分支，分類的目的是根據已有數據集通過學習找到一個目標函數，該函數將屬性集映射到目標類集。這樣對於新進樣本，就可以根據其的特徵，預測其所屬類集。
2.1 CBA關聯分類算法思路[2]
CBA算法全稱是Classification Based on Associations，在1998年由Bing Liu等提出，是基於關聯規則進行分類的算法。這一算法首次將關聯規則用於分類，很多之後的分類算法都將其作為baseline。近年來，對CBA算法的加強改進提高了其效率，使得CBA算法能夠更廣泛地運用到實際業務場景中。
CBA算法引入了一個概念稱為類別關聯規則(CAR)，這一規則在原來 的基礎上給蘊含式的後件(RHS)添加了限制條件，限制每個規則的後件只包含一個項以對應一個分類標籤，其中關聯規則的挖掘，使用了類Apriori算法。
在挖掘CARs之前，需要對特徵做離散化，這樣可將每一行數據轉化為事務記錄的形式，以鳶尾花數據集為例：
其中
{, , ,,}
為一條事務記錄。
有了這樣的事務庫，接下來便可按照如下步驟進行分類：
通過Apriori算法挖掘CARs;對所得到的CARs進行剪枝和排序;根據第一條能匹配上的類別規則獲得對應分類Apriori所挖掘出來的所有CARs並不能直接使用，因為即使是在很小的數據集上，CARs的總量依舊可能很大。除此以外，可能存在相衝突的關聯規則以及沒有默認規則也會給分類帶來困難。
為了應對這些問題，CBA採用了如下排序規則和默認策略：
置信度更大的規則優先級更高；置信度一樣，支持度更大的規則優先級更高；置信度和支持度都一樣，先產生的規則優先級更高（根據Apriori算法，前件包含更少項的規則會更早產生，因此優先級更高）；對於沒有被已有規則包括在內事務記錄，把其中佔比最大的類別標籤作為後件，空集作為前件，形成默認的類別關聯規則。2.2 CBA算法實現
目前，CBA可以通過3個R算法包實現：arc[3]；arulesCBA[4]；rCBA[5]。
其中，arc為純R實現的算法包，arulesCBA和rCBA則分別結合了C和JAVA實現，這也使得arc的運行速度會慢於其餘兩個，不能承載過大的數據量；在特徵離散化上，arc使用了最小描述長度準則（MDLP)進行離散化處理，arulesCBA可以選擇包括MDLP、Chi2在內的多種離散化方法，rCBA則不包括內建離散化處理；對於置信度和支持度的閾值選擇上，arc和rCBA支持自動調參，而arulesCBA不支持。除此以外，rCBA支持FP-growth代替Apriori算法進行關聯規則挖掘。
這裡以arc為例介紹如何使用CBA算法進行分類：
使用鳶尾花數據集，分為80%訓練集和20%測試集data("iris")set.seed(123)iris <- iris[sample(seq(nrow(iris))), ]iris_train <- iris[1:(nrow(iris)*.8), ]iris_test <- iris[-(1:(nrow(iris)*.8)), ]載入arc包創建分類器。cba()可以自動採用最小描述長度準則對特徵進行離散化處理。cba()同樣支持自動閾值調節，根據目標規則數調節置信度和支持度的取值。library("arc")classifier <- arc::cba(iris_train, "Species")inspect(classifier@rules) lhs rhs support confidence coverage lift count lhs_length[1] {Petal.Length=[-Inf;2.45]} => {Species=setosa} 0.333333331.00000000.333333333.00000040.0001.000[2] {Sepal.Length=(5.55; Inf], Petal.Length=(2.45;4.75]} => {Species=versicolor} 0.183333331.00000000.183333333.42857122.0002.000[3] {Sepal.Width=(3.25; Inf], Petal.Width=(1.75; Inf]} => {Species=virginica} 0.058333331.00000000.058333332.6666677.0002.000[4] {Petal.Width=(1.75; Inf]} => {Species=virginica} 0.333333330.97560980.341666672.60162640.0001.000[5] {Petal.Length=(2.45;4.75]} => {Species=versicolor} 0.258333330.96875000.266666673.32142931.0001.000[6] {} => {Species=virginica} 0.375000000.37500001.000000000.0000000.3750.375使用分類器進行預測pred<-predict(classifier,iris_test)table(pred,iris_test$Species)pred setosa versicolor virginica setosa 1000 versicolor 0130 virginica 0253 總結
本文主要介紹了關聯規則以及基於關聯規則的一種關聯分類算法CBA（Classification base of Association）。
關聯規則是在支持度-置信度框架下的統計算法。Apriori算法主要利用頻繁項集反單調性對統計過程進行簡化，提高了運算效率。CBA算法是使用了類Apriori關聯規則的分類算法，其引入了類別關聯規則(CAR)的概念，這一規則在原的基礎上給蘊含式的後件添加了限制條件以對應分類標籤。參考資料
[1] 沈斌．關聯規則技術研究：浙江大學出版社，2012年: http://e.dangdang.com/products/1900292695.html
[2] Integrating Classification and Association Rule Mining: https://www.aaai.org/Papers/KDD/1998/KDD98-012.pdf
[3] arc: Association Rule Classification: https://cran.r-project.org/web/packages/arc/
[4] arulesCBA: Classification Based on Association Rules: https://cran.r-project.org/web/packages/arulesCBA/
[5] rCBA: CBA Classifier: https://cran.r-project.org/web/packages/rCBA/index.html
我們是光大科技公司的追光算法實驗室團隊，將不定期推出數據挖掘和算法相關的數據科學原創文章。團隊定位打造基於知識驅動的機器學習算法實驗室，由實踐經驗豐富的數據分析挖掘工程師和專注算法的數據科學家精心準備相關作品，志在分享結合實際業務的理論應用和算法創新，以及其中的心得體會。