8數(shù)據(jù)挖掘ppt

1、挖掘頻繁模式，關(guān)聯(lián)和相關(guān)性： 基本概念和方法6.1基本概念 6.2頻繁項集挖掘方法6.3哪些模式是有趣的：模式評估方法頻繁模式頻繁模式是頻繁的出現(xiàn)在數(shù)據(jù)集中的模式。（項集，子序集，子結(jié)構(gòu)） 頻繁項集頻繁項集：頻繁的同時出現(xiàn)在交易數(shù)據(jù)集中的商品的集合。（面包和牛奶） 頻繁子序集頻繁子序集：一個子序列，如果它頻繁的出現(xiàn)在購物歷史數(shù)據(jù)中。（pc數(shù)碼相機內(nèi)存卡） 頻繁子結(jié)構(gòu)頻繁子結(jié)構(gòu)：一個子結(jié)構(gòu)可能涉及不同的結(jié)構(gòu)形式，如：子圖，子樹，子格；如果一個子結(jié)構(gòu)頻繁出現(xiàn)。6.1.1購物籃分析 頻繁項集挖掘的一個典型例子是購物籃分析。該過程通過發(fā)現(xiàn)顧客放入他們“購物籃購物籃”中的商品之間的關(guān)聯(lián)，分析顧客習慣。這

2、種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助零售商了解哪些商品頻繁的被顧客同時購買，從而更好地制定方案。 購物籃分析可以幫助設(shè)計不同的商品布局。一種一種策略策略：經(jīng)常買的商品可以擺放近一些，以便進一步刺激這些商品同時銷售；另一種策略另一種策略：把兩種關(guān)聯(lián)度高的產(chǎn)品放在商店兩端，可以誘發(fā)買這些商品的顧客一路挑選其他商品。（如面包和黃油） 每一個購物籃可以由一個布爾向量表示，可以分析布爾向量，得到反映商品頻繁關(guān)聯(lián)或同時購買的購買模式，這些模式可以用關(guān)聯(lián)規(guī)則的形式表示。 例 購買計算機也趨向于同時購買殺毒軟件，可以表示為computerantivirus softwaresupport=2%;confidence=60%(

3、6.1) 意義：分析所有事務的2%顯示計算機和殺毒軟件被同時購買；置信度60%意味著購買計算機的60%頁購買了殺毒軟件。 規(guī)則的支持度和置信度是規(guī)則興趣度的兩種度量。它們分別分別反映所發(fā)現(xiàn)規(guī)則的有用性有用性和確定確定性性。 最小支持度閾值，最小置信度閾值6.1.2 頻繁項集，閉項集和關(guān)聯(lián)規(guī)則 支持度s support(AB)=P(AUB) (6.2) 置信度c confidence(AB) =P(BA) (6.3) 同時滿足最小支持度閥值，最小置信度閥值 的規(guī)劃稱為強強規(guī)劃規(guī)劃。 項的集合稱為項集項集。包含k個項的項集稱為k項集 如果相對支持度滿足預定義最小支持度閾值，則是頻繁項集頻繁項集 。

