基于粗糙集的 Web事务聚类算法

邱 波

基于粗糙集的 Web事务聚类算法

邱 波

针对现有 Web 数据挖掘方法发现的知识和规则存在不精确或不完全的问题，将粗糙集引入到 Web 挖掘中，进行Web事务聚类。粗糙近似算法基于用户访问序列的顺序和内容建立用户事务相似度矩阵，运用基于相似度矩阵的粗糙上近似提取初始类，使用相对相似性的条件作为合并准则，基于约束相似性的上近似形成后续类。粗糙近似算法能够有效挖掘Web访问日志，聚类 Web 事务，发现用户访问 Web 页面的模式。

Web挖掘；粗糙集；相似上近似；约束相似性上近似；事务聚类

1 概述

聚类是按照事物间的相似性进行区分和分类的过程，是一种无监督的分类。聚类分为硬计算方法和软计算方法。在硬聚类方法中，根据相似度将对象划分到不同的聚类中，不同的聚类之间没有交集。在软聚类方法中，一个对象可以被分配到2个或者2个以上的聚类中。软聚类可能具有模糊或粗糙的边界域[1]。

用户事务聚类是一个通过 Web 网站相关信息的聚类得到具有相似访问兴趣的用户事务集合的整理和挖掘过程。用户事务聚类可用来准确预测用户浏览行为[2]， 理解和影响购买模式[3]并实现个性化用户访问服务等。Rough 理论[4]是由波兰华沙理工大学 Pawlak 教授于 20 世纪 80 年代提出的一种研究不完整、不确定的知识和数据的表示、学习、归纳的理论方法。对于有大量噪声和孤立点的 Web 数据来说，粗糙集理论正是处理隐藏在信息中的不确定性、含糊性的有力工具。它解决了一般的聚类算法发现知识和规则不够完整、不够准确的难题。本文将利用粗糙集理论对 Web 事务进行聚类，从用户浏览网站的数据中抽取感兴趣的模式，理解用户的浏览兴趣行为。

2 基于粗糙近似的 Web事务聚类算法

2.1 用户访问序列相似度矩阵的建立

事务是用户从开始浏览一个站点到结束浏览该站点过程中所执行的所有操作序列的集合。设有 m 个用户，用户事务的集合为：T= ｛t1, t2, t3 ,…, tm｝。假设 U 是用户点击流的集合，一用 户事务可以表示成

为了挖掘访问序列模式，在计算两个事务相似度时应考虑序列所包含的项和各项出现的顺序。这里利用[5]中所提出的基于顺序和内容的 S3M 度量方法计算序列相似性。两个序列的最长共同子序列的长度 LLCS 决定了序列的顺序相似性。两个序列的内容相似性是两个序列公有项的个数与两个序列并操纵后项的个数之比。

定义 2 内容相似度：

定义 3 用户访问序列相似度：

p+q=1 且 p，q>0,p 和 q 用于调整序列顺序相似性和序列内容相似性的权重。

定义4用户事务相似度矩阵如下：

易知，此矩阵满足自反性、对称性[6]。

2.2 粗糙集模型

定义 6 给定一个非负域δ∈(0,1]和一个集合 X={x1, x2,…，xn},X ⊆ U，则第一粗糙上近似为:

定义 7 设 X={x1, x2,…，xn},X ⊆ U，给定一个非负域σ∈(0,1)，xi约束相似性上近似为：

2.3 聚类算法

输入：

Web 用户事务 T= ｛t1, t2, t3,…, tm｝；

阀值δ∈(0,1]；

相对相似性约束条件σ∈(0,1)；

权重值 p，q。

输出：Web 用户事务聚类 C

Begin

Step 1：计算用户事务相似度矩 SIMm×m

Step 2：对于每个用户 ti∈U， 利用得到每个用户的第一个上近似

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

Step 4：对于所有的 Si∈US ，在给定的阈值σ条件下计算它们的下一个约束相似性上近似 Si’

If Si= Si’

C=C∪Si’

US=US{ Si}

Endif

Step 5：重复 Step 5 直到 US=∅

Step 6：Return C

3 实验结果

数据源来自 UCI网站测试数据集 msnbc.com 的 IIS 服务器登陆日志，经数据预处理得到17个URL和9个访问用户，用户事务的相似度矩阵如下：

计算每个用户的第一个上近似时，阀值δ=0.2 得到每个用户的 R(ti)如下：

计算每个用户的二次相似上近似时使用定义 4取σ=1只有满足定义 4的事务才会合并到二次相似上近似中，如下：

得到事务的二次相似上近似后，只有 t9 的一次相似上近似和二次相似上近似不同，再计算 t9 的三次相似上近似这时算法停止，聚类结果如图1所示：

图1 Web 事务聚类结果

4 结束语

已有的粗糙聚类算法大多没有考虑用户点击流的顺序，本文提出的聚类算法综合考虑用户访问序列的顺序和访问内容建立相似度，运用基于相似度矩阵的粗糙上近似提取初始类，使用相对相似性的条件合并初始类，基于约束相似性的上近似形成后续类。这种方法有助于发现用户的访问兴趣，帮助 Web 站点设计者更好地理解用户的访问模式， 以用于调整 Web 站点的结构。

[1] 张 文 修 .粗 糙 集 理 论 与 方 法 [M].北 京 ： 科 学 出 版社,2001:124-125

[2] 涂承胜.Web 使用挖掘技术研究[J].小型微型计算机系统,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—），女，汉族，江苏宿迁人，江苏师范大学现代教育技术中心，硕士，讲师，研究方向：数据挖掘，粗糙集理论，徐州，221116