An Iterated Local Search Approach for Minimum Sum-of-Squares Clustering
An Iterated Local Search Approach for Minimum Sum-of-Squares Clustering
复制标题
DOI：
10.1007/978-3-540-45231-7_27
复制
发表时间：
2003-08
期刊：
影响因子：
--
通讯作者：
P. Merz
中科院分区：
文献类型：
--
作者：
P. Merz
由于最小平方和聚类(MSSC)是一个NP难的组合优化问题，应用全局优化技术对数值数据进行可靠的聚类似乎是很有前途的。本文考虑了组合启发式优化的概念来逼近MSSC：提出了一种迭代局部搜索(ILS)方法，它能够非常快地找到(近)最优解。在生物微阵列实验得到的基因表达数据上，实验结果表明，ILS算法的性能优于多启发式算法以及其他三种与k-Means相结合的聚类启发式算法。
Since minimum sum-of-squares clustering (MSSC) is anNP-hard combinatorial optimization problem, applying techniques from global optimization appears to be promising for reliably clustering numerical data. In this paper, concepts of combinatorial heuristic optimization are considered for approaching the MSSC: An iterated local search (ILS) approach is proposed which is capable of finding (near-)optimum solutions very quickly. On gene expression data resulting from biological microarray experiments, it is shown that ILS outperforms multi–startk-means as well as three other clustering heuristics combined withk-means.