基于FP—GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法研究

陳寅

摘 要：互聯(lián)網(wǎng)世界的數(shù)據(jù)每年都在成倍增長，但是對用戶有用的信息卻好像在減少，用戶淹沒在數(shù)據(jù)的海洋中，雖然類似于Google這樣的搜索引擎可以幫用戶找到需要的信息，但是正確率和查全率都不盡如人意。數(shù)據(jù)挖掘是興起于20世紀(jì)90年代的一項(xiàng)用于決策支持的新技術(shù)。FP-GROWTH算法只進(jìn)行2次數(shù)據(jù)庫掃描。它不使用侯選集，直接壓縮數(shù)據(jù)庫成一個頻繁模式樹，最后通過這棵樹生成關(guān)聯(lián)規(guī)則。文章研究FP-GROWTH算法理論的同時實(shí)現(xiàn)了一個簡單算法演示的系統(tǒng)。系統(tǒng)包括算法的執(zhí)行，對數(shù)據(jù)庫的修改、查詢、刪除的操作。最后，對FP-GROWTH算法和Apriori算法進(jìn)行了比較。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；FP-GROWTH算法；候選集；頻繁模式樹

1 基于FP-GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法

1.1 FP-GROWTH算法的基本思想

FP-GROWTH算法采用歸納分散的策略，對數(shù)據(jù)庫進(jìn)行第一次掃描，把數(shù)據(jù)庫中的頻繁項(xiàng)集壓縮到一棵頻繁模式樹（FP-Tree），同時依然保留其中的關(guān)聯(lián)信息，隨后再將FP-Tree分化成一些條件數(shù)據(jù)庫，每個條件數(shù)據(jù)關(guān)聯(lián)一個頻繁項(xiàng)，然后再分別對這些條件庫進(jìn)行挖掘。FP-GROWTH算法核心思想如下所示：輸入事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出頻繁模式的完全集。FP-tree的產(chǎn)生可由下例進(jìn)行簡單的介紹[1-3]。

我們給出了一個簡單的數(shù)據(jù)集合{1，3，4}，{2，4，5}、{2，4，6}。先對數(shù)據(jù)庫進(jìn)行一次掃描，根據(jù)集合中項(xiàng)的出現(xiàn)頻率可以得出一個數(shù)據(jù)集合{4，2，1，3，5，6}（項(xiàng)的次序按出現(xiàn)頻率由高到低排列），可以把這個集合認(rèn)為是對數(shù)據(jù)庫掃描后進(jìn)行了一次整理，生成了一個新的數(shù)據(jù)庫。由這個集合按項(xiàng)出現(xiàn)的頻率生成FP-Tree。我們先讀取第一個集合，并按集合中項(xiàng)的出現(xiàn)頻率決定是否優(yōu)先插入，插入后該節(jié)點(diǎn)的計(jì)數(shù)加1，同樣的方法再插入第二個集合，如果集合中項(xiàng)與FP-Tree中已有的節(jié)點(diǎn)重復(fù)，那么該節(jié)點(diǎn)計(jì)數(shù)加1，如果不重復(fù)，插入該項(xiàng)并且該節(jié)點(diǎn)計(jì)數(shù)加1，重復(fù)上述操作直至完成所有項(xiàng)的插入。具體實(shí)現(xiàn)步驟如圖1所示[4-7]。

圖

1.2 基于FP-GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法的系統(tǒng)實(shí)現(xiàn)

1.2.1 算法實(shí)現(xiàn)環(huán)境

從上面的闡述中，可以了解到系統(tǒng)的實(shí)現(xiàn)采用了C++和SQL server，在這里我們對編譯環(huán)境進(jìn)行簡介，并說明它們的優(yōu)點(diǎn)。

Visual C++是一個功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C++1.0后，隨著其新版本的不斷問世，Visual C++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具[8]。

SQL Server 2000是為迅速提供可伸縮性電子商務(wù)、企業(yè)及數(shù)據(jù)倉庫解決方案而開發(fā)的完整數(shù)據(jù)庫與分析軟件產(chǎn)品。SQL SERVER 2000定位于Internet背景下的數(shù)據(jù)庫應(yīng)用，它為用戶的Web應(yīng)用提供了一款完善的數(shù)據(jù)管理和數(shù)據(jù)分析解決方案。同時SQL SERVER 2000還是Windows分布式網(wǎng)絡(luò)架構(gòu)（Distributed Internet Architecture，DNA）架構(gòu)的一個核心組件。它極大地縮短了用戶開發(fā)電子商務(wù)、數(shù)據(jù)倉庫應(yīng)用的時間。SQL SERVER 2000還提供對擴(kuò)展標(biāo)示語言支持（Extensible Markup Language，XML）和HTTP的全方位支持[9-10]。

