基于Web挖掘的關(guān)聯(lián)推薦算法研究

金加和 張泯泯

（浙江省電子政務(wù)學(xué)會(huì)，浙江杭州 310000）

0 引言

Web 技術(shù)的研究熱點(diǎn)是提供個(gè)性化服務(wù)給用戶，Web個(gè)性化的實(shí)現(xiàn)采用的是關(guān)聯(lián)規(guī)則，使用關(guān)聯(lián)規(guī)則挖掘在Web上對用戶訪問網(wǎng)站的模式進(jìn)行挖掘，并且對用戶在線推薦結(jié)合當(dāng)前訪問行為進(jìn)行。采用的是支持度—信任的約束，在現(xiàn)有的在線推薦算法中減少或消除無用的規(guī)則，這種算法能夠產(chǎn)生準(zhǔn)確的推薦，一定程度上的保證了推薦系統(tǒng)的實(shí)時(shí)性。本文對用戶個(gè)性化需求進(jìn)行探討分析，用戶事務(wù)模式的挖掘基于Log 文件，在線方式的智能個(gè)性化推薦服務(wù)是通過關(guān)聯(lián)規(guī)則挖掘算法和Web 挖掘技術(shù)來實(shí)現(xiàn)的。

1 關(guān)于Web數(shù)據(jù)挖掘技術(shù)

1.1 Web數(shù)據(jù)挖掘技術(shù)：指在Web環(huán)境下應(yīng)用數(shù)據(jù)挖掘技術(shù)，在挖掘搜索信息、用戶訪問日志文件、網(wǎng)絡(luò)用戶登記信息、商品信息、購銷信息以等內(nèi)容中充分利用網(wǎng)絡(luò)（Internet），在其中找出潛在有用的、有價(jià)值并且是隱性的商業(yè)信息，然后把這些信息應(yīng)用到企業(yè)管理以及商業(yè)決策。從專業(yè)技術(shù)上，它完美的結(jié)合了數(shù)據(jù)挖掘技術(shù)和WWW技術(shù)，作為種新興的網(wǎng)絡(luò)技術(shù)在不同的領(lǐng)域都得到了很好的應(yīng)用，例如常見的計(jì)算機(jī)語言和Internet、人工智、、信息學(xué)以及統(tǒng)計(jì)學(xué)等。

1.2 Web數(shù)據(jù)挖掘具備的特點(diǎn)：一是可以處理大規(guī)模的數(shù)據(jù)量；二是用戶“訪問模式動(dòng)態(tài)

獲取”不會(huì)過時(shí)；三是用戶不用提供主觀的評價(jià)信息，使用方便；四是Web的優(yōu)勢在于提供了一個(gè)巨大、分布廣泛、全球性的信息服務(wù)中心，這是傳統(tǒng)數(shù)據(jù)庫和數(shù)據(jù)倉庫無法比擬的。

2 關(guān)聯(lián)推薦算法思路分析

在離線狀態(tài)下上傳Log文件是通過WEB服務(wù)器實(shí)現(xiàn)的，把頻繁前向訪問路徑集找出，從而生成頻繁訪問路徑聚集圖，導(dǎo)航頁和內(nèi)容頁包含在其中；在線狀態(tài)情況下對用戶最新的訪問記錄進(jìn)行始終記錄由活動(dòng)窗口來完成，活動(dòng)窗口的W個(gè)網(wǎng)頁為記錄個(gè)數(shù)，并且這個(gè)網(wǎng)頁作為當(dāng)前訪問路徑；從離線生成的聚集圖上獲取W＋1 個(gè)網(wǎng)頁，作為候選的推薦路徑；結(jié)合網(wǎng)站的結(jié)構(gòu)刪除一些候選推薦路徑，這些路徑中含有最小偏愛度要求、最小支持度和導(dǎo)航頁，最后待推薦集由剩余的網(wǎng)頁來形成，推薦給用戶推薦度在前TOP_N 個(gè)的網(wǎng)頁。

3 算法分析

