基于云平臺的知識關聯挖掘研究

凌 玥，劉晶晶，章 韻

（南京郵電大學，江蘇 南京 210046）

基于云平臺的知識關聯挖掘研究

凌 玥，劉晶晶，章 韻

（南京郵電大學，江蘇 南京 210046）

針對用戶動態瀏覽過程，文章提出了一種基于權值矩陣的FP-Growth關聯規則。經過時間因子過濾，得到初始矩陣，進一步計算出權值向量，用于FP-Growth算法改進。同時，解決了動態事務項集部分更新及支持度變化的問題，分析頻繁項集的關聯規則，在云平臺上進行并行處理，改進算法性能和時空間效率，最終得到更有效、更精準的頻繁項集，為后續推送研究做基礎。

數據挖掘；Hadoop；關聯規則；MapReduce近年來，“云計算”［1］和大數據（Big Data）［2］技術在全世界迅猛發展，引起了全世界的廣泛關注。大數據技術發展的主要推動力來自并行計算硬件和軟件技術的發展，以及近年來行業大數據處理需求的迅猛增長。其中，大數據處理技術最直接的推動因素，當數MapReduce大規模數據分布存儲和并行計算技術，以及開源Hadoop MapReduce并行計算系統的普及使用。從宏觀角度分析，數據挖掘等同于“數據中的知識發現”，但從微觀上看，數據挖掘只是KDD過程的一個關鍵步驟。KDD包含數據清理［3］、數據集成、數據選擇、數據變換、數據挖掘［4］、模式評估、知識表示幾個環節［5］。本文基于關聯規則［6］的推薦思想：挖掘了論文之間的相關性，即用戶讀取文獻及其參考文獻時間與其之間相互引用次數累計，找出兩者的關系密切程度，再排序選出優先推送，研究了這一問題并提出了一個在頁面瀏覽時間因子矩陣的基礎上挖掘頻繁項集的關聯規則算法。關聯規則挖掘方法自提出以來已有很多改進算法，本文從事務項的時間角度，針對用戶瀏覽軌跡，停留時間及路徑等問題，提出了一種基于時間矩陣FP-tree關聯規則挖掘方法。

1 關聯規則問題描述及關聯規則實現

1.1 關聯規則和FP樹及FP-Growth算法

1.1.1 關聯規則

一個關聯規則［7］是一個形式如下的蘊含關系：，其中，且。

X（或Y）可以被認為是一個總和，稱為項集，并稱X為前件，Y為后件。如果 X是事務集ti∈T的一個子事務，則稱ti包含X。支持度（Support，）和置信度（Confidence），這兩個是關聯規則判斷的主要數據指標，決定是否是關聯規則。頻繁項集就是如果項集I的支持度大于等于預定義的最小支持度閾值，則I是頻繁項集。

關聯規則是通過頻繁項集挖掘，構成形如X→Y蘊含關系，其中，并且。同時計算蘊含式X→Y的置信度，若其置信度大于等于預定義的最小置信度閾值，則是有效的關聯規則。

1.1.2 FP樹

FP樹［8］是通過依次順序讀取事務數據記錄，并把每個事務映射到一棵根結點為null的樹上，根據樹生成的路徑模擬數據事務關系，它是一種輸入數據的壓縮形式。

1.1.3 FP-Growth算法

FP-Growth 算法［9］的最核心的步驟是 FP 樹的構造過程，需要掃描兩次事務數據集：第一次掃描事務數據集，計算出所有事務中項支持度，找出滿足支持度的項（1 頻繁項），并且將頻繁項按支持度值降序排列；第二次掃描，以前一次掃描獲取的事務集為基礎構建一棵以“null”為根的FP樹；然后FP-Growth算法將FP-tree劃分成條件子樹，以自底向上方式探索樹，相當于基于后綴的方法對頻繁項集的挖掘。FP樹中的每一條路徑映射一個事務，通過對指定結點的路徑考察，可以挖掘以該結點結尾的頻繁項集。

1.2 關聯規則實現

1.2.1 瀏覽軌跡日志信息

