基于云平臺的知識關(guān)聯(lián)挖掘研究

凌 玥，劉晶晶，章 韻

（南京郵電大學(xué)，江蘇 南京 210046）

基于云平臺的知識關(guān)聯(lián)挖掘研究

凌 玥，劉晶晶，章 韻

（南京郵電大學(xué)，江蘇 南京 210046）

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

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

1 關(guān)聯(lián)規(guī)則問題描述及關(guān)聯(lián)規(guī)則實(shí)現(xiàn)

1.1 關(guān)聯(lián)規(guī)則和FP樹及FP-Growth算法

1.1.1 關(guān)聯(lián)規(guī)則

一個(gè)關(guān)聯(lián)規(guī)則［7］是一個(gè)形式如下的蘊(yùn)含關(guān)系：，其中，且。

X（或Y）可以被認(rèn)為是一個(gè)總和，稱為項(xiàng)集，并稱X為前件，Y為后件。如果 X是事務(wù)集ti∈T的一個(gè)子事務(wù)，則稱ti包含X。支持度（Support，）和置信度（Confidence），這兩個(gè)是關(guān)聯(lián)規(guī)則判斷的主要數(shù)據(jù)指標(biāo)，決定是否是關(guān)聯(lián)規(guī)則。頻繁項(xiàng)集就是如果項(xiàng)集I的支持度大于等于預(yù)定義的最小支持度閾值，則I是頻繁項(xiàng)集。

關(guān)聯(lián)規(guī)則是通過頻繁項(xiàng)集挖掘，構(gòu)成形如X→Y蘊(yùn)含關(guān)系，其中，并且。同時(shí)計(jì)算蘊(yùn)含式X→Y的置信度，若其置信度大于等于預(yù)定義的最小置信度閾值，則是有效的關(guān)聯(lián)規(guī)則。

1.1.2 FP樹

FP樹［8］是通過依次順序讀取事務(wù)數(shù)據(jù)記錄，并把每個(gè)事務(wù)映射到一棵根結(jié)點(diǎn)為null的樹上，根據(jù)樹生成的路徑模擬數(shù)據(jù)事務(wù)關(guān)系，它是一種輸入數(shù)據(jù)的壓縮形式。

1.1.3 FP-Growth算法

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

1.2 關(guān)聯(lián)規(guī)則實(shí)現(xiàn)

1.2.1 瀏覽軌跡日志信息

當(dāng)用戶瀏覽知網(wǎng)等網(wǎng)站服務(wù)器時(shí)，在服務(wù)器中會記錄用戶瀏覽過程相關(guān)聯(lián)的一些日志文件信息。在日志文件中，每條記錄被稱作項(xiàng)或條目，這樣可以根據(jù)用戶瀏覽文獻(xiàn)的習(xí)慣，對其瀏覽路徑及用戶在頁面停留時(shí)間做信息采集，通過關(guān)聯(lián)分析找出頻繁項(xiàng)集，關(guān)聯(lián)規(guī)則挖掘的目標(biāo)是發(fā)現(xiàn)用戶對站點(diǎn)各頁面的訪問之間的關(guān)系。

1.2.2 用戶瀏覽路徑關(guān)聯(lián)規(guī)則挖掘

關(guān)聯(lián)模式的挖掘算法通常是把用戶的訪問時(shí)間或者用戶的訪問頻率當(dāng)作瀏覽過程中很重要的一個(gè)環(huán)節(jié)。通過日志分析可以把用戶這些瀏覽軌跡的信息能夠形成用戶在網(wǎng)頁上最頻繁瀏覽的路徑，是可以將信息轉(zhuǎn)換成數(shù)據(jù)形式存入數(shù)據(jù)庫中，通過對數(shù)據(jù)庫中數(shù)據(jù)遍歷路徑進(jìn)行挖掘得出頻繁項(xiàng)集。

在造林之前，應(yīng)該詳細(xì)科學(xué)合理、精心組織情況下，根據(jù)生態(tài)區(qū)位的重要性規(guī)劃林地，根據(jù)造林地的地理優(yōu)勢、水分等條件進(jìn)行合理布局，尤其是道路與排灌設(shè)施等。為此，加快修建新的主干道，進(jìn)一步完善排灌設(shè)施。對于油茶幼樹種植靠近田地邊田埂上的，幼樹栽植應(yīng)盡量保持與田埂一定的距離，方便于后續(xù)作業(yè)、油茶果實(shí)采摘運(yùn)輸?shù)取Ｅ潘矫娲胧涸谟酌绲闹車钔潦怪纬蓧艩?，壟約高于地面25厘米，組織有關(guān)人員及時(shí)開挖排水溝渠，及時(shí)排出去多余的水分。科學(xué)合理規(guī)劃建設(shè)油茶林地，為油茶栽培奠定良好基礎(chǔ)。

