大數(shù)據(jù)挖掘?qū)д撆c案例課件-第6章 關(guān)聯(lián)分析概念與方法

第1章緒論第2章數(shù)據(jù)分析與可視化技術(shù)第3章認(rèn)識(shí)數(shù)據(jù)第4章數(shù)據(jù)預(yù)處理第5章分類概念與方法第6章關(guān)聯(lián)分析概念與方法第7章聚類分析概念與方法第8章大數(shù)據(jù)挖掘關(guān)鍵技術(shù)第9章案例分析第6章關(guān)聯(lián)分析概念與方法大數(shù)據(jù)挖掘?qū)д撆c案例學(xué)習(xí)目標(biāo)/Target掌握Apriori算法挖掘關(guān)聯(lián)規(guī)則的基本步驟,，了解Apriori算法的優(yōu)缺點(diǎn)，了解提升算法效率的方法。理解FP樹(shù)挖掘頻繁項(xiàng)集的原理,

熟悉挖掘頻繁項(xiàng)集的其他方法。了解關(guān)聯(lián)模式評(píng)估的指標(biāo),

熟悉各指標(biāo)的應(yīng)用場(chǎng)景。掌握關(guān)聯(lián)分析的基本概念，理解頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的內(nèi)容，掌握先驗(yàn)原理。引言/Introduction關(guān)聯(lián)分析（associationanalysis）從大量數(shù)據(jù)中發(fā)現(xiàn)項(xiàng)集之間有趣的聯(lián)系，被用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)集中的有意義的關(guān)聯(lián)。通常將所發(fā)現(xiàn)的聯(lián)系表示為關(guān)聯(lián)規(guī)則（associationrule）或頻繁項(xiàng)集（frequentitemset）。目錄/Contents01基本概念02關(guān)聯(lián)分析的方法03關(guān)聯(lián)模式評(píng)估基本概念6.16.1.1購(gòu)物籃分析關(guān)聯(lián)分析的目的是發(fā)現(xiàn)被顧客放入購(gòu)物籃中的不同商品之間的聯(lián)系，從而分析顧客的購(gòu)買(mǎi)習(xí)慣，了解哪些商品經(jīng)常被顧客連帶購(gòu)買(mǎi)，為制定方便顧客選取的貨架擺放方案和合理的營(yíng)銷(xiāo)策略提供依據(jù)，也被稱為購(gòu)物籃分析。完整的購(gòu)物籃數(shù)據(jù)至少包含兩方面的信息：一方面是顧客的購(gòu)買(mǎi)行為序號(hào)，一個(gè)顧客可能會(huì)發(fā)生多次購(gòu)買(mǎi)行為，每次購(gòu)買(mǎi)行為均被記錄下來(lái)，這個(gè)序號(hào)也就是超市或者商店的交易流水號(hào)；另一方面是顧客在每次購(gòu)物過(guò)程中交易的商品列表，此處商品列表只涉及顧客購(gòu)買(mǎi)的不同商品的名稱。6.1.1購(gòu)物籃分析購(gòu)物籃數(shù)據(jù)涉及關(guān)聯(lián)分析的兩個(gè)基本術(shù)語(yǔ)：事務(wù)（transaction）和項(xiàng)集（itemset）。事務(wù)是關(guān)聯(lián)分析的研究對(duì)象，一個(gè)事務(wù)包含一個(gè)唯一標(biāo)識(shí)TID和對(duì)應(yīng)顧客購(gòu)買(mǎi)的商品的集合。項(xiàng)目（item）是事務(wù)中的單個(gè)對(duì)象。一次交易中的商品通常是若干個(gè)項(xiàng)目的集合，叫作項(xiàng)集。購(gòu)物籃分析的目的是找到所有購(gòu)物籃中不同商品之間的關(guān)聯(lián)關(guān)系，從而了解哪些商品頻繁地被顧客同時(shí)購(gòu)買(mǎi)，幫助零售商制定合理的營(yíng)銷(xiāo)策略。6.1.1購(gòu)物籃分析在對(duì)購(gòu)物籃數(shù)據(jù)進(jìn)行關(guān)聯(lián)分析時(shí)，需要處理兩個(gè)關(guān)鍵問(wèn)題：第一，計(jì)算復(fù)雜度問(wèn)題。從大型事務(wù)數(shù)據(jù)集中發(fā)現(xiàn)有意義的規(guī)則在計(jì)算上要付出很高的代價(jià)；第二，規(guī)則的篩選問(wèn)題。所發(fā)現(xiàn)的某些規(guī)則可能是虛假的或不令人感興趣的，因?yàn)樗鼈兛赡苁桥既话l(fā)生的或者是已經(jīng)被研究者所熟知的。除了購(gòu)物籃分析外，關(guān)聯(lián)分析也被應(yīng)用于公共管理、生物信息學(xué)、醫(yī)療診斷、網(wǎng)頁(yè)挖掘和推薦系統(tǒng)等領(lǐng)域。例如，關(guān)聯(lián)分析可以幫助公安機(jī)關(guān)從已有的案件中找到各屬性之間的隱含關(guān)系，發(fā)現(xiàn)其中的犯罪行為規(guī)律，為新案件的偵破提供線索；在移動(dòng)通信行業(yè)，關(guān)聯(lián)分析可以幫助運(yùn)營(yíng)商發(fā)現(xiàn)不同業(yè)務(wù)之間的關(guān)聯(lián)關(guān)系，從而推進(jìn)新業(yè)務(wù)的發(fā)展；關(guān)聯(lián)分析也可以用來(lái)分析保險(xiǎn)行業(yè)的客戶數(shù)據(jù)，找到各險(xiǎn)種可能被購(gòu)買(mǎi)的人群特征，進(jìn)而進(jìn)行精準(zhǔn)營(yíng)銷(xiāo)。6.1.2頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則

