聚類挖掘在電子商務中的應用

[摘 要] 闡述了在電子商務系統中的研究和應用中，利用基于關聯規則的多層次、超圖分割聚類方法，對Web網頁和用戶進行有效聚類。該方法借助網站層次圖，可以根據實際需要，在各個層次上進行聚類分析，僅將高度相關的網頁和用戶聚在同一類，而將關聯性較小的網頁排除在聚類外。

[關鍵詞] 聚類挖掘 電子商務 關聯規則 超圖

由于Web具有方便、易用、高效的特點，電子商務顯示出越來越強大的生命力，同時各種商業Web站點也面臨越來越激烈的競爭。

有效聚類Web用戶和網頁對改進網站質量、完善電子商務中產品銷售策略具有十分重要的意義。在電子商務中，瀏覽模式相似的用戶具有相似的購買習慣，通過聚類挖掘，將這些用戶聚集在同一類，可以制定相似的銷售策略。根據瀏覽模式聚集在同一類中的網頁，是大多數用戶共同訪問的網頁，在這些網頁之間建立超鏈接，以方便用戶使用。

現有的基于瀏覽模式的Web聚類挖掘研究方法中，只要用戶請求了一個網頁，便認為用戶閱讀了該網頁，事實上有些被請求的網頁用戶并不關心，不會認真閱讀的。通常一個實用網站包含大量的網頁，現有的Web聚類方法將每個網頁當作一個被聚項，無論用戶訪問的頻繁與否，總是歸入一個類中，結果造成有些類中的網頁之間幾乎沒有相關性。

鑒于以上考慮，本文提出了基于關聯規則和超圖分割的聚類Web網頁及用戶的方法，不僅考慮了用戶瀏覽網頁的時間長短，還考慮了聚類層次（級別），將不相關網頁項排除在聚類之外，使每個類中的網頁具有較高的相關性。采用這種方法，可以優化Web站點拓撲結構，指導企業調整營銷策略，給客戶提供動態的個性化的高效率服務。

一、建立電子商務網站的層次模型

建立電子商務網站的層次模型出于三點考慮。第一，網站中網頁內容組織呈現樹狀結構。第二，在進行關聯規則挖掘過程中，可能最下一級挖掘不出達到指定Support的強規則，但是能從上級層次挖掘出達到指定Support的強規則，或根據實際需要在某一個層次進行聚類分析。第三，對于電子商務網站，有些用戶雖然訪問了某網頁，但是對其內容并不感興趣，可能只是掃一眼就放棄。在此情況下，不應該認為用戶認真閱讀了該網頁，所以應該記錄網頁的長度，通過計算用戶的瀏覽時間和網頁長度的比值來判斷用戶是否真正認真閱讀了該頁內容。

層次模型采用樹狀結構來描述，節點的數據域包含對應網頁的層次名稱（編號）和網頁長度。樹根應該取所研究的網站根目錄（研究整個網站）或所研究的網站分支的最上層目錄。在建立層次模型時，應根據網站的具體情況決定采用的方法。通常情況下，網頁文件名能完全反映網頁所在的層次，可以采用完全自動方法進行轉換。

二、基于關聯規則的聚類挖掘

1.預處理

在Web站點中，服務器日志文件記錄用戶的訪問方式、所訪問的頁面、訪問時間、用戶IP地址等信息，通過收集Web日志所記錄的用戶瀏覽信息可以對網頁和用戶聚類。首先要對收集到的數據進行預處理，獲得每個用戶所訪問的網頁序列。將一個用戶對某個特定網站的一次連續瀏覽（從登錄該網站一直到離開該網站）所訪問的網頁序列稱為一個用戶瀏覽事務。如果用戶中途訪問了另一網站，而后又返回該網站，返回后所瀏覽的網頁序列將組成另一個用戶瀏覽事務。處理后的事務序列將具有如下的形式：

u_id（用戶標志編號），p_id(頁面編號)序列

2.挖掘關聯規則并計算關聯規則可信度的平均值

對經過預處理的瀏覽事務進行關聯規則挖掘，挖掘出滿足一定支持度的關聯規則。關聯規則是在挖掘出頻繁網頁集的基礎上發現的，由于頻繁網頁集是大多數用戶在一個事務，即一次網站訪問中所共同瀏覽的頁面，所以頻繁網頁集反映了這些網頁或共同訪問這些網頁的用戶之間存在一定的聯系，如網頁內容高度相關。在進行聚類時，應該首先考慮將頻繁網頁集中的網頁聚合在一個類中。

