一種基于用戶訪問行為的推薦系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

祝燕冠中，何洪波，肖云

1.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100190

2.中國科學(xué)院大學(xué)，北京 100049

一種基于用戶訪問行為的推薦系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

祝燕冠中1,2，何洪波1，肖云1

1.中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100190

2.中國科學(xué)院大學(xué)，北京 100049

本文基于“中國科普博覽”網(wǎng)站 Web日志數(shù)據(jù)，設(shè)計(jì)和實(shí)現(xiàn)了一種推薦系統(tǒng)的原型。該系統(tǒng)主要包括數(shù)據(jù)預(yù)處理模塊，基于改進(jìn)型 FP-growth 算法設(shè)計(jì)的頻繁項(xiàng)集挖掘模塊，以及基于滑動窗口設(shè)計(jì)的推薦模型模塊。改進(jìn)型 FP-growth 算法利用頁面訪問次數(shù)與頁面停留時(shí)間組成的權(quán)值，產(chǎn)生更符合挖掘需求的頻繁項(xiàng)集。

Web日志挖掘；關(guān)聯(lián)規(guī)則挖掘；FP-growth 算法；推薦系統(tǒng)；滑動窗口

引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上積累的信息越來越多，信息的種類也越來越復(fù)雜，人們面對太多的復(fù)雜信息無從選擇，這種現(xiàn)象被稱為信息過載。另一方面，互聯(lián)網(wǎng)上分布于各個(gè)網(wǎng)站中的種類繁多的信息資源，也為用戶找到自己感興趣的信息增加了諸多困難，這便是信息迷失。為了解決這些問題，許多大型網(wǎng)站建立了推薦系統(tǒng)[1-2]，以對用戶未來的訪問行為做出一定的預(yù)測并為用戶提供訪問建議。

