# Context-Based Geodesic Dissimilarity Measure for Clustering Categorical Data
## 3 Materials and Methods
### Constructing the Mutual k-Nearest Neighbor Graph  
The second phase is to represent the observations as a neighborhood graph. The dissimilarity between two observations \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), \(d(\mathbf{x}_{i},\mathbf{x}_{j})\), based on the association-based dissimilarities (AD), is a good dissimilarity measure to reflect correlations among categorical variables but does not capture the nonlinear pattern of data. Therefore, we combine it with the concept of _connectivity_ for the similarity explained below using the mutual \(k\)-nearest neighbor graph. A cluster may be assumed simply as a group of similar objects, but there is no universal consensus on how a similarity should be measured. The best measure of similarity depends on the application. That is, it depends on the structure of the data set being analyzed. The most common measure of similarity may be the concept of _compactness_, which means that how consistent the objects in the same cluster are and those in different clusters are far away from each other. Rather than the concept of compactness, another concept to measure cluster quality is the _connectivity_, which means how well connected the objects in the cluster are to one another. The concept of connectivity deals with clusters of complex shapes and allows finding clusters of arbitrary shapes using the more local concept of clustering, which is based on the fact that adjacent data objects must belong to the same cluster [27]. Several authors ([PERSON] and [PERSON] [28], [PERSON] and [PERSON] [27], [PERSON] and [PERSON] [14]) adopted a measure of cluster quality based on the concept of connectivity rather than compactness. To this end, two concepts of the \(k\)-nearest neighbor consistency (\(k\)-NN consistency) and \(k\)-mutual nearest-neighbor consistency (\(k\)-MN consistency) are necessary, which are explained as follows. According to [PERSON] and [PERSON] [28], the principle of kNN consistency is that all data objects in a cluster must also have \(k\)-nearest neighbors in the same cluster. If objects in the same cluster are close to each other, the closest neighbors of objects in the cluster are also likely to be in the same cluster. Another related concept is the \(k\)-MN consistency. If the nearest neighbor of an object \(A\) is the object \(B\) and the nearest neighbor of object \(B\) is object \(A\), then we say that they are mutual nearest neighbors. In general, if we assume that the object \(A\) is in the set of \(p\) nearest neighbors of object \(B\), and object \(B\) is in the set of \(q\) nearest neighbors of object \(A\), and \(k=max(p,q)\), then we say that the object \(A\) is in the \(k\)-mutual nearest neighbors of the object \(B\) and vice versa. The principle of \(k\)-MN consistency states that for any data object in a cluster, its \(k\)-mutual nearest-neighbors should also be in the same cluster. The principle of \(k\)-MN consistency is stronger and more interactive than that of \(k\)-NN, and it expresses the natural grouping more strictly in the definition of clustering. The \(k\)-NN consistency and \(k\)-MN consistency can be visualized using the \(k\)-nearest neighbor graph and the mutual \(k\)-nearest neighbor graph, respectively. To create the mutual \(k\)-nearest neighbor graph, one should define the \(k\)-nearest neighborhood and the mutual neighborhood set of each node (observation). First, the \(k\)-nearest neighborhood of node \(\mathbf{x}_{i}\), \(K(\mathbf{x}_{i})\), is characterized as follows:\[K(\mathbf{x}_{i})=\{\mathbf{x}_{j}\mid d(\mathbf{x}_{i},\mathbf{x}_{j})\leq d_{i}^ {k}\}, \tag{4}\]  
where \(d(\mathbf{x}_{i},\mathbf{x}_{j})\) represents the dissimilarity measure between node \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), and \(d_{i}^{k}\) is the \(k\)th smallest dissimilarity measure from node \(\mathbf{x}_{i}\) to the other nodes.