基于谱聚类的社区发现算法实现研究(3)
1.3.3 传统的聚类算法
虽然聚类的方法很多，对聚类算法很难有一个简洁的分类，分类很有可能会有重叠，因为一种方法具有很多种特征。但是根据不同的算法过程，我们依然可以系统地将聚类方法分为以下四类：基于划分的方法、基于层次的划分、基于密度的方法和基于网络的方法，本文将在这一章节里逐一介绍这四种方法[7]。
(1).基于划分的方法
聚类分析中最简单、最基本的版本是划分，它把对象组织成多个互斥的组和簇。本文假定簇个数K作为给定的背景知识，这个参数很重要，因为它是划分方法的起点。形式地，当给出有n个数据对象的一个数据集D，另外还有生成的簇数K，对象则会被划分算法分成K个分区（K<n），那么每个分区就是一个簇。所以为了达到全局最优解，划分的方法一般都必须枚举所有的情况，这样容易导致开销巨大，一般采用经典算法渐进的提高聚类的质量，逐步逼近最优解。比如说K-Means算法，或者是K-中心点算法，这类算法很适合发现一些球状簇。倘若因为需要对极大类的数据集或者形态繁杂的簇使用聚类，基于划分的方法就必须被扩展了。这也是划分方法的缺陷之一。
(2).基于层次的方法
尽管划分方法满足把对象分为一些相异的簇这一基本聚类要求，但是在一些不同的情况下，研究者可能会想要将数据划分成不同层次上的组群。层次方法创建给定数据对象集的层次分解，数据对象会被层次聚类方法划分为不同的结构或者“树”，凝聚层次聚类法以及分裂层次聚类法是层次聚类的两种划分[8]。凝聚层次聚类的方法先将n个独立的数据点看做是n个簇，然后不断的合并，直到簇的个数与之前规定的相符合为止。分裂层次聚类的方法是先将n个数据点划归同一个簇，然后不断分裂，等到簇的数目与之前规定的相符合为止。经典算法有AGNES算法和DIANA算法。这些算法的缺点就是如果哪一步完成了，这一步就不能被撤回，回溯在这种基于层次的方法中完全不能使用，所以，基于层次的方法不能更正错误的决定。
(3).基于密度的方法
划分和层次方法是为了去寻找球状簇，但是很难可以寻找到任何形状的簇。对此只需要将簇视为数据空间中由稀疏区域划分出的稠密区域就可以发现所有形状的簇了。主要思想是只要对象或者是数据点的数目超过某个阈值，就继续增长给定的簇，也就是说，对于给定簇中的每个数据点，在给定的半径领域中必须至少包括最少数目的点，这是基于密度聚类方法的主要策略[9]。三种代表性的方法为DBSCAN方法、OPTICS方法和DENCLUE方法。
(4).基于网格的方法
在之前本文对所有使用数据驱动的算法进行了讨论，它们会划分对象集合，并且会将它们自动适应嵌入空间中的数据分布。这种方式使用的是空间驱动的方法，嵌入空间被区分为一个个独立于输入对象分布的单元。STING聚类以及CLIQUE聚类是两个比较经典的算法。
对于许多空间数据挖掘问题，利用网格通常都是有效的方法。所以，这种方法一般会与别的聚类方法放在一起使用，比如前面所说的密度或层次的方法。
不同的分类方法的对比如表1.3.2-1：
方法 一般特点
基于划分的方法
1、能够发现球形互斥的簇
2、基于距离
3、一个簇的中心能够被均值或者是中心点去代表
4、当在中小规模的数据集上进行应用时很有效
基于层次的方法 1、聚类是一个层次的分解
2、不能回溯
3、可以集成其他技术
基于密度的方法 1、任何形状的簇都会被发现