USA\
author:
- 'M. Emre Celebi'
- 'Hassan A. Kingravi'
title: 'Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering'
---

Introduction {#sec_intro}
============

Clustering, the unsupervised classification of patterns into groups, is one of the most important tasks in exploratory data analysis [@Jain99]. Primary goals of clustering include gaining insight into data (detecting anomalies, identifying salient features, etc.), classifying data, and compressing data. Clustering has a long and rich history in a variety of scientific disciplines including anthropology, biology, medicine, psychology, statistics, mathematics, engineering, and computer science. As a result, numerous clustering algorithms have been proposed since the early 1950s [@Jain10].

Clustering algorithms can be broadly classified into two groups: hierarchical and partitional [@Jain10]. Hierarchical algorithms recursively find nested clusters either in a top-down (divisive) or bottom-up (agglomerative) fashion. In contrast, partitional algorithms find all the clusters simultaneously as a partition of the data and do not impose a hierarchical structure. Most hierarchical algorithms have quadratic or higher complexity in the number of data points [@Jain99] and therefore are not suitable for large data sets, whereas partitional algorithms often have lower complexity.

Given a data set ${{\mathcal X}}= \{ {{\bf x}}_1, {{\bf x}}_2, \dotsc, {{\bf x}}_N \}$ in $\mathbb{R}^D$, 