目前應(yīng)用于資訊類網(wǎng)站的推薦系統(tǒng)[3-4]已有不少，但應(yīng)用于科普類網(wǎng)站的推薦系統(tǒng)并不常見，應(yīng)用于資訊類網(wǎng)站的推薦系統(tǒng)對于科普類網(wǎng)站而言，由于新聞信息和科普內(nèi)容具有較大的差異性[5]，用戶的訪問行為和目的大相徑庭，因此僅具有借鑒意義，卻不能完全適用，這就使得為科普類網(wǎng)站建立一個(gè)推薦系統(tǒng)更具意義[6]?！爸袊破詹┯[”網(wǎng)站 (http://www.kepu.net.cn) 是我國最早啟動的大型綜合性科普網(wǎng)站之一，在科普領(lǐng)域具有廣泛地影響力，本文將以“中國科普博覽”網(wǎng)站的 Web日志數(shù)據(jù)為基礎(chǔ)，為網(wǎng)站設(shè)計(jì)并實(shí)現(xiàn)一套推薦系統(tǒng)原型，幫助網(wǎng)站提升用戶體驗(yàn)，增加用戶訪問量，促進(jìn)網(wǎng)站更好地發(fā)展。

1 推薦系統(tǒng)基本架構(gòu)設(shè)計(jì)

推薦系統(tǒng)的基本框架包括數(shù)據(jù)預(yù)處理模塊、數(shù)據(jù)挖掘分析模塊以及用戶推薦模塊。其中，數(shù)據(jù)預(yù)處理模塊主要完成 Web日志中干擾數(shù)據(jù)的剔除、多個(gè) Web日志文件的歸并以及用戶識別和會話識別的工作，最終生成可用于關(guān)聯(lián)規(guī)則挖掘的事務(wù)數(shù)據(jù)集；數(shù)據(jù)挖掘分析模塊主要完成對事物數(shù)據(jù)集的關(guān)聯(lián)規(guī)則挖掘，并產(chǎn)生多項(xiàng)頻繁項(xiàng)集用于用戶推薦；用戶推薦模塊主要是根據(jù)之前產(chǎn)生的多項(xiàng)頻繁項(xiàng)集以及定義的推薦規(guī)則為用戶產(chǎn)生推薦集，使用戶擁有更好地瀏覽體驗(yàn)。下圖展示了推薦系統(tǒng)的基本框架設(shè)計(jì)圖：

圖1 推薦系統(tǒng)基本架構(gòu)圖Fig.1 Basic architecture of the recommended system

2 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理[7]是 Web日志挖掘的基礎(chǔ)內(nèi)容，之后的頻繁項(xiàng)集挖掘和用戶推薦都是建立在其基礎(chǔ)上的，因此也是推薦系統(tǒng)中的重要部分之一。進(jìn)行數(shù)據(jù)預(yù)處理首先要獲取網(wǎng)站多個(gè)服務(wù)器上的 Web日志，這是由于網(wǎng)站采用負(fù)載均衡的方式，運(yùn)行有多臺服務(wù)器。獲取到的 Web日志格式如下所示：

每條日志中包含9項(xiàng)信息，依次為訪問主機(jī) (remotehost)、標(biāo)識符 (Ident)、授權(quán)用戶 (authuser)、日期時(shí)間 (data)、請求 (request)、狀態(tài)碼 (status)、傳輸字節(jié)數(shù) (bytes)、來源頁面 (referrer) 和用戶代理 (useragent)。其中標(biāo)識符和授權(quán)用戶項(xiàng)目前絕大部分的網(wǎng)站 Web日志均不進(jìn)行記錄。下面將分別介紹數(shù)據(jù)預(yù)處理的四個(gè)步驟。

2.1 數(shù)據(jù)清洗

數(shù)據(jù)清洗階段主要去除 Web日志數(shù)據(jù)中的干擾數(shù)據(jù)，為之后的數(shù)據(jù)挖掘做準(zhǔn)備。在數(shù)據(jù)清洗中會按照以下規(guī)則進(jìn)行：

(1) 根據(jù)訪問主機(jī) (remotehost) 項(xiàng)判斷訪問主機(jī)的 IP 段是否為網(wǎng)站的內(nèi)部 IP，如果是將內(nèi)部人員的訪問記錄剔除，以免其影響對其他用戶訪問行為的挖掘分析。

(2) 根據(jù)請求 (request) 項(xiàng)首先判斷請求類型 (METHOD) 是否為 GET 類型的，如果不是則直接剔除；其次再對請求資源 (RESOURCE) 即 URL 進(jìn)行解析，判斷并剔除嵌入式文件，例如 png、js、swf 等文件；最后仍然是對 URL 進(jìn)行判斷，將 URL 為 404.html 等的錯(cuò)誤頁面也剔除。

(3) 根據(jù)狀態(tài)碼 (status) 項(xiàng)判斷服務(wù)器對一條資源請求的響應(yīng)，從中刪除請求失敗的日志記錄。例如301 (永久刪除) 、400 (請求錯(cuò)誤) 、501 (未被實(shí)現(xiàn)) 等失敗的記錄會被剔除，它們會對數(shù)據(jù)挖掘產(chǎn)生影響。

(4) 根據(jù)用戶代理 (useragent) 中的爬蟲標(biāo)記刪除搜索引擎、排名網(wǎng)站、實(shí)驗(yàn)室科研項(xiàng)目等非正常用戶產(chǎn)生的訪問記錄，從而避免它們影響正常用戶行為的挖掘分析。一般的爬蟲標(biāo)識會包含 spider、bot、crawler、monitor 等關(guān)鍵字信息。

2.2 數(shù)據(jù)歸并與排序

在數(shù)據(jù)清洗之后，會對多臺服務(wù)器產(chǎn)生的 Web日志進(jìn)行歸并，而每個(gè) Web日志文件中的記錄并不是完全按照時(shí)間序排列的，因此，在歸并的同時(shí)還要對其按時(shí)間序進(jìn)行排序。完成數(shù)據(jù)歸并與排序后，會得到按時(shí)間有序的完整的 Web日志記錄。

2.3 用戶識別

用戶識別使用 Web日志中的訪問主機(jī) (remotehost)的IP和用戶代理 (useragent) 來判斷哪些 Web日志記錄來自同一個(gè)用戶的訪問。但是這樣的用戶識別是有一定的誤判在其中的，而由于這樣的情況并不常見，故在大量的正常情況的數(shù)據(jù)中可以削減掉這些特殊情況的影響。

2.4 會話識別

會話識別一般理解為識別用戶在網(wǎng)站上的一次訪問過程，在這一過程中用戶對網(wǎng)站的瀏覽行為是不間斷的。通常根據(jù) Web日志記錄中的日期時(shí)間 (data)項(xiàng)進(jìn)行判斷，認(rèn)為用戶會在一個(gè)時(shí)間閥值內(nèi)完成一次網(wǎng)站的訪問過程，而超出這一時(shí)間閥值后的該用戶的Web日志記錄會被認(rèn)為是另外一個(gè)會話，本文根據(jù)需要設(shè)置的時(shí)間閥值為 60 分鐘，并加入動態(tài)的判斷方式，改善判斷的準(zhǔn)確性。

在進(jìn)行會話識別的同時(shí)，會識別惡意爬蟲，使用基于以下規(guī)則的啟發(fā)式識別模式。正常的用戶在訪問并瀏覽一個(gè)網(wǎng)頁時(shí)需要花費(fèi)一定的時(shí)間，因此，我們在會話識別的同時(shí)會對一個(gè)會話中同一用戶的連續(xù)多條訪問記錄中的每相鄰兩條的時(shí)間間隔進(jìn)行統(tǒng)計(jì)，如果有超過半數(shù)的時(shí)間間隔均不超過 2 秒的話，則認(rèn)定該用戶的這一次會話為網(wǎng)絡(luò)爬蟲的記錄。并且，即便這部分記錄是正常用戶的訪問，那么在這么短的時(shí)間內(nèi)頻繁的點(diǎn)擊網(wǎng)頁的行為也不會很好的反應(yīng)一個(gè)用戶的真實(shí)行為，將其加入挖掘分析也會對整體的分析結(jié)果造成影響，因此將其剔除掉。在完成數(shù)據(jù)預(yù)處理的四個(gè)步驟后，將得到完整的事務(wù)數(shù)據(jù)集。

3 核心算法設(shè)計(jì)

在網(wǎng)站推薦系統(tǒng)的設(shè)計(jì)中，其核心的內(nèi)容是利用數(shù)據(jù)預(yù)處理后的事務(wù)數(shù)據(jù)集挖掘頻繁項(xiàng)集，再根據(jù)頻繁項(xiàng)集生成推薦集，本節(jié)中將詳細(xì)介紹這兩個(gè)部分的內(nèi)容，即用于挖掘頻繁項(xiàng)集的改進(jìn)型 FP-growth 算法和基于滑動窗口的推薦模型設(shè)計(jì)。下面給出本節(jié)所涉及的一些概念，這些概念在許多有關(guān)數(shù)據(jù)挖掘的文獻(xiàn)和著作[8]中均有給出，這里將它們概述如下：

設(shè)I= {i1，i2，…，im} 是m個(gè)不同項(xiàng)的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù) D 為數(shù)據(jù)庫事務(wù)的集合，其中每一個(gè)事務(wù)T是一個(gè)非空的項(xiàng)集，即中的每個(gè)事務(wù)均有一個(gè)唯一的標(biāo)識符，記作 TID。設(shè)X是一個(gè)項(xiàng)集，事務(wù)T包含X，當(dāng)且僅當(dāng)

項(xiàng)集：項(xiàng)的集合稱為項(xiàng)集。包含 k 個(gè)項(xiàng)的集合稱為k項(xiàng)集。如果項(xiàng)集 X 的相對支持度滿足最小支持度閥值，則稱 X 為頻繁項(xiàng)集。頻繁 k 項(xiàng)集的集合通常記作 Lk。

在調(diào)研挖掘關(guān)聯(lián)規(guī)則的算法 Apriori 算法[9]、FP-growth 算法[10]和 Eclat 算法[11]，以及一些對它們的改進(jìn)算法[12]后，對主要的幾種算法進(jìn)行對比。發(fā)現(xiàn)最早開始被廣泛使用的挖掘關(guān)聯(lián)規(guī)則的算法是 Apriori算法，之后由于該算法的挖掘效率較低，因此出現(xiàn)了FP-growth 算法，F(xiàn)P-growth 算法的效率大致可以比Apriori 算法高一個(gè)數(shù)量級。而 Eclat 算法則是與另外的兩個(gè)算法不同的一類算法，該算法是對事務(wù)數(shù)據(jù)集進(jìn)行縱向挖掘的，而其他兩個(gè)算法則是進(jìn)行橫向挖掘的，因此挖掘的角度是不同的，挖掘的需求與挖掘的結(jié)果也是不同的。在本文對基于關(guān)聯(lián)規(guī)則的挖掘算法進(jìn)行挖掘效率和挖掘目的等方面的考慮之后，決定使用 FP-growth 算法進(jìn)行挖掘，同時(shí)對 FP-growth 算法進(jìn)行改進(jìn)，使之更適合本文的挖掘任務(wù)，下面將進(jìn)行詳細(xì)的介紹。

3.1 改進(jìn)型 FP-growth 算法

本文以“中國科普博覽”網(wǎng)站的 Web日志數(shù)據(jù)作為研究對象。由于中國科普博覽網(wǎng)站的頁面?zhèn)€數(shù)較多，涉及的內(nèi)容領(lǐng)域也很廣，用戶訪問特別分散，造成支持度要確定很低才可以發(fā)現(xiàn)滿足支持度的關(guān)聯(lián)規(guī)則。因此本文將針對“中國科普博覽”網(wǎng)站 Web日志特點(diǎn)，引入權(quán)值到算法當(dāng)中，以改善挖掘關(guān)聯(lián)規(guī)則支持度很低的情況，也可以利用加入的權(quán)值挖掘到更加符合用戶實(shí)際需求的關(guān)聯(lián)規(guī)則。通?；陉P(guān)聯(lián)規(guī)則挖掘的算法中只關(guān)注一個(gè)頁面被訪問的次數(shù)，當(dāng)次數(shù)達(dá)到一定的閥值時(shí)，其就會被認(rèn)定為頻繁的。但是有一些頁面的訪問頻率并不高而被用戶瀏覽的時(shí)間卻很長，這些頁面通常是用戶最感興趣的頁面，但這些頁面在未改進(jìn)的算法中沒有被列入頻繁項(xiàng)集，造成推薦的項(xiàng)集丟失了這些重要頁面。因此本文將在算法中加入權(quán)值，從而使這些頁面可以進(jìn)入到頻繁項(xiàng)集中，并可以被用于推薦。

