基于FP—GROWTH算法的關聯規則挖掘算法研究

陳寅

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

關鍵詞：數據挖掘；關聯規則；FP-GROWTH算法；候選集；頻繁模式樹

1 基于FP-GROWTH算法的關聯規則挖掘算法

1.1 FP-GROWTH算法的基本思想

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

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

圖

1.2 基于FP-GROWTH算法的關聯規則挖掘算法的系統實現

1.2.1 算法實現環境

從上面的闡述中，可以了解到系統的實現采用了C++和SQL server，在這里我們對編譯環境進行簡介，并說明它們的優點。

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

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

1.2.2 系統功能設計

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

1.2.3 數據庫設計

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

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

1.2.4 系統界面設計

系統的界面，主要提供了數據庫的基本操作界面，FP-GROWTH算法的執行界面，在進入程序后會彈出用戶登入界面，用戶登入后，為方便用戶對系統進行針對性的操作，筆者設計了工具選擇窗口。具體設計如圖2所示。

圖2 登入設計界面

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

在數據庫的界面上人們能夠實現數據的查詢、添加、修改、刪除等操作。界面中還包含了商品序列號、商品名稱、查詢方式等操作窗口（見圖3）。這些使得人們更能直觀地進行使用。

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

1.3 系統實現和結果分析

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

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

1.3.1 數據庫相關界面endprint

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

以查詢為例，SecIo是按照商品屬性的第幾列來查詢，如ID對應第一列，Name對應第2列，以此類推。這樣可以從數據庫中調出人們需要查找的那一項。當人們要查詢ID為a的商品時，生成結果如圖8所示。

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

1.3.2 FP-GROWTH算法相關界面

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

1.3.3 系統實現結果

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

圖11 原始數據

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

2 Apriori算法的性能瓶頸

2.1 對數據庫的掃描次數過多

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

2.2 可致使龐大的侯選集的產生

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

2.3 有用數據少

基于支持度和可信度框架理論發現的大量規則中，有一些規則即使滿足用戶指定的最小支持度和可信度，但仍沒有實際意義；如果最小支持度閾值定得越高，有用數據就越少，有意義的規則也就不易被發現，這樣會影響決策的制定。

2.4 算法適應范圍小

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

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

3 結語

在本課題里，我們對基于FP-GROWTH算法的關聯規則挖掘算法進行了理論研究和系統的實現。描述了數據挖掘和關聯規則的背景、理論基礎以及國內外研究現狀。采用了C++，SQL server來實現的系統，在系統中，人們能夠對數據庫進行基本操作并能執行算法。對于最后結果筆者給出了分析，并與Apriori算法進行了比較。

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

雖然系統還有很多需要完善之處，但就系統的設計思路和方法來說還是有其特色的。將會在現有基礎上，進一步改進和完善系統，使其可以達到更好的效果，更好地滿足用戶的使用需求。通過對基于FP-GROWTH算法的關聯規則挖掘算法系統的開發，讓人們對實際系統的開發有了一個初步的整體概念，真正體會到了軟件工程以及面向對象的思想在實踐中的指導作用。

[參考文獻]

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

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

[3]朱明.數據挖掘[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]李瑞軒，盧正鼎.多數據庫系統原理與技術[M].北京：電子工業出版社，2005.

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

[7]崔立新.約束性相聯規則發現方法及算法[J].計算機學報，2000（2）：216-220.

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

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

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

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

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

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

[14]李菁菁.數據挖掘在中國的現狀和發展研究[J].管理工程學報，2004（3）：10-15.

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

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

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

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

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

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

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