基于群體智慧的Web訪問日志會話主題識別研究

方 奇，劉奕群，張 敏，茹立云，馬少平

(智能技術(shù)與系統(tǒng)國家重點(diǎn)實驗室 清華信息科學(xué)與技術(shù)國家實驗室(籌)，清華大學(xué) 計算機(jī)系，北京 100084)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，Web上存儲的信息量日新月異。如今萬維網(wǎng)已經(jīng)成為人們獲取信息的重要來源。據(jù)最新CNNIC統(tǒng)計報告顯示[1]，截止2009年底，中國網(wǎng)民規(guī)模已達(dá)3.84億人，網(wǎng)站數(shù)量達(dá)到323萬個，繼續(xù)平穩(wěn)增長。與此同時，主流搜索引擎公司如谷歌(http://toolbar.google.com/)、雅虎(http://toolbar.yahoo.com/)、百度(http://bar.baidu.com/)、微軟(http://toolbar.live.com/)等都通過瀏覽器工具欄基于匿名策略收集用戶的Web訪問行為數(shù)據(jù)，以便為工具欄用戶提供更多個性化的增值服務(wù)。近來，Web訪問日志的使用挖掘成為了研究界和產(chǎn)業(yè)界關(guān)注的熱點(diǎn)，基于Web訪問日志的用戶行為分析被廣泛應(yīng)用于搜索引擎算法改進(jìn)[2-3]，競價廣告投放[4]，作弊頁面識別[5]等方面的工作中。

Web訪問日志中包含了大量的點(diǎn)擊信息，將其劃分成能體現(xiàn)用戶意圖的合適的處理單元是進(jìn)行后續(xù)挖掘分析工作的基礎(chǔ)。所謂用戶意圖，是指用戶在訪問Web資源之前或過程中產(chǎn)生并伴隨著整個訪問過程的意識動機(jī)。用戶意圖指導(dǎo)用戶的操作行為，同時也會在訪問過程中進(jìn)行轉(zhuǎn)變。作為一種被廣泛應(yīng)用的處理單元形式，傳統(tǒng)的會話(session)在體現(xiàn)用戶意圖上往往粒度太粗： 要么只考慮了用戶和時間的因素，完全沒有考慮用戶意圖的限制，要么雖然考慮了用戶意圖的限制，但是作為由連續(xù)操作構(gòu)成的序列，無法處理意圖交叉的情況。其中，意圖交叉是指用戶在一段時間內(nèi)根據(jù)兩個或兩個以上的意圖進(jìn)行訪問，意圖對應(yīng)的操作記錄交叉出現(xiàn)的情況。基于上述原因，我們有必要在會話的基礎(chǔ)上做進(jìn)一步的細(xì)化，識別出與用戶意圖有關(guān)的更合適的處理單元。

本文基于Web訪問日志完善了一套與用戶意圖相關(guān)的概念體系，認(rèn)為會話(session)是與用戶、時間相關(guān)的操作序列，將主題(topic)定義成會話中與用戶意圖相關(guān)的處理單元，即會話中具有相同用戶意圖的子序列。在對會話(session)、主題(topic)、劃分等概念做形式化定義的基礎(chǔ)上，為區(qū)別前人識別主題邊界的工作，我們將會話主題識別任務(wù)轉(zhuǎn)化為求session的最大劃分問題。進(jìn)一步地，為了解決該問題，本文僅使用 Web訪問日志信息，設(shè)計出基于用戶群體智慧的會話主題識別算法，取得了不錯的實驗效果。

2 相關(guān)研究工作概述

會話 (session)的概念并沒有一個十分標(biāo)準(zhǔn)的定義，在不同的工作中會被賦予不同的涵義。在有些工作中，session的定義只考慮了時間跨度和用戶的因素。例如，在文獻(xiàn)[6]中，session被定義成用戶在一次訪問網(wǎng)站期間從進(jìn)入網(wǎng)站到離開網(wǎng)站所進(jìn)行的一系列活動；文獻(xiàn)[7]在研究搜索引擎日志的工作中，將一個用戶與搜索引擎的所有交互行為定義為一個session，在session內(nèi)部進(jìn)行與用戶意圖相關(guān)的主題(topic)邊界識別。在另一部分工作中，session的定義加入了用戶意圖的限制。例如，文獻(xiàn)[8]認(rèn)為session是用戶為了同一個意圖進(jìn)行的一系列訪問活動；文獻(xiàn)[9]在數(shù)據(jù)庫查詢記錄上也有類似的定義。

時間是識別session最為常用的特征。文獻(xiàn)[10]推導(dǎo)出用戶一次訪問的持續(xù)時間大約是25.5分鐘，據(jù)此得到按時間跨度識別session的方法。按前后兩次訪問的時間間隔作為session邊界的識別是另一種被普遍使用的方法。文獻(xiàn)[8]在Excite和Reuters的訪問日志上使用時間間隔屬性進(jìn)行實驗，結(jié)果表明時間間隔取值在10～15分鐘之間時，session包含的訪問記錄數(shù)量趨于穩(wěn)定。除了單個session內(nèi)部的信息，有的工作還基于統(tǒng)計使用了群體信息。文獻(xiàn)[9]在數(shù)據(jù)庫訪問日志中使用語言模型進(jìn)行session識別。

從目標(biāo)上看，盡管關(guān)于session的定義不全一致，但大部分相關(guān)工作都希望將日志信息劃分成具有相同用戶意圖的處理單元。對于劃分結(jié)果單元，有的稱之為session，有的稱之為topic。從劃分方法和結(jié)果上看，上述相關(guān)工作都存在一個缺陷，即將算法輸出的相同用戶意圖處理單元表示成連續(xù)的操作記錄，完成的只是一個邊界識別工作，無法解決意圖交叉的問題。

3 會話主題識別問題的形式化定義

Web訪問日志包含了用戶在訪問互聯(lián)網(wǎng)資源時的操作記錄，主要由大量的用戶點(diǎn)擊數(shù)據(jù)構(gòu)成。經(jīng)過清理，用戶點(diǎn)擊數(shù)據(jù)一般都能轉(zhuǎn)化成至少包含用戶ID、點(diǎn)擊發(fā)生時刻、請求目標(biāo)網(wǎng)頁URL這三項的記錄格式。由此引出以下定義。

定義1點(diǎn)擊記錄c： 用戶訪問網(wǎng)頁時的點(diǎn)擊操作記錄。用三元組表示。c=。其中，cuserID表示該點(diǎn)擊記錄的userID，ctime表示該點(diǎn)擊記錄的點(diǎn)擊發(fā)生時刻，cURL表示該點(diǎn)擊記錄的請求目標(biāo)網(wǎng)頁URL。

定義2Web訪問日志C： 所有點(diǎn)擊記錄的集合。

定義3session(s)： 在滿足一定時間條件限制下，某個用戶的所有點(diǎn)擊按發(fā)生先后順序構(gòu)成的序列。所有session的集合用S表示。s的形式化定義如下:

su=(c1,c2,c3…cn) ?1≤i≤n,

由上面定義可知，session只考慮了時間屬性，沒有考慮用戶訪問時的意圖。

為了定義session的劃分和劃分之后的結(jié)果，我們引入與序列有關(guān)的兩個概念。

易知，連續(xù)子序列是子序列的一種特殊情況。

為了表述方便，定義函數(shù)L(s)，L(s)表示序列s中所有元素構(gòu)成的集合。例如，當(dāng)s表示某個session序列時，L(s)表示s中所有點(diǎn)擊構(gòu)成的集合。

定義4topic(t)： 點(diǎn)擊序列t稱為session(s)的一個topic，當(dāng)且僅當(dāng)t滿足以下兩個條件：

1)t是s的子序列；

