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