基于粗糙集理论的Web事务聚类框架

### 基于粗糙集理论的Web事务聚类框架 #### 1. 引言 Web使用数据涵盖了来自Web服务器访问日志、代理服务器日志、浏览器日志、用户配置文件、注册文件、用户会话或事务、用户查询、书签文件夹、鼠标点击和滚动等，以及用户与Web交互产生的其他任何数据。Web挖掘技术旨在利用数据挖掘工具从Web数据仓库中提取知识，如内容、链接和使用信息等。其中，用户点击流（即使用数据）可用于捕捉用户的导航模式和识别用户的预期任务。一旦有效地刻画了用户的导航行为，将为进一步的Web应用带来益处，进而提高基于Web的组织和终端用户的Web服务质量。 在Web数据挖掘研究中，许多数据挖掘技术（如聚类）被广泛应用，以提高Web挖掘的可用性和可扩展性。Web上的访问事务可以用两个有限集表示：用户事务和超链接/URL。用户事务U是一个项目序列，由m个用户形成，集合A是用户点击的不同n个点击（超链接/URL）的集合，即U = {t1, t2, ..., tm} 和A = {hl1, hl2, ..., hln}，其中每个ti ∈T ⊆U是U的非空子集，并且考虑了用户在事务中点击的时间顺序。用户事务t ∈T用向量t = ⌊ut1, ut2, ..., utn⌋表示，若hli ∈t，则ut i = 1，否则ut i = 0。 一种著名的Web事务聚类方法是使用粗糙集理论。有研究提出了一种基于粗糙近似的Web事务聚类算法，该算法基于给定阈值下事务上近似的相似性。然而，该方法在合并具有相同上近似相似性的两个或多个聚类时需要进行多次迭代，并且没有解决给定阈值下存在多个事务的问题。为克服这些问题，本文提出了一种基于粗糙集理论的替代聚类技术。 #### 2. 粗糙集理论 信息系统是一个四元组S = (U, A, V, f)，其中： - U = {u1, u2, u3, ..., u|U|} 是一个非空有限对象集。 - A = {a1, a2, a3, ..., a|A|} 是一个非空有限属性集。 - V = ∪a∈AVa，Va是属性a的域（值集）。 - f : U × A −→V是一个信息函数，对于每个 (u, a) ∈U × A，f(u, a) ∈Va，称为信息（知识）函数。 粗糙集近似的起点是不可分辨关系，它由感兴趣对象的信息生成。如果信息系统中的两个对象具有相同的特征，则称它们是不可分辨（不可区分或相似）的。 **定义1**：两个元素x, y ∈U被称为B - 不可分辨（在S中由属性集B ⊆A不可分辨），当且仅当对于每个a ∈B，f(x, a) = f(y, a)。 显然，A的每个子集都会诱导出唯一的不可分辨关系。由属性集B诱导的不可分辨关系记为IND(B)，它是一个等价关系。由IND(B)诱导的U的划分记为U/B，划分U/B中包含x ∈U的等价类记为[x]B。集合的下近似和上近似的概念定义如下： **定义2**：X的B - 下近似记为B(X)，B - 上近似记为B(X)，分别定义为B(X) = {x ∈U|[x]B ⊆X} 和B(X) = {x ∈U|[x]B ∩ X ≠ φ}。 任何子集X ⊆U相对于B ⊆A的近似精度（粗糙度精度）αB(X) 由下式测量： αB(X) = |B(X)| / |B(X)| 其中|X|表示X的基数。对于空集φ，定义αB(φ) = 1。显然，0 ≤αB(X) ≤1。如果X是U的某些等价类的并集，则αB(X) = 1，此时集合X相对于B是精确的；如果X不是U的某些等价类的并集，则αB(X) < 1，此时集合X相对于B是粗糙的。这意味着任何子集X ⊆U的近似精度越高，其本身越精确（越不粗糙）。 #### 3. 相关工作 给定两个事务t和s，它们之间的相似度测量为sim(s,t) = |t ∩ s| / |t ∪ s|。显然，sim(t,s) ∈[0, 1]，当两个事务t和s完全相同时，sim(t,s) = 1；当两个事务t和s没有共同项时，sim(t,s) = 0。有研究使用在T上定义的二元关系R，对于任何阈值th ∈[0, 1]和任何两个用户事务t和s ∈T，二元关系R表示为tRs当且仅当sim(t, s) ≥th。这个关系R是一个容差关系，因为它是自反和对称的，但传递性不一定总是成立。 **定义3**：t的相似类记为R(t)，是与t相似的事务集合，即R(t) = {s ∈T : sRt}。 对于不同的阈值，可以得到不同的相似类。领域专家可以根据经验选择阈值以获得合适的相似类。显然，对于固定的阈值∈[0, 1]，给定相似类中的一个事务可能与另一个相似类中的对象相似。 **定义4**：设P ⊆T，对于固定的阈值∈[0, 1]，在T上定义二元容差关系R。P的下近似记为R(P)，上近似记为R(P)，分别定义为R(P) = {t ∈P : R(t) ⊆P} 和R(P) = ∪t∈P R(t)。 该研究提出了一种对用户导航点击进行聚类的技术，称为相似上近似，记为Si。可能与R(t