\input{figures/pseudo-code/kmeans}
K-Means\cite{KMeans} is an iterative clustering algorithm designed to find the centroids of clusters within the input space. K-Means has a very long run time, indicative of its $O(kN)$ runtime. This algorithm creates $k$ clusters before even examining any of the data, often leading to vastly incorrect initial centroids. Although the centroids are chosen at random, the iterative process of the algorithm will move the centroids to their correct location. The value of $k$ chosen strongly impacts the performance of the algorithm. The optimal value of $k$ is specific to each dataset, as each dataset has a specific number of clusters within the data. The algorithm follows the below 4 steps:
\be
\item Select $K$ centroids at random.
\item Assign each training instance to its nearest centroid.
\item Move each centroid to it's instances' mean Cartesian coordinates.
\item Steps 2 and 3 are repeated until the centroids stop moving.
\ee
\input{figures/triangle}

\label{pg:triangle}The runtime of K-Means can be decreased by utilizing the "Triangle of Inequality"\cite{kmeansSpeedUp} in \fig{triangle} described by Elkan. Each time the centroids are moved, the distance between each of the centroids and all of the other centroids are cached. The "Triangle of Inequality" is based on the principle that, in a triangle, the length of the hypotenuse is $\le$ the combined length of the other two sides. With this principal, it means that if the distance between two centroids is greater then twice the distance between the testing instance and one of the centroids, than the distance is larger between the testing instance and the other centroid. By using this, it has been shown that the runtime of this accelerated K-Means algorithm is up to 351 times faster than the runtime of a unaccelerated K-Means implementation.