改進(jìn)型的 FP-growth 算法的關(guān)鍵在于頁面權(quán)值的設(shè)置，為了將用戶對頁面的瀏覽時(shí)間作為一個(gè)頻繁項(xiàng)集的產(chǎn)生因素加入到算法的運(yùn)算中，因此使用相對頁面訪問次數(shù)與相對頁面停留時(shí)間組成頁面權(quán)值，參與算法的運(yùn)算，下面將給出用于權(quán)值計(jì)算的幾個(gè)變量的定義：

相對頁面訪問次數(shù)：是指在一天內(nèi)同一頁面被不同用戶所訪問的總次數(shù)與所有頁面的總訪問次數(shù)的平均值的比值，因?yàn)橐粋€(gè)頁面被用戶訪問的次數(shù)越多，就說明該頁面越受用戶偏愛，其計(jì)算公式如下：

其中，visit(i)是指一天內(nèi)同一頁面i被所有用戶訪問的總次數(shù)，集合I是這一天中所有被訪問的頁面集，則 |I| 是集合中元素的個(gè)數(shù)。

相對頁面停留時(shí)間：是指在一天內(nèi)同一頁面被訪問的平均時(shí)間與所有頁面被訪問的平均時(shí)間的比值，同理，一個(gè)頁面被用戶瀏覽的時(shí)間越長，那么該頁面就越受偏愛，其計(jì)算公式如下：