6.1.2頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則

6.1.2頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則

6.1.2頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則實(shí)際應(yīng)用中的關(guān)聯(lián)規(guī)則有許多類型，可以根據(jù)不同的標(biāo)準(zhǔn)對(duì)關(guān)聯(lián)規(guī)則進(jìn)行分類。根據(jù)處理的數(shù)據(jù)類型，關(guān)聯(lián)規(guī)則可以分為布爾關(guān)聯(lián)規(guī)則和量化關(guān)聯(lián)規(guī)則。布爾型關(guān)聯(lián)規(guī)則是指處理的數(shù)據(jù)類型都是離散屬性或分類屬性，量化關(guān)聯(lián)規(guī)則則是指處理的數(shù)據(jù)類型包含連續(xù)屬性。根據(jù)處理的數(shù)據(jù)維度，關(guān)聯(lián)規(guī)則可以分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則。單維關(guān)聯(lián)規(guī)則通常從事務(wù)數(shù)據(jù)中挖掘，涉及到數(shù)據(jù)的只有一個(gè)維度，處理的是單個(gè)維內(nèi)的關(guān)系。根據(jù)數(shù)據(jù)的抽象層次，關(guān)聯(lián)規(guī)則可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。在單層關(guān)聯(lián)規(guī)則中，沒(méi)有考慮現(xiàn)實(shí)數(shù)據(jù)的多層次性。多層關(guān)聯(lián)規(guī)則是指在規(guī)則挖掘中，對(duì)數(shù)據(jù)的多層性進(jìn)行了充分考慮。關(guān)聯(lián)分析的方法6.2

6.2關(guān)聯(lián)分析的方法6.2.1先驗(yàn)原理

