Web日志矩陣挖掘算法研究

邵天會

【摘要】 Web日志常用的挖掘算法焦點在用戶訪問習慣上提取相關數據，主要的算法有Apriori，最大向前算法，拓撲算法等，這些算法只是簡單的設計用戶的訪問頻度，通過用戶訪問頻度進行達到用戶興趣度的測量，其實這不是很精確的解決方法。因為影響網頁相應的因素很多，比如網頁之間的自動鏈接，頁面和頁面之間的相對位置都會起到至關重要的作用。矩陣算法進行有向圖的轉換，用戶信息的存儲利用，同時利用Apriori算法進行事務集的篩選，統計，綜合各種算法的優點，提出一種基于矩陣的改進的挖掘算法進行用戶興趣度的挖掘。

【關鍵字】 Web日志 挖掘算法 用戶興趣度

一、基礎概念

定義 1：會話矩陣：用戶會話集合的二維矩陣，列為會話，行為訪問路徑，每行代表一個用戶訪問一次的記錄，一列代表用戶對該站點訪問的總量。

定義 2：用戶訪問的遍歷矩陣：行為訪問路徑，列為當前訪問路徑結束或者跳轉。添加支持度m，構成路徑：引用頁面----訪問頁面----頁面訪問頻度。同時在矩陣的第一個單元格設置一個null值，表示用戶直接進入該網站的url，而沒有通過其他的頁面跳轉，如果網站有n個url，該網站可以形成n+1矩陣。

定義 3：頁面的距離：會話矩陣任意兩行x，y。如果x>0則x=1，同理y>0則y=1，構成向量x，y-à0，1。我們就稱x，y之間的頁面距離為d。

定義 4：興趣支持度：假設所有訪問路徑S中，t是屬于S的子集，如果x屬于t，那么可以認為x和S中的路徑前m位是相同的，不同的t就得出多種相同m位，歸集相同的部分得出用戶的興趣支持度

定義 5：支持----偏向度：設支持度是s，興趣支持度為 P則支持----偏向度為Ps=（S×P）。

二、基于用戶訪問的矩陣算法實現

算法步驟：數據清理、用戶識別、會話識別、相似用戶的相關頁面聚類及頻繁路徑。

2.1 數據清理

只保留get方式獲取的數據，過濾掉其他和算法不相關信息。

2.2 用戶識別

通過IP地址進行識別用戶。

2.3會話識別

結合最大向前路徑和時間窗口模式進行設計算法-----用戶事務識別算法，該算法由事務分割、事務合并兩部分組成。事務分割：將web數據庫通過最大向前路徑和時間窗口模式進行分割為符合兩者標準的短事務；分割原則：當相鄰的訪問路徑超過了設定的時間窗口，或者不同的IP事務集中已經存在該路徑，那么就進行分割。分割結果：一個頁面只包含在一個事務中。例如表1-1中第1-3條記錄，由于IP地址不同相同的頁面被分割為3個事務。

記錄合并：將用戶本來屬于同一路徑，但是在分割階段進行不同實務分割，進行按照IP地合并，即相同用戶訪問記錄合并。

例如：表1-2顯示的是進行合并后的結果。

按照定義 4建立用戶會話矩陣：以訪問路徑為行，回話ID為列，建立會話矩陣SM[][]，SM[m][n]：用戶訪問頁面m中第n次訪問。SM[m][]：針對某具體頁面m的訪問記錄。SM[][n]：訪問記錄n對所有瀏覽過的頁面。用戶會話矩陣無法顯示用戶訪問先后次序問題，因此我們設計了用戶訪問的遍歷矩陣。根據定義5得出：以訪問路徑為行，標識ID為列生成路徑MT[][]矩陣，MT[m][n]：m頁面鏈接訪問n頁面的會話集合。第一行表示用戶直接訪問該網頁，不經過其他跳轉，一般可視為用戶首次進行會話。第一列表示用戶結束本次會話，跳轉到其他頁面或者結束訪問。

2.4 相似用戶的相關頁面聚類

本算法的設計中，關鍵是利用訪問頁面頻度st和頁面訪問距離dt對網頁進行篩選，根據預先設定的訪問頁面頻度st，將頁面的訪問次數歸集到Fs中，從而把Fs中的小于dt頁面距離值的進行聚類。

2.5 訪問路徑的挖掘

假設S_Set={pag-1， pag-2，…pag-n}，通過用戶訪問的遍歷矩陣MT[i][j]中pag-1，pag2…pagn相對應的i和j值，生成新的矩陣MT[n+1][n+1]，然后在其中找出所有大于偏向----支持度的項，最后構成我們需要的訪問路徑集合，再將得到的頻繁路徑合并，到無法合并停止，即我們需要的頻繁訪問路徑

三、驗證性試驗

平臺：IOS平臺利用Edv C++ 實現該挖掘算法和經典的Apriori算法，在某學校的網站上對50M日志文件進行分析，以1M，2.7M，3.2M，5.9M，6.7M，7.2M，8.7M7個測試點進行用例分析。在Intel（R）Celeron（R）CPU 2.8 GHz，2GRAM平臺進行數據測試，試驗結果如圖1-1所示。

圖1-1得出相同數據和平臺上，用戶矩陣算法比Apriori算法用時明顯降低，并且隨著數據的增大用戶矩陣算法表現出良好的穩定性，曲線變化平緩，表現出算法的擴展性優點，而Apriori算法隨著數據的增大時間曲線波動變化明顯，因此在面對此類問題時本文的用戶矩陣算法明顯優于Apriori算法。

參 考 文 獻

[1]Bing Liu（美）.Web Data Mining[M].北京：清華大學出版社，2009.

[2]朱志勇，徐長梅，劉志兵，胡晨剛.基于貝葉斯網絡的客戶流失分析研究[J].計算機工程與科學.2013（03）