CURE算法详解

CURE算法详解

第二十九次写博客，本人数学基础不是太好，如果有幸能得到读者指正，感激不尽，希望能借此机会向大家学习。这一篇作为可伸缩聚类（Scalable Clustering）算法的第二篇，主要是对CURE（Clustering Using Representative）算法进行详细介绍，其他可伸缩聚类算法的链接可以从《可伸缩聚类算法综述（可伸缩聚类算法开篇）》这篇文章中找到。

CURE算法简介

  CURE（Clustering Using Representative）采用了一种新型的层次聚类算法，这种算法介于“单链”和“组平均”之间，他克服了这两种层次聚类算法的不足之处，如下图所示分别使用“单链”与“组平均”处理图1（a）中的数据，“单链”会将由低密度带连接的两个簇错误的合并为一个簇（如图1（c）所示），而“组平均”得到的簇偏向于球形，因此会将图中瘦长的簇拆散（如图1（b）所示），而CURE算法可以处理大型数据、离群点和具有非球形大小和非均匀大小的簇的数据。

  该算法采用簇中的多个代表点来表示一个簇，首先选择簇中距离质心最远的点做为第一个点，然后依次选择距离已选到的点最远的点，直到选到$c$个点为止（一般选择$c\ge 10$），这些点捕获了簇的形状和大小。然后将这些选取到的点根据参数$\alpha$（$0\le \alpha \le 1$）向该簇的质心收缩，距离质心越远的点（例如离群点）的收缩程度越大，因此CURE对离群点是不太敏感的，这种方法可以有效的降低离群点带来的不利影响。
  在得到上述缩减后的代表点后，两个簇之间的距离就可以定义为这两个簇中距离最近的两个代表点之间的距离，距离的数学定义如下

其中，簇$u$的代表点集合表示为$u.rep$，$dist\left(\cdot ,\cdot \right)$可以采用$L_p$或其他距离度量方式。然后在CURE层次聚类算法的每一步中对距离最近的簇进行合并。可以看到，当$\alpha =0$时每个代表点都缩减到了该簇的质心上，这相当于“组平均”层次聚类，而当$\alpha =1$时每个代表点不会缩减，因此相当于“单链”层次聚类。
  CURE算法的空间复杂度与数据集大小$n$呈线性关系，而时间复杂度高达$O\left(n^2\log n\right)$，对于低维数据集该复杂度可以降低到$O\left(n^2\right)$，因此其时间