Canopy聚类

Canopy聚类是一种非常简单、快速、准确地把对象划分成聚类的方法。所有的对象都用多维特征空间中的一个点表示，此算法使用一种快速近似度量法，其两个距离阈值为T1>T2。

算法的基本思想是一开始有一个点集，先从其中选取一个点，并把此点移除此点集，接着创建一个包含此点的Canopy并对点集中剩余的点进行迭代，对于每一点，如果它与第一个点的距离小于T1，就把它添加到此Canopy中;如果它与第一个点的距离小于T2，先把此添加到Canopy中并把它从点集中删除。这种方式避免了对那些距中心点距离小于T2的点做进一步的处理。

此算法不断地迭代直到初始点集为空为止，最终的结果是产生了一个Canopy的集合，每一个Canopy都包含了一个或多个点，每个点都可能出现在一个或多个Canopy中。Canopy集群经常用做更加严格的聚类技术(如k-Means聚类)的初始阶段。

1)并行策略

● 把数据转换为恰当的输入格式。

● 每个mapper对输入集中的点执行Canopy聚类，并输出Canopy的中心。

● reducer收集Canopy的中心，然后计算产生最终的Canopy中心。

● 最后，将各个点划分到最终的Canopy中。

2)设计实现

此实现把包含多维点的序列文件作为Hadoop输入，点可用密集型矢量来表示，也可以用稀疏型矢量来表示。处理过程分为两个阶段，即Canopy生成阶段和聚类阶段(可选)。

(1)Canopy生成阶段

在Map阶段，每个mapper处理一个点的子集，并且使用已选的距离度量和阈值来产生Canopy。mapper根据已知的距离度量和阈值把各个点添加到Canopy中，接着产生此Canopy的中心即为输出，reducer收集所有的初始中心，然后再次应用距离度量和阈值来产生最终的Canopy中心的集合即为输出。reducer的输出格式为SequenceFile(Text,Canopy)，关键字是Canopy标识符。

(2)聚类阶段

在聚类阶段中，每一个mapper都读取由第一阶段产生的Canopy作为输入，因为所有的mapper都由相同的Canopy定义，它们的输出都在shuffle阶段会产生合并，这样每一个reducer都会看到所有的点属于一个或多个Canopy。输出是SequenceFile(IntWritable, WeightedVectorWritable)，关键字是CanopyId。WeightedVectorWritable有两个段，即一个double型的weight和一个VectorWritable的矢量，其表示了一个矢量属于一个给定Canopy的可能性。