改進的FP-growth關聯規則算法及其在圖書推薦系統中的應用

劉敏娜，吳建衛

改進的FP-growth關聯規則算法及其在圖書推薦系統中的應用

劉敏娜，吳建衛

在FP-growth關聯規則算法的基礎上提出了基于動態二維數組的算法，引入可變二維數組結構，動態的將事務數據庫存入該數組中，可以大大提高數據挖掘的效率。并以圖書館管理系統中的圖書借閱數據作為訓練數據，使用改進的FP-growth算法實現了高校圖書推薦系統，本系統能夠從圖書館圖書借閱記錄中挖掘和發現讀者借閱行為中隱含的規律，得到讀者與圖書的頻繁項集，從而可以實現對不同身份的讀者推薦不同類型的圖書功能。

數據挖掘；關聯規則算法；FP-growth算法；頻繁項集；高校圖書推薦系統

0 引言

使用關聯規則算法能夠得到關聯度較高的項集，從而揭示事務數據項之間的相關性[1]。對該算法進行深入的研究和改進有助于為很多行業的決策提供更加可信的參考依據。

1 關聯規則描述

關聯規則(Association Rule)，反映的是事務之間的依賴關系。規則可描述為：設有項目集合 A={a1,a2…,am}，事務數據庫T={t1,t2,…,tn}，其中滿足ti? I[2][3]。

如果項集A中包含k個項目，則稱其為k項集。D為事務數據庫，項集A在事務數據庫D中出現的次數占D中總事務的百分比叫做項集的支持度（Support）[4]。支持度是指規則中所出現模式的頻率，如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集[4]。

置信度是指蘊含的強度，即事務D中c%的包含X的交易同時包含Y。若X的支持度是support(x)，規則的信任度為即為：support(XY)/support(X)[5]，這是一個條件概率 P（Y|X），即confidence（X→Y）= P（Y|X）；

2 關聯規則的算法

關聯規則算法按照是否產生候選模式分為兩大類：產生候選集/候選模式的方法和不產生候選集/候選模式的方法

[6]。前一種方法以 Apriori算法為代表[7]；后一種方法以FP-growth（Frequent Pattern growth）[8]算法為代表。

2.1 Aprior算法

Aprior的核心是基于兩階段頻集思想的迭代算法。該關聯規則在分類上屬于單維、單層、布爾關聯規則。

算法的基本思想：掃描一遍數據庫，得到一階頻繁項；用一階頻繁項構造二階候選項；掃描數據庫對二階候選項進行計數，刪除其中的非頻繁項，得到二階頻繁項；然后構造三階候選項，以此類推，直到無法構造更高階的候選項，或到達頻繁項集的最大長度限制[9]。

其核心思想簡要描述如下：

執行此方法要多次掃描交易數據庫，需要很大的I/O負載。

因此產生大量的候選集,以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點。

2.2 FP-growth算法

FP-Growth（頻繁模式增長）算法是韓家煒在2000年提出的關聯分析算法，它采取如下分治策略：將提供頻繁項集的數據庫壓縮到一棵頻繁模式樹（FP-Tree），但仍保留項集關聯信息；該算法和Apriori算法最大的不同有兩點：第一，不產生候選集，第二，只需要兩次遍歷數據庫，大大提高了效率[10]。

它的過程分為兩步：第一步，構造FP-Tree和項頭表；第二步：挖掘FP-Tree中所有的頻繁項集。

2.3 FP_growth算法的改進

FP-growth算法在生成條件FP樹時，需要沿著節點鏈中的各個節點依次遍歷FP-Tree,降低了算法的效率[11]。此外，FP-Tree需要自頂向下生成，而頻繁模式的挖掘需要自底而上處理，因此，FP-Tree必須雙向可遍歷。這樣，FP-Tree的節點中就需要更多的指針，從而需要更大的內存空間來維護FP-T[12] [13]。

本文引入可變二維數組結構，動態的將事務數據庫存入該結構中，依據頻繁l-項集的逆序順序，直接挖掘以該項目為尾的頻繁模式基，無需生成各個節點的點鏈和條件模式庫，可以提高了關聯規則挖掘的效率。

算法的詳細描述如下：

input：事務數據庫DB和最小支持度計數min_sup。

output：頻繁模式的完全集。

步驟：

（1）掃描一次DB，得到頻繁1-項集，并按逆序排序，得到Rev_1。

（2）依據逆序的頻繁1-項集Rev_1對DB進行重排，得到DB_new。

（3）依據DB_new,創建邏輯FP樹FP_Tree_logic。

