【摘要】Canopy是一种对“大数据”进行聚类的算法。亦即当聚类问题满足以下条件时，Canopy算法相比于其他算法会非常有效：·类簇的个数很多·样本数

Canopy是一种对“大数据”进行聚类的算法。亦即当聚类问题满足以下条件时，Canopy算法相比于其他算法会非常有效：

·类簇的个数很多

·样本数很多

·样本的维度很高

算法简介

Canopy算法的主要思想是：首先使用一种简单的距离度量方法来将所有样本划分成许多个canopy，然后再在各个canopy之内使用其他的聚类算法进行聚类。第一步可以大幅度降低需要进行比较的次数，因为第二步只需要在划分好的canopy内进行样本的亮亮比较。

1.创建canopy

在第一步中，会使用一个简单的距离度量方法来将所有的样本快速的划分到多个canopy中去。每个canopy是样本的一个子集，包含了一个中心点以及所有到这个中心点的距离小于一定阀值的点。一个样本有可能属于多个canopy。

创建canopy的意图在于，如果两个样本不属于一个公共的canopy，那么这两个样本不可能聚类在一起。为了满足这种性质，可以允许canopy之间有重合(亦即一个样本可以属于多个canopy)，可以设置一个大一点的阀值，等等。

canopy的创建过程为：设置两个距离阀值T_1和T_2，并且T_1 > T_2，令所有样本的集合为S。从S中取出一个样本S_i，计算其到所有其他样本的距离(使用一种简单的距离度量方法)，所有距离小于T_1的点构成一个新的canopy(包括S_i)，然后把所有距离S_i的距离小于T_2的点从S中移除。重复以上步骤直至S为空。上述步骤中将距离S_i的距离小于T_2的点移除的用意是，这些点距离S_i太近了，没有必要以这些点为中心再去构造canopy，因为这些canopy和以S_i为中心点的canopy非常相似。

2.简单的距离度量方法

对于文本文档，可以使用倒排索引来加快距离计算。如果想要找到所有和一个查询比较相关的文章，则只需要先通过倒排索引找到那些包含查询中的关键词的文章。如果我们使用两个文章共同包含的词的个数作为简单距离度量方法，则使用倒排索引会很高效。

倒排索引的思想也可以用在实数域的特征，每个特征离散化成多个桶，然后每个样本就转换成包含多个桶(亦即"关键词")的"文档"，然后就可以使用倒排索引了，如果想避免边缘效应(edge effect，亦即如果把[0,1]划分成[0,0.5]，[0.5, 1]两个桶，虽然0.49和0.51非常接近，但是还是属于不同的桶)，可以可以通过记录相邻的桶来解决这个问题。

python学习网，大量的免费python视频教程，欢迎在线学习！