第四講數據挖掘概述與關聯(lián)規(guī)則(2013)

1、數據挖掘入門(r mn)什么激發(fā)了數據挖掘，為什么它是重要的？什么是數據挖掘？在何種數據上進行(jnxng)數據挖掘？數據挖掘的功能幾種較為流行的數據挖掘技術12022/7/19共六十五頁1、什么激發(fā)(jf)了數據挖掘，為什么它是重要的？數據爆炸性的增長：從兆字節(jié)terabytes 到千兆字節(jié)petabytes。多種海量數據源商業(yè): 網絡, 電子商務, 交易, 股票, 科學: 遙感數據, 生物信息學, 科學模擬, 社會各個角落: 新聞, 數字影像, 視頻， “我們(w men)被信息淹沒卻信息貧乏!” “需要是發(fā)明之母” 數據挖掘海量數據庫的自動化分析。22022/7/19共六十五頁32、什么

2、(shn me)是數據挖掘?數據挖掘（從數據中發(fā)現(fxin)知識） 數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。2022/7/19共六十五頁7/19/20224數據挖掘和商務(shngw)智能Increasing potentialto supportbusiness decisionsEnd UserBusiness Analyst DataAnalystDBADecision MakingData PresentationVisualization TechniquesData MiningInfo

3、rmation DiscoveryData ExplorationStatistical Summary, Querying, and ReportingData Preprocessing/Integration, Data WarehousesData SourcesPaper, Files, Web documents, Scientific experiments, Database Systems數據庫管理員OLAP商務智能通常被理解為將企業(yè)中現有(xin yu)的數據轉化為知識，幫助企業(yè)做出明智的業(yè)務經營決策的工具。一般由數據倉庫、聯(lián)機分析處理、數據挖掘、數據備份和恢復等部分組成。

4、共六十五頁數據挖掘：多種學科(xuk)的交叉5Data MiningDatabase TechnologyStatisticsMachineLearningPatternRecognitionAlgorithmOtherDisciplinesVisualization2022/7/19共六十五頁6、數據挖掘的功能(gngnng)關聯(lián)分析(fnx)分類和預測聚類異常值探測序列模式挖掘62022/7/19共六十五頁關聯(lián)分析是用于挖掘、發(fā)現大量數據(shj)中項集之間存在的、重要的、有趣的知識。若兩個或多個變量的取值之間存在某種規(guī)律性，就稱為關聯(lián)。在不知道關聯(lián)函數或關聯(lián)函數不確定的情況下，為了反映所

5、發(fā)現規(guī)則的有用性和確定性，關聯(lián)分析生成的規(guī)則都要滿足最小支持度閾值和最小置信度閾值。7關聯(lián)(gunlin)分析2022/7/19共六十五頁關聯(lián)分析(fnx)的應用：比 如 人 壽 保 險。 保 險 公 司 在 接 受 保 險 前， 往 往 需 要 記 錄 投 保 人 詳 盡 的 信 息， 有 時 還 要 到 醫(yī) 院 做 身 體 檢 查。 保 單 上 記 錄 有 投 保 人 的 年 齡、 性 別、 健 康 狀 況、 工 作 單 位、 工 作 地 址、 工 資 水 平 等。通 過 分 析 這 些 數 據， 可 以 得 到 類 似 以 下 這 樣 的 關 聯(lián) 規(guī) 則： 年 齡 在40 歲 以 上，

6、工 作 在A 區(qū) 的 投 保 人 當 中， 有45 的 人 曾 經 向 保 險 公 司 索 賠 過。 在 這 條 規(guī) 則 中，“ 年 齡 在40 歲 以 上”“ 工 作 在A 區(qū)” “向 保 險 公 司 索 賠 過” 可 以 看 出 來，A 區(qū) 可 能 污 染 比 較 嚴 重， 環(huán) 境 比 較 差， 導 致 工 作 在 該 區(qū) 的 人 健 康 狀 況 不 好， 索 賠 率 也 相 對 比 較 高。2022/7/198共六十五頁分類(fn li)和預測分類是對一個類別進行描述及概括相關特征，并提取出描述重要數據類的模型。數據挖掘中的分類方法很多，主要有決策樹和決策規(guī)則、貝葉斯網絡、神經網絡以及遺

