# Context-Based Geodesic Dissimilarity Measure for Clustering Categorical Data
## 3 Materials and Methods
### Calculating the Association-Based Dissimilarities (AD) between Two Observations  
For the notation, let us have a dataset with \(n\) observations, which is expressed as \(\mathbf{x}=\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}\}\), and composed by a set of categorical variables \(\mathbb{A}=\{A_{1},A_{2},\cdots,A_{p}\}\), where \(p\) is the dimensionality of the data. Each categorical variable \(A_{k}\) can take an element of the domain that contains all possible categorical values. Because the domains of the categorical variables are finite and nominal (or ordinal), the domain of \(A_{k}\) with \(q_{k}\) elements can be expressed as \(A_{k}=\{a_{k1},a_{k2},\cdots,a_{kq_{k}}\}\). For convenience, we use \(A_{k}\) and \(a_{kq}\) to refer to the \(k\)-th categorical variable and its categorical value, respectively. Then, each data observation \(\mathbf{x}_{i}\) consists of \((x_{i1},x_{i2},\cdots,x_{ip})\), where \(x_{ik}\in A_{k}\). The dissimilarity between two categorical values, \(a_{ks}\) and \(a_{kt}\), with respect to a specific categorical variable \(A_{k}\) is expressed by \(d_{A}(a_{ks},a_{kt})\) and the distance between two data observations, \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), is expressed by \(d(\mathbf{x}_{i},\mathbf{x}_{j})\)[21]. [PERSON] and [PERSON] [8] proposed an indirect method which is called the association-based dissimilarity (AD), to measure the distance between two categorical values. It considers the dissimilarity measure between two categorical values as a sum of dissimilarities between two conditional probability distributions of other variables, given these two nominal or ordinal values. In particular, their proposed method is suitable for datasets whose categorical variables are highly correlated. The association-based dissimilarity measure is composed of two iterative steps: (1) First, the dissimilarity between two values \(a_{ks}\) and \(a_{kt}\) of a categorical variable \(A_{k}\) is calculated, denoted by \(d_{A}(a_{ks},a_{kt})\). (2) Then, the dissimilarity between two data observations \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), which is denoted by \(d(\mathbf{x}_{i},\mathbf{x}_{j})\), is obtained as the sum of dissimilarities for their categorical value pairs. The dissimilarity between two observations \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\), denoted by \(d(\mathbf{x}_{i},\mathbf{x}_{j})\), can be calculated using the association-based dissimilarity (AD), denoted by \(d_{A}(a_{ks},a_{kt})\), between two categorical values as follows. \[d(\mathbf{x}_{i},\mathbf{x}_{j})=\sum_{k=1}^{p}d_{A}(x_{ik},x_{jk}), \tag{1}\]  
where \(\forall x_{ik},x_{jk}\in A_{k}\). According to [PERSON] and [PERSON] [8], an association-based dissimilarity (AD) between two values \(a_{ks}\) and \(a_{kt}\) of a categorical variable \(A_{k}\) is the sum of the dissimilarities between two conditional probability distributions of other categorical variables, given that categorical variable \(A_{k}\) holds value \(a_{ks}\) and \(a_{kt}\), in the form of  
\[d_{A}(a_{ks},a_{kt})=\sum_{k^{\prime}=1,\ k^{\prime}\
eq k}^{p}\psi(P(A_{k^{ \prime}}|A_{k}=a_{ks}),P(A_{k^{\prime}}|A_{k}=a_{kt})), \tag{2}\]  
where \(\forall k,\ k^{\prime}\in\{1,2,\cdots,p\}\), \(\forall s,t\in\{1,2,\cdots,q_{k}\}\), \(P(\cdot|\cdot)\) are the conditional probability distributions, and \(\psi(\cdot,\ \cdot)\) is a dissimilarity function for two probability distributions. To date, several dissimilarity measures \(\psi(\cdot,\ \cdot)\) between probability distributions have been proposed [22; 23; 24; 25]. [PERSON] and [PERSON] [8] employed KL divergence [26] in a dissimilarity function for two probability distributions. Although KL divergence is the most popular dissimilarity measure between probability distributions, the direct use of KL divergence in our study may cause a critical drawback in two different perspectives; (1) First, KL divergence is not defined when the denominator in log term in the definition becomes zero.