4、 頻繁k項集的集合通常記為 kL 由（6.3）式，有 一般而言，關(guān)聯(lián)規(guī)則的挖掘是一個兩步過程：（1）找出所有的頻繁項集；（2）由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。 從大型數(shù)據(jù)集中挖掘頻繁項集的主要挑戰(zhàn)是，這種挖掘常常產(chǎn)生大量滿足最小閥值的項集，當閥值設(shè)定的很低時尤其如此。這是因為如果一個項集是頻繁的，則它的每一個項集都是頻繁的。 例 一個長度為100頻繁項集a1,a2,.a100包含100個頻繁1項集， 個頻繁2項集，因此頻繁項集的總個數(shù)為 個。為了克服這個困難，引入閉頻繁項集和極大頻繁項集的概念。)4 .6()(sup)(sup)/()(AportBAportABPBAconfidence2nC12

5、n 項集X的數(shù)據(jù)集D中是閉的閉的，如果不存在真超項集Y使得Y與X在D中 具有相同的支持度計數(shù)。 項集X是數(shù)據(jù)集D中的閉頻繁項集閉頻繁項集，如果X在D中是閉的和頻繁的。 項集X是D中的極大頻繁項集或極大項集，如果X是頻繁的，并且不存在超項集Y使得 并且Y在D中是頻繁的。（它的任意一個超級都是非頻繁的）例6.2閉的和極大的頻繁項集閉的和極大的頻繁項集。假設(shè)事務數(shù)據(jù)庫只有兩個事務：a1,a2,.a100,a1,a2,.a50.設(shè)最小支持度閥值為1.我們發(fā)現(xiàn)兩個頻繁項集和他們的支持度即：C=a1,a2, .a100：1，a1,a2,.a50:2.只有一個極大頻繁項集M=a1,a2, .a100:1。注

6、意，我們不能斷言a1,a2,.a50是極大頻繁項集，因為它有一個頻繁的超集a1,a2, .a100。閉的頻繁項集的集合包含了頻繁項集的完整信息。例YX 可以從C推出：（1）a2,a45:2,是因為a2,a45是a1,a2,.a50:2的子集(2)a8,a55:1,因為a8,a55不是a1,a2,.a50:2的子集，而是a1,a2, .a100：1的子集。然而，從極大頻繁項集只能斷言兩個集合a2,a45，a8,a55是頻繁的，但不能推斷它們的實際支持度計數(shù)。6.2頻繁項集挖掘方法 6.2.1 Apriori 算法：通過限制候選產(chǎn)生發(fā)算法：通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集現(xiàn)頻繁項集 Apriori算法

7、算法使用一種稱為逐層搜索的迭代方法，其中k項集用于探索（k+1）項集。首先，通過每一項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項的集合，記為L1；然后，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此進行下去，直到不能再找到頻繁K項集。找出每個LK需要一次數(shù)據(jù)庫的完整掃描。 為了提高頻繁項集逐層產(chǎn)生的效率，一種稱為先驗性質(zhì)先驗性質(zhì)的重要性質(zhì)用于壓縮搜索空間。 先驗性質(zhì)：先驗性質(zhì)：頻繁項集的所有非空子集也一定是頻繁的。 反單調(diào)性：如果一個集合不能通過測試，則它的所有超集也不能通過相同的測試。 使用先驗性質(zhì)的步驟：鏈接步和剪枝步。6.2.2由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則 根據(jù)公式產(chǎn)生關(guān)聯(lián)規(guī)則

8、對于每個頻繁項集l，產(chǎn)生所有的非空子集 對于l的每個非空子集s，如果 則輸出規(guī)則”s(l-s)” 例6.4)(sup)(sup)/()(AportcountBAportcountBAPBAconfidenceconfsportcounttportcountmin)(sup)(sup6.2.3提高Apriori算法的方法散列項集計數(shù)散列項集計數(shù)：一種基于散列的技術(shù)可以用于壓縮候選K項集的集合Ck。事務壓縮事務壓縮：不包含任何頻繁k項集的事務不可能包含任何頻繁（k+1）項集。劃分劃分：可以使用劃分技術(shù)，它只需要兩次數(shù)據(jù)庫掃描，就能挖掘頻繁項集。它包括兩個階段（1）把事務劃分成n個非重疊的分區(qū)，對每

9、個分區(qū)找出局部頻繁項集。（2）評估每個候選的實際支持度，以確定全局頻繁項集。抽樣抽樣：選取給定數(shù)據(jù)庫D的隨機樣本S，然后在S而不是在D中搜索頻繁項集。動態(tài)項集計數(shù)動態(tài)項集計數(shù)：動態(tài)項集計數(shù)技術(shù)將數(shù)據(jù)庫劃分為用開始點標記的塊。6.2.4挖掘頻繁項集的模式增長方法 頻繁模式增長頻繁模式增長：首先，將代表頻繁項集的數(shù)據(jù)庫劃分成一棵頻繁模式樹，該樹仍保留項集的關(guān)聯(lián)信息。然后，把這種壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫，每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或“模式段”，并分別挖掘每個條件數(shù)據(jù)庫。6.2.5使用垂直數(shù)據(jù)格式挖掘頻繁項集 Apriori算法和FP-growth算法都從TID項集格式的事務集中挖掘頻繁模式，

10、其中TID是事務標識符，而itemset是事務TID中購買的商品。這種數(shù)據(jù)格式稱為水平數(shù)據(jù)格式水平數(shù)據(jù)格式?；蛘?，數(shù)據(jù)也可以用項-TID集格式表示，其中item是項的名稱，而TID-set是包含item的事務的標識符的集合，稱為垂直數(shù)據(jù)格垂直數(shù)據(jù)格式。例式。例6.66.2.6挖掘閉模式和極大模式 如何挖掘閉模式項集：首先挖掘頻繁項集的完全集，然后刪除這樣的頻繁項集，它們是某個頻繁項集的真子集，并且具有相同支持度。然而，這種開銷太大。 一種推薦的方法是在挖掘的過程中直接搜索閉頻繁項集。這要求在挖掘過程中，一旦識別閉項集就盡快對搜索空間進行剪枝。剪枝包括如下策略： 項合并項合并：如果包含頻繁項集X

11、的每個事物都包含項集Y，但不包含Y的任何真超集，則 形成一個閉頻繁項集，并且不必再搜索包含X但不包含Y的任何項集。 子項集剪枝子項集剪枝：如果頻繁項集X是一個已經(jīng)發(fā)現(xiàn)的閉頻繁項集Y的真子集，并且support-count（X）=support-count（Y），則X和Y在集合枚舉樹中的所有后代都不可能是閉頻繁項集，因此可以剪枝。 項跳過項跳過：在深度優(yōu)化挖掘閉項集時，每一層都有一個與頭表和投影數(shù)據(jù)庫相關(guān)聯(lián)的前綴項集X。如果一個局部頻繁項集p在不同層的多個頭表中都具有相同的支持度，則可以將p從較高頭表中剪裁掉XUY6.3哪些模式是有趣的：模式評估方法 6.3.1強規(guī)則不一定是有趣的 例6.76.

12、3.2從關(guān)聯(lián)分析到相關(guān)分析 相關(guān)規(guī)則相關(guān)規(guī)則不僅用支持度和置信度，而且還用項集A和B之間的相關(guān)性度量。用許多不同的相關(guān)性度量可供選擇。提升度提升度是種簡單的相關(guān)性度量定義：,supncorrelatioconfidentportBA)sup(/ )()(/ )/()()()(),(BBAconfBPABPBPAPBAPBAlift如果（6.8）式的值小于1，則A與B是負相關(guān)如果（6.8）式的值大于1，則A與B是正相關(guān)如果（6.8）式的值等于1，則A與B是獨立沒有相關(guān)性例6.8 進行相關(guān)分析例6.926.3.3模式評估度量比較 全置信度定義 最大置信度定義 Kulczynski度量定義 余弦度量

13、定義)/(),/(min)sup(),maxsup()sup(),(_ABPBAPBABABAconfall)/(),/(max),(max_ABPBAPBAconf)/()/()sup()sup()sup()()()(),(cosABPBAPBABABPAPBAPBAine)/()/(21),(ABPBAPBAKulc 例6.10零事務零事務是不包含任何考察項集的事務。對于指示有趣的模式聯(lián)系，全置信度，最大置信度，Kulczynski度量，余弦度量哪個更好？我們引入不平衡比不平衡比定義如果A和B兩個方向的蘊含相同，則IR(A,B)=0，否則兩者之差越大，不平衡比就越大。例6.11)sup()

