关联规则算法及其在Web日志挖掘中的应用研究

论文摘要

随着Internet的迅速发展和广泛应用,各种数字化信息每天以极高的速度增长,网络上积累了海量的数据。面对如此巨大的信息量,如何发现自己所需要的信息,成了困扰网络用户的一大难题。Web数据挖掘是数据挖掘技术在Web环境下的应用,是从大量的Web文档集合和用户浏览网站的数据中发现蕴涵的、未知的、有潜在应用价值的、非平凡模式的过程。Web挖掘分为Web内容挖掘、Web结构挖掘和Web使用挖掘。Web使用挖掘可以从用户浏览网站的数据中抽取感兴趣的模式,理解用户的浏览行为,以便进一步改善网站结构,为用户提供个性化服务。关联规则是数据库中存在的一种十分有用的知识模式,目的是发现大量数据中项集之间有趣的关联或相关联系,其挖掘算法已得到较为广泛的重视和研究,并取得了较大的进展。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。本文在研究数据挖掘理论的基础上,详细研究了经典关联规则挖掘算法Apriori算法。该算法在产生频繁项集的时候需要产生大量的候选项集,多次扫描数据库,时空复杂度过高。针对该算法的局限性,本文从两个方面对算法进行改进:（1）减少事务数据库的规模;（2）减少候选集是否频繁的判断次数。提出了三种改进算法:改进算法1在生成k-频繁集之前删除事务数据库中长度小于k的事务数据,降低了事务数据库的规模,减少了扫描数据库的时间;改进算法2在判断候选k-项集是否频繁的时候用SQL语句中的count函数用and运算直接判断该候选k-项集是否频繁,以减少对数据库的扫描次数;改进算法3结合了以上两种方法,提出了在减少数据库规模方面采用删除长度小于k的事务数据,在减少对数据库的扫描方面采用SQL语句的count函数来统计候选k-项集的频度,从而进一步提高算法效率。最后本文用三种改进算法在不同规模的事务数据下进行了挖掘测试,并对测试结果进行了比较。采用效率较高的改进算法3设计了一个虚拟主机网站日志挖掘程序。针对中国发动机网所采用的虚拟主机没有日志记录功能的情况,设计了一个日志记录模块嵌套于网页之中。将记录下来的日志数据用挖掘程序进行了关联规则挖掘,根据挖掘结果分析网站页面之间的关联性,得到了用户的访问习惯,为完善网站功能和改进网站结构提供了决策支持。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 前言
• 1.2 关联规则的研究现状
• 1.3 本文研究内容、数据来源及使用工具
• 1.4 本文的组织结构
• 2 关联规则概述
• 2.1 关联规则的基本概念
• 2.2 挖掘关联规则的算法
• 2.3 Apriori算法
• 2.3.1 算法描述
• 2.3.2 算法示例
• 2.3.3 Apriori算法的不足
• 2.4 本章小结
• 3 Apriori算法的改进
• 3.1 引言
• 3.2 减少事务数据库的规模
• 3.2.1 算法改进思想
• 3.2.2 算法描述
• 3.2.3 算法评价
• 3.3 减少对事务数据库的扫描次数
• 3.3.1 算法改进思想
• 3.3.2 算法描述
• 3.3.3 算法评价
• 3.4 结合减少数据库的规模和对事务数据库的扫描次数
• 3.4.1 算法改进思想
• 3.4.2 算法描述
• 3.4.3 算法评价
• 3.5 本章小结
• 4 关联规则在虚拟主机网站日志挖掘中的应用
• 4.1 日志挖掘概述
• 4.1.1 数据挖掘的基本概念
• 4.1.2 Web挖掘
• 4.1.3 Web日志挖掘
• 4.1.3.1 日志挖掘的步骤
• 4.1.3.2 数据预处理
• 4.1.3.3 模式识别算法
• 4.1.3.4 模式分析
• 4.2 虚拟主机
• 4.3 虚拟主机日志挖掘
• 4.3.1 系统概述
• 4.3.2 数据预处理
• 4.3.3 Apriori改进算法实证
• 4.3.4 挖掘结果分析
• 4.4 本章小结
• 5 总结与展望
• 5.1 本文总结
• 5.2 未来工作展望
• 参考文献
• 作者在攻读硕士学位期间发表的论文目录、科研情况
• 致谢