动态数据库增量式挖掘算法及其应用的研究

摘要

传统的数据挖掘是从静态的数据库中发现知识。然而，数据仓库往往是动态变化的，新的数据积累可能导致以前采用的挖掘算法所发现的知识失效，因此发现的知识或模式也需要动态维护，及时更新。动态数据库与静态数据库挖掘的一个本质区别在于人们对于新增的事务可能更感兴趣。跟踪这种动态变化将使管理者在进行决策时更加受益。增量算法是在已有的挖掘结果的基础上，利用已经获得的知识对数据的增量部分进行挖掘，而不是对数据增量后的整体数据库进行重新挖掘，从而大大节省知识维护的开销。 Web日志中数据的规模往往很大，日志记录每时每刻都在不停地产生，用户的访问模式也随之而变化，而这种用户访问模式的变化趋势对于网站管理者而言是非常重要的。由日志记录构成的数据库就是典型的动态数据库，面对这种海量的动态数据，需要寻找高效的增量挖掘算法，极大地降低平均搜索时间和空间，是十分迫切而且必要的。本文的研究正是针对海量的Web访问信息所构成的数据库的动态特性而展开，研究如何利用Web访问信息的动态特性，寻找快速高效的增量挖掘算法，重点研究Web挖掘中聚类、分类和关联规则等若干关键问题的理论和方法。 本文对动态数据库增量挖掘技术的国内外研究状况作了系统、全面的归纳、总结和分析，并对典型的应用领域Web使用挖掘的研究现状进行了回顾。在此基础上，重点研究了模糊层次聚类算法、神经网络聚类分类模型、基于聚类划分的并行关联规则挖掘方法以及它们的增量更新算法，主要贡献和创新点如下： 1．利用模糊集合的理论，提出了基于模糊连接度的层次聚类算法FHC。首先采用基本的划分方法将大型数据集划分成子类，然后分析子类间的连接模糊度，构建子类模糊图。通过对模糊图进行入截图，得到模糊图的连通分支，从而得到聚类结果。FHC算法能对任意形状的簇进行有效聚类。并将该方法与其他算法进行了比较，无论在聚类质量还是运行时间上都具有优势，是一种快速高效的聚类方法。 2．对FHC算法进一步扩展，提出了该算法的增量挖掘方法IFHC和面向大型数据库的分区聚类算法PFHC。IFHC通过对受影响的邻域集合进行分析，高效地处理动态增量数据。PFHC针对密度不均匀区域或者大型数据集合对于内存容量不足的需求而提出的基于数据分区的模糊层次聚类算法，实验结果表明了这两种算法作为对FHC算法的扩充，具有很好的聚类效果。 3．结合自适应谐振理论和竞争型神经网络的特点，提出了一种新型的基于竞争型神经网络的SIN模型，该方法综合了自适应谐振理论和竞争型神经网络的特点，并在隐含层采用了Hebb学习规则进行神经元的侧学习，既能保证原有记忆不受影响，又能对新的信息加以记忆，同时又克服了ART网络对噪音敏感的缺点，具有在线学习的功能，能够实现动态数据的聚类。 4．传统的对传网络模型和学习算法中，隐含层神经元个数过多将产生死神经元，过少又使得竞争层不稳定，网络功能退化。针对这个缺陷，提出了一种自适应地确定隐含层神经元个数的ASCPN网络模型和学习算法，使得竞争层中每一个神经元节点都能充分发挥作用，使得网络能实现运用最少的神经元，达到要求的性能。并在竞争层采用软竞争机制，在一定程度上克服了初始权值选取敏感的问题，虽然竞争层的权向量计算比CPN复杂，但是泛化能力显著提高，与其他的基于软竞争的算法相比，收敛速度快，模拟精度高，能更好地逼近模拟函数，提高了网络的使用效率，使得网络的性能得到很大的提高。 5．提出了基于聚类划分的最大频繁项集挖掘算法PARUC和它的动态增量更新方法IPARUC算法。FP-tree是一种快速有效的关联规则挖掘方法，它采用建立FP-tree的方法将信息集中到压缩树上，不需要产生候选项集。该方法使用最不频繁的项作后缀，大大降低了搜索开销。但是，面对海量数据，构造基于内存的FP-tree是不现实的，而且很难实现增量数据的挖掘。我们采用快速聚类的方法对海量数据进行划分，使得划分后每部分数据具有一定程度的相似性，从而压缩局部FP-树。同时对FP-tree的构造算法进行改进，通过节点交换的方式压缩树的规模，以达到最佳压缩效果。并讨论了在增量情况下的最大频繁项集的动态更新方法，采用“剪枝-交换-接回”的方法解决新事务的插入问题。 6．提出了基于Web日志挖掘的增量式分析系统的系统框架，并实现了原型系统Weblog Analyzer。在该原型系统中，实现日志文件的预处理，最大频繁项集的挖掘、分类和聚类分析，并能对增量日志文件进行处理，同时将预处理后的增量数据进行最大频繁项的增量挖掘，增量的分类模型的建立和增量聚类分析，动态更新知识库，为用户推荐感兴趣的内容。 最后，本文对作者所做的工作进行了归纳总结，并提出了进一步研究的方向。