當用戶瀏覽知網等網站服務器時，在服務器中會記錄用戶瀏覽過程相關聯的一些日志文件信息。在日志文件中，每條記錄被稱作項或條目，這樣可以根據用戶瀏覽文獻的習慣，對其瀏覽路徑及用戶在頁面停留時間做信息采集，通過關聯分析找出頻繁項集，關聯規則挖掘的目標是發現用戶對站點各頁面的訪問之間的關系。

1.2.2 用戶瀏覽路徑關聯規則挖掘

關聯模式的挖掘算法通常是把用戶的訪問時間或者用戶的訪問頻率當作瀏覽過程中很重要的一個環節。通過日志分析可以把用戶這些瀏覽軌跡的信息能夠形成用戶在網頁上最頻繁瀏覽的路徑，是可以將信息轉換成數據形式存入數據庫中，通過對數據庫中數據遍歷路徑進行挖掘得出頻繁項集。

在造林之前，應該詳細科學合理、精心組織情況下，根據生態區位的重要性規劃林地，根據造林地的地理優勢、水分等條件進行合理布局，尤其是道路與排灌設施等。為此，加快修建新的主干道，進一步完善排灌設施。對于油茶幼樹種植靠近田地邊田埂上的，幼樹栽植應盡量保持與田埂一定的距離，方便于后續作業、油茶果實采摘運輸等。排水方面措施：在幼苗的周圍填土使之形成壟狀，壟約高于地面25厘米，組織有關人員及時開挖排水溝渠，及時排出去多余的水分。科學合理規劃建設油茶林地，為油茶栽培奠定良好基礎。

1.2.3 基于用戶瀏覽分析的時間因子

網頁的有效性與用戶所瀏覽網頁時的瀏覽行為是密切相關的。從表面上能夠看出網頁對用戶整個瀏覽過程中的重要性的瀏覽行為很多，其中最為重要是用戶在某一網頁上的瀏覽時停留的時間和來回重復瀏覽某一網頁的次數。在依據閱讀文獻的習慣及上述關聯規則FP-tree的基礎上，考慮用戶在頁面的瀏覽時間及次數這方面的因素，將時間因子作為關聯規則過濾因子，來更好地計算出用戶瀏覽的路徑。

1.2.4 基于矩陣的FP-Growth改進算法

根據研究發現將矩陣運算和樹的存儲結構相結合應用于關聯規則挖掘是比較高效且實用算法改進方法的手段。矩陣被認為高效的且有利于提高關聯規則效率及減少空間開銷的算法之一。樹形結構，可以直觀明朗地表示頻繁項集之間的內在聯系，便于動態更新處理。

2　基于云平臺算法設計

2.1 算法步驟

根據上面的分析，得出理論分析步驟及改進算法思想流程如下：（1）掃描數據庫，依據時間因子的約束，得到時間過濾矩陣。（2）在時間過濾矩陣的基礎上，計算每個項目支持度，生成權值矩陣，調用剪枝函數（大于支持度閾值）得到頻繁矩陣。（3）通過程序掃描頻繁矩陣，及數據庫或最小支持度變化，動態更新頻繁矩陣，采用MapReduce并行框架，來構建FP樹。（4）在并行化FP樹輸出結果中，用關聯挖掘算法FP-Growth（FP-tree，最小支持度）挖掘最終的頻繁項集。（5）最后通過頻繁項集在聚類中加權篩選，得出最終的頻繁項集，得到關聯關系。

2.2 MapReduce模型并行化設計

基于云平臺的MapReduce 的改進FP-Growth 算法MR-FP具有以下兩個步驟：（1）第一次MapReduce任務計算事務中項的支持度構成權值矩陣。首先是將數據庫分割成小數據塊，后將這些塊被發送服務器進行支持數的并行計算。這個計算過程可以通過MapReduce分布式地計算完成，計數結果構成為頻繁列表和項目是按降序排序的頻繁矩陣，頻繁項目的所有項目被分為若干組。（2）第二次MapReduce任務執行MapReduce-FP-Growth（MR-FP）算法計算滿足支持度頻繁項集關聯挖掘。在MR-FP算法是將改進算法中的一些步驟做并行化處理，實現分布式處理。它需要MapReduce處理并收集從節點的頻繁項集，將矩陣數據映射到FP樹，讀取事務項目矩陣列表和根據改進算法在從節點建立自己的本地條件FP樹并且在從節點同時進行遞歸調用，得出頻繁項集，最后reduce合并形成最終頻繁項集。并行化的核心任務，將串行算法中對各頻繁項的條件FP樹挖掘，改為在從節點結點處理，進行并行化遞歸挖掘，最后再合并成頻繁項集，并以<頻繁項，頻繁項集>輸出。至此，項集挖掘結束并由此得到關聯規則。

