聚类算法

1.概念

聚类 -> 无监督学习(无分类、分组信息)
实现 -> 距离、相似性系数
目的 -> 数据预处理 -> 复杂数据结构(多维) -> 标准化
发现数据之间的依赖关系，删除或合并有密切依赖关系的数据

2.分类

1.基于划分的聚类方法

自顶向下
概念：n个元素组成的数据集D, 将数据分成k(k <= n)个簇
典型算法：k-means(k-平均), k-medoids(k-中心)
特点：
优 -> 收敛速度快
缺 -> 根据数据k可以合理的估计，初始中心的选择和噪声对聚类结果产生很大影响

2.基于层次的聚类方法

对数据进行层次分解，直到满足某种条件
自底向上
典型算法：凝聚式层次聚类 (AGNES(AGglomerativeNESing))
每个对象为一个簇，根据簇之间的距离，将距离最近的点合并到同一个簇，重复操作，直到达到某个终止条件为止
簇与簇之间距离计算：
1.最短距离法 -> 将簇与簇的距离定义为簇与簇之间数据对象的最短距离
2.中间距离法
3.类平均法
自顶向下
典型算法：分裂式层次聚类(DIANA(DivisiveANAlysis))
所有个体为一个簇，逐渐细分为更小的簇，直到每个数据对象都在不同的簇中，或达到某个中止条件

3.基于密度的聚类方法

寻找被低密度区域分离的高密度区域
特点：
1.基于距离的聚类算法的聚类结果是球状的簇，基于密度的聚类算法可以发现任意形状的簇
2.从数据对象分布的的密度着手，如果给定类的数据对象在给定的范围中，则数据对象的密度超过某一阈值就继续聚类
3.通过连接密度较大的区域，形成不同的簇，可以消除孤立点和噪声对聚类质量的影响，形成任意形状的簇
典型算法：DBSAN、OPTICS、DENCLUE

4.基于网格的聚类方法

将空间量化为有限数目的单元，形成一个网格结构，所有聚类都在网格上进行，建立网格单元的集合
特点：
优 -> 处理速度快，处理时间独立于数据对象数，仅依赖量化空间中每一维的单元数
缺 -> 只能发现边界是水平或垂直的簇，而不能检测到斜边界，而且在处理高维数据时，网格单元数目会随着属性维度的增长而成指数级增长

5.基于模型的聚类方法

优化给定数据和某些数学模型之间的适应性，给每一个簇假定了一个模型，寻找数据对给定模型的最佳组合
假定的模型可能是代表数据对象在空间分布情况的密度函数或者其他函数
原理：假定目标数据集是由一系列潜在的概率分布决定的
优化给定数据和某些数据模型之间的适应性

Question

1.基于模型的聚类方法，如何寻找数据对给定模型的最佳组合

基于模型的聚类方法中有很多算法，不同的算法在如何寻找数据对给定模型的最佳组合方面可能略有不同。不过一般来说，这些算法都需要先定义出一个合适的模型，并将数据按照这个模型进行分组，得到初始的聚类结果后，再通过优化算法不断调整分组的方式，以期得到更加合理的聚类结果。其中常用的优化算法包括k-means算法、层次聚类算法等。

具体而言，寻找数据对给定模型的最佳组合通常包括以下步骤：

1.选择合适的模型。不同的数据集适合不同的模型，因此首先需要选择适合当前数据集的合适的模型。
2.初始化。根据选择的模型，需要确定聚类的数量，并随机初始化一组聚类中心点。
3.计算每个数据点到各个聚类中心的距离。根据选定的相似度度量规则，计算每个样本点到每个聚类点的距离或者相似度。
4.将数据点分配到距离最近的聚类中心。每个数据点都属于距离他最近的聚类中心所在的簇。
5.调整聚类中心。将簇内所有数据点的坐标平均值作为新的聚类中心。
6.重复迭代，直到聚类中心不再发生变化或达到最大迭代次数时停止迭代。
7.评估聚类结果。通过一些指标（如轮廓系数、DB指数等）来评估当前的聚类结果是否合理，是否需要进一步优化。
以上是一般基于模型的聚类方法寻找数据对给定模型的最佳组合的大致流程。当然，具体实现还需要根据所使用的算法进行具体调整和优化。

2.k-means算法不是基于划分的聚类方法吗，为什么基于模型的聚类方法也会用到

k-means算法是一种基于划分的聚类算法，而基于模型的聚类方法则不一定是基于划分的，有些可能使用层次聚类等其他算法。在基于模型的聚类方法中，可能会选择合适的模型，如高斯混合模型、概率分布模型等，然后将数据按照这个模型进行聚类。以高斯混合模型为例，可以通过最大期望算法来估计模型参数，得到每个数据点属于每个混合成分的概率，并将概率最大的混合成分作为数据点所属的簇。因此，在基于模型的聚类方法中，可能会使用k-means算法等基于划分的聚类算法作为子任务来实现更复杂的聚类操作。