7、傳算法等。預測是通過(tnggu)建立連續(xù)值函數模型達到預測未來的數據趨勢。預測的方法主要有回歸分析、時間序列分析等。各種分類模型也可以預測，但主要是預測分類標號。92022/7/19共六十五頁聚類聚類是在要劃分的類未知的情況下，將數據庫中的記錄劃分為多個類或簇，使得同類內的對象之間具有較高的相似度，不同類間的差異較大。它是概念描述和偏差分析(fnx)的先決條件。數據挖掘中的聚類方法有劃分方法、層次的方法、基于密度的方法、基于網格的方法以及基于模型的方法等。102022/7/19共六十五頁異常(ychng)值探測異常值指的是數據庫中不符合數據一般模型的數據對象。從數據庫中探測異常值很有意義，因

8、為它們本身可能隱藏著重要的信息，比正常的數據更有用，忽略或刪除它們都會導致信息的丟失。例如(lr)，發(fā)現金融和保險領域的欺詐行為、稅款的脫逃、通信費用的惡意欠費、網絡中的黑客入侵、追尋極低或極高收入者的消費行為以及對多種治療方式不尋常反映的發(fā)現等。112022/7/19共六十五頁序列(xli)模式挖掘序列模式挖掘是指挖掘相對時間或其他序列出現頻率高的規(guī)律或趨勢，并建模。這里的序列一般(ybn)指時間序列數據庫和序列數據庫（Web日志分析和DNA分析）。在許多行業(yè)產生的數據庫都是時間序列數據庫，例如，商業(yè)交易、電信部門、天氣數據等等，因此，序列模式的挖掘是非常有意義的。122022/7/19共六

9、十五頁序列分析和關聯(lián)規(guī)則的相似之處在于，它們所用的樣本數據中，每一個(y )樣本都包含了一個(y )項集或狀態(tài)集合。其不同之處在于序列分析研究的是項集(或狀態(tài))間的轉換，而關聯(lián)規(guī)則模型研究的是項集之間的相關性。在序列分析模型中，先購買計算機再購買音箱，和先購買音箱再購買計算機是兩種不同的序列。而在關聯(lián)規(guī)則中這兩種行為都表達了一個同樣的項集計算機，音箱。2022/7/1913共六十五頁14決策樹聚類時間序列關聯(lián)規(guī)則貝葉斯分類類神經網絡羅吉斯回歸線性回歸(hugu)文本(wnbn)數據挖掘7、幾種數據挖掘技術2022/7/19共六十五頁算法(sun f)與任務對應共六十五頁數據挖掘的任務(rn w

10、u)：分類：基于一個可預測屬性(shxng)把事例分成多個類。典型的分類算法包括決策樹算法、神經網絡算法和貝葉斯算法聚類：基于一組屬性對事例進行分組，是一種無監(jiān)督的數據挖掘任務，沒有一個屬性用于指導模型的構建過程?；貧w：類似于分類任務，最大的區(qū)別在回歸任務中可預測的屬性是連續(xù)的。線性回歸和邏輯回歸是最常用的回歸算法。其他的回歸分類技術包括回歸樹和神經網絡關聯(lián)：也稱為購物籃分析。用于確定一組項集和規(guī)則。預測：預測技術處理一般的趨勢分析、周期分析和噪聲過濾。常用的時間序列技術是ARIMA，它代表AutoRegressive Integrated Moving Average模型序列分析：用來發(fā)現離

11、散序列中的模式。序列分析的是狀態(tài)的轉移，關聯(lián)模型認為客戶購物車中的每一個商品都是平等和相互獨立的。偏差分析：是為了找出一些特殊事例。如信用卡欺詐等共六十五頁數據挖掘模型：可以認為數據挖掘模型（或者簡稱挖掘模型）是一個關系表。他包括鍵列、輸入列和可預測列。一個模型的設定與挖掘算法有關，模型由該數據挖掘算法訓練。通過使用指定的挖掘算法和適當的算法參數值，訓練一個挖掘模型就是在訓練數據集中發(fā)現模式。在對模型進行訓練之后，數據挖掘模型講存儲模式，這些模式是關于某個數據集的，并且這些模式是由數據挖掘算法發(fā)現。如果說關系表是一個存儲記錄的容器(rngq)，那么數據挖掘模型就是一個存儲模式的容器(rngq)

