朱 志 國

（1.大連理工大學系統(tǒng)工程研究所，遼寧大連 116024；2.東北財經(jīng)大學管理科學與工程學院，遼寧大連 116023）

0 引 言

用戶會話是指用戶在一次訪問網(wǎng)站期間從進入網(wǎng)站到離開網(wǎng)站所進行的一系列訪問活動.會話識別工作就是將每個用戶的活動日志按照某種方法映射到會話中去.會話識別是否準確直接決定了后續(xù)的Web使用挖掘處理結(jié)果是否有意義，因此在Web使用模式挖掘系統(tǒng)的數(shù)據(jù)預處理中，用戶會話識別和重建是非常重要的步驟之一［1］.在實踐過程中本地緩存、代理服務器和防火墻的存在，使Web日志中記錄的數(shù)據(jù)并不精確，增加了識別和重建用戶會話的難度.

目前，已經(jīng)有不少學者提出了一些用戶會話識別方法［2～4］，其中較經(jīng)典的有基于時間的啟發(fā)式方法和基于引用的啟發(fā)式方法［5］.

基于時間的啟發(fā)式方法只考慮用戶與網(wǎng)站交互中的時間因素.這種方法又可以分為基于會話時間的啟發(fā)式方法（T1）和基于頁面訪問時間的啟發(fā)式方法（T2）兩種類型.T1的主要思想是：一個用戶會話持續(xù)時間不能超過一個預設閾值Φ，通常Φ采用30 min；T2的主要思想是：用戶在一個頁面停留的時間不能超過閾值δ，否則判定新會話開始，通常δ取10 min.

基于引用的啟發(fā)式方法（H－ref）的主要思想是：利用頁面之間的實際鏈接關(guān)系來分割會話.假設同一用戶依次發(fā)出相鄰的兩個頁面請求p和q（其中p屬于會話S），參照網(wǎng)站的拓撲結(jié)構(gòu)圖之后，發(fā)現(xiàn)q的引用頁面是p或者已經(jīng)存在于會話S當中（可能利用瀏覽器的后退功能），那么可以判定q屬于會話S，反之亦然.

上述識別和構(gòu)建用戶會話方法，比較適合于一些簡單的模式挖掘過程.為發(fā)現(xiàn)更多潛在的和有意義的Web用戶偏好模式，本文基于Web站點目錄結(jié)構(gòu)，把用戶訪問的URL中攜帶的信息概念化后，進行用戶會話識別與重構(gòu)工作.

1 Web日志數(shù)據(jù)模型

Web日志中的每一條訪問請求可以反映出用戶在瀏覽過程中的意圖和興趣.本文采用Web站點目錄結(jié)構(gòu)為本體，將這些Web訪問記錄中URL攜帶的語義信息概念化.目前有幾種常見的Web日志數(shù)據(jù)模型，例如：NCSA、擴展W3C和IRCache［6］格式等.下面僅以IRCache格式的Web日志為例進行討論.每一個IRCache日志文件包含了10個基本域，圖1展示了一個IRCache日志文件中一條記錄的詳細內(nèi)容.

圖1 IRCache日志格式示例Fig.1 The example of IRCache log format

每一條發(fā)送給服務器的訪問請求必不可少的3部分信息包括時間、源IP地址和請求的URL.一條完整的URL信息可以被分割成基本部分和剩余部分.它們分別代表Web服務器主機域名和URL的其余部分.本文采用URL的基本部分來語義化表征每條URL.

如表1所示，假定一個Web日志文件中按照時間順序有t1～t8共8條請求記錄.這里將URL序列集合｛…，b＿urli＋rj，…｝與時間記錄｛…，tk，…｝對應起來.接下來，首先將這些日志記錄以相應的IP地址信息來分類，然后對每個請求集合中的URL基本部分間的語義距離進行比較.可以認為一個語義會話中的URL應該有相似的語義，也就是說，通過對于URL間語義相似性的比較可以考察一個Web用戶的訪問意圖是否具有延續(xù)性和持久性.

