4 基于模糊相似矩阵的Web日志的动态聚类
4.1.3基于密度的聚类算法
基于密度的聚类方法的主要思想是只要一个区域中的点的密度( 对象或数据点的数目) 大过某个阈值，就把它加到与之相近的聚类中去。该方法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。其主要算法为DBSCAN 算法、OPTICS算法和DENCUE算法。
(1)、DBSCAN 算法：DBSCAN 算法的基本思想就是检查一个对象的ε领域的密度是否足够高，即一定距离ε内数据点的个数是否超过Minpts 来确定是否建立一个以该对象为核心对象的新簇，再合并密度可达簇，它可以在带有“噪声”的空间数据库中发现任意形状的聚类。在算法复杂度上，若采用空间索引R 3 - 树，其时间复杂度为O(nlogn) ，否则仍为O(n2) 。
（2）、OPTICS 法：OPTICS 法是为了解决DBSCAN 算法中参数ε和Minpts 难以确定而提出来的。它不显式地产生一个数据集合簇，而是为自动和交互的聚类分析计算一个聚类分析方法，因此OPTICS 法产生的是一个基于密度的簇的次序集合，它的时间复杂度与DBSCAN 相同。
4.1.4基于网格的聚类算法
基于网格的方法把数据空间量划分成为有限个单元（cell）的网络结构。所有的聚类都是以单个的单元为对象的。网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定。其主要算法有：
(1)、统计信息网格( STING) 算法：STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。对不同级别的分辨率，存在不同级别的矩阵单元，这些单元形成了一个层次结构，高层的每个单元被划分为多个低一层的单元。高层单元的统计信息可以由计算低层单元获得，而统计信息的查询则采用自顶向下的基于网格的方法，其聚类时间复杂度为O(n)。
(2)、CLIQUE 算法：CLIQUE 算法利用自顶向上方法求出各个子空间的聚类单元。 CLIQUE 算法主要用于找出高维数据空间中存在的低维聚类，该方法最主要的优点是能发现数据子空间中的簇，另外，对数据输入顺序不敏感，对数据高维有良好的伸缩性，但需要用户输入数据聚类空间等间隔距离和密度阈值参数。
4.1.5基于模型的聚类算法
基于模型的聚类方法是给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。基于模型的方法主要包括统计学类方法和神经网络类方法。
31
工程硕士学位论文
（1）、COBWEB 算法：COBWEB 法是一个通用且简单的基于统计的聚集方法，它用分类树的形式来表现层次聚集，并用一种启发式的评估衡量标准来引导树的建立。
（2）、竞争学习：竞争学习的方法采用了若干个单元的层次(神经元) ，以一种“胜者全取”的方式对系统当前处理的对象进行竞争。这种方法要输入两个参数：结果簇的数目和每个簇中单元的数目。
4.2 模糊聚类 (Fuzzy Clustering)
在现实中，分类往往伴随着模糊性，在很多场合，一个事务是否形成一个类群，一个事务是否隶属于某个子类，都不是很分明的，因此用模糊集合的理论和方法来描述和处理聚类的问题更为方便。模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象在分组中的隶属用隶属函数来确定，也就是说，对象在各分组中的隶属度为连续区间[0, 1]之间的某个值，以不同程度隶属于多个簇，而非确定性聚类中的0或1的二值逻辑。
动态聚类的基本思想是：先将所研究的n个样品各自为一类，计算它们之间的相似度或距离，选择最相似的或距离最小的两类归为新的一类，每次归类就减少一个类，直到所有样品都划到一个类为止。
4.2.1相关概念
定义1：Web模糊矩阵 若U={u1,u2,…,un}为聚类的Web对象（用户或页面）集合，设i=1,2,…,n,j=1,2,…,m,都有rij∈[0,1],则称R=（rij）nxm为Web模糊矩阵。
定义2：Web模糊相似矩阵 R为n阶Web模糊矩阵，I为单位矩阵，若R满足 若U={u1,u2,…,un}为聚类的Web对象（用户或页面）集合，设i=1,2,…,n,j=1,2,…,m,都有rij∈[0,1],则称R=（rij）nxm为Web模糊矩阵。
定义3：矩阵A=[aij]mxn称为一个Fuzzy矩阵，如果对任意i≤m及j≤n，都有aij∈[0,1]，我们约定A表示m行n列的模糊矩阵的集合。
定义4：设R是论域U上的一个模糊关系，如果R满足： 自反性 R(u,v）=1； 对称性 R(u,v）=R(v,u）；
则称R是U上的一个模糊相似关系，这里R(v,u）表示U的元素u与v的相关度。
定义5：包含模糊矩阵R的最小的模糊传递矩阵叫做R的传递闭包。记作：t（R）
定义6：模糊等价矩阵，我们把满足自反性、对称性以及传递性R2≤R的模糊矩阵称为模糊等价矩阵[38-39]。
32
4 基于模糊相似矩阵的Web日志的动态聚类
4.2.2相似度的度量
我们用[ 0,1]中的rij来表示X中的元素xi与xj的相似度的程度，为确定相似系数rij，可以用以下方法来进行[40]。
1、夹角余弦[1]
mrij =
?xk?1m2ikk?1ikxjkm （1）
jk?x?xk?12、数量积法 1, i=j rij =
1mxikxjk,i?j （2） ?Mk?1M= max(?xikxjk) k?1i?j3、绝对值减数法
rij = 1-c?|xik?xjk| （3）
k?1mm4、算术平均最小法
2?xik?xjkmrij =
?(xk?1mk?1m （4）
ik?xjk)5、最大最小法
rij =
?(xk?1mk?1ik?xjk) （5）
ik?(x?xjk)4.2.3 Web模糊聚类
在访问信息挖掘中, 模糊聚类的应用主要体现在根据数据预处理后的用户会话信息对用户、页等对象进行分类。
1、 客户群体的模糊聚类算法
在一定时间段内, 根据访问信息挖掘的数据预处理阶段获得的用户会话, 得
33
工程硕士学位论文
到各用户共同访问的页面数等信息, 然后使用模糊聚类方法对用户聚类。
用C表示客户集合, C={C1,C2,…,Ci,… Cm}；用U表示某一站点URL的集合,U={U1,U2,…,Uj… Un}，客户Ci的浏览子图Εci可用站点URL 表示, 即：
Εci={(Uj,fEc(Uj) ︱Uj∈U }
i其中, fEic(Uj)→[0,1]是客户Ci和URL(Uj)之间的关联度函数：
fEc(Uj)=
ihits(Uj)?mi?1hits(Ui) （6）
式中的n为n为URL的数量, hits(Uj )是客户Ci访问URL（Uj）的次数。这样, 就可以根据(5) 式和(7) 式建立模糊相似矩阵, 根据〔6〕式构造相似类, 合并相似类中的公共元素得到等价类。
2、 Web页面的模糊聚类算法
定义与客户群体聚类算法相同, 客户的访问情况可用URL（Uj）表示，即 （Uj）之间的Suj={(Cj,fS(Ci) ︱Ci∈C },其中,fS(Ci)→[0,1]是客户Ci和URL
ujuj关联度：
fSu(Ci)=
jhits(Ci)?mj?1hits(Cj) （7）
式中m为客户的数量, hits (Ci)是客户Ci访问URL（Uj）的次数[41-42]。
4.2.4 Web模糊聚类过程模型
Web模糊聚类的过程就是将Web的访问日志数据集经数据预处理后得到数据矩阵，通过式(6)、（7）将数据矩阵标准转化为适合 [ 0,1] 的Web模糊矩阵，再使用模糊聚类方法进行聚类。在模糊聚类方法中计算被分类对象间相似程度的统计量的方法有很多，常用的有夹角余弦方法、数量积法、绝对值减数法、算术平均最小方法以及最大最小方法。本文在计算被分类对象间相似程度时使用最大最小方法式（5）建立Web模糊相似矩阵，将Web模糊相似矩阵通过循环自乘转化为模糊等价关系，在模糊等价关系的基础上进行模糊聚类分析，最后输出聚类结果。
Web模糊聚类过程模型如图4-1：
34
4 基于模糊相似矩阵的Web日志的动态聚类
Web访问日志 数据清理 Web数 据矩阵 数据标准化 Web模 糊矩阵 标定 Web模糊相似矩阵 聚类过程 聚类结果 图4-1 Web模糊聚类过程模型
Figure 4-1 Web fuzzy clustering process model
4.3 利用最大-最小相似性度量的实例 (Real Examples Using the Maximum – Minimization of Fuzzy Similarity Measure)
我们取某网站的一日内的访问日志，原始日志是248050条，经数据清理后10933条，取其中的部分数据，假设Web站点的页面集合是P={p1,p2,p3,p4,p5,p6,p7,p8},经数据预处理后Web用户的集合为U={u1，u2，u3，u4，u5，u6，u7，u8},网站拓扑结构如图4-2，Web用户访问Web页面的次数如下：
U1:P1(15)-P2(10)-P5(3)-P3(11) U2:P1(10)-P3(5) U3:P1(8)-P3(5)-P6(4)
U4:P1(20)-P3(17)-P6(11)-P8(5) U5:P1(17)-P3(10)-P7(3) U6:P1(25)-P4(20) U7:P1(12)-P2(11)-P3(10) U8:P3(25)-P6(13)-P7(10)
P8 P5 P6 P7 P2 P3 P4 P1 图4-2 网站拓扑结构图
Figure 4-2 Site topology structure map
根据上面提供的数据构造数据矩阵，
35