其中，totalDura(i) 是指一天內(nèi)同一頁面i被所有用戶瀏覽的總時(shí)長。而頁面停留時(shí)間的計(jì)算則是根據(jù)一個(gè)事務(wù)中連續(xù)的兩個(gè)被訪問的 URL 之間的時(shí)間間隔確定的。但是，對于那些在一個(gè)事務(wù)中作為最后一個(gè)被訪問的頁面，由于其無法計(jì)算時(shí)間間隔，因此將其頁面停留時(shí)間使用對該頁面的平均頁面停留時(shí)間來代替。

頁面權(quán)值：本文使用如下公式計(jì)算頁面權(quán)值，即對相對頁面訪問次數(shù)與相對頁面停留時(shí)間使用兩個(gè)參數(shù)進(jìn)行協(xié)調(diào)之后相加獲取，在公式中加入兩個(gè)參數(shù)變量 a 和 b，其中 a 和 b 的取值范圍在 0 到1 之間：

對于 a 和 b 這兩個(gè)參數(shù)的設(shè)置可以表現(xiàn)出對于頁面訪問次數(shù)和頁面停留時(shí)間這個(gè)兩個(gè)因素的重視程度，對于哪個(gè)因素更加重視，可以將哪個(gè)因素前面的那個(gè)參數(shù)相應(yīng)的調(diào)大即可。為了使頁面停留時(shí)間得到足夠的重視，并使相對頁面訪問次數(shù)與相對頁面停留時(shí)間得到相對的平衡，本文中將使用 a = 0.3，b = 0.7來計(jì)算頁面權(quán)值。

