基于局部序列比對相似度的用戶會話聚類新方法

姚 瑤，周 銅

(鄭州工程技術學院 信息工程學院，河南 鄭州 450044)

1 引言

伴隨大數據時代的到來，網絡信息無論從數量上還是形態上均增長迅速，尤其是用戶行為數據越來越復雜。降低用戶訪問延遲的核心方法歸納為緩存技術與預取技術[1]。預取技術的關鍵是頁面預測，預測的準確率直接影響預取效率[2]，而精準預測的難點在于如何挖掘用戶瀏覽行為的相似性，提高用戶會話聚類準確度是關鍵。

聚類方法分為劃分聚類,層次聚類法,密度聚類,模型聚類,基于神經網絡的聚類和圖論聚類等[3]。利用聚類方法分析大數據環境下用戶的行為偏好是近年來研究的熱點[4]。通過計算用戶會話之間的距離彼此相似度是一種有效方法。但是，由于網絡信息的復雜環境影響，用戶及其訪問行為數量巨大、變化多端，網絡會話會根據其不同的性質導致長短不齊，傳統的用戶相似性判定算法普遍存在數據過于稀疏和計算量過大的問題。

基于計算會話距離從而聚類網絡用戶的研究始終是焦點。用于衡量用戶會話間距離具有較高準確性的方法是序列對比方法(簡稱SAM)[5]，源于氨基酸序列的比對校準，但是側重于劃分基于用戶請求的導航序列[6]，未曾考慮用戶偏好，受限于用戶會話因不同的瀏覽偏好導致會話序列長短不齊的問題。Khasawneh等人[7]采用動態規劃的多維會話比較方法，其中頁面列表是比較的主要維度，但是計算代價較高。Poornalatha[8]提出了一種有效的基于VLVD函數的K-means算法來對Web會話進行聚類，該算法雖然考慮了可變長度會話的問題，卻忽略了頁面訪問的順序。文獻[9]提出了一種針對大規模數據的快速聚類方法，旨在降低聚類的時間，但聚類效果有所降低。文獻[10]介紹了一種基于kullback-Leibler(Kl)散度的相似度度量方法，依據不對稱因素評判用戶的偏好，該模型適用于稀疏數據。文獻[11]采用基于MapReduce的算法，通過貝葉斯網絡的概率推理來測量相關度，側重于發現數據密集型的用戶相似性。

上述方法主要集中在對用戶相似性的數學模型改進上，卻沒有充分考慮用戶本身的評分偏好，忽略了網絡會話的復雜環境。因此，本文提出基于用戶會話聚類的頁面預測新模型，通過計算序列比對技術的集成距離度量衡量任何兩個會話之間的相似度。該方法兼顧用戶聚類和評分偏好，重點對最近鄰選取和預測評分生成方法進行改進，具有較好的聚類性能。

2 基于頁面會話聚類的Web預測模型

預測模型分兩個階段工作：離線和在線階段，如圖1所示。離線階段在服務器上執行，在線階段包括服務器和客戶端。

圖1 Web頁面預測模型

Web日志模塊：日志包含每個客戶端訪問服務器的信息，包括客戶端IP地址，訪問服務器的日期和時間，HTTP方法(例如get)、請求的URL、響應代碼，從服務器傳輸到客戶端的字節數等。用戶會話是基于IP地址、日期和時間創建的，由用戶在一定時間段內(例如30分鐘)訪問的一組連續的網頁序列組成。 此外，對會話進行過濾以刪除圖像文件，機器人導航等。從這些過濾的會話中識別出唯一請求，并為每個會話賦予唯一的ID。

聚類模塊：將用戶會話劃分為60%的訓練集和40%的測試集。訓練集會話部分的聚類由改進的K均值算法獲得。隨機選擇聚類中心，并且中心可能在每次迭代中都發生變化，直到收斂為止。形成聚類后，將對每個聚類進行唯一標識。

