英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
基于密度的带噪声的大型空间数据库聚类算法
Martin Ester，Hans-Peter Kriegel，Jouml;rg Sander，徐晓维
慕尼黑大学计算机科学研究所,Oettingenstr. 67, D-80538 Muuml;nchen,德国
{ester | kriegel | sander | 徐晓维} @informatik.uni-muenchen
摘 要
聚类算法对于空间数据库中的类标识任务很有吸引力，但是应用到大型空间数据库需满足以下要求：确定输入参数的领域知识应最少，在大数据库中能发现具有任意形状的聚类并且效率高。著名的聚类算法并没有很好的满足上述三个要求，在本文中，我们提出了一种新的聚类算法——DBSCAN，它依赖于基于密度的聚类概念，该概念旨在发现任意形状的簇。 DBSCAN只需要一个输入参数，并支持用户为其确定适当的值。我们选用SEQUOIA 2000工作台的人工合成数据和真实数据对DBSCAN的有效性和效率进行了实验评估，实验结果表明：（1）在发现任意形状的聚类方面，DBSCAN比著名的算法CLARANS更有效（2）在引入的100多个因素来反映效率方面，DBSCAN优于CLARANS。
关键词：聚类算法，任意形状的簇，大型空间数据库效率，噪声处理
1 介绍
许多应用程序都需要空间管理数据，即与空间有关的数据。空间数据库系统（SDBS）（1994年，Gueting）是空间数据管理的数据库系统。日益增多的大量数据来自卫星图像，X射线晶体学或其他自动设备。因此，自动化知识发现在空间数据库中变得越来越重要。
数据库中知识发现的几项任务（KDD）已在文献中定义（Matheus，Chan＆Pi-atetsky-Shapiro 1993）。本文考虑的任务是类识别，即将数据库的对象分组为有意义的子类。例如，在地球观测数据库中，我们可能想要发现沿着某条河流的房屋类别。
聚类算法对类识别任务很有吸引力，但是应用到大型空间数据库需满足以下要求：
（1）确定输入参数的领域知识应最少，因为在处理大型数据库时，通常不会提前知道适当的值；
（2）发现具有任意形状的聚类，因为空间数据库中聚类的形状可能是球形，拉伸，线性，细长等；
（3）处理大型数据库时的高效率，即处理的是数据库，而不仅仅是几千个对象。
著名的聚类算法并没有很好的满足上述三个要求。在本文中，我们提出了一种新的聚类算法——DBSCAN。该算法只需要一个输入参数，并支持用户为其确定适当的值；能发现任意形状的簇；对于大型是空间数据库很有效。本文的其余部分组织如下：我们在第2节讨论聚类算法，根据上述要求对它们进行评估；在第3节中，我们介绍了基于数据库中密度概念的簇概念；第4节介绍了在空间数据库中发现这种簇的算法DBSCAN；在第5节中，我们使用SEQUOIA 2000基准的合成数据和数据对DBSCAN的有效性和效率进行了实验评估；第6节总结了未来研究的一些方向。
2 聚类算法
有两种基本类型的聚类算法（Kaufman和Rousseeuw 1990）：划分算法和层次算法。划分算法将具有n个对象的数据库D划分成k个簇，k是这些算法的一个输入参数，即某一领域的知识是必需的，但对许多应用程序并不适用。划分算法通常给定数据库D的初始划分，然后采用一种迭代控制策略来优化目标函数。每个簇由簇的质心（k-means算法）或位于簇的中心附近的一个对象（k-medoids 算法）来代表。因此，划分算法有两个步骤：首先，确定最小化目标函数中的k；其次，将每个数据对象赋给离它最近的簇中心所代表的簇。第二步意味着一个分区就相当于一个维诺图并且每个簇被包含某个维诺单元中。因此，通过划分算法得到的每个簇的形状是凸形的。
Ng amp; Han（1994）研究了数据挖掘在空间数据库中的划分算法。CLARANS算法（基于随机搜索的大型应用聚类算法）提出了改进的k-medoids算法。与以前的k-means算法相比，CLARANS更有效并且更高效。实验分析表明，CLARANS在具有上千个对象的数据库上运行效率更高。Ng amp; Han（1994）也讨论了决定簇的值的方法。他们提出将k从2取到n执行CLARANS算法,然后计算每个发现的簇的聚类系数（Kaufman和Rousseeuw 1990），最后将聚类系数最大的聚类作为最优聚类。但是，当n取很大值时，运行时间很长，因为该算法的时间复杂度为O（n）。
CLARANS算法假定所有将要被聚类的对象可以同时存储在主存储器而不需要适用于大型数据库。此外，CLARANS在大型数据库上的运行时间很长。因此，Ester，Kriegel＆Xu（1995）提出了几种聚焦技术，通过将聚类过程集中在数据库的相关部分来解决这两个问题。首先，要聚类的对象小到可以存储到内存；其次，CLARANS在当前需要聚类的数据库的一部分上的运行时间明显少于其在整个数据库上运行的时间。
层次算法将数据库D进行分层，由树状图表示。该树状图可以将数据库D迭代划分成更小的子树，直至每颗子树只包含一个对象。树的每个节点代表数据库D的一个簇。树状图可以在每一步从叶到根通过合并生成（凝聚法）或从根到叶通过分裂生成（分裂法）。与划分算法不同，层次算法不需要k作为输入；但是，层次算法必须定义一个终止条件以使合并或分裂过程结束。例如，在凝聚算法中，终止条件可以是所有簇之间的临界距离Dmin。
当今层次聚类算法的主要问题是难以得到合适的终止条件参数，比如满足既要小到所有的簇能被划分也要大到同一个簇不会被分成两部分要求的Dmin值。最近，信号处理领域的分层算法Ejcluster已经被提出 (Garcfa,Fdez-Valdivia, Cortijo amp; Molina 1994) 用于自动获取终止条件。其核心思想是：同一簇中的两个点之间的距离是否小于“足够小”的一个距离。Ejcluster沿用了分裂的方法，它不需要任何领域知识的输入；此外，实验表明，它在发现非凸状簇方面非常有效。但是，由于需计算任意两点之间的距离，ejcluster时间复杂度为。该时间复杂度对字符识别这样n值适中的应用程序是可以接受的，但对大型数据库是难以接受的。
Jain（1988）研究了一种基于密度的方法来确定k维数据集中的簇。数据集被划分成若干互不重叠的单元和并且构造直方图。相对较高的频率计数点单元是潜在的簇中心和簇之间的边界点落在直方图“山谷”处。该方法能识别任意形状的簇，但是用于存储和检索多维直方图所需的空间和运行时间是巨大的。即使对空间和运行时间进行优化，这种方法的性能取决于划分单元的大小。
3 一种基于密度聚类的概念
当看着图1描述的样本集，我们可以很容易地检测不属于任何簇的簇点和噪声点。
数据库1 数据库2 数据库3
图1：示例数据库
我们认识这些聚类的主要原因在于，在每个聚类中，我们有一个典型的点密度，这个密度比聚类外的要高得多。 此外，噪声区域内的密度低于任何簇中的密度。
在下文中，我们试图在一些k维空间S的点的数据库D中将这种直观的“簇”和“噪声”的概念形式化。注意，我们对簇的概念和DBSCAN算法既适用于二维或三维欧几里德空间也适用于一些高维特征空间。核心思想是对于聚类的每个点，给定半径的邻域必须至少包含最小数量的点，即邻域中的密度必须超过某个阈值。 一个邻域的形状由选择的两点p和q的距离函数决定，用表示。例如，当在二维空间中使用曼哈顿距离时，邻域的形状是矩形的。请注意，我们的方法适用于任何距离函数，因此可以为某些特定应用选择适当的函数。为了可视化，所有示例都将在2D空间中使用欧几里得距离。
定义1：（一个点的Eps邻域）点P的邻域用表示，定义为={q属于D|lt;=}。
一个朴素的方法可能需要簇中的每个点在一个点的Eps邻域中有最小数目（MinPts）的点。但是，这种方法会失败，因为聚类中有两种点，聚类内部的点（核心点）和聚类边界上的点（边界点）。一般来说，边界点的Eps邻域比核心点的Eps邻域包含的点少得多。因此，我们必须将最小点数设置为相对较低的值，以包含属于同一个簇的所有点。但是这个值对于相应的簇不是特征 ， 特别是在存在噪声的情况下。因此，我们要求对于聚类C中的每个点p，在C中有一个点q，使得p在点q的Eps邻域内，并且至少包含MinPts个点。这个定义在下面详细说明。
定义2 :(直接密度可达）从q点关于Eps，MinPts,点p是直接密度可达的,如果
1）p 属于
2）||gt;= MinPts（核心点条件）。
显然，直接密度可达对于核心点对是对称的。但是，一般而言，如果涉及一个核心点和一个边界点，则它不是对称的。图2显示了不对称情况。
P从q直接密度可达
q从p直接密度不可达
p:边界点
q:核心点
图2：核心点和边界点
定义3：（密度可达）从q点关于Eps，MinPts,点p是密度可达的,如果存在点P1 ..... Pn，Pl = q，Pn = P，使得从Pi直接密度可达。
密度可达性是直接密度可达性的规范扩展，这种关系是可传递的，但它不是对称的。图3描述了一些样本点的关系，特别是不对称情况。虽然通常不是对称的，但显然密度可达性对于核心点是对称的。
相同簇C的两个边界点可能密度不可达，因为核心点条件可能不适用于它们两者。但是，C中必须有一个核心点，使得C的边界点从该点密度可达。因此，我们引入覆盖这种边界点关系的密度连通性的概念。
定义4：（密度连接）点p是密度连接到点q ，如果存在一个点o使得p和q都可以从o密度可达。
密度连通性是一种对称关系。对于密度可达点，密度连通性的关系也是自反性的（参见图3）。
现在，我们可以定义我们基于密度的簇概念。直观地说，一个聚类被定义为一组关于密度可达性密度最大的密度连接点。噪声将相对于给定的一组簇来定义。噪声就是D中不属于任何一组的点。
通过o，p和q彼此密度相连
p从q密度可达
q从p密度不可达
图3：密度可达性和密度连通性
定义5: (簇）设D是点的数据库，簇C是D的非空子集，满足以下条件：
1） p，q：如果p 属于 C并且q从p密度可达，那么q 属于C（极大性）
2） p，q属于C：p密度连接到q（连通性）
定义6: (噪声）令 ，...,是数据库D关于参数和的聚类，i = 1，...，k。然后，我们将噪声定义为不属于任何簇的数据库D中的点的集合，即噪声= {p 属于D |i:p不属于）。
请注意，簇C 由于以下原因至少包含MinPts个点。由于C包含至少一个点p，所以p必须通过某点o（其可能等于p）与其自身密度连接。因此，至少o必须满足核心点条件，因此，o的Eps邻域至少包含MinPts个点。
以下词条对验证聚类算法的正确性很重要。直观地说，他们陈述如下。给定参数Eps和MinPts，我们可以用两步法发现一个簇。第一，从数据库中选择一个满足核心点条件的任意点作为种子。其次，从获得包含种子的聚类的种子中检索所有密度可达的点。
引理1：令p是数据库D中的一个点并且，然后集合O = {o | o 属于 D，o从p 密度可达}是一个簇。
簇C并不明显是由其任何核心点唯一决定。但是，C中的每个点都可以从C的任意核心点密度可达，因此，簇C恰好包含从C的任意核心点密度可达的点。
引理2： 设C是一个簇，让p是C中的任意一点，，那么C等于集合O = {o | o是从p密度可达}。
4 DBSCAND：基于密度的带噪声空间聚类应用
在本节中，我们提出了算法DBSCA（基于密度的带噪声空间聚类应用），该算法用于根据定义5和6发现空间数据库中的聚类和噪声。理想情况下，我们必须知道合适的每个簇的参数Eps和MinPts以及来自相应簇的至少一个点。然后，我们可以使用正确的参数从给定点取到所有密度可达的点。但是，对于数据库的所有簇来说，没有简单的方法可以提前获取这些信息。 但是这是一个简单而有效的启发式方法（在4.2节中介绍），用于确定数据库中“最薄”（即最密集）簇的参数Eps和MinPts。因此，DBSCAN使用Eps和MinPts的全局值，即所有簇的值都相同。“最薄”簇的密度参数是指定不被认为是噪声的最低密度的这些全局参数值的良好候选者。
4.1算法
为了找到一个簇，DBSCAN从任意点p开始，并获取从p关于Eps和MinPts所有密度可达的点。如果p是核心点，则此过程会生成一个关于Eps和MinPts聚类（见引理2）；如果p是一个边界点，没有点从p密度可达，并且DBSCAN访问数据库中的下一个点。
因为我们使用Eps和MinPts的全局值，所以D
全文共10666字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[15187]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
