【正文】 根據(jù)項(xiàng)目集支持?jǐn)?shù)的定義，很容易知道支持 X 的元組一定支持 Y，所以 s1 ≥s ，即 support（ Y） ≥ support （ X）。 □ ? 定理（ Appriori 屬性 2） .如果項(xiàng)目集 X 是非頻繁項(xiàng)目集，那么它的所有超集都是非頻繁項(xiàng)目集。 ? 算法 31 Apriori（發(fā)現(xiàn)頻繁項(xiàng)目集） （ 1） L1 = {large 1itemsets}。 Lk1??。 // Ck是 k候選集 （ 4） FOR all transactions t?D DO BEGIN （ 5） Ct=subset（ Ck， t） 。 （ 8） END （ 9） Lk={c?Ck |?minsup_count} （ 10） END （ 11） L= ?Lk。 ? has_infrequent_subset（ c， Lk1），判斷 c是否加入到 k侯選集中。//把 q的第 k1個(gè)元素連到 p后 （ 5） IF has_infrequent_subset（ c， Lk1） THEN （ 6） delete c。 （ 8） END （ 9） Return Ck。 ? 算法 34 從給定的頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則 ? 算法 34的核心是 genrules遞歸過程，它實(shí)現(xiàn)一個(gè)頻繁項(xiàng)目集中所有強(qiáng)關(guān)聯(lián)規(guī)則的生成。 2020年 10月 5日星期一 17 算法 遞歸測(cè)試一個(gè)頻集中的關(guān)聯(lián)規(guī)則 genrules（ lk: frequent kitemset， xm: frequent mitemset） （ 1） X={（ m1） itemsets xm1 | xm1 in xm }； （ 2） FOR each xm1 in X BEGIN （ 3） conf = support（ lk） /support（ xm1） 。 （ 6） IF （ m1 1） THEN //generate rules with subsets of xm1 as antecedents （ 7） genrules（ lk， xm1） 。 ? Apriori算法有兩個(gè)致命的性能瓶頸 : ? 1．多次掃描事務(wù)數(shù)據(jù)庫(kù)，需要很大的 I/O負(fù)載 ? 對(duì)每次 k循環(huán)，侯選集 Ck中的每個(gè)元素都必須通過掃描數(shù)據(jù)庫(kù)一次來(lái)驗(yàn)證其是否加入 Lk。 ? 2．可能產(chǎn)生龐大的侯選集 ? 由 Lk1產(chǎn)生 k侯選集 Ck是指數(shù)增長(zhǎng)的，例如 104個(gè) 1頻繁項(xiàng)目集就有可能產(chǎn)生接近 107個(gè)元素的 2侯選集。 2020年 10月 5日星期一 21 第 3章 知識(shí)發(fā)現(xiàn)與關(guān)聯(lián)規(guī)則挖掘（ 二 ） 內(nèi)容提要 ? 基本概念與解決方法 ? 經(jīng)典的頻繁項(xiàng)目集生成算法分析 ? Apriori算法的性能瓶頸問題 ? Apriori的改進(jìn)算法 ? 對(duì)項(xiàng)目集格空間理論的發(fā)展 ? 基于項(xiàng)目序列集操作的關(guān)聯(lián)規(guī)則挖掘算法 ? 改善關(guān)聯(lián)規(guī)則挖掘質(zhì)量問題 ? 約束數(shù)據(jù)挖掘問題 ? 關(guān)聯(lián)規(guī)則挖掘中的一些更深入的問題 ? 數(shù)量關(guān)聯(lián)規(guī)則挖掘方法 2020年 10月 5日星期一 22 提高 Apriori算法效率的技術(shù) ? 一些算法雖然仍然遵循 Apriori 屬性，但是由于引入了相關(guān)技術(shù)，在一定程度上改善了 Apriori算法適應(yīng)性和效率。 ? 基于散列（ Hash）的方法：基本原理是“在一個(gè) hash桶內(nèi)支持度小于最小支持度的 k項(xiàng)集不可能是全局頻繁的 ” 。 ? 其他：如，動(dòng)態(tài)刪除沒有用的事務(wù)：“不包含任何 Lk的事務(wù)對(duì)未來(lái)的掃描結(jié)果不會(huì)產(chǎn)生影響，因而可以刪除 ” 。如果一個(gè)數(shù)據(jù)分塊 Di 的局部最小支持?jǐn)?shù) minsup_counti （ i=1， 2， …， n），按著如下方法生成： minsup_counti= minsup_count *||Di|| / ||D|| 則所有的局部頻繁項(xiàng)目集涵蓋全局頻繁項(xiàng)目集。 ? 2．支持并行挖掘算法： 每個(gè)分塊的局部頻繁項(xiàng)目集是獨(dú)立生成的，因此提供了開發(fā)并行數(shù)據(jù)挖掘算法的良好機(jī)制。因此， Park等利用了這個(gè)性質(zhì)引入 雜湊技術(shù) 來(lái)改進(jìn)產(chǎn)生 2頻繁項(xiàng)目集的方法。因此，探索新的理論和算法來(lái)減少數(shù)據(jù)庫(kù)的掃描次數(shù)和侯選集空間占用，已經(jīng)成為近年來(lái)關(guān)聯(lián)規(guī)則挖掘研究的熱點(diǎn)之一。 ? 什么是一個(gè)閉合的項(xiàng)目集？ ? 一個(gè)項(xiàng)目集 C是閉合的，當(dāng)且僅當(dāng)對(duì)于在 C中的任何元素，不可能在 C中存在 小于或等于 它的支持度的子集。 樣本數(shù)據(jù)庫(kù) TID Itemset 1 A， B， C， D 2 B， C， E 3 A， B， C， E 4 B， D， E 5 A， B， C， D 2020年 10月 5日星期一 29 FPtree算法的基本原理 ? 進(jìn)行 2次數(shù)據(jù)庫(kù)掃描：一次對(duì)所有 1項(xiàng)目的頻度排序；一次將數(shù)據(jù)庫(kù)信息轉(zhuǎn)變成緊縮內(nèi)存結(jié)構(gòu)。 ? 基本步驟是： ? 兩次掃描數(shù)據(jù)庫(kù)，生成頻繁模式樹 FPTree： ? 掃描數(shù)據(jù)庫(kù)一次，得到所有 1項(xiàng)目的頻度排序表 T； ? 依照 T，再掃描數(shù)據(jù)庫(kù)，得到 FPTree。 2020年 10月 5日星期一 30 生成頻繁模式樹 FPTree {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 min_support = TID Original Items (ordered) frequent items 100 {f, a, c, d, g, i, m, p} {f, c, a, m, p} 200 {a, b, c, f, l, m, o} {f, c, a, b, m} 300 {b, f, h, j, o} {f, b} 400 {b, c, k, s, p} {c, b, p} 500 {a, f, c, e, l, p, m, n} {f, c, a, m, p} 2020年 10月 5日星期一 31 挖掘頻集步驟 1：生成條件模式庫(kù) ? 為每個(gè)節(jié)點(diǎn)， 尋找它的所有前綴路徑并記錄其頻度，形成 CPB條件模式庫(kù) CPB item cond. pattern base c f:3 a fc:3 b fca:1, f:1, c:1 m fca:2, fcab:1 p fcam:2, cb:1 {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020年 10月 5日星期一 32 挖掘頻集步驟 2：構(gòu)造 CFPtree ? 為每一個(gè)節(jié)點(diǎn)，通過 FPtree構(gòu)造一個(gè) CFPtree ? 例如， m節(jié)點(diǎn)的 CFPtree為： mCPB: fca:2, fcab:1 {} f:3 c:3 a:3 mconditional FPtree ? {} f:4 c:1 b:1 p:1 b:1 c:3 a:3 b:1 m:2 p:2 m:1 T Item frequency head f 4 c 4 a 3 b 3 m 3 p 3 2020年 10月 5日星期一 33 挖掘頻集步驟 3：遞歸構(gòu)造 CFPtree {} f:3 c:3 a:3 mconditional FPtree {} f:3 c:3 amconditional FPtree {} f:3 cmconditional FPtree f:3 {} camconditional FPtree 所有頻集： m, fm, cm, am, fcm, fam, cam, fcam 單路徑可以形成頻集 2020年 10月 5日星期一 34 ? 定理：令 α 是 DB的一個(gè)頻繁集， B為 α 的條件模式庫(kù)， β 是 B中一個(gè)項(xiàng)，要使 α∪ β 是 DB中的頻繁集，當(dāng)且僅當(dāng) β 是 B的頻繁集 ? 例子： abcde是頻繁集，且 f在包含 abcde的事物中是頻繁的，則 abcdef是頻繁集，依據(jù)上述定理，我們可以實(shí)現(xiàn)頻繁集的增長(zhǎng)。 ? 所謂 項(xiàng)目序列 是指項(xiàng)目集中的元素按著某種標(biāo)準(zhǔn)進(jìn)行有序排列。 ? 為了重復(fù)利用對(duì)數(shù)據(jù)庫(kù)的掃描信息，把來(lái)自數(shù)據(jù)庫(kù)的信息組織成項(xiàng)目序列集（ Set of itemsequences）形式，并且對(duì)項(xiàng)目序列集格及其操作代數(shù)化。 ? 定義 36（項(xiàng)目序列集間（上）的屬于（ ?）、包含（ ?）、并（ ∪ ）、交（ ∩ ）、差（－）等操作和普通的集合操作相同。 2020年 10月 5日星期一 38 項(xiàng)目序列集格上的亞操作 ? 定義 37 設(shè) ISS1和 ISS2是定義在 I上的兩個(gè)項(xiàng)目序列集， IS是定義在 I上的一個(gè)項(xiàng)目序列，定義如下操作： ? 亞屬于（ ?sub）： IS?sub ISS1當(dāng)且僅當(dāng) ? IS1?ISS1使得 IS?IS1； ? 亞包含（ ?sub）： ISS1?subISS2當(dāng)且僅當(dāng) ? IS1?ISS1? IS1?subISS2； ? 亞交（ ∩ sub）： ISS1∩ subISS2={IS | IS?subISS1且IS?subISS2}； ? 亞并（ ∪ sub）： ISS1∪ subISS2={IS | IS?subISS1或IS?subISS2}。 2020年 10月 5日星期一 39 基于項(xiàng)目序列集操作的關(guān)聯(lián)規(guī)則挖掘算法 算法 314 ISSDM Algorithm 輸入：數(shù)據(jù)庫(kù) D 輸出：最大頻繁項(xiàng)目序列集 ISS* （ 1） Input（ minsup_count）； （ 2） ISS ? 216。 ISS* ? 216。 ? make_fre（ IS， ISS， ISS*）從 ISS挑選頻繁的并加入到 ISS*。 216。 2 BCE {（ ABCD， 1），（ BCE， 1） } {BC} 3 ABCE {（ ABCD， 1） ， （ BCE， 1） ， （ ABCE， 1） } {ABC， BCE} 裁 *BC。BD。 ? 實(shí)用性：挖掘出的規(guī)則必須是簡(jiǎn)潔可用的。 ? 改善關(guān)聯(lián)規(guī)則挖掘 質(zhì)量 是一件很困難的工作。粗略地說，可以在 用戶主觀和系統(tǒng)客觀 兩個(gè)層面上考慮關(guān)聯(lián)規(guī)則挖掘的質(zhì)量問題。 ? 用戶可以在不同的層面、不同的階段、使用不同的方法來(lái)主觀設(shè)定約束條件。例如，如果一個(gè)商業(yè)企業(yè)希望根據(jù)客戶特點(diǎn)進(jìn)行有針對(duì)性地銷售，那么使用 分類或聚類 形式可以幫助用戶形成客戶群。 ? 維 /層次約束： 限制聚焦的維數(shù)或粒度層次，也可以針對(duì)不同的維設(shè)置約束條件。 ? 針對(duì)具體