Clustering algorithms are a method of pre processing the data. Clustering finds the structure within the dataset, and groups current and new training instances and testing instances by this discovered structure. Much like localized learning, clustering is employed to help reduce the noise found within the training data. In fact, many locality based classifiers\footnote{RIPPER, Ridor, and Clump employ this mechanism} act by segmenting the data into clusters, often based on a subset of the attributes, and basing the classification off of one or more clusters.

A subset of clustering algorithms work to reduce the time necessary to perform nearest neighbor calculations. These can be referred to as Indexing algorithms, and include KD Trees, Cover Trees, and Ball Trees. These algorithms create recursive divisions of the entire search space, assigning the training data to each of the divisions. By applying these Indexing algorithms, the nearest neighbor calculations only need to be applied to a subset of the entire training dataset, speeding up gathering of local data.

I will also explain two standard clustering algorithms: K-Means and Greedy Agglomerative Clustering. These algorithms identify and create clusters within the dataset. Because of its relevancy filtering, the Burak Filter\cite{08Turhan} described in \tion{burak} can also be considered a clustering algorithm that discards all training instances that do not fall within one of its K Nearest Neighbor clusters\cite{KNN}. These clustering and indexing algorithms each represent a unique approach to the clustering problem.
