caption{Clustering by overall minimum distance (left), and clustering by closeness to the centroid of all locations (right). Each symbol (other than the yellow one) represents the location of an ambiguous gazetteer entry of a place name.}
	\label{fig:clustering}
\end{figure}

The DBSCAN algorithm (Density Based Spatial Clustering of Applications with Noise) is a density-based method that relies on two parameters: the neighborhood distance threshold $\varepsilon$, and the minimum number of points to form a cluster \emph{MinPts}. There is no straightforward way to fit the parameters without pre-knowledge of the data. Moncla \emph{et al.} use DBSCAN for the purpose of place name disambiguation \citep{moncla2014geocoding}, and the parameters in their case were empirically adjusted, since the authors have good understanding of the spatial coverages of the input data as hiking itineraries. A heuristic is proposed to estimate the value of parameters based on \textit{k-dist graph} (a line plot representing the distances to the \textit{k}-st nearest neighbor of each point) in the paper of DBSCAN \citep{ester1996density}. However, it is not trivial to detect the threshold, which requires a selection of value \textit{k} as well as knowledge of the percentage of noise within the data.

\subsubsection{General clustering algorithms for data mining} \label{sec:2.2}
This section introduces clustering algorithms from four groups: density-based, hierarchical-based, partitioning relocation-based, and uncategorized ones.

Using DBSCAN requires a-priori knowledge of the input data to determine the parameters. Some data, such as everyday descriptions in this research, have potentially various conversational contexts, and thus distances between the places mentioned. The algorithm OPTICS (Ordering Points To Identify the Clustering Structure) \citep{ankerst1999optics} address the problem by building an augmented ordering of data which is consistent with DBSCAN, but covers a spectrum of all different $\varepsilon' \leq \varepsilon$. The OUTCLUST algorithm exploits local density to find clusters that are mostly deviating from the overall population (clustering by exceptions) \citep{angiulli2006clustering} given \textit{k}, the number of nearest neighbors for computing local densities, as well as \textit{f}, a frequency threshold, for detecting outliers. 

Hierarchical clustering algorithms typically build cluster hierarchies and flexibly partition data at different granularity levels. The main disadvantage is the vagueness of when to terminate the iterative process of merging or dividing subclusters. CURE (Clustering Using REpresentatives) \citep{Guha1998cure} samples an input dataset and uses an agglomeration process to produce the requested number of clusters. CHAMELEON \citep{karypis1999chameleon} leverages dynamic modelling method for cluster aggregation considering k-nearest neighbor connectivity graph. HDBSCAN \citep{campello2013density} extends DBSCAN based on excluding border-points from the clusters and follows the definition of density-levels.

Partitioning relocation clustering divides data into several subsets, and certain greedy heuristics are then used for iterative optimization. The KMeans algorithm \citep{hartigan1979algorithm} divides the data into \textit{k} clusters through some random initial samples as well as an iterative process to update the centroids of the clusters until convergence. A Gaussian Mixture Model (GMM) \citep{celeux1992classification} attempts to find a mixture of probability distributions that best model the input dataset through methods such as the Expectation-Maximization (EM) algorithm. KMeans is often regarded as a special case of GMM.

There are other algorithms that do not belong to the previous three categories. The SNN (Shared Nearest Neighbours) algorithm \citep{ertoz2003finding} blends a density based approach by first constructing a linkage matrix representing the similarity, e.g., distance, among shared nearest neighbors based on $k$-nearest neighbors (KNN). The remaining part of the algorithm is similar to DBSCAN. Spectral clustering relies on the eigenvalues of the similarity matrix (e.g., KNN) of the data and performs partition of the data into the required number of clusters. Compared to KMeans, spectral clustering cares about connectivity instead of compactness (e.g., geometrical proximity). Kohen's Self Organizing Maps (SOM) \citep{kohonen1998self} is an artificial neural network-based clustering technique applying competitive learning using a grid of neurons. It is able to perform dimensionality reduction and map high-dimensional data to (typically) two-dimensional representation. 

