试述算法改善K—均值聚类算法在Web日志挖掘技术中运用

论文导读：
摘要：实现Web日志挖掘技术的方法有很多，例如：聚类、分类、关联规则、序列模式和路径分析技术等。针对K-均值算法的缺陷提出了改进方向，然后依据改进方向改进算法，并且通过实验比较原始算法和改进算法的性能，证明改进算法的优越性。
关键词：Web日志挖掘；聚类；K-均值算法
1 Web日志挖掘

1.1 Web日志挖掘简介

严格的说，Web日志挖掘是Web使用模式挖掘的一种，就是通过对Web日志记录的挖掘，发现用户访问Web页面的模式，从而进一步分析和研究Web日志记录中的规律，以期改进Web站点的性能和组织结构，提高用户查找信息的质量和效率，并通过统计和关联的分析找出特定用户与特定地域、特定时间、特定页面等要素之间的内在联系。

1.2 Web日志挖掘的过程

Web日志的挖掘过程一般包括数据预处理、模式识别和模式分析三个阶段。如下图所示：
（1）数据预处理
Web日志挖掘的第一个步骤就是搜集原始数据，由于Web日志数据的特殊性，而且为了保证数据分析的准确性和数据挖掘算法的有效性，在数据分析之前必须要对搜集到的原始数据进行预处理，即将原始的日志文件经过数据清理、用户识别、会话识别、路径补充和事务识别等几个步骤，转化成可供数据挖掘阶段使用的事务数据库，以此保证模式分析阶段使用的数据是规则的、准确的、干净的、简洁的和完整的源数据，从而提高数据挖掘的精度和性能。
（2）模式识别
模式识别阶段就是运用各种技术和算法从预处理后的数据中挖掘和发现用户使用的各种潜在的规律和模式的过程。这一阶段使用的技术和算法来自各个领域，如：数据挖掘领域、社会学和统计学等领域。但是，需要注意的是，针对Web数据的特殊性，不同领域的算法和技术如果要拿过来使用的话，必须进行相应的改善，才能更好的发挥算法的优越性。在Web日志挖掘的模式识别阶段，常采用的技术有统计、关联规则、序列模式、聚类和依赖关系等。
（3）模式分析
模式分析阶段是从所挖掘的大量规则或者模式中进行分析，找出用户感兴趣的模式。目前，模式分析阶段的工作主要借助合适的技术和工具来辅助分析人员的理解，所以开发各种分析技术和工具也是非常必要的。
目前，常用的模式分析技术有以下几种：
① 知识查询：对挖掘出的大量模式，需要一种类似关系数据库SQL的知识查询机制使用户可以很方便的查询到想要的模式，从而使解释和分析有针对性。
② 联机分析处理（OLAP）：把Web使用数据装入数据仓库，以便执行OLAP操作，以获得用于预测用途的模式和趋势。
③ 可视化技术（Visualization）：可视化技术在其它领域应用中己经取得巨大成功，因此人们很自然的选择它来理解Web用户的行为。

1.3 Web日志挖掘技术

（1）聚类算法
聚类是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。一般的，一个群体就是一个类。
（2）分类算法
分类就是对数据库中的每一类数据挖掘出关于该数据的描述和模型，而这些数据库中的类是事先建立起来的。在Web日志挖掘中，分类技术可以根据用户注册信息或共同的访问模式进行分类，得出访问某一服务器文件的用户特征。
（3）关联规则
关联规则通常用在事务数据库当中，每个事务由若干事务数据项组成。它定义了数据项中的所有关联和相互关系，即事务中一组数据项的出现可能标志着其它数据项的出现。在Web日志挖掘中，关联规则可以发现某个用户生成的服务器文件中不同引用之间的关系。
（4）序列模式技术
序列模式挖掘旨在从时间序列数据库中挖掘出用户行为模式。因为用户的一次访问会在Web服务器记录一段时间，所以序列模式分析技术可以确定一段时间内所有客户访问特定页面所共有的特征。在Web日志挖掘中，序列模式挖掘着重寻找的是用户页面访问序列随时间推移发生的变化，目的是挖掘出用户访问会话之间的变化规律。
（5）路径分析技术
路径分析技术是利用链接记录文件项来决定每个访问者的路径，并将路径按时间顺序排序。在设计Web站点的合理布局时，图的节点表示Web页面，有向边表示页面的超链接。其它各式各样的图也是建立在页面与页面之间的联系或者是一定数量的用户浏览页面顺序的基础上的。
2改进的算法和原始的K-均值算法的性能比较
由于聚类分析中的类不是事先给定的，而是根据数据的相似性和距离来划分，因此，衡量一个聚类算法的优越性，我们可以从整个簇的纯度、簇内相似度和簇间相异度几个方面去比较[50]。本次实验的数据来源为依据河南商业高等专科学校的Web日志文件建立的数据表。

2.1 纯度比较

衡量改进算法的优越性，我们可以使用常用的纯度（Purity） [51]来度量。设簇Ci的大小为ni，则该簇的纯度定义为：
其中ni’表示簇Ci 与第j类的交集的大小，整个簇类的纯度定义为：
其中k为聚类最终形成的簇的数目。
通过反复聚类实验得到改进算法和原始K-均值算法的纯度比较值，如下表所示：
通过比较发现，改进的算法在纯度和稳定性方面都要优于原来的K-均值聚类算法。

2.2 簇内相似度的比较

一个好的聚类方法应当产生高质量的聚源于：论文www.7ctime.com
类，即簇内的相似度要高。簇内相似度即是簇内任意数据项与簇内中心点的距离，该距离越小，证明簇内的数据项越紧密，算法的优越性越好。簇内相似度的计算公式采用马氏距离进行计算。通过反复聚类实验得到改进算法和原始K-均值算法的簇内相似度的比较，如下表所示：
通过比较发现，改进的算法在簇内相似度方面要优于原来的K-均值算法，即使用改进的聚类算法得到的簇内部比较紧密。

2.3 簇间相异度的比较

一个好的聚类方法除了要保证簇内具有较高的相似度以外，而且还要保证簇间具有较高的相异度。簇间的相异度在有些参考资料上也称为簇间相似度，即是任意数据项与其所在的簇以外的其它簇内中心点的距离，该距离越大，证明簇间差别越大，聚类效果越论文导读：
好。簇间相异度的计算公式同样采用马氏距离进行计算。通过反复聚类操作得到改进算法和原始K-均值算法的簇间相异度的比较，如下表所示：
通过比较发现，改进的算法在簇间相异度方面要优于原来的K-均值算法。
[参考文献]
谢丹夏.Web上的数据挖掘技术和工具设计.计算机工程与应用，2001：134
毛国君，段立娟，王实等.数据挖掘原理与算法.清华大学出版社，2005：323
[3] 王澜.教学网站中数据挖掘技术的研究和应用.大连交通大学硕士学位论文，2006：23
[4] 张娥，冯秋红，宣慧玉等.Web使用模式研究中的数据挖掘.计算机应用研究，2001：18
[5] 周涓，熊忠阳，张玉芳等.基于最大最小距离法的多中心聚类算法.计算机应用，2006：1425-1428
[6] 王黎明.田源等，基于K-均值聚类算法的Web日志挖掘技术. 郑州大学学位论文，2009：05
（作者单位：1，河南大学教育科学学院，河南 开封 475000，2，郑州科技学院，河南 郑州 450000）