客戶端模塊：每當用戶請求網頁時，瀏覽器首先在緩存中查找該網頁是否存在。如果找到該頁面，則立即檢索該頁面并將其顯示給用戶，否則將請求轉發到實際的Web服務器。該請求由用戶訪問的一組頁面組成。服務器通過發送所請求的頁面以及預測列表進行響應。當瀏覽器空閑時，它將嘗試下載預測列表中列出的網頁，這些網頁目前在緩存中。當用戶請求下一頁時，用戶立即從本地緩存中獲取頁面，并且用戶立即獲得響應。因此，通過預取網頁，可以使用戶等待時間最小化。

聚類發現模塊：在線階段預測的第一步，通過使用集成距離度量將請求與所有現有聚類中心進行比較，可以確定最接近請求的簇。

聚類搜索模塊:根據從聚類發現模塊獲得的聚類搜索請求的網頁，檢索下一個頁面，并根據聚類中下一個頁面所在的會話數以及當前請求的頁面數來認定下一個頁面的計數。

頁面序列模塊：主要認定聚類搜索模塊接收的頁面列表。

3 基于用戶會話距離集成測量的聚類方法

對于給定的任意兩個用戶會話，為了計算彼此間的有效距離，需要查找會話間的匹配對。如果兩個頁面是相同的，則認為它們是匹配的。對于不匹配序列，則需要經過插入/刪除/替代操作后使其成為相似序列，然后對匹配和不匹配序列進行有效評分。目的是找到兩個會話間的兩兩比對數，插入/刪除/替換操作被認為是相同的(不匹配)。為匹配和不匹配適當的計分，分別為2和-1。通過計分，構建頁面對的評分矩陣，通過矩陣計算可得兩個Web用戶會話的距離，從而進一步計算會話間的相似度。

3.1 局部比對算法(SAM)

著名的局部比對算法最早由Smith-Waterman提出[12]，主要用于對共同分子子序列的局部比對，其中相似性的度量考慮到了任意長度序列的刪除和插入。對于不夠相似的序列局部比對顯得更為有應用價值，序列排序SAM方法可以有效衡量用戶會話間距離，側重于劃分基于用戶請求的導航序列。一組會話的兩個會話序列包含的Web頁面分為兩種，共同頁面和單獨頁面。共同頁面為兩組會話均訪問的頁面，單獨頁面表示各自訪問的獨立的頁面，與其他會話并無交叉。為了使兩組會話更為相似，兩組會話中相同的頁面被重新排序，彼此結合，單獨的頁面被插入或刪除。插入操作、刪除操作和重排操作的數量被用來計算兩組會話間的距離。排序操作改變的序列中，Web頁面是在一個會話訪問。SAM方法中關于會話距離的計算公式如式(1)所示，參數說明如表1所示：

dSAM(S1,S2)=MIN[(wdD+wiI)+δR]

(1)

表1 SAM計算方法參數說明

從公式(1)可以看出，采用兩會話間的距離由刪除操作、插入唯一元素和重排共同元素的開銷構成。由于刪除和插入是單獨操作，故ωD和ωI假設為1，并且δ=ωD+ωI。如果共同頁面的數量過多，但是訪問的頁面順序又不相同，那么需要花費較大的開銷查找共同元素并重新排序的計算操作。SAM方法無法區分出完全不同的會話和有相似序列的會話。

3.2 基于會話距離的局部序列比對方法(SDM)

鑒于SAM方法存在計算量大并且尚未考慮相似序列的會話等問題，本文對該方法做適度改進，通過引入評分矩陣、距離矩陣和線索矩陣的構建，將該方法有效應用在衡量任意兩個用戶會話的距離，從而判斷用戶的相似性，簡稱SDM方法。該方法采取通過計算用戶會話間頁面匹配數量的情況衡量會話的相似度，從而達到為用戶分組目的。通過衡量用戶之間的會話距離來度量用戶會話的相似度。

若給定兩組會話序列S1=(ABCDE)和S2=(ACDBE)，會話長度m=5，n=5，mismatch=-1，match=2。