\section{A new robust, parameter-independent algorithm} \label{sec:new}
The task of this research is the following: Given a place description $D$ with $i$ gazetteered place names extracted, $\{p_{1},p_{2},\ldots,p_{i}\}$, each name has a set of (one or more) corresponding gazetteer entries $\{p_{i}^1,p_{i}^2,\ldots,p_{i}^j\}$ that it can be matched to. In order to disambiguate each place name and link it to the entry that it is actually referring to (e.g., $p_{i}$ to $p_{i}^2$), clustering algorithms can be used to either minimize the geographic distances between the disambiguated entries according to some objective function (e.g., minimal average pairwise distance), or to derive high-density clusters that are likely to represent the geographic extents where the original descriptions are embedded. The input to such a clustering algorithm is a 2-dimensional point cloud with the locations of all ambiguous entries $p_{m}^n, m \in (1, i)$. 

The task is to select clusters by these objectives rather than to classify input data into several clusters. Such clusters will then be used for disambiguation, since they are expected to capture the true entries that the place names actually refer to. Points not captured by these clusters will be regard as noise. Therefore, certain clustering algorithms seem more suitable for this task than others, e.g., DBSCAN over KMeans. Furthermore, algorithms that are not parameter-sensitive or require no parameter are preferable, as place descriptions may have various spatial coverages, distance between places, and levels of granularity, thus no pre-knowledge can be assumed. In this section, we propose a novel density-based clustering algorithm \textit{DensityK}. The algorithm is robust, parameter-independent, and consists of three steps.

\subsection{Step one: computing point-wise distance matrix} \label{3.2}
In the first step, the algorithm computes all point-wise distances of an input point cloud, and the time complexity is $O(n^2)$ ($n$ is the number of input points). The time complexity can be reduced to $O((n^2-n)/2)$ with a distance dictionary to avoid re-computation (but needs $O(n^2)$ memory). The worst case time complexity is equal to DBSCAN, both without any indexing mechanism for neighborhood queries. In practice, DBSCAN is expected to be faster since it requires a defined distance threshold $\varepsilon$ and only considers point-wise distances below or equal to the value. With an index, e.g., R-Tree, the computation time can be reduced. $O(n^2)$ is also the worst case time complexity for algorithms that require computing neighborhood distances, e.g., OUTCLUST, SNN, and HDBSCAN. Still, a distance upper-bound value can be enforced for DensityK as an optional parameter to facilitate proceeding time, with an indexing approach similar to DBSCAN.

\subsection{Step two: deriving cluster distance}
In the second step, DensityK analyzes the computed point-wise distances, and derives a cluster distance automatically. The cluster distance is similar to the parameter $\varepsilon$ in DBSCAN, and will be used in the next step for generating clusters. 

First, a \textit{DensityK function} is computed given the point-wise distances in the first step, as shown in Function~\ref{eq:dk}. $K(d)$ represents the average point density for points within a given distance interval $(d-\Delta d, d]$ for all points in an annular region. The reason to apply annular search region for computing point density instead of circular region (i.e., $\Delta d = d$) is because we found the former one leads to better clustering results. A comparison of applying the two search regions is given later in this section. In Function~\ref{eq:dk}, the expression $count(p\in region(p_{i}, {(d-\Delta d, d]}))$ represents the number of points that are at a distance between $d-\Delta d$ and $d$ (including $d$) from point $p_{i}$. If there is no point within all the search regions for all points for a distance interval $(d_{j}-\Delta d, d_{j}]$, skip to the next interval ($(d_{j}, d_{j}+\Delta d]$). Thus, $K(d)$ is aways positive. The denominator of the left side of the function is the area of the annular region. $\Delta d$ is for discretizing the function and is set to 100$m$ in this research. The resulting cluster distance threshold will be the integer multiple of $\Delta d$. We will demonstrate