An Empirical Comparison of NML Clustering Algorithms
An Empirical Comparison of NML Clustering Algorithms
复制标题
NML 聚类算法的实证比较
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
P. Myllymäki
中科院分区：
文献类型：
--
作者：
P. Kontkanen;P. Myllymäki
聚类可以定义为一个数据分配问题，其目标是将数据划分为非层次的项目组。在我们以前的工作中，我们提出了一个信息理论的标准，基于最小描述长度（MDL）的原则，用于定义数据聚类的良好性。这个框架背后的基本思想是通过将属于同一簇的数据项编码在一起来优化数据的总代码长度。在这种情况下，有效的编码是可能的，只有通过利用底层的聚类成员是共同的，这意味着这种方法产生一个隐式定义的数据项之间的相似性度量。形式上的全球代码长度标准进行优化的定义，通过使用直观吸引人的通用归一化最大似然（NML）代码已被证明产生最佳的代码长度在最坏的情况下的意义。在本文中，我们专注于聚类问题的优化方面，并研究了五种算法，可用于有效地搜索指数大小的聚类空间。由于建议的NML聚类标准可以用于比较具有不同数量的聚类标签的聚类，因此聚类的数量事先并不知道，并且确定它是优化过程的一部分。在本文的实证部分，我们比较了所建议的算法的性能优化的NML聚类标准的任务，使用几个真实世界的数据集。
Clustering can be defined as a data assignment problem where the goal is to partition the data into nonhierarchical groups of items. In our previous work, we suggested an information-theoretic criterion, based on the minimum description length (MDL) principle, for defining the goodness of a clustering of data. The basic idea behind this framework is to optimize the total code length over the data by encoding together data items belonging to the same cluster. In this setting efficient coding is possible only by exploiting underlying regularities that are common to the members of a cluster, which means that this approach produces an implicitly defined similarity metric between the data items. Formally the global code length criterion to be optimized is defined by using the intuitively appealing universal normalized maximum likelihood (NML) code which has been shown to produce optimal code lengths in the worst case sense. In this paper, we focus on the optimization aspect of the clustering problem, and study five algorithms that can be used for efficiently searching the exponentially-sized clustering space. As the suggested NML clustering criterion can be used for comparing clusterings with different number of cluster labels, the number of clusters is not known beforehand and determining it is part of the optimization process. In the empirical part of the paper we compare the performance of the suggested algorithms in the task of optimizing the NML clustering criterion using several real-world datasets.