12、。共六十五頁數據挖掘的三個步驟：(1)建立數據挖掘模型（DMM）；(2)利用已用數據和挖掘算法培訓挖掘模型；(3)預測查詢。數據挖掘模型從某種意義上可以被視為一個關系(gun x)表，它包含一些不同數據類型的列，分別為輸入列和預測列。共六十五頁共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘關聯(lián)規(guī)則挖掘發(fā)現大量數據(shj)中項集之間有趣的關聯(lián)或相關聯(lián)系。隨著大量數據不停地收集和存儲，人們對于從數據庫中挖掘關聯(lián)規(guī)則越來越感興趣。從大量商業(yè)事務記錄中發(fā)現有趣的關聯(lián)關系，可以幫助許多商務決策的制定，如分類設計、交叉購物和促銷分析等。2共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘如何從事務(shw)

13、DB或關系DB的大量數據中挖掘出關聯(lián)規(guī)則知識？什么樣的關聯(lián)規(guī)則才是最有意義的？如何才能使挖掘過程盡快發(fā)現有價值的關聯(lián)規(guī)則知識？這就是本章要討論的內容。3共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘1. 購物籃分析(fnx)購物籃分析是關聯(lián)規(guī)則挖掘的最初形式。假定作為某商店經理，你想更加了解你的顧客的購物習慣。例如：“顧客多半會在一次購物時同時購買什么商品組或集合？”，為解答這個問題，可以在商店顧客事務零售數據上運行購物籃分析。分析的結果可用于市場規(guī)劃、廣告策劃和分類設計。4共六十五頁54.1 關聯(lián)(gunlin)規(guī)則挖掘購物籃分析(fnx)若設商店中所有銷售商品為一個集合，則每個商品均為一個

14、布爾變量，表示該商品是否被(一個)顧客購買。因此每個購物籃就可以用一個布爾向量表示。分析相應布爾向量，得到反映商品頻繁關聯(lián)或同時購買的購買模式，并可用關聯(lián)規(guī)則的形式表示模式。例如，購買計算機也趨向于同時購買財務管理軟件可用以下關聯(lián)規(guī)則表示：共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘購物籃分析(fnx)computer = financial _ management _ softwaresupport = 2%, confidence = 60%關聯(lián)規(guī)則的支持度(support)2% 表示：分析中的全部事務的2% 同時購買計算機和財務管理軟件。關聯(lián)規(guī)則的置信度(confidence)60%

15、 表示：購買計算機的顧客60% 也購買財務管理軟件。6共六十五頁規(guī)則的支持度和置信度是兩個規(guī)則興趣度量值，它們分別表示發(fā)現規(guī)則的有用性和確定性規(guī)則A = B在事務級中D中成立，具有支持度s，其中s是D中事務包含（即A和B二者）的百分比，它是概率p(AU B)關聯(lián)模式(msh)的支持度是模式(msh)為真的任務相關的元組（或事務）所占的百分比。對于關聯(lián)規(guī)則 A= B（其中A和B是項目的集合），支持度定義為：共六十五頁規(guī)則(guz)A = B在事務集中具有置信度c，其中D中包含A的事務同時也包含B的百分比是c。這是條件概率P ( B | A)共六十五頁4.1 關聯(lián)規(guī)則挖掘基本概念【例1 】任務相關

16、數據由某商店(shngdin)計算機部購買物品的事務數組成，一個置信度為80% 的關聯(lián)規(guī)則：buys ( X , “ computer” ) = buys ( X , “ software ” )意味著買計算機的顧客(gk)80% 也買軟件。10共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘基本概念【例2 】例1中一個支持度為30% 的關聯(lián)規(guī)則，意味著計算機部的所有顧客的30%,同時(tngsh)購買了計算機和軟件。支持度和置信度是兩個興趣度度量,分別反映發(fā)現規(guī)則的有用性和確定性。支持度?。阂?guī)則使用面窄置信度小：規(guī)則無意義12共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘基本概念滿足最小支持度閾值和

