Canopy算法聚类

　　>Canopy一般用在Kmeans之前的粗聚类。考虑到Kmeans在使用上必须要确定K的大小，而往往数据集预先不能确定K的值大小的，这样如果
K取的不合理会带来K均值的误差很大（也就是说K均值对噪声的抗干扰能力较差）。总之基于以下三种原因，选择利用Canopy聚类做为Kmeans的前奏
比较科学、也是Canopy的优点。

一、canopy算法的优缺点

Canopy的优点：

    1、Kmeans对噪声抗干扰较弱，>通过Canopy对比较小的NumPoint的Cluster直接去掉
有利于抗干扰。

>    2、Canopy选择出来的每个Canopy的centerPoint作为Kmeans比较科学。

   
3、只是针对每个Canopy的内容做Kmeans聚类，>减少相似计算的数量。

Canopy的缺点：算法中
T1、T2（T2 ） 的确定问题
（在并行计算上Maper的T1、T2 可以和Raduce的T1、T2不同）

二、canopy聚类过程

src="https://img8.php1.cn/3cdc5/18d35/711/e7b1e147a811f914.jpeg">

while D is not empty
      >select element d from D to initialize canopy
c
     
remove d from D
   
  Loop through remaining elements in D

           if distance between d_i and c <
T1 : add element to the canopy c

           if distance between d_i and c <
T2 : remove element from D

      end

      add canopy c to the list of canopies
C
end

>　　当距离小于T1大于T2时，这些点会被归入到该中心所在的canopy中，但是它们并不会从D中被移除，也就是说，它们将会参与到下一轮的聚类过程中，成为新的canopy类的中心或者成员。亦即，两个Canopy类中有些成员是重叠的。

src="https://img8.php1.cn/3cdc5/18d35/711/49ca8f4b5cc61e2f.jpeg">

三、公式推导

>        Canopy的关键是以下公式：

>        S0
表示Canopy包含点的权重之和  

>        S1
表示各点的加权和       src="http://chart.apis.google.com/chart?cht=tx&chl=s_1%3d%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_iw_i%7d+">

　　　S2
表示各点平方的加权和

>        聚类分析的抽象是计算：
NumPoint、Radius、Center、(其中
Radius、Center 均是N维向量)

　　 计算公式推导如下：

>        NumPoint 
=  S0

>       Center       = 
S1/S0    

>       Radius     
=   Sqrt(S2*S0-S1*S1)/S0

　　推导过程如下：

    public void
computeParameters();

>　　#根据s0、s1、s2计算numPoints、center和Radius，

>　　其中numPoints=（int）s0，

　　center=s1/s0，

>　　Radius=sqrt(s2*s0-s1*s1)/s0

　　简单点来，假设所有点权重都是1，

     src="http://chart.apis.google.com/chart?cht=tx&chl=std%3d%5csqrt%7b%5cfrac%7b%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7b%28x_i-%5cmu%29%5e2%7d+%7d%7bn%7d%7d">，其中 alt="\mu=\frac{1 }{n}\sum\limit_{i=0}^{n}{x_i}" src="http://chart.apis.google.com/chart?cht=tx&chl=%5cmu%3d%5cfrac%7b1+%7d%7bn%7d%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_i%7d">

>                alt="=\sqrt{\frac{\sum\limit_{i=0}^{n}({x_i^2}-2\mu x_i+\mu^2) }{n}} " src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5csqrt%7b%5cfrac%7b%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%28%7bx_i%5e2%7d-2%5cmu+x_i%2b%5cmu%5e2%29+%7d%7bn%7d%7d%0a%0a">

>                alt="=\sqrt{\frac{\sum\limit_{i=0}^{n}{x_i^2} -2\mu \sum\limit_{i=0}^{n}{x_i} +n\mu^2 }{n}}=\sqrt{\frac{\sum\limit_{i=0}^{n}{x_i^2} -2n\mu^2 +n\mu^2 }{n}}"
src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5csqrt%7b%5cfrac%7b%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_i%5e2%7d+-2%5cmu+%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_i%7d+%2bn%5cmu%5e2++%7d%7bn%7d%7d%3d%5csqrt%7b%5cfrac%7b%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_i%5e2%7d+-2n%5cmu%5e2+%2bn%5cmu%5e2++%7d%7bn%7d%7d">

