一种基于元启发式策略的迭代自学习K-Means算法

类内误差平方和最小化的聚类准则求解是NP难问题,K-Means采用的迭代重定位方法本质上是一种局部搜索的爬山算法,因此聚类结果对初始代表点的选择非常敏感,只能保证局部最优.为此,引入元启发式策略,通过建立评估函数对K-Means初始代表点和目标函数之间的依赖关系进行近似,然后利用近似评估函数指导新的初始代表点的选择,构成一种迭代自学习框架下的K-Means算法.实验表明算法可以很好地克服K-Means对初始代表点的依赖性,获得较高质量的聚类结果.

Metaheuristic Strategy Based K-Means with the Iterative Self-Learning Framework

The clustering problems based on minimizing the sum of intra-cluster squared-error are known to be NP-hard.The iterative re-locating method using by K-Means is essentially a kind of local hill-climbing algorithm,which will find a locally minimal solution eventually and cause much sensitivity to initial representatives.The meta-heuristic strategy was introduced to minimize the squared-error criterion globally.Firstly,an evaluation function was built to approximate the dependency between a series of initial r...