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

在数据仓库环境下的增量式聚类挖掘摘要 数据仓库为数据挖掘任务的执行提供了很多支持，例如分类和聚类。典型的情况是，更新可以被收集，然后定期地以批处理的模式应用在数据仓库上，比如在夜里。因此，所有由数据挖掘算法从数据仓库中挖掘出来的模式也要及时更新上去。由于数据的规模巨大，因此利用数据仓库来执行这些更新是非常可取的。本文介绍了第一个增量式聚类算法，本算法是基于DBSCAN聚类算法的，DBSCAN算法适用于任何数据库，包含的数据可以是空间数据、空间数据库、WWW-log数据库等。由于DBSCAN算法的本质是基于密度的，因此插入或删除一个对象只会在该对象附近影响到当前簇。因此，高效的增量式插入和删除算法可以应用到现有的聚类中。根据簇的定义可以知道，增量算法和DBSCAN算法会得到相同的结果。针对基于空间数据库和WWW-log数据库的增量式DBSCAN算法提出了效率评估，论证了该算法的效率。即使是基于每天有大量更新的数据仓库，增量式DBSCAN算法的效率也比DBSCAN算法有了显著的提高。一、 简介很多公司已经认识到了隐藏在他们大型数据库中的知识的战略重要性，因此，他们建立了数据仓库。数据仓库是一个数据集，这个数据集由不同的数据源中的数据组成，为了决策支持集合在了一个普通仓库中，并且被汇总信息（例如汇总的意见）扩展。讲到数据仓库环境，我们往往不会想到任何特殊的结构，但是数据仓库环境具有以下两个特点：1） 挖掘出来的信息有决策支持的作用；2） 该环境是动态变化的，比如，经常会更新。基于这样的环境，能够实现借助具有合理分析能力的工具的手动分析及自动化或半自动化的数据挖掘。数据挖掘被定义成在一定的计算机效率范围内，根据数据得到一定数量的模式的数据分析和知识发现的过程。现在已经定义了很多数据挖掘的任务，例如聚类、分类、统计。例如有如下典型的数据挖掘结果：1） 消费者经常一起购买的商品形成簇（针对购物篮数据仓库的聚类分析）2） 疾病A和疾病B的症状区别（针对医疗数据仓库的分类）3） WWW入口模式的描述（针对网络提供者数据仓库的统计分析）本文关心的挖掘任务是聚类，例如，将一个数据库中的对象按照特定的意义分成小类。近年来，出现了很多挖掘大型数据库的聚类算法。通常情况下，对于在可操作的数据库中执行的插入和删除操作，数据仓库不会得到立刻更新。更新可以被收集，然后定期（比如每天夜里）地以批处理的模式应用在数据仓库上。因此，所有由数据挖掘算法从数据仓库中挖掘出来的模式也要及时更新上去。这些更新必须被高效的完成使得第二天用户在使用数据仓库时，数据仓库是可用的状态。由于数据库的规模很大，所以以批处理的方式完成这些更新是必要的。只要考虑在白天插入或删除的旧的簇或元素，而不是应用聚类算法更新这种巨大的数据库。维护推导出来的信息，例如观点或者汇总表，一直都是一个积极研究的领域。但是，在动态变化的数据库环境下，增量式的更新挖掘出来的模式这个问题知识最近才开始得到更多的研究。一个增量式的技术对在大型数据库中已经挖掘出来的关联规则的维护及在增量式的数据库中发现频繁项集的高效算法这两篇文章，针对从数据库中挖掘出一套关联规则这个问题提出了高效的算法。在数据仓库的环境下为数据挖掘所做的增量式概括一文，介绍了在数据仓库环境下的增量式归纳的通用算法。本文介绍了第一个增量式聚类算法。这个算法以DBSCAN（基于密度的）为基础。DBSCAN是一种高效的基于数据仓库的在度量数据库（数据库有计算一对对象的距离的函数）下的聚类算法。由于DBSCAN算法的本质是基于密度的，因此插入或删除一个对象只会在该对象附近影响到当前簇。本文论证了在空间数据库、WWW入口及log数据库下的高效率的增量式聚类。本文的剩余部分按照如下方式组织。第二部分讨论了与聚类算法相关的工作。第三部分简单的介绍了DBSCAN算法。第四部分介绍了基于数据库中插入和删除数据的增量式更新聚类算法。第五部分介绍了广泛的性能评价。第六部分得出了总结性的结论并且说明了未来的研究方向。二、 相关工作 在数据库的改变后引起的增量式更新挖掘出来的模式这个问题到最近才开始得到一些关注。快速挖掘关联规则算法一文介绍了挖掘关联规则算法的步骤。一个关联规则是一个形如“I1 = I2”的规则，这里I1和I2是一个项目集的不同子集。对于一个给定的交易记录数据库DB（即数据库DB中的每个记录包含一组项目，记录了一些客户所买的东西），所有的关联规则必须大于最小支持度和最小置信度。大于最小支持度的I的子集叫做频繁项集。在增量式数据库中发现频繁项集的高效算法一文介绍了两种在动态数据库中挖掘关联规则的典型方法。例如，在一个医疗数据库中，医生可能会探索治疗方案和恢复效果之间的关联规则。数据库可以在任何给定的时间里更新，医疗人员对得到当前的关联规则比较感兴趣。例如，在一个新闻文章的数据库里，相关主题的文章中同时出现的模式可能会被关注。经济分析师每天会收到大量的文章，他会在当前所有的文章中挖掘相应的关联规则。一个增量式的技术对在大型数据库中已经挖掘出来的关联规则的维护一文提出了应用关联规则的非增量式挖掘算法来挖掘新插入到数据库中的对象，即针对数据库中增加的数据，然后将原数据库和新增值产生的频繁集结合起来。在增量式数据库中发现频繁项集的高效算法一文中提到的增量式算法是基于属性集和边界集的信息。由于追踪这些频繁项集的空间开销很小，增量式算法要比非增量式算法快几个数量级。例如，概括总结是另外一个重要的数据挖掘方法。一种关系的泛化是这样一个过程，由一个更通用的属性值来代替现在的属性值，一个属性一个属性的代替，直到关系的元组的数量小于指定的阈值。这些更通用的属性值是取自概念层次，可典型的用于数据仓库中大多数的属性值。在数据仓库的环境下为数据挖掘所做的增量式概括一文提出的以增量属性为导向的泛化的算法具有这样的矛盾：较高的效率和最低限度的过度泛化。增量式插入和删除算法是基于在中级泛化水平的关系的物化，例如，锚的关系。实验结果表明，增量式泛化可以以低程度的过度泛化高效的执行。本文着重探讨了数据挖掘的聚类方法，在下文中，我们从数据挖掘的角度回顾了聚类算法。聚类算法将有n个对象的数据库分成K个类，这里的K是输入的参数。对于K均值算法，每一个簇由该簇的重心代表，对于K中心点算法，每一个簇由该簇中靠近中心位置的对象代表，每个对象被指定到和它距离最近的代表值所在的簇。典型情况是，聚类算法最开始先对数据库中的数据进行聚类，然后利用迭代控制策略来优化聚类的精度，例如，一个对象和其所在簇的代表值所在的距离的精度。高效的空间数据挖掘聚类方法讨论了在空间数据库中进行的聚类算法，介绍了一个叫做CLARANS（基于随机搜索的大型应用程序聚类）的算法，该算法比前面讨论的聚类算法效率高。分层算法会对数据库进行层次性分解。分层聚类分解是一个不断分解的过程，一棵树将数据库迭代分解成小子集直到每个子集只包含一个元素。在这样的一个层次中，树的每一层代表数据库的一个簇。基本的层次聚类方法如下。开始，每个对象被划分到一个特定的簇。对于每一对簇，计算它们的相似度或者距离。例如，距离可能是两个簇中所有两两对象之间距离的最小值。在线聚类一文论述了距离的另外一种定义，结果表明，一般情况下，从聚类精度来看没有一种方法优于其他方法。在每一步中，距离最小的簇要合并在一起，直到所有的对象都包含在了一个簇中。在数据库很大的时候，以上算法中，没有一个算法是高效的。因此，提出了一些实现高效聚类算法的关键技术。大型空间数据库中的知识发现技术高效的类别识别关键技术一文提出了一种基于R * -tree的关键技术，创建一个由来自每一个R * -tree数据页组成的样本数据库，并且只把这种聚类算法应用到这个样本上。BIRCH在超大数据库下的高效聚类方法一文提出了一个特殊的数据结构来压缩子簇点的信息。一个簇的特点（CF）由三部分组成，包含点的数量、线性总和及簇中所有点的平方和。聚类特点被组织在一个平衡树上。例如，CF-Tree,BIRCH(利用层次的思想平衡迭代减少和聚类)是一个基于多相聚类的CF-Tree。首先，扫描数据库，建立一个初始的内存CF-Tree。在可选的第二阶段中，这个CF-Tree可以被进一步减小，直到叶子的数量达到了足够的数量。在第三阶段，可以用任意的一种聚类算法对存储在该CF-tree的叶子节点上的值进行聚类。需要注意的是，CF-tree是一个增量式的结构，而BIRCH不是增量式的。最近，一种新型的单次扫描聚类算法公开了。单次扫描聚类算法的基本思想是，将数据库中的相邻数据组合起来，根据当前簇的条件放到簇中，从而对数据库只执行一次扫描操作。如果检索一个对象的相邻数据是支持DBMS的，那么单次扫描聚类算法的效率是非常高的。簇的条件不同要应用不同的簇的定义和聚类方法。例如，DBSCAN（基于密度的有噪声应用数据的空间聚类）依赖一种基于密度的簇的概念。由于以下原因，我们以DBSCAN作为增量式聚类的基础。首先，DBSCAN是基于大型数据库的高效算法之一。第二，DBSCAN可以应用于任何包含度量空间（假设只有一个计算距离的功能）数据的数据库，而BIRCH只能应用于空间数据库（欧式空间中的向量空间）。三、 DBSCAN算法 基于密度的聚类算法的核心思想是，对于簇中的每一个对象，以该对象为中心，一个给定的量为半径（Eps）的区域中应该至少包含最小数目的对象。即，和一个对象相邻的数据的数目要达到一个阈值（MinPts）。我们会对DBSCAN做一个简单的介绍，包括其定义，是增量式聚类所需要的。DBSCAN的详细介绍可以参考在包含噪声的空间数据库中实现基于密度的聚类算法一文。定义1：（直接可达密度）对象p是对象q直接密度可达的，Eps和MinPts在对象集D中，需要满足下面的条件： 1）p NEps(q)（NEps(q)是D的包含q的以Eps为半径子集）；2）Card(NEps(q) MinPts.定义2：（可达密度）对象p是对象q可达密度的。在数据集D中的Eps和 MinPts，“p D q”这种记法表示，如果有一个对象链p1,.,pn, p1=q, pn=p，其中piD，那么pi+1是 pi可达密度的可达密度是直接可达密度的典型延伸。这种关系是具有传递性的，但不是对称的。虽然整体来看不是对称的，但是很明显，如果对于对象集o，Card(NEps(o) MinPts，那么可达密度是对称的。簇中的两个边界对象集也许相互不是可达密度的，因为这两个数据集的相邻数据集的个数达不到要求的数量。但是，必须有第三个数据集，是这两个边界数据集都可达密度的。因此，我们介绍了可达密度这个概念。定义3：（密度连通）数据集p是密度连通到数据集q的。在数据集D中的Eps和 MinPts，如果有一个对象oD，那么数据集p和q是数据集o可达密度的。密度连通具有对称性，图1说明了基于由来自二维向量空间的对象组成的样本数据库的密度连通的定义。然而，注意到上面的定义只需要一个距离的度量并且同样适用于来自度量空间的数据。图1 可达密度和密度连通簇被定义为一系列密度连通的对象的最大集合，可达密度和噪声是一系列不在任何簇中的元组的集合。定义4：（簇）设D是一组对象的集合。D中的簇C，Eps和 MinPts是一个满足下列条件的D的子集：（1）最大化：p,qD:如果pC 并且 qD p wrt. 满足Eps 和MinPts,那么qC。（2）连通性：p,qC，如果p是密度连通到q wrt.的。满足Eps和MinPts。定义5：（噪声）设C1 ,. . ., Ck是簇，Eps和MinPts是属于D的，那么噪声被定义为数据库D中所有不属于任何簇的数据集的集合。即，噪声 = pD | i: p!Ci在后文中，如果很容易从上下文中判断出来，我们会缩写“wrt. Eps and MinPts”。在一个簇中有两种不同类型的对象集：核心对象集（满足定义1中的第二个条件）和非核心对象集（跟第一种类型相反）。下文中我们将把对象的这个特点指定为对象的核心对象特征。相反，非核心对象既不是边界对象集（不是核心对象但是是从另外一个核心对象可达密度的）也不是噪声对象集（不是核心对象也不是其他对象集密度可达的）。根据以上的定义，DBSCAN算法是用来高效的挖掘簇以及数据库中的噪声的。查找一个簇的程序基于这样一个事实：一个簇是被它的任何一个核心对象集确定的。首先，给出任意一个满足核心对象条件的对象p，全体对象的子集o | oDp，o密度可达于D中的p，形成了一个完整的簇C，pC。第二，给出一个簇C以及任意一个核心对象pC,相反，C和集合o | oD p是一样的。为了查找一个簇，DBSCAN始于