基于FP_Growth算法的關(guān)聯(lián)規(guī)則挖掘研究及應(yīng)用

馬瑞敏，吳海霞

(長(zhǎng)治學(xué)院 計(jì)算機(jī)系，山西 長(zhǎng)治 046011)

0 引言

隨著計(jì)算機(jī)技術(shù)、移動(dòng)互聯(lián)網(wǎng)與物聯(lián)網(wǎng)的高速發(fā)展，可供人們采集利用的數(shù)據(jù)越來(lái)越多，呈現(xiàn)爆炸式增長(zhǎng).大量的數(shù)據(jù)背后隱藏著許多重要的信息，如何對(duì)其進(jìn)行更高層次的分析，并轉(zhuǎn)換成有用的信息和知識(shí)，成為數(shù)據(jù)挖掘技術(shù)研究的主要內(nèi)容.關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的一個(gè)重要分支，其概念最早由美國(guó)科學(xué)家R.Agrawal等人于1993年提出，最初用于挖掘顧客交易數(shù)據(jù)庫(kù)中用戶購(gòu)買的商品之間內(nèi)在的隱含關(guān)系及關(guān)聯(lián)規(guī)則，從而為決策者提供決策支持.現(xiàn)在關(guān)聯(lián)規(guī)則挖掘不但在商業(yè)分析中得到了廣泛的應(yīng)用，在通信、金融、交通、健康醫(yī)療和Web用戶行為分析等領(lǐng)域也得到了廣泛應(yīng)用.

1 關(guān)聯(lián)規(guī)則及其抽象描述

關(guān)聯(lián)規(guī)則挖掘主要用于發(fā)現(xiàn)存在于數(shù)據(jù)庫(kù)中的項(xiàng)或?qū)傩蚤g的關(guān)聯(lián)關(guān)系.設(shè)I={I1,I2,…,Im}是項(xiàng)的集合，其中m表示項(xiàng)的數(shù)目.對(duì)于項(xiàng)集A，若A中含有的項(xiàng)數(shù)為k(k≤m)，則稱A為k-項(xiàng)集[1].D為數(shù)據(jù)庫(kù)事務(wù)的集合，用|D|表示事務(wù)集中事務(wù)的個(gè)數(shù).對(duì)于每個(gè)事務(wù)T有T={t1,t2,…,tm}，ti∈I，T≠?.關(guān)聯(lián)規(guī)則是形如A?B的蘊(yùn)涵式，其中A?I，B?I，A≠?，B≠?，并且A∩B=?.表示事務(wù)T在含有項(xiàng)集A的條件下，同時(shí)含有B的概率[2].用戶關(guān)心的關(guān)聯(lián)規(guī)則，可以用兩個(gè)標(biāo)準(zhǔn)來(lái)衡量：支持度和可信度.

1.1 支持度

支持度的意義在于度量項(xiàng)集在整個(gè)事務(wù)集中的重要性.我們?cè)诎l(fā)現(xiàn)規(guī)則時(shí)，總希望找到高概率出現(xiàn)的項(xiàng)集.單一項(xiàng)集的支持度表示該項(xiàng)集在事務(wù)集中出現(xiàn)的概率.即，

support(A)=P(A)=count(A)/|D|.

規(guī)則A?B的支持度，表示項(xiàng)集{A,B}在事務(wù)集中同時(shí)出現(xiàn)的概率.即，

support(A?B)=P(A∪B)=count(A∪B)/|D|.

最小支持度是項(xiàng)集的最小支持閾值，記為min_sup，代表了用戶關(guān)心的關(guān)聯(lián)規(guī)則的最低重要性[3].

1.2 置信度

置信度通常用來(lái)衡量規(guī)則的可信程度，表示在關(guān)聯(lián)規(guī)則的先決條件A發(fā)生的條件下，關(guān)聯(lián)結(jié)果B發(fā)生的概率[4].計(jì)算公式如下：

