第九章 聚类分析：其他问题与算法

数据、簇和聚类算法的特性

比较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(m²),除非用于诸如低维欧几里得数据这样的特殊情况。
• DBSCAN多次运行产生相同的结果,而K均值通常使用随机初始化质心,不会产生相同的结果。
• DBSCAN自动地确定簇个数;对于K均值,簇个数需要作为参数指定。然而, DBSCAN必须指定另外两个参数:Eps(邻域半径)和MinPts(最少点数)。
• K均值聚类可以看作优化问题,即最小化每个点到最近的质心的误差的平方和,并且可以看作一种统计聚类(混合模型)的特例。 DBSCAN不基于任何形式化模型。

数据特性

1. 高维性：传统的欧几里得密度定义没有意义——使用维归约技术或重新定义邻近度和密度概念
2. 规模：不能处理大型数据集
3. 稀疏性：一般使用适合于非对称属性的相似性度量，但会出现其他问题
4. 噪声和离群点：之前删除或之后删除
5. 属性和数据集类型：不同的邻近性和密度度量适合于不同类型的数据
6. 尺度：不同的尺度度量影响距离或相似性
7. 数据空间的数学性质：使用其他数学运算

簇特性

1. 数据分布：某些聚类技术假定数据具有特定的分布
2. 形状：簇可以具有任意形状
3. 不同大小：簇具有不同大小时不能很好地完成任务
4. 不同密度：具有很不相同的密度的簇可能对算法造成问题
5. 无明显分离的簇：簇接触或重叠时
6. 簇之间的联系：考虑簇之间的联系
7. 子空间簇：维的可能子集数以总维数的指数相加

聚类算法的一般特性

1. 次序依赖性：数据处理的次序不同，产生的簇的质量和个数也不同
2. 非确定性：簇的质量可能随运行而变化
3. 可伸缩性：大型数据集时间空间问题
4. 参数选择：选择合适的参数值十分困难
5. 变换聚类问题到其他领域
6. 将聚类作为最优化问题处理

基于原型的聚类

基于原型的概念：

• 允许对象属于多个簇
• 用统计分布对簇进行建模
• 簇被约束为具有固定的联系

模糊聚类

使用混合模型的聚类

混合模型将数据看作从不同概率分布得到的观测值的集合

使用最大似然估计模型参数

使用最大似然估计混合模型参数：EM算法

• 优点：可以使用各种类型的分布，提供了一种消除与数据相关联的复杂性的办法
• 缺点：算法很慢，数据点少或数据点近似协线性时也不能很好处理

自组织映射

Kohenen自组织特征映射（SOFM或SOM）是一种基于神经网络观点的聚类和数据可视化技术。SOM的目标是发现质心的集合，赋予质心地形序，也更新附近的质心

• 优点：互为邻居的簇之间比非邻居的簇之间更相关，有利于聚类结果的解释和可视化
• 缺点：用户必须选择参数、邻域函数、网格类型和质心个数；一个SOM簇通常并不对应于单个自然簇；SOM缺乏具体的目标函数；SOM不能保证收敛，尽管实际中它通常收敛。

基于密度的聚类

基于网格的聚类

将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合，每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值

• 优点：基于网格的聚类可能是非常有效的
• 缺点：非常依赖于密度阈值的选择，还存在一些其他问题

子空间聚类

仅考虑特征子集

• 优点：提供了一种搜索子空间发现簇的有效技术
• 缺点：允许簇重叠
  
• 优点：具有坚实的理论基础
• 缺点：计算开销更大，对于密度估计的精度可能具有负面影响

基于图的聚类

稀疏化

在实际的聚类开始之前，将许多低相似度的值置0

• 压缩了数据量
• 可以更好地聚类
• 可以使用图划分算法

最小生成树聚类

OPOSSUM：使用METIS的稀疏相似度最优划分

• 优点：简单、速度快
• 缺点：簇可能被分裂或合并

Chameleon：使用动态建模的层次聚类

• 确定合并哪些簇

• 优点：能够有效地聚类空间数据，即便存在噪声和离群点
• 缺点：划分过程未产生子簇时，有问题

共享最近邻相似度

如果两个点都与一些相同的点相似，则即使直接的相似性度量不能指出，它们也相似

• 高维空间相似度很低
• 密度不同的问题

Jarvis-Patrick 聚类算法

SNN密度

可伸缩的聚类算法

可伸缩：一般问题和方法

• 多维或空间存取方法
• 邻近度界
• 抽样
• 划分数据对象
• 汇总
• 并行与分布式计算

BIRCH

CURE

使用哪种聚类算法

• 聚类的类型
• 簇的类型
• 簇的特性
• 数据集和属性的特性
• 噪声和离群点
• 数据对象的个数
• 属性的个数
• 簇描述
• 算法考虑