表1 URL請求的日志記錄示例Tab.1 The example of URL request in a log file

2 利用Web目錄對URL概念化

為了判定一條URL的語義特征，必須基于本體來對URL進行概念化，在本文中借助Web站點的目錄結(jié)構(gòu)來構(gòu)建這樣的本體，然后在獲取到一個概念化的URL樹狀結(jié)構(gòu)基礎上，評測URL之間的語義相似性.

本體又被稱為語義分類器，它是可定義為被共享的概念化的一個形式的規(guī)格說明［7］.這意味著本體對于未概念化數(shù)據(jù)的語義富化或者結(jié)構(gòu)化起到重要的作用.類似于Cora（http：／／cora.whizbang.com）這樣的Web目錄結(jié)構(gòu)可以作為一個本體，對一個URL所指向的網(wǎng)頁內(nèi)容給出一個標準和通用的描述.此外，Web目錄采用的是主題層級結(jié)構(gòu)的組織方式，這種結(jié)構(gòu)對于大量信息的組織、查閱和檢索是高效率的，否則采用其他結(jié)構(gòu)組織方式，將會非常麻煩［8］.

本文假設站點中所有的URL可以通過良好組織的Web目錄服務被概念化［9］.可是在實際操作方面仍然存在一些困難，這是因為大多數(shù)的Web站點目錄為了避免由于冗余信息［10］所造成的存儲空間浪費而采用了非通用的樹形結(jié)構(gòu).把利用Web目錄作為本體，概念化URL過程中存在的問題簡單總結(jié)如下：

（1）一條URL的多屬性.一個Web站點可以有多個主題.不同主題范疇之間的相互關(guān)系使得它們的層級結(jié)構(gòu)越發(fā)復雜.一條URL能夠?qū)儆诙鄠€不同范疇，如圖2（a）中的A和B.

（2）范疇之間的關(guān)系.一個范疇從根節(jié)點可以有多條路徑，因此它就可以附屬于多個父范疇.如圖2（b）所示，范疇C不僅僅是P的子類，同時也是A的子類.而且一些范疇盡管有不同的標記，但是從語義上來說還是相同的.

圖2 概念化URL中存在的問題Fig.2 The problems in URL conceptualization process

為了簡化處理上面所提出的問題，本文把每一條URL歸類到所有與它最可能相關(guān)的范疇中去，因此一條URLurli可以被歸并到一個范疇集合Category（urli）中去，范疇集的大小取決于Web目錄的復雜程度.一個范疇集中每個元素代表了Web目錄上一條從根節(jié)點到相應范疇的路徑.設在表1中將URL的基本部分｛b＿url1，b＿url2，b＿url3｝語義豐富為｛〈a：b：d，a：b：f：k〉，〈a：c：h〉，〈a：b：f：j〉｝，最左邊的概念a表示W(wǎng)eb目錄結(jié)構(gòu)的根節(jié)點，那么這些URL基本部分相應地可以被范疇化為〈d，k〉、〈h〉和〈j〉.特別指出的是，范疇Category（b＿url1）由兩個不同的概念（〈a：b：d，a：b：f：k〉）所組成.

3 語義會話識別方法

3.1 基本符號和相關(guān)定義

本文定義了一些Web請求URL之間的語義關(guān)系的測度指標.以Web目錄為本體對每條請求的URL概念化后，可以獲得該條URL所有可能的概念化有序路徑path.首先，語義距離可以通過計算兩條URL之間的語義差異而得到.設一條URLurli被劃歸到所屬的范疇集合后，相應的路徑如下：

其中M表示范疇路徑的條數(shù).對Levenshtein編輯距離公式［11］簡單擴展后，就可以得到兩條URLurl i和url j之間的語義距離公式，如下：

