Mahout canopy聚类

时间:2024-04-10 18:34:58

Canopy 聚类

一、Canopy算法流程

Canopy 算法,流程简单,容易实现,一下是算法

(1)设样本集合为S,确定两个阈值t1和t2,且t1>t2。

(2)任取一个样本点p,作为一个Canopy,记为C,从S中移除p。

(3)计算S中所有点到p的距离dist

(4)若dist<t1,则将相应点归到C,作为弱关联。

(5)若dist<t2,则将相应点移出S,作为强关联。

(6)重复(2)~(5),直至S为空。

上面的过程可以看出,dist<t2的点属于有且仅有一个簇,t2<dist<t1 的点可能属于多个簇。可见Canopy是一种软聚类。

数据集合划分完后:

Mahout canopy聚类

Canopy有消除孤立点的作用,而K-means在这方面却无能为力。建立canopies之后,可以删除那些包含数据点数目较少的canopy,往往这些canopy是包含孤立点的。根据canopy内点的数目,来决定聚类中心数目k,这样效果比较好。

当T1过大时,会使许多点属于多个Canopy,可能会造成各个簇的中心点间距离较近,各簇间区别不明显;当T2过大时,增加强标记数据点的数量,会减少簇个个数;T2过小,会增加簇的个数,同时增加计算时间。

二、MapReduce实现

在执行Canopy之前需要用将文本合并,然后用Mahout文本向量化模块计算TFIDF,作为文本向量。向量化之后再用Canopy算法聚类。

(一)簇定义

簇Cluster是一个实体,保存该簇的关键信息,canopy 就是一个cluster。

 privateint id;
簇编号

核心参数:计算完数据后最终的簇属性

private long numPoints;
簇中点的个数

private Vector center;
中心向量 center=

private Vector radius;
半径向量 radius =

调整参数:簇中加入一个点后调整的参数

private double s0; s0= 权重和。对于canopy,w=1
,所有s0=numPoints

private Vector s1;  s1=  x
为point,w为权重。对canopyw =1

private Vector s2 ;  s2= x
为point,w为权重。对canopyw =1

(二)发现中心点

该Job 通过多个Map 寻找局部Canopy ,用1个reduce将map计算的canopy合并,最终输出全局的中心。

输入数据:SequenceFile 格式,key 文件路径,value TFIDF向量。

Map: key 文件路径 ,  value TFIDF 向量

Collection<Canopy> canopies = new ArrayList<Canopy>()

Map(WritableComparable<?> key, VectorWritable point){

CanopyClusterer 将Point 加入到canopies 集合中。加入集合的过程中计算T1,T2.加入到相应的Canopy中。

}

Close(){

遍历canopies 集合,计算每一个Canopy的中心点。

For(canopy :canopies){

计算每一个Canopy的中心点。

输出 key :Text(“centroid”)value: Canopy中心点向量。

}

}

Reduce:key  Text(“centroid”)  value VectorWritable

用1个reduce 将所有map 计算的canopy 中心合并。

Reduce中执行的代码和map的一样。

最终输出canopy 。

For(canopy c :canopys ){

输出:key c.getIdentifier()  ,Value c

}

(三)划分数据

通过上一步找到中心点后,划分数据的过程就比较容易了。输入数据为向量化后的TFIDF向量。该过程只需用Map 就行。

输入格式:key  文档路径  value  TFIDF向量

 Map:

         
Collection<Canopy>canopies = new ArrayList<Canopy>()

Map(WritableComparable<?> key, VectorWritable point){

计算point 和所有中心点的距离,将其划分到距离最近的canopy中

CanopyClusterer.emitPointToClosestCanopy(point,canopyes)

输出 key: canopyid ,value:point

}

setup(){

读Canopy ,到 canopies

}

三、API说明

API

CanopyDriver.main(args);

--input (-i)

输入路径

--output(-o)

输出路径

--distanceMeasure(-dm)

距离度量类的权限命名,如:”org.apache.mahout.common.distance.CosineDistanceMeasure”

--t1 (-t1)

t1值 (t1>t2)

--t2 (-t2)

t2值

--t3 (-t3)

t3值,默认t3=t1

--t4(-t4)

t4值,默认t4=t2

--overwrite (-ow)

是否覆盖上次操作的结果

--clustering (-cl)

是否执行聚类操作,即划分数据

--method (-method)

默认,mapreduce。还可选sequential,执行单机模式

示例

String  [] args ={“--input”,“vector/tfidf-vectors”,

“--output”,      “cluster/canopy”,

“--method”,    “mapreduce”,

“--distanceMeasure”,      “org.apache.mahout.common.distance .CosineDistanceMeasure”,

“--t1”,     “0.45”,

“--t2”,     0.38”,

“--overwrite”,

“--clustering”}

CanopyDriver.main(args);

输出

结果文件

Key类型

Value类型

说明

clusters-*

类id (org.apache.hadoop.io.Text)

类中心

(org.apache.mahout.

clustering.kmeans.Cluster)

每条记录以类id和类中心表示一个类别

clusteredPoints

类id (org.apache.hadoop.io.IntWritable)

文档向量

(org.apache.

mahout.clustering.WeightedVectorWritable)

每条记录中,文档向量代表文档,类id代表该文档所属类别

注:clusters-*中*代表数字,第i次迭代产生的类信息即为clusters-i

四、参考文献