聚类算法 AP 和 DBSCAN解读

Afinity Propagation

 

AP 的关键在于用 匹配度 (Responsibility) 和  (Availability) 来衡量中心点(Examplar).

 

先上原文:

The “responsibility” r(i,k), sent from data point i to candidate exemplar point k, reflects the accumulated evidence for how well-suited point k is to serve as the exemplar for point i, taking into account other potential exemplars for point i

聚类算法 AP 和 DBSCAN解读

 

The “availability” a(i,k), sent from candidate exemplar point k to point i, reflects the accumulated evidence for how appropriate it would be for point i to choose point k as its exemplar, taking into account the support from other points that point k should be an exemplar

    聚类算法 AP 和 DBSCAN解读

 

 个人理解:

如果用耍朋友来比喻,

Responsibility相当于'恋爱度',衡量i和k两人是否会恋爱,主要考虑双方是否合得来(similarity),然后再考虑周围的人的感受(availability)。

Availibily 相当于 '结婚度', 要考虑两人是否结婚,就要考虑两个人周围的家人,朋友的态度,所以把大家对我女朋友的态度搜集起来( sum(r(i',k)) ) 评估我们结婚的可行性(Availability)

 

最终我们要找到像林志玲这样国民老婆,那就把每个人的R得分和A得分汇总,看谁既和最多人的人在感情上合得来,又尽量得到最多人的祝福。

 

优点:

1. 尽可能考虑到了所有人的看法。

2. 不用像K MEAN那样预设中心点。

缺点:

1.计算复杂

2. damping(阻尼,即训练衰减) 和 prefrence(sim(k,k)初始值) 参数设得不好就完了

 

DBSCAN

D for density.

 

用密度(Density)+领域来定义关键点,然后用中心点的领域相交来定义是否连通,最后将连同的点分在一起。

这篇blog讲得不错:https://www.cnblogs.com/LHWorldBlog/p/8318207.html

 

优点:

1. 过滤噪音

2. 避免初始中心点拍板

缺点:

1. 密度定义困难,特别高维空间计算困难

2. 分类不是很均匀

 

上一篇:九、dockerfile指令讲解


下一篇:NPB Benchmark安装教程(version:3.3.1,Ubuntu14.04)