This chapter focuses on the basic version of the k-means clustering algorithm equipped with the quadratic Euclidean distance-like function. First, the classical batch k-means clustering algorithm with a general distance-like function is described and a best representative of a cluster, or centroid, is introduced. This completes description of the batch k-means with general distance-like function, and the rest of the chapter deals with k-means clustering algorithms equipped with the squared Euclidean distance.

Elementary properties of quadratic functions are reviewed, and the classical quadratic k-means clustering algorithm is stated. The following discussion of the algorithm s advantages and deficiencies results in the incremental version of the algorithm (the quadratic incremental k-means algorithm). In an attempt to address some of the deficiencies of batch and incremental k-means we merge both versions of the algorithm, and the combined algorithm is called the k-means clustering algorithm throughout the book.

The analysis of the computational cost associated with the merger of the two versions of the algorithm is provided and convexity properties of partitions generated by the batch k-means and k-means algorithms are discussed. Definition of centroids as affine subspaces of R ⁿ and a brief discussion of connections between quadratic and spherical k-means (formally introduced in Chapter 4) complete the chapter.