福建省科學技術(shù)信息研究所 張章學

?

基于Web信息挖掘的關(guān)聯(lián)推薦算法研究與實現(xiàn)

福建省科學技術(shù)信息研究所 張章學

使用Web數(shù)據(jù)挖掘技術(shù)對用戶需求進行分析，其中實現(xiàn)Web信息個性化使用的是關(guān)聯(lián)規(guī)則，這一規(guī)則能夠為用戶提供個性化服務(wù)，目前已成為Web 應(yīng)用技術(shù)的研究熱點。該文分析了應(yīng)用于個性化推薦的Web頁面關(guān)聯(lián)規(guī)則的特點，對Web數(shù)據(jù)挖掘技術(shù)常用的關(guān)聯(lián)推薦算法進行探討，內(nèi)容主要涉及到Web數(shù)據(jù)挖掘技術(shù)、關(guān)聯(lián)推薦算法的思路、算法分析。

Web數(shù)據(jù)挖掘 關(guān)聯(lián)推薦算法 個性化內(nèi)容服務(wù)

1 概述

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

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

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

Web數(shù)據(jù)挖掘具備的特點體現(xiàn)在：一是可以處理大規(guī)模的數(shù)據(jù)量；二是用戶“訪問模式動態(tài)獲取”不會過時；三是用戶不用提供主觀的評價信息，使用方便；四是Web提供了一個巨大、分布廣泛、全球性的信息服務(wù)中心，這是傳統(tǒng)數(shù)據(jù)庫和數(shù)據(jù)倉庫無法比擬的。

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

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

4 算法分析與實現(xiàn)

4.1 頻繁訪問路徑圖的生成

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

4.2 推薦集的計算

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

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

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

（2）離線部分：該部分用于對用戶信息的收集和分析，進行數(shù)據(jù)預處理用戶之前的訪問日志歷史，把它轉(zhuǎn)變?yōu)榧儍舻倪m合挖掘的數(shù)據(jù)，興趣訪問模式的獲取是對該用戶訪問頁面之間的關(guān)聯(lián)規(guī)則采用關(guān)聯(lián)規(guī)則挖掘算法FP-Mine算法進行挖掘。 Web個性化推薦系統(tǒng)體系結(jié)構(gòu)圖示意圖如下：

4.3 算法實現(xiàn)

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

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

struct FSnode

{ unsigned int *id；// 存儲項集的名字

unsigned int support；// 項集的支持度

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

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

FSnode *right；指向與本節(jié)點的id有相同長度的另一個項集對應(yīng)的節(jié)點

}；

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

struct FPnode

{ unsigned int name；// 是1-size項集名稱

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

set *child；//指向其后繼節(jié)點

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

}；

算法、輸入、輸出方法：

Algorithm FP-Mine()

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

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

{ ⑴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é)點；

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

}

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

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

6 結(jié)束語

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

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

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

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

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

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

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