計算用戶會話距離的主要步驟表現在構建評分矩陣、構建距離矩陣和計算線索矩陣，最后依據上述的三個矩陣計算會話的相似度。

3.2.1 構建評分矩陣

構建(m+1)*(n+1)的用戶的評分矩陣，記作Ps，公式如下：

Ps(i,0)=mismatch,其中0

Ps(0,i)=match,其中0

(2)

如表2所示，構建了會話S1和S2的評分矩陣，其中Ps(i,j)代表兩組會話對應頁面是否匹配，匹配計分2，否則計分-1。初始化該矩陣的第1行第1列為0，第2行第1列為-1。對于i如果S1(i)=S2(j)，代表匹配，否則代表不匹配。

表2 會話S1和S2的評分矩陣

3.2.2 構建距離矩陣Pd

計算會話間對應頁面的比對距離Pd(i,j)，其中i∈(0,m+1]，j∈(0,n+1]，計算方法如式(3)：

Pd(0,j)=Pd(0,j-1)+mismatch

Pd(i,0)=Pd(i-1,0)+mismatch

(3)

其中，第一項參數0概況了當比對評分為負時忽略不計的情況；第二項和第三項參數表示為插入/刪除/替換操作插入一個空缺所執行的延伸操作；第四項考慮到對兩個會話延伸序列的每一頁的比對。給定序列兩會話的Pd如表3所示。

表3 會話S1和S2的距離矩陣Pd

3.2.3 構建線索矩陣Pp

在計算Pd的同時構建線索矩陣Pp，主要為后續的遍歷工作做準備。首先，初始化該矩陣的第0行和第0列值為0。然后，根據Pd(i,j)的取值來源數據單元的所在位置top/left/left-top為Pp(i,j)分別賦值為1/2/3。

給定會話序列的線索矩陣如表4所示。

表4 會話S1和S2的線索矩陣Pp

3.2.4 相似度計算

依次構建評分矩陣、距離矩陣和線索矩陣后，開始計算用戶會話的相似度。具體計算方法是遍歷Pd，確定其中最大值的位置單元，對應在Ps中檢查是否匹配，如果匹配則SimCount值加1。同時，在Pp中根據Pp(i,j)的取值確定下一次的線索。重復遍歷Pd，直至其中出現值為0的單元。若Pd中多個單元格包含相同的最大值，重復上述步驟。

會話相似度的計算方法依賴于會話間的相似頁面的個數，會話距離度量方法參見式(4)。

dSDM(S1,S2)=

[Max(m,n)-SimCount]/Max(m,n)

(4)

其中，m和n分別代表會話S1和S2的長度；SimCount代表采用局部序列比對后的子序列數量；d∈[0,1]，1表示兩會話完全不一樣，0表示兩會話極度相似。因此，SDM可以區分完全不同的會話。

示例中的會話S1和S2的相似度經計算為0.2。

3.2.5 SDM算法

算法1：基于距離測量的序列比對算法

Input:用戶訪問會話序列S1，S2

Output: d(S1,S2)

Method:

Step1.根據式(2)構建Ps；

Step2.根據式(3)構建Pd，同時修正Pp的值；

Step3.遍歷Pd，確定其中最大值的位置MaxValLoc(i,j)

If (Ps(i,j)=2)

SimCount=SimCount+1;

掃描Pp(i,j)的值，確定next(i,j);

Step4.Repeat Step3直到Pd(i,j)=0；

Step5.If MaxCountPd(i,j)!=1

Repeat Step3;

Step6.根據式(4)計算d(S1,S2)。

3.3 基于集成距離的用戶會話相似性度量方法(SADM)