1.2.2 系統(tǒng)功能設(shè)計(jì)

系統(tǒng)功能主要包括以下幾點(diǎn)：（1）對數(shù)據(jù)庫有基本的操作功能，如查詢、修改、刪除等操作。（2）采用C++來實(shí)現(xiàn)FP-GROWTH算法。（3）界面可視化[11-15]。

1.2.3 數(shù)據(jù)庫設(shè)計(jì)

首先我們需要挖掘商品之間的潛在關(guān)聯(lián)關(guān)系，那么必須知道商品的最基本的一些屬性，建立一個名叫shangpin的表，其中ID為主鍵，數(shù)據(jù)類型為varchar，長度為50.其中還包括了Name（商品名稱）；Pdate（生產(chǎn)日期）；Sdate（銷售時間）；Price（商品價格）[16]。具體設(shè)置如表1所示。

在執(zhí)行算法之后，人們真正感興趣的是顧客所購買的商品之間潛在的關(guān)聯(lián)規(guī)則，再建立一張名叫sale的表，在該表內(nèi)所有的購買項(xiàng)目生成了聯(lián)合主鍵item1代表了顧客購買的一件商品，以此類推item2，item3分別為購買的第二、三件商品，所有的項(xiàng)組成了顧客一次購買的商品所組成的集合。

1.2.4 系統(tǒng)界面設(shè)計(jì)

系統(tǒng)的界面，主要提供了數(shù)據(jù)庫的基本操作界面，F(xiàn)P-GROWTH算法的執(zhí)行界面，在進(jìn)入程序后會彈出用戶登入界面，用戶登入后，為方便用戶對系統(tǒng)進(jìn)行針對性的操作，筆者設(shè)計(jì)了工具選擇窗口。具體設(shè)計(jì)如圖2所示。

圖2 登入設(shè)計(jì)界面

登入界面包含了用戶名和密碼，可對用戶輸入的用戶名、密碼進(jìn)行驗(yàn)證。如果錯誤提示重新輸入，輸入錯誤次數(shù)超過3次時自動退出系統(tǒng)。

在數(shù)據(jù)庫的界面上人們能夠?qū)崿F(xiàn)數(shù)據(jù)的查詢、添加、修改、刪除等操作。界面中還包含了商品序列號、商品名稱、查詢方式等操作窗口（見圖3）。這些使得人們更能直觀地進(jìn)行使用。

在算法執(zhí)行界面里，人們可以對sale表進(jìn)行錄入操作，并提供最小支持度輸入窗口，使得用戶可以根據(jù)自己的需要對最小支持度進(jìn)行設(shè)置[17]，如圖4所示。

1.3 系統(tǒng)實(shí)現(xiàn)和結(jié)果分析

在本系統(tǒng)中，創(chuàng)建了一個簡單的登入界面，在界面里顯示了用戶名和密碼，如圖5所示。

輸入的用戶名和密碼正確后，可以選擇對數(shù)據(jù)庫進(jìn)行操作或者對FP-Tree算法進(jìn)行操作，這樣能方便地對整個程序進(jìn)行管理，也方便使用，如圖6所示。

1.3.1 數(shù)據(jù)庫相關(guān)界面endprint

進(jìn)入數(shù)據(jù)庫操作后程序自動彈出如圖7所示界面，在該界面上能夠?qū)崿F(xiàn)數(shù)據(jù)的查詢、插入、修改、刪除等操作。界面中還包含了現(xiàn)實(shí)窗口、序列現(xiàn)實(shí)口、生產(chǎn)日期、價格等。這些使得人們更能直觀地進(jìn)行使用。

以查詢?yōu)槔琒ecIo是按照商品屬性的第幾列來查詢，如ID對應(yīng)第一列，Name對應(yīng)第2列，以此類推。這樣可以從數(shù)據(jù)庫中調(diào)出人們需要查找的那一項(xiàng)。當(dāng)人們要查詢ID為a的商品時，生成結(jié)果如圖8所示。

在進(jìn)入FP-Tree算法界面后，能看到如圖9所示的界面。其中Item是顧客在一次購買行為中購買的商品（項(xiàng)）的集合。只需在后面空白處輸入對應(yīng)的商品ID，輸入完成后點(diǎn)擊數(shù)據(jù)錄入按鈕即可。重復(fù)上述操作完成數(shù)據(jù)錄入。事務(wù)查詢是對購買商品的整體查詢，按第幾列查詢，并在第幾列輸入你所要查詢的商品ID即可。在執(zhí)行算法之前只需在“請輸入支持度”按鈕后面輸入所需的支持度即可。支持度定義在0到1之間，事務(wù)個數(shù)由程序自動生成，它代表了所有顧客總的消費(fèi)次數(shù)，最小支持度為支持度與實(shí)務(wù)個數(shù)的乘積。