6.2.1先驗(yàn)原理即，一旦發(fā)現(xiàn)一個(gè)非頻繁項(xiàng)集，那么包含該項(xiàng)集的所有超集都可以被剪枝，這樣的方法被稱為基于支持度的剪枝（support-basedpruning）?；谥С侄鹊募糁σ蕾囉谥С侄榷攘康男再|(zhì)，即一個(gè)項(xiàng)集的支持度決不會(huì)超過(guò)它的子集的支持度，這個(gè)性質(zhì)也被稱為支持度度量的反單調(diào)性（anti-monotone）。任何具有反單調(diào)性的度量都能夠直接結(jié)合到挖掘算法中，對(duì)候選項(xiàng)集的指數(shù)搜索空間有效地進(jìn)行剪枝，以降低生成頻繁項(xiàng)集的計(jì)算代價(jià)。6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集Apriori算法是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，它開(kāi)創(chuàng)性地使用了基于支持度的剪枝技術(shù)來(lái)控制候選項(xiàng)集的指數(shù)增長(zhǎng)。此處以下表所示的事務(wù)數(shù)據(jù)集為例，展示Apriori算法挖掘頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則的基本過(guò)程。TID商品集合1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3雞蛋，面包，薯片4牛奶，雞蛋，面包，爆米花，薯片，啤酒5牛奶，面包，啤酒6雞蛋，面包，啤酒7牛奶，面包，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){爆米花}2{黃油}2{雞蛋}7{面包}7{牛奶}6{薯片}7{啤酒}46.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){雞蛋}7{面包}7{牛奶}6{薯片}7{啤酒}46.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){雞蛋，面包}5{雞蛋，薯片}6{雞蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，雞蛋}4{牛奶，面包}5{牛奶，薯片}5{牛奶，啤酒}2{薯片，啤酒}26.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){雞蛋，面包}5{雞蛋，薯片}6{雞蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，雞蛋}4{牛奶，面包}5{牛奶，薯片}56.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){雞蛋，面包，薯片}4{雞蛋，面包，啤酒}2{牛奶，雞蛋，面包}3{牛奶，雞蛋，薯片}4{牛奶，面包，薯片}46.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){雞蛋，面包，薯片}4{牛奶，雞蛋，面包}3{牛奶，雞蛋，薯片}4{牛奶，面包，薯片}46.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù){牛奶，雞蛋，面包，薯片}36.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

項(xiàng)集支持度計(jì)數(shù)6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

產(chǎn)生候選項(xiàng)集6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

產(chǎn)生候選項(xiàng)集6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集候選項(xiàng)集剪枝

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)

6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)首先進(jìn)行第一層散列，首項(xiàng)為1的項(xiàng)集，應(yīng)該散列在左邊，而首項(xiàng)為2的散列在中間，首項(xiàng)為3的散列在右邊，如下圖所示：6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)按同樣方式進(jìn)行第二層散列，第1項(xiàng)為1的3-項(xiàng)集中第2項(xiàng)為2、3和5，其中第2項(xiàng)為2和5的3-項(xiàng)集被散列到第二層的中間結(jié)點(diǎn)，其第2項(xiàng)為3的3-項(xiàng)集被散列到第二層的右結(jié)點(diǎn)，結(jié)果如下圖。6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)同理進(jìn)行第三層散列，結(jié)果如右。圖中灰色葉子結(jié)點(diǎn)表示候選Hash樹(shù)上事務(wù)3-項(xiàng)集被散列的桶。6.2.2Apriori算法產(chǎn)生頻繁項(xiàng)集計(jì)算支持度計(jì)數(shù)

6.2.3Apriori算法生成關(guān)聯(lián)規(guī)則

6.2.3Apriori算法生成關(guān)聯(lián)規(guī)則

6.2.3Apriori算法生成關(guān)聯(lián)規(guī)則6.2.3Apriori算法生成關(guān)聯(lián)規(guī)則

基于置信度的剪枝6.2.3Apriori算法生成關(guān)聯(lián)規(guī)則基于置信度的剪枝6.2.4Apriori算法效率提升

事務(wù)壓縮技術(shù)

6.2.4Apriori算法效率提升

劃分技術(shù)6.2.4Apriori算法效率提升劃分技術(shù)6.2.4Apriori算法效率提升

