基于加权矩阵聚类的Web日志挖掘算法

摘 要：Web服务器日志中记录了用户的浏览模式，为了从中提取出具有相似访问模式的用户群，对其提供个性化服务，提出一种针对Web日志的分析方法。通过构建UserID-URL关联矩阵，引入加权关联矩阵，提出一种基于加权矩阵的聚类算法――多标记传播算法。实验表明，该算法在Web日志挖掘中进行用户聚类和页面聚类是高效可靠的。

关键词：数据挖掘；Web日志挖掘；加权矩阵聚类；多标记传播算法;用户聚类

Web Log Mining Algorithm Based on Weighted Matrix Cluster

HAO Na1，2 ，TIAN Baohui1，JIANG Jianguo1

(1.Xidian University,Xi′an,710071,China;2.Qinghai Architecture Vocational Techniqual College,Xining,810012,China

Abstract：Web server log files registered browsing patterns of users,in order to extract users with similar accessing patterns and provide personal service for them，a new method of analysis on Web log is proposed.A User-URL matrix is created and weighted matrix is introduced，additionally,a mutlimarker propagation algorithm based on weighted matrix cluster is proposed.The experiments show that this algorithm has high-performance and reliability to cluster users and pages in Web log mining.

eywords：data mining；Web log mining；weighted matrix cluster；mutlimarker propagation algorithm；users clusteringオ

1 引 言

随着因特网的迅速发展，Web在人们的日常生活和工作中的地位日益显著［1,2］。Web中包含页面的内容信息、超链接信息，以及Web页面的访问和使用信息，如何针对这些信息，应用数据挖掘技术挖掘出有用的信息，更好地为用户服务，已经成为目前国内外的一个新的研究热点［3］。在Internet中，对于特定的网站而言，其页面之间的拓扑结构是已知的。尽管不同的用户在不同时期可能会有不同的浏览模式，但长期趋势应该是稳定的。因此，挖掘特定网站一定时期内用户的访问信息，便可以发现该网站的相似用户群体以及相关页面信息，从而对相似用户群提供个性化服务。本文对Web站点的拓扑结构和用户浏览信息进行分析，以UserID为行、URL为列，构建UserID-URL关联矩阵，元素值为用户访问页面的次数。在此基础上，通过阈值参数的引入，将关联矩阵转化为加权关联矩阵，提出一种基于加权矩阵的聚类算法――多标记传播算法(multiMarker propagation algorithm。该算法利用矩阵的稀疏特性，可从1个稀疏矩阵中抽出1个稠密子矩阵，因此，对用户（页面）聚类的过程，也转化为从稀疏矩阵中抽取稠密子矩阵的过程。

2 加权矩阵聚类

矩阵聚类［4］（Matrix Cluster，MC）最初是为客户关系管理（Customer Relationship Management，CRM）提出的。图1所示的关联矩阵,[WTHX]M[WTBX]m×n中，行代表用户，列代表页面。矩阵元素值hi,j表示用户i访问页面j,的次数。以往文献常见做法是用0或者1来表示用户是否访问某个页面，直接对关联矩阵进行归一化处理得到元素值非0即1的矩阵，再运用各种算法进行聚类分析。

为了更好地刻画用户的特征向量，反映出用户的访问频度和兴趣所在，本文引入加权关联矩阵的概念。加权关联矩阵,[WTHX]A[WTBX]m×n由关联矩阵加权处理转化而来。通常这样的加权矩阵是个大而稀疏的矩阵。

由于用户和页面的顺序不是很重要，所以行和列可以任意交换。图2显示了从给定加权矩阵中抽取出的稠密矩阵。如图所示，抽取出的稠密矩阵包括用户B,D,F,G 及页面1,3,6，这个子矩阵可解释成如下这样：用户B,D,F,G在访问页面1,3,6时具有一个共同特征。同时页面1,3,6被用户B,D,F,G的访问也具有一个共同的特征。

下面给出支持度和置信度的概念：

支持度抽取出的子矩阵的面积，此处定义为：子矩阵的行×子矩阵的列；

置信度抽取出的子矩阵的密度，即：子矩阵中非0元素的个数/子矩阵的面积；

这样，加权矩阵聚类的问题就转化为从稀疏矩阵中找出面积大于指定支持度且密度大于指定置信度的所有子矩阵的问题。

3 多标记传播算法

当矩阵很大时，一般算法会反复交换行或列，进行大量的计算，本文提出的基于加权矩阵聚类的多标记传播算法能够通过应用矩阵的稀疏特性来减少执行时间。该算法使用标记传播，标记传播通常定义为一个计算模型，它描述一个作为结点的处理单元和一个作为链接边的结点间的关系。标记传播通过从与结点,N相连的活动结点传输一个标记的方式激活结点N。在多标记传播算法中，行(列代表结点。当一个矩阵元素非0时，相应的行和列被一个双向边连接。当一个结点收到一个标记时，它会把该标记累积起来形成标记总数，标记总数通常用于裁剪。,

如果某结点收到的标记总数小于指定的阈值，那么，该结点对应的行(列被裁剪，被裁剪掉的行(列不再参与后面的运算；需要说明的是，当执行行裁剪时，活动列只能激活那些与对应活动列标记相同的行。不过，由行发送标记时，只要对应列为非0元素均可被激活。标记会反复地在行(列之间传播，直到活动的行(列不再变化为止，即行(列裁剪结束，此时如果发现剩余的活动行和列，均大于用户指定的行和列的最小值(支持度，并且矩阵密度也大于用户指定的最小密度(置信度，则剩余的活动行(列对应的用户(页面即为用户(页面聚类，否则，说明没有满足要求的用户(页面聚类存在。

为了算法的需要，这里引入几个概念：

用户信度：用户点击所有页面的累计次数；

页面信度：页面被所有用户点击的累计次数；

最小标记数：剪切矩阵的条件。

多标记传播算法结构如下：

输入：加权关联矩阵,[WTHX]A[WTBX]m×n、,最小支持度、最小置信度、最小用户信度、最小页面信度、最小标记数。

输出：用户聚类和页面聚类。

初始化；

找出所有用户信度小于指定值的行；

找出所有页面信度小于指定值的列；

剪切掉所有用户信度低于给定阈值的行和所有页面信度低于给定阈值的列；