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

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

作　　者：雷小锋[1] 杨阳[1] 张克[1] 谢昆青[2] 夏征义[3] 

机构地区：[1]中国矿业大学计算机科学与技术学院,徐州221116 [2]北京大学智能科学系/视觉与听觉国家重点实验室,北京100871 [3]中国人民解放军总后勤部后勤科学研究所,北京100071

出　　处：《计算机科学》2009年第7期175-178,共4页Computer Science

基　　金：中国矿业大学科技基金(OD080313);国家863高技术研究发展计划(2006AA12Z217)资助

摘　　要：类内误差平方和最小化的聚类准则求解是NP难问题,K-Means采用的迭代重定位方法本质上是一种局部搜索的爬山算法,因此聚类结果对初始代表点的选择非常敏感,只能保证局部最优。为此,引入元启发式策略,通过建立评估函数对K-Means初始代表点和目标函数之间的依赖关系进行近似,然后利用近似评估函数指导新的初始代表点的选择,构成一种迭代自学习框架下的K-Means算法。实验表明算法可以很好地克服K-Means对初始代表点的依赖性,获得较高质量的聚类结果。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 approxi- mate the dependency between a series of initial representatives of K-Means and the local minimal of objective criterion, and then the selection of initial representatives was done under the supervision of the evaluation function for the next K- Means. This iterative and self-learning process is called Meta-KMeans algorithm. The experimental demonstrations show that Meta-KMeans can overcome the sensitivity to initial representatives of K-Means to a great extent.

关 键 词：聚类问题K-Means算法 元启发式策略 迭代自学习框架 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]