選樣技術(shù)6.2.5模式增長(zhǎng)算法頻繁項(xiàng)集的挖掘是關(guān)聯(lián)分析的關(guān)鍵步驟，Apriori算法通過(guò)多次掃描事務(wù)數(shù)據(jù)庫(kù)產(chǎn)生候選項(xiàng)集，再由候選項(xiàng)集得到頻繁項(xiàng)集。JiaweiHan等人在2000年提出了一種關(guān)聯(lián)分析方法——頻繁模式增長(zhǎng)算法（FP-growthalgorithm），這是一種不通過(guò)產(chǎn)生候選項(xiàng)集來(lái)挖掘全部頻繁項(xiàng)集的方法。FP-growth算法采取分治的策略，首先將頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮為一棵頻繁模式樹(shù)（frequentpatterntree），簡(jiǎn)稱FP樹(shù)，該樹(shù)仍保留項(xiàng)集的關(guān)聯(lián)信息。然后在FP樹(shù)中通過(guò)遞歸直接挖掘頻繁項(xiàng)集。即算法分為兩個(gè)步驟：第一步構(gòu)建FP樹(shù)，第二步從FP樹(shù)中挖掘頻繁模式。6.2.5模式增長(zhǎng)算法FP樹(shù)是輸入數(shù)據(jù)集的一種壓縮表示，它通過(guò)逐一讀取事務(wù)數(shù)據(jù)，并把每個(gè)事務(wù)映射到FP樹(shù)的一條路徑來(lái)構(gòu)造。由于不同的事務(wù)中可能會(huì)存在部分相同的項(xiàng)目，因此FP樹(shù)的路徑會(huì)有部分重疊，重疊的部分越多，說(shuō)明使用FP樹(shù)壓縮的效果越好。如果FP樹(shù)足夠小，可以把FP樹(shù)存放在內(nèi)存中，從中直接提取頻繁項(xiàng)集，而不需要一遍遍地掃描事務(wù)數(shù)據(jù)庫(kù)，從而提高計(jì)算的效率。創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法創(chuàng)建FP樹(shù)TIDItems12345678910

6.2.5模式增長(zhǎng)算法

創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法

創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法重復(fù)該過(guò)程，直到將所有的事務(wù)讀入完畢，每個(gè)事務(wù)都映射到了FP樹(shù)上的一條路徑中，如右圖（d）所示。創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法通過(guò)以上方法構(gòu)造的FP樹(shù)具有以下幾個(gè)特點(diǎn)。（1）在FP樹(shù)中，事務(wù)通過(guò)共享前綴項(xiàng)得到了壓縮。如果數(shù)據(jù)集中所有事務(wù)的項(xiàng)目都相同，那么FP樹(shù)只包含一條結(jié)點(diǎn)路徑；如果數(shù)據(jù)集中每個(gè)事務(wù)中均不存在相同的項(xiàng)目，那么構(gòu)造的FP樹(shù)的大小和原數(shù)據(jù)集的大小一樣。（2）FP樹(shù)的大小與項(xiàng)目按支持度計(jì)數(shù)的排序方式有關(guān)。當(dāng)?shù)谝徊绞聞?wù)中的項(xiàng)目按支持度的增序排列時(shí)，則根結(jié)點(diǎn)上的分支數(shù)目由2個(gè)增加到了5個(gè)，并且包含高支持度項(xiàng)目a和b的結(jié)點(diǎn)數(shù)目由3個(gè)增加到了12個(gè)，也就是說(shuō)構(gòu)造的FP樹(shù)顯得更加茂盛，如下圖所示。需要注意的是，按支持度計(jì)數(shù)降序排列并非總是能夠得到最小的樹(shù)。（3）FP樹(shù)中還包含了連接相同項(xiàng)目結(jié)點(diǎn)的指針列表。這些指針在圖中用虛線表示，有助于方便快速地訪問(wèn)樹(shù)中的項(xiàng)目。創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法創(chuàng)建FP樹(shù)6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法從FP樹(shù)中挖掘頻繁模式6.2.5模式增長(zhǎng)算法

