基于Web信息挖掘的關聯推薦算法研究與實現

福建省科學技術信息研究所 張章學

?

基于Web信息挖掘的關聯推薦算法研究與實現

福建省科學技術信息研究所 張章學

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

Web數據挖掘 關聯推薦算法 個性化內容服務

1 概述

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

2 關于Web數據挖掘技術

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

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

3 關聯推薦算法思路分析

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

4 算法分析與實現

4.1 頻繁訪問路徑圖的生成

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

4.2 推薦集的計算

首先從聚集圖關聯推薦服務算法中發現關聯規則，并且這個關聯規則匹配用戶訪問路徑，再確定推薦項，這個過程是根據推薦度因子的大小來實現的，其中推薦度因子是指距離因子乘以關聯規則的置信度。對用戶訪問路徑的獲取采用滑窗采樣，對用戶的訪問操作進行有效的實時跟蹤，可以實現在線推薦。滑窗采樣是用戶訪問路徑滑窗覆蓋為W去匹配聚集圖上的子訪問路徑，從而獲取頻繁子訪問路徑，所有長度為 W＋1。

收集和分析用戶信息、進行推薦、產生推薦結果等都屬于個性化推薦系統，它們可以分為在線和離線兩個部分。

（1）在線部分：根據支持數的大小對用戶當前的訪問頁面序列進行排序，關聯規則的前項在規則集中尋找相匹配的規則，推薦給用戶推薦度在前TOP_N個的網頁。

（2）離線部分：該部分用于對用戶信息的收集和分析，進行數據預處理用戶之前的訪問日志歷史，把它轉變為純凈的適合挖掘的數據，興趣訪問模式的獲取是對該用戶訪問頁面之間的關聯規則采用關聯規則挖掘算法FP-Mine算法進行挖掘。 Web個性化推薦系統體系結構圖示意圖如下：

4.3 算法實現

FP-Mine挖掘算法使關聯規則的挖掘效率得到了很大提高，它不僅能夠尋找頻繁訪問模式集，而且給出關聯規則的方法。算法實現如下：

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

struct FSnode

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

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

double confidence；// i-size節點中關聯規則(p p …p =>p)的置信度

FSnode *left；// 指向比本節點的id長度增1的一個超集對應的節點

FSnode *right；指向與本節點的id有相同長度的另一個項集對應的節點

}；

每個節點在樹中的結構：

struct FPnode

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

unsigned int support；// 為其計數域

set *child；//指向其后繼節點

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

}；

算法、輸入、輸出方法：

Algorithm FP-Mine()

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

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

{ ⑴for each itemin i-size

①P_Insert()；/*生成i-size 和(i+1)-size的Freq-Set-Tree并生成相應的關聯規則*/

⑵從Freq-Set-Tree中釋放所有i-size節點；

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

}

5 在商業網站中的應用價值分析

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

6 結束語

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

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

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

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

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

[5] 何小東,劉衛國.數據挖掘中關聯規則挖掘算法比較研究[J].計算機工程與設計,2005,26(5):1265-1268.

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