版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
第七章關(guān)聯(lián)規(guī)則的挖掘一、關(guān)聯(lián)規(guī)則挖掘的含義關(guān)聯(lián)規(guī)則用于表示OLTP數(shù)據(jù)庫中諸多屬性(項集)之間的關(guān)聯(lián)程度。而關(guān)聯(lián)規(guī)則挖掘(AssociationRulesMining)則是利用數(shù)據(jù)庫中的大量數(shù)據(jù)通過關(guān)聯(lián)算法尋找屬性間的相關(guān)性。例:(超級市場)在購買商品A的客戶中有90%的人會同時購買商品B,則可用關(guān)聯(lián)規(guī)則表示為:支持度(Support)
同時購買A和B的客戶人數(shù)占總客戶數(shù)的百分比稱為規(guī)則的支持度。置信度(Confidence)
同時購買A和B的客戶人數(shù)占購買A的客戶人數(shù)的百分比稱為規(guī)則的置信度。由于在實際應(yīng)用中,概率P一般是無法事先給出的,所以常以頻度代替購買A的顧客購買B的顧客同時購買A和B的顧客(AB)如果不考慮關(guān)聯(lián)規(guī)則的支持度和置信度,那么在事務(wù)數(shù)據(jù)庫中存在無窮多的關(guān)聯(lián)規(guī)則。事實上,人們一般只對滿足一定的支持度和可信度的關(guān)聯(lián)規(guī)則感興趣。為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則,需要給定兩個閾值:最小支持度和最小置信度。關(guān)聯(lián)規(guī)則挖掘的實質(zhì)是在數(shù)據(jù)集合中尋找滿足用戶給定的最小支持度和最小置信度的規(guī)則。
例:交易情況如下表,要求最小支持度為50%,最小可信度為50%,則可得到:AC(50%,66.6%)CA(50%,100%)ID號購買的商品001A,B,C002A,C003A,D004B,E,F(xiàn)二、關(guān)聯(lián)規(guī)則挖掘算法:TheAprioriAlgorithm
Agrawal等人提出1、術(shù)語項集:在數(shù)據(jù)庫中出現(xiàn)的屬性值的集合。頻繁項集:滿足最小支持度要求的項集。關(guān)聯(lián)規(guī)則一定是在滿足用戶的最小支持度要求的頻繁項集中產(chǎn)生的,因此,關(guān)聯(lián)規(guī)則挖掘也就是在數(shù)據(jù)庫中尋找頻繁項集的過程。K_項集:包含K個項的項集。交易號購買的商品001A,B,C002A,C003A,D004B,E,F(xiàn)例:項集:{A,B,C,D,E,F(xiàn),..}1_項集:{A},{B},{C},..,{F}2_項集:{A,B},{A,C}….如要求最小支持度為50%,則:頻繁項集:{A},{B},{C},{A,C}頻繁項集的任何子集也一定是頻繁的??!2、關(guān)聯(lián)規(guī)則分類1)根據(jù)規(guī)則中所處理的值類型布爾關(guān)聯(lián)規(guī)則:規(guī)則考慮的關(guān)聯(lián)項是否存在量化關(guān)聯(lián)規(guī)則:規(guī)則描述的是量化的項或?qū)傩蚤g的規(guī)則2)根據(jù)規(guī)則中所涉及的數(shù)據(jù)維(1)是單維的,涉及buys;(2)多維,涉及年齡、收入和buys3)根據(jù)規(guī)則中所涉及的抽象層商品位于不同層,計算機的抽象層高,稱為多層關(guān)聯(lián)規(guī)則3、Apriori算法符號定義:Lk:k項頻繁集的集合;Ck:k項集的候補集合步驟:連接:
用Lk-1自連接得到Ck,(k>2)[注]
設(shè)l1,l2是有兩個有k-1個有序項的項集,lj[i]代表k-1個項的第i項(j=1,2;i=1,2,k-1)。l1和l2是可連接的l1Xl2,需滿足:
l1[1]=l2[1],l1[2]=l2[2],….,l1[k-2]=l2[k-2],
l1[k-1]≠l2[k-1],產(chǎn)生的項是:
l1[1]l1[2]….l1[k-2]l1[k-1]l2[k-1](lj[i]是有序的)*注:C2=由1_項集兩兩組合生成,共C2m(m為1_項集合的項數(shù))修剪:
一個k-項集,如果它的一個k-1項子集不是頻繁的,那它本身也不可能是頻繁的。例:l1={A,B,C},l2={A,B,D},l3={A,C,F}則:l1Xl2={A,B,C,D}l1X
l3,l2X
l3均為空為什么l1
X
l3不生成{A,B,C,F}?{A,B,C},{A,B,F(xiàn)}4、偽代碼:min_support為最小支持度
L1=找頻繁1_項集;for(k=2;Lk!=;k++){
Ck=由Lk-1生成候補集合;
foreach
t
∈
Ck
{
計算t在數(shù)據(jù)集合中出現(xiàn)的次數(shù);
if(出現(xiàn)計數(shù)小于min_support)
從Ck中剔除;
}
Lk=Ck;
}return
k
Lk;5、關(guān)聯(lián)規(guī)則挖掘例,(要求最小支持?jǐn)?shù)為2)數(shù)據(jù)庫D掃描DC1itemsetsup{12}1{13}2{15}1{23}2{25}3C2{35}2C2掃描DC3掃描DL3L1L26、可以產(chǎn)生哪些規(guī)則前面的例子中,得到一個頻繁集{2,3,5},非空真子集有{2},{3},{5},{2,3},{2,5},{3,5}L1L3L2規(guī)則:2353
255
2323
525
335
2置信度:2/3=66%({2,3,5}頻度/{2}頻度)2/3=66%({2,3,5}頻度/{3}頻度)2/3=66%({2,3,5}頻度/{5}頻度)2/2=100%({2,3,5}頻度/{2,3}頻度)2/3=66%({2,3,5}頻度/{2,5}頻度)2/2=100%({2,3,5}頻度/{3,5}頻度)支持度:2/4=50%7、Apriori
夠快了嗎?—性能瓶頸Apriori算法的核心:用頻繁的(k-1)_項集生成候選的頻繁k_項集用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度Apriori
的瓶頸:候選集生成巨大的候選集:104
個頻繁1_項集要生成107
個候選2_項集要找尺寸為100的頻繁模式,如{a1,a2,…,a100},你必須先產(chǎn)生21001030
個候選集(1_項集)多次掃描數(shù)據(jù)庫:如果最長的模式是n的話,則需要n次數(shù)據(jù)庫掃描為提高Apriori算法的性能,有許多改進的算法。8、如何在概念分層有效地挖掘多層關(guān)聯(lián)規(guī)則
一般采用自頂向下策略,由概念層1開始向下,到較低的更特定的概念層,對每個概念層的頻繁集累加計數(shù),直到不能再找到頻繁項集。計算機[支持度=10%]臺式機[支持度=6%]筆記本[支持度=4%]層1:minsup=5%層2:minsup=5%非頻繁
問題:因為較低層次抽象的項不大可能像較高層次抽象的項出現(xiàn)得那么頻繁。如果最小支持度閥值設(shè)置的太高,可能丟掉出現(xiàn)在較低抽象層次中有意義的關(guān)聯(lián)規(guī)則。如果閥值設(shè)置太底,可能會出現(xiàn)在較高抽象層的無興趣的關(guān)聯(lián)規(guī)則。對于所有層使用一致的最小支持度8、如何在概念分層有效地挖掘多層關(guān)聯(lián)規(guī)則
一般采用自頂向下策略,由概念層1開始向下,到較低的更特定的概念層,對每個概念層的頻繁集累加計數(shù),直到不能再找到頻繁項集。對于所有層使用一致的最小支持度在較低層使用遞減的最小支持度計算機[支持度=10%]臺式機[支持度=6%]筆記本[支持度=4%]層1:minsup=5%層2:minsup=3%9、冗余的多層關(guān)聯(lián)規(guī)則處理買筆記本買打印機[支持度=8%,置信度=70%](1)
買IBM筆記本買打印機[支持度=2%,置信度=72%](2)規(guī)則2有用嗎?它提供了新穎的信息嗎?
如果后一個具有較小一般性的規(guī)則,它不提供新的信息,應(yīng)當(dāng)刪除它!如果一個規(guī)則的祖先,它的支持度和置信度都接近于該規(guī)則的“期望”值,這個規(guī)則是冗余的。
從(1)的置信度=70%推斷:
買筆記本同時買打印機的交易數(shù)/買筆記本交易數(shù)=70%IBM筆記本屬于筆記本,因此置信度也應(yīng)該在70%左右。由(2)實際為72%,基本無差異。9、冗余的多層關(guān)聯(lián)規(guī)則處理買筆記本買打印機[支持度=8%,置信度=70%](1)
買IBM筆記本買打印機[支持度=2%,置信度=72%](2)規(guī)則2有用嗎?它提供了新穎的信息嗎?
如果后一個具有較小一般性的規(guī)則,它不提供新的信息,應(yīng)當(dāng)刪除它!如果一個規(guī)則的祖先,它的支持度和置信度都接近于該規(guī)則的“期望”值,這個規(guī)則是冗余的。
從(1)的支持度=8%推斷:
買筆記本同時買打印機的交易數(shù)/總交易數(shù)=8%,假定從數(shù)據(jù)集中還發(fā)現(xiàn),IBM筆記本在占整個筆記本銷量的25%。
則:買IBM筆記本的支持度應(yīng)該為8%*25%=2%,由(2)實際為2%,兩者相同。結(jié)論:規(guī)則(2)不是有趣的,因為它不提供有趣的信息。10、關(guān)聯(lián)規(guī)則的相關(guān)分析
強關(guān)聯(lián)規(guī)則不一定有趣其實,規(guī)則是誤導(dǎo),因為購買影碟機的可能性是75%,比66%還大。事實是:計算機游戲和影碟機是負相關(guān)的。
A和B的相關(guān)性:corrAB:<1,負相關(guān)
=1,A和B是獨立的
>1,正相關(guān),每一個出現(xiàn)蘊涵另一個出現(xiàn)例:在10000個交易中,6000個顧客交易包含計算機游戲,7500個顧客交易包含影碟機,4000個交易包含計算機游戲和影碟機。10、關(guān)聯(lián)規(guī)則的相關(guān)分析
強關(guān)聯(lián)規(guī)則不一定有趣其實,規(guī)則是誤導(dǎo),因為購買影碟機的可能性是75%,比66%還大。事實是:計算機游戲和影碟機是負相關(guān)的。例:在10000個交易中,6000個顧客交易包含計算機游戲,7500個顧客交易包含影碟機,40
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 提升表達能力課程設(shè)計
- 包裝材料質(zhì)量手冊第一版(一)
- 特殊計算器課程設(shè)計c
- 2024年藥房管理制度
- PEP小學(xué)英語三年級上冊Unit1 PartA Let's talk 同步課時練
- 財務(wù)工作總結(jié)應(yīng)收賬款與付款管理
- 導(dǎo)演行業(yè)人事工作總結(jié)
- 研究所保安工作總結(jié)
- 聚焦業(yè)績提升的年度工作方案計劃
- 股份接受協(xié)議三篇
- 保潔突發(fā)事件應(yīng)急預(yù)案
- 膽囊術(shù)后并發(fā)癥護理
- 醫(yī)療廢物暫存間消毒制度
- 2023-2024學(xué)年人教版高中信息技術(shù)必修二第二章第二節(jié)《 信息系統(tǒng)的開發(fā)過程》教案
- 2024六年級英語上冊 Module 9 Unit 1 Do you want to visit the UN building教案 外研版(三起)
- 2024年廣東省高中學(xué)業(yè)水平合格性考試語文試卷真題(含答案解析)
- 混凝土股東合同范本
- 人教版九年級英語知識點復(fù)習(xí)課件全冊
- 2024年7月國家開放大學(xué)??啤掇k公室管理》期末紙質(zhì)考試試題及答案
- 2024年自然資源部直屬企事業(yè)單位公開招聘考試筆試(高頻重點提升專題訓(xùn)練)共500題附帶答案詳解
- 五金材料采購?fù)稑?biāo)方案(技術(shù)方案)
評論
0/150
提交評論