Gaussian model-based partitioning using iterated local search
Gaussian model-based partitioning using iterated local search
复制标题
DOI：
10.1111/bmsp.12084
复制
发表时间：
2017-02-01
影响因子：
2.6
通讯作者：
Cradit, J. Dennis
中科院分区：
文献类型：
--
作者：
Brusco, Michael J.;Shireman, Emilie;Cradit, J. Dennis
基于高斯模型的划分作为K均值聚类的可行替代方案的出现促进了对可以使用基于模型的标准有效实现的离散优化方法的需求。对于更一般的数据条件，已经提出了各种替代的划分标准，这些条件允许椭圆簇，簇的不同空间方向和不等的簇大小。不幸的是，其中许多划分标准对计算要求很高，这使得通常用于K均值划分的多次重启（多启动）方法作为启发式求解策略的有效性较差。作为替代方案，我们提出了一种基于迭代局部搜索（ILS）的方法，该方法在以前的组合数据分析环境中已被证明是有效的。我们比较了多启动，ILS和混合多启动ILS程序最小化一个非常一般的基于模型的标准，假设没有限制集群大小或组内协方差结构。这一比较，其中使用了23个数据集的分类文献，揭示了ILS和混合动力学一般提供更好的标准函数值比多启动的方法时，所有三种方法都被限制在相同的10分钟的时间限制。在许多情况下，标准函数值的这些差异反映了所获得的分区的深刻差异。
The emergence of Gaussian model-based partitioning as a viable alternative to K-means clustering fosters a need for discrete optimization methods that can be efficiently implemented using model-based criteria. A variety of alternative partitioning criteria have been proposed for more general data conditions that permit elliptical clusters, different spatial orientations for the clusters, and unequal cluster sizes. Unfortunately, many of these partitioning criteria are computationally demanding, which makes the multiple-restart (multistart) approach commonly used for K-means partitioning less effective as a heuristic solution strategy. As an alternative, we propose an approach based on iterated local search (ILS), which has proved effective in previous combinatorial data analysis contexts. We compared multistart, ILS and hybrid multistart-ILS procedures for minimizing a very general model-based criterion that assumes no restrictions on cluster size or within-group covariance structure. This comparison, which used 23 data sets from the classification literature, revealed that the ILS and hybrid heuristics generally provided better criterion function values than the multistart approach when all three methods were constrained to the same 10-min time limit. In many instances, these differences in criterion function values reflected profound differences in the partitions obtained.