一种基于KD树子样的自动聚类方法

摘要

基于进化算法的自动聚类方法具有搜索目标函数全局最优和自动发现聚类数的优点,同时也存在时间代价过高的缺陷.本文提出一种基于KD树子样的自动聚类方法,该方法使用KD树对样本空间进行分割,并在各子空间中随机取样形成KD树子样,然后在子样中自动聚类,最后运用K-Means在整个样本集中优化子样中的聚类结果.本文方法能够有效避免随机子样分布有偏的缺陷,即使比例很小的子样也能获得较好的聚类效果.仿真结果表明,本文方法能够保证聚类效果没有明显下降的情况下,显著缩短进化算法自动聚类的时间.%The evolution theory based automatic clustering method has advantages in finding the global optimum and the cluster number, but shows the lack of efficiency in machine time.An auto-clustering method using the KD-Tree sub-sampling technique is proposed in this paper.The sample space is divided into subspaces using the KD-Tree method.In each subspace, the KD-Tree subsamples are produced by randomly sampling for later auto-clustering.The K-Means method is used to optimize the cluster results of the sub-samples.The method can effectively overcome the defect of biased distribution for random subsamples and give good cluster results even for small samples.The simulation results show that the method remarkably reduces the machine time for auto clustering without decreasing the clustering effect.