# Context-Based Geodesic Dissimilarity Measure for Clustering Categorical Data
## 3 Materials and Methods
### Calculating the Context-Based Geodesic Dissimilarity (CGD) Measure  
The proposed dissimilarity measure, CGD, can be computed from the shortest path in the mutual \(k\)-nearest neighbor graph. Actually, the mutual \(k\)-nearest neighbor graph itself has the meaning of clustering, but there is still the necessity of measuring the dissimilarity measure between the objects in a graph. For example, when there are \(l\) distinct and separated graphs that connect similar objects, if we want to form more than \(l\) clusters, the clustering method needs to partition a graph into more than or equal to two, based on the information of dissimilarity matrix that is composed of \(g_{ij}\) in Equation (8). As a conclusion, measuring the dissimilarity between objects for clustering is necessary even though the mutual \(k\)-nearest neighbor graphs are already configured.  
The distance \(g_{ij}\) between node \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) is defined as follows:  
\[g_{ij}=\min_{p\in P_{ij}}\sum_{l=0}^{|p|-1}w_{i+(l),i+(l+1)}, \tag{8}\]  
where \(P_{ij}\) is the set of all paths between node \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), and \(p=(\mathbf{x}_{i+(0)},\mathbf{x}_{i+(1)},\cdots,\mathbf{x}_{i+(|p|)})\) is one of the paths between node \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\). \(|p|\) is the number of edges in the path. \(\mathbf{x}_{i+(|p|)}\) and \(\mathbf{x}_{i+(0)}\) are the destination (\(\mathbf{x}_{j}\)) and origin (\(\mathbf{x}_{i}\)) of the path, respectively.  
The context-based geodesic dissimilarity measure, \(g_{ij}\) is the minimized sum of the edge weights in the path between node \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\). The shortest path between two nodes in the mutual \(k\)-nearest neighbor graph is a path with the smallest number of edges. If the graph is weighted, it is a path with the minimum sum of edge weights. The length of a geodesic path is called the geodesic distance or shortest distance. Geodesic paths are not necessarily unique, and there can be many, but there is no problem with the geodesic distance being well-defined since all geodesic paths have identical lengths. There exist various algorithms to find the shortest paths in a neighborhood graph [29; 30; 31; 32]. Among these algorithms, [PERSON]'s method [32] has often been used to search for the geodesic distance when the graph is constructed with nonnegative edge weights [33; 34]. For a given source node (observation) in the graph, [PERSON]'s method finds the shortest path between that node and every other node. It can also be used to find the shortest paths from a single node to a single destination node by stopping the iterative algorithm once the shortest path to the destination node has been figured out.  
The key difference between the traditional geodesic distance and the proposed context-based geodesic dissimilarity (CGD) measure is as follows; the traditional geodesic distance is defined based on any graph structure using the Euclidian distance between two numerical data nodes. However, in our study, to accommodate the categorical data clustering problem, the proposed context-based geodesic dissimilarity (CGD) measure is obtained based on the mutual \(k\)-nearest neighbor graph using the association-based dissimilarities between two categorical data nodes.