confidence(A?B)=P(B|A)=P(AB)/P(A)=
support(A∪B)/support(A)=count(A∪B)/count(A).

最小置信度是置信度的最低閾值，記為min_conf，代表關(guān)聯(lián)規(guī)則的最低可信度.

1.3 頻繁項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則

支持度不小于min_sup的項(xiàng)集稱為頻繁項(xiàng)集.如果規(guī)則A?B滿足support(A?B)〉=min_sup且confidence(A?B)〉=min_conf,則稱A?B為強(qiáng)關(guān)聯(lián)規(guī)則.min_sup和min_conf通常由用戶根據(jù)先驗(yàn)知識(shí)來(lái)設(shè)定.

2 關(guān)聯(lián)規(guī)則挖掘的相關(guān)算法及分析

關(guān)聯(lián)規(guī)則挖掘的目標(biāo)就是要找出所有的強(qiáng)關(guān)聯(lián)規(guī)則.挖掘過(guò)程主要分為兩步：

步驟1：找到所有不小于最小支持度閾值的規(guī)則，即所有頻繁項(xiàng)集；

步驟2：對(duì)頻繁項(xiàng)集進(jìn)行過(guò)濾，濾掉小于最小置信度的項(xiàng)集，找出強(qiáng)關(guān)聯(lián)規(guī)則.

步驟2只需根據(jù)步驟1找出的頻繁項(xiàng)集使用簡(jiǎn)單的計(jì)算就能得出，因此關(guān)聯(lián)規(guī)則挖掘算法的核心在于頻繁項(xiàng)集的挖掘.最簡(jiǎn)單的算法是窮舉所有的項(xiàng)集組合作為候選集，然后分別檢驗(yàn)支持度是否滿足預(yù)先設(shè)定的閾值.這種算法雖簡(jiǎn)單，但計(jì)算效率卻很低.隨著特征維度的增大，候選集數(shù)量會(huì)呈指數(shù)級(jí)增加；且對(duì)于每一個(gè)候選項(xiàng)集，都需要掃描數(shù)據(jù)集計(jì)算其支持度，當(dāng)數(shù)據(jù)量很大時(shí)，需要的計(jì)算量也很大[5].顯然這種暴力算法不是最好的選擇，因此人們致力于尋找更為高效的算法，其中FP_Growth算法是較為經(jīng)典的算法.

2.1 FP_Growth算法

FP_Growth算法是韓家煒等人于2000年提出的一個(gè)關(guān)聯(lián)規(guī)則挖掘算法.它設(shè)計(jì)了一種稱為頻繁模式樹(shù)(FP-tree)的數(shù)據(jù)結(jié)構(gòu)，將原始數(shù)據(jù)集進(jìn)行壓縮存儲(chǔ).樹(shù)的根結(jié)點(diǎn)為“null”，其余節(jié)點(diǎn)代表一個(gè)特征項(xiàng)及其支持度信息，每一個(gè)項(xiàng)集對(duì)應(yīng)樹(shù)上的一條路徑.為了更加快速地挖掘頻繁項(xiàng)集，F(xiàn)P-tree還包含一個(gè)兩列的頻繁項(xiàng)表.第一列是特征項(xiàng)名稱，按照特征項(xiàng)支持度降序排序.第二列存儲(chǔ)一個(gè)鏈表，將FP-tree樹(shù)中相同特征項(xiàng)的節(jié)點(diǎn)連接起來(lái).FP_Growth算法主要分為構(gòu)建FP-tree和基于FP-tree遞歸的挖掘頻繁項(xiàng)集兩個(gè)步驟[6].

FP-tree的構(gòu)建方法如表1所示.FP-tree構(gòu)建完成后，便可基于它來(lái)挖掘頻繁項(xiàng)集.分別以頻繁項(xiàng)表中的項(xiàng)作為后綴，構(gòu)造它的條件模式基，條件模式基是FP-tree中與該后綴一起出現(xiàn)的前綴路徑的集合.通過(guò)條件模式基構(gòu)造該項(xiàng)的條件FP-tree,并遞歸地在該樹(shù)上進(jìn)行挖掘.模式增長(zhǎng)通過(guò)后綴模式與條件FP-tree產(chǎn)生的頻繁項(xiàng)目連接實(shí)現(xiàn)[7].具體流程如圖1所示.

