【正文】 層次的最小支持度相對(duì)較小，而較高層次的最小支持度相對(duì)較大。但是弊端也是顯然的： ? 不同層次可能考慮問題的精度不同、面向的用戶群不同。 2020年 10月 5日星期一 53 約束之間的關(guān)系 Succinctness Antimonotonicity Monotonicity Convertible constraints Inconvertible constraints 2020年 10月 5日星期一 54 第 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日星期一 55 多層次關(guān)聯(lián)規(guī)則挖掘 ? 根據(jù)規(guī)則中涉及到的層次，多層次關(guān)聯(lián)規(guī)則可以分為： ? 同層關(guān)聯(lián)規(guī)則： 如果一個(gè)關(guān)聯(lián)規(guī)則對(duì)應(yīng)的項(xiàng)目是同一個(gè)粒度層次，那么它是同層關(guān)聯(lián)規(guī)則。 ? 如果一個(gè)約束是簡(jiǎn)潔的，那么我們就可以直接使用 SQL查詢來得到滿足條件的集合。 ? 定義 318 如果一個(gè)約束 C滿足下面的條件，那么稱它是單調(diào)可轉(zhuǎn)變的： ? C（ S）既不是單調(diào)性約束，也不是反單調(diào)性約束； ? 若存在順序 R，使得經(jīng) R排序后的 I滿足：任給 S*∈{suffix_S} ，有C（ S*） =C（ S）。 ? 這樣的約束可以用來裁減不必要的探索，提高挖掘效率。因?yàn)橐粋€(gè)項(xiàng)目集滿足這個(gè)條件，那么它的超集也一定滿足這個(gè)條件。 ? 將約束條件用于頻繁集的查詢無非是找出那些滿足 C的頻繁集。 2020年 10月 5日星期一 47 約束的類型 ? 一些常用的名詞和符號(hào)： ? 定義 312 設(shè)項(xiàng)目集 I={i1， i2， ? ， im}，事務(wù)數(shù)據(jù)庫(kù)T=tid， It，模式 S和 S*都是項(xiàng)目集 I的子集，如果S*?S，則稱 S*是 S的 子模式（ Subpattern） ； S是 S*的 超模式（ Superpattern） 。約束的使用可以幫助我們發(fā)現(xiàn)問題，并及時(shí)加以調(diào)整，使知識(shí)發(fā)現(xiàn)的各個(gè)階段按著正確的方向發(fā)展。 ? 這些工作都期望通過引入新的度量機(jī)制和重新認(rèn)識(shí)關(guān)聯(lián)規(guī)則的系統(tǒng)客觀性來改善挖掘質(zhì)量。 2020年 10月 5日星期一 44 系統(tǒng)客觀層面 ? 使用 “ 支持度 可信度 ” 的關(guān)聯(lián)規(guī)則挖掘度量框架，在客觀上也可能出現(xiàn)與事實(shí)不相符的結(jié)果。 ? 數(shù)據(jù)的約束： 對(duì)數(shù)據(jù)的約束可以起到減少數(shù)據(jù)挖掘算法所用的數(shù)據(jù)量、提高數(shù)據(jù)質(zhì)量等作用。 2020年 10月 5日星期一 43 用戶主觀層面 ? 一個(gè)規(guī)則的有用與否最終取決于 用戶的感覺 。 ? 新穎性：挖掘出的關(guān)聯(lián)規(guī)則可以為用戶提供新的有價(jià)值信息。BCE 4 BDE {（ ABCD， 1），（ ABCE， 1），（ BDE， 1） } {ABC， BCE， BD} 5 ABCD {（ ABCD， 2） ， （ ABCE， 1） ， （ BDE， 1） } { ABCD， BCE } 裁 *ABC。 2020年 10月 5日星期一 40 ISSDM例子 操作 IS ISS 頻繁 ISS* 說明 初始 216。 。 ? 例子： 設(shè) ISS1={AB， CD}和 ISS2={ABCD， AD}是定義在 I ={A， B， C， D}上的項(xiàng)目序列集，則 AB?ISS1； AB?ISS2；{AB}?ISS1； {AB}?ISS2； ISS1∪ISS 2={AB， CD， ABCD，AD}； ISS1∩ISS 2= 216。 例如，我們可以按項(xiàng)目名稱的字典順序排列，也可以象 FPTree算法那樣，按它們?cè)跀?shù)據(jù)庫(kù)中出現(xiàn)次數(shù)的多少降序排列。 ? 使用 FPTree，生成頻集： ? 為 FPtree中的每個(gè)節(jié)點(diǎn)生成條件模式庫(kù)； ? 用條件模式庫(kù)構(gòu)造對(duì)應(yīng)的條件 FPtree； ? 遞歸挖掘條件 FPtrees同時(shí)增長(zhǎng)其包含的頻繁集： ? 如果條件 FPtree只包含一個(gè)路徑，則直接生成所包含的頻繁集。 ? 例如， C1={AB3， ABC2}是閉合的； C2={AB2， ABC2}不是閉合的； 2020年 10月 5日星期一 28 Close算法的例子 ? 下面是 Close算法作用到表 31數(shù)據(jù)集的執(zhí)行過程（假如 minsup_count=3）： ? 掃描數(shù)據(jù)庫(kù)得到 L1={(A,3), (B,5), (C,4), (D,3), (E,3)}；相應(yīng)關(guān)閉項(xiàng)目集為 Cl (A)={ABC,3}， Cl (B)={B,5}， Cl (C)={BC,4}， Cl (D)={BD,3}，Cl(E)={BE,3} ； ? L2={(AB,3), (AC,3), (BC,4), (BD,3), (BE,3)}；相應(yīng)關(guān)閉集為 C2 (AB)={ABC,3}； ? L3， L4， L5不用測(cè)，于是頻繁大項(xiàng)集為 {ABC }。 ? 例子： 桶地址 =（ 10x+y） mod 7； minsupport_count=3 TID Items 1 I1， I2， I5 2 I2， I4 3 I2， I3 4 I1， I2， I4 5 I1， I3 6 I2， I3 7 I1， I3 8 I1， I2， I3， I5 9 I1， I2， I3 桶地址 0 1 2 3 4 5 6 桶計(jì)數(shù) 2 2 4 2 2 4 4 桶內(nèi) {I1， I4} {I1， I5} {I2， I3} {I2， I4} {I2， I5} {I1， I2} {I1， I3} {I3， I5} {I1， I5} {I2， I3} {I2， I4} {I2， I5} {I1， I2} {I1， I3} {I2， I3} {I1， I2} {I1， I3} {I2， I3} {I1， I2} {I1， I3} L2={{I2， I3} ， {I1， I2} ， {I1， I3}} 2020年 10月 5日星期一 25 第 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日星期一 26 探索新的理論 ? 隨著數(shù)據(jù)庫(kù)容量的增大，重復(fù)訪問數(shù)據(jù)庫(kù)（外存）將導(dǎo)致性能低下。 ? 作用： ? 1．合理利用主存空間： 數(shù)據(jù)分割將大數(shù)據(jù)集分成小的塊，為塊內(nèi)數(shù)據(jù)一次性導(dǎo)入主存提供機(jī)會(huì)。 ? 基于采樣（ Sampling）的方法：基本原理是“通過采樣技術(shù)，評(píng)估被采樣的子集中，并依次來估計(jì) k項(xiàng)集的全局頻度 ” 。如此大的侯選集對(duì)時(shí)間和主存空間都是一種挑戰(zhàn)。 （ 8） END （ 9） END； 2020年 10月 5日星期一 18 Rulegenerate算法例子 ? Minconfidence=80% 序號(hào) lk xm1 confidence support 規(guī)則（是否是強(qiáng)規(guī)則） 1 235 23 100% 50% 23?5（ 是 ） 2 235 2 67% 50% 2?35（ 否 ） 3 235 3 67% 50% 3?25（否） 4 235 25 67% 50% 25?3（否） 5 235 5 67% 50% 5?23（否） 6 235 35 100% 50% 35?2（ 是 ） 2020年 10月 5日星期一 19 第 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日星期一 20 Apriori算法的性能瓶頸 ? Apriori作為經(jīng)典的頻繁項(xiàng)目集生成算法，在數(shù)據(jù)挖掘中具有里程碑的作用。 Rulegenerate（ L， minconf） （ 1） FOR each frequent itemset lk in L （ 2） genrules（ lk ， lk） 。//刪除含有非頻繁項(xiàng)目子集的侯選元素 （ 7） ELSE add c to Ck。 2020年 10月 5日星期一 14 apriorigen過程 ? 算法 apriori中調(diào)用了 apriorigen（ Lk1），是為了通過（ k1） 頻集產(chǎn)生 K侯選集。 k++） DO BEGIN （ 3） Ck=apriorigen（ Lk1） 。 證明 （略） 2020年 10月 5日星期一 13 經(jīng)典的發(fā)現(xiàn)頻繁項(xiàng)目集算法 ? 1994年， Agrawal 等人提出了著名的 Apriori 算法。對(duì) X的任一非空子集為 Y，設(shè) T中支持 Y的元組數(shù)為 s1。 ? 第 1個(gè)子問題是近年來關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)。 2020年 10月 5日星期一 9 可信度與關(guān)聯(lián)規(guī)則 ? 定義（關(guān)聯(lián)規(guī)則與可信度） .給定一個(gè)全局項(xiàng)目集 I和數(shù)據(jù)庫(kù) D，一個(gè)定義在 I和 D上的關(guān)聯(lián)規(guī)則形如I1?I2，并且它的 可信度 或 信任度 或 臵信度（ Confidence） 是指包含 I1和 I2的事務(wù)數(shù)與包含 I1的事務(wù)數(shù)之比，即 Confidence（ I1?I2） = support（ I1∪ I2） / support（ I1）， 其中 I1， I2?I， I1∩I 2=Ф 。