邱 波

基于粗糙集的 Web事務(wù)聚類算法

邱 波

針對現(xiàn)有 Web 數(shù)據(jù)挖掘方法發(fā)現(xiàn)的知識(shí)和規(guī)則存在不精確或不完全的問題，將粗糙集引入到 Web 挖掘中，進(jìn)行Web事務(wù)聚類。粗糙近似算法基于用戶訪問序列的順序和內(nèi)容建立用戶事務(wù)相似度矩陣，運(yùn)用基于相似度矩陣的粗糙上近似提取初始類，使用相對相似性的條件作為合并準(zhǔn)則，基于約束相似性的上近似形成后續(xù)類。粗糙近似算法能夠有效挖掘Web訪問日志，聚類 Web 事務(wù)，發(fā)現(xiàn)用戶訪問 Web 頁面的模式。

Web挖掘；粗糙集；相似上近似；約束相似性上近似；事務(wù)聚類

1 概述

聚類是按照事物間的相似性進(jìn)行區(qū)分和分類的過程，是一種無監(jiān)督的分類。聚類分為硬計(jì)算方法和軟計(jì)算方法。在硬聚類方法中，根據(jù)相似度將對象劃分到不同的聚類中，不同的聚類之間沒有交集。在軟聚類方法中，一個(gè)對象可以被分配到2個(gè)或者2個(gè)以上的聚類中。軟聚類可能具有模糊或粗糙的邊界域[1]。

用戶事務(wù)聚類是一個(gè)通過 Web 網(wǎng)站相關(guān)信息的聚類得到具有相似訪問興趣的用戶事務(wù)集合的整理和挖掘過程。用戶事務(wù)聚類可用來準(zhǔn)確預(yù)測用戶瀏覽行為[2]， 理解和影響購買模式[3]并實(shí)現(xiàn)個(gè)性化用戶訪問服務(wù)等。Rough 理論[4]是由波蘭華沙理工大學(xué) Pawlak 教授于 20 世紀(jì) 80 年代提出的一種研究不完整、不確定的知識(shí)和數(shù)據(jù)的表示、學(xué)習(xí)、歸納的理論方法。對于有大量噪聲和孤立點(diǎn)的 Web 數(shù)據(jù)來說，粗糙集理論正是處理隱藏在信息中的不確定性、含糊性的有力工具。它解決了一般的聚類算法發(fā)現(xiàn)知識(shí)和規(guī)則不夠完整、不夠準(zhǔn)確的難題。本文將利用粗糙集理論對 Web 事務(wù)進(jìn)行聚類，從用戶瀏覽網(wǎng)站的數(shù)據(jù)中抽取感興趣的模式，理解用戶的瀏覽興趣行為。

2 基于粗糙近似的 Web事務(wù)聚類算法

2.1 用戶訪問序列相似度矩陣的建立

事務(wù)是用戶從開始瀏覽一個(gè)站點(diǎn)到結(jié)束瀏覽該站點(diǎn)過程中所執(zhí)行的所有操作序列的集合。設(shè)有 m 個(gè)用戶，用戶事務(wù)的集合為：T= ｛t1, t2, t3 ,…, tm｝。假設(shè) U 是用戶點(diǎn)擊流的集合，一用 戶事務(wù)可以表示成

為了挖掘訪問序列模式，在計(jì)算兩個(gè)事務(wù)相似度時(shí)應(yīng)考慮序列所包含的項(xiàng)和各項(xiàng)出現(xiàn)的順序。這里利用[5]中所提出的基于順序和內(nèi)容的 S3M 度量方法計(jì)算序列相似性。兩個(gè)序列的最長共同子序列的長度 LLCS 決定了序列的順序相似性。兩個(gè)序列的內(nèi)容相似性是兩個(gè)序列公有項(xiàng)的個(gè)數(shù)與兩個(gè)序列并操縱后項(xiàng)的個(gè)數(shù)之比。

定義 2 內(nèi)容相似度：

定義 3 用戶訪問序列相似度：

p+q=1 且 p，q>0,p 和 q 用于調(diào)整序列順序相似性和序列內(nèi)容相似性的權(quán)重。

定義4用戶事務(wù)相似度矩陣如下：

易知，此矩陣滿足自反性、對稱性[6]。

2.2 粗糙集模型

定義 6 給定一個(gè)非負(fù)域δ∈(0,1]和一個(gè)集合 X={x1, x2,…，xn},X ? U，則第一粗糙上近似為:

定義 7 設(shè) X={x1, x2,…，xn},X ? U，給定一個(gè)非負(fù)域σ∈(0,1)，xi約束相似性上近似為：

2.3 聚類算法

輸入：

Web 用戶事務(wù) T= ｛t1, t2, t3,…, tm｝；

閥值δ∈(0,1]；

相對相似性約束條件σ∈(0,1)；