1.3.2 FP-GROWTH算法相關(guān)界面

在使用中，人們對不同的支持度產(chǎn)生的選項(xiàng)有需求。那么就需要程序可根據(jù)我們輸入的支持度來輸出，這為下一步的決策提供了依據(jù)。可根據(jù)當(dāng)時的需要輸入相應(yīng)的支持度，在這里以0.4為例，如圖10所示。

1.3.3 系統(tǒng)實(shí)現(xiàn)結(jié)果

數(shù)據(jù)庫中的原始數(shù)據(jù)如圖11所示，在這些數(shù)據(jù)的基礎(chǔ)上人們能方便地得出要預(yù)計(jì)的結(jié)果。

圖11 原始數(shù)據(jù)

從圖11能了解到商品和銷售的一些基本信息，為了驗(yàn)證程序的正確性，在sale表中給出了3條銷售記錄。這些記錄源于利物浦大學(xué)計(jì)算機(jī)科學(xué)系給出的實(shí)驗(yàn)原始數(shù)據(jù)。從圖11我們可以直觀地發(fā)現(xiàn)一個集合db，根據(jù)需求輸入了一個支持度0.4，在整個數(shù)據(jù)庫中存在著3個實(shí)務(wù)個數(shù)，由于最小支持?jǐn)?shù)是事務(wù)個數(shù)與支持度的乘積，很容易就得到了最小支持度為1.2，把測得項(xiàng)的支持度與1.2對比，支持?jǐn)?shù)比1.2大的集合為{b，d，db}。根據(jù)程序設(shè)計(jì)要求，把符合要求的最大項(xiàng)輸出實(shí)現(xiàn)結(jié)果如圖12所示。

2 Apriori算法的性能瓶頸

2.1 對數(shù)據(jù)庫的掃描次數(shù)過多

當(dāng)事務(wù)數(shù)據(jù)庫中存放大量事務(wù)數(shù)據(jù)時，在有限的內(nèi)存容量下，系統(tǒng)I/O負(fù)載相當(dāng)大。對每次k循環(huán)，候選集CK中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗(yàn)證其是否加入LK。假如有一個頻繁大項(xiàng)集包含10個項(xiàng)的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫10遍。每次掃描數(shù)據(jù)庫的時間就會非常長，這樣導(dǎo)致Apriori算法效率相對低。

2.2 可致使龐大的侯選集的產(chǎn)生

由LK-1產(chǎn)生k-侯選集CK是指數(shù)增長的，例如104的1-頻繁項(xiàng)集就有可能產(chǎn)生接近107個元素的2-侯選集。如果要產(chǎn)生一個很長的規(guī)則時，產(chǎn)生的中間元素也是巨大的。

2.3 有用數(shù)據(jù)少

基于支持度和可信度框架理論發(fā)現(xiàn)的大量規(guī)則中，有一些規(guī)則即使?jié)M足用戶指定的最小支持度和可信度，但仍沒有實(shí)際意義；如果最小支持度閾值定得越高，有用數(shù)據(jù)就越少，有意義的規(guī)則也就不易被發(fā)現(xiàn)，這樣會影響決策的制定。

2.4 算法適應(yīng)范圍小

Apriori算法僅僅考慮了布爾型的單維關(guān)聯(lián)規(guī)則的挖掘，在實(shí)際應(yīng)用中，可能出現(xiàn)多類型的、多維的、多層的關(guān)聯(lián)規(guī)則[18-21]。

兩種算法最小支持度設(shè)置與執(zhí)行時間的性能比較如圖13所示，當(dāng)最小支持度分別為1%，0.5%，0.2%，0.1%時，Apriori算法比FP-GROWTH算法運(yùn)行時間長。當(dāng)兩個算法運(yùn)行時間相同時，F(xiàn)P-GROWTH算法能夠?qū)崿F(xiàn)比Aprior算法最小支持度更低的運(yùn)算。從測試結(jié)果可以看出，F(xiàn)P-GROWTH算法在挖掘頻繁項(xiàng)目集方面的性能要好于Apriori算法。

3 結(jié)語

在本課題里，我們對基于FP-GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行了理論研究和系統(tǒng)的實(shí)現(xiàn)。描述了數(shù)據(jù)挖掘和關(guān)聯(lián)規(guī)則的背景、理論基礎(chǔ)以及國內(nèi)外研究現(xiàn)狀。采用了C++，SQL server來實(shí)現(xiàn)的系統(tǒng)，在系統(tǒng)中，人們能夠?qū)?shù)據(jù)庫進(jìn)行基本操作并能執(zhí)行算法。對于最后結(jié)果筆者給出了分析，并與Apriori算法進(jìn)行了比較。

