# Common Nearest Neighbor Clustering--A Benchmark
## 1 Introduction  
A data point \(\mathbf{x}_{i}\) is a vector in a (high-dimensional) state space (or feature space) \(\Omega\). A dataset \(S=\{\mathbf{x}_{1},\ldots\mathbf{x}_{n}\}\) is a set of \(n\) data points. The task of cluster algorithms is to partition the dataset into meaningful subsets \(C_{1}\subset S,\ldots C_{m}\subset S\), where the subsets \(C_{1}\ldots C_{m}\) are called clusters. In many practical cases, the dataset \(S\) represents a sample of a probability density \(\rho:\Omega\rightarrow\mathbb{R}_{\geq 0}\), and the true goal of the analysis is to characterize this density. There are several reasons why one would take the detour via a cluster analysis of the sample rather than by analyzing the probability density directly. For example, the probability density might not be known analytically, or the state space \(\Omega\) might be too high dimensional to allow for an analytical or numerical analysis of the probability density. If the goal is to characterize a probability density, then the clusters are often interpreted as discretizations of the state space \(\Omega\), where we denote the state associated to cluster \(C_{i}\) by \(C_{i}\), with \(C_{i}\subset\Omega\). Cluster algorithms can be classified according to a wide range of categories. A very basic categorization is according to whether or not the cluster algorithm enforces a one-to-one mapping of each data point to a specific cluster [1]. In strict partitioning clustering, each data point is assigned to exactly one cluster. By contrast, in overlapping clustering, each data point belongs to one or moreclusters. Finally, in strict partitioning clustering with outliers, any given data point can either belong to exactly one cluster or to no cluster at all. The data points that are not assigned to a cluster are called outliers. Strict partitioning clustering yields a discretization of the state space into crisp, non-overlapping states \(\bigcup_{i=1}^{n}\tilde{C}_{i}=\Omega\), and \(\tilde{C}_{i}\cap\tilde{C}_{j}=\mathcal{O}\) for all \(i\
eq j\) (Figure 1c). By contrast, strict partitioning clustering with outliers yields a discretization that does not fully partition the state space \(\bigcup_{i=1}^{n}\tilde{C}_{i}\subset\Omega\), and \(\tilde{C}_{i}\cap\tilde{C}_{j}=\mathcal{O}\) for all \(i\
eq j\). That is, there is a region \(I=\Omega\backslash\bigcup_{i=1}^{n}\tilde{C}_{i}\) that is not covered by the cluster states. This is the region in which the outliers are located (Figure 1d). An alternative way to categorize cluster algorithms is according to the criterion the algorithms uses to assign a data point \(\mathbf{x}_{i}\) to a cluster [1]. Many commonly used cluster algorithms assign an objective function or a cost function to each possible partitioning of the dataset and aim to optimize the objective function by modifying the partitioning. For example, \(k\)-means clustering aims to minimize the sum of the squared deviations of the cluster members to the cluster center. Because their objective function is based on the relation of each single data point to the cluster center, these algorithms tend to yield spherically shaped clusters. However, shapes in a dataset that we intuitively recognize as clusters are in fact defined by a sudden change in the data-point density at the rims of the cluster, rather than by how distant its members are to the cluster center. This can for example be seen in the _t4.8k_[2] and _Flame_ datasets [3] (Figure 2). Thus, cluster algorithms that are based on such distance-based objective functions are poorly suited to identify clusters with complex shapes or to characterize an underlying probability density [4]. Unfortunately, measuring the data-point density, that is, the number of data points per volume element, is often not possible, because calculating the volume of a state with irregular borders in a high-dimensional and sometimes non-linear state space is extremely difficult.