17、最小置信度閾值的關聯(lián)規(guī)則被認為是有趣(yuq)的。閾值由用戶或專家設定。強規(guī)則：同時滿足用戶定義的最小支持度閾值（min_sup）和最小置信度閾值(min_conf)的規(guī)則稱為強規(guī)則。為方便計，用0% 和100%之間的值表示支持度和置信度。13共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘基本概念項集的頻率：即包含項集的事務數，也稱為項集的支持計數(support_count)。如果項集的出現頻率大于或等于(dngy)min_sup與D中事務總數的乘積，就稱該項集滿足最小支持度min_sup 。頻繁項集：滿足最小支持度的項集稱為頻繁項集。頻繁k-項集的集合通常記作Lk。14共六十五頁4.1 關聯(lián)(g

18、unlin)規(guī)則挖掘基本概念關聯(lián)規(guī)則挖掘包含兩個(lin )步驟：1）找出所有頻繁項集：根據定義，這些項集的頻繁性至少和預定義的最小支持計數一樣。2）由頻繁項集產生強關聯(lián)規(guī)則：根據定義，這些規(guī)則必須滿足最小支持度和最小置信度。15共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘3.關聯(lián)(gunlin)規(guī)則挖掘分類根據不同的標準，關聯(lián)規(guī)則可以分成若干類型：(1)根據規(guī)則所處理的值的類型，關聯(lián)規(guī)則可以分為布爾的和量化的如果規(guī)則考慮的關聯(lián)是項的在與不在，則它是布爾關聯(lián)規(guī)則。例如，由購物籃分析得到的就是布爾關聯(lián)規(guī)則。16共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘關聯(lián)規(guī)則(guz)挖掘分類如果規(guī)則描述的是量化的項

19、或屬性之間的關聯(lián)，則它是量化關聯(lián)規(guī)則。在這種規(guī)則中，項或屬性的量化值劃分為區(qū)間。例如，下面的規(guī)則就是量化關聯(lián)規(guī)則，其中X是代表顧客的變量。age ( X，“31 -35 ”) income ( X， 5萬 - 8萬)= buys ( X， computer )注：量化屬性age和income已離散化。17共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘關聯(lián)規(guī)則(guz)挖掘分類(2)根據規(guī)則中數據涉及的維，關聯(lián)規(guī)則可以分為單維的和多維的如果關聯(lián)規(guī)則中的每個項或屬性只涉及一個維，則它是單維關聯(lián)規(guī)則。下面的規(guī)則buys(X , “computer”) = buys(X , “software”)由于

20、只涉及一個維(屬性buys),因此它是一個單維關聯(lián)規(guī)則。18共六十五頁4.1 關聯(lián)(gunlin)規(guī)則挖掘關聯(lián)規(guī)則挖掘(wju)分類如果規(guī)則涉及兩個或多個維，則它是多維關聯(lián)規(guī)則。下面的規(guī)則age ( X，31-35 ) income ( X，5萬 - 8萬)= buys ( X，computer )涉及三個維age、income和buys，它是一個多維關聯(lián)規(guī)則。19共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘關聯(lián)規(guī)則挖掘(wju)分類單維關聯(lián)規(guī)則展示的是屬性內聯(lián)系，即同一個屬性或維內的關聯(lián)；多維關聯(lián)規(guī)則展示的是屬性間聯(lián)系，即屬性/維之間的關聯(lián)。20共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘關聯(lián)規(guī)則(

21、guz)挖掘分類(3)根據規(guī)則涉及的抽象層，關聯(lián)規(guī)則可以分為單層的和多層的有些挖掘關聯(lián)規(guī)則的方法可以在不同的抽象層發(fā)現關聯(lián)規(guī)則。例如，假定挖掘的關聯(lián)規(guī)則集包含下面規(guī)則：age ( X, 31 - 35 ) = buys ( X, notebook_computer )age ( X, 31 - 35 ) = buys ( X, computer )21共六十五頁4.1 關聯(lián)規(guī)則(guz)挖掘關聯(lián)(gunlin)規(guī)則挖掘分類在上面的規(guī)則集中，購買的商品涉及不同的抽象層。則稱所挖掘的規(guī)則集由多層關聯(lián)規(guī)則組成。反之，若在給定的規(guī)則集中，規(guī)則不涉及不同抽象層的項或屬性，則該集合包含單層關聯(lián)規(guī)則。(4)