（4）依據Rev_1的順序，遞歸遍歷FP_Tree_log，挖掘頻繁模式基。

對第三步重點介紹：

//改變各個共根項的計數，形成邏輯上的fp樹

//初始化，分支上各個單項的計數都為1

3 高校圖書流通記錄預處理

3.1 問題分析

圖書館擁有大量的圖書流通數據，這些數據除了記錄讀者的借閱信息外，也隱含了讀者所借閱的圖書和其年齡、性別、興趣等諸多因素之間的關系，比如20歲年齡段，男性較之于女性更喜愛軍事類書籍，而女性則更喜歡情感類的書籍。如果能發現這些隱藏但非常有價值的信息，將能夠促進圖書館更好的為讀者服務。然而目前大多數的高校讀書管理系統只支持常規的查詢統計功能，根本不能發掘海量數據背后隱藏的信息，因此對高校圖書流通記錄進行挖掘是意義重大的。

3.2 數據分析

（1）對讀者信息匯總和分析。

讀者信息主要涉及的信息表如下：

① 學生借閱記錄表（學號，姓名，性別，院系，借書證號，書名，索引號，借書日期，應還書日期，實還書日期，滯納金額）；

② 學生基本情況表（學號，姓名，性別，出生年月，民族，院系，專業，年級，個人特長，入學前戶口，孤殘，單親，烈士子女，健康狀況，家庭人口數，家庭年收入，家庭通訊地址）；

③ 學生成績表（學號，姓名，性別，課程，成績）；

④ 飯卡月消費情況表（學號，姓名，月消費金額）；

（2）對數據進行預處理，去除對分析沒有作用的信息。在學生的基本情況表中，孤殘，單親，烈士子女，健康狀況，家庭人口數，家庭年收入，這些字段可以去掉。而其他的字段如年級，性別，個人特長，入學前戶口，地區等可以作為圖書推薦的參考因素。

學生借閱記錄表中的借書日期，應還書日期，實還書日期，滯納金額可以去掉。

經過整理得到讀者信息表包括學號，姓名，性別，年級，院系，月消費金額，地區，個人愛好，入學前戶籍，成績，書名，索引號等字段。

4 改進的關聯規則算法在高校圖書推薦系統中的應用

4.1 算法介紹

輸入：事務數據庫D；最小支持度閾值min_sup。輸出：頻繁模式的完全集。

構造FP-樹

（a）第一次掃描事務數據庫D。收集頻繁項的集合F 和它們的支持度。對F 按支持度降序排序，結果為頻繁項表L。

（b）創建FP-樹的根結點，以”null”標記。對于D 中每個事務Trans，執行：選擇 Trans 中的頻繁項，并按L 中的次序排序。設排序后的頻繁項表為[p | P]，其中，p 是第一個元素，而P 是剩余元素的表。調用insert_tree([p | P], T)。

該過程執行情況如下。如果 T 有子女 N 使得N.item-name = p.item-name，則N 的計數增加1；否則創建一個新結點N，將其計數設置為1，鏈接到它的父結點T，并且通過結點鏈結構。

將其鏈接到具有相同item-name 的結點。如果P 非空，遞歸地調用insert_tree(P, N)。

挖掘頻繁項

算法：頻繁模式基挖掘算法

FP-樹的挖掘通過調用FP_growth(FP_tree, null)實現。該過程實現如下：

procedure FP_growth(Tree, α)如果FP-tree中含單個路徑P

for 路徑 P 中結點的每個組合（記作β）

產生模式β ∪ α，其支持度support = β中結點的最小支持度；

否則 for each ai 在 Tree 的頭部 {

產生一個模式β = ai ∪ α，其支持度 support = ai .support；

構造β的條件模式基，然后構造β的條件FP-樹Treeβ；

如果Treeβ ≠ ? then

調用 FP_growth (Treeβ, β)；}

4.2 數據結果及分析

以《Java程序設計》,ISBN為9787111340812為例，依據借閱此書的讀者數據，挖掘喜歡這本書讀者的性別，年級，院系，生源地，月消費額，地區，成績，個人愛好等因素之間的關系。

在進行數據挖掘之前要預先設定一個比較合理的最小支持度和最小置信度。本實驗設定最小支持度是5%，最小置信度是50%。

使用Apriori算法對處理后的數據進行挖掘后得到的部分關聯規則，如表1、表2所示：

表1 Apriori算法挖掘關聯規則

表2 基于動態二維數組改進的FP-growth算法挖掘到的部分規則