相對頁面權(quán)值：取所有頁面權(quán)值中的最大值，記作 maxW，之后將所有的頁面權(quán)值除以 maxW 的一半，從而使所有的頁面權(quán)值集中到0 到2 的區(qū)間范圍內(nèi)，其公式如下：

本文將使用相對頁面權(quán)值來代替支持度計(jì)數(shù)，即將算法中事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)出現(xiàn)一次，其支持度計(jì)數(shù)加一，變?yōu)橹С侄扔?jì)數(shù)增加一個(gè)相對頁面權(quán)值。因此，在算法運(yùn)算時(shí)要給出一個(gè)新的最小支持度閥值，其大小是與相對頁面權(quán)值相適應(yīng)的。

相應(yīng)的，對于支持度與置信度的計(jì)算，都要做出相應(yīng)的改變，均將原有使用支持度計(jì)數(shù)的地方改為使用相對頁面權(quán)值進(jìn)行計(jì)算。

我們重新定義用于支持度和置信度計(jì)算的項(xiàng)集的概率P(A)，原本的P(A) 是項(xiàng)集A在事務(wù)數(shù)據(jù)集中出現(xiàn)的概率，現(xiàn)在重新定義，記項(xiàng)集A中各項(xiàng)的相對頁面權(quán)值里最小的一個(gè)為 minWeight(A)，記事務(wù)數(shù)據(jù)集中所有頁面的相對頁面權(quán)值的均值為 aveW，則重新定義的P(A) 如下：

其中，|A|為項(xiàng)集A中項(xiàng)的個(gè)數(shù)，|I| 為所有項(xiàng)的個(gè)數(shù)。

因此，P(A∪B) 的定義為：

則對于支持度和置信度的計(jì)算也可以根據(jù)項(xiàng)集的概率進(jìn)行相應(yīng)的計(jì)算。

在算法的計(jì)算流程上，與 FP-growth 算法基本相同，不同的地方在于使用相對頁面權(quán)值代替支持度計(jì)數(shù)進(jìn)行計(jì)數(shù)操作。由于每個(gè)頁面均設(shè)有自己的相對頁面權(quán)值，因此需要單獨(dú)設(shè)置一張事務(wù)數(shù)據(jù)集中的數(shù)據(jù)項(xiàng)與相對頁面權(quán)值相對應(yīng)的表，以供算法運(yùn)算時(shí)查找使用。下面分別給出 FP-tree 構(gòu)建流程圖與 FP-growth算法挖掘流程圖：

3.2 推薦模型設(shè)計(jì)

圖2 FP-tree 構(gòu)建流程圖Fig.2 Flow chartof FP-tree construction

圖3 改進(jìn)型 FP-growth 算法流程圖Fig.3 Improved Fp-tree algorithmflow chart

在根據(jù)改進(jìn)型 FP-growth 算法產(chǎn)生頻繁項(xiàng)集后，將根據(jù)一定的推薦規(guī)則從頻繁項(xiàng)集中產(chǎn)生推薦集，而推薦模型的主要目的正是根據(jù)推薦規(guī)則產(chǎn)生推薦。本文主要基于滑動窗口設(shè)計(jì)推薦模型，滑動窗口用于選取用戶的部分訪問記錄，將其與頻繁項(xiàng)集匹配，并依據(jù)最小置信度閥值產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。再依據(jù)置信度的大小對強(qiáng)關(guān)聯(lián)規(guī)則排序，在每條規(guī)則內(nèi)部則依據(jù)相對頁面權(quán)值進(jìn)行排序，最后組合這些強(qiáng)關(guān)聯(lián)規(guī)則成頁面集，去除其中重復(fù)的頁面，即可得到推薦集。本節(jié)將重點(diǎn)介紹置信度的計(jì)算與滑動窗口的設(shè)置。下面給出本節(jié)中所涉及概念的定義：

(1) 置信度：