22、根據對關聯(lián)挖掘的不同擴充，關聯(lián)挖掘可以擴充到相關分析，最大模式，頻繁閉項集的挖掘。22共六十五頁4.2 挖掘單維布爾關聯(lián)(gunlin)規(guī)則本節(jié)介紹(jisho)最簡單關聯(lián)規(guī)則(單維、單層、布爾關聯(lián)規(guī)則)的挖掘方法。購物籃分析就是挖掘這種關聯(lián)規(guī)則。Apriori算法是一種最有影響的挖掘布爾關聯(lián)規(guī)則頻繁項集的基本算法。24共六十五頁Apriori算法(sun f)25共六十五頁4.2 挖掘單維布爾關聯(lián)(gunlin)規(guī)則1.Apriori 算法(sun f)Apriori算法是根據有關頻繁項集性質的先驗知識而命名的。該算法使用一種逐層搜索的迭代方法，利用k-項集探索(k+1)-項集。具體做法：首

23、先找出頻繁1-項集的集合，記為L1 ；再用L1找頻繁2-項集的集合L2 ；再用L2找L3 如此下去，直到不能找到頻繁k-項集為止。找每個Lk需要一次數據庫掃描。26共六十五頁4.2 挖掘(wju)單維布爾關聯(lián)規(guī)則Apriori 算法(sun f)Apriori算法的有效性,在于它利用了一個非常重要的原理,即Apriori性質。Apriori性質：如果一個項集是頻繁的，則這個項集的任意一個非空子集都是頻繁的。它基于如下觀察：如果項集I不滿足最小支持度閾值min_sup，則I 不是頻繁的。如果增加項i到I，則結果項集 I Ui不可能比I更頻繁出現。因此，也不是頻繁的。27共六十五頁4.2 挖掘單維

24、布爾關聯(lián)(gunlin)規(guī)則Apriori 算法該性質屬于一種特殊的分類，也稱作反單調性。意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。反單調性能迅速剪枝，提高(t go)搜索頻繁項集的處理效率。下面我們來看Apriori算法是如何利用反單調性，用Lk-1尋找Lk 。28共六十五頁4.2 挖掘單維布爾關聯(lián)規(guī)則(guz)Apriori 算法整個過程由連接和剪枝兩步組成，即：連接步產生(chnshng)候選項集剪枝步確定頻繁項集(1)連接步為找Lk，可通過Lk-1與自己連接，產生一個候選k-項集的集合，該候選項集的集合記作Ck 。29共六十五頁4.2 挖掘單維布爾關聯(lián)(gun

25、lin)規(guī)則Apriori 算法設l1和l2是Lk-1中的項集，記號(j ho)lij表示li的第j項。為方便計，假定事務或項集中的項按字典次序排序。執(zhí)行連接 Lk-1 Lk-1 ， 其中Lk-1的元素是可連接的，如果它們前(k-2 )個項相同。30共六十五頁4.2 挖掘單維布爾關聯(lián)(gunlin)規(guī)則Apriori 算法即，Lk-1的元素(yun s)l1和l2是可連接的，若：（ l11 = l21 l1 2 = l2 2 l1k-2 = l2k-2 l1k-1 l2k-1 ）而條件（l1k-1 l2k-1）可確保不產生重復的項集。31共六十五頁4.2 挖掘(wju)單維布爾關聯(lián)規(guī)則Apri

26、ori 算法(2)剪枝(jin zh)步Ck是Lk的超集，即它的成員不一定都是頻繁項集，但所有的頻繁k-項集都包含在Ck中。掃描數據庫，確定Ck中每個候選項集的計數，從而確定Lk。然而， Ck可能很大，這樣所涉及的計算量就很大。32共六十五頁4.2 挖掘(wju)單維布爾關聯(lián)規(guī)則Apriori 算法為了壓縮(y su)Ck，可利用Apriori性質：任何非頻繁的(k-1)-項集都不可能是頻繁k-項集的子集。因此，若一個候選k-項集的(k-1)-項子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除。33共六十五頁344.2 挖掘單維布爾關聯(lián)(gunlin)規(guī)則Apriori 算法