2)t中的所有點(diǎn)擊都具有相同的用戶意圖。

定義5連續(xù)topic(tsuc)： 點(diǎn)擊序列tsuc稱為session(s)的一個連續(xù)topic，當(dāng)且僅當(dāng)tsuc滿足以下兩個條件：

1)tsuc是s的一個topic；

2)tsuc是s 的連續(xù)子序列。

由上述兩個定義可知，連續(xù)topic是topic的一種特殊情況。

定義6session的劃分D： topic集合D{t1,t2,t3…tn}稱為session(s)的一個劃分，當(dāng)且僅當(dāng)L(t1)∪L(t2)∪L(t3)…∪L(tn)=L(s)，且?1≤i

需要說明的是，定義6使用了如下假設(shè)：

假設(shè)1session中的每個點(diǎn)擊行為，具有唯一的用戶意圖。

對劃分D加入不同的限制條件，我們可以得到兩種特殊的劃分。

定義7session的連續(xù)劃分Dsuc： topic集合Dsuc{t1,t2,t3…tn}稱為session(s)的連續(xù)劃分，當(dāng)且僅當(dāng)Dsuc滿足以下兩個條件：

1)Dsuc是s的一個劃分；

2) ?t∈Dsuc，t是連續(xù)topic。

定義8session的最大劃分Dmax： topic集合Dmax{t1,t2,t3…tn}稱為session(s)的最大劃分，當(dāng)且僅當(dāng)滿足以下兩個條件：