置信度[8]是指事務(wù)數(shù)據(jù)集 D 中同時(shí)包含項(xiàng)集 X和項(xiàng)集 Y 的事務(wù)占包含項(xiàng)集 X 的事務(wù)的百分比。其體現(xiàn)了關(guān)聯(lián)規(guī)則的可靠性，即置信度越高，Y 在包含X 的事務(wù)中出現(xiàn)的可能性就越大，則關(guān)聯(lián)規(guī)則的置信度就越強(qiáng)。而同時(shí)滿足最小支持度閥值 (min_sup) 和最小置信度閥值 (min_conf) 的關(guān)聯(lián)規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。通常置信度的定義為：

其中，X和Y均為非空的項(xiàng)集，他們可能包含一個(gè)或一個(gè)以上的數(shù)據(jù)項(xiàng)，是事務(wù)數(shù)據(jù)集中項(xiàng)集I的子集。support(X) 是項(xiàng)集X的支持度，support_count(X)是項(xiàng)集X的支持度計(jì)數(shù)。

對于本文而言，由于將相對頁面權(quán)值relaW(i) 替換了支持度計(jì)數(shù)，因此，需要對置信度的公式進(jìn)行重新的定義。對應(yīng)于每一項(xiàng)的相對頁面權(quán)值relaW(i)，這里給出項(xiàng)集X的相對頁面權(quán)值：

relaW(X)=min(relaW(i))，其中i是項(xiàng)集X中的任意一項(xiàng)

其表示項(xiàng)集的相對頁面權(quán)值是項(xiàng)集中各項(xiàng)的相對頁面權(quán)值中的最小一個(gè)。而項(xiàng)集X∪Y的相對頁面權(quán)值則可以表示為：

relaW(X∪Y)=min(relaW(i) )，其中 i 是項(xiàng)集X∪Y中的任意一項(xiàng)

則相應(yīng)的置信度可以表示為：

一般而言，關(guān)聯(lián)規(guī)則的挖掘分為兩步，首先是根據(jù)定義找出滿足要求的所有頻繁項(xiàng)集，即這些頻繁項(xiàng)集的所有非空子集在事務(wù)數(shù)據(jù)庫中的出現(xiàn)次數(shù)至少要達(dá)到最小支持度計(jì)數(shù)的要求；其次是從這些頻繁項(xiàng)集中找出強(qiáng)關(guān)聯(lián)規(guī)則，即這些規(guī)則必須同時(shí)滿足最小支持度閥值與最小置信度閥值，才可以被認(rèn)定為強(qiáng)關(guān)聯(lián)規(guī)則。而后一步也正是確定推薦集中較為重要的一步，是本節(jié)的主要內(nèi)容。

(2) 滑動窗口設(shè)置

推薦模型的設(shè)計(jì)是基于滑動窗口的，對于滑動窗口的設(shè)置[13]，一般將大小設(shè)置為 2 到4 個(gè)頁面為宜。本文將滑動窗口的大小設(shè)置為3。對于用戶訪問記錄數(shù)不足滑動窗口大小的，則直接使用所有記錄與頻繁項(xiàng)集進(jìn)行匹配。對于滿足和超過滑動窗口大小的，則根據(jù)滑動窗口的大小選擇最近的訪問記錄與頻繁項(xiàng)集匹配。如果無法匹配到合適的頻繁項(xiàng)集，則會將滑動窗口擴(kuò)大一個(gè)，從而選取4個(gè)頁面，并對這4個(gè)頁面進(jìn)行組合，產(chǎn)生4組3個(gè)頁面的組合，從中除去一個(gè)已經(jīng)匹配失敗的3個(gè)頁面的頁面集組合，還會產(chǎn)生3組新的3個(gè)頁面的頁面集組合，并依次使用它們與頻繁項(xiàng)集進(jìn)行對比。如果可以匹配到合適的頻繁項(xiàng)集，則按照之前的匹配成功的推薦規(guī)則進(jìn)行用戶推薦。否則，再次修改滑動窗口的大小，將其大小降為2，選取用戶最近的兩條訪問記錄進(jìn)行頻繁項(xiàng)集的對比。如果成功，則可以產(chǎn)生推薦，反之則繼續(xù)對滑動窗口的大小進(jìn)行修改，并依次進(jìn)行與頻繁項(xiàng)集的對比，直到無法產(chǎn)生合適的滑動窗口，則會按照新用戶的推薦規(guī)則產(chǎn)生推薦。而繼續(xù)對滑動窗口的大小進(jìn)行修改的規(guī)則為，首先依次增大滑動窗口，并將選中的頁面集組合為大小為3的小頁面集，其次，將這些大小為3的頁面集剔除之前已經(jīng)參與過對比的頁面集的組合，使用新組合成的頁面集進(jìn)行對比，最后，如果對比成功，則可以產(chǎn)生推薦，否則，循環(huán)進(jìn)行滑動窗口的修改。但是，由于這樣不斷地修改滑動窗口的大小，并不斷的對比頻繁項(xiàng)集，會消耗大量的時(shí)間，因此考慮到一種平衡的方法，即設(shè)置一個(gè)計(jì)時(shí)器，當(dāng)計(jì)算用時(shí)超出規(guī)定的時(shí)間閥值時(shí)，會結(jié)束與頻繁項(xiàng)集的匹配，并以用戶訪問記錄中最近一個(gè)可以產(chǎn)生的強(qiáng)關(guān)聯(lián)規(guī)則的訪問頁面為依據(jù)，產(chǎn)生推薦集作為用戶推薦使用，并結(jié)束整個(gè)運(yùn)算。

