【文章內(nèi)容簡介】 科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 6 和最小支持度閾值 .置信度 和支持度大于相應(yīng)閾值的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則 , 反之稱為弱關(guān)聯(lián)規(guī)則 . 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的任務(wù)就是從數(shù)據(jù)庫中發(fā)現(xiàn) 那些 置信度 、支持度大小等于給定值的強(qiáng)壯規(guī)則 . 基于上述概念，我們可以很容易得到一些基本結(jié)論 : (1) K維數(shù)據(jù)項(xiàng)集 XK是頻繁項(xiàng)集的必要條件是它所有 K1維子項(xiàng)集也為頻繁項(xiàng)集， 記為 XK1 (2)如果 K 維數(shù)據(jù)項(xiàng)集 XK的任意一個(gè) K1 維子集 XK1，不是頻繁項(xiàng)集，則 K維數(shù)據(jù)項(xiàng)集 XK本身也不是最大數(shù)據(jù)項(xiàng)集。 (3) XK是 K 維頻繁項(xiàng)集，如果所有 K1維 頻繁項(xiàng)集集合 XK1中包含 XK 的 K1維子項(xiàng)集的個(gè)數(shù)小于 K，則 XK不可能是 K維最大頻繁數(shù)據(jù)項(xiàng)集。 證明 : 很明顯，數(shù)據(jù)項(xiàng)集 XK1:的 K1 維子項(xiàng)集的個(gè)數(shù)為 K1。如果高頻繁數(shù)據(jù)項(xiàng)集XK1，中包含 XK的 k，則存在 XK的 K1 維子項(xiàng)集不是頻繁數(shù)據(jù)項(xiàng)集，由結(jié)論 (2)知 K 維數(shù)據(jù)項(xiàng)集本身也不是高頻繁數(shù)據(jù)項(xiàng)集 。 關(guān)聯(lián)規(guī)則挖掘舉例 一個(gè)超級(jí)市場的銷售系統(tǒng)記錄了顧客購物的情況。表 31中記錄了 5 個(gè)顧客的購物單。 表 31 記錄號(hào) 所購物品清單 1 啤酒、尿布，嬰兒爽身粉，面包，雨傘 2 尿布，嬰兒爽身粉 3 啤酒、尿布，牛奶 4 尿布，啤酒，洗衣粉 5 啤酒，牛奶，可樂飲料 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 7 超市經(jīng)理想知道商品之間的關(guān)聯(lián)，要求列出那些同時(shí)購買的、且支持度≥40% （即在 5 行中至少出現(xiàn)兩次）的商品名稱。 KDD 系統(tǒng)通過特定算法（例如著名的 Apriori(驗(yàn)證 )算法及或改進(jìn)算法）多次掃描數(shù)據(jù)庫，依次得出如表 2 和表 3。其中支持度 2/5 的項(xiàng) ,如單項(xiàng)的 {面包 }， {雨傘 }和 雙項(xiàng)中的 {尿布，牛奶 }等等已經(jīng)略去，三項(xiàng)統(tǒng)計(jì)為空，其中只有 {啤酒，尿布 ,牛奶 }出現(xiàn)了一次 (表 31中 3 號(hào)記錄 )，支持度小于 40%,略去。 單項(xiàng)統(tǒng)計(jì) 支持度 {啤酒 } 4/5 {尿布 } 4/5 {嬰兒爽身粉 } 2/5 {牛奶 } 2/5 表 32 表 33 從單項(xiàng)統(tǒng)計(jì)中看出 80%的顧客買了啤酒、 80%的顧客買了尿布。從雙項(xiàng)統(tǒng)計(jì)中看出， 60%的顧客同時(shí)買了啤酒和尿布， 40%的顧客買了啤酒和牛奶， 40%的顧客買了尿布和爽身粉。還可觀察到買了啤酒顧客中又買了尿布的占 {啤酒，尿布 }/{啤酒 }=75% (稱為置信度 )。于是可得出下列六條規(guī)則 ,其中： s為支持度， c 為置信度。 R1：啤酒→尿布 ,S=60%， C=R2：尿布→啤酒 ,S=60%， C=R3：牛奶→啤酒 , S=40%， C=R4：啤酒→牛奶 , S=40%， C=R5：尿布→爽身粉。 S=40%， C=R6：嬰兒爽身粉→尿布。 S=40%， C=雙項(xiàng)統(tǒng)計(jì) 支持度 {啤酒，尿布 } 3/5 {啤酒，牛奶 } 2/5 {尿布，嬰兒爽身粉 } 2/5 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 8 KDD 規(guī)則反映了物品之間的表面聯(lián)系，不一定是現(xiàn)實(shí)世界的因果關(guān)系。規(guī)則是死的，人是活的，運(yùn)用之妙成乎于人。例如， R6“嬰兒爽身粉→尿布”有很高的置信度，是合理可理解的， R3有很高的置信度將提示進(jìn)一 步的調(diào)查分析，本例中是因?yàn)橛?xùn)練資料太少引起的失真。 關(guān)聯(lián)規(guī)則問題的分解 關(guān)聯(lián)規(guī)則挖掘問題可分解為以下兩個(gè)子問題 : 1. 找出事務(wù)數(shù)據(jù)庫 D 中所有大于等于用戶指定最小支持度的項(xiàng)目集 (itemset). 具有最小支持度的項(xiàng)目集稱為最大項(xiàng)目集 .項(xiàng)目集的支持度指包含該項(xiàng)目集的數(shù)目 . 2. 利用最大項(xiàng)目集生成所需要的關(guān)聯(lián)規(guī)則 對 每 一 最 大 項(xiàng) 目 集 A, 找到 A 的 所 有 非 空 子 集 a, 如 果 比 率support(A)/support(a)=minconfidence,就生 成關(guān)聯(lián)規(guī)則 a=(Aa).support(A)/support(a) 即規(guī)則 a=(Aa)的 置信度 . 事實(shí)上 ,挖掘關(guān)聯(lián)規(guī)則的整個(gè)執(zhí)行過程中第一個(gè)子問題是核心問題 .當(dāng)找到所有的最大項(xiàng)目集后 ,相應(yīng)的關(guān)聯(lián)規(guī)則將很容易生成 .在本文中將對關(guān)聯(lián)規(guī)則的第一個(gè)問題進(jìn)行探討、研究 。 4 Apriori 算法的描述 Apriori 算法的說明 在 Apriori 算法中 ,尋找最大項(xiàng)目集的基本思想是 : 算法需要對數(shù)據(jù)集進(jìn)行多步處理 .第一步 ,簡單統(tǒng)計(jì)所有含一個(gè)元素項(xiàng)目集出現(xiàn)的頻率 ,并找出那些不小于最小支持度的項(xiàng)目集 , 即一維最大項(xiàng)目集 . 從第二步開始循環(huán)處理直到再?zèng)]陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 9 有最大項(xiàng)目集生成 . 循 環(huán)過程是 : 第 k 步中 , 根據(jù)第 k1 步生成的 (k1)維最大項(xiàng)目集產(chǎn)生 k 維侯選項(xiàng)目集 , 然后對數(shù)據(jù)庫進(jìn)行搜索 , 得到侯選項(xiàng)目集的項(xiàng)集支持度 , 與最小支持度比較 , 從而找到 k維最大項(xiàng)目集 . 為方便后文敘述，現(xiàn)約定如下 : ,每個(gè)項(xiàng)目用 TID,item來標(biāo)識(shí) , 這里 TID 表示相應(yīng)事務(wù)的標(biāo)識(shí)符 , item 則表示項(xiàng)目名稱 . size. 當(dāng)項(xiàng)目集的 size=k時(shí) , 稱該項(xiàng)目集為 kitemset(k 維項(xiàng)目集 ). 下文中遇到的以下符號(hào) ,分別代表相應(yīng)的內(nèi)容 kitemset k 維項(xiàng)目集 Lk 具有最小支持度的最大 kitemset Ck 侯選的 kitemsets(潛在的最大項(xiàng)目集 ) Apriori 算法的描述 Apriori 算法的第一步是簡單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)集出現(xiàn)的頻率 ,來決定最大的一維項(xiàng)目集 .在第 k步 ,分兩個(gè)階段 ,首先用一函數(shù) sc_candidate(候選 ),通過第 (k1)步中生成的最大項(xiàng)目集 Lk1來生成侯選項(xiàng)目集 Ck. 然后搜索數(shù)據(jù)庫計(jì)算侯選項(xiàng)目集 Ck的支持度 . 為了更快速地計(jì)算 Ck中項(xiàng)目的支持度 , 文 中使用函數(shù) count_support 計(jì)算支持度 . Apriori 算法描述如下 (1) C1={candidate1itemsets}。 (2) L1={c∈ C1|≥ minsupport}。 (3) For(k=2,Lk1≠Φ ,k++) //直到不能再生成最大項(xiàng)目集為止 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 10 (4) Ck=sc_candidate(Lk1)。 //生成含 k個(gè)元素的侯選項(xiàng)目集 (5) for all transactions t∈ D //辦理處理 (6) Ct=count_support(Ck,t)。 //包含在事務(wù) t中的侯選項(xiàng)目集 (7) for all candidates c∈ Ct (8) =+1。 (9) next (10) Lk={c∈ Ck|≥ minsupport}。 (11) next (12) resultset=resultset∪ Lk 其中 , D 表示數(shù)據(jù)庫 。 minsupport 表示給定的最小支持度 。 resultset 表示所有最大項(xiàng)目集 . Sc_candidate 函數(shù) 該函數(shù)的參數(shù)為 Lk1,即 : 所有最大 k1 維項(xiàng)目集 ,結(jié)果返回含有 k 個(gè)項(xiàng)目的侯選項(xiàng)目集 ,Ck是 k維最大項(xiàng)目集的超集 ,通過函數(shù) count_support計(jì)算項(xiàng)目的支持度 ,然后生成 Lk. 該函數(shù)是如何完成這些功能的 , 詳細(xì)說明如下 : 首先 , 通過對 Lk1 自連接操作生成 Ck39。,稱 join(連接 )步 , 該步可表述為 : insert into Ck ,......, from Lk1P,Lk1Q =,......=, 若用集合表示 :Ck39。={X∪ X39。|X,X39。∈ Lk1,|X∩ X39。|=k2} 陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系開放性實(shí)驗(yàn)結(jié)題報(bào)告 11 然后 ,是 prune(修剪 )步 ,即對任意的 c,c∈ Ck, 刪除 Ck 中所有那些 (k1)維子集不在 Lk1 中的項(xiàng)目集 ,得到侯選項(xiàng)目集 : for all itemset c∈ Ck for all (k1)維子集 s of c if (s 不屬于 Lk1) then delete c from Ck。 用集合表 示 :Ck=={X∈ Ck39。|X 的所有 k1 維子集在 Lk1中 } 在此函數(shù)中需要說明以下幾點(diǎn) : (1) 最大項(xiàng)目集的子集必為最大項(xiàng)目集 . 這是該算法中隱含的最基本的一條性質(zhì) . 因?yàn)樽畲箜?xiàng)目集定義為不小于最小支持度 (minsupport)的項(xiàng)目集 . 若