1)Dmax是s的一個劃分；

2) ?ci∈L(t),cj∈L(t′),t∈Dmax,t′∈Dmax′t≠t′，有ciintent/cj。其中ciintentcj表示ci和cj用戶意圖相同，ciintent/cj表示ci和cj用戶意圖不同。

對比定義7和定義8，我們可以發(fā)現(xiàn)，最大劃分Dmax中的topic是具有同一個用戶意圖的所有點(diǎn)擊的集合，這是人們最終需要的結(jié)果。而連續(xù)劃分Dsuc則不能保證滿足這一點(diǎn)，往往會將最大劃分中的topic進(jìn)一步切分成一系列零碎的點(diǎn)擊片段。例如，已知sessions=(c1,c2,c3,c4,c5,c6) ，其中點(diǎn)擊c1,c2,c5,c6具有一個用戶意圖，c3,c4具有另一個用戶意圖。對于這種意圖交叉的情況，Dmax={(c1,c2,c5,c6),(c3,c4)}，Dsuc={(c1,c2),(c3,c4),(c5,c6)}?？梢钥吹紻suc將具有相同用戶意圖的topic(c1,c2,c5,c6)分成了兩個： (c1,c2)和(c5,c6)。

在以往的相關(guān)工作中，人們更多的是使用本文的定義5，直接將Web訪問日志中具有相同用戶意圖的處理單元定義成連續(xù)topic，完成的是連續(xù)topic邊界識別任務(wù)，得到的是連續(xù)劃分Dsuc，無法處理意圖交叉的情況。為了得到更好的劃分結(jié)果，我們基于上述定義，將會話主題識別問題描述為： 已知session(s)，求出s的最大劃分Dmax。

4 基于群體智慧的會話主題識別算法

4.1 Session劃分求解算法

根據(jù)假設(shè)1，可以得到如下推論。

推論1若點(diǎn)擊ci和cj滿足ciintentcj，點(diǎn)擊cj和ck滿足cjintentck，則有ciintentck。

設(shè)圖Gc=，其中點(diǎn)集Vc={c|c∈L(s)}，邊集Ec={(ci,cj)|ci∈L(s),cj∈L(s),ciintentcj}。

推論2若已知session(s)和s中部分具有相同用戶意圖的點(diǎn)擊對集合EI，即EI?Ec。構(gòu)造圖GI=，則GI中同一個連通分量中的所有點(diǎn)擊都具有相同的用戶意圖，每一個連通分量都對應(yīng)session中的一個topic。