目录

文摘

英文文摘

论文说明：图表目录

第1章绪论

1.1研究背景和意义

1.1.1研究背景

1.1.2研究对象

1.2增量挖掘技术的研究发展现状

1.2.1关联规则的增量挖掘

1.2.2聚类的增量挖掘

1.2.3增量的分类算法

1.2.4序列模式的增量挖掘

1.3本文的主题

1.4本文的主要贡献

1.5本文的组织

1.6本章小结

第2章WEB日志挖掘综述

2.1数据源

2.1.1服务器端

2.1.2客户端

2.1.3代理端

2.2 Web日志文件预处理

2.2.1数据清理

2.2.2用户识别

2.2.3会话识别

2.2.4路径补充

2.2.5增量日志文件的处理

2.3 Web日志中的知识发现

2.4 Web使用挖掘的应用

2.4.1个性化传递Web页面的内容

2.4.2通过预取和缓冲技术改进用户导航

2.4.3改进Web站点的设计

2.4.4电子商务

2.5软件

2.6 Web日志的增量挖掘

2.7本章小结

第3章基于模糊连接度的层次聚类算法

3.1聚类的基本概念

3.1.1聚类算法中的数据结构

3.1.2相似性度量

3.1.3准则函数

3.2模糊聚类

3.2.1模糊集和模糊关系

3.2.2模糊图

3.3模糊层次聚类算法

3.3.1邻域

3.3.2基于模糊连接度的层次聚类算法

3.3.3计算复杂度

3.4增量式模糊层次聚类算法(IFHC)

3.4.1插入对象的情况

3.4.2删除对象的情况

3.5基于数据分区的模糊聚类算法(PFHC)

3.5.1数据分区

3.5.2边界处理

3.5.3 PFHC算法描述

3.6实验结果

3.6.1 FHC算法的性能测试与比较

3.6.2 IFHC算法的性能测试与比较

3.6.3 PFHC算法的性能测试与比较

3.7本章小结

第4章基于竞争的神经网络模型

4.1竞争型神经网络

4.2 SIN网络模型和算法实现

4.2.1网络结构

4.2.2学习算法

4.2.3 SIN网络的学习规则

4.2.4网络回想

4.2.5在线聚类

4.3 ASCPN模型

4.3.1学习过程

4.3.2 ASCPN网络的学习算法

4.3.3网络回想

4.3.4 ASCPN网络模型的特点

4.4有效性测试

4.4.1 SIN网络模型的实验

4.4.2 ASCPN网络模型的实验

4.5本章小结

第5章基于聚类划分的最大频繁项集的挖掘

5.1关联规则的挖掘

5.1.1关联规则

5.1.2 FP-growth算法

5.1.3存在的问题

5.2局部频繁项集和全局频繁项集

5.2.1基本概念

5.2.2算法思想

5.3基于聚类划分的关联规则挖掘算法

5.3.1改进的FP-tree构造

5.3.2算法描述

5.4全局频繁项目集的快速更新

5.4.1增量FP-growth挖掘算法

5.4.2算法描述

5.5基于聚类划分的关联规则增量更新算法

5.6实验结果

5.6.1无增量数据时的实验结果

5.6.2增量数据的实验结果

5.7本章小结

第6章基于WEB日志挖掘的动态分析系统

6.1 Weblog Analyzer的系统框架和功能

6.2 Weblog Analyzer原型系统的设计与实验

6.2.1事务数据库和模式数据库

6.2.2数据预处理

6.2.3最大频繁模式挖掘

6.2.4聚类分析

6.2.5分类

6.3本章小结

第7章总结与展望

7.1总结

7.2未来工作的展望

参考文献

攻读博士学位期间主要的研究成果

致谢