在数据仓库环境下的增量式聚类挖掘.doc

在数据仓库环境下的增量式聚类挖掘 摘要 数据仓库为数据挖掘任务的执行提供了很多支持，例如分类和聚类。典型的情况是，更新可以被收集，然后定期地以批处理的模式应用在数据仓库上，比如在夜里。因此，所有由数据挖掘算法从数据仓库中挖掘出来的模式也要及时更新上去。由于数据的规模巨大，因此利用数据仓库来执行这些更新是非常可取的。本文介绍了第一个增量式聚类算法，本算法是基于DBSCAN聚类算法的，DBSCAN算法适用于任何数据库，包含的数据可以是空间数据、空间数据库、WWW-log数据库等。由于DBSCAN算法的本质是基于密度的，因此插入或删除一个对象只会在该对象附近影响到当前簇。因此，高效的增量式插入和删除算法可以应用到现有的聚类中。根据簇的定义可以知道，增量算法和DBSCAN算法会得到相同的结果。针对基于空间数据库和WWW-log数据库的增量式DBSCAN算法提出了效率评估，论证了该算法的效率。即使是基于每天有大量更新的数据仓库，增量式DBSCAN算法的效率也比DBSCAN算法有了显著的提高。 简介 很多公司已经认识到了隐藏在他们大型数据库中的知识的战略重要性，因此，他们建立了数据仓库。数据仓库是一个数据集，这个数据集由不同的数据源中的数据组成，为了决策支持集合在了一个普通仓库中，并且被汇总信息（例如汇总的意见）扩展。讲到数据仓库环境，我们往往不会想到任何特殊的结构，但是数据仓库环境具有以下两个特点： 挖掘出来的信息有决策支持的作用； 该环境是动态变化的，比如，经常会更新。 基于这样的环境，能够实现借助具有合理分析能力的工具的手动分析及自动化或半自动化的数据挖掘。数据挖掘被定义成在一定的计算机效率范围内，根据数据得到一定数量的模式的数据分析和知识发现的过程。现在已经定义了很多数据挖掘的任务，例如聚类、分类、统计。例如有如下典型的数据挖掘结果： 消费者经常一起购买的商品形成簇（针对购物篮数据仓库的聚类分析） 疾病A和疾病B的症状区别（针对医疗数据仓库的分类） WWW入口模式的描述（针对网络提供者数据仓库的统计分析） 本文关心的挖掘任务是聚类，例如，将一个数据库中的对象按照特定的意义分成小类。近年来，出现了很多挖掘大型数据库的聚类算法。 通常情况下，对于在可操作的数据库中执行的插入和删除操作，数据仓库不会得到立刻更新。更新可以被收集，然后定期（比如每天夜里）地以批处理的模式应用在数据仓库上。因此，所有由数据挖掘算法从数据仓库中挖掘出来的模式也要及时更新上去。这些更新必须被高效的完成使得第二天用户在使用数据仓库时，数据仓库是可用的状态。由于数据库的规模很大，所以以批处理的方式完成这些更新是必要的。只要考虑在白天插入或删除的旧的簇或元素，而不是应用聚类算法更新这种巨大的数据库。 维护推导出来的信息，例如观点或者汇总表，一直都是一个积极研究的领域。但是，在动态变化的数据库环境下，增量式的更新挖掘出来的模式这个问题知识最近才开始得到更多的研究。《一个增量式的技术——对在大型数据库中已经挖掘出来的关联规则的维护》及《在增量式的数据库中发现频繁项集的高效算法》这两篇文章，针对从数据库中挖掘出一套关联规则这个问题提出了高效的算法。《在数据仓库的环境下为数据挖掘所做的增量式概括》一文，介绍了在数据仓库环境下的增量式归纳的通用算法。 本文介绍了第一个增量式聚类算法。这个算法以DBSCAN（基于密度的）为基础。DBSCAN是一种高效的基于数据仓库的在度量数据库（数据库有计算一对对象的距离的函数）下的聚类算法。由于DBSCAN算法的本质是基于密度的，因此插入或删除一个对象只会在该对象附近影响到当前簇。本文论证了在空间数据库、WWW入口及log数据库下的高效率的增量式聚类。 本文的剩余部分按照如下方式组织。第二部分讨论了与聚类算法相关的工作。第三部分简单的介绍了DBSCAN算法。第四部分介绍了基于数据库中插入和删除数据的增量式更新聚类算法。第五部分介绍了广泛的性能评价。第六部分得出了总结性的结论并且说明了未来的研究方向。 相关工作 在数据库的改变后引起的增量式更新挖掘出来的模式这个问题到最近才开始得到一些关注。《快速挖掘关联规则算法》一文介绍了挖掘关联规则算法的步骤。一个关联规则是一个形如“I1 = I2”的规则，这里I1和I2是一个项目集的不同子集。对于一个给定的交易记录数据库DB（即数据库DB中的每个记录包含一组项目，记录了一些客户所买的东西），所有的关联规则必须大于最小支持度和最小置信度。大于最小支持度的I的子集叫做频繁项集。《在增量式数据库中发现频繁项集的高效算法》一文介绍了两种在动态数据库中挖掘关联规则的典型方法。例如，在一个医疗数据库中，医生可能会探索治疗方案和恢复效果之间的关联规则。数据库可以在任何给定的时间里更新，医疗人员对得到当前的关联规则比