證明： 若點(diǎn)擊ci和cj處在圖GI的一個連通分量中，必存在路徑使ci和cj可達(dá)。設(shè)路徑為ci→ca1→ca2…→cak→cj,則有ciintentca1,ca1intentca2…cak-1intentcak,cakintentcj。根據(jù)推論1，可以得到ciintentcj，即Gc中同一個連通分量中的任意兩個點(diǎn)擊具有相同的用戶意圖。再根據(jù)假設(shè)1，可以推出GI中同一個連通分量中的所有點(diǎn)擊都具有相同的用戶意圖, 每一個連通分量都對應(yīng)session中的一個topic。證畢。

推論2提供了計算session劃分的思路。給定點(diǎn)擊對集合EI，由此構(gòu)建出的圖GI中連通分量對應(yīng)的topic的集合就是session的一個劃分。當(dāng)構(gòu)建GI所依賴的初始集合EI中包含的點(diǎn)擊對足夠多時，該算法得到的劃分就是session的最大劃分。我們希望EI逼近Ec，于是session的最大劃分求解問題轉(zhuǎn)化成初始點(diǎn)擊對集合EI的求解問題。

基于群體智慧的會話主題識別算法的主要思想就是利用用戶群體信息，盡量多地發(fā)現(xiàn)具有相同用戶意圖的點(diǎn)擊對，然后根據(jù)推論2，求出session的最大劃分。

4.2 EI的求解

Web訪問日志中包含了大量不同用戶的操作記錄，群體的智慧蘊(yùn)含在這海量數(shù)據(jù)集中。使用統(tǒng)計方法對大規(guī)模數(shù)據(jù)進(jìn)行分析，有利于我們發(fā)現(xiàn)其中潛藏的規(guī)律。在求解session劃分問題中，我們嘗試比較兩個點(diǎn)擊對應(yīng)的網(wǎng)頁(page)在Web訪問日志中的出現(xiàn)情況，判斷兩者是否具有相同的用戶意圖。

圖1 二分圖和鄰接矩陣的構(gòu)建

4.2.1 用session表示page

構(gòu)造二分圖GSP=表示W(wǎng)eb訪問日志中所有會話(session)和網(wǎng)頁(page)的關(guān)系。圖GSP節(jié)點(diǎn)集VSP由session集合S和page集合P兩部分構(gòu)成，page用對應(yīng)的URL表示。VSP={v|v∈S或v∈P}。圖GSP邊集ESP={(s,p)|s∈S或p∈P，且?c∈L(s)，使CURL=p}。即二分圖GSP中session結(jié)點(diǎn)s和page節(jié)點(diǎn)p之間存在一條無向邊，當(dāng)且僅當(dāng)p是s中某次點(diǎn)擊的目標(biāo)URL對應(yīng)的page。

如圖1所示，給定四個session，先構(gòu)建出二分圖GSP，然后導(dǎo)出鄰接矩陣A。注意到由于二分圖GSP是一個無權(quán)無向圖，所以矩陣A是對稱的01矩陣。根據(jù)矩陣A，我們可以用行向量表示page。例如，p1=(1,1,0,0)，p2=(1,1,1,0)。

4.2.2 Page相關(guān)度計算

向量之間的相關(guān)度計算公式有很多。本算法中主要使用了賈卡德相似度(Jaccard Similarity)和余弦距離(Cosine Similarity)兩種。

賈卡德相似度(Jaccard Similarity)：

(1)

用鄰接矩陣A表示，有

(2)

余弦距離(Cosine Similarity)：

(3)

用鄰接矩陣A表示，有

(4)

通過用session表示page，并選取合適的相關(guān)度計算公式，我們可以得到page之間的相關(guān)度σ(x,y)。相關(guān)度σ(x,y)是0到1之間的實數(shù)。