3.1 頻繁訪問路徑圖的生成

在服務(wù)器端進(jìn)行數(shù)據(jù)預(yù)處理日志文件Log，這些文件包含用戶歷史訪問信息，建立用戶訪問事務(wù)集；過濾掉不頻繁的項(xiàng)使用最小支持度，頻繁訪問路徑聚集圖的形成用戶訪問事務(wù)集中進(jìn)行，為在線階段計(jì)算推薦集打好基礎(chǔ)。尋找MFPS即最大前向訪問路徑集，更新的頁面屬性值時(shí)，對于同一頁面的不同MFP，則將曾為內(nèi)容頁的頁面更新為內(nèi)容頁；對于同一頁面的同一MFP中，只要MFP中的個(gè)頁面在次訪問中是用戶感興趣的，就當(dāng)作是內(nèi)容頁；通過這些方法對所有興趣不同的主題頁面進(jìn)行收集，根據(jù)后面提出的推薦因子來對與訪問的無關(guān)的頁面進(jìn)行過濾，生成頻繁訪問路徑聚集圖G。

3.2 推薦集的計(jì)算

首先從聚集圖關(guān)聯(lián)推薦服務(wù)算法中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，并且這個(gè)關(guān)聯(lián)規(guī)則匹配用戶訪問路徑，接下確定推薦項(xiàng)，這個(gè)過程是根據(jù)推薦度因子的大小來實(shí)現(xiàn)的，其中推薦度因子是指距離因子乘以關(guān)聯(lián)規(guī)則的置信度。對用戶的訪問路徑的獲取采用滑窗采樣，對用戶的訪問操作有效實(shí)時(shí)地跟蹤，可以實(shí)現(xiàn)在線推薦?；安蓸邮怯脩粼L問路徑滑窗覆蓋為W去匹配聚集圖上的子訪問路徑，從而獲取頻繁子訪問路徑，所有長度為 W＋1。

3.3 收集和分析用戶信息、進(jìn)行推薦、產(chǎn)生推薦結(jié)果等都屬于個(gè)性化推薦系統(tǒng)，它們可以分為在線和離線兩個(gè)部分。

a、在線部分：根據(jù)支持?jǐn)?shù)的大小對用戶當(dāng)前的訪問頁面序列進(jìn)行排序，關(guān)聯(lián)規(guī)則的前項(xiàng)在規(guī)則集中去尋找相匹配的規(guī)則，推薦給用戶推薦度在前TOP_N 個(gè)的網(wǎng)頁。

b、離線部分：該部分用于對用戶信息的收集和分析，進(jìn)行數(shù)據(jù)預(yù)處理用戶之前的訪問日志歷史，把它轉(zhuǎn)變?yōu)榧儍舻倪m合挖掘的數(shù)據(jù)，興趣訪問模式的獲取是對該用戶訪問頁面之間的關(guān)聯(lián)規(guī)則采用關(guān)聯(lián)規(guī)則挖掘算法FP-Mine算法進(jìn)行挖掘。

Web個(gè)性化推薦原型的體系結(jié)構(gòu)圖如下：

3.4 FP-Mine挖掘算法使關(guān)聯(lián)規(guī)則的挖掘效率得到了很大提高，它不僅能夠?qū)ふ翌l繁訪問模式集而且給出關(guān)聯(lián)規(guī)則的方法。算法描述如下：

作為樹形結(jié)構(gòu)Freq-Set-Tree，對(i+1)-size 和i-size和(i=1，2，3…，n)的頻繁項(xiàng)集進(jìn)行存儲(chǔ)，分為5個(gè)域的樹中節(jié)點(diǎn)，如下為其具體定義：

struct FSnode

