基于改進頻繁模式聚類算法的網站結構優化

摘要：分析了現有頻繁模式聚類算法的不足，提出了距離函數改進，并在模式聚類函數的基礎上生成一個壓縮的偏序（partial order）的算法（FCWSO算法）。實驗結果顯示該算法可以對頻繁序列模式進行高效、高質量的壓縮，可以得到數量更少、信息量更大的模式，從而提高發現的頻繁訪問序列的興趣性。

關鍵詞：數據挖掘； 頻繁序列模式； 壓縮； Web設計

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)04－1222－02

由于全球Web 站點數目迅速增長，Web 站點的信息量及其復雜度也在迅速上升，給用戶訪問增加了一定的難度。人們不得不借助關聯規則、序列模式和頁面聚類等Web日志挖掘工具來獲得更深層次的用戶訪問信息。針對網站目前的訪問信息，對網站的設計進行優化，建設一個更合理、更易用、注重個性化和相關性的網站成為研究的熱點之一[1]。

現有的一些Web站點設計方法中，提出了利用尋找用戶頻繁訪問的頁組來實現調整網站結構的算法。例如文獻[2]是應用基于頻繁項集的關聯規則來找到頻繁訪問路徑，以及稱做關聯規則的超圖劃分的聚類方法來進行URL集聚類，然后通過推薦引擎進行在線推薦。文獻[3]提出了結合站點拓撲結構和Web頁面內容的頁面聚類改進算法以提高挖掘結果的興趣性。文獻[4]指出數據流頻繁模式挖掘在Web中發現頻繁模式，可以優化網站結構，提高網站性能。目前許多頻繁序列模式挖掘及其更新算法已提出，如AprioriSome[5]、GSP[6]、SPADE[7]、ISE[8]、FASTUP[9]等。但是現階段頻繁序列模式挖掘，研究的瓶頸已不在挖掘的效率上，而是在其結果的可用性和可理解性上。當頻繁序列模式的數量非常龐大時，人們很難從中挖掘有用的知識。為了解決這個問題，一個很自然的想法就是將挖掘出來的結果再進行精簡壓縮，從而可以得到數量更少、信息量更大的模式。

本文提出的基于頻繁序列模式壓縮技術的網站結構優化算法（FCWSO算法），挖掘網站中被瀏覽者頻繁訪問的網頁集合以及序列模式挖掘算法用于挖掘網站中頻繁訪問的頁面序列，以發現隱藏在其中的用戶訪問模式，合理、有效地優化站點的結構，最終為用戶提供一個方便快捷的信息獲取環境。

1FCWSO算法概論

本算法是以瀏覽者頻繁訪問網頁形成的頻繁序列模式為輸入，將頻繁序列模式總結成近似偏序。算法分兩個步驟：a)充分考慮了時間和效率的關系，提出了一種高效的距離定義方法，并根據距離函數進行聚類；b)以簡便、保持信息不丟失的方法生成偏序。本算法的主要目的就是希望能從序列數據中挖掘出更精簡、更易理解的模式，并可排除部分噪聲的干擾。

所謂偏序就是一個三維向量p=（V，E，l）。其中：V是所有頂點的集合；EV×V是所有邊的集合，通過邊可以表示頂點之間的關系，它們是自反，反對稱和傳遞的；l是從頂點到屬性項的映射函數。在前面的例子中，用的均是單屬性項，但也可以將一個頂點與一個屬性集相映射。對于一個partial order p=(V，E，l)的傳遞約簡就是將圖中利用傳遞約簡后刪除邊的最小關系集合。筆者用圖形化的形式來表示這種傳遞約簡后的模式，可以讓它們更加容易被人理解。

2聚類算法

2．1距離函數

現實的數據挖掘中，筆者能得到支持度大小信息。支持度反映的是一個模式支持的交易數量。在一定程度上，對于支持度大小相仿的模式，尤其是支持度均比較大的模式，如果支持度的大小相似，則這兩個模式出現在同一條交易中的概率相對也是較大的。本文也考慮用支持度大小來聚類，其距離公式為

D1（P1，P2）=｜‖T(P1)‖-‖T(P2)‖｜/max(‖T(P1)‖，‖T(P2)‖)。

為了提高聚類效果，筆者考慮將序列模式本身的信息加入進來。因為序列本身的相似程度也隱含地反映了它們一起出現的概率。為了讓產生的距離在不同長度的序列中具有可比性，文獻[10]中定義了ApproxMAP算法。此算法的目的是在序列數據庫中挖掘出更長的頻繁序列模式，從而展現給用戶更少的模式。它沒有采用傳統的模式精確匹配的方法，首先定義了兩個模式之間的距離函數replace：

此距離函數與雅可比系數(Jaccard coefficient)很相似，但它更注重兩個模式之間的相同模式。當距離函數定義后，此算法可以將所有的序列模式進行聚類，然后對每一個group的序列利用multi align的方法，將一個group中的序列總結成一條有權重的序列。

采用這個距離函數，有效地將序列的支持度信息和序列模式本身所包含的信息結合起來。實驗證明可以得到比較好的聚類效果。

2．2算法分析

在前面小節中，已經定義出任意兩個閉合模式之間的距離。有了這個距離函數，就可以對輸入的閉合模式進行聚類。筆者需要將距離相近的模式聚類到一起，所以最常用的聚類方法均可以用到這里來。在本算法中，不過多地敘述聚類方法的細節，所以實現了距離函數的k－中心方法下的聚類。

算法將閉合序列模式聚類

輸入:閉合模式集P={P1，P2，…，Pm}

聚類簇數K輸出: 需要連接的序列位置列表。

輸出:k個閉合模式集C1，C2，…，Ck