規則二 女，華東地區=>喜歡 23.25% 88.72%規則三 成績在80分以上，喜愛閱讀=>喜歡 6.35% 85.15%規則四男，成績在70分以上，月消費額600到800之間，華南地區=>喜歡3.45% 100%規則五 女，文傳院=>喜歡 5.65% 98.24%規則六 女，化工院，喜愛閱讀=>喜歡 3.05% 100%

4.3 分析和評估

通過以上結果分析發現，無論采用 Apriori算法、FP-growth算法和改進算法在進行數據挖掘時，改進的FP-growth算法生成頻繁項目集的時間最短，而且數據量越大，改進型算法的挖掘效果越好。

5 總結

本文利用高校圖書管理系統數據庫中的借閱記錄，將關聯規則算法應用于高校圖書推薦系統，挖掘出讀者特性和圖書之間的關系，從而為不同讀者推薦圖書，為讀者提供更加智能的服務。進一步研究將關聯規則應用到圖書采購、圖書分類編目、用戶咨詢等圖書管理環節，輔助圖書館工作人員工作，能夠將圖書館員從日常繁雜的工作中解脫出來，專注于更高層次的研究，提高圖書館的效率和服務水準。

[1] Tom M.Mitchell.機器學習 [M].曾華軍等.北京:機械工業出版社,2003.

[2] Peter Harrington.機器學習實戰 [M].李銳.北京:人民郵電出版社,2013.

[3] 宋余慶,朱玉全,孫志輝.基于FP-Tree的最大頻繁項目集挖掘及更新算法[J].軟件學報.2013,14(9): 86-92.

[4] 秦亮曦,蘇永秀,劉永彬.基于壓縮FP-樹和數組技術的頻繁模式挖掘算法[J].計算機研究與發展,2014,45: 44-49.

[5] 趙曉敏,何松華,李賢鵬.一種改進的FP-growth算法及其在業務關聯中的作用[J].計算機應用,2013,28(9): 41-45.

[6] 范明,李川.在 FP-樹中挖掘頻繁模式而不生成條件 FP樹[J].計算機研究與發展,2013,40(8): 16-23.

[7] 李洪波,周莉,張吉贊.用垂直數據格式構建FP增長樹的算法[J].計算機工程與應用,2011,45(8):161-164.

[8] 盛偉翔,龍佳麗.數據倉庫與數據挖掘技術[J].電腦知識與技術,2010(3), 31-32.

[9] 鄧豐義,劉震宇.基于模式矩陣的FP-growth改進算法[J].廈門大學學報:自然科學版,2012(6):50-51.

[10] 尢磊,蘭洋.一種改進的FP-growth關聯規則挖掘算法的實現[J].河南科技,2012(6):50-51.

[11] Han Jiawei, Micheline Kamber. Data Mining: Concepts and Techniques[M]. Beijing: Higher Education Press, 2011.

[12] Rakesh Agrawal, Ramakrishnan Srikant. Fast algoritms for mining association rules[A].proceedings of the 20th VLDB conference[C].Santigao,Chile,2012.

[13] Grahne G,Zhu J. Fast algorithms for frequent itemset mining using FP-trees[J]. IEEE Transactions on Knowledge and Data Engineeting,2011,17(10): 47-62.

The Improve and Application of FP-Growth Algorithm of Association Rules

Liu Minna, Wu Jianwei
(Institute of Graphics and Image Processing, Xianyang Normal University, Xianyang 712000, China)

Based on the algorithm of FP-growth, the paper proposed a dynamic two-dimensional array. The algorithm leads in the variable two-dimensional array structure and stores the dramatic transaction database into the array. It significantly improves the efficiency of data mining, meanwhile, by using library’s managing systems’ book lending data as a training data. The paper uses the improved FP - growth algorithm and has accomplished to the book recommendation system in colleges and universities. From the lending record in the library, this system can explore and find the rules from readers’ behavior as well as frequent itemsets between readers and books, thus it manages to recommend different types of books to readers of different identity.

Data Mining; Association Rules Algorithm; FP-Growth Algorithm; Frequent Item Sets; Book Recommendation System

TP391

A

2014.10.31）

1007-757X(2014)12-0045-03

自然科學基金（面上項目）（2013JM8037），陜西省科學技術研究發展計劃項目

劉敏娜（1980-）女，咸陽人，咸陽師范學院，圖形圖像處理研究所，講師，碩士，研究方向：機器學習，高性能網站研究，咸陽，712000

吳建衛（1996-）男，咸陽人，咸陽師范學院，圖形圖像處理研究所，研究方向：機器學習，咸陽，712000