通常挖掘頻繁網頁集的方法是在給定某一支持度的基礎上進行的，滿足該給定支持度的一個頻繁網頁集中的網頁可能是另一個或另幾個頻繁網頁集中的元素，那么將這些網頁應該聚合到前一項目集還是后面的某一項目集？正確的選擇應該是看這些網頁和哪一項目集聯系更為密切，可采用的方案有兩種：提高支持度繼續挖掘頻繁網頁集直到每一網頁僅處于一個項目集或利用各頻繁網頁集中網頁之間關聯規則的可信度。進一步仔細分析，前一方案不可取，首先可能不存在一個支持度使每個網頁僅位于一個頻繁網頁集中；其次即使存在這樣一個支持度，再進行多次的頻繁網頁集挖掘代價也太高，實際中是不可行的。

相比之下，后一方案可行度高，在挖掘出滿足指定支持度的頻繁網頁集的基礎上，可以較為方便地計算出每一個頻繁網頁集中的每個關聯規則的可信度?？尚哦鹊拇笮∫卜从沉司W頁之間關聯的密切程度。為此，計算每個頻繁網頁集中所有的關聯規則的可信度，在此基礎上計算其所有關聯規則可信度的平均值，用可信度的平均值反映網頁與不同的頻繁網頁集之間聯系的密切程度。

3.利用超圖進行網頁聚類

超圖是對圖的擴充，允許一條邊連接三個或三個以上的點。每條邊帶有權的超圖稱為加權超圖，在挖掘出頻繁網頁集和關聯規則的基礎上，可以得到網站的加權超圖。超圖中的一個頂點代表一個網頁，超圖的邊稱為超邊，超邊連接的頂點是頻繁網頁集中的網頁。每個超邊的權取該邊所對應的頻繁網頁集中所有關聯規則可信度的平均值。

上圖為超圖的示意圖，代表A，B和C所組成的頻繁網頁集的超邊的權值，0.7是A，B和C三個網頁所組成的所有關聯規則可信度的平均值。

為了使聚集結果的每個類中的網頁具有高度相關性，超圖中僅包含出現在強關聯規則中的網頁。利用超圖進行聚類的方法是逐步切割超邊將超圖進行分割，分割成多個子超圖，分割的原則是被切割的超邊的權值和盡可能小，從而保證將相互關聯比較小的網頁分割在不同的子圖，而將關聯比較密切的網頁保留在同一子圖內。分割過程繼續進行直到被切割超邊的權值和與留下的超邊權值和的比值大于某一臨界值，或所得到的子超圖數目達到某指定值，分割過程結束，留下的各子超圖便是聚類的結果。每一個子超圖對應一個聚類，超圖中的各頂點代表該聚類中所包含的網頁。

4.事務和用戶聚類

在將網頁進行聚類的基礎上，可以將瀏覽網站的事務和用戶進行聚類。瀏覽事務聚類的原則是根據事務和網頁聚類的相似度進行，將事務聚合在相似度最高的網頁類中。事務和網頁類的相似度可以按照如下公式計算：

|Tj∩Ci|/|Ci|

其中，Tj為一個事務，Ci為一個聚類，|Tj∩Ci|為Tj和Ci中所包含的相同頁面的數目，|Ci|為Ci中所包含的頁面數目。

在記錄網站用戶標志的情況下，可以通過用戶的瀏覽事務聚類將用戶進行聚類，即將訪問相似網頁的用戶聚在同一類。

5.聚類挖掘結果的可視化

聚類挖掘的結果是多維的，由于笛卡兒坐標系最多只有三個坐標，所以不能用通常的方法作圖。而且這些多維的數據集一般不含有空間語義，數據集的各維之間沒有空間連貫性，這也很難用傳統的二維或三維圖形直接表達多維空間。本文采用了一種通過主分量分析將多維空間坐標轉換為三維坐標的挖掘結果可視化方法，實現聚類挖掘結果的可視化。根據生成的各個點之間的距離和簇的形狀，我們可以有效地從大量數據中發現對我們有用的信息。

三、結論

闡述了在電子商務系統的研究和應用中，利用基于關聯規則的多層次、超圖分割聚類方法，對Web網頁和用戶進行有效聚類。該方法借助網站層次圖，可以根據實際需要，在各個層次上進行聚類分析；在挖掘出滿足一定Support的關聯規則的基礎上進行聚類，僅將高度相關的網頁和用戶聚在同一類，而將關聯性較小的網頁排除在聚類外。該方法對于改進網站質量、完善電子商務中產品銷售策略具有十分重要的意義。

參考文獻:

[1]Pei J， Han J， Behazad M， et al. Proceedings of the 1999 KDD Workshop on Web Mining[C]， Kyoto: PKDD， 1999. 396-407

[2]Cooley R， Mobasher B， Srivastava J. Data Preparation for mining World Wide Web Browsing Patterns [J]. Knowledge and Information System， 1999，1(1): 25-29

[3]Karypis G， Aggarwal R， Kumar V， et al. Multi-level Hypergraph Partitioning: Applications in VLSI Domain[R]. Minnesota: University of Minnesota， Department of Computer Science， 1997.1-50

[4]劉子維等：一種聚類挖掘結果的可視化方法[J].計算機應用研究，2006，23（5）：75-76

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>