其中和分別代表路徑以及兩者共同部分的長度.因為在樹結(jié)構(gòu)中標記的路徑代表了概念化的URL，據(jù)此能夠輕松得知URL之間互相疊加的共同部分.利用Δ◇對兩條URLurl i和url j所有概念化路徑分別進行計算，取其中的最小值.這個值應在區(qū)間［0，1］內(nèi)，其中0代表完全匹配.式（2）中作分母的指數(shù)函數(shù)用來增強的作用.

第二個語義指標是要聚合預定義時間段T中的所有URL，因此語義距離矩陣DΔ◇的計算公式如下式所示：

此矩陣的規(guī)模取決于預定義時間間隔T，并且矩陣中對角元素全部為0.

基于DΔ◇，給出語義平均值μ◇的計算公式如下式所示：

其中DΔ◇（i，j）是距離矩陣中第（i，j）元素的計算值.μ◇實際上是矩陣中除了對角線以外的上三角元素的平均值，考慮給定的時間間隔T，可以推導出語義偏離值σ◇的計算公式如下：

以上這些設定指標主要用來定量分析兩個任意日志間的語義距離，根據(jù)給定的時間間隔，從統(tǒng)計學角度甄別出超過某一預設閾值的語義奇異值.

3.2 靜態(tài)Web日志中的語義奇異值鑒別

當對Web日志集進行會話分割時，一般來說日志中的記錄都是隨時間變化的，更準確地講是流動的，這樣在流數(shù)據(jù)集中進行會話識別不僅僅需要上面給出的一定時間間隔內(nèi)的語義關(guān)系的測度指標，還需要計算語義均值μ◇的分布，這個將會在后面作詳細描述.下面首先簡單地考慮一個給定的數(shù)據(jù)集不隨時間變化的情況，并且在這里假定它的大小是固定不變的.

為了分析會話識別中的語義奇異值，本文把每個會話的部分語義偏離值σ◇之和最小視為給定數(shù)據(jù)集達到了最優(yōu)的會話分割.因此，本文給出一個會話識別原則PSI（principle session identifiers），其定義如下式，PSI實際上是會話邊界位置的集合.

其中變量S和T分別表示會話數(shù)量和時間間隔.

下面首先給出在靜態(tài)日志中進行會話識別時關(guān)于PSI的目標函數(shù)SOAs，具體計算公式如下：

其中表示第i分段的部分語義偏離值.為了最小化SOAs，在語義距離矩陣DΔ◇中搜尋出最顯著差異的一對值，也就是在矩陣DΔ◇中的最大值.具體的計算公式如下：

式中：是一個在給定時間區(qū)間［Ta，Tb］求得最大值的函數(shù).當計算得到了最大語義距離值DΔ◇（p，q）時，可以推斷在第p和q個URL之間至少存在一個psi.接下來用時間區(qū)間［T p，Tq］取代初始的區(qū)間［T a，Tb］，經(jīng)過遞歸，在縮小的時間區(qū)間中進一步掃描，找到最大的語義距離值，接下來可以將兩個相鄰元素之間的psi作為候選，用SOAs（psi）來評估.如果值小于σ◇，那么這個候選psi可以插入PSI中去，否則由這個候選psi產(chǎn)生的會話分割就取消掉.這就是會話識別中自頂向下的過程，直到發(fā)現(xiàn)的會話數(shù)量滿足要求為止.此外，在SOAs（psi）評估過程中，還能夠把會話識別中過擬合所導致的錯誤也及時地檢查出來.

