mahout之1-Canopy聚类

1.Canopy聚类

Canopy聚类是一种简单、快速、但不太准确的聚类方法。

该算法需一种快速的近似距离度量方法和两个距离阈值T1>T2。

while(没有标记的数据点){

选择一个没有强标记的数据点p

把p看作一个新Canopyc的中心

离p距离<T1的所有点都认为在c中,给这些点做上弱标记

离p距离<T2的所有点都认为在c中,给这些点做上强标记

}

Canopy聚类常作为更强聚类方法的初始步骤。

mahoutCanopy聚类实现,采用了两个map-reducejob

第一个Joborg.apache.mahout.clustering.canopy.CanopyDriver:

mapper:org.apache.mahout.clustering.canopy.CanopyMapper

对划分到每个mapper的点根据阈值T1,T2标记Canopy,输出在该mapper上所有Canopy的中心;

mahout实现对原算法略做改动,而避免需先保存所有的点

修改后的算法org.apache.mahout.clustering.canopy.addPointToCanopies

对于一个数据点,遍历已有Canopy{

该点到某Canopy距离<T1,则加入该Canopy;

若点到某Canopy距离<T2,则标记该点已于该Canopy强关联;

}

若该点不存在强关联的Canopy,则为其创建一个新Canopy

reducer:org.apache.mahout.clustering.canopy.CanopyReducer

整个Job就一个reduce任务,对mapper输出的所有点再次使用Canopy聚类,并输出中心点

第二个Joborg.apache.mahout.clustering.canopy.ClusterDriver

使用第一个Job输出的中心点,采用最近距离原则对原数据点进行聚类

用Canopy聚类作为其他方法的初始步骤时,通常不执行该Job

参数调整:

当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)

以及带权重的欧式距离和马氏距离。

相关推荐