第六章關聯(lián)分析

基本概念與算法關聯(lián)分析的基本概念Apriori算法FP增長算法關聯(lián)模式的評估目錄關聯(lián)分析的基本概念ItemsetAcollectionofoneormoreitemsExample:{Milk,Bread,Diaper}k-itemsetAnitemsetthatcontainskitemsSupportcount()FrequencyofoccurrenceofanitemsetE.g.({Milk,Bread,Diaper})=2SupportFractionoftransactionsthatcontainanitemsetE.g.s({Milk,Bread,Diaper})=2/5FrequentItemsetAnitemsetwhosesupportisgreaterthanorequaltoaminsupthreshold項集：包含0個或多個項的集合。支持度計數(shù)：包含特定項集的事務個數(shù)。支持度：未定義。頻繁項集：滿足最小支持度閾值的所有項集。

關聯(lián)規(guī)則形如X->Y的蘊含表達式。{牛奶，啤酒}->{尿布}偶然么？支持度：同時包含X,Y的事務的比例可信么？置信度：在包含X的事務中，Y出現(xiàn)的比例關聯(lián)分析的基本概念關聯(lián)規(guī)則挖掘：第一步：產生頻繁項集；因為規(guī)則的支持度僅依賴于XUY的支持度。第二部：產生關聯(lián)規(guī)則。難點在第一步，指數(shù)空間內的搜索。關聯(lián)分析的基本概念問題：

為什么n個項的數(shù)據(jù)集中所有的可能規(guī)則為： 3^n-2^(n+1)+1關聯(lián)分析的基本概念先驗原理：如果一個項集是頻繁的，那么它的所有子集也一定是頻繁的。Apriori算法

反單調性：一個項集的支持度不會超過其子集的支持度?；谥С侄鹊募糁Γ喝绻硞€項集是非頻繁的，其超集也一定是非頻繁的。Apriori算法剪枝實例：Apriori算法蠻力法C(6,1)=6C(6,2)=15C(6,3)=2041剪枝C(6,1)=6C(4,2)=6113Apriori算法Apriori-gen子函數(shù)蠻力法：枚舉所有C(d，k)個k-項集合；Fk-1×F1方法：組合頻繁(k-1)-項集和頻繁-1項集。Fk-1×Fk-1方法:合并前k-2項相同的兩個頻繁k-1項集。后兩者依賴字典序以避免重復生成候選。Apriori算法支持度計數(shù)（1）蠻力法：

對每個事務與當前項做比較，并更新當前第k-候選集中每個元素的支持度計數(shù)。Apriori算法支持度計數(shù)（2）枚舉事務的k-項集并與候選的頻繁項集比對

核心思想：各項字典排序，生成有序排列Apriori算法支持度計數(shù)（3）使用Hash樹進行支持度計數(shù)由候選項集構成Hash樹，再讓每條事務來遍歷。Apriori算法1，確定Hash函數(shù)，本例為h(p)=pmod3;2，由hash函數(shù)確定候選項集的Hash樹；3，對每一條事務，采用同樣的函數(shù)遍歷Hash樹；4，如果葉子上的候選項集是該事務的子集，則支持度+1；復雜度分析（1）影響復雜度的可能因素：支持度閾值：頻繁項集的數(shù)量和長度。項數(shù)：儲存開銷，候選項集數(shù)。事務數(shù)：每次Hash剪枝都要掃描數(shù)據(jù)集。事務的平均寬度：頻繁項集的長度和支持度計數(shù)時的遍歷Hash樹次數(shù)。Apriori算法復雜度分析（2）生成候選集。

采用Fk-1×Fk-1方法，每次合并前需要檢查其前k-2項目是否相同，即需要做k-2次比較。在壞的情況下，需要對每一對k-1項集都要進行合并，且每次都需要比較到k-2次的時候才能決定是否合并。Apriori算法復雜度分析（3）針對每個k-項候選集構造Hash樹并儲存。

K-項集存入的Hash樹的深度為k，因此時間復雜度為：Apriori算法復雜度分析（4）候選集剪枝（計算支持度計數(shù)之前）。

每一個候選k-項集由兩個k-1項集合并產生，要附加的候選剪枝步驟來確保該候選的其余k-2個子集是頻繁的。因此這一步的復雜度為：？？？×|Fk-1|Apriori算法復雜度分析（5）支持度計數(shù)。

每個事務平均將產生C(w,k)個k-項集。每個k-項集在Hash樹查找對應葉子的花費是O(k)。書中認為其開銷為：；O(N*Σ(k*C(w,k)))Apriori算法復雜度分析（6）未統(tǒng)計的復雜度，包括了：Fk+1×Fk+1時的字典排序；結論：多次掃描事務是Apriori算法的固有缺陷，此算法有效，但是時間復雜度巨大。Apriori算法生成規(guī)則基于置信度的剪枝如果規(guī)則X->Y-X不滿足置信度閾值，則X’->Y-X’的規(guī)則也一定不滿足置信度閾值，X’為X的子集。Apriori算法先從后件為1的的規(guī)則開始剪枝。Apriori算法FP（頻繁模式）樹FP增長算法掃描數(shù)據(jù)集，統(tǒng)計頻繁項，拋棄非頻繁項，對事務進行排序；第二次掃描數(shù)據(jù)集，構建并擴充FP樹；FP樹中包含了：每個節(jié)點的指針和計數(shù)，另有連接相同節(jié)點的指針列表。1.找到后綴e；2.尋找e的前綴路徑；3.更新條件FP樹；4.迭代下一個結尾Xe；FP增長算法如果挖掘了很多的關聯(lián)模式怎么辦？每個關聯(lián)模式都是非平凡的么？僅僅依賴支持度和置信度就一定正確么？關聯(lián)模式的評估{茶}->{咖啡}支持度15%，置信度75%，但是實際上喝咖啡的人愛喝茶的比例（75%）低于所有人中愛喝茶的人（80%）比例。基于興趣度的客觀度量。支持度-置信度缺陷原因：忽略了后件的支持度。提升度（li