{ unsigned int *id；// 存儲(chǔ)項(xiàng)集的名字

unsigned int support；// 項(xiàng)集的支持度

double confidence；// i-size節(jié)點(diǎn)中關(guān)聯(lián)規(guī)則(p p …p =＞p) 的

置信度

FSnode *left；// 指向比本節(jié)點(diǎn)的id長度增1的一個(gè)超集對應(yīng)的

節(jié)點(diǎn)

FSnode *right； 指向與本節(jié)點(diǎn)的id有相同長度的另一個(gè)項(xiàng)集對

應(yīng)的節(jié)點(diǎn)

}；

每個(gè)節(jié)點(diǎn)在樹中的結(jié)構(gòu)：

struct FPnode

{ unsigned int name；// 是1-size項(xiàng)集名稱

unsigned int support；// 為其計(jì)數(shù)域

set＜FPnode＞ *child；//指向其后繼節(jié)點(diǎn)

FPnode *nodelink；// 指向與其具有相同name的另一個(gè)節(jié)點(diǎn)

}；

算法、輸入、輸出方法：

Algorithm FP-Mine()

{ ⒈利用FP-Tree頭表，建立1-size節(jié)點(diǎn)；

⒉for(i=1；i＜＝n；i++)/*n為生成規(guī)則前項(xiàng)的最大長度*/

{ ⑴for each itemin i-size

①P_Insert()；/*生成i-size 和(i+1)-size的Freq-Set-Tree并生成

相應(yīng)的關(guān)聯(lián)規(guī)則*/

⑵從Freq-Set-Tree中釋放所有i-size節(jié)點(diǎn)；

⑶刪除Freq-Set-Tree樹中不滿足最小支持?jǐn)?shù)的(i+1)-size節(jié)

點(diǎn)；

}

4 在商業(yè)網(wǎng)站中的應(yīng)用價(jià)值分析

結(jié)合商品目錄應(yīng)用多層關(guān)聯(lián)推薦算法，快速自動(dòng)選擇最佳的匹配粒度，在頻繁集的基礎(chǔ)上進(jìn)行在線推薦。在實(shí)踐中得到，這種算法對在線匹配的質(zhì)量和性能有很大程度的提高，在電子商務(wù)中能夠成功的應(yīng)用在個(gè)性化服務(wù)中。用戶在商務(wù)網(wǎng)站購買商品、瀏覽、搜索等方面的信息在Web服務(wù)器中都會(huì)有記錄，商家利用這些數(shù)據(jù)提供個(gè)性化優(yōu)質(zhì)的服務(wù)給用戶，能夠留住舊客戶，并且提高客戶的忠誠度，更多的新客戶也能被吸引過來。

5 結(jié)束語

通過上述內(nèi)容分析和探討了關(guān)聯(lián)規(guī)則的挖掘算法，并對FPMine挖掘算法的性能進(jìn)行了探討，設(shè)計(jì)出個(gè)性化推薦系統(tǒng)模型，能夠個(gè)性化對用戶進(jìn)行推薦。采用支持度—信任的約束，在現(xiàn)有的在線推薦算法中減少或消除無用的規(guī)則，這種算法能夠產(chǎn)生準(zhǔn)確的推薦，一定程度上的保證了推薦系統(tǒng)的實(shí)時(shí)性。

[1]李恒杰，李明.基于本體的Web分類技術(shù)研究[J].微計(jì)算機(jī)信息, 2006，7-3:215-217

[2]薛惠鋒,張文宇,寇曉東.智能數(shù)據(jù)挖掘技術(shù)[M].西安:西北工業(yè)大學(xué)出社,2005:33-35.

[3]閆瑩，王大玲.支持個(gè)性化推薦的Web頁面關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)科學(xué)工程.2005，31(1): 79-81

[4]韓曉莉，李秉智.個(gè)性化Web推薦服務(wù)研究[J].計(jì)算機(jī)科學(xué),2006，33(2):135-138

[5]何小東,劉衛(wèi)國.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法比較研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2005,26(05):1265-1268.

[6]馮珺，孫濟(jì)慶.基于前項(xiàng)不定長關(guān)聯(lián)規(guī)則個(gè)性化推薦算法的研究[J].計(jì)算機(jī)工程與應(yīng)用, 2006，7(6): 174-177