權(quán)重值 p，q。

輸出：Web 用戶事務(wù)聚類 C

Begin

Step 1：計(jì)算用戶事務(wù)相似度矩 SIMm×m

Step 2：對于每個(gè)用戶 ti∈U， 利用得到每個(gè)用戶的第一個(gè)上近似

Step 3：假定 US=｛S1, S2, Si,…, Sm｝ , C =?

Step 4：對于所有的 Si∈US ，在給定的閾值σ條件下計(jì)算它們的下一個(gè)約束相似性上近似 Si’

If Si= Si’

C=C∪Si’

US=US{ Si}

Endif

Step 5：重復(fù) Step 5 直到 US=?

Step 6：Return C

3 實(shí)驗(yàn)結(jié)果

數(shù)據(jù)源來自 UCI網(wǎng)站測試數(shù)據(jù)集 msnbc.com 的 IIS 服務(wù)器登陸日志，經(jīng)數(shù)據(jù)預(yù)處理得到17個(gè)URL和9個(gè)訪問用戶，用戶事務(wù)的相似度矩陣如下：

計(jì)算每個(gè)用戶的第一個(gè)上近似時(shí)，閥值δ=0.2 得到每個(gè)用戶的 R(ti)如下：

計(jì)算每個(gè)用戶的二次相似上近似時(shí)使用定義 4取σ=1只有滿足定義 4的事務(wù)才會(huì)合并到二次相似上近似中，如下：

得到事務(wù)的二次相似上近似后，只有 t9 的一次相似上近似和二次相似上近似不同，再計(jì)算 t9 的三次相似上近似這時(shí)算法停止，聚類結(jié)果如圖1所示：

圖1 Web 事務(wù)聚類結(jié)果

4 結(jié)束語

已有的粗糙聚類算法大多沒有考慮用戶點(diǎn)擊流的順序，本文提出的聚類算法綜合考慮用戶訪問序列的順序和訪問內(nèi)容建立相似度，運(yùn)用基于相似度矩陣的粗糙上近似提取初始類，使用相對相似性的條件合并初始類，基于約束相似性的上近似形成后續(xù)類。這種方法有助于發(fā)現(xiàn)用戶的訪問興趣，幫助 Web 站點(diǎn)設(shè)計(jì)者更好地理解用戶的訪問模式， 以用于調(diào)整 Web 站點(diǎn)的結(jié)構(gòu)。

[1] 張 文 修 .粗 糙 集 理 論 與 方 法 [M].北 京 ： 科 學(xué) 出 版社,2001:124-125

[2] 涂承勝.Web 使用挖掘技術(shù)研究[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25(7):1177-1184.

[3] Yun C H, Chen M S. Using pattern-loin and purchase-combination for mining web transaction patterns in an electronic commerce environment [C].Taipei, Taiwan: Proc of the 24th annual Intern'l Computer Software and Application Conference (COMPSAC),2000:216-219.

[4] Pawlak. Rough Sets[J].International Journal of Computer and information Science,1982,11:314-356.

[5] P. Kumar, M.V. Rao, P.R. Krishna, R.S. Bapi, A. Laha. Intrusion detection system using sequence and set preserving metric[C]. Atlanta: Proceedings of IEEE International Conference on Intelligence and Security Informatics, 2005:498–504.

[6] M.H. Dunham, Data Mining: Introductory and Advanced Topics[R]. NJ: Prentice Hall, 2003.

[7] De S K, Krishna P R. Clustering Web Transactions Using Rough Approximation [J]. Fuzzy Sets and Systems, 2004, 148(1): 134-138.

[8] Slowinski R, Vanderpooten D.A generalized definition of rough approximation based on similarity [J]. IEEE Trans Knowledge Data Eng, 2000, 12(2):331-333

Web Transactions Clustering Algorithm on Rough Set

Qiu Bo
(Modern Educational Technology Center, Xuzhou Normal University, Xuzhou, 221116, China)

Web usage mining can mine useful information from web access log. The discovered knowledge or unexpected rules are likely to be imprecise or incomplete. Rough set is introduced into the web mining to cluster web transactions. The set as well as sequence similarity of users’ sessions is considered to form similarity matrix. Initial clusters are formed using a similarity upper approximation. Subsequent clusters are formed using the concept of constrained-similarity upper approximation wherein a condition of relative similarity is used as a merging criterion. Using this approach, users can effectively mine web log records to discover web page access patterns.

Web Mining; Rough Set; Similarity Upper Approximation; Constrained-similarity Upper Approximation; Transaction Clustering

TP301

A

1007-757X(2014)02-0056-03

2013.11.25)

邱波（1980—），女，漢族，江蘇宿遷人，江蘇師范大學(xué)現(xiàn)代教育技術(shù)中心，碩士，講師，研究方向：數(shù)據(jù)挖掘，粗糙集理論，徐州，221116