圖3所示的兩個例子中，URL記錄分別屬于兩個會話SA和S B.圖中A（i）和B（i）分別代表會話SA和S B中的第i個部分.可以認為A（i）（或B（i））之間的語義距離遠小于A（i）與B（i）間的語義距離.設4個最大的語義距離Δ◇［A（1），B（1）］、Δ◇［A（2），B（2）］、Δ◇［A（2），B（0）］和Δ◇［A（2），B（1）］分別是0.86、0.85、0.81和0.79，最終分割為兩段會話.在Case 1中，由于在初始時間間隔區(qū)間［1，6］中最大的語義距離是Δ◇［A（1），B（1）］，當時間間隔區(qū)間縮短為［2，5］后，這時Δ◇［A（2），B（0）］是最大值，因此在這個時間段中可以確定psi3作為一個候選，最后，計算得到σ◇［1，3］＋σ◇［4，6］＜σ◇［1，6］后，判定候選psi3可以插入PSI中去.Case 1相對來說是比較簡單的，可以明顯地找到候選psi，并且也能夠驗證會話分割是正確的.比較復雜的情況是Case 2，會話SA中有一個不同類的請求B（0）.同樣首先確定在初始時間間隔區(qū)間［1，6］中最大的語義距離是Δ◇［A（1），B（1）］，之后在縮減的時間間隔［2，5］中第1個psi3由Δ◇［B（0），A（2）］生成，但是通過計算發(fā)現(xiàn)σ◇［1，3］＋σ◇［4，6］≥σ◇［1，6］，則這個候選psi3不符合要求，被刪除掉.接下來，第2個候選psi4由Δ◇［A（2），B（1）］生成，并且通過計算σ◇［1，4］＋σ◇［5，6］＜σ◇［1，6］，確定這個psi4符合要求可以被插入到PSI集中去.

圖3 自頂向下的會話識別方法示例Fig.3 Top－down approach for session identification methods

3.3 Web日志流中的語義會話識別

實際應用中，在線Web日志總是在不斷變化中.但是既要考慮到現(xiàn)有的日志數(shù)據(jù)又要顧及到流數(shù)據(jù)幾乎是不可能的，為此定義了一個時間窗口W.W作為一個預定義值，來約束能夠從當前位置容納的最新URL條目數(shù)量，每一次當有新的URL請求，這個時間窗口也相應向前移動.為了甄別和分析日志流中的語義孤立值，本文不僅要著眼于基本的語義指標，還要根據(jù)給定的時間窗口把語義均值的分布情況μ◇（W（T））考慮進去.

作為SOAs的擴展，給出分析動態(tài)日志中語義孤立值的目標函數(shù)SOAd的計算公式，如下式所示：

式中：W（i）代表從第i條URL開始的時間窗口.這個目標函數(shù)通過找到最正確的PSI集合來最小化SOAd（psi）的值.候選psi i的產(chǎn)生依靠連續(xù)時間窗口中的語義均值與預設閾值ε之間的比較估算得出，如下式所示：

4 實驗和討論

4.1 會話識別方法的評估

對于一個會話識別方法h的一般測評方法是通過比較Ch（由方法h劃分日志文件后得到的識別會話集合）與R（日志文件被劃分成由真實會話組成的集合）之間的差別來對方法h進行評價.將識別方法h的得分表示為M（h），其值域為［0，1］.目前，有兩種常用的測評方法：一種是依據(jù)真實會話被完全識別出來的數(shù)量進行評價的絕對型測評方法；另外一種就是依據(jù)會話被識別出來的程度進行評價的漸進型測評方法.

4.1.1 絕對型測評方法

定義1 當一個真實會話中的所有成員都包含于某個識別會話中時，那么可以稱這個真實會話被“完全識別”出來.

如果含有n個成員的真實會話r被“完全識別”，當且僅當存在一個識別會話c含有m個成員，并滿足i＝1，2，…，n，罷j∈｛1，2，…，m｝：r［i］＝c［j］.識別會話保持了真實會話的成員序列.

根據(jù)上述完全重構(gòu)的真實會話的定義，絕對型測評方法的定義通常可以采用精確率和召回率這兩個指標，來衡量一個會話識別方法完全推測出的真實會話的數(shù)量，如下式：

