Initialization-independent spectral clustering with applications to automatic video analysis
Initialization-independent spectral clustering with applications to automatic video analysis
复制标题
DOI：
10.1109/icassp.2004.1326626
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
A. Ekin;Sharath Pankanti;A. Hampapur
中科院分区：
文献类型：
--
作者：
A. Ekin;Sharath Pankanti;A. Hampapur
常用的聚类算法，如K均值（KM）和期望最大化（EM），对聚类中心的初始化敏感。相比之下，最近提出的K-调和均值（KHM）算法是更强大的初始化的随机性。然而，当数据的维数（N）很小时（通常小于8），KHM效果最好。由于用于图像/视频和语音处理中的许多聚类问题的特征的维数很大，KHM的好处不能被利用。基于这一观察，本文提出了一种新的方法，将KHM应用于高维数据，以实现与初始化无关的聚类。所提出的方法采用高效的谱聚类技术，从而将数据的亲和矩阵分解为其特征向量和k（簇总数）特征向量对应的k个最大的特征值被保留。也就是说，当k < N时，我们用k-D变换的数据表示N-D数据，并提出在该k-D变换的数据上采用KHM。k < N的假设确实包含了大量重要的视频处理和计算机视觉问题，其中KHM的使用在以前是没有好处的。我们证明了所提出的算法的有效性和效率的人的数量（k）是不是很大的领域，如主持人分组，基于视频的扬声器聚类视频会议，并在小型办公室环境中基于身份的跟踪。
Popular clustering algorithms, such as K-means (KM) and expectation maximization (EM), are sensitive to the initialization of cluster centers. In contrast, recently proposed K-harmonic means (KHM) algorithm is more robust to the randomness of the initialization. However, KHM works best when the dimensionality of the data (N) is small (usually less than 8). Because the dimensionality of features that are used for many clustering problems in image/video and speech processing is large, the benefits of KHM cannot be exploited. Based upon this observation, this paper proposes a novel method to employ KHM for high-dimensional data so as to realize initialization-independent clustering. The proposed method employs efficient spectral clustering techniques whereby the affinity matrix of the data is decomposed into its eigenvectors and k (total number of clusters) eigenvectors corresponding to the k largest eigenvalues are retained. That is, we represent N-D data by k-D transformed data when k < N and propose to employ KHM over this k-D transformed data. The assumption of k < N indeed encompasses a large number of significant video processing and computer vision problems where the use of KHM was not beneficial before. We demonstrate the effectiveness and the efficiency of the proposed algorithm for face clustering in the domains where the number of persons (k) is not large, such as anchorperson grouping, video-based speaker clustering in videoconferencing, and identity-based tracking in small office environments.