14、sup()sup()sup()sup(),(BABABABAIR多維，多層空間中的模式挖掘 7.2.1多層關(guān)聯(lián)規(guī)則多層關(guān)聯(lián)規(guī)則：在多個抽象的數(shù)據(jù)上挖掘產(chǎn)生，的關(guān)聯(lián)規(guī)則。在支持度-置信度框架下，使用概念分層可以有效地挖掘多層關(guān)聯(lián)規(guī)則，一般而言，可以采取自頂向下，由概念1層開始，向下到較低的，更特定的概念層，在每一個概念層積累計數(shù)，計算頻繁項集，直到不能再找到頻繁項集。 一致支持度一致支持度：在抽象層上挖掘時，使用相同的最小支持度閾值。使用此方法比較簡單，用戶只需要指定一個最小的支持度閾值。選擇這個支持度閾值就會有一些缺陷，較低抽象層的項不大可能像較高層那樣頻繁出現(xiàn)。如果最小支持度閾值設(shè)置太高，則

15、可能錯失在較低抽象層中出現(xiàn)的有意義的關(guān)聯(lián)；如果最小支持度閾值設(shè)置太低則可能會產(chǎn)生出現(xiàn)在較高抽象層的無趣的關(guān)聯(lián)。我們就引出下一種方法 在較低層使用遞減的最小支持度在較低層使用遞減的最小支持度：每個抽象層由它自己的最小支持度閾值。抽象層越低，對應的閾值就越小 使用基于項基于分組的最小支持度：由于用戶或?qū)＜彝ǔＧ宄切┙M比其他組更重要，在挖掘多層規(guī)則時，有時更希望建立用戶指定基于項或基于分組的最小支持度閾值。 7.2.2挖掘多維關(guān)聯(lián)規(guī)則挖掘多維關(guān)聯(lián)規(guī)則 單維或維內(nèi)關(guān)聯(lián)規(guī)則：單維或維內(nèi)關(guān)聯(lián)規(guī)則：單個謂詞的多次出現(xiàn)。 例 )int_ ,()_ ,(erprHPXbuyscameradigitalXbuy

16、s 多維關(guān)聯(lián)規(guī)則：涉及兩個或多個維或謂詞的關(guān)聯(lián)規(guī)則。例 規(guī)則包括三個謂詞，每個謂詞在規(guī)則中只出現(xiàn)一次，稱為不重復謂詞，具有不重復謂詞的關(guān)聯(lián)稱為維間關(guān)聯(lián)規(guī)則；如果包含某些謂詞的重復出現(xiàn)，稱為混合維關(guān)聯(lián)規(guī)則例) ,() ,() 29.20 ,(laptopXbuysstudentXoccupationXage) int ,() ,() 29.20 ,(erHPprXbuyslaptopXbuysXage 數(shù)據(jù)庫屬性可能是標稱的或是量化的。 標稱屬性的值是“事物的名稱”，標稱屬性具有有限多個可能值，值之間無序。例：（occupation,brand,color） 量化屬性是數(shù)值的，并在值之間具有一個

17、穩(wěn)序。例：（age,income,price）。根據(jù)量化屬性的處理，挖掘多維關(guān)聯(lián)規(guī)則的技術(shù)可以分為兩種方法：（一）使用預先定義的概念分層對量化屬性離散化。這種離散化在挖掘之前進行。例：可以使用income的概念定義，用區(qū)間“0.20k”,“21.30k”替換原來屬性的值。離散化的數(shù)值屬性具有區(qū)間標號，可以想標稱屬性一樣處理，我們稱這種方法為使用量化屬性的靜態(tài)離散化挖掘多維關(guān)聯(lián)規(guī)則。 （二）根據(jù)數(shù)據(jù)分布將量化屬性離散化或聚類到“箱”。離散化的過程是動態(tài)的，以滿足某種挖掘標準，如最大化所挖掘的置信度。由于該策略將數(shù)值屬性的值處理成數(shù)量，而不是預先定義的區(qū)間或類別，所以由這種方法挖掘的關(guān)聯(lián)規(guī)則稱為（

18、動態(tài)）量化關(guān)聯(lián)規(guī)則。7.2.3挖掘量化關(guān)聯(lián)規(guī)則 我們介紹三種方法：（1）數(shù)據(jù)立方體方法）數(shù)據(jù)立方體方法（2）基于聚類的方法（）基于聚類的方法（3）揭示異常行為）揭示異常行為的統(tǒng)計方法的統(tǒng)計方法 （1）量化關(guān)聯(lián)規(guī)則的基于數(shù)據(jù)立方體挖掘量化關(guān)聯(lián)規(guī)則的基于數(shù)據(jù)立方體挖掘數(shù)據(jù)立方體非常適合挖掘多維關(guān)聯(lián)規(guī)則，它們在多維空間儲存聚類信息，這對于計算多維關(guān)聯(lián)規(guī)則的支持度和置信度是基本的。如圖7.5 （2）挖掘基于聚類的化關(guān)聯(lián)規(guī)則挖掘基于聚類的化關(guān)聯(lián)規(guī)則介紹兩種發(fā)現(xiàn)量化關(guān)聯(lián)規(guī)則一種是自頂向下的聚類方法另一種是自底向上的聚類方法。自頂向下的聚類方法自頂向下的聚類方法對于每個量化維，可以使用一種標準的聚類算法，發(fā)現(xiàn)該維上滿足最小支持度閾值的簇。對于每個這樣的簇，我們考察該簇與另一維的一個簇或標稱屬性值組合生成的二維空間，看這以組合是否滿足最小支持度閾值。如果滿足，則繼續(xù)在該二維區(qū)域搜索簇，并繼續(xù)考察更高維空間。 自底向上的聚類方法自底向上的聚類方法發(fā)現(xiàn)基于聚類的頻繁模式的自底向上方法先在高維空間聚類，形成支持度滿足最小支持度閾值的簇，然后投影并合并較少維組合上的簇。然后，對高維數(shù)據(jù)集，發(fā)現(xiàn)高維聚類本身就是一個困難問題。因此這種方法