Canopy是一种对“大数据”进行聚类的算法。亦即当聚类问题满足以下条件时,Canopy算法相比于其他算法会非常有效:
·类簇的个数很多
·样本数很多
·样本的维度很高
算法简介
Canopy算法的主要思想是:首先使用一种简单的距离度量方法来将所有样本划分成许多个canopy,然后再在各个canopy之内使用其他的聚类算法进行聚类。第一步可以大幅度降低需要进行比较的次数,因为第二步只需要在划分好的canopy内进行样本的亮亮比较。
1.创建canopy
在第一步中,会使用一个简单的距离度量方法来将所有的样本快速的划分到多个canopy中去。每个canopy是样本的一个子集,包含了一个中心点以及所有到这个中心点的距离小于一定阀值的点。一个样本有可能属于多个canopy。
创建canopy的意图在于,如果两个样本不属于一个公共的canopy,那么这两个样本不可能聚类在一起。为了满足这种性质,可以允许canopy之间有重合(亦即一个样本可以属于多个canopy),可以设置一个大一点的阀值,等等。
canopy的创建过程为:设置两个距离阀值T_1和T_2,并且T_1 > T_2,令所有样本的集合为S。从S中取出一个样本S_i,计算其到所有其他样本的距离(使用一种简单的距离度量方法),所有距离小于T_1的点构成一个新的canopy(包括S_i),然后把所有距离S_i的距离小于T_2的点从S中移除。重复以上步骤直至S为空。上述步骤中将距离S_i的距离小于T_2的点移除的用意是,这些点距离S_i太近了,没有必要以这些点为中心再去构造canopy,因为这些canopy和以S_i为中心点的canopy非常相似。
2.简单的距离度量方法
对于文本文档,可以使用倒排索引来加快距离计算。如果想要找到所有和一个查询比较相关的文章,则只需要先通过倒排索引找到那些包含查询中的关键词的文章。如果我们使用两个文章共同包含的词的个数作为简单距离度量方法,则使用倒排索引会很高效。
倒排索引的思想也可以用在实数域的特征,每个特征离散化成多个桶,然后每个样本就转换成包含多个桶(亦即"关键词")的"文档",然后就可以使用倒排索引了,如果想避免边缘效应(edge effect,亦即如果把[0,1]划分成[0,0.5],[0.5, 1]两个桶,虽然0.49和0.51非常接近,但是还是属于不同的桶),可以可以通过记录相邻的桶来解决这个问题。
python学习网,大量的免费python视频教程,欢迎在线学习!