聚类算法概念、分类、特点及应用场景【机器学习】【无监督学习】

概念

机器学习聚类算法‌是一种无监督学习方法，旨在将数据集分割成不同的类或簇，使得同一簇内的数据对象相似性尽可能大，而不同簇之间的数据对象差异性也尽可能大。聚类算法广泛应用于新闻自动分组、用户分群、图像分割等领域。‌

主要聚类算法及其特点

‌层次聚类算法‌

层次法(hierarchical methods)

   通过构建数据点之间的层次结构来进行聚类，可以是自底向上的凝聚方法或自顶向下的分裂方法。代表算法包括CURE和ROCK，适用于任意形状和属性的数据集，但执行时间较长。‌

‌分割聚类算法‌

又叫划分法(partitioning methods)

   基于密度的聚类‌：如DBSCAN和OPTICS，能够识别任意形状的簇，并对噪声和离群点具有较好的鲁棒性。代表算法包括DENCLUE和DBCLASD，主要用于空间数据的聚类。
‌   基于网格的聚类‌：如STING和CLIQUE，利用属性空间的多维网格数据结构，适用于大规模数据集，但可能降低聚类质量。
‌   基于图论的聚类‌：将聚类问题转换为组合优化问题，利用图论和相关启发式算法解决，适用于复杂数据结构。

密度算法

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
这个方法的指导思想就是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；

图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

网格算法

基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。
代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

模型算法

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。
通常有两种尝试方向：统计的方案和神经网络的方案。

其他聚类算法‌

   ‌谱聚类‌：使用数据的相似性矩阵进行聚类，适用于复杂形状的数据集。‌
   ‌高斯混合模型‌：基于概率模型的聚类方法，适用于估计子群体的分布。
‌   模糊C-means‌：与K-means相似，但允许一个数据点属于多个簇，每个簇有一定的隶属度或概率。
‌   K-medoids‌：使用数据点（medoids）而不是均值作为簇的中心，类似于K-means但更稳健。
‌   Mean Shift‌：通过迭代更新候选簇中心点来寻找数据点密度最高的区域。
‌   BIRCH‌：专为大型数据集设计的层次聚类方法。

具体方法

K-MEANS

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：
首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；
然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

K-MEDOIDS

K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。
改进的算法：k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值，在 K-medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。 [2]
步骤：
1，任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。
以下是循环的：
2，将余下的对象分到各个类中去（根据与medoid最相近的原则）；
3，对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。
4，这样循环直到K个medoids固定下来。
这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。

Clara

上面提到K-medoids算法不适合于大数据量的计算。Clara算法，这是一种基于采样的方法，它能够处理大量的数据。
Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1, O2 … Oi … Ok），然后在这当中选取E最小的一个作为最终的结果。

Clarans

Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。
在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。
与上面所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。

应用

聚类算法在多个领域有广泛应用，例如：
  ‌ 商业领域‌：市场研究、商品归类、广告推荐等。
‌   社会科学领域‌：犯罪区域分析等。
   ‌生物信息学‌：基因片段识别等。
‌   图像处理‌：图像分割、降维等。
   通过这些应用场景，聚类算法在数据处理和分析中发挥了重要作用。

附件

附件一：聚类分析

聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法。

聚类（Cluster）分析是由若干模式（Pattern）组成的，通常，模式是一个度量（Measurement）的向量，或者是多维空间中的一个点。

聚类分析以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。