目录
第九章 聚类分析：其他问题与算法
数据、簇和聚类算法的特性
比较K均值和DBSCAN
- DBSCAN和K均值都是将每个对象指派到单个簇的划分聚类算法,但是K均值一般聚类所有对象,而DBSCAN丢弃被它识别为噪声的对象。
- K均值使用簇的基于原型的概念,而 DBSCAN使用基于密度的概念
- DBSCAN可以处理不同大小和不同形状的簇,并且不太受噪声和离群点的影响。K均值很难处理非球形的簇和不同大小的簇。当簇具有很不相同的密度时,两种算法的性能都很差
- K均值只能用于具有明确定义的质心(如均值或中位数)的数据。 DBSCAN要求密度定义(基于传统的欧几里得密度概念)对于数据是有意义的
- K均值可以用于稀疏的高维数据,如文档数据。 DBSCAN通常在这类数据上性能很差, 因为对于高维数据,传统的欧几里得密度定义不能很好处理它们。
- K均值和 DBSCAN的最初版本都是针对欧几里得数据设计的,但是它们都被扩展,以便处理其他类型的数据。
- DBSCAN不对数据的分布做任何假定。基本K均值算法等价于一种统计聚类方法(混合模型),假定所有的簇都来自球形高斯分布,具有不同的均值,但具有相同的协方差矩阵。
- DBSCAN和K均值都寻找使用所有属性的簇,即它们都不寻找可能只涉及某个属性子集的簇。
- K均值可以发现不是明显分离的簇,即便簇有重叠也可以发现,但是 DBSCAN会合并有重叠的簇。
- K均值算法的时间复杂度是O(m),而 DBSCAN的时间复杂度是O(m2),除非用于诸如低维欧几里得数据这样的特殊情况。
- DBSCAN多次运行产生相同的结果,而K均值通常使用随机初始化质心,不会产生相同的结果。
- DBSCAN自动地确定簇个数;对于K均值,簇个数需要作为参数指定。然而, DBSCAN必须指定另外两个参数:Eps(邻域半径)和MinPts(最少点数)。
- K均值聚类可以看作优化问题,即最小化每个点到最近的质心的误差的平方和,并且可以看作一种统计聚类(混合模型)的特例。 DBSCAN不基于任何形式化模型。
数据特性
- 高维性：传统的欧几里得密度定义没有意义——使用维归约技术或重新定义邻近度和密度概念
- 规模：不能处理大型数据集
- 稀疏性：一般使用适合于非对称属性的相似性度量，但会出现其他问题
- 噪声和离群点：之前删除或之后删除
- 属性和数据集类型：不同的邻近性和密度度量适合于不同类型的数据
- 尺度：不同的尺度度量影响距离或相似性
- 数据空间的数学性质：使用其他数学运算
簇特性
- 数据分布：某些聚类技术假定数据具有特定的分布
- 形状：簇可以具有任意形状
- 不同大小：簇具有不同大小时不能很好地完成任务
- 不同密度：具有很不相同的密度的簇可能对算法造成问题
- 无明显分离的簇：簇接触或重叠时
- 簇之间的联系：考虑簇之间的联系
- 子空间簇：维的可能子集数以总维数的指数相加
聚类算法的一般特性
- 次序依赖性：数据处理的次序不同，产生的簇的质量和个数也不同
- 非确定性：簇的质量可能随运行而变化
- 可伸缩性：大型数据集时间空间问题
- 参数选择：选择合适的参数值十分困难
- 变换聚类问题到其他领域
- 将聚类作为最优化问题处理
基于原型的聚类
基于原型的概念：
- 允许对象属于多个簇
- 用统计分布对簇进行建模
- 簇被约束为具有固定的联系
模糊聚类
使用混合模型的聚类
混合模型将数据看作从不同概率分布得到的观测值的集合
使用最大似然估计模型参数
使用最大似然估计混合模型参数：EM算法
- 优点：可以使用各种类型的分布，提供了一种消除与数据相关联的复杂性的办法
- 缺点：算法很慢，数据点少或数据点近似协线性时也不能很好处理
自组织映射
Kohenen自组织特征映射（SOFM或SOM）是一种基于神经网络观点的聚类和数据可视化技术。SOM的目标是发现质心的集合，赋予质心地形序，也更新附近的质心
- 优点：互为邻居的簇之间比非邻居的簇之间更相关，有利于聚类结果的解释和可视化
- 缺点：用户必须选择参数、邻域函数、网格类型和质心个数；一个SOM簇通常并不对应于单个自然簇；SOM缺乏具体的目标函数；SOM不能保证收敛，尽管实际中它通常收敛。
基于密度的聚类
基于网格的聚类
将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合，每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值
- 优点：基于网格的聚类可能是非常有效的
- 缺点：非常依赖于密度阈值的选择，还存在一些其他问题
子空间聚类
仅考虑特征子集
- 优点：提供了一种搜索子空间发现簇的有效技术
- 缺点：允许簇重叠
- 优点：具有坚实的理论基础
- 缺点：计算开销更大，对于密度估计的精度可能具有负面影响
基于图的聚类
稀疏化
在实际的聚类开始之前，将许多低相似度的值置0
- 压缩了数据量
- 可以更好地聚类
- 可以使用图划分算法
最小生成树聚类
OPOSSUM：使用METIS的稀疏相似度最优划分
- 优点：简单、速度快
- 缺点：簇可能被分裂或合并
Chameleon：使用动态建模的层次聚类
- 确定合并哪些簇
- 优点：能够有效地聚类空间数据，即便存在噪声和离群点
- 缺点：划分过程未产生子簇时，有问题
共享最近邻相似度
如果两个点都与一些相同的点相似，则即使直接的相似性度量不能指出，它们也相似
- 高维空间相似度很低
- 密度不同的问题
Jarvis-Patrick 聚类算法
SNN密度
可伸缩的聚类算法
可伸缩：一般问题和方法
- 多维或空间存取方法
- 邻近度界
- 抽样
- 划分数据对象
- 汇总
- 并行与分布式计算
BIRCH
CURE
使用哪种聚类算法
- 聚类的类型
- 簇的类型
- 簇的特性
- 数据集和属性的特性
- 噪声和离群点
- 数据对象的个数
- 属性的个数
- 簇描述
- 算法考虑