為了判斷同一個session中的兩個點(diǎn)擊是否具有相同的用戶意圖，我們認(rèn)為：

intentcj

(5)

根據(jù)本文4.1的理論推導(dǎo)，我們可以令EI=Eσ，算法執(zhí)行的結(jié)果就是session的一個劃分。通過上述轉(zhuǎn)化，我們運(yùn)用用戶群體智慧，將具有相同意圖的點(diǎn)擊對判斷近似成了page的相關(guān)度計算。

4.3 算法實施流程

如圖2所示，算法分為離線和在線兩個部分。

圖2 基于群體智慧的會話主題識別算法流程

離線部分

步驟1： 使用Web訪問日志構(gòu)建包含session和page的二分圖；

步驟2： 由二分圖導(dǎo)出鄰接矩陣A。

在線部分：

步驟2： 根據(jù) EI構(gòu)建點(diǎn)擊意圖關(guān)系圖GI，使用圖搜索算法計算出它的所有連通分量；

步驟3： 將圖GI的每個連通分量轉(zhuǎn)化為s 的topic，得到s 的劃分。

5 評價方案與實驗結(jié)果

5.1 會話主題識別的評價標(biāo)準(zhǔn)

我們采用人工標(biāo)注的方法對真實Web 訪問日志中的session進(jìn)行劃分，識別出一系列會話主題。設(shè)人工標(biāo)注的結(jié)果為最大劃分Dmax，評價會話主題識別算法的優(yōu)劣，就是比較算法求出的劃分D與最大劃分Dmax的差異。文獻(xiàn)[6]在評價session重構(gòu)性能的工作中引入了IR領(lǐng)域常用的準(zhǔn)確率(precision)和召回率(recall)。類似地，我們同樣使用了這兩個指標(biāo)，并增加了兩者的綜合指標(biāo)F1。

(6)

(7)

(8)

其中，|D|表示算法結(jié)果劃分D中topic數(shù)量，|Dmax|表示人工標(biāo)注結(jié)果最大劃分Dmax中topic數(shù)量，|D∩Dmax|表示算法完全識別正確的topic數(shù)量。

上述三個指標(biāo)可以看成是在topic層面上的評價。除此之外，我們從點(diǎn)擊層面提出了相應(yīng)的指標(biāo)。定義二元準(zhǔn)確率PP(pairwiseprecision)如下：

PP(pairwiseprecision)=

(9)

其中|s|表示session中包含點(diǎn)擊的數(shù)量。event_topic(D,ci,cj)表示事件——點(diǎn)擊ci和cj在劃分D上屬于同一個topic。I(event)是示性函數(shù)。

5.2 實驗結(jié)果分析

本次實驗使用的 Web訪問日志是由國內(nèi)一家著名的搜索引擎公司通過瀏覽器工具欄搜集并提供的。我們抽取了2010年3月28日一整天的數(shù)據(jù)進(jìn)行分析。日志數(shù)據(jù)面向萬維網(wǎng)，包含34 918 182條點(diǎn)擊記錄。將擁有相同用戶ID的點(diǎn)擊記錄合并，按發(fā)生時刻從小到大排序，我們得到1 393 046個session，并從中隨機(jī)挑選出500個作為測試集合。專業(yè)人員對測試集合中的每一個session進(jìn)行手動劃分，標(biāo)注出一系列會話主題。在此基礎(chǔ)上，我們實現(xiàn)并評價了基于群體智慧的識別算法(求最大劃分)和基于空閑時間間隔的識別算法。其中，基于群體智慧的識別算法分別使用了賈卡德相似度和余弦距離，閾值θ分別取0.1和0.05。基于空閑時間間隔的識別算法取空閑時間間隔為30分鐘。

表1 會話主題識別算法評價結(jié)果

