一种新的基于Web日志的数据聚类算法研究

摘要：针对当前FCM算法在处理Web日志数据聚类中存在对孤立点比较敏感，要求输入聚类原型参数的先验数据以及容易陷入局部极值等缺陷，在引入竞争凝聚算法机制的基础上，该文提出了一种新的Web日志数据聚类算法CAWFCM，该算法通过对隶属度加权来减小孤立点数据的影响，引入竞争机制策略来解决模糊 均值聚类算法不能自动确定聚类类别数的问题。仿真实验表明，CAWFCM算法对Web日志数据的挖掘效果良好，其性能优于FCM算法。

关键词：数据挖掘；聚类；FCM；Web挖掘

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)21-5159-04

Research of Data Clustering Algorithms Based on Web Log

ZHANG Xiao

(Chengdu Branch, Sichuan Telecom Industry Service Co., LTD, Chendu 611730, China)

Abstract: In the current FCM algorithm in dealing with Web log data clustering the existence of outlier comparison sensitive, asked to enter clustering prototype parameters and easy to get into a priori data defects such as local extremum in introducing competition condensing algorithm, the basis of the mechanism, this paper puts forward a new Web log data clustering algorithm, the proposed algorithm based on CAWFCM membership weighting to reduce the influence of outlier data, introduce a competitive mechanism strategies to solve fuzzy c-mean algorithm does not automatically determine the number of clustering category. Simulation experiments show that CAWFCM algorithms on the Web log data mining effect is good, and its performance than the FCM algorithm.

Key words: data mining; clustering; FCM; Web mining

作为丰富信息资源的提供者，Web已逐渐深入到人们学习、工作和生活的方方面面。随着Web结构的日益复杂，信息的日趋庞杂，用户要想在大多没有考虑其偏好和浏览兴趣的网站上获得有用信息变得越来越困难。Web服务器日志是一个结构化较好的记录集，保存了用户访问Web各页面的情况，利用Web日志挖掘技术可以发现用户访问网站的浏览模式及网站页面之间的关系，继而进行用户聚类和页面聚类。聚类是数据挖掘的重要分支之一，引入模糊理论的模糊聚类分析为现实数据提供了模糊处理能力，在许多领域被广泛应用,其中模糊 均值聚类算法是目前广泛使用的模糊聚类算法，但它也存在着一些缺点。针对当前FCM算法在处理Web日志数据聚类中存在的各种问题，本文提出了一种新的Web日志数据聚类算法CAWFCM。

1 相关研究

伴随着模糊集理论的发展和深化，用模糊的手段处理聚类分析问题成为该领域研究的主流。最早系统地表述和研究模糊聚类问题的是著名学者Ruspini[1],他率先定义了模糊划分的概念。利用这一概念人们提出了多种模糊聚类分析方法，比较典型的有:基于相似性关系和模糊关系的方法(Tamra[2],Backer[3])、基于模糊等价关系的传递闭包方法、基于模糊图论的最大树方法、以及基于数据集的凸分解、动态规划和难以辨识关系等方法。然而上述方法均不能适用于大数据量的情况，难以满足实时性要求较高的场合，因此在实际中应用并不广泛。

实际中受到普遍欢迎的是基于目标函数的模糊聚类方法，即把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。该方法设计简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现。因此随着计算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点。

2 基本概念

设待聚类的数据对象集合为X={x1,x2,…,xn}?奂Rs,定义相应的相异矩阵R?奂Rs,用Rjk=||cj-xk||2,1≤j，k≤n表示数据对象xj和xk之间的相异程度,它满足下式:

1）Rjk≥0,1≤j≤n,1≤k≤n；

2）Rjk= Rkj, 1≤j≤n,1≤k≤n；

3）Rjj=0, 1≤j≤n。

关系型数据的FCM算法要求数据对象xj和xk之间的相异度Rjk必须从两者之间的欧氏距离得出,即:

Rjk-djk 2=||xj-xk||2,j,k=1,…n(1)

只有满足上式,才能保证uik的取值非负,即0≤uik≤1。然而在某些情况下，相异矩阵R是非欧氏的，这一问题可通过某种转换来实现，即给相异矩阵R中的所有非对角线元素加上一个正数β，并用Rβ表示经过转换的矩阵，它的定义如下:

(2)

对于选择β,假设矩阵 满足0≤uik≤1，，但不是基于欧氏距离的，则存在一个正数β0，使得对于所有的β≥β0，Rβ都是欧氏的，而对于所有的β

3 CAWFCM算法研究

3.1 隶属度的修正

在通常的FCM算法中，数据对象对于每个特定类的隶属度，是根据这个对象到特定类中心的相对距离确定的。每个对象的隶属度表明了这个数据对象隶属于这个类的程度，同时在聚类中心的更新中，隶属度也显示了每个对象对新的聚类中心调整的贡献的程度。隶属度的值越大，它对聚类中心位置的影响也就越大，相反，隶属度的值越小，影响也就越小。然而，由于生成的隶属度是相对数量，它们很可能在实际的应用中是不合适的。因此使用这些隶属度计算得到的聚类中心很有可能不是期望的聚类位置。为了减少孤立点对聚类结果的影响，对数据对象的模糊隶属度增加一个加权值，来减少孤立点对聚类中心的影响，从而达到改进聚类分析结果的目的。

对隶属度uik给予一个加权值，将其修改为:

(3)

通过隶属度的修正，可以看到处于[0,1]区间内的隶属度在经过改进之后，比原来的值有了一定的减少，并且隶属度越小，相应的减少就越明显。当它应用于聚类中心公式后，可以明显看到那些隶属度小的数据对象对聚类中心的影响降低了，修改后的聚类中心为：

