所谓的valley seeking聚类方法,就是在特征空间中寻找特征分布密度较小的位置,作为聚类的边界。如下图中的2维特征空间,形成5个分布密度较高的峰,如果能确定峰-峰间的谷的位置,也就等于确定了各个类别的边界,从而完成聚类。算法的目标是非常直观的。
这种聚类方法的流程可以简单描述如下:
1. 确定初始半径,可以取为样本标准差的某个倍数;初始半径的设置影响聚类的数目;
2. 在该半径范围内,确定每个特征的近邻数目,以及近邻的集合。 如果特征的数目为N,需要初始化一个N×N的数组来存放每个特征的近邻编号,计算完成后,可以根据最大近邻集合中元素的数目,删去多余的元素。
3. 如果一个特征的近邻数目,超过它每一个近邻各自的近邻数目,则该特征确定了上图中一个特征密度峰。如此,设置一个最小近邻标准,可以找出全部五个峰。
4. 五个峰确定5个类别,给每个峰的近邻特征设置类别标记;
5. 将所有特征按照近邻数目从大到小排序;
6. 从近邻数目最大的特征开始,看其近邻中属于哪一类别的最多,就将该特征也归入这一类;如此,完成全部特征的聚类。 在上面的聚类结果中,右上角有几个较密集的特征没有归类,反而归类了旁边更分散的几个特征。出现这种问题的原因是这几个特征的形成一个小的局部峰值,这些特征的聚类次序在周围特征之前,而这时,周围的这些特征还没有获得聚类信息。
1. 确定初始半径,可以取为样本标准差的某个倍数;初始半径的设置影响聚类的数目;
2. 在该半径范围内,确定每个特征的近邻数目,以及近邻的集合。 如果特征的数目为N,需要初始化一个N×N的数组来存放每个特征的近邻编号,计算完成后,可以根据最大近邻集合中元素的数目,删去多余的元素。
3. 如果一个特征的近邻数目,超过它每一个近邻各自的近邻数目,则该特征确定了上图中一个特征密度峰。如此,设置一个最小近邻标准,可以找出全部五个峰。
4. 五个峰确定5个类别,给每个峰的近邻特征设置类别标记;
5. 将所有特征按照近邻数目从大到小排序;
6. 从近邻数目最大的特征开始,看其近邻中属于哪一类别的最多,就将该特征也归入这一类;如此,完成全部特征的聚类。 在上面的聚类结果中,右上角有几个较密集的特征没有归类,反而归类了旁边更分散的几个特征。出现这种问题的原因是这几个特征的形成一个小的局部峰值,这些特征的聚类次序在周围特征之前,而这时,周围的这些特征还没有获得聚类信息。