load pattern P1，P2，…，Pm

initialize C1，C2，…，Ck

/*計算兩個模式之間的距離*/

for each Pi

for each Pj，j

DISTij=D(Pi，Pj)

/*對模式進行聚類*/

repeat

DistributeSamples();/*指派每個剩余的對象給離它最近的中心點所代表的簇*/

CalcNewClustCenters();/*重新計算該簇的中心點*/

until每個簇的中心都不發生變化；

/*除掉每個聚類中的冗余項*/

for each Cluster Ci(i=1…k)

for each Pattern Pn in Cluster Ci

if(IsCovered(Pn)==True)

remove Pn from Ci

returnCi(i=1 … k)

3實驗結果

在本章中，筆者在真實的數據集上測試了算法FCWSO的性能和效果。此算法是用C++實現，在 VS .NET 2003的環境下編譯運行的。所有的實驗均在操作系統為Windows XP，CPU為Celeron(R) 2.02 GHz，內存為512 MB的單機上運行。

實驗部分主要分為聚類效果的實現和偏序的可視化。在實驗中主要用到了Gazelle數據文件，這個數據曾用在KDDCup2000競賽中，現在可以從http://www.ecn.purdue.edu/KDDCUP/得到。此數據中一共提供了70 163個會話，每個會話包含一序列的瀏覽頁面。這個數據庫文件也是一個稀疏的數據庫文件，它包含1 037個不同的屬性項；每個會話的平均長度只有2.50，實驗中稱之為Gazelle_Data。

圖1是Gazelle_Data中挖掘出來的偏序樣例。Gazelle_Data是網站用戶的點擊流數據，所以每個節點均代表網站的一個子域名(或頁面)。在此例中，1代表的是main/home\\jhtml，為此網站的主頁；15代表的是 main/registration\\jhtml，為注冊頁面；19代表的是articles/dpt_about\\jhtml，是網站介紹頁面。雖然從有些頁面的名稱中很難推斷出其功能，但是可以推測，這些頁面均是比較重要的頁面，用戶的點擊量相對較大，可以將它們放在主頁上比較重要的位置。 

圖2也是Gazelle_Data中挖掘出來的偏序樣例，可以看到更有趣的知識。其中：3代表的頁面為 main/search_results\\jhtml， 是一個搜索頁面；6代表的頁面為 products/productDetailLegwear\\jhtml，是一個顯示商品詳細信息的頁面;而10代表的頁面是 main/boutique\\jhtml，為小商店頁面。這說明當用戶登錄主頁之后，有兩種常用的方式來查看具體的商品信息，即通過搜索頁面來搜索商品及通過查看小商品的信息列表來查看商品的信息，這也是一般購物網站的常見方式。

4結束語

筆者對Web網站結構優化的FCWSO算法是在頻繁序列模式的基礎上試圖將閉合序列模式進一步壓縮，使其變成更精簡也更易理解的偏序形式。本文首先討論了模式之間距離的計算方法，并且提出了結合序列支持度信息和模式間相同項權重值的距離函數。利用此函數，可以在高效的情況下對閉合序列模式進行聚類，且取得很好的聚類效果。其次，描述和證明了怎樣在保證信息不丟失的情況下，從一個聚類中總結出一個最精簡的偏序出來。實驗結果顯示該算法能夠在高效的情況下挖掘出一些用其他的方法無法挖掘出來的知識。這對于開發一些目的性強的網站具有較大幫助（如電子商務網站），可以提高Web用戶的服務質量，使用戶享用到滿意的個性化服務。

參考文獻：

［1］WANG Y W， WANNG D W. Design strategy ofWeb page for e－supermarket[C]// JIANG Ping－yu，et al. Proc of 2001 International Conference on eCommerce Engineering 2001. Xi’an: China Machine Press， 2001:101－107.

[2］MOBASHER B， COOLEY R， SRIVASTAVA J. Creating adaptive sites through usage－based clustering of URLs[C]//Proc of1999 IEEE Knowledge and Data Eng Exchange Workshop.NewYork:IEEE Press，1999:32－37.

[3］楊怡玲，管旭東，尤晉元. 基于頁面內容和站點結構的頁面聚類挖掘算法[J]. 軟件學報，2002，13(3): 467－469.

[4］潘云鶴，王金龍，徐從富. 數據流頻繁模式挖掘研究進展[J]. 自動化學報， 2006， 32(4) :594－602.

[5］AGRAWAL R， SRIKANT R. Mining sequential patterns[C]//Proc ofthe 11th Int’l Conf on Data Engineering. Washington D C: IEEE Computer Society Press，1995:3－14.

[6］AGRAWAL R， SRIKANT R. Mining sequential patterns: generalizations and performance improvement[C]//Proc of the 5th Int’l Conf on Extending Database Technology. Heidelberg: Springer－Verlag， 1996:3－17.

[7］ZAKI M J. SPADE: an efficient algorithm for mining frequent sequences[J]. Machine Learning Journal， Special Issue on Unsupervised Learning， 2001， 42(1/2): 31－60.

[8］MASSEGLIA F， PONCELET P， TEISSEURE M. Incremental mining of sequential patterns in large database[J]. Data and Knowledge Engineering， 2003， 46(1): 97－121.

[9］LIN M Y， LEE S Y. Incremental update on sequential patterns in large databases[C]//Proc ofthe 10th IEEE International Conference on Tools with Artificial Intelligence. Taipei: [s.n.]，1998: 24－31.

[10］KUM H C ， PEI J， WANG W， et al.Approx MAP: approximate mining of consensus sequential patterns[C]//Proc ofthe 3rd SIAM International Conference on Data Mining. San Francisco， CA:[s.n.]， 2003: 311－315.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”