(4)

3.2 算法具体实现

算法步骤如下：

1) 初始化,令m=2，目标函数为:

(5)

其中*代表噪音类, 令迭代计数器t=0, 确定最大聚类类别数c值,η0值，τ值，λ值，初始化隶属度矩阵P(t), 类基数最小阈值nε, 迭代停止阈值ε。并令β=0,Rβ为原始相异度矩阵R=?WRjkn×n。P(t)满足下式:

, k=1,2,…,n(6)

0≤uik≤1, i=1,2…,c,k=1,2,…,n (7)

0≤u*k≤1，k=1,2,…,n(8)

计算聚类i的基数和噪音类的基数：

, i=1,2…,c(9)

(10)

2）更新距离,计算新的隶属度向量以及数据对象与聚类的距离:

, 1≤i≤c (11)

,1≤i≤c,1≤k≤n (12)

对于任何一个i和k,如果, 则计算:

(13)

, 1≤i≤c,1≤k≤n(14)

β=β+Δβ(15)

(16)

上式中的ek表示Rn中单位矩阵的第k列向量。

确定数据对象到噪音类的距离值:

(17)

,k≤1≤n(18)

3) 更新a(t+1)和隶属度矩阵:

η(t+1)= η0e-(t+1)/ ?子 (19)

(20)

对于k=1,2,…,n，定义下列集合:

Ik={1,2,…,c}-Ik

如果Ik为空集

(21)

(22)

如果uik(t)>1=>uik(t)=1 ,如果uik(t)uik(t)=0

(23)

如果u*k(t)>1=>u*k(t)=1,如果u*k(t)u*k(t)=0

如果Ik不为空集 (24)

4) 更新聚类数目,计算聚类的基数:

, i=1,2,…,c (25)

计算噪音类的基数:

(26)

如果ni(t)

5) 检查是否收敛,如果聚类类别数c不变,且||P(t)=P(t+1)||

3.3 聚类结果评价指标

对聚类结果好坏的评价可以采用以下两个经典的度量指标[7]:

1) 类内距离(intra-cluster distance)。

类内距离是同一聚类内所有两两用户会话之间距离的平均值，用下式表示:

(27)

其中dkl是聚类i中的用户会话k和用户会话l之间的距离,|ci|为聚类i中用户会话的总数。Dint ra越小，则聚类越紧密，说明聚类效果越好。

2) 类间距离(inter-cluster distance)。

类间距离是某个聚类中的用户会话与其它聚类中的用户会话之间的距离的平均值，用下式表示:

(28)

其中dkl是聚类i中的用户会话k和聚类j中的用户会话l之间的距离，|ci|为聚类i中用户会话的总数，|cj|为聚类j中用户会话的总数。Dint er越大，则聚类与聚类之间越松散，说明聚类效果越好。

综上所述，对于聚类结果来说，Dint ra越小越好，而Dint er越大越好。

4 实验结果与分析

为了比较CA-WFCM与FCM算法的运算性能,本文分别选取了100,300,500,1000,2000,5000,7000条经预处理后的Web日志用户访问会话进行聚类运行时间比较,分别记录下采用CA-WFCM和FCM算法时的CPU执行时间,结果如图1所示。

由图1可以看出,当日志数据量少于5000条以下时,CAWFCM算法的CPU执行时间曲线的上升趋势比较缓慢,性能优于传统的FCM算法。但大于5000条日志时,CAWFCM算法的执行时间上升较快,性能差于FCM算法,这是因为CAWFCM算法与FCM算法虽然两者在迭代过程中的更新步骤是相同的, CA-WFCM能够利用竞争凝聚机制自动确定最佳聚类类别数, 而不需要FCM算法那样需要有先验知识或采用自适应方法,但由于CA-WFCM算法计算用户访问会话相似度的时间复杂度为O（n2）高于FCM算法,说明CA-WFCM算法在执行大数据量Web日志数据挖掘时需要进一步的改进,这也是下一步研究的内容。

5 结束语

本文基于Web日志数据的特点对FCM算法进行了改进,使其能够直接进行关系型数据聚类。针对FCM算法c的缺点,采用了基于竞争凝聚算法的机制与FCM算法相结合的方法,通过给隶属度增加一个权值以减少孤立点对聚类中心的影响,提出了基于竞争凝聚的加权FCM算法――CAWFCM算法,最后对该算法进行了仿真实验，验证了算法的可行性和正确性。

参考文献：

[1] Ruspini E H.A new approach to clustering[J].Inf Cont,1969,15(1):22-32.

[2] Tamra S.Pattern classification based on fuzzy relations[J].IEEE Trans SMC,1971,1(1):217-242.

[3] Backer E,Jain A K.A clustering performance measure based on fuzzy set decomposition[J].IEEE Trans PAMI,1981,3(1):66-74.

[4] Cooley R,Mobasher B,Srivastava J.Data preparation for mining world wide web browsing patterns[J].Knowledge and Information Systems,1999,1(1):5-32.

[5] Qyanagi S,Kubota K,Nakase A.Application of Matrix Clustering to Web Log Analysis and Access Prediction[C].SanFrancisco,CA:WEB KDD’2001,2001.

[6] Smyth P.Breaking Out of the Black-Box:Research Challenges in Data Mining[Z].SIGKDD,2001.

[7] Nasraoui O,Krishnapuram R,Joshi A.Mining Web Access Logs Using a Relational Clustering Algorithm Based on a Robust Estimator[C].Toronto:Proceedings of the Eighth International World Wide Web Conference (poster),1999.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文