從FP樹(shù)中挖掘頻繁模式后綴頻繁項(xiàng)集edcba6.2.5模式增長(zhǎng)算法FP-growth算法使用了事務(wù)數(shù)據(jù)集的壓縮表示有效地生成頻繁項(xiàng)集。需要注意的是，F(xiàn)P-growth算法只能用來(lái)發(fā)現(xiàn)頻繁項(xiàng)集，不能用來(lái)尋找關(guān)聯(lián)規(guī)則。與Apriori算法相比，F(xiàn)P-growth算法發(fā)現(xiàn)頻繁項(xiàng)集的效率較高，只需要對(duì)事務(wù)數(shù)據(jù)集進(jìn)行兩次掃描，執(zhí)行速度快于Apriori算法。6.2.6使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集事務(wù)數(shù)據(jù)集的表示方法有很多，最常見(jiàn)的是列表表示方法，在實(shí)際運(yùn)用中還會(huì)用到二元表格形式的矩陣表示方法，還有將數(shù)據(jù)庫(kù)壓縮為樹(shù)狀結(jié)構(gòu)的表示方法等，與列表表示方法相對(duì)應(yīng)的垂直數(shù)據(jù)結(jié)構(gòu)表示方法也可用于表示事務(wù)數(shù)據(jù)集。列表表示法將一個(gè)事務(wù)數(shù)據(jù)集用兩列來(lái)表示，第一列是交易流水號(hào)，用來(lái)標(biāo)識(shí)每一個(gè)事務(wù)，記為事務(wù)標(biāo)識(shí)符TID；第二列是每個(gè)事務(wù)中交易的商品集合，記為T(mén)ID中的項(xiàng)集，如下表1所示，也把這樣的表示方法稱為水平數(shù)據(jù)布局。將一個(gè)水平數(shù)據(jù)布局的事務(wù)數(shù)據(jù)集轉(zhuǎn)換為垂直數(shù)據(jù)布局，可以看作是將水平數(shù)據(jù)布局的數(shù)據(jù)集進(jìn)行了一次轉(zhuǎn)置，記錄的是每個(gè)項(xiàng)目出現(xiàn)的事務(wù)集合，如下表2所示。6.2.6使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集ItemsTID集合a{1,4,5,6,7,8,9}b{1,2,5,7,8,10}c{2,3,4,5,8,9}d{2,4,5,9}e{3,9}TIDItems12345678910表1表26.2.6使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集下面使用垂直數(shù)據(jù)格式有效地挖掘頻繁項(xiàng)集。（1）掃描一次事務(wù)數(shù)據(jù)集，將水平數(shù)據(jù)格式的數(shù)據(jù)集轉(zhuǎn)換成垂直數(shù)據(jù)格式。（2）計(jì)算每個(gè)項(xiàng)目的TID集合的長(zhǎng)度，即為該項(xiàng)目的支持度計(jì)數(shù)。設(shè)定支持度計(jì)數(shù)的閾值為3，將每個(gè)項(xiàng)目的支持度計(jì)數(shù)和支持度閾值進(jìn)行對(duì)比，得到頻繁1-項(xiàng)集，如下表所示。ItemTID集合支持度計(jì)數(shù)是否頻繁1-項(xiàng)集a{1,4,5,6,7,8,9}7是b{1,2,5,7,8,10}6是c{2,3,4,5,8,9}6是d{2,4,5,9}4是e{3,9}2否6.2.6使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集（3）使用頻繁1-項(xiàng)集構(gòu)造候選2-項(xiàng)集，通過(guò)項(xiàng)目TID集合的交集運(yùn)算得到每個(gè)候選2-項(xiàng)集的TID集合，進(jìn)而得到頻繁2-項(xiàng)集，如下表所示。ItemTID集合支持度計(jì)數(shù)是否頻繁2-項(xiàng)集{1,5,7,8}4是{4,5,8,9}4是{4,5,9}3是{2,5,8}3是{2,5}2否{2,4,5,9}4是6.2.6使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集