表1 FP-tree構(gòu)建算法

圖1 基于FP-tree挖掘頻繁項(xiàng)集流程圖

FP_Growth算法通過(guò)兩次遍歷原始數(shù)據(jù)集，將數(shù)據(jù)以FP-tree的形式進(jìn)行壓縮存儲(chǔ).后續(xù)頻繁項(xiàng)集的挖掘直接利用FP-tree，避免生成無(wú)用的候選項(xiàng)集，大大提高了效率.但該算法生成的是頻繁項(xiàng)集，而不是關(guān)聯(lián)規(guī)則.如要進(jìn)一步生成關(guān)聯(lián)規(guī)則，需根據(jù)頻繁項(xiàng)集生成候選關(guān)聯(lián)規(guī)則，然后通過(guò)最小置信度對(duì)關(guān)聯(lián)規(guī)則進(jìn)一步過(guò)濾，得到強(qiáng)關(guān)聯(lián)規(guī)則.

表2 商品交易數(shù)據(jù)集

2.2 FP_Growth算法實(shí)例演示

下面以商品交易數(shù)據(jù)集為例演示算法實(shí)現(xiàn)過(guò)程.該數(shù)據(jù)集中有6位顧客的購(gòu)買記錄,如表2所示，設(shè)定最小支持度為3.

步驟1：掃描數(shù)據(jù)集，構(gòu)建FP-tree.

a.第一次掃描數(shù)據(jù)集，得到頻繁1項(xiàng)集的集合，并按支持度降序排列.結(jié)果集記為：L1，即L1={{z:5}，{x:4}，{y:3}，{r:3}，{s:3}，{t:3}}.

b.創(chuàng)建FP-tree，構(gòu)建根結(jié)點(diǎn)，標(biāo)記為“null”,創(chuàng)建頻繁項(xiàng)表，將鏈表設(shè)置為空.

c.第二次掃描數(shù)據(jù)集，對(duì)每個(gè)事務(wù)中的項(xiàng)都按L1中的次序排序并濾掉不頻繁的項(xiàng).

加入第一個(gè)事務(wù)后FP-tree如圖2所示.依次加入其他事務(wù)后完整的FP-tree如圖3所示.

圖2 加入事務(wù)1圖3 最終FP-tree

步驟2：挖掘頻繁項(xiàng)集.

首先以t為后綴，找出它的條件模式基：{{z，x，y，s:2}，{z，x，y，r:1}}.使用這些條件模式基構(gòu)造t的條件FP- tree，它只包含單個(gè)路徑〈z:3，x:3，y:3〉，不包含s，r，因?yàn)檫@兩個(gè)項(xiàng)的支持度計(jì)數(shù)小于3.因此產(chǎn)生了以特征項(xiàng)t為后綴的所有頻繁模式.同理依次可以產(chǎn)生s，r，y，x，z的頻繁項(xiàng)集如表3所示.

表3 通過(guò)條件模式基挖掘FP- tree

3 FP_Growth算法在問(wèn)卷調(diào)查中的應(yīng)用

用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集來(lái)自于網(wǎng)站https://www.kaggle.com，主要針對(duì)大學(xué)生開(kāi)展的一項(xiàng)問(wèn)卷調(diào)查，收集年輕人愛(ài)好和生活習(xí)慣等方面的信息.調(diào)查問(wèn)卷共涉及1 010人關(guān)于150項(xiàng)問(wèn)題的調(diào)查，例如興趣愛(ài)好、消費(fèi)習(xí)慣、衛(wèi)生習(xí)慣、以及性別、身高、體重等個(gè)人基本信息.

3.1 數(shù)據(jù)預(yù)處理

