第3章
關聯(lián)規(guī)則挖掘
3.1基本概念
關聯(lián)規(guī)則挖掘是用來發(fā)現(xiàn)大量數據中項集之間有趣的關聯(lián)聯(lián)系。如果兩項或多項屬性之間存在關聯(lián)，那么其中一項的屬性就可以依據其他屬性值進行預測，關聯(lián)規(guī)則挖掘是數據挖掘中的一個重要課題，*近幾年已被業(yè)界深入研究和廣泛應用。
關聯(lián)規(guī)則研究有助于發(fā)現(xiàn)交易數據庫中不同商品（項）之間的聯(lián)系，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。分析結果可以應用于商品貨架布局、貨存安排以及根據購買模式對用戶進行分類。
關聯(lián)規(guī)則挖掘問題可以分為兩個子問題：*步是找出事務數據庫中所有大于等于用戶指定的*小支持度的數據項集；第二步是利用頻繁項集生成所需要的關聯(lián)規(guī)則，根據用戶設定的*小置信度進行取舍，*后得到強關聯(lián)規(guī)則。識別或發(fā)現(xiàn)所有頻繁項目集是關聯(lián)規(guī)則發(fā)現(xiàn)算法的核心，關聯(lián)規(guī)則的基本描述如下。
1.項與項集
數據庫中不可分割的*小單位信息稱為項（或項目），用符號i表示，項的集合稱為項集。設集合I={i1,i2,…,ik}是項集，I中項目的個數為k，則集合I稱為k項集。例如，集合{啤酒，尿布，奶粉}是一個3項集。
2.事務
設I={i1,i2,…,ik}是由數據庫中所有項目構成的集合，事務數據庫T={t1,t2,…,tn}是由一系列具有唯一標識的事務組成。每一個事務ti(i=1,2,…,n）包含的項集都是I的子集。例如，如果顧客在商場里同一次購買多種商品，這些購物信息在數據庫中有一個唯一的標識，用以標識這些商品是同一顧客同一次購買的，則稱該用戶的本次購物活動對應一個數據庫事務。
3.項集的頻數（支持度計數）
包括項集的事務數稱為項集的頻數（支持度計數）。
4.關聯(lián)規(guī)則
關聯(lián)規(guī)則是形如XY的蘊含式，其中X、Y分別是I的真子集，并且X∩Y=。X稱為規(guī)則的前提，Y稱為規(guī)則的結果。關聯(lián)規(guī)則反映X中的項目出現(xiàn)時，Y中的項目也跟著出現(xiàn)的規(guī)律。
5.關聯(lián)規(guī)則的支持度（support）
關聯(lián)規(guī)則的支持度是交易集中同時包含X和Y的交易數與所有交易數之比，它反映了X和Y中所含的項在事務集中同時出現(xiàn)的頻率，記為support（XY），即
support(XY)=support(X∪Y)=P(XY)(31)
6.關聯(lián)規(guī)則的置信度（confidence）
關聯(lián)規(guī)則的置信度是交易集中同時包含X和Y的交易數與包含X的交易數之比，記為confidence（XY），置信度反映了包含X的事務中出現(xiàn)Y的條件概率。
confidence（XY）=support(X∪Y)support(X)=P(Y|X)(32)
7.*小支持度與*小置信度
通常用戶為了達到一定的要求，需要指定規(guī)則必須滿足的支持度和置信度閾限值，此兩個值稱為*小支持度閾值(min_sup)和*小置信度閾值(min_conf)。其中，min_sup描述了關聯(lián)規(guī)則的*低重要程度，min_conf規(guī)定了關聯(lián)規(guī)則必須滿足的*低可靠性。
8.強關聯(lián)規(guī)則
如果support（XY）≥min_sup且confidence(XY)≥min_conf，則稱關聯(lián)規(guī)則
XY為強關聯(lián)規(guī)則；否則，稱XY為弱關聯(lián)規(guī)則。通常所說的關聯(lián)規(guī)則一般是指強關聯(lián)規(guī)則。
9.頻繁項集
設UI，項目集U在數據集T上的支持度是包含U的事務在T中所占比例，即
support(U）=‖{t∈T|Ut}‖‖T‖（33）
式中，‖·‖表示集合中元素數目。對項目集I，在事務數據庫T中所有滿足用戶指定的*小支持度的項目集，即不小于min_sup的I的非空子集，稱為頻繁項目集或大項目集。
10.項目集空間理論
Agrawal等建立了用于事務數據庫挖掘的項目集空間理論，理論的核心為：頻繁項目集的子集仍是頻繁項目集，非頻繁項目集的超集是非頻繁項目集。
3.2關聯(lián)規(guī)則挖掘算法——Apriori算法原理
3.2.1Apriori算法原理解析
*著名的關聯(lián)規(guī)則發(fā)現(xiàn)方法是R.Agrawal提出的Apriori算法。
1.Apriori算法基本思想
Apriori算法基本思想是通過對數據庫的多次掃描計算項集的支持度，發(fā)現(xiàn)所有的頻繁項集，從而生成關聯(lián)規(guī)則。Apriori算法對數據集進行多次掃描。*次掃描得到頻繁1項集的集合L1，第k（k>1）次掃描首先利用第k-l次掃描的結果Lk-1產生候選k項集的集合Ck，然后在掃描的過程中確定Ck中元素的支持度，*后在每一次掃描結束時計算頻繁k項集的集合Lk，算法當候選k項集的集合Ck為空時結束。
2.Apriori算法產生頻繁項集的過程
產生頻繁項集的過程主要分為連接和剪枝兩步，如下所示。
（1）連接步。為了找Lk(k≥2），通過Lk-1與自身作連接產生候選k項集的集合Ck，設l1和l2是Lk-1中的項集，記li［j］表示li的第j個項。Apriori算法假定事務或項集中的項按字典次序排序，對于（k-1）項集li，對應的項排序為：li1
3.Apriori算法的主要步驟
（1）掃描全部數據，產生候選1項集的集合C1。
（2）根據*小支持度，由候選1項集的集合C1產生頻繁1項集的集合L1。
（3）對k>1，重復執(zhí)行步驟（4）、（5）和（6）。
（4）由Lk執(zhí)行連接和剪枝操作，產生候選（k+l）項集的集合Ck+1。
（5）根據*小支持度，由候選（k+l）項集的集合Ck+1，產生頻繁（k+1）項集的集合Lk+1。
（6）若L≠，則k=k+1，跳往步驟（4）；否則，跳往步驟（7）。
（7）根據*小置信度，由頻繁項集產生強關聯(lián)規(guī)則，結束。
4.Apriori算法描述
輸入：數據庫D，*小支持度閥值min_sup。
輸出：D中的頻繁集L。
偽代碼描述：
//找出頻繁1項集
L1=find_frequent_1-itemsets(D);
For(k=2;Lk-1!=null;k++){
//產生候選，并剪枝
Ck=apriori_gen(Lk-1);
//掃描D進行候選計數
Foreach事務tinD{
Ct=subset(Ck,t);//得到t的子集
Foreach候選c屬于Ct
c.count++;
}
……
新書資訊