文档介绍：1空间聚类的内涵理解 定义空间聚类作为聚类分析的一个研究方向,是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度,而不同类中的对象间差异较大[3]。作为一种无监督的学习方法,空间聚类不需要任何先验知识。这是聚类的基本思想,因此空间聚类也是要满足这个基本思想。 对空间数据聚类的要求[2] [5][6] ①可伸缩性; 许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是, 一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。②发现任意形状的聚类; 许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。(虽然聚类分析属于非监督学习方法,但在某些情况下一些基本的客观规律也会或多或少指示聚类分析的结果) ③用于决定输入参数的领域知识最小化; 许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。④对噪声数据不敏感; 绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。⑤对于输入记录的顺序不敏感; 一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。⑥处理高维数据; 一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能分布非常稀疏,而且高度偏斜。 2 空间聚类的主要算法空间聚类的主要方法有五大类:划分聚类算法、层次聚类算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。[2][3] 图 2-1 空间聚类算法分类 划分聚类算法主要包括: K-means 、 K-medoids 、 PAM 、 CLARA 、 K- 模、 K- 原型、 EM 和 CLARANS 等。基本思想:给定一个包含 n个对象或数据的集合,将数据集划分为 k个子集,其中每个子集均代表一个聚类(k≤ n),划分方法首先创建一个初始划分,然后利用循环再定位技术,即通过移动不同划分中的对象来改变划分内容。典型的算法说明: K-means 算法是首先从 n个数据对象随机地选择 k个对象, 每个对象初始地代表了一个簇中心,对剩余的每个对象,根据其与各个簇中心的距离,将它赋给最近的簇,然后重新计算每个簇的平均值。这个过程不断重复, 直到准则函数收敛(说明:一般都采用均方差作为标准测度函数)。特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开,这个特点正是聚类的最根本的实质要求[4]。但是 K-means 也有其缺点: 产生类的大小相差不会很大,对于脏数据很敏感。而在这一点上, K-medoids 做出了相应的改进, K-medoids 不采用聚类中对象的平均值作为参照点,而选用聚类中位置最中心的对象,即中心点,仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。 层次聚类算法层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的,层次聚类方法又可分为自顶向下的分裂算法和自底向上的凝聚算法两种。分裂聚类算法,首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一簇,或者达了某个终结条件,这里的终结条件可以是簇的数目,或者是进行合并的阈值。而凝聚聚类算法正好相反,首先将每个对象作为一个簇,然后将相互邻近的合并为一个大簇,直到所有的对象都在一个簇中, 或者某个终结条件被满足。 CURE(clustering using representatives) 算法采取随机取样和划分相结合的方法:一个随机样本首先被划分,每个划分被局部聚类,最后把每个划分中产生的聚类结果用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题,在处理孤立点时也更加健壮。 CHAMELEON(hierarchical clustering using dynamic modeling) 算法的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类,其次使用凝聚的层次聚类算法反复地合并子类来找到真正的结果类。 CHAMELEON 算法是在 CURE 等算法的基础上改进而来,能够有