ItemTID集合支持度計(jì)數(shù)是否頻繁3-項(xiàng)集{5,8}2否{4,5,9}3是（5）由于（4）中只產(chǎn)生了一個(gè)頻繁3-項(xiàng)集，無(wú)法構(gòu)造候選4-項(xiàng)集，算法結(jié)束。采用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集，算法在執(zhí)行整個(gè)過(guò)程中只掃描了一次事務(wù)數(shù)據(jù)庫(kù)，比水平數(shù)據(jù)格式在時(shí)間效率上有一定的優(yōu)越性，節(jié)省了多次掃描數(shù)據(jù)庫(kù)的時(shí)間開(kāi)銷(xiāo)。但是實(shí)際工作中TID集合可能很長(zhǎng)，此時(shí)不僅需要大量存儲(chǔ)空間而且交集運(yùn)算也需要大量的計(jì)算資源。因此使用垂直數(shù)據(jù)格式挖掘頻繁項(xiàng)集的方法仍然具有很大的改進(jìn)空間。6.2.7頻繁項(xiàng)集的緊湊表示

6.2.7頻繁項(xiàng)集的緊湊表示如果某個(gè)項(xiàng)集的直接超集都不是頻繁項(xiàng)集，則稱該項(xiàng)集為極大頻繁項(xiàng)集（maximalfrequentitemset）。極大頻繁項(xiàng)集是一種十分有效的頻繁項(xiàng)集的緊湊表示。極大頻繁項(xiàng)集的任意一個(gè)子集都是頻繁的，即從一個(gè)極大頻繁項(xiàng)集中可以導(dǎo)出所有的頻繁項(xiàng)集，又由于極大頻繁項(xiàng)集的超集都不是頻繁的，所以極大頻繁項(xiàng)集是能完成這一任務(wù)的最小的項(xiàng)集。盡管極大頻繁項(xiàng)集能夠?qū)С鏊械念l繁項(xiàng)集，但是它無(wú)法提供其子集的支持度信息，這就需要再掃描一遍數(shù)據(jù)集來(lái)確定這些子集的支持度計(jì)數(shù)，此時(shí)能提供保持支持度信息的頻繁項(xiàng)集的最小表示是有用的。極大頻繁項(xiàng)集6.2.7頻繁項(xiàng)集的緊湊表示閉頻繁項(xiàng)集（closedfrequentitemset）提供了頻繁項(xiàng)集的一種最小表示，該表示不會(huì)丟失支持度信息。如果一個(gè)項(xiàng)集的直接超集的支持度計(jì)數(shù)都不等于該項(xiàng)集本身的支持度計(jì)數(shù)，則稱該項(xiàng)集為閉項(xiàng)集（closeditemset）。也就是說(shuō)，如果一個(gè)項(xiàng)集不是閉的，那么至少存在一個(gè)它的直接超集，該超集的支持度計(jì)數(shù)和它本身的支持度計(jì)數(shù)相等。如果一個(gè)項(xiàng)集是閉項(xiàng)集，同時(shí)其支持度滿足支持度閾值，則稱該項(xiàng)集為閉頻繁項(xiàng)集。閉頻繁項(xiàng)集6.2.7頻繁項(xiàng)集的緊湊表示

閉頻繁項(xiàng)集6.2.7頻繁項(xiàng)集的緊湊表示閉頻繁項(xiàng)集使用極大頻繁項(xiàng)集和閉頻繁項(xiàng)集進(jìn)行頻繁項(xiàng)集的緊湊表示可以減少頻繁項(xiàng)集中的冗余，降低算法計(jì)算的復(fù)雜度。需要注意的是，要使用極大頻繁項(xiàng)集和閉頻繁項(xiàng)集的緊湊表示，前提是能夠有效地從事務(wù)數(shù)據(jù)集中快速識(shí)別極大頻繁項(xiàng)集和閉頻繁項(xiàng)集。關(guān)聯(lián)模式評(píng)估6.36.3.1模式興趣度度量在商業(yè)數(shù)據(jù)集中挖掘關(guān)聯(lián)規(guī)則時(shí)，盡管有支持度閾值和置信度閾值的限制，但仍然會(huì)挖掘出大量的關(guān)聯(lián)規(guī)則，其中有很大一部分是商業(yè)決策者們不感興趣的，因?yàn)檫@些規(guī)則沒(méi)有實(shí)際的應(yīng)用價(jià)值。因此，需要建立一組能被廣泛接受的評(píng)估關(guān)聯(lián)模式質(zhì)量的標(biāo)準(zhǔn)來(lái)對(duì)關(guān)聯(lián)規(guī)則進(jìn)行評(píng)價(jià)和篩選。目前認(rèn)可度較高的關(guān)聯(lián)模式評(píng)估標(biāo)準(zhǔn)有以下兩種。第一種是通過(guò)統(tǒng)計(jì)論據(jù)建立的，被稱為客觀興趣度度量（objectiveinterestingnessmeasure）?？陀^興趣度度量是從數(shù)據(jù)中推導(dǎo)統(tǒng)計(jì)量，用統(tǒng)計(jì)量來(lái)判斷關(guān)聯(lián)模式是否有趣。這時(shí)，相互獨(dú)立的模式或者覆蓋少量事務(wù)的模式被認(rèn)為是沒(méi)有意義的，可以排除。支持度和置信度都是客觀興趣度度量。6.3.1模式興趣度度量

