英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
BIRCH：一种用于超大型数据库的有效数据聚类方法
摘要：
最近，关于寻找对大型数据库有用的模式已经吸引了广泛的关注。在这个领域中，最被广泛关注的问题之一是如何聚类。之前关于聚类的研究并没有充分解决大数据集的问题和最小化输入输出成本的问题。
这篇论文展示了一种叫做BIRCH（使用层次结构平衡迭代减少和聚类）的聚类算法，并证明此算法非常适用于大型的数据库。BIRCH算法递增和动态地对传入的多维度量数据点进行聚类，以尝试用可用资源产生最佳质量聚类（在内存和时间允许范围内）。BIRCH通常可以通过一次扫描数据找到一个好的聚类，并通过一些额外的扫描来提高聚类质量。BIRCH也是数据库领域中第一个有效地处理“噪声”（不是底层模式的一部分的数据点）的聚类算法。我们通过几个实验来评估BIRCH的时间/空间效率，数据输入顺序灵敏度和聚类质量。我们也提供了BIRCH和CLARANS的比较，CLARANS也是一种对于大数据集的聚类算法，并且证明BIRCH是一贯优越的聚类方法。
1介绍
在这篇论文中，我们研究了如何将数据聚类，数据聚类是一种特殊的数据挖掘问题。在给定大量的多维数据点时，数据不会被一次性读入内存。数据聚类可以识别稀疏和拥挤的地方，从而可以发现数据集的整体分布模式。此外，导出的聚类可以比原始数据集更有效的可视化。
一般来说，在要被聚集的数据中涉及到两种类型的属性：度量的和非度量的。在这篇论文中，我们考虑度量属性，正如在大多数统计学文献中那样，聚类延长的形式化普遍如下：给定聚类K的数目和N个聚类的数据集，以及基于距离的测量函数（例如，聚类中的点对之间的加权总数/平均距离），我们被要求找到最小化的数据集的分区。这是一个非常常见的离散优化问题。由于大量的局部最小值，在不尝试所有可能的分区的情况下，通常没有办法找到一个全局最小的解决方案。我们采用统计中使用的问题定义，但是有一个额外的面向数据库的约束：可用内存的数量是有限的（通常比数据集的大小要小得多），我们希望最小化I / O所需的时间。相关的一点是，希望能够考虑到用户愿意花大量时间等待聚类算法的结果。
我们提出一个名为BIRCH的聚类方法，并证明它特别适用于非常大的数据库。它的I / O成本在数据集的大小上是线性的：对数据集进行一次扫描就可以得到很好的聚类，并且可以（可选地）使用一个或多个额外的流程来进一步提高质量。通过评估BIRCH的时间/空间特征，数据输入顺序敏感性和聚类质量，并通过实验比较其他已有的算法，认为BIRCH是超大型数据库的最佳可用聚类方法。BIRCH的体系结构还提供了并行机会，以及在执行过程中获得的基于数据集知识的交互式或动态性能调整。最后，BIRCH是第一个能解决噪声问题的聚类算法（直观的数据点应该被视为“噪声”），并提出了一个合理的解决方案。
论文概述
本文的其余部分安排如下：第二节对相关工作进行了调查，并总结了BIRCH的贡献。第三节介绍一些背景材料。第四节引入了聚类特征（CF）和（CF树）的概念，它们是BIRCH的核心，BIRCH算法的详细描述在第5节中，并且在第6节中给出了BIRCH的初步性能研究，最后得出了我们的结论和未来的发展方向研究在第七部分介绍。
2相关研究综述
统计学，机器学习和数据库已经对数据聚类进行了研究，不同的方法有不同的侧重点。以前的方法，基于概率（像机器学习中的大多数方法）或基于距离（像大多数统计中的工作）一样，没有充分考虑数据集可能太大而不能适应主存的情况。特别是，他们不重新认识到必须从这个角度来看问题如何使用有限的资源（例如，通常远小于数据集的大小的存储器）来尽可能准确地执行集群，同时保持低I / O成本。
基于概率的方法：他们通常假设分离属性的概率分布在统计上彼此独立，事实上，这远非如此。属性之间的关系存在，并且有时这种相关性正是我们正在寻找的。群集的概率表示使得更新和存储群集非常昂贵，特别是如果属性具有大量值，因为它们的复杂性不仅取决于属性的数量，还取决于每个属性的值的数量。相关的问题通常是，构建用于识别集群的基于概率的树不是高度平衡的。对于偏斜的输入数据，这可能会导致性能急剧下降。
基于距离的方法：他们假设所有的数据点都是预先给出的，并且可以被快速扫描。他们完全或部分地忽略了这样一个事实，即并非数据集中的所有数据点在集群目的上同等重要，而且密集的数据点应该集中而不是单独考虑，它们是数据点粒度的全局或半全局方法。也就是说，对于每个聚类决策，他们都检查所有数据点或所有现有的聚类，无论它们多么近或远，他们使用全局测量，这需要扫描所有数据点或所有现有的群集。因此它们都没有线性时间可扩展性和稳定的质量。例如，使用穷举列举（EE），将一组N个数据点划分为K个子集大约有种方法。所以在实践中，虽然它可以找到全局最低限度，但它是除非N和K非常小，否则不可行。迭代优化（IO）从初始分区开始，然后尝试从一个组到另一个组的所有可能的数据点的移动或交换，以查看这样的移动或交换是否提高了测量功能的值。它可以找到一个局部最小值，但是，局部最小值的质量对最初选择的分区是非常敏感的，而最坏的情况时间复杂度仍然是指数的。分层聚类（HC）并不试图找到“最好”的聚类，而是继续合并最近的一对（或分裂最远的一对）对象以形成聚类。通过合理的距离测量，实际HC算法的最佳时间复杂度为0（）。所以N还不能很好地扩展。
聚类已被认为是最近比较有用的空间数据挖掘方法。基于随机搜索的“CLARANS”在统计学上胜过传统的聚类算法。在CLARANS中，一个簇由其中一个中心点或集群中位于最中心的数据点表示。聚类过程被形式化为搜索其中每个节点。是由一组K-rnedoids表示的K分区的图，并且如果两个节点仅相差一个中心点，则两个节点是邻居。CLARANS从随机选择的节点开始。对于当前节点，它最多检查最大邻居，随机选择邻居的数量，如果找到了更好的邻居，则移动到邻居并继续。否则将当前节点记录为本地最小值，并重新启动一个新的随机选择的节点来搜索另一个本地最小值。CLARANS在找到所谓的局部最小值的局部编号后停止，并返回其中最好的局部最小值。CLANS与上述I / O方法效率一样具有相同的缺点，另外，由于最大邻居控制的搜索调整，它可能找不到真正的局部最小值。后来提出了聚焦技术来提高CLARANS处理可能存在于磁盘上的数据对象的能力（1）聚类从每个R *树数据页面绘制的数据集样本;（2）重点关注距离和质量更新的相关数据点，他们的实验表明，时间1s改善，质量损失小。
2.1BIRCH的贡献
一个重要的贡献是我们通过明确的时间和内存约束来制定聚类问题，这种方法适用于非常大的数据集。另外，BIRCH比以前的基于距离的方法具有以下优点：
1、BIRCH是本地的（而不是全局的），因为每个聚类决定都是在不扫描所有数据点或所有现有的聚类的情况下做出的。它使用反映自然亲密度的测量积分，同时，可以在聚类过程中逐步维护。
2、BIRCH利用数据空间通常不被统一占用的现象，因此不是每个数据点对于聚类目的同等重要。点的密集区域被统称为一个单一的群集。稀疏区域中的点被视为超出值并可选择删除。
3、BIRCH充分利用可用内存来派生尽可能好的子集群（以确保准确性），同时最大限度地降低I / O成本（以确保效率）。聚类和缩减过程是组织,其特点是使用内存中高度平衡和高度占领的树结构。由于这些功能，其运行时间可线性扩展。
4、如果我们省略可选的阶段4 5，BIRCH就是一种增量方法，不需要预先提供整个数据集，只扫描一次数据集。
3背景
假设读者熟悉向量空间的术语，我们首先为集群定义质心，半径和直径。给定集群中的N维数据点：其中i = 1,2，hellip;hellip; N，簇的质心，半径R和直径D被定义为：
(1)
(2)
(3)
R是从成员点到质心的平均距离。 D是群集内的平均配对距离。它们是围绕质心的簇的紧密度的两个替代度量。接下来在两个群集之间，我们定义了5个可供选择的距离来测量它们的接近度。
给定两个簇的质心：X01和X02，两个簇的质心欧几里得距离DO和质心曼哈顿距离D1定义为：
(4)
(5)
给定一个聚类中的N1个d维数据点：{Xi}其中i = 1,2，hellip;hellip;N1，另一个聚类中有N2数据点：{Xj}其中j = N1 1，N1 2，...hellip;，N1 N2。这两个簇的平均簇间距离D2，平均簇内距离D3和方差增加距离D4被定义为：
(6)
(7)
（8）
D3实际上是合并群集的D。为了清楚起见，我们将X0，R和D视为单个群集的属性，将D0，D1，D2，D3和D4视为两个群集之间的属性并分别表示它们。用户可以选择预加工数据，方法是在不影响相对位置的情况下加权或移动不同的维度。
4聚类特征和CF树
聚类特征和CF树的概念是BIRCH增量聚类的核心。聚类特征是对我们维护的关于聚类的信息进行总结的一个三元组。
定义4.1：给定一个簇中的N维数据点：{Xi}其中i = 1,2，... N，簇的聚类特征（CF）向量被定义为三元组：CF =（N，LS，SS），其中N是簇中数据点的数量。LS是N个数据点的线性和， SS是N个数据点的平方和。
定理4.1（CF加性定理）：假设CF1 =（N1，LS1，...，SS1），并且CF2 =（N2，LS2，...，SS2）是两个不相交群集的CF矢量。然后通过合并两个不相交群集形成的群集的CF矢量是：
CF1 CF2 =（N1 N2，LS1 LS2，...，SS1 SS2） (9)
证明由直截了当的代数组成。
根据CF定义和加性定理，我们知道随着簇合并，簇的CF矢量可以被递增地，准确地存储和计算。也很容易证明，给定簇的CF矢量，相应的X0，R，D，D0，D1，D2，D3和D4以及通常的质量函数（如簇的加权总数/平均直径）都可以轻松计算。
人们可以将一个簇看作一组数据点，但只将CF矢量存储下来。这个CF矢量不仅是有效的，因为它存储的数据比集群中所有数据点少得多，而且也是准确的，因为它足够计算我们在BIRCH中进行集群决策所需的所有测量。
4.1 CF树
CF树是一个高度平衡的树，具有两个参数：分支因子B和阈值T。每个非叶节点至多包含形式[CFi，childi]的B个条目，其中i = 1，2，...，B，“child”是指向其第i个子节点的指针，CF是CF 由这个孩子代表的子集群。因此，非叶节点表示由其条目表示的所有子集群组成的集群。一个叶节点至多包含L个条目，每个形式为[CFi]，其中i = 1，2，..hellip;hellip;，L。另外，每个叶节点都有两个指针，“prev”和“next”，它们用于链接所有叶节点以便进行高效扫描。叶节点还表示由其条目表示的所有子集群组成的集群。但是叶子节点中的所有条目必须满足关于阈值T的阈值要求：直径（或半径）必须小于T。树大小是T的函数。较大的T是树越小。我们需要一个节点给它，在一个大小为P的页面中。一旦数据空间的维度d被给定，叶子和非叶子条目的大小已知，那么B和L由P确定。因此P可以变化为性能调整。这种CF树将在插入新数据对象时动态构建。它用于引导一个新的插入到正确的子集群中，以便集群使用，就像B 树被用来引导新的插入到正确的位置以进行排序一样。 CF树是数据集的一种非常紧凑的表示方式，因为叶节点中的每个条目不是单个数据点，而是一个子集群（它在特定阈值T下吸收了具有直径（或半径）的许多数据点）。
4.2插入到CF树中
我们现在介绍一种将条目插入CF树的算法。给定条目“Ent”，它按如下方式进行：
- 识别适当的叶子：从根开始，通过根据选择的距离度量选择最近的子节点递归地下降CF树：D0，D1，D2，D3或D4，如在第3节中定义的。
- 修改叶子：当它到达一个叶节点时，它找到最接近的叶子条目，比如Li，然后测试Li是否可以在不违反阈值条件的情况下“吸收”这个“Ent”。如果是这样，则更新Li的CF矢量以反映这一点。如果不是，则向叶子添加用于“Ent”的新条目。如果这个新条目的叶子上有空间，我们就完成了，否则我们必须拆分叶节点，节点分裂是通过选择最远的一对条目作为种子，并根据最接近的标准重新分配剩余的条目来完成的。
- 修改叶子的路径：将“Ent”插入叶子后，我们必须更新叶子路径上每个非叶子条目的CF信息。在没有分裂的情况下，这只需要添加CF矢量以反映“Ent”的添加。叶子分裂要求我们在父节点中插入一个新的非叶子条目来描述新创建的叶子，如果父级具有这个条目的空间，则在所有更高级别上，我们只需要更新CF矢量以反映，添加“Ent”。但是，一般情况下，我们可能不得不拆分父项，直到根目录。如果根目录被拆分，树高会增加1。
-
合并细化：分割是由页面大小引起的，该大小独立于数据的聚类属性。在存在倾斜数据输入顺序的情况下，这可能会影响聚类质量，并且还会降低空间利用率。简单的附加合并步骤通常有助于改善这些问题：假设存在叶分裂，并且该分裂的传播在某个非叶节点Nj处停止，即，Nj可以容纳由分裂产生的附加条目。我们现在扫描节点Nj以找到两个最接近的条目。如果它们不是与分割对应的一对，我们则尝试合并
全文共7549字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15371]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