1.2.3 基于用戶瀏覽分析的時(shí)間因子

網(wǎng)頁的有效性與用戶所瀏覽網(wǎng)頁時(shí)的瀏覽行為是密切相關(guān)的。從表面上能夠看出網(wǎng)頁對用戶整個(gè)瀏覽過程中的重要性的瀏覽行為很多，其中最為重要是用戶在某一網(wǎng)頁上的瀏覽時(shí)停留的時(shí)間和來回重復(fù)瀏覽某一網(wǎng)頁的次數(shù)。在依據(jù)閱讀文獻(xiàn)的習(xí)慣及上述關(guān)聯(lián)規(guī)則FP-tree的基礎(chǔ)上，考慮用戶在頁面的瀏覽時(shí)間及次數(shù)這方面的因素，將時(shí)間因子作為關(guān)聯(lián)規(guī)則過濾因子，來更好地計(jì)算出用戶瀏覽的路徑。

1.2.4 基于矩陣的FP-Growth改進(jìn)算法

根據(jù)研究發(fā)現(xiàn)將矩陣運(yùn)算和樹的存儲結(jié)構(gòu)相結(jié)合應(yīng)用于關(guān)聯(lián)規(guī)則挖掘是比較高效且實(shí)用算法改進(jìn)方法的手段。矩陣被認(rèn)為高效的且有利于提高關(guān)聯(lián)規(guī)則效率及減少空間開銷的算法之一。樹形結(jié)構(gòu)，可以直觀明朗地表示頻繁項(xiàng)集之間的內(nèi)在聯(lián)系，便于動態(tài)更新處理。

2　基于云平臺算法設(shè)計(jì)

2.1 算法步驟

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

2.2 MapReduce模型并行化設(shè)計(jì)

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

3　實(shí)驗(yàn)結(jié)果和性能分析

3.1 硬件和軟件環(huán)境

實(shí)驗(yàn)云平臺環(huán)境為5臺服務(wù)器節(jié)點(diǎn)組成的Hadoop集群，其中1個(gè)節(jié)點(diǎn)作為Hadoop集群的Master結(jié)點(diǎn)，剩余4個(gè)節(jié)點(diǎn)作為slave節(jié)點(diǎn)。各節(jié)點(diǎn)操作系統(tǒng)為Linux CentOS 6.7、Mahout 0.8等，并根據(jù)Hadoop的環(huán)境搭建約定，建立集群環(huán)境。

3.2 關(guān)聯(lián)實(shí)驗(yàn)結(jié)果分析

在圖一的實(shí)驗(yàn)中可以看出，相比于傳統(tǒng)的算法，并行化算法的運(yùn)行效率大大提高，尤其是隨著事務(wù)規(guī)模的增加，這種優(yōu)勢更加凸顯。另一方面，在事務(wù)規(guī)模較小時(shí)，并行算法的運(yùn)行效率反而會低于傳統(tǒng)算法，原因是并行化算法中需要使用額外時(shí)間的開銷來實(shí)現(xiàn)各個(gè)節(jié)點(diǎn)（map、reduce等）的管理和調(diào)度，這在小規(guī)模事務(wù)處理時(shí)占了大部分運(yùn)行時(shí)間。但隨著事務(wù)規(guī)模的持續(xù)增大時(shí)，并行化算法效率超過了傳統(tǒng)算法，優(yōu)勢相當(dāng)明顯。

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

4　結(jié)語

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

基于對云平臺的MapReduce框架的研究，可以將上述算法進(jìn)行并行化。對實(shí)驗(yàn)進(jìn)行評價(jià)，進(jìn)行實(shí)驗(yàn)，減少了挖掘時(shí)間和內(nèi)存空間的消耗。

［1］趙廣才，張雪萍.云計(jì)算技術(shù)分析及其展望［J］.電子設(shè)計(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］.重慶：重慶大學(xué)，2014.

［6］張素蘭.一種基于事務(wù)壓縮的關(guān)聯(lián)規(guī)則優(yōu)化算法［J］.計(jì)算機(jī)工程與設(shè)計(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— ），女，江蘇無錫，本科。