從表1可以看出，在各個指標(biāo)上基于群體智慧的識別算法都明顯優(yōu)于基于空閑時間間隔的識別算法。其中，使用余弦距離作為page相關(guān)度時，基于群體智慧的識別算法達(dá)到最好結(jié)果，TP、TR、F1、PP分別為0.572 4、0.564 4、0.568 3、0.858 1，比基于空閑時間間隔的識別算法分別提高了83.52%、85.96%、84.75%、16.61%。

5 結(jié)論與分析

本文形式化定義了 Web訪問日志中會話(session)、主題(topic)和劃分的相關(guān)概念。特別地，為了區(qū)別于前人識別topic邊界的工作，本文還形式化地提出了連續(xù)topic的概念。針對 topic和連續(xù)topic，本文嘗試性地給出了session的最大劃分和連續(xù)劃分的形式化定義。同時，本文通過對大規(guī)模真實Web訪問日志的分析研究，提出并實現(xiàn)了基于群體智慧的會話主題識別算法，解決了用戶意圖交叉問題。該算法只使用了Web訪問日志中最基本的請求目標(biāo)網(wǎng)頁URL信息，在完全沒有使用頁面之間的鏈接關(guān)系和頁面內(nèi)容文本信息的情況下，與常用的基于空閑時間間隔的識別算法相比，取得了不錯的識別效果。在評價準(zhǔn)則方面，我們擴(kuò)展了前人在線性空間上針對連續(xù)topic邊界識別的評價方法，定義了二維的準(zhǔn)確度指標(biāo)，并運(yùn)用到了評價最大劃分的任務(wù)上。在今后的工作中，我們將針對同一session中的點(diǎn)擊行為具有唯一用戶意圖這一假設(shè)做進(jìn)一步深入研究，提高會話主題識別的性能。

[1] CNNIC (China Internet Network Information Center). The 25st report in development of Internet in China[EB/OL]. http://www.cnnic.net.cn/uploadfiles/pdf/2010/1/15/101600.pdf, 2010.

[2] Liu, Y., Gao, B., Liu, T., Zhang, Y., Ma, Z., He, S., and Li, H. BrowseRank: letting web users vote for page importance[C]//Proceedings of the 31st ACM SIGIR Conference. 2008： 451-458.

[3] Liu, Y., Zhang, M., Ma, S., Ru, L., User Browsing Graph: Structure, Evolution and Application[C]//The 2nd ACM International Conference on Web Search and Data Mining (WSDM 2009).

[4] 陳磊,劉奕群,茹立云,等.基于用戶日志挖掘的搜索引擎廣告效果分析[J]. 中文信息學(xué)報，2008,22(6): 92-97.

[5] Yiqun Liu, Rongwei Cen, Min Zhang, Shaoping Ma, Liyun Ru. Identifying Web Spam with User Behavior Analysis[C]//The Fourth International Workshop on Adversarial Information Retrieval on the Web. 2008.

[6] M Spiliopoulou, B Mobasher, B Berendt, Miki Nakagawa. A framework for the evaluation of session reconstruction heuristics in web-usage analysis[J]. INFORMS journal of Computing, 2003，15(2)：171-190.

[7] Seda Ozmutlu, H. Cenk Ozmutlu, Amanda Spink. Automatic New Topic Identification in Search Engine Transaction Logs using Multiple Linear Regression[C]//Proceedings of the 41st Hawaii International Conference on System Sciences. 2008.

[8] Daqing He, Ayse Goker. Detecting session boundaries from Web user logs[C]//Proceedings of the 22nd annual colloquium on information, 2000.

[9] Qingsong Yao, Xiangji Huang and Aijun An. Applying Language Modeling to Session Identification from Database Trace Logs[J]. Knowledge and Information Systems, 2006，10(4)：473-504.

[10] Catledge, L, J Pitkow. Characterizing Browsing Behaviors on the World Wide Web[J]. Computer Networks and ISDN System 1995，27(6)：1065-1073.