聚类算法总结

Posted on 2018-09-09(星期日) 16:46 in Data

基于划分聚类算法(partition clustering)

  • k-means: 是一种典型的划分聚类算法,它用一个聚类的中心来代表一个簇,即在迭代过程中选择的聚点不一定是聚类中的一个点,该算法只能处理数值型数据
  • k-modes: K-Means算法的扩展,采用简单匹配方法来度量分类型数据的相似度
  • k-prototypes: 结合了K-Means和K-Modes两种算法,能够处理混合型数据
  • k-medoids: 在迭代过程中选择簇中的某点作为聚点,PAM是典型的k-medoids算法
  • CLARA: CLARA算法在PAM的基础上采用了抽样技术,能够处理大规模数据
  • CLARANS: CLARANS算法融合了PAM和CLARA两者的优点,是第一个用于空间数据库的聚类算法
  • Focused CLARAN: 采用了空间索引技术提高了CLARANS算法的效率
  • PCM: 模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法

基于层次聚类算法:

  • CURE: 采用抽样技术先对数据集D随机抽取样本,再采用分区技术对样本进行分区,然后对每个分区局部聚类,最后对局部聚类进行全局聚类
  • ROCK: 也采用了随机抽样技术,该算法在计算两个对象的相似度时,同时考虑了周围对象的影响
  • CHEMALOEN(变色龙算法): 首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇,找到真正的结果簇
  • SBAC: SBAC算法则在计算对象间相似度时,考虑了属性特征对于体现对象本质的重要程度,对于更能体现对象本质的属性赋予较高的权值
  • BIRCH: BIRCH算法利用树结构对数据集进行处理,叶结点存储一个聚类,用中心和半径表示,顺序处理每一个对象,并把它划分到距离最近的结点,该算法也可以作为其他聚类算法的预处理过程

    • Birch 在高维数据上表现不好。一条经验法则,如果 n_features 大于20,通常使用 MiniBatchKMeans 更好。
    • 如果需要减少数据实例的数量,或者如果需要大量的子聚类作为预处理步骤或者其他, Birch 比 MiniBatchKMeans 更有用。
  • BUBBLE: BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间

  • BUBBLE-FM: BUBBLE-FM算法通过减少距离的计算次数,提高了BUBBLE算法的效率

基于密度聚类算法:

  • DBSCAN: DBSCAN算法是一种典型的基于密度的聚类算法,该算法采用空间索引技术来搜索对象的邻域,引入了“核心对象”和“密度可达”等概念,从核心对象出发,把所有密度可达的对象组成一个簇

    DBSCAN 算法是具有确定性的,当以相同的顺序给出相同的数据时总是形成相同的聚类。 然而,当以不同的顺序提供数据时聚类的结果可能不相同。首先,即使核心样本总是被 分配给相同的聚类,这些集群的标签将取决于数据中遇到这些样本的顺序。第二个更重 要的是,非核心样本的聚类可能因数据顺序而有所不同。 当一个非核心样本距离两个核心样本的距离都小于 eps 时,就会发生这种情况。 通过三角不等式可知,这两个核心样本距离一定大于 eps 或者处于同一个聚类中。 非核心样本将被非配到首先查找到改样本的类别,因此结果将取决于数据的顺序。

  • GDBSCAN: 算法通过泛化DBSCAN算法中邻域的概念,以适应空间对象的特点

  • OPTICS: OPTICS算法结合了聚类的自动性和交互性,先生成聚类的次序,可以对不同的聚类设置不同的参数,来得到用户满意的结果
  • FDC: FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间,当空间维数较少时可以大大提高DBSCAN的效率

基于网格的聚类算法:

  • STING: 利用网格单元保存数据统计信息,从而实现多分辨率的聚类
  • WaveCluster: 在聚类分析中引入了小波变换的原理,主要应用于信号处理领域。(备注:小波算法在信号处理,图形图像,加密解密等领域有重要应用,是一种比较高深和牛逼的东西)
  • CLIQUE: 是一种结合了网格和密度的聚类算法

基于神经网络的聚类算法:

  • 自组织神经网络SOM: 该方法的基本思想是--由外界输入不同的样本到人工的自组织映射网络中,一开始时,输入样本引起输出兴奋细胞的位置各不相同,但自组织后会形成一些细胞群,它们分别代表了输入样本,反映了输入样本的特征

基于统计学的聚类算法:

  • COBWeb: COBWeb是一个通用的概念聚类方法,它用分类树的形式表现层次聚类
  • AutoClass: 是以概率混合模型为基础,利用属性的概率分布来描述聚类,该方法能够处理混合型的数据,但要求各属性相互独立

facenet chinese whispers原理

  • 1、 构建无向图,将每个人脸做为无向图中的一个节点,人脸之间的相似度,作为节点之间的边,如果人脸之间的相似度小于上面设定的阈值,那么.这两个人脸对应的节点之间就没有边;

  • 2、 迭代开始时,将每个人脸都赋予一个id,该id作为该人脸的类别,也就是说初始化时,每个人脸都是一个类别

  • 3、 开始第一次迭代,随机选取某个节点,对该节点的所有邻居依次进行下面的处理:

    • 3.1 如果是初始化的时候,由于每个节点都有自己所属的类别,就将所有邻居中权重最大的节点对应的类做为该节点的类别,完成对该节点的类别更新

    • 3.2 如果迭代到第2次,那么对某个节点,就可能会出现有两个邻居属于同一个类,那么就将同一个类下的邻居权重累加,最后,再看该节点下的所有邻居节点所属的类别的累加权重,取权重最大的类别作为当前节点的类别.

  • 4、 当所有的节点都完成后,就完成了一次迭代,重复2步骤,直到达到迭代次数.


Affinity Propagation

AP聚类是通过在样本对之间发送消息直到收敛来创建聚类。然后使用少量示例样本作为聚类中心来描述数据集, 聚类中心是数据集中最能代表一类数据的样本。在样本对之间发送的消息表示一个样本作为另一个样本的示例样本的 适合程度,适合程度值在根据通信的反馈不断更新。更新迭代直到收敛,完成聚类中心的选取,因此也给出了最终聚类。

AP聚类算法主要的缺点是算法的复杂度. AP聚类算法的时间复杂度是 O(N^2 T), 其中 N 是样本的个数 ,T 是收敛之前迭代的次数. 如果使用密集的相似性矩阵空间复杂度是 O(N^2) 如果使用稀疏的相似性矩阵空间复杂度可以降低。 这使得AP聚类最适合中小型数据集。


Mean Shift

MeanShift 算法旨在于发现一个样本密度平滑的 blobs 。 均值漂移算法是基于质心的算法,通过更新质心的候选位置为所选定区域的偏移均值。 然后,这些候选者在后处理阶段被过滤以消除近似重复,从而形成最终质心集合。

算法自动设定聚类的数目,取代依赖参数 bandwidth(带宽),带宽是决定搜索区域的size的参数。 这个参数可以手动设置,但是如果没有设置,可以使用提供的评估函数 estimate_bandwidth 进行评估。

该算法不是高度可扩展的,因为在执行算法期间需要执行多个最近邻搜索。 该算法保证收敛,但是当 质心的变化较小时,算法将停止迭代。

参考