精確率（precision ratio）是完全識別的會話數(shù)量與構(gòu)造生成的總會話數(shù)量的比值.

召回率（recall ratio）是完全識別的會話數(shù)量與真正的會話數(shù)量的比值.

4.1.2 漸進型測評方法 許多情況下，識別會話與真實會話可能只是存在部分的相同.下面對于識別會話和真實會話間的重疊度問題進行討論.

定義2 重疊度定義為真實會話和識別會話間的相同成員數(shù)量除以真實會話中的成員總數(shù).即真實會話r（含有n個成員）與識別會話c（含有m個成員）間的重疊度dego（r，c），定義如下式所示：

可以通過定義函數(shù)f求得所有識別會話與真實會話間重疊度的平均值或最大值來計算出一個真實會話r的重疊度.本文f定義為取最大值，即如下式所示：

最后，定義函數(shù)g為對所有真實會話的重疊度值求平均，以此對會話識別方法進行評價.即

在根據(jù)上述定義，本文給出的漸進型測評方法就是通過函數(shù)g對真實會話集R與C h中識別會話的重疊度進行計算，從而得到對于某一會話識別方法h的評價.

重疊度為1表示這個真實會話與其識別會話完全符合.

如果一個識別會話錯誤地包含了一些本應該分配到其他會話中去的成員，此時重疊度并沒有發(fā)生改變，自然也不會影響對啟發(fā)式方法h的評價，但這樣一些不符合邏輯的頁面關(guān)系可能會被推導出來.為此，提出一個改進的重疊度定義.

定義3 改進重疊度定義為真實會話和識別會話間的相同成員數(shù)量w a除以真實會話與識別會話并集中的所有成員數(shù)量.這樣重疊度的計算公式為測評方法Ms（g）（h）的定義與Mo（g）（h）相似，如下式所示：

4.2 實驗結(jié)果與分析

實驗數(shù)據(jù)取自sv.us.ircache.net網(wǎng)站，這個網(wǎng)站采用了IRCache的格式.由于要人工識別真實會話，數(shù)據(jù)量和工作量都比較大，只選取2006－05－25 1 d發(fā)生的14 292個頁面請求進行分析.根據(jù)分析判斷，5月25日比較接近整個月份的平均訪問水平線，具有一定代表性，因此本文只對該天的日志進行分析.為了正確地反映用戶的瀏覽行為，站點禁止使用緩存.實驗運行環(huán)境是酷睿雙核E2160，操作系統(tǒng)為Windows 2003 Server，內(nèi)存為1 GB.實驗的主要目的是對本文提出的會話識別方法與其他會話識別啟發(fā)方法進行對比分析.實驗首先對原始數(shù)據(jù)進行清理，參照Web目錄清除掉URL域中模糊不清的日志記錄（錯誤的拼寫或IP地址等）.

實驗前，經(jīng)過人工識別得到479個用戶與1 344個真實會話，接下來取出會話的邊界標.采用本文前面所討論的3種經(jīng)典方法以及本文提出的語義會話識別方法分別進行計算.對于基于會話持續(xù)時間的識別方法，實驗選擇30 min為一個會話的最長持續(xù)時間，記為T1－30.對于基于頁面停留時間的識別方法，實驗選擇10 min為頁面最長停留時間，記為T2－10.對于基于頁面間引用關(guān)系的識別方法，實驗中將Δ設置為10，記為H－ref.本文提到的方法，針對靜態(tài)和流動兩類Web日志類型的語義奇異值分析方法分別用SOAs和SOAd代表，時間窗口W預設值定為50，表2顯示了實驗的結(jié)果.

表2 5種會話識別方法的絕對型測評結(jié)果Tab.2 The categorical evaluation results of five session identification methods

