聚类算法之Canopy

一算法简介：
传统的聚类算法，如K-Means,聚类精度高，但在聚类过程中需要进行大量的计算，速度较慢，只能解决一般的小规模数据应用问题。为了弥补传统聚类算法的不足，便出现了Canopy聚类算法，Canopy聚类最大的特点是不需要事先指定k值(即clustering的个数)，因此具有很大的实际应用价值。与其他聚类算法相比，Canopy聚类虽然精度较低，但其在速度上有很大优势，因此可以使用Canopy聚类先对数据进行“粗”聚类，得到k值后再使用K-means进行进一步“细”聚类。

Canopy算法的主要思想是把聚类分为两个阶段：阶段一，使用简单、快捷的距离计算方法计算对象的相似度，并将相似的对象放在一个子集中，这个子集被叫做Canopy ，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；阶段二，在各个Canopy中使用传统的聚类方法（如K-Means）计算同一Canopy中所有数据向量的距离。

二 Canopy算法流程

1. 将数据集向量化得到一个list后放入内存，选择两个距离阈值：T1和T2，其中T1 > T2，对应下图，实线圈为T1，虚线圈为T2，T1和T2的值可以用交叉校验来确定；

2. 从list中任取一点P，用低成本计算方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy；

3. 如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

4. 重复步骤2、3，直到list为空结束。

使用Canopy算法聚类后，效果如下：

image.png image.png

python实现Canopy算法