【文章內(nèi)容簡(jiǎn)介】 (X) ≥minsup then X稱為大項(xiàng)集（ large item set），滿足最小支持度的項(xiàng)集也稱為頻繁項(xiàng)集（ frequent itemset）。2）利用大項(xiàng)集生成關(guān)聯(lián)規(guī)則，對(duì)每一大項(xiàng)集 X，若 Y?X，Y=?，并且 support (Y)/support (X) ≥minconf。45 關(guān)聯(lián)規(guī)則的概念及分類? 為了發(fā)現(xiàn)出有意義的關(guān)聯(lián)規(guī)則，必需給定兩個(gè)閾值，即最小支持度和最小置信度。? 最小支持度是用戶規(guī)定的關(guān)聯(lián)規(guī)則必需滿足的最小支持度，它表示一組物品集在統(tǒng)計(jì)意義上的需滿足的最低程度，即衡量關(guān)聯(lián)規(guī)則在整個(gè)數(shù)據(jù)集中的統(tǒng)計(jì)重要性。? 最小置信度是用戶規(guī)定的關(guān)聯(lián)規(guī)則必需滿足的最小可信度，它反映了關(guān)聯(lián)規(guī)則的最低可靠度，即衡量關(guān)聯(lián)規(guī)則的可信程度。? 關(guān)聯(lián)分析可用于銷售配貨、商品陳列設(shè)計(jì)、產(chǎn)品目錄設(shè)計(jì)、產(chǎn)品定價(jià)和促銷等，也可以使我們從客戶的購(gòu)買模式中推知他們的嗜好。46 關(guān)聯(lián)規(guī)則的概念及分類? 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則通常要經(jīng)過(guò)以下三個(gè)步驟：? 1）連接數(shù)據(jù)，作數(shù)據(jù)準(zhǔn)備；? 2）給定最小支持度和最小可信度，利用數(shù)據(jù)挖掘工具提供的算法發(fā)現(xiàn)關(guān)聯(lián)規(guī)則；? 3）可視化顯示、理解、評(píng)估關(guān)聯(lián)規(guī)則。47 關(guān)聯(lián)規(guī)則的概念及分類? 關(guān)聯(lián)規(guī)則的優(yōu)缺點(diǎn)：? 優(yōu)點(diǎn)：? 它可以產(chǎn)生清晰有用的結(jié)果；? 它支持間接數(shù)據(jù)挖掘；? 可以處理變長(zhǎng)的數(shù)據(jù)；? 它的計(jì)算的消耗量是可以預(yù)見(jiàn)的。? 缺點(diǎn)：? 當(dāng)問(wèn)題變大時(shí)，計(jì)算量增長(zhǎng)得厲害；? 難以決定正確的數(shù)據(jù)；? 容易忽略離群數(shù)據(jù)。48 關(guān)聯(lián)規(guī)則的概念及分類? （ 2）關(guān)聯(lián)規(guī)則的分類表 關(guān)聯(lián)規(guī)則的分類分 類標(biāo) 準(zhǔn) 類 別規(guī)則 中所 處 理的值布 爾 關(guān) 聯(lián)規(guī)則 與量化關(guān) 聯(lián)規(guī)則規(guī)則 中所涉及的數(shù)據(jù) 維單維 關(guān) 聯(lián)規(guī)則 與多 維 關(guān) 聯(lián)規(guī)則規(guī)則 中所涉及的抽象 層單層 關(guān) 聯(lián)規(guī)則 與多 層 關(guān) 聯(lián)規(guī)則規(guī)則 中的 擴(kuò) 充 最大的模式與 頻繁 閉項(xiàng) 集關(guān) 聯(lián) 特性 分 類 分析與相關(guān)分析49 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法? 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法（單維、單層和布爾關(guān)聯(lián)規(guī)則）主要是經(jīng)典頻集方法（基于 Apriori的頻集方法）。（ 1）簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則的核心算法? 是一個(gè)兩階段頻集思想的方法。? 關(guān)聯(lián)規(guī)則算法的設(shè)計(jì)可以分解為兩個(gè)子問(wèn)題：1） 找到所有支持度大于最小支持度的項(xiàng)集，即頻集。 由 k個(gè)數(shù)據(jù)頻集稱為 k項(xiàng)頻集 ，找出所有的頻集由 Apriori算法實(shí)現(xiàn)。Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須也是頻繁的。50 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法2）使用第 1步找到的頻集產(chǎn)生期望的規(guī)則。? 為了生成所有頻集，使用遞推的方法：首先產(chǎn)生頻繁 1項(xiàng)集 L1，然后產(chǎn)生頻繁 2項(xiàng)集 L2，直到有某個(gè) r值使得 Lr為空，這時(shí)算法停止。? 這里在 k次循環(huán)中，過(guò)程先產(chǎn)生候選 k項(xiàng)集的集合 Ck， Ck中的每一個(gè)項(xiàng)集是對(duì)兩個(gè)只有一個(gè)項(xiàng)不同的屬于 Lk1的頻集做一個(gè) (k2)連接來(lái)產(chǎn)生的。 Ck中的項(xiàng)集是用來(lái)產(chǎn)生頻集的候選集，最后的頻集 Lk必須是 Ck的一個(gè)子集。 Ck中的每個(gè)元素須在交易數(shù)據(jù)庫(kù)中進(jìn)行驗(yàn)證來(lái)決定是否加入 Lk ，這里的驗(yàn)證過(guò)程是算法性能的一個(gè)瓶頸。51 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法? Apriori算法的核心思想L1={large 1itemsets}。 //發(fā)現(xiàn) 1項(xiàng)頻集for (k=2。 Lk1 =?。k++) do beginCk=apriorigen (Lk1,minsup)。 //根據(jù) k1項(xiàng)頻集產(chǎn)生新的 k項(xiàng)候選集for all transactions t?D。 //遍歷數(shù)據(jù)庫(kù)確定每個(gè)候選集的支持頻度Ct=subset(Ck,t)。 //事務(wù) t中包含的候選集for all candidates c ?Ct do++。Lk={c?Ck | ≥minsup}Return L= 。//求所有頻繁項(xiàng)集 Lk的和52 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法? apriorigen函數(shù)以 Lk1作為輸入?yún)?shù)，返回所有大 k項(xiàng)集的集合 Lk，具體實(shí)現(xiàn)如下：第一步：聯(lián)合，將兩個(gè)項(xiàng)連接在一起Procedure apriorigen (Lk1,minsup)insert into Ckselect ,…,(k1),(k1)from Lk1p,Lk1qwhere =,…,(k2)=(k2), (k1)(k1)53 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法? 第二步，剪枝（ pruning），如果存在 c的 (k1)子序列不包含于 Lk1中，則刪除所有項(xiàng)集 c ?Ck。For all itemsets c ?Ck dofor all (k1) subsets s of c doif (s? Lk1) thendelete from Ck 54Apriori算法 —— 示例Database TDB1st scanC1 L1L2C2 C22nd scanC3 L33rd scanTid Items10 A, C, D20 B, C, E30 A, B, C, E40 B, EItemset sup{A} 2{B} 3{C} 3{D} 1{E} 3Itemset sup{A} 2{B} 3{C} 3{E} 3Itemset{A, B}{A, C}{A, E}{B, C}{B, E}{C, E}Itemset sup{A, B} 1{A, C} 2{A, E} 1{B, C} 2{B, E} 3{C, E} 2Itemset sup{A, C} 2{B, C} 2{B, E} 3{C, E} 2Itemset{B, C, E}Itemset sup{B, C, E} 255 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法（ 2）頻集算法的幾種優(yōu)化方法? 1）基于劃分的方法? 2）基于 hash的方法? 3）基于采樣的方法? 4）減少交易的個(gè)數(shù)56 簡(jiǎn)單形式的關(guān)聯(lián)規(guī)則算法（ 3）其他的頻集挖掘方法? 基于 Apriori方法的缺陷及解決辦法1）可能產(chǎn)生大量的候選集 ——FPgrowth2）無(wú)法對(duì)稀有信息進(jìn)行分析 —— 挖掘高可信度的規(guī)則：計(jì)算特征、生成候選集、過(guò)濾候選集57 多層和多維關(guān)聯(lián)規(guī)則的挖掘（ 1）多層關(guān)聯(lián)規(guī)則? 多層關(guān)聯(lián)規(guī)則的分類：根據(jù)規(guī)則中涉及的層次，多層關(guān)聯(lián)規(guī)則可以分為 同層關(guān)聯(lián)規(guī)則 和 層間關(guān)聯(lián)規(guī)則 。? 多層關(guān)聯(lián)規(guī)則的挖掘基本上可以沿用 “支持度 可信度 ”的框架。不過(guò)在支持度設(shè)置的問(wèn)題上有一些要考慮的問(wèn)題。? 同層關(guān)聯(lián)規(guī)則可以采用兩種支持度策略：1）統(tǒng)一的最小支持度。對(duì)于不同的層次，都使用同一個(gè)最小支持度。2）遞減的最小支持度。每個(gè)層次都有不同的最小支持度，較低層次的最小支持度相對(duì)較小。同時(shí)還可以用上層挖掘得到的信息進(jìn)行一些過(guò)濾工作。? 層間關(guān)聯(lián)規(guī)則考慮最小支持度的時(shí)候，應(yīng)根據(jù)較低層次的最小支持度來(lái)定。58 多層和多維關(guān)聯(lián)規(guī)則的挖掘（ 2）多維關(guān)聯(lián)規(guī)則? 根據(jù)是否允許同一個(gè)維重復(fù)出現(xiàn)，可以細(xì)分為 維間的關(guān)聯(lián)規(guī)則 （不允許維重復(fù)出現(xiàn)）和 混合維關(guān)聯(lián)規(guī)則 （允許維在規(guī)則的左右同時(shí)出現(xiàn)）。? 例：年齡 (X,”20…30”) ∪ 購(gòu)買 (X,”筆記本電腦 ”)==購(gòu)買