表3中列出了5種會話重構(gòu)啟發(fā)方法根據(jù)兩種漸進型測評方法得到的計算值（Mo（g）（h）和Ms（g）（h）表示兩種漸近型評測值）.可以看出本文提出的基于URL本體的SOAs和SOAd的啟發(fā)方法從識別會話的精確率和召回率來看，比現(xiàn)有的其他3種經(jīng)典方法提高了一些.

表3 5種會話識別方法的漸進型測評結(jié)果Tab.3 The gradual evaluation results of five session identification methods

從實驗結(jié)果總體分析，本文提出的基于URL語義分析的會話識別方法的主要優(yōu)點在于：可以不受瀏覽時間間隔和用戶IP地址限制，把超過時間間隔或者沒有直接引用關(guān)系的URL通過語義關(guān)聯(lián)在一起，形成一個更為準確的會話.但是T1－30、T2－10和H－ref這些經(jīng)典方法對于用戶會話識別分割的考慮因素比較簡單，這樣在應用層面利于實現(xiàn)和推廣，因此本文提出的這個方法可以作為經(jīng)典方法的一個有益補充，主要用來分析復雜的用戶訪問模式.同時這個方法可以得到語義化的用戶會話，有助于開展本體概念層次的Web使用挖掘工作.

5 結(jié) 語

本文提出的會話識別方法采用Web目錄作為本體，對日志記錄中的每一條URL記錄賦予一定的語義信息，在此基礎上根據(jù)文中給定的一些測度指標對URL間語義相似度進行評價，繼而對用戶會話識別和分割.實驗結(jié)果表明，本文提出的會話識別方法在各種測評方法的評估中均占優(yōu).基于語義的Web用戶會話識別算法可以不受用戶瀏覽時間間隔和IP地址的限制，在對經(jīng)常改變?yōu)g覽興趣或習慣于同時進行多代理瀏覽的用戶進行會話識別時，該方法有較強的優(yōu)越性——更高的會話識別率.

本文的下一步工作為深入研究一個Web站點如果沒有在Web目錄中注冊，如何通過分析鏈接間接地對這個站點中的訪問URL進行概念化.

［1］FEDERICO M F，PIER L L.Mining interesting knowledge from weblogs：a survey［J］.Data and Knowledge Engineering，2005，53（3）：225－241

［2］陳子軍，王鑫昱，李 偉.一種Web日志會話識別的優(yōu)化方法［J］.計算機工程，2007，33（1）：95－97

［3］張 輝，宋瀚濤，徐曉梅.基于語義的Web用戶會話識別算法［J］.北京理工大學學報，2007，27（6）：471－473

［4］SPILIOPOULOU M，MOBASHER B，BERENDT B，etal.A framework for the evaluation of session reconstruction heuristics in Web－usage analysis［J］.INFORMS Journal of Computing，2003，15（2）：10－16

［5］朱志國，鄧貴仕.Web使用挖掘技術(shù)的分析與研究［J］.計算機應用研究，2008，25（1）：41－47

［6］NLANR／NSF.IRCache users guide［EB／OL］.［2008－03－18］.http：／／www.ircache.net／

［7］GRUBER T.What is an ontology？［EB／OL］.［2008－02－21］.http：／／www－ksl.stanford.edu／kst／what－is－an－ontology.htm

［8］JUNG J，YOON J.Collaborative information filtering by using categorized bookmarks on the Web［C］／／Proceedings of the 14th International Conference on Applications of Prolog.Tokyo：The Prolog Association，2001：343－357

［9］MEO R，LANZI P L，MATERA M.Integrating Web conceptual modeling and Web usage mining［C］／／KDD Workshop on Web Mining and Web Usage Analysis.Berlin：Springer，2004：117－214

［10］EIRINAKI M，VAZIRGIANNIS M，VARLAMIS I.Sewep：using site semantics and a taxonomy to enhance the Web personalization process［C］／／Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2003：99－108

［11］LEVENSHTEIN I V.Binary codes capable of correcting deletions，insertions，and reversals［J］.Soviet Physics Doklady，1966，10（8）：707－710