陳寅

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

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

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

1.1 FP-GROWTH算法的基本思想

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

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

圖

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

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

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

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

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

1.2.2 系統(tǒng)功能設計

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

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

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

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

1.2.4 系統(tǒng)界面設計

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

圖2 登入設計界面

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

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

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

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

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

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

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

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

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

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

1.3.2 FP-GROWTH算法相關界面

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

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

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

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

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

2 Apriori算法的性能瓶頸

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

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

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

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

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

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

2.4 算法適應范圍小

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

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

3 結(jié)語

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

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

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

[參考文獻]

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

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

[3]朱明.數(shù)據(jù)挖掘[M].合肥：中國科學技術大學出版社，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)原理與技術[M].北京：電子工業(yè)出版社，2005.

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

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

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

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

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

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

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

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

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

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

[16]李敏強，寇紀淞.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

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

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

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

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

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