Constrained Clustering withk‐means Type Algorithms
Ziqiu Su, Jacob Kogan, Charles Nicholas · 2010
This chapter focuses on three k-means type clustering algorithms and two different distance-like functions. The clustering algorithms are k-means, smoka, and spherical k-means. The chapter introduces the basic notations, and briefly reviews the batch and incremental versions of classical quadratic k-means. It presents the clustering algorithm equipped with Bregman divergences and constraints. The chapter shows by an example that a straightforward adoption of batch k-means may lead to erroneous results, and introduces a modification of incremental k-means that generates a sequence of partitions with improved quality. When information about a large number of must-linked vectors is available, the proposed elimination technique may significantly reduce the size of the dataset. The chapter also introduces a smoka type clustering with constrains. Elimination of must-link constraints is based on results reported in Kogan. The chapter presents the spherical k-means with constraints and the numerical experiments that illustrate the usefulness of constraints are provided. Controlled Vocabulary Terms K-means clustering