4 推薦系統(tǒng)原型的實(shí)現(xiàn)與效果

基于上述研究，作者設(shè)計(jì)和實(shí)現(xiàn)了 “中國科普博覽”網(wǎng)站的推薦系統(tǒng)原型，主要包含數(shù)據(jù)預(yù)處理模塊、數(shù)據(jù)挖掘分析模塊以及用戶推薦模塊。其中數(shù)據(jù)預(yù)處理模塊完成Web日志的清洗等工作，并最終生成事務(wù)數(shù)據(jù)集；數(shù)據(jù)挖掘分析模塊使用改進(jìn)的FP-growth算法，將頁面訪問次數(shù)與頁面停留時(shí)間組合后融入算法的運(yùn)算中，并最終生成頻繁項(xiàng)集；用戶推薦模塊使用滑動窗口選取用戶部分訪問記錄，與頻繁項(xiàng)集匹配后，根據(jù)最小置信度閥值產(chǎn)生推薦集，為用戶推薦。

為了驗(yàn)證推薦系統(tǒng)的效果，作者邀請了10位用戶對推薦系統(tǒng)原型進(jìn)行了模擬使用。在測試過程中，分別使用了基于FP-grow算法的推薦和基于改進(jìn)型的FP-growth算法進(jìn)行推薦，請測試用戶對推薦結(jié)果進(jìn)行顯性評價(jià)，從而分析對比推薦系統(tǒng)的效果。在模擬使用過程中，用戶并不知曉推薦集對應(yīng)的算法。用戶評價(jià)經(jīng)轉(zhuǎn)化為對應(yīng)算法后，結(jié)果如下圖所示：

圖4 用戶測試結(jié)果圖Fig.4 User test result chart

從實(shí)驗(yàn)結(jié)果來看，基于改進(jìn)型 FP-growth 算法的推薦系統(tǒng)在一定程度上產(chǎn)生了較好的效果。其中，認(rèn)為原 FP-growth 算法效果較好的為2人，認(rèn)為基本一致的為3人，認(rèn)為改進(jìn)型 FP-growth 算法較好的為 5人，50% 以上的用戶認(rèn)為基于改進(jìn)型 FP-growth 算法的推薦具有更好的效果。但是由于參與評價(jià)實(shí)驗(yàn)的人數(shù)較少，評價(jià)結(jié)果有一定的局限性。今后可以進(jìn)行更大規(guī)模的測試，從而更準(zhǔn)確的評價(jià)推薦系統(tǒng)的效果。

5 結(jié)語

本文以“中國科普博覽”網(wǎng)站的Web日志數(shù)據(jù)為研究對象，為網(wǎng)站設(shè)計(jì)了與其自身特點(diǎn)相符合的推薦系統(tǒng)原型，以幫助網(wǎng)站改善用戶體驗(yàn)，并獲取更多的用戶訪問。經(jīng)過小范圍的測試試驗(yàn)，該推薦系統(tǒng)獲得了預(yù)期效果。由于本文的時(shí)間有限，推薦系統(tǒng)原型的設(shè)計(jì)也存在一定的局限性，在后續(xù)的設(shè)計(jì)中可以加入針對 Web 內(nèi)容的挖掘，從而使推薦系統(tǒng)獲得更好地效果。