3　實驗結果和性能分析

3.1 硬件和軟件環境

實驗云平臺環境為5臺服務器節點組成的Hadoop集群，其中1個節點作為Hadoop集群的Master結點，剩余4個節點作為slave節點。各節點操作系統為Linux CentOS 6.7、Mahout 0.8等，并根據Hadoop的環境搭建約定，建立集群環境。

3.2 關聯實驗結果分析

在圖一的實驗中可以看出，相比于傳統的算法，并行化算法的運行效率大大提高，尤其是隨著事務規模的增加，這種優勢更加凸顯。另一方面，在事務規模較小時，并行算法的運行效率反而會低于傳統算法，原因是并行化算法中需要使用額外時間的開銷來實現各個節點（map、reduce等）的管理和調度，這在小規模事務處理時占了大部分運行時間。但隨著事務規模的持續增大時，并行化算法效率超過了傳統算法，優勢相當明顯。

圖1　串行與并行算法性能比較

4　結語

針對用戶動態瀏覽過程，提出一種基于矩陣的FPGrowth的關聯規則分析。對服務器日志信息進行數據提取，并根據本文提出的時間因子過濾，得到初始矩陣，繼續對矩陣做進一步處理，將改進后的權值矩陣用對FP-Growth進行算法改進，同時解決了動態事務項集部分更新及支持度變化的問題，得出頻繁項集，對頻繁項集中的項基于聚類的結果進行加權篩選，最終得到更有效、更精準的頻繁項集，得出關聯規則，為推送工作做準備。

基于對云平臺的MapReduce框架的研究，可以將上述算法進行并行化。對實驗進行評價，進行實驗，減少了挖掘時間和內存空間的消耗。

［1］趙廣才，張雪萍.云計算技術分析及其展望［J］.電子設計工程，2011（22）：4-7.

［2］Wu X，ZHU X，Wu G Q，et al.Data Mining with Big Data［J］.Knowledge&Data Engineering，2014（1）：97-107.

［3］KARR A F.Exploratory Data Mining and Data Cleaning［J］.American Statistical Association，2006（473）：1152-1154.

［4］SHI Y，XU W，CHEN Z.Data Mining and Knowledge Management［J］.Springerbriefs in Business，2015（3327）：1-11.

［5］唐匯.基于自然最近鄰居的離群檢測算法研究［D］.重慶：重慶大學，2014.

［6］張素蘭.一種基于事務壓縮的關聯規則優化算法［J］.計算機工程與設計，2006（18）：3450-3453.

［7］SAHOO J，DAS A K，GOSWAMI A.An efficient approach for mining association rules from high utility itemsets［J］.Expert Systems with Applications，2015（13）：5754-5778.

［8］GADIA K，BHOWMICK K.Parallel Text Mining in Multicore Systems Using FP-tree Algorithm［J］.Computer Science，2015（45）：111-117.

［9］BORETLT C.An Implementation of the FP-growth Algorithm［J］.International Workshop on Open Source Data Mining Frequent Pattern，2010（3）：1-5.

Based on A Cloud Platform Knowledge Association Mining Research

Ling Yue，Liu Jingjing，Zhang Yun
（Nanjing University of Posts and Telecommunications， Nanjing 210046，China）

In view of the user dynamic browsing process， this paper proposes a FP - Growth of association rules based on weight matrix，after a time factor filter， gets the initial matrix， further compute the weight vector， used for FP - Growth algorithm is improved. At the same time， solved the dynamic part of the update transaction itemsets and support the analysis of frequent item sets of association rules，on the cloud platform for parallel processing， the algorithm to improve performance and space efficiency， eventually get frequent itemsets，more effective and more accurate for subsequent push research foundation。

data mining； Hadoop； association rules； graphs

凌玥（1995— ），女，江蘇無錫，本科。