Web日志矩陣挖掘算法研究

邵天會(huì)

【摘要】 Web日志常用的挖掘算法焦點(diǎn)在用戶訪問(wèn)習(xí)慣上提取相關(guān)數(shù)據(jù)，主要的算法有Apriori，最大向前算法，拓?fù)渌惴ǖ?，這些算法只是簡(jiǎn)單的設(shè)計(jì)用戶的訪問(wèn)頻度，通過(guò)用戶訪問(wèn)頻度進(jìn)行達(dá)到用戶興趣度的測(cè)量，其實(shí)這不是很精確的解決方法。因?yàn)橛绊懢W(wǎng)頁(yè)相應(yīng)的因素很多，比如網(wǎng)頁(yè)之間的自動(dòng)鏈接，頁(yè)面和頁(yè)面之間的相對(duì)位置都會(huì)起到至關(guān)重要的作用。矩陣算法進(jìn)行有向圖的轉(zhuǎn)換，用戶信息的存儲(chǔ)利用，同時(shí)利用Apriori算法進(jìn)行事務(wù)集的篩選，統(tǒng)計(jì)，綜合各種算法的優(yōu)點(diǎn)，提出一種基于矩陣的改進(jìn)的挖掘算法進(jìn)行用戶興趣度的挖掘。

【關(guān)鍵字】 Web日志 挖掘算法 用戶興趣度

一、基礎(chǔ)概念

定義 1：會(huì)話矩陣：用戶會(huì)話集合的二維矩陣，列為會(huì)話，行為訪問(wèn)路徑，每行代表一個(gè)用戶訪問(wèn)一次的記錄，一列代表用戶對(duì)該站點(diǎn)訪問(wèn)的總量。

定義 2：用戶訪問(wèn)的遍歷矩陣：行為訪問(wèn)路徑，列為當(dāng)前訪問(wèn)路徑結(jié)束或者跳轉(zhuǎn)。添加支持度m，構(gòu)成路徑：引用頁(yè)面----訪問(wèn)頁(yè)面----頁(yè)面訪問(wèn)頻度。同時(shí)在矩陣的第一個(gè)單元格設(shè)置一個(gè)null值，表示用戶直接進(jìn)入該網(wǎng)站的url，而沒(méi)有通過(guò)其他的頁(yè)面跳轉(zhuǎn)，如果網(wǎng)站有n個(gè)url，該網(wǎng)站可以形成n+1矩陣。

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

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

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

二、基于用戶訪問(wèn)的矩陣算法實(shí)現(xiàn)

算法步驟：數(shù)據(jù)清理、用戶識(shí)別、會(huì)話識(shí)別、相似用戶的相關(guān)頁(yè)面聚類及頻繁路徑。

2.1 數(shù)據(jù)清理

只保留get方式獲取的數(shù)據(jù)，過(guò)濾掉其他和算法不相關(guān)信息。

2.2 用戶識(shí)別

通過(guò)IP地址進(jìn)行識(shí)別用戶。

2.3會(huì)話識(shí)別

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

記錄合并：將用戶本來(lái)屬于同一路徑，但是在分割階段進(jìn)行不同實(shí)務(wù)分割，進(jìn)行按照IP地合并，即相同用戶訪問(wèn)記錄合并。

例如：表1-2顯示的是進(jìn)行合并后的結(jié)果。

按照定義 4建立用戶會(huì)話矩陣：以訪問(wèn)路徑為行，回話ID為列，建立會(huì)話矩陣SM[][]，SM[m][n]：用戶訪問(wèn)頁(yè)面m中第n次訪問(wèn)。SM[m][]：針對(duì)某具體頁(yè)面m的訪問(wèn)記錄。SM[][n]：訪問(wèn)記錄n對(duì)所有瀏覽過(guò)的頁(yè)面。用戶會(huì)話矩陣無(wú)法顯示用戶訪問(wèn)先后次序問(wèn)題，因此我們?cè)O(shè)計(jì)了用戶訪問(wèn)的遍歷矩陣。根據(jù)定義5得出：以訪問(wèn)路徑為行，標(biāo)識(shí)ID為列生成路徑MT[][]矩陣，MT[m][n]：m頁(yè)面鏈接訪問(wèn)n頁(yè)面的會(huì)話集合。第一行表示用戶直接訪問(wèn)該網(wǎng)頁(yè)，不經(jīng)過(guò)其他跳轉(zhuǎn)，一般可視為用戶首次進(jìn)行會(huì)話。第一列表示用戶結(jié)束本次會(huì)話，跳轉(zhuǎn)到其他頁(yè)面或者結(jié)束訪問(wèn)。

2.4 相似用戶的相關(guān)頁(yè)面聚類

本算法的設(shè)計(jì)中，關(guān)鍵是利用訪問(wèn)頁(yè)面頻度st和頁(yè)面訪問(wèn)距離dt對(duì)網(wǎng)頁(yè)進(jìn)行篩選，根據(jù)預(yù)先設(shè)定的訪問(wèn)頁(yè)面頻度st，將頁(yè)面的訪問(wèn)次數(shù)歸集到Fs中，從而把Fs中的小于dt頁(yè)面距離值的進(jìn)行聚類。

2.5 訪問(wèn)路徑的挖掘

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

三、驗(yàn)證性試驗(yàn)

平臺(tái)：IOS平臺(tái)利用Edv C++ 實(shí)現(xiàn)該挖掘算法和經(jīng)典的Apriori算法，在某學(xué)校的網(wǎng)站上對(duì)50M日志文件進(jìn)行分析，以1M，2.7M，3.2M，5.9M，6.7M，7.2M，8.7M7個(gè)測(cè)試點(diǎn)進(jìn)行用例分析。在Intel（R）Celeron（R）CPU 2.8 GHz，2GRAM平臺(tái)進(jìn)行數(shù)據(jù)測(cè)試，試驗(yàn)結(jié)果如圖1-1所示。

圖1-1得出相同數(shù)據(jù)和平臺(tái)上，用戶矩陣算法比Apriori算法用時(shí)明顯降低，并且隨著數(shù)據(jù)的增大用戶矩陣算法表現(xiàn)出良好的穩(wěn)定性，曲線變化平緩，表現(xiàn)出算法的擴(kuò)展性優(yōu)點(diǎn)，而Apriori算法隨著數(shù)據(jù)的增大時(shí)間曲線波動(dòng)變化明顯，因此在面對(duì)此類問(wèn)題時(shí)本文的用戶矩陣算法明顯優(yōu)于Apriori算法。

參 考 文 獻(xiàn)

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

[2]朱志勇，徐長(zhǎng)梅，劉志兵，胡晨剛.基于貝葉斯網(wǎng)絡(luò)的客戶流失分析研究[J].計(jì)算機(jī)工程與科學(xué).2013（03）