[1]洪亮,任秋圜,梁樹賢.國內(nèi)電子商務(wù)網(wǎng)站推薦系統(tǒng)信息服務(wù)質(zhì)量比較研究——以淘寶、京東、亞馬遜為例[J].圖書情報(bào)工作.2016,60(23): 97 - 110.

[2]徐海玲,吳瀟,李曉東,閻保平.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報(bào).2009,20(2): 350-362.

[3]孫曉會.基于用戶行為的個(gè)性化新聞推薦系統(tǒng)研究[D].成都：電子科技大學(xué),2015.

[4]曹一鳴.基于協(xié)同過濾的個(gè)性化新聞推薦系統(tǒng)的研究與實(shí)現(xiàn)[D].北京：北京郵電大學(xué),2013.

[5]王盛.從“今日頭條”看個(gè)性化推薦時(shí)代信息生態(tài)的演變與挑戰(zhàn)[D].保定：河北大學(xué),2016.

[6]楊麗芳.基于Web日志的“中國科普博覽”網(wǎng)站用戶行為分析[D].北京: 中國科學(xué)院大學(xué),2016.

[7]李中良.基于Web日志挖掘和關(guān)聯(lián)規(guī)則的個(gè)性化推薦系統(tǒng)模型研究[D].重慶：西南大學(xué),2014.

[8]Jiawei Han,Micheline Kamber,Jian Pei.數(shù)據(jù)挖掘：概念與技術(shù) (第3版)[M],范明,孟小峰.北京：機(jī)械工業(yè)出版社,2012.

[9]Lazcorreta E,Botella F,Fernandez-Caballero A.Towards personalized recommendation by two-step modified Apriori data mining algorithm[J].Expert Systems with Applications,2008,35(3): 1422-1429.

[10]Mishra R,Choubey A.Discovery of frequent patterns from web log data by using FP-growth algorithm for web usage mining[J].International Journal of Advanced Research in Computer Science and Software Engineering,2012,2(9):311 - 318.

[11]Yu X,Wang H.Improvement of Eclat algorithm based on support in frequent itemset mining[J].Journal of Computers,2014,9(9): 2116-2124.

[12]Zang J,Li W J,Chen J H,et al.Research and Application on Hybrid-weighted Association Rule Algorithm[J].DEStech Transactions on Computer Science and Engineering,2016 (iceiti): 706 - 710.

[13]Saddys Segrera,Maria N.Moreno.An experimental comparative study of web mining methods for recommender systems[C].Proceedings of the 6th WSEAS International Conference on Distance Learning and Web Engineering,Lisbon,Portugal,September 22 - 24,2006:56 – 61.

A Design and Implementation of Recommendation System Based on User’s Visiting Behavior

Zhu Yanguanzhong1,2,He Hongbo1,Xiao Yun1

1.Computer Network Information Center,Chinese Academy of Sciences,Beijing 100190,China
2.University of the Chinese Academy of Sciences,Beijing 100049,China

The paper based on “Science Museums of China” website log designsandimplements a recommendation system prototype.The system mainly includes data preprocessing module,frequent itemset mining module based on the modi fied FP-growth algorithm,and recommendation model modulebased on sliding window.The modi fied FP-growth algorithm takes advantage ofthe weightwhichconsists of the page visit times and the page dwell time to generate the frequent itemset whichis more satis fied for the demand of mining.

Web log mining; association rules mining; FP-growth algorithm; recommendation system; sliding window

10.11871/j.issn.1674-9480.2017.02.003

2017年1月7日

祝燕冠中：中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，碩士研究生，主要研究方向?yàn)樾旅襟w技術(shù)應(yīng)用。

E-mail:hnkfzygz@qq.com

何洪波：中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心、高級工程師，主要研究方向?yàn)樾旅襟w技術(shù)應(yīng)用、數(shù)據(jù)挖掘與信息推薦。

E-mail:hhb@cnic.cn

肖 云：中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，正研級高級工程師，主要研究方向?yàn)樾旅襟w科學(xué)傳播、科普教育技術(shù)與應(yīng)用、科普融合創(chuàng)作與傳播。

E-mail:xy@cnic.cn