由于在SDM中缺少對兩個會話之間存在的直接匹配方式和通過插入間隙獲得的對齊方式的區分，進而提出基于集成距離的用戶會話相似度度量方法(SADM)，該方法融合SAM和SDM計算方法，可以獲得更準確的距離度量，既找到了SAM 方法中的單獨序列數量，又可基于SDM方法獲得無須調整頁碼順序的序列數量。該方法實際上捕獲了一對原始會話之間的序列方式，也獲得了局部比對后的比對序列和它們之間的唯一元素。計算方法如式(5)。

dINTE(S1,S2)=
[CAP-+2(|CAP+-CPD| )]/(|S1|+|S2|)

(5)

其中，dINTE(S1,S2)代表兩會話間的集成距離。

CAP-表示未匹配頁面的數量，一對會話的唯一網頁，不能通過插入間隙對齊。例如，如果S1=(A,B,C,D)和S2=(A,B,C,E)，那么D和E是唯一的。因此CAP-=2；CAP-表達含義等同于與SAM方法中的(wdD+wiI)。

CAP+表示匹配頁面數量，是通過SDM方法找到的匹配序列，可以通過插入間隙來對齊， 例如，S1=(A,B,C,F,G,H)和S2=(A,F,G,J,U)，則在S2中的A之后插入兩個間隙后，頁面F和頁面G分別與S1的F和G匹配，故CAP+是2。

CPD表示直接比對數量，指在原始會話中匹配的頁碼，例如，S1=(A,B,C,F,G,H)，S2=(A,E,G,F,U)，CPD為2。兩會話的頁面A與頁面F彼此匹配，頁面A位于會話的第1位，F位于第4位。|S1|與|S2|分別表示其會話的長度。

|CAP+-CPD|給出實際的頁面數可以通過插入間隙來對齊。即插入間隙是一項操作，移動現有頁面插入間隙的位置是另一種操作，故乘以系數2。

例如，給定會話：S1=(ABDFCABEDHGB)，S2=(ABGGEDABFEHGC)，匹配的路徑過程如下：

AB--EFCAB-EDHGB||||||||ABGGED-ABFE-HGC

分析序列，-表示間隙，|表示匹配。頁面AB是直接匹配，故CPD=2；經插入間隙操作后獲得的匹配頁面數CAP+=6；依據SAM剩下的單獨頁面是G，G，B，故CAP-=3；經計算，dINTE(S1,S2)=0.44，即表示兩會話的相似度為0.44。集成距離度量方法可以實現在不對序列做任何修改的前提下獲得任意兩個任意長度的會話之間距離。

4 實驗結果與分析

為了進一步驗證用戶相似度的實際性能，將其應用于用戶推薦的相關實驗，分別與Needleman-Wunsch全局比對算法(以下簡稱NW方法)和SAM算法比較，該方法應用于基于用戶相似度的Web預取系統取得了較好的推薦效果，并在用戶會話挖掘上表現了有效性。

與NW相比，該方法最大的優點在于能夠發現序列間的序列，因為該方法搜尋的范圍是在相似區域內的序列，而不是調整每一個序列的殘基。因此，所獲得距離值小于NW方法。例如，參見會話示例S1=(ABCDE)和S2=(ACDBE)，NW方法為頁面A排序。觀察會話S1和S2，訪問完A后均訪問C和D。唯一不同的是，S1中在訪問C、D之前還訪問了B，S2中用戶直接訪問的C和D。說明在頁面A、C和D之間有某種關聯性。在NW方法中，這種信息無法獲取到，但是在SADM的算法中可以挖掘出該關聯性，換言之，本文的方法搜索的序列數量將遠遠大于NW方法。與SAM相比，SADM側重基于插入、刪除和重排序方法查找會話間的集成距離，獲得的距離與SAM方法相比更有可比性。

4.1 實驗設計

實驗通過對不同的會話序列分別采用三種傳統方法進行測試，計算會話間的集成距離。首先采用簡短會話序列進行比對，分析不同方法的優劣。然后采用真實日志文件，基于Markov模型建立用戶訪問路徑序列，最后將其用于Web預取系統，衡量預取效果，并根據會話的相似度對用戶進行聚類，分析其聚類效果。