27、TID項ID的列表(li bio)【例3 】一個Apriori的具體例子，該例基于右圖某商店的事務DB。DB中有9個事務，Apriori假定事務中的項按字典次序存放。T100T200T300T400T500T600T700T800T900I1，I2，I5I2，I4I2，I3I1，I2，I4I1，I3I2，I3I1，I3I1，I2，I3，I5I1，I2，I3共六十五頁（1）在算法(sun f)的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法簡單地掃描所有的事務，對每個項的出現次數計數(j sh)。C1項集 支持度計數掃描D,對每個候選計數I1I2I3I4I56762235共六十五頁（2

28、）設最小支持計數為2，可以確定頻繁1-項集的集合L1 。它由具有最小支持度的候選(hu xun)1-項集組成。L1項集 支持度計數比較候選支持(zhch)度計數與最小支持度計數I1I2I3I4I56762236共六十五頁（3）為發(fā)現頻繁2-項集的集合L2 ，算法(sun f)使用 L1 L1 產生候選2-項集集合C2 。由L1產生(chnshng)候選C2C2項集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I537共六十五頁42（4）掃描D中事務，計算(j sun)C2中每個候選項集的支持計數。 C2項集I1，I2I1，I3I1，I4I1，I

29、5支持(zhch)度計數4412掃描D,對每個候選計數I2，I3I2，I4I2，I5I3，I4I3，I5201I4，I5038共六十五頁42（5）確定頻繁2-項集的集合L2 ，它由具有最小支持(zhch)度的C2中的候選2-項集組成。L2項集I1，I2支持(zhch)度計數4比較候選支持度計數與最小支持度計數I1，I3I1，I5I2，I3I2，I4I2，I542239共六十五頁（6）候選(hu xun)3-項集的集合C3 的產生如下： 連接(linji)： C3 = L2 L2 = I1,I2，I1,I3，I1,I5，I2,I3，I2,I4，I2,I5 I1,I2，I1,I3，I1,I5，I2

30、,I3，I2,I4，I2,I5 =I1,I2,I3，I1,I2,I5，I1,I3,I5，I1,I2,I4I2,I3,I4， I2,I3,I5，I2,I4,I540共六十五頁 利用(lyng)Apriori性質剪枝：頻繁項集的所有子集(z j)必須是頻繁的。存在候選項集，判斷其子集是否頻繁。I1,I2,I3的2-項子集是I1,I2，I1,I3和I2,I3,它們都是L2的元素。因此保留I1,I2,I3在C3中。I1,I2,I5的2-項子集是I1,I2，I1,I5和I2,I5,它們都是L2的元素。因此保留I1,I2,I5在C3中。I1,I3,I5的2-項子集是I1,I3，I1,I5和I3,I5,I3

31、,I5不是L2的元素，因而不是頻繁的，由C3中刪除I1,I3,I5。41共六十五頁42I2,I3,I4的2-項子集(z j)是I2,I3，I2,I4和I3,I4,其中I3,I4不是(b shi)L2的元素，因而不是頻繁的，由C3中刪除I2,I3,I4。I2,I3,I5的2-項子集是I2,I3，I2,I5和I3,I5,其中I3,I5不是L2的元素，因而不是頻繁的，由C3中刪除 I2,I3,I5。I2,I4,I5的2-項子集是I2,I4，I2,I5和I4,I5,其中I4,I5不是L2的元素，因而不是頻繁的，由C3中刪除I2,I4,I5 。共六十五頁43 這樣(zhyng)，剪枝后C3 = I1,I2,I3，I1,I2,I5。（7）掃描D中事務，以確定L3 ，它由C3中具有最小支持度的的候選3-項集組成。C3由L2產生(chnshng)候選C3C3項集I1，I2，I3I1，I2，I5掃描D,對每個候選計數項集I1，I2，I3I1，I2，I5支持度計數22共六十五頁（8）算法使用(shyng) L3 L3 產生候選4-項集的集合C4 。盡管連接產生結果 I1,I2,I3,I5,這個項集被剪去，因為它的子集I2,I3,I5不是頻繁的。則 C4 = ,因此算法終止，找出了所有的頻繁項集。L3比較候選(hu xun)支持度計數與最小支持度計數項集I