FP_Growth算法只能處理布爾類型的數(shù)據(jù)，因此在進(jìn)行數(shù)據(jù)分析之前，首先要進(jìn)行預(yù)處理.

1.數(shù)據(jù)刪除.本案例收集到的問(wèn)卷中少量存在未填寫的項(xiàng)目，刪除將不會(huì)影響數(shù)據(jù)分析的結(jié)果，因此對(duì)存在缺失值的樣本進(jìn)行了刪除.

2.數(shù)據(jù)轉(zhuǎn)換.數(shù)據(jù)集中既有數(shù)值型數(shù)據(jù)又有字符型數(shù)據(jù),為了轉(zhuǎn)換成適合挖掘的形式，需要對(duì)屬性取值進(jìn)行處理.本案例中絕大多數(shù)特征的取值范圍根據(jù)學(xué)生的喜愛(ài)度分為五個(gè)等級(jí)，對(duì)于這類數(shù)據(jù)直接進(jìn)行二值化處理，設(shè)定閾值為3，當(dāng)特征值大于3時(shí)賦值為1否則為0.對(duì)于年齡、身高、體重等連續(xù)型特征變量，先進(jìn)行變量離散化，然后進(jìn)行特征編碼.對(duì)于字符型特征值，也使用特征編碼的方式進(jìn)行了處理.最終生成的新數(shù)據(jù)集屬性數(shù)量由150增加為175個(gè)，取值均為0或者1.

3.2 數(shù)據(jù)分析

表4 不同參數(shù)下的運(yùn)行結(jié)果

通過(guò)FP_Growth算法挖掘頻繁項(xiàng)集，當(dāng)設(shè)置不同支持度和置信度時(shí)，挖掘到的頻繁子集個(gè)數(shù)和生成關(guān)聯(lián)規(guī)則數(shù)目如表4所示.通過(guò)運(yùn)行結(jié)果可看出，當(dāng)最小支持度為0.8時(shí)，產(chǎn)生的頻繁子集個(gè)數(shù)為10，生成關(guān)聯(lián)規(guī)則的置信度都很高，均在0.9之上，因此最小置信度設(shè)置為0.6或0.8生成的規(guī)則數(shù)都是12條.置信度排在前三位的關(guān)聯(lián)規(guī)則分別為：

Confidence(看電影?聽(tīng)音樂(lè))=0.963

Confidence(與朋友玩?聽(tīng)音樂(lè))=0.96

Confidence(與朋友玩?看電影)=0.932

經(jīng)過(guò)分析，我們可以了解到學(xué)生普遍的生活狀態(tài)和興趣愛(ài)好.比如和朋友玩耍時(shí)選擇一起看電影、聽(tīng)音樂(lè)頻度較高；讀書(shū)、上網(wǎng)、戶外運(yùn)動(dòng)、社團(tuán)活動(dòng)等這些大學(xué)生活的重要組成部分伴隨出現(xiàn)的頻度也較高.此外還發(fā)現(xiàn)遵守約定、守時(shí)、愛(ài)護(hù)公物等一些好的生活習(xí)慣也是學(xué)生比較重視的.

4 結(jié)束語(yǔ)

本文對(duì)數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則算法進(jìn)行了研究，重點(diǎn)分析了利用FP_Growth算法構(gòu)建FP-tree和遞歸挖掘頻繁項(xiàng)集的過(guò)程，并將該算法應(yīng)用于學(xué)生興趣愛(ài)好的問(wèn)卷調(diào)查結(jié)果分析中.通過(guò)發(fā)現(xiàn)隱藏在數(shù)據(jù)中的關(guān)聯(lián)規(guī)則，可以幫助老師更深入準(zhǔn)確地了解學(xué)生的生活習(xí)慣，個(gè)性特點(diǎn)和興趣愛(ài)好，以便提供更好的生活服務(wù)和有針對(duì)性地開(kāi)展豐富多彩的文化活動(dòng)，營(yíng)造積極向上朝氣蓬勃的校園環(huán)境.