6.3.1模式興趣度度量

支持度-置信度框架的局限性

6.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量支持度的缺點(diǎn)：由于支持度閾值是由主觀經(jīng)驗(yàn)人為設(shè)定，如果閾值過(guò)低，會(huì)產(chǎn)生大量的頻繁項(xiàng)集，增加算法的計(jì)算復(fù)雜度；如果閾值過(guò)高，會(huì)導(dǎo)致一些潛在的有意義的規(guī)則被刪除。例如，在商場(chǎng)的購(gòu)物記錄中購(gòu)買(mǎi)奢侈品的人數(shù)是比較少的，那么奢侈品的購(gòu)買(mǎi)模式就有可能因?yàn)檫_(dá)不到支持度閾值而被過(guò)濾掉。置信度的缺點(diǎn)：計(jì)算置信度時(shí)并沒(méi)有考慮規(guī)則前后件的關(guān)系，當(dāng)規(guī)則的前后件是兩個(gè)完全獨(dú)立的事件時(shí)，就有可能生成誤導(dǎo)性的規(guī)則。下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明。支持度-置信度框架的局限性6.3.1模式興趣度度量一個(gè)谷類早餐的零售商對(duì)一所學(xué)校學(xué)生每天早上所從事的活動(dòng)進(jìn)行了一次調(diào)查。該所學(xué)校共有5000名學(xué)生。數(shù)據(jù)表明：60%的學(xué)生（即3000名學(xué)生）打籃球，75%的學(xué)生（即3750名學(xué)生）吃該零售商售賣(mài)的谷類早餐，40%的學(xué)生（即2000名學(xué)生）既打籃球也吃這種谷類早餐。假設(shè)關(guān)聯(lián)規(guī)則挖掘的支持度閾值40%，置信度閾值為60%。得到相依表如下。實(shí)例

吃谷類早餐不吃谷類早餐打籃球200010003000不打籃球175025020003750125050006.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量

支持度-置信度框架的局限性6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

提升度（lift）6.3.1模式興趣度度量

卡方度量（chi-squaremeasures）6.3.1模式興趣度度量卡方度量（chi-squaremeasures）

吃谷類早餐不吃谷類早餐打籃球2000（2250）1000（750）3000不打籃球1750（1500）250（500）20003750125050006.3.1模式興趣度度量

卡方度量（chi-squaremeasures）6.3.1模式興趣度度量

全置信度6.3.1模式興趣度度量

最大置信度

Kulczynski度量6.3.1模式興趣度度量

余弦度量6.3.2關(guān)聯(lián)模式評(píng)估度量比較

6.3.2關(guān)聯(lián)模式評(píng)估度量比較數(shù)據(jù)集提升度全置信度最大置信度Kulc余弦10000100010001000009.2690556.760.910.910.910.9110000100010001001.000.000.910.910.910.91100100010001000008.44670.010.090.090.090.0910001000100010000025.7524740.300.500.500.500.501000100100001000009.188172.830.090.910.500.291000101000001000001.97965.540.010.990.500.106.3.2關(guān)聯(lián)模式評(píng)估度量比較

6.3.2關(guān)聯(lián)模式評(píng)估度量比較

6.3.2關(guān)聯(lián)模式評(píng)估度量比較度量方法定義取值