寻谷聚类算法

valley seeking clustering method
所谓的valley seeking聚类方法，就是在特征空间中寻找特征分布密度较小的位置，作为聚类的边界。如下图中的2维特征空间，形成5个分布密度较高的峰，如果能确定峰-峰间的谷的位置，也就等于确定了各个类别的边界，从而完成聚类。算法的目标是非常直观的。

这种聚类方法的流程可以简单描述如下:
1. 确定初始半径，可以取为样本标准差的某个倍数；初始半径的设置影响聚类的数目；
2. 在该半径范围内，确定每个特征的近邻数目，以及近邻的集合。 如果特征的数目为N，需要初始化一个N×N的数组来存放每个特征的近邻编号，计算完成后，可以根据最大近邻集合中元素的数目，删去多余的元素。
3. 如果一个特征的近邻数目，超过它每一个近邻各自的近邻数目，则该特征确定了上图中一个特征密度峰。如此，设置一个最小近邻标准，可以找出全部五个峰。
4. 五个峰确定5个类别，给每个峰的近邻特征设置类别标记；
5. 将所有特征按照近邻数目从大到小排序；
6. 从近邻数目最大的特征开始，看其近邻中属于哪一类别的最多，就将该特征也归入这一类；如此，完成全部特征的聚类。

在上面的聚类结果中，右上角有几个较密集的特征没有归类，反而归类了旁边更分散的几个特征。出现这种问题的原因是这几个特征的形成一个小的局部峰值，这些特征的聚类次序在周围特征之前，而这时，周围的这些特征还没有获得聚类信息。