Towards information-theoretic K-means clustering for image indexing
Towards information-theoretic K-means clustering for image indexing
复制标题
DOI：
10.1016/j.sigpro.2012.07.030
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Jie Cao;Zhiang Wu;Junjie Wu;Wenjie Liu
中科院分区：
文献类型：
--
作者：
Jie Cao;Zhiang Wu;Junjie Wu;Wenjie Liu
信息论K-means（Info-Kmeans）旨在使用K-means算法对高维数据进行聚类，例如由特征袋（BOF）模型表征的图像，并将KL散度作为距离。虽然沿着这条路线的研究努力沿着已经显示出有希望的结果，但仍然存在的挑战是处理图像数据的高度稀疏性。事实上，质心可能包含许多零值特征，这些零值特征在Info-Kmeans的迭代过程中将对象分配给质心时会造成困境。为了应对这一挑战，本文提出了一种基于求和的增量学习（SAIL）算法的Info-Kmeans聚类。具体地说，SAIL可以避免零特征的困境，取代计算的KL分歧之间的实例和质心，由计算的质心熵。为了进一步提高聚类质量，我们还引入了可变邻域搜索（VNS）元启发式算法，并提出了V-SAIL算法。在各种基准数据集上的实验结果清楚地证明了SAIL和V-SAIL的有效性。特别是，它们有助于从极高维和稀疏的图像向量中成功识别出11个地标中的9个，并且存在严重的噪声。
Information-theoretic K-means (Info-Kmeans) aims to cluster high-dimensional data, such as images featured by the bag-of-features (BOF) model, using K-means algorithm with KL-divergence as the distance. While research efforts along this line have shown promising results, a remaining challenge is to deal with the high sparsity of image data. Indeed, the centroids may contain many zero-value features that create a dilemma in assigning objects to centroids during the iterative process of Info-Kmeans. To meet this challenge, we propose a Summation-bAsed Incremental Learning (SAIL) algorithm for Info-Kmeans clustering in this paper. Specifically, SAIL can avoid the zero-feature dilemma by replacing the computation of KL-divergence between instances and centroids, by the computation of centroid entropies only. To further improve the clustering quality, we also introduce the Variable Neighborhood Search (VNS) meta-heuristic and propose the V-SAIL algorithm. Experimental results on various benchmark data sets clearly demonstrate the effectiveness of SAIL and V-SAIL. In particular, they help to successfully recognize nine out of 11 landmarks from extremely high-dimensional and sparse image vectors, with the presence of severe noise.