關(guān)聯(lián)規(guī)則的性質(zhì)

關(guān)聯(lián)規(guī)則是提取數(shù)據(jù)的核心技術(shù)。r.agrawal等人首先提出了關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則是指定一組項目（元素）和記錄組。通過分析記錄組，我們可以看出相關(guān)性。關(guān)聯(lián)規(guī)則廣泛應(yīng)用于商業(yè)界、保險、金融、司法部門等。這對于研究非常重要。1相關(guān)規(guī)則理論1.1關(guān)聯(lián)規(guī)則xy定義1設(shè)I={i1,i2,…,im}是由m個不同的屬性(謂詞或項目)組成的集合(習(xí)慣上我們還稱I為項集,但其中的元素與R.Agrawal等人的定義有所不同,這里項集中的元素可能是謂詞或項目,而R.Agrawal等人定義的項集僅包含項目).給定一個數(shù)據(jù)庫D,其中的每一個記錄T是I中一組屬性的集合,即T?I,T有一個唯一的標(biāo)識符TID.若集合X?I且X?T,則記錄T包含集合X.一條關(guān)聯(lián)規(guī)則就是形如X?Y的蘊涵式,其中X?I,Y?I,X∩Y=Ф.關(guān)聯(lián)規(guī)則X?Y成立的條件是:(1)它具有支持度S.即數(shù)據(jù)庫D中至少有S%的記錄包含X∪Y,(2)它具有置信度C.即在數(shù)據(jù)庫D中包含的X記錄至少有C%的同時也包含Y.習(xí)慣上將關(guān)聯(lián)規(guī)則表示為X?Y(S%,C%).其中,支持度定義了項目在整個數(shù)據(jù)庫中所占的比例;置信度定義了發(fā)現(xiàn)規(guī)則的強度.根據(jù)上面的論述,關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)任務(wù)或問題可以定義為:給定一個事務(wù)數(shù)據(jù)庫D,求出所有滿足最小支持度Smin和最小置信度Cmin的關(guān)聯(lián)規(guī)則.1.2最小支持度的計算目前關(guān)聯(lián)規(guī)則的算法很多,但所有的采掘算法不論它是采用什么數(shù)據(jù)結(jié)構(gòu),其復(fù)雜度、效率如何,都可以分為如下幾個步驟:(1)預(yù)處理與采掘任務(wù)有關(guān)的數(shù)據(jù).根據(jù)具體問題的要求對數(shù)據(jù)庫進行相應(yīng)的操作,從而構(gòu)成規(guī)格化的數(shù)據(jù)庫D.(2)針對D,求出所有滿足最小支持度的項集,即大項集.由于一般情況下我們所面臨的數(shù)據(jù)庫都比較大,所以此步是算法的核心.(3)生成滿足最小置信度的規(guī)則,形成規(guī)則集R,解釋并輸出R.因為第(2)步是采掘關(guān)聯(lián)規(guī)則問題的重點與難點,所以目前大部分研究集中在此步驟上.2頻繁項目集的生成關(guān)于關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的算法相當(dāng)多,但絕大部分是經(jīng)典算法Apriori的演繹和改進.Apriori是一種寬度優(yōu)先算法,通過對數(shù)據(jù)庫D的多趟掃描來發(fā)現(xiàn)所有的頻繁項目集,在每一趟掃描中只考慮具有同一長度K(即項目集中所含項目的個數(shù))的所有K-項目集.在第一趟掃描中,Apriori算法計算數(shù)據(jù)庫D中所有單個項目的支持度,生成所有長度為1的頻繁項目集.在后續(xù)的每一趟掃描中,首先以前一趟中所發(fā)現(xiàn)的所有頻繁項目集為基礎(chǔ),生成所有新的候選項目集(CandidateItemsets),即潛在的頻繁項目集,然后掃描數(shù)據(jù)庫D,計算這些候選項目集的支持度,最后確定候選項目集中哪一些真正成為頻繁項目集.重復(fù)上述過程直到再也發(fā)現(xiàn)不了新的頻繁項目集.算法高效的關(guān)鍵在于生成較小的候選項目集,也就是盡可能不生成和計算那些不可能成為頻繁項目集的候選項目集.它利用了這樣一個基本性質(zhì):即一個頻繁項目集的任一子集必定也是頻繁項目集.這個性質(zhì)被目前的絕大部分關(guān)聯(lián)規(guī)則算法所繼承.關(guān)于Apriori的具體算法描述如下:輸入:數(shù)據(jù)庫D和最小支持度;輸出:存在于數(shù)據(jù)庫D中的大項集L;ProcedureApriori()BeginL1={large1-itemsets};For{k=2;L[k-1]<>nil;k++}doBeginC[k]=Apriori-gen(L[k-1]);Foralltransactionst∈DdoBeginC[t]=subset(C[k],t);ForallcandidatesC∈C[t]doccount++;End;L[k]={C∈C[k]∣ccount>=minsup};End;Gen-rules(L[k]);End;Functionapriori-gen(L[k-1]);InsertintoC[k],SelectCp,Cp,…,Cp[k-2],Cp[k-1],Cq[k-1]FromL[k-1]CpL[k-1]CqWhereCp=Cq,Cp=Cq,…,Cp[k-2]=Cq[k-2],Cp[k-1]<Cq[k-1];If(k-1)-subsetcofC[k],cL[k-1]thendeletecfromC[k];ReturnC[k];3其他2-2參與實驗的hish過濾器由Park等人提出的DHP(DirectHashandPruning)算法試圖用一個Hash過濾器在第2趟減小C2來改進Apriori的性能.他們認(rèn)為C2通常是最大的,算法的絕大部分時間消耗在生成頻繁2-項目集上.實際上,C2并不見得是最大的,尤其是交易的平均長度較長以及項目個數(shù)較少的時候.DHP在第1趟中掃描交易的同時構(gòu)造一個Hash過濾器.對于包含在某條交易中的每一個2-項目集,將該項目集所對應(yīng)的Hash桶的計數(shù)加1.當(dāng)這一趟掃描結(jié)束時,對于出現(xiàn)在交易數(shù)據(jù)庫中的每個2-項目集,就得到了它的支持度計數(shù)的一個上限.然后在用L1來生成C2時,對每個候選項目集進行Hash,如果它在Hash表中的支持度計數(shù)小于最小支持度,那么就將它刪去.Park等人通過他們的實驗認(rèn)為DHP在第1趟中由于要構(gòu)造Hash過濾器導(dǎo)致它的執(zhí)行時間要比Apriori長,但在第2趟中將明顯快于Apriori.然而Agrawal和Shafer指出Park等人的這一優(yōu)化實際上降低了Apriori的執(zhí)行速度.既然C2中的任何候選項目集都不能被Apriori算法所修剪,它就等于L1和L1的笛卡爾積.因此C2中可以被表示成一個簡單的二維支持度計數(shù)數(shù)組,這樣一來將顯著地減少對內(nèi)存的需求以及函數(shù)調(diào)用的開銷.任何由于使用Hash過濾器修剪C2所得的時間節(jié)余,都會因為構(gòu)造Hash過濾器以及使用通常的Hash樹來保存C2和進行支持度計數(shù)的開銷所損失.4關(guān)聯(lián)規(guī)則的應(yīng)用4.1關(guān)聯(lián)規(guī)則挖掘為了獲得最大的利潤,零售商都在考慮如下問題:①銷售什么樣的商品?②怎樣設(shè)計優(yōu)惠券?③怎樣擺放貨架上的商品?了解顧客的購買習(xí)慣和偏愛會使他們對以上問題作出很好的決策.關(guān)聯(lián)規(guī)則采掘正好可以提供這些信息.在零售行業(yè),關(guān)聯(lián)規(guī)則采掘的最有效的應(yīng)用就是對市場籃子數(shù)據(jù)進行分析,從而得到顧客的購買特性,并將發(fā)現(xiàn)的結(jié)果進行有效的行動.例如,所有以“面包”作為后件的關(guān)聯(lián)規(guī)則會使零售商知道采取什么樣的措施能夠促進它的銷售.4.2關(guān)聯(lián)規(guī)則采血技術(shù)在金融風(fēng)險分析中的應(yīng)用金融服務(wù)