【正文】 于項(xiàng)集 }I,{I 21 ，它在事 務(wù) 1， 4， 5 中都出 12 現(xiàn)了，意味著其支持度計(jì)數(shù)要增加 3 次。 圖 32 給出了 Apriori 算法產(chǎn)生頻繁項(xiàng)集的一個(gè)高層實(shí)例。對(duì)其進(jìn)行計(jì)數(shù)后發(fā)現(xiàn) }I,{I 41 和}I,{I 42 均小于 3，因此被刪除。 13 圖 3 2 基于支持度的剪枝策略的實(shí)例 (3)支持度計(jì)數(shù)策略 確定在候選項(xiàng)剪枝步驟保留下來的每個(gè)候選項(xiàng)集出現(xiàn)的頻繁程度是支持度計(jì) 數(shù)的主要工作。 以上幾種方法都是針對(duì)減少數(shù) 據(jù)庫的掃描 和 比較次數(shù)而設(shè)計(jì)的，我們還可以結(jié)合基于支持度的剪枝策略對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行壓縮，這樣記錄減少，計(jì)數(shù)開銷也就少了。 首先創(chuàng)建并用 “nul ”標(biāo)記樹的根結(jié)點(diǎn)，然后掃描數(shù)據(jù)庫，并對(duì)每個(gè)事務(wù)中的項(xiàng)按 L 中的次序處理，并建立一個(gè)分枝 ； 如果要給一個(gè)事務(wù)增加分枝，首先將與此結(jié)點(diǎn)有共同前綴上的每個(gè)結(jié)點(diǎn)的計(jì)數(shù)都增加 1，然后為跟隨在前綴之后的項(xiàng)創(chuàng)建結(jié)點(diǎn)，并將其鏈接。[1 8 ]下面圖 33 給出了 growthFP 算法。 表 3 2 按結(jié)果集 L 中的次序處理 D 中的每個(gè)事務(wù)的項(xiàng) TID 項(xiàng) ID 的列表 T1 a， f， b， m， p T2 a， f， b， c， m T3 a， c T4 f， c， p T5 a， f， b， m， p 具體 treeFP? 構(gòu)造如下： 首先，創(chuàng)建 treeFP? 的根結(jié)點(diǎn)，標(biāo)記為 “null”，然后根據(jù)表 32 中每個(gè)處理過的事務(wù)創(chuàng)建相應(yīng)的分枝，構(gòu)建 treeFP? ，這里處理過的事務(wù)是指只包括頻繁掃描 D，對(duì)每個(gè)候選計(jì)數(shù) 項(xiàng)集 a b c d e f m p 支持度計(jì) 數(shù) 4 3 3 2 1 4 3 3 刪除候選支持度計(jì)數(shù)小于最小支持度計(jì)數(shù)的項(xiàng)集 C1 項(xiàng)集 a b c f m p 支持度計(jì) 數(shù) 4 3 3 4 3 3 L1 頻繁項(xiàng)的集合按支持度計(jì)數(shù) 遞減排序 結(jié)果集 L 項(xiàng)集 a f b c m p 支持度計(jì) 數(shù) 4 4 3 3 3 3 16 項(xiàng)，且頻繁項(xiàng)已按結(jié)果集 L 排序。對(duì)于第四個(gè)事務(wù) pc,f,:T4 ，由于不共享任何前綴，所以創(chuàng)建一個(gè)新的分枝 ?? 1):(p1) ,:(c1) ,:f( ，其中 f 作為根的子女鏈接， c 鏈接到 f， p 鏈接到c。 圖 3 5 根據(jù)表 31 構(gòu)建的 FPtree 第三步，挖掘 treeFP? 。 對(duì)于項(xiàng)頭表中倒數(shù)第二個(gè)頻繁項(xiàng) m，由項(xiàng)頭表中 m 的結(jié)點(diǎn)鏈，考慮 m 作為后綴，可知它的對(duì)應(yīng)前綴路徑為 ?? 2):bf,a,( 和 ?? 1):cb,f,a,( ，從而構(gòu)成了 m的條件模式基。 表 3 3 挖掘圖 34 的 FPtree 的結(jié)果 項(xiàng) 條件模式基 條件 treeFP? 產(chǎn)生的頻繁模式 p 1) }:c(f,2) ,:mb,f,{ ( a , ?? 3:f 3:p f m 1) }:cb,f,( a ,2) ,:bf,{ ( a , ?? 3:b3,:f3,:a 3,:m b3,:m f3,:m a 3,:m b f3,:m b a3,:m f a 3:m b f a c 1) }:bf,( a ,1) ,:(f1) ,:{ ( a ? ? b 3)}:f{(a, ?? 3:f3,:a 3:b f a3,:b f3,:b a f 3)}:{(a ?? 3:a 3:f a growthFP? 算法有其優(yōu)缺點(diǎn)，相對(duì) Apriori 算法，優(yōu)點(diǎn)在于它避免產(chǎn)生大量的候選項(xiàng)集并減少了掃描數(shù)據(jù)庫的次數(shù)，尤其適合挖掘長的和短的頻繁模 式。 結(jié)合 “一般到特殊 ”和 “特殊到一般 ”的遍歷策略，它需要更多的空間存儲(chǔ)候選項(xiàng)集以便進(jìn)行雙向搜索，但有助于快速確定頻繁項(xiàng)集邊界。 ② 事務(wù)數(shù)據(jù)集的表示方法?？梢愿鶕?jù)項(xiàng)集的前綴或后綴來定義等價(jià)類。 (5) 產(chǎn)生頻繁項(xiàng)集的其他方法 ① 遍歷項(xiàng)集格的策略主要包括以下幾種策略： “一般到特殊 ” 的遍歷策略，即合并兩個(gè)頻繁 ??1)(k 項(xiàng)集得到候選 ?k 項(xiàng)集， Apriori 算法使用的就是這個(gè)策略，它對(duì)于頻繁項(xiàng)集的最大長度不是太長的情況是有效的。 [17] 利用相同的分析方法，可以得到項(xiàng)頭表中其他頻繁項(xiàng)的條件模式基和條件treeFP? ，并導(dǎo)出相應(yīng)的頻繁模式。 對(duì)于圖 34 中構(gòu)建的 treeFP? ，從項(xiàng)頭表中最后一個(gè)頻繁項(xiàng) p 開始，由項(xiàng)頭表中 p 的結(jié)點(diǎn)鏈，可知在圖 34 的 treeFP? 中 p 出現(xiàn)在兩個(gè)分枝上，分別為項(xiàng) ID a f b c m p 支持度 計(jì)數(shù) 4 4 3 3 3 3 結(jié)點(diǎn)鏈 null{} a： 4 f： 3 b： 3 m： 2 p： 2 c： 1 c： 1 m： 1 f： 1 c： 1 p： 1 17 ?? 2):(p2) ,:(m3) ,:(b3) ,:(f4) ,:a( 和 ?? 1):(p1) ,:(c1) ,:f( ，考慮 p 作為后綴，它的兩個(gè)對(duì)應(yīng)前綴的路徑為 ?? 2):mb,f,a,( 和 ?? 1):cf,( ，構(gòu)成了 p 的條件模式基。為方便樹的遍歷，通常需要?jiǎng)?chuàng)建一個(gè)項(xiàng)目頭，它由項(xiàng) ID，對(duì)應(yīng)的支持度計(jì)數(shù)和結(jié)點(diǎn)鏈組成，每個(gè)項(xiàng)可以通過一個(gè)結(jié)點(diǎn)鏈指向它在樹中的出現(xiàn)。 [18]對(duì)于第二個(gè)事務(wù) m,c,b,f,a:2T ， 由 于 它 與 treeFP? 的 第 一 個(gè) 分 枝?? 1):(p1) ,:(m1) ,:(b1) ,:(f1) ,:a( 有共享前綴 ?? bf,a, ，所以將共享前綴的計(jì)數(shù)均增加 1，此時(shí)第一個(gè)分枝變?yōu)??? 1):(p1) ,:(m2) ,:(b2) ,:(f2) ,:a( ，對(duì)于 T2 中剩余的頻繁項(xiàng)，按順序創(chuàng)建新的結(jié)點(diǎn) 1):(c 和 1):(m ，使 1):(c 作為 2):(b 的子女鏈接，m 鏈接到 c。 表 3 1 事務(wù)數(shù)據(jù)庫 D TID 項(xiàng) ID 的列表 T1 a， b， f， m， p T2 a， b， c， f， m T3 a， c， e T4 c， d， f， p T5 a， b， d， f， m， p 第一步，如圖 34 所示，生成 L1 和結(jié)果集 L。 ③ treeFP? 的挖掘，即頻繁模式的挖掘。 下面將用三步描述此算法： 掃描 D，對(duì)每個(gè)候選計(jì)數(shù) 項(xiàng)集 { I1 ,I2 } { I1 ,I3 } { I1 ,I4 } { I2, I3 } { I2 ,I4 } { I3 ,I4 } 支持度計(jì) 數(shù) 4 4 5 3 1 2 刪除候選支持度計(jì)數(shù)小于最小支持度計(jì)數(shù)的項(xiàng)集 C1 項(xiàng)集 I1 I2 I3 I4 支持度計(jì) 數(shù) 4 4 5 3 L1 由 L1 產(chǎn)生候選 C2 ，并對(duì)每個(gè)候選計(jì)數(shù) 項(xiàng)集 I1 I2 I3 I4 I5 I6 C2 支持度計(jì) 數(shù) 3 4 2 4 2 3 刪除候選支持度計(jì)數(shù)小于最小支持度計(jì)數(shù)的項(xiàng)集 項(xiàng)集 { I1 ,I2 } { I1 ,I3 } { I2, I3 } { I3 ,I4 } 支持度計(jì) 數(shù) 3 4 4 3 L2 由 L 2 產(chǎn)生候選 C3 ，并對(duì)每個(gè)候選計(jì)數(shù) 項(xiàng)集 { I1 ,I2,I3 } 支持度計(jì) 數(shù) 3 C3 項(xiàng)集 { I1 ,I2,I3 } 支持度計(jì) 數(shù) 3 L3 14 ① 已知 min_sup ，掃描數(shù)據(jù)庫 D，產(chǎn)生頻繁 1 項(xiàng)集，并按支持度計(jì)數(shù)遞減排序，生成結(jié)果集 L。 另外一種方法是利用前綴結(jié)構(gòu)，即通過從最左項(xiàng)到最右項(xiàng)依次指定項(xiàng)集的項(xiàng)的方式，將每個(gè)事務(wù)所包含的項(xiàng)集系統(tǒng)地枚舉出來，然后利用它們更新對(duì)應(yīng)的候選項(xiàng)集的支持度。 通過實(shí)例，降低產(chǎn)生頻繁項(xiàng)集計(jì)算復(fù)雜度具體表現(xiàn)在，在枚舉所有項(xiàng)集到3 項(xiàng)集的方法中將產(chǎn)生 4120xx6C 362616 ?????? CC 個(gè)候選，而使用 Apriori 時(shí)，將減少為 131661C 2416 ?????? C 個(gè)候選，數(shù)目降低了 %。初始時(shí)每個(gè)項(xiàng)都被看作是候選 1 項(xiàng)集，當(dāng)給每個(gè)項(xiàng)計(jì)數(shù)支持度時(shí)，發(fā)現(xiàn) }{I5 和 }{I6 的支持度計(jì)數(shù)均小于 3，故被刪除。 圖 3 1 費(fèi)力策略示意圖 (2) 基于支持度的剪枝 (supportbased pruning)策略 這個(gè)策略主要幫助減少頻繁項(xiàng)集產(chǎn)生時(shí)需要探查的候選項(xiàng)集個(gè)數(shù)，主要使用支持度度量對(duì)候選項(xiàng)集進(jìn)行有效地剪枝，主要依據(jù)的是性質(zhì) , 和 。 [16] 例 已知事務(wù)數(shù)據(jù)庫 D ， 5|D| ? ，并按字典次序存放事務(wù)中的項(xiàng)。 產(chǎn)生頻繁項(xiàng)集和規(guī)則的相關(guān)技術(shù) 頻繁項(xiàng)集的產(chǎn)生策略 (1) 費(fèi)力策略 費(fèi)力策略是指對(duì)于格結(jié)構(gòu)中每個(gè)候選項(xiàng)集 item s ets ) (c andi da te 的支持度進(jìn)行計(jì)數(shù)。由 支持度 (s)的公式可得出，規(guī)則 YX? 的支持度僅依賴于其對(duì)應(yīng)項(xiàng)集 YX? 。對(duì)于每個(gè)可能的規(guī) 則，我們都計(jì)算它的支持度和置信度，顯然這個(gè)做法十分費(fèi)力且代價(jià)大，畢竟規(guī)則是呈指數(shù)級(jí)從數(shù)據(jù)集中提取出來。 [14] 證明：已知頻繁項(xiàng)目集 Y，即 m in_ supsup po rt(Y) ? ，對(duì)于 YX? ，由性質(zhì) ， 11 可知 m i n_s ups uppo r t ( Y )s uppo r t ( X ) ?? ，可得項(xiàng)目集 X 也是頻繁的。 定義 ：強(qiáng)關(guān)聯(lián)規(guī)則必須 同 時(shí)滿足 min_sup 和 min_conf 。數(shù)據(jù)集需滿足的最小支持度 閾 值被稱為最小支持度s up por t) (m ini m um ，簡記為 min_sup 。數(shù)學(xué)上用T}t,tX|{tσ (X ) iii ??? 表示項(xiàng)集 X 的支持度計(jì)數(shù)，其中，符號(hào) |?|表示集合中元素的個(gè)數(shù)。用 TID 標(biāo)識(shí) 每個(gè)事務(wù)， 事務(wù)的寬度定義為 事務(wù)中出現(xiàn)項(xiàng)的個(gè)數(shù)。 本章小結(jié) 本章主要介紹了數(shù)據(jù)挖掘的起源，數(shù)據(jù)挖掘的基本概念，數(shù)據(jù)挖掘的任務(wù)、過程和方法，并簡要介紹了數(shù)據(jù)挖掘研究的發(fā)展趨勢。 (6) 復(fù)雜數(shù)據(jù)類型挖掘的新方法。在改進(jìn)多個(gè)數(shù)據(jù)挖掘系統(tǒng)和功能間的互操作、數(shù)據(jù)挖掘的系統(tǒng)化開發(fā)以及數(shù)據(jù)挖掘系統(tǒng)在社會(huì)和企業(yè)中的教育和使用等方面，標(biāo)準(zhǔn)化的數(shù)據(jù)挖 掘語言起到極大的促進(jìn)作用。在電子商務(wù)和衛(wèi)生保健領(lǐng)域，人們?cè)絹碓疥P(guān)注數(shù)據(jù)挖掘破壞隱私的問題，導(dǎo)致人們對(duì)研究保護(hù)用戶隱私的數(shù)據(jù)挖掘算法的興趣膨脹。 確定合適的聚類算法，需要考慮很多因素，比如聚類的類型、簇的類型和特性、簇描述、數(shù)據(jù)集和屬性的特性、噪聲和離群點(diǎn)、數(shù)據(jù)對(duì)象的個(gè)數(shù)、屬性的個(gè)數(shù)和算法的考慮等，但是沒有一種算法能夠適應(yīng)所有的數(shù)據(jù)類型、簇和應(yīng)用，所以進(jìn)一步開發(fā)的空間很大。另外還 有 Chameleon 算法，它是一種使用自相似性概 念確定簇是否應(yīng)當(dāng)合并的層 次聚類算法；基于共享的最 近鄰S N N )N e igh bo r ,N e a r e s t ( S ha r e d 相 似性度量 的 )P atric k( JPJarvis 聚類算 法和基 于SNN 密度的聚類算法。第二種是子空間聚類，它是在所有維的子空間中尋找簇（稠密區(qū)域）， Q U E s t )I n s t e r ingC L I Q U E ( C lu 算法是系統(tǒng)地發(fā)現(xiàn)子空間簇的基于網(wǎng)格的聚類算法。使用簇中對(duì)象的質(zhì)心作為簇的原型 的 k 均值算法是最常用的 。 除了以上分類方法以外，還有由訓(xùn)練數(shù)據(jù)構(gòu)建一組基分類器，然后通過對(duì)每個(gè)基分類器 )classifier (base 的預(yù)測進(jìn)行投票來進(jìn)行分類 的組合 (ensemble) 方法 ，代表算法有 AdaBoost 、 c ombi ni ng ) a nd r e s a mpl ing pti veA r c ing ( a da 自適應(yīng)再抽樣和組合算法等。它的特點(diǎn)是至少含有一個(gè)隱藏層的多層神經(jīng)網(wǎng)絡(luò)是可以用來近似任何目標(biāo)函數(shù)， ANN 可以處理冗余特征，對(duì)訓(xùn)練數(shù)據(jù)中的噪聲很敏感， ANN 權(quán)值學(xué)習(xí)使用的梯度下降方法經(jīng)常會(huì)收斂到局部極小值，并且 訓(xùn)練 ANN 是一個(gè)很耗時(shí)的過程，尤其 當(dāng)隱藏結(jié)點(diǎn)數(shù)量很大 的情況下。除自頂向下方法外，其他生長決策樹的策略還有自底向上的方法和雙向的方法。 (2) 分類分析方法 ① 有這樣一種分類法， 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)， 它采取一系列局部最優(yōu)決策來構(gòu)造決策樹， 從而能夠在合理的時(shí)間內(nèi)構(gòu)造出具有一定 準(zhǔn)確率的次最優(yōu)決策樹。它的主要依