>                alt="=\sqrt{\frac{\sum\limit_{i=0}^{n}{x_i^2} }{n}-\mu^2 } " src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5csqrt%7b%5cfrac%7b%5csum%5climit_%7bi%3d0%7d%5e%7bn%7d%7bx_i%5e2%7d++%7d%7bn%7d-%5cmu%5e2+%7d%0a">，其中 alt="s1=s0 \quad \mu" src="http://chart.apis.google.com/chart?cht=tx&chl=s1%3ds0+%5cquad+%5cmu">

>                alt="=\frac{\sqrt{s2\quad s0 -s1\quad s1}}{s0} " src="http://chart.apis.google.com/chart?cht=tx&chl=%3d%5cfrac%7b%5csqrt%7bs2%5cquad+s0+-s1%5cquad+s1%7d%7d%7bs0%7d+%0a">

四、参数调整

>当T1过大时，会使许多点属于多个Canopy，可能会造成各个簇的中心点间距离较近，各簇间区别不明显；

当T2过大时，增加强标记数据点的数量，会减少簇个个数；T2过小，会增加簇的个数，同时增加计算时间

　　另外：mahout提供了几种常见距离计算的实现 ，均实现org.apache.mahout.common.distance.DistanceMeasure接口

CosineDistanceMeasure：计算两向量间的夹角
SquaredEuclideanDistanceMeasure：计算欧式距离的平方
EuclideanDistanceMeasure：计算欧式距离
ManhattanDistanceMeasure：马氏距离，貌似图像处理中用得比较多
TanimotoDistanceMeasure：Jaccard相似度，T(a,
b) = a.b / (|a|^2 + |b|^2 - a.b)
以及带权重的欧式距离和马氏距离。

　　需要注意：

1. 首先是轻量距离量度的选择，是选择数据模型其中的一个属性，还是其它外部属性这对canopy的分布最为重要。

2. T1, T2的取值影响到canopy重叠率f，以及canopy的粒度。
3.
Canopy有消除孤立点的作用,而K-means在这方面却无能为力。建立canopies之后，可以删除那些包含数据点数目较少的canopy，往往这些canopy是包含孤立点的。
4.
根据canopy内点的数目,来决定聚类中心数目k,这样效果比较好

五、算法实现

>       单机版Canopy算法:

>                1、从PointList中取一个Point
，寻找已经建立好的Canopy
计算这个点于所有的Canopy的距离。如果和某一个Canopy的距离小于T1，　　　　　　                    
则把这个点加到Canopy中，如果没有Canopy则选择这个点为一个Canopy的中心。

>                2、如果这个店Point和某个Canopy的距离小于T2,则把这个点从PointList中删除（这个点以后做不了其他的Canopy的中心了）。

>                3、循环直到所有的Point都被加入进来，然后计算各个Canopy的Center和Radius。

>       模型MapReduce版本：

>              1、把数据整理成SequcnceFile格式（Mahout-InputMapper）作为初始化文件PointFile

>              2、CanopyMapper阶段本机聚成小的Canopy
中间文件写成SequenceFile 这一步的T1、T2 和Reduce的T1、T2可以是不同的（ index、Canpy）

>              3、所有的Mapper阶段的输出到1个Reducer中
然后Reduce把Map阶段中的Center点再次做聚类算法。聚出全局的Canopy。同时计算每个Canopy的CenterPoint点。写到临时文件CenterPoint中。

>              4、针对全集合PointFile在CenterPoint上的findClosestCanopy操作（通过传入的距离算法）。然后输出一个SequenceFile。 

六、问题总结

>       
有2个问题不知道如何答案：

>               1、T1、T2
的选择(我需要采样计算出吗？)

>               2、如何和Kmeans结合？（只在Canopy内做K均值是什么意思呢？）

Reference：

http://trailblizer.blog.163.com/blog/static/59630364201141973937341/

Mahout学习——Canopy
Clustering

mahout下的Canopy
Clustering实现

聚类—
Canopy算法

http://www.shahuwang.com/2012/08/14/canopy%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95.html

Canopy算法聚类,布布扣,bubuko.com