選取準確率(Pr)、召回率(Re)、預取綜合性能指標(PRS)以及聚類比率對實驗結果進行評價。其中PRS計算公式如下：

(5)

其中，P+和P-分別表示正確的和不正確的預測數，R+表示模型預測的請求數，|R|表示總請求數。

4.2 實驗結果

實驗一，選用4組不同會話序列，分別采用NW方法、SAM方法、SDM方法和SADM方法計算給定會話的集成距離。

表5 會話距離比較

如表5可以看出，本文提出的方法測量的會話距離較其他方法表現出了優勢。由于SADM方法挖掘了會話間隱含的序列，會話間的集成距離值相對較近，更為精確。因此，考慮到兩組會話的長度不等的問題，通過保留導航序列的相關信息尤為重要，SADM方法計算所得會話距離更為有效，那么聚類的準確率越高。

實驗二，針對聚類后的會話序列應用于預取系統，分析其預取效果。其中預測分為兩個階段，在第一個階段通過預處理服務器日志文件創建會話，60%的會話作為訓練集，經過集成聚類法對其聚類。一般情況下一個聚類總會包含一些單獨頁面，但是像起始頁面可能會出現在不止一個聚類中這種情況是可能的。另外，聚類是基于用戶訪問頁面的序列產生的，不是基于訪問頁面的類型。實驗中，為評估本文的預測模型要求而對最后一個頁面進行預測。測試會話的最后一頁先被刪除，其余頁面被用來查找最近的聚類中心。例如會話序列(P1,P2,…,Pn-1,Pn) ，頁面P1到頁面Pn-1用來查找最近的聚類，一旦查找成功，只有最后一個頁面如Pn-1用來預測下一個頁面。實驗選取信息網絡重點實驗室日志文件為數據源，數據清洗后進行會話聚類，然后應用于預取系統，使用SADM方法前后的預取效果如表6所示。

表6 預取效果比較

依據表中實驗結果可知，隨機抽取的四組數據集中，在使用SADM聚類方法后僅有第一組數據的準確率稍微有些降低。由于聚類使得狀態特性趨于一般化，四組數據在召回率方面表現很好，均有提高。綜合兩方面，對PRS指標的影響也是積極的，聚類后使得PRS上浮了3%左右。

對比本文改進的SADM方法與NW、SAM、SDM三種聚類方法對預取性能(PRS)的影響，如圖2所示。

圖2 不同聚類算法對預測模型的綜合影響

整體上，數據越密級，頁面相似的可能性越大，三種方法的預取性能越有優勢。當數據密集度低于10%時，NW和SAM算法對于數據的稀疏性并不敏感，預取效率維持在不高的水平。而SADM模型采用的聚類算法相比傳統方法在預取效率方面有明顯的優勢，具有可行性和高效性。

5 結語

隨著網絡應用的大面積普及以及網絡對象的爆炸性增長，通過分析用戶會話挖掘其相似性，并應用在Web預取系統有很大的意義。本文通過對傳統SAM的局部比對算法進行改進，提出了一種基于提取共同分子子序列的序列比對(SADM)計算會話距離的用戶聚類方法。文中首先考察為不同會話構建評分矩陣；再者，通過計算會話間相應頁面的比對距離構建距離矩陣，具體地引入線索矩陣為后續的遍歷做鋪墊；最后，選取會話長度不一的數據集進行測試分析，并將改聚類結果應用于預取系統，分析預取效果。實驗驗證了該模型有較好的聚類效果并在預取性能方面具有一定優勢。由于SADM方法兼顧了不同會話長度的問題和保留用戶訪問頁面序列的問題進行測量會話的長度，通過對用戶會話的合理度量，可以進一步地對用戶聚類，從而能夠更好地應用在頁面預測、Web緩存和預取中。進一步的工作，將該方法用于大數據背景下的用戶聚類中，考慮基于滑動窗口的預測模型，增加數據集數量進行綜合評價，進而改進聚類效果。