由于時間的倉促，系統(tǒng)的界面排版還不夠完美。程序主界面較為簡單，沒有插入圖片點(diǎn)綴界面使界面更加好看。數(shù)據(jù)庫設(shè)計(jì)方面，設(shè)定的查詢、修改、刪除等操作較為繁瑣，不夠人性化。在當(dāng)時設(shè)計(jì)算法界面時，沒把顧客購買的項(xiàng)目集和算法執(zhí)行分開，導(dǎo)致算法執(zhí)行界面較為復(fù)雜。使用者在操作時容易混淆相關(guān)操作。界面的布局相當(dāng)擁擠，這是在當(dāng)時設(shè)計(jì)時沒有想到的。

雖然系統(tǒng)還有很多需要完善之處，但就系統(tǒng)的設(shè)計(jì)思路和方法來說還是有其特色的。將會在現(xiàn)有基礎(chǔ)上，進(jìn)一步改進(jìn)和完善系統(tǒng)，使其可以達(dá)到更好的效果，更好地滿足用戶的使用需求。通過對基于FP-GROWTH算法的關(guān)聯(lián)規(guī)則挖掘算法系統(tǒng)的開發(fā)，讓人們對實(shí)際系統(tǒng)的開發(fā)有了一個初步的整體概念，真正體會到了軟件工程以及面向?qū)ο蟮乃枷朐趯?shí)踐中的指導(dǎo)作用。

[參考文獻(xiàn)]

[1]劉乃麗，李玉忱，馬磊，等.一種基于FP-tree的最大頻繁項(xiàng)目集挖掘算法[J].計(jì)算機(jī)應(yīng)用，2005（5）：998-1000.

[2]韓家煒，米歇爾·坎伯. 數(shù)據(jù)挖掘概念與技術(shù)[M].2版.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2001.

[3]朱明.數(shù)據(jù)挖掘[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2002.

[4]HAN J，KAMBER M. Data mining concepts and techniques[J].Data Mining Concepts Models Methods & Algorithms Second Edition，2012（4）：1-18.

[5]李瑞軒，盧正鼎.多數(shù)據(jù)庫系統(tǒng)原理與技術(shù)[M].北京：電子工業(yè)出版社，2005.

[6]張?jiān)茲?，龔?數(shù)據(jù)挖掘原理與技術(shù)[M].北京：電子工業(yè)出版社，2004.

[7]崔立新.約束性相聯(lián)規(guī)則發(fā)現(xiàn)方法及算法[J].計(jì)算機(jī)學(xué)報，2000（2）：216-220.

[8]毛國君，段立娟.數(shù)據(jù)挖掘原理和算法[M].北京：清華大學(xué)出版社，2016.

[9]邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京：中國水利水電出版社，2003.

[10]李冠乾，許亮.CRM數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的應(yīng)用[J].昆明理工大學(xué)學(xué)報（自然科學(xué)版），2004（1）：113-117.

[11]趙巖，趙慧娟.數(shù)據(jù)挖掘理論與技術(shù)[J].福建電腦，2006（2）：54.

[12]薛慧君.數(shù)據(jù)挖掘技術(shù)及其在電子商務(wù)中的應(yīng)用研究[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報（自然科學(xué)版），2005（4）：86-90.

[13]楊克儉.數(shù)據(jù)挖掘及其應(yīng)用研究回顧[J].福建電腦，2004（7）：9-10.

[14]李菁菁.數(shù)據(jù)挖掘在中國的現(xiàn)狀和發(fā)展研究[J].管理工程學(xué)報，2004（3）：10-15.

[15]瑪格麗特·鄧納姆.數(shù)據(jù)挖掘教程[M].郭崇慧，田鳳占，靳曉明，譯.北京：清華大學(xué)出版社，2005.

[16]李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.

[17]吉根林，帥克，孫志揮.數(shù)據(jù)挖掘技術(shù)及其應(yīng)用[J].南京師范大學(xué)學(xué)報（自然科學(xué)版），2000（2）：25-27.

[18]唐華松，姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討[J].計(jì)算機(jī)應(yīng)用研究，2000（8）：18-22.

[19]周志華，陳世福.神經(jīng)網(wǎng)絡(luò)集成[J].計(jì)算機(jī)學(xué)報，2002（6）：587-590.

[20]李永敏，朱善君，陳湘暉，等.基于粗糙理論的數(shù)據(jù)挖掘模型[J].清華大學(xué)學(xué)報（自然科學(xué)版），1999（1）：110-113.

[21]糜元根.數(shù)據(jù)挖掘方法的評述[J].南京化工大學(xué)學(xué)報，2001（9）：105-109.endprint