Ghashti and Thompson John Thompson, 3187 University Way, Kelowna, British
Columbia, Canada, V1V 1V7

# Mixed-type Distance Shrinkage and Selection for Clustering via Kernel Metric
Learning

Jesse S. Ghashti  University of British Columbia, Department of Computer
Science, Mathematics, Physics, and Statistics, Kelowna, BC, Canada  John R. J.
Thompson  University of British Columbia, Department of Computer Science,
Mathematics, Physics, and Statistics, Kelowna, BC, Canada
<EMAIL_ADDRESS>
## Abstract

Distance-based clustering and classification are widely used in various fields
to group mixed numeric and categorical data. In many algorithms, a predefined
distance measurement is used to cluster data points based on their
dissimilarity. While there exist numerous distance-based measures for data
with pure numerical attributes and several ordered and unordered categorical
metrics, an efficient and accurate distance for mixed-type data that utilizes
the continuous and discrete properties simulatenously is an open problem. Many
metrics convert numerical attributes to categorical ones or vice versa. They
handle the data points as a single attribute type or calculate a distance
between each attribute separately and add them up. We propose a metric called
KDSUM that uses mixed kernels to measure dissimilarity, with cross-validated
optimal bandwidth selection. We demonstrate that KDSUM is a shrinkage method
from existing mixed-type metrics to a uniform dissimilarity metric, and
improves clustering accuracy when utilized in existing distance-based
clustering algorithms on simulated and real-world datasets containing
continuous-only, categorical-only, and mixed-type data.

Keywords: Mixed-type data, metric learning, clustering, smoothing, kernel
methods, similarity measures

##  1 Introduction

Datasets comprising continuous, ordered, and unordered categorical data are
known as mixed-type data and are prevalent across various disciplines, and the
availability of such heterogeneous data types continues to increase. Although
several approaches have been employed to calculate the distance for mixed-type
data points, there is no broadly accepted definition of distance. The
challenge of quantifying distance is balancing the contributions of each
variable–particularly between discrete and continuous–to the overall
difference between data entries. In this paper, we develop a data-driven
distance method that estimates the importance of discrete and continuous
variables to the difference between entries using a shrinkage approach.

Many existing distances homogenize mixed-type data to single-type by
projecting all data to either discrete or continuous, through methods such as
discretization or dummy coding before calculating distance (see, for example,
Guha et al., 2000; Dougherty et al., 1995). While these distances are
computationally efficient and well-known, they can inaccurately calculate the
meaningful differences between data points and overweight variables in the
continuous or discrete domains. This overweighting can severely affect the
clustering outcome of any methodology that requires distances through a
significant loss of information on the homogenized data types.

Clustering is a fundamental technique in data analysis that involves grouping
similar data points together based on distance. When clustering mixed-type
data, choosing an appropriate distance metric that can handle the
heterogeneity of the data types and scales is crucial. The metric should
utilize and balance each data type appropriately to provide a meaningful
distance between data points that accurately represents the similarity and
dissimilarity between data points within a particular dataset. The choice of
metric can have a significant impact on the accuracy, reliability, and
interpretability of distance-based clustering results, and it is essential to
carefully consider its performance using the standard statistics of clustering
accuracy (CA) and Adjusted Rand Index (ARI) (Hubert & Arabie, 1985).

We propose a novel kernel distance for mixed-type data that balances mixed-
type data important to within-dataset similarity for clustering applications.
We prove that kernel similarity functions can be used as a distance metric and
our specific kernel distance metric (called KDSUM) is a shrinkage method
between maximized dissimilarity and uniform similarity between all points. We
demonstrate that maximum similarity cross-validation chooses optimal
bandwidths. The advantage of this method is that the importance of each
variable to similarity between data points are balanced by the magnitudes of
cross-validated bandwidths.

We apply kernel distance to agglomerative hierarchical clustering and
demonstrate the utility of our metric for clustering both simulated and real-
world datasets. We find a kernel distance almost unilaterally improves
clustering performance compared to other common mixed-type distances, such as
Gower’s distance (Gower 1971). A kernel distance provides researchers and
practitioners with a unified, robust, effective, and efficient distance for
mixed-type data, aiding in informed decision-making from the more accurately
characterized clusters. We compare KDSUM with agglomerative cluster to
competing clustering approaches. For continuous data, we compare to
hierarchical clustering techniques with standard linkage methods and
Partitioning Around Medoids with Euclidean distance, $k-$means, and Gaussian
Mixture models. For categorical data, we compare to hierarchical clustering
techniques with standard linkage methods and Partitioning Around Medoids with
Gower’s distance, $k-$modes, and Robust Clustering using links (ROCK). For
mixed-type data, we compare to hierarchical clustering techniques with
standard linkage methods and Partitioning Around Medoids with Gower’s
distance, $k-$prototypes, and model based clustering for mixed-type data
(clustMD).

The paper is structured as follows: Section 2 discusses existing homogenized
and non-homogenized approaches for mixed-type distances. Section 3 describes
the kernel methods derived from probability density estimation used in this
paper. Section 4 contains the methodology for the kernel distance metric
(KDSUM). Sections 5 and 6 describe the clustering algorithms, evaluation
metrics, and the simulated and real data. Finally, Section 7 are the
conclusions and insights for future work.

##  2 Mixed-type distances

Consider a $n\times p$ mixed-type data matrix $X$ consisting of $n$
observations with $p$ many variables that are a combination of continuous,
unordered and ordered categorical variables. Assume that the $p$ variables are
arranged such that the first continuous variables $p_{c}$ are first, followed
by unordered categorical variables $p_{u}$, and then the ordered categorical
variables $p_{o}$ such that $p=p_{c}+p_{u}+p_{o}$. For mixed-type distances,
consider that the rows of $X$ are observation vectors $\mathbf{x}_{j}$, and
the dissimilarity or distance between any two observations $\mathbf{x}_{i}$
and $\mathbf{x}_{j}$ is denoted $d(\mathbf{x}_{i},\mathbf{x}_{j})$, whereas
the similarity between the observations is denoted
$s(\mathbf{x}_{i},\mathbf{x}_{j})$.

Typical methodologies for calculating mixed-type distance require data to be
homogenized to either numerical or categorical type. Discretization is the
process of converting continuous variables into discrete categories or
intervals; an example of this is  binning  which  divides the range of a
continuous variable into intervals and assigns each observation to the
corresponding interval (Dougherty et al., 1995). For example, a person’s age
can be binned into discrete ordered categories such as "0-18", "19-30",
"31-50", and so on.

Let $\mathbf{x}_{i}$ be an observation with mixed-type variables. To calculate
distance between observations using a categorical-only metric, we first
homogenize the data using discretization. The $k^{\textup{th}}$ continuous
variable of $\mathbf{x}_{i}$ is divided into $C=\\{1,2,\ldots,c_{k}\\}$
ordered categories of disjoint intervals
$\mathcal{Z}_{1},\mathcal{Z}_{2},\ldots,\mathcal{Z}_{c_{k}}$.Then, we define
new order categorical variable such that
$\mathbf{z}_{k}=\\{z_{i,k}=c|x_{i,k}\in\mathcal{Z}_{c}\\}$ and replace each
value $x_{i,k}$ with $z_{i,k}$. Discretization is often useful in cases where
the data is highly skewed. However, it leads to a loss of information, and
choosing an optimal interval width can be challenging and affect the analysis
results.

Another method for coercing continuous data to categorical is dummy-coding
that involves representing binned categorical variables as binary (0 or 1)
variables. For each category in $C$, a corresponding binary variable is
created $x_{i,h,m}$, where the binary variable assumes value 1 if
$\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are both in category $c_{h,m}$, and 0
otherwise. The distance between any two dummy coded observations
$d(\mathbf{x}_{i},\mathbf{x}_{j})$ can be calculated using any binary distance
metric (for more information, see Choi et al., 2010). Dummy-coding has the
advantage of preserving all the information in the categorical variable and
ease of interpretation. However, such an approach increases the dimensions of
the feature space and ignores the ordered values of continuous scales. Foss et
al. (2019) illustrated the inadequacy of dummy coding, noting that the
expectation of the interval scale variable is always greater than 1, while the
expectation from the categorical is always less than 1. This means that the
choice of coding can lead to different interpretations of the data and may
affect the analysis results.

The coercion of categorical data to continuous is typically conducted through
an ordered numerical assignment such as converting Likert scale data to
numerical. Then, the differences are calculated using any continuous metric,
such as Euclidean distance. Additionally, continuous data may need to be
scaled as not to over or under weigh the contribution of individual continuous
variables, and the choice of scaling also affects distance calculations and
thus clustering performance. Hennig et al. (2015) noted that distance-based
clustering methods are not invariant to affine transformations, and Foss et
al. (2016) showed that the choice of scaling can affect clustering
performance.

Various mixed-type distance metrics do not require the homogenization or
scaling of the data. The quadratic distance proposed by Lindsay et al. (2008)
extends the chi-squared measures of distance between two distributions and
requires the choice of a nonnegative definite kernel. De Leon & Carriere
(2005) use a general mixed-data model to define the distance between two
populations of mixed unordered categorical, ordered categorical, and interval
scale data. Krzanowski (1983) proposes a distance based on Matusita’s
distance, as mixtures of these location models and generalizations are not
identifiable without further conditions on some of the parameters. Recently,
van de Welden et al., (2023) introduced a framework that allows for an
implementation of distances between observations that can be extended to many
existing distances for categorical variables. Modha and Spangler (2003)
propose a method similar to $k-$prototypes that includes estimating a suitable
weight that scales the relative contribution of the interval and categorical
variables. However, the brute-force search to cluster repeatedly for a range
of values for the weight that minimizes its objective function is
computationally exhaustive.

The metrics shown in Table 1 will be used as benchmarks for the analysis of
metrics herein. For any arbitrary variable $l$, denote $w_{i,j,l}=0$ if
variable $l$ has missing data, otherwise $w_{i,j,l}=1$. Denote
${\color[rgb]{0,0,0}\mathds{1}}_{i,j,l}\equiv\mathds{1}_{c}(x_{i,l}=x_{j,l})$
for categorical variables, where $\mathds{1}_{i,j,l}=1$ if the two
observations for the $l$th variables are the same, and $0$ otherwise. Gower’s
distance (Gower, 1971) is a common hybrid distance function that calculates
the distance between two vectors of the same length. It uses a weighted
combination of interval and categorical distances, where the categorical
distance is based on whether the categories match or not, and the interval
distance is scaled based on the range of the variable. The user-specified
weights for each variable may lead to intractable solutions and varying
results based on the data. The $k-$prototypes algorithm (Huang, 1998) utilizes
another hybrid distance technique that uses a similar approach to Gower’s
distance, except the squared Euclidean distance is used for the interval scale
variables. Unlike Gower’s distance, it does not require variable-specific
weights, but rather a single weight used for the entire categorical
contribution of the distance function. The Podani distance metric (1999)
extends Gower’s general coefficient of similarity to ordinal variables, while
the Wishart (2003) metric is similar to the Podani metric, except it makes use
of the sample standard deviation for continuous variables, rather than the
range of the continuous variables.

Metric | Definition
---|---
Gower (1971): | $d(\mathbf{x}_{i},\mathbf{x}_{j})=1-s_{i,j};$
|
$s_{i,j}=\frac{\sum_{l=1}^{p}w_{i,j,l}{\color[rgb]{0,0,0}s}_{i,j,l}}{\sum_{l=1}^{p}w_{i,j,l}}$
|
${\color[rgb]{0,0,0}s_{i,j,l}=1-\frac{|x_{i,l}-x_{j,l}|}{\max_{k}(x_{k,l})-\min_{k}(x_{k,l})}}$
Huang (1998): | $d(\mathbf{x}_{i},\mathbf{x}_{j})=\sum_{l=1}^{p_{c}}(x_{i,l}-x_{j,l})^{2}+$
|
$+\gamma\sum_{l=p_{c}+1}^{p_{u}+p_{o}}{\color[rgb]{0,0,0}\mathds{1}}_{c}(x_{i,l}=x_{j,l});$
| $\gamma=\frac{\sum_{r=1}^{p_{c}}s_{r}^{2}}{p_{c}}$
Podani (1999): | $d(\mathbf{x}_{i},\mathbf{x}_{j})=\sqrt{\sum_{l=1}^{p}w_{i,j,l}\left(\frac{x_{i,l}-x_{j,l}}{{\color[rgb]{0,0,0}s}_{i,j,l}}\right)^{2}};$
|  ${\color[rgb]{0,0,0}s}_{i,j,l}=\max_{k}(x_{k,l})-\min_{k}(x_{k,l})$ (if $l$
is continuous)
Wishart (2003): | $d(\mathbf{x}_{i},\mathbf{x}_{j})=\sqrt{\sum_{{\color[rgb]{0,0,0}r}=1}^{p}w_{i,j,{\color[rgb]{0,0,0}r}}\left(\frac{x_{i,{\color[rgb]{0,0,0}r}}-x_{j,{\color[rgb]{0,0,0}r}}}{{\color[rgb]{0,0,0}s_{r}}}\right)^{2}};$
|  ${\color[rgb]{0,0,0}s_{r}}:=$ sample standard deviation of $l$th variable
(if $l$ is continuous)
Table 1: Common mixed-type distance metrics.

##  3 Kernel Density Estimation and Bandwidth Selection Procedures

Kernel functions are weighting functions that can map data points from a high-
dimensional sample space to a low-dimensional space. Kernel functions are non-
negative real-valued functions, integrate or sum to 1, and often assumed to be
symmetric. We denote the kernel functions specific to datatypes as $K$, $L$,
and $l$ for continuous, unordered and ordered categorical variables,
respectively. For each kernel, we denote bandwidths associated with the kernel
functions as
$\bm{\lambda}\equiv\\{{\color[rgb]{0,0,0}\bm{\lambda}}^{c},{\color[rgb]{0,0,0}\bm{\lambda}}^{u},{\color[rgb]{0,0,0}\bm{\lambda}}^{o}\\}$
where
$\\{{\color[rgb]{0,0,0}\bm{\lambda}}^{c}\\}\equiv\\{\lambda_{i}\\}_{i=1}^{p_{c}},\\{{\color[rgb]{0,0,0}\bm{\lambda}}^{u}\\}\equiv\\{\lambda_{i}\\}_{i=p_{c}+1}^{p_{c}+p_{u}},$
and
$\\{{\color[rgb]{0,0,0}\bm{\lambda}}^{o}\\}\equiv\\{\lambda_{i}\\}_{i=p_{c}+p_{u}+1}^{p}$.

There exist many common kernel functions used in the smoothing literature,
such as the Gaussian kernel for continuous variables given by

$\displaystyle{\color[rgb]{0,0,0}k(x_{i},x,\lambda^{c})=\frac{1}{\sqrt{2\pi}}e^{\frac{-(x_{i}-x)^{2}}{2(\lambda^{c})^{2}}},}$
(1)

where $\lambda^{c}>0$. The Epanechnikov kernel (Epanechnikov, 1969) given by

$\displaystyle{\color[rgb]{0,0,0}k(z)=k(x_{i},x,\lambda^{c})=\frac{3}{4}\left(1-\frac{(x_{i}-x)^{2}}{(\lambda^{c})^{2}}\right){\color[rgb]{0,0,0}\mathds{1}}\left(\left|\frac{x_{i}-x}{\lambda^{c}}\right|\leq
1\right),}$ (2)

where $\lambda^{c}>0$. For unordered categorical variables, we use an Aitken
kernel (Li and Racine, 2023) given by

$\displaystyle{\color[rgb]{0,0,0}L(x_{i},x,\lambda^{u})=\begin{cases}1,&x_{i}=x,\\\
\lambda^{u},&x_{i}\neq x,\end{cases}}$ (3)

where $\lambda^{u}\in[0,1]$. For ordered categorical variables, a Wang & van
Ryzin kernel (Wang & van Ryzin, 2008) given by

$\displaystyle{\color[rgb]{0,0,0}l(x_{i},x,\lambda^{o})=\begin{cases}1-\lambda^{o},&x_{i}=x,\\\
\frac{1}{2}\left(1-\lambda^{o}\right)\left(\lambda^{o}\right)^{|X_{i}-x|},&x_{i}\neq
x,\end{cases}}$ (4)

where $\lambda^{o}\in[0,1]$. A mixed-type joint kernel function between a
random vector
$\mathbf{x}_{j}\equiv\\{\mathbf{x}_{j}^{c},\mathbf{x}_{j}^{u},\mathbf{x}_{j}^{o}\\}$
and an arbitrary point $\mathbf{x}$ is written as

${\color[rgb]{0,0,0}K}(\mathbf{x}_{i},\mathbf{x})=\prod_{k=1}^{p_{c}}\frac{1}{\lambda_{k}}k\left(\frac{{\color[rgb]{0,0,0}x_{i,k}}^{c}-x_{k}^{c}}{\lambda_{k}}\right)\prod_{k={\color[rgb]{0,0,0}p_{c}+}1}^{{\color[rgb]{0,0,0}p_{c}+p_{u}}}L\left(x_{i,k}^{u},{\color[rgb]{0,0,0}x}_{k}^{u},\lambda_{k}\right)\times\cdots\times\prod_{k={\color[rgb]{0,0,0}p_{c}+p_{u}+1}}^{{\color[rgb]{0,0,0}p}}l\left(x_{i,k}^{o},{\color[rgb]{0,0,0}x}_{k}^{o},\lambda_{k}\right).$
(5)

These kernel functions can be used for probability density estimation, such as
the Rozenblatt-Parzen density estimator ([53, 47])
$\widehat{p}(\mathbf{x})=\frac{1}{n\lambda_{1}\lambda_{2}\cdots\lambda_{p_{c}}}\sum_{i=1}^{n}K(\mathbf{x}_{i},\mathbf{x})$
converges in probability to the underlying density function $p(x)$ under the
assumption that as $n\to\infty$, then $\bm{\lambda}\to\mathbf{0}$ and
$n\lambda_{1}\lambda_{2}\cdots\lambda_{p_{c}}\to\infty$. Optimal bandwidth
selection methods are designed to preserve estimator convergence while having
several other desirable properties, including smoothing out irrelevant
variables (Loader, 1999). There is a wide range of methods for optimal
bandwidth selection, including Akaike Information Criterion (Hurvich et al.,
1998), Least Squares Cross-Validation (Sain et al., 1994), Rule of Thumb
(Silverman, 1986), and Maximum-Likelihood Cross-Validation (MLCV) (Hall 1981).
The MLCV objective function to be minimized is

$\displaystyle
CV(\bm{\lambda})=\sum_{i=1}^{n}\ln\left(\frac{1}{(n-1)}\sum_{j=1,j\neq
i}^{n}\mathcal{L}_{\bm{\lambda}}(x_{i,k},x_{j,k})\right)=\sum_{i=1}^{n}\ln\left(\hat{\mathcal{L}}_{-i}(x_{i})\right),$
(6)

where $\hat{\mathcal{L}}_{-i}(x_{i})$ is the leave-one-out estimator of
$\mathcal{L}_{\bm{\lambda}}(\cdot)$ in Equation (5). These kernels and cross-
validation approaches can be adapted to similarity functions, which are used
for the kernel distance metric in this paper.

##  4 Similarity Functions and Mixed-type Kernel Distances

Consider a real-valued function
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})$
on the Cartesian product $X\times X$. $\mathcal{L}$ is a similarity function
if, for any points
$\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}}\in
X$, it satisfies four conditions (Chen et al., 2009):

  * (S1)

Symmetry:
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})$,

  * (S2)

Indiscernible:
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})\iff\mathbf{x}_{{\color[rgb]{0,0,0}i}}=\mathbf{x}_{{\color[rgb]{0,0,0}j}}$,

  * (S3)

Nonnegative self-similarity:
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})\geq\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})\geq
0$,

  * (S4)

Similarity triangle inequality:
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})\leq\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})$.

Let $\mathcal{L}(\cdot)$ be a similarity function that maps two
$p$-dimensional data vectors to the real numbers with the additional property
that as the difference between two observations $\mathbf{x}_{i}$ and
$\mathbf{x}_{j}$ increases, $\mathcal{L}(\mathbf{x}_{i},\mathbf{x}_{j})$
decreases.

The definition of norm and distance between two vectors is defined by the
choice of kernel similarity function. For example, a Euclidean norm is
positive, definite, and symmetric, and yields the similarity function
$\mathcal{L}_{L_{2}}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=1-\sum_{k=1}^{p}(x_{i,k}-x_{j,k})^{2}$.
The Gaussian kernel function defined in Equation (1) can be written in terms
of a non-linear transformation of $\mathcal{L}_{L_{2}}$ as
$\mathcal{L}_{gauss}(x_{i},x_{j}):=k\left(\frac{x_{i}-x_{j}}{\lambda_{k}}\right)=\frac{1}{\sqrt{2\pi}}\mbox{exp}\left(-\frac{1}{2}\left(\frac{x_{i}-x_{j}}{\lambda_{k}}\right)^{2}\right)$.
Each of these kernels satisfy the necessary conditions of positive, definite
and symmetric kernel functions ([2]) and satisfy the properties (S1)-(S4) to
be similarity functions (Joshi et al., 2011; Phillips & Venkatasubramanian,
2011; Jäkel et al., 2008). The Epanechnikov kernel function in Equation (2)
can be viewed as a scaled and truncated version of $\mathcal{L}_{L_{2}}$ by
using $z=\frac{x_{i,k}-x_{j,k}}{h}$. As an example for continuous kernels, we
show that the Gaussian is a similarity functions.

Lemma 1: The Gaussian kernel is a similarity function.
Proof: We demonstrate that the Gaussian kernel
$k(x_{i},x_{j},\lambda^{c})=\frac{1}{\sqrt{2\pi}}e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}$
satisfies properties (S1)-(S4) of a similarity function
$\forall\>\lambda^{c}>0$.
(S1): Since $(x_{i}-x_{j})^{2}=(x_{j}-x_{i})^{2}$, then
$k(x_{i},x_{j},\lambda^{c})=k(x_{j},x_{i},\lambda^{c})$.
(S2): ($\Rightarrow$) Let
$k(x_{i},x_{j},\lambda^{c})=k(x_{i},x_{i},\lambda^{c})=k(x_{j},x_{j},\lambda^{c})=\frac{1}{\sqrt{2\pi}}$
but assume that $x_{i}\neq x_{j}$. Considering that
$k(x_{i},x_{i},\lambda^{c})$, then
$k(x_{j},x_{j},\lambda^{c})=\frac{1}{\sqrt{2\pi}}$ which implies
$(x_{i}-x_{j})^{2}=0$. However, $(x_{i}-x_{j})^{2}>0$ by the assumption
$x_{i}\neq x_{j}$ which is a contradiction. Thus,
$k(x_{i},x_{j},\lambda^{c})=k(x_{i},x_{i},\lambda^{c})=k(x_{j},x_{j},\lambda^{c})=\frac{1}{\sqrt{2\pi}}\Rightarrow
x_{i}=x_{j}$. ($\Leftarrow$) Let $x_{i}=x_{j}$, then by (S1)
$k(x_{i},x_{j},\lambda^{c})=k(x_{i},x_{i},\lambda^{c})=k(x_{j},x_{j},\lambda^{c})=\frac{1}{\sqrt{2\pi}}$.
(S3): First, $k(x_{i},x_{i},\lambda^{c})=\frac{1}{\sqrt{2\pi}}>0$. Assuming
$x_{i}\neq x_{j}$, then $\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}<0$ and
$e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}<1$, and
$k(x_{i},x_{i},\lambda^{c})>k(x_{i},x_{j},\lambda^{c})$. If $x_{i}=x_{j}$,
then by (S2) $k(x_{i},x_{i},\lambda^{c})=k(x_{i},x_{j},\lambda^{c})$. Thus,
$k(x_{i},x_{i},\lambda^{c})\geq k(x_{i},x_{j},\lambda^{c})\geq 0$.
(S4): If either $x_{i}=x_{j}$ or $x_{j}=x_{k}$, then the inequality holds by
(S1)-(S3). Consider the case when $x_{i}\neq x_{j}$ and $x_{j}\neq x_{k}$. The
Euclidean norm triangle inequality gives

$\displaystyle(x_{i}-x_{k})^{2}\leq(x_{i}-x_{j})^{2}+(x_{j}-x_{k})^{2},$
$\displaystyle\implies$ $\displaystyle
2-\left(\frac{1}{2(\lambda^{c})^{2}}(x_{i}-x_{j})^{2}+\frac{1}{2(\lambda^{c})^{2}}(x_{j}-x_{k})^{2}\right)\leq
2-\frac{1}{2(\lambda^{c})^{2}}(x_{i}-x_{k})^{2}$ (7)

Consider $e^{-x}\geq 1-x$, thus
$e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}\geq
1-\frac{1}{2(\lambda^{c})^{2}}(x_{i}-x_{j})^{2}$. Using this inequality gives

$\displaystyle
e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}+e^{\frac{-(x_{j}-x_{k})^{2}}{2(\lambda^{c})^{2}}}\geq
2-\left(\frac{1}{2(\lambda^{c})^{2}}(x_{i}-x_{j})^{2}+\frac{1}{2(\lambda^{c})^{2}}(x_{j}-x_{k})^{2}\right)$
(8)

and

$\displaystyle 1+e^{\frac{-(x_{i}-x_{k})^{2}}{2(\lambda^{c})^{2}}}\geq
2-\frac{1}{2(\lambda^{c})^{2}}(x_{i}-x_{k})^{2}$ (9)

Inserting Equations (8) and (9) into (7) yields

$\displaystyle
e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}+e^{\frac{-(x_{j}-x_{k})^{2}}{2(\lambda^{c})^{2}}}\leq
e^{\frac{-(x_{i}-x_{k})^{2}}{2(\lambda^{c})^{2}}}+1$ $\displaystyle\implies$
$\displaystyle\frac{1}{\sqrt{2\pi}}e^{\frac{-(x_{i}-x_{j})^{2}}{2(\lambda^{c})^{2}}}+\frac{1}{\sqrt{2\pi}}e^{\frac{-(x_{j}-x_{k})^{2}}{2(\lambda^{c})^{2}}}\leq\frac{1}{\sqrt{2\pi}}e^{\frac{-(x_{i}-x_{k})^{2}}{2(\lambda^{c})^{2}}}+\frac{1}{\sqrt{2\pi}}$
$\displaystyle\implies$ $\displaystyle
k(x_{i},x_{j},\lambda^{c})+k(x_{j},x_{k},\lambda^{c})\leq
k(x_{i},x_{k},\lambda^{c})+k(x_{j},x_{j},\lambda^{c})$

which is (S4) and thus the Gaussian kernel is a similarity function. $\square$
Similar arguments can be made to show that an Epanechnikov kernel function is
a similarity function, which we omit for brevity. For categorical kernels,
there is far less literature support for their usage as similarity functions.
We show that Equations (3) and (4) are similarity functions. Lemma 2: The
Aitken unordered kernel is a similarity function.
Proof: We demonstrate that the Aitken Kernel satisfies all properties of a
similarity function (S1)-(S4). (S1): By the definition of symmetry for this
kernel function, (S1) is satisfied.
(S2): Suppose
$L(x_{i},x_{j},\lambda^{u})=L(x_{i},x_{i},\lambda^{u})=L(x_{j},x_{j},\lambda^{u})$.
Then $k(\cdot)=1$, by definition. Conversely, if $x_{i}=x_{j}$, then
$L(x_{i},x_{j},\lambda^{u})=L(x_{i},x_{i},\lambda^{u})=L(x_{j},x_{j},\lambda^{u})=1$.
(S3): First, $L(x_{i},x_{i},\lambda^{u})=1\geq 0$. Then,
$L(x_{i},x_{j},\lambda^{u})=\lambda^{u}\leq 1$, based on the bounds of
$\lambda^{u}$. Thus, $L(x_{i},x_{i},\lambda^{u})\geq
L(x_{i},x_{j},\lambda^{u})\geq 0$.
(S4): If $x_{i}=x_{j}$ or $x_{j}=x_{k}$, the result is trivial. Assume
$x_{i}\neq x_{j}$ and $x_{j}\neq x_{k}$. Then,

$\displaystyle L(x_{i},x_{j},\lambda^{u})+L(x_{j},x_{k},\lambda^{u})$
$\displaystyle\leq L(x_{i},x_{k},\lambda^{u})+L(x_{j},x_{j},\lambda^{u})$
$\displaystyle\implies\lambda^{u}+\lambda^{u}$
$\displaystyle\leq\lambda^{u}+1$ $\displaystyle\implies\lambda^{u}$
$\displaystyle\leq 1,$

which is true based on the bounds of $\lambda^{u}$. $\square$

Lemma 3: The Wang & van Ryzin ordered kernel is a similarity function.
Proof: We demonstrate that the Wang & van Ryzin Kernel satisfies all
properties of a similarity function (S1)-(S4). By definition, (S1) and (S2)
are satisfied.
(S3): First, $l(x_{i},x_{i},\lambda^{o})=1-\lambda^{o}\in[0,1]$. Then,
$l(x_{i},x_{j},\lambda^{o})=\frac{1}{2}(1-\lambda^{o})(\lambda^{o})^{|x_{i}-x_{j}|}$.
To show
$1-\lambda^{o}\geq\frac{1}{2}(1-\lambda^{o})(\lambda^{o})^{|x_{i}-x_{j}|}$,
divide both sides by $1-\lambda^{o}$ to see
$1\geq\frac{1}{2}(\lambda^{o})^{|x_{i}-x_{j}|}$ (note that we can divide by
$1-\lambda^{o}$, since if $\lambda^{o}=1$, we have $0\geq 0$ which holds).
Since $|x_{i}-x_{j}|$ is a positive integer, and since $\lambda^{o}\in[0,1]$,
$(\lambda^{o})^{|x_{i}-x_{j}|}\in[0,1]$, and the inequality follows.
(S4): If $x_{i}=x_{j}$ or $x_{j}=x_{k}$, the result is trivial. Assume
$x_{i}\neq x_{j}$ and $x_{j}\neq x_{k}$. Then,

$\displaystyle l(x_{i},x_{j},\lambda^{o})+l(x_{j},x_{k},\lambda^{o})$
$\displaystyle\leq l(x_{i},x_{k},\lambda^{o})+l(x_{j},x_{j},\lambda^{o})$
$\displaystyle\implies\frac{1}{2}(1-\lambda^{o})(\lambda^{o})^{|x_{i}-x_{j}|}+\frac{1}{2}(1-\lambda^{o})(\lambda^{o})^{|x_{j}-x_{k}|}$
$\displaystyle\leq\frac{1}{2}(1-\lambda^{o})(\lambda^{o})^{|x_{i}-x_{k}|}+(1-\lambda^{o})$
$\displaystyle\implies\frac{1}{2}\left((\lambda^{o})^{|x_{i}-x_{j}|}+(\lambda^{o})^{|x_{j}-x_{k}|}\right)$
$\displaystyle\leq\frac{1}{2}(\lambda^{o})^{|x_{i}-x_{k}|}+1.$

Now,
$\frac{1}{2}\left((\lambda^{o})^{|x_{i}-x_{j}|}+(\lambda^{o})^{|x_{j}-x_{k}|}\right)\leq\max\left\\{(\lambda^{o})^{|x_{i}-x_{j}|},(\lambda^{o})^{|x_{j}-x_{k}|}\right\\}$,
so it will be sufficient to show

$\max\left\\{(\lambda^{o})^{|x_{i}-x_{j}|},(\lambda^{o})^{|x_{j}-x_{k}|}\right\\}\leq\frac{1}{2}(\lambda^{o})^{|x_{i}-x_{k}|}+1.$

If $|x_{i}-x_{j}|\leq|x_{j}-x_{k}|$, then
$\max\left\\{(\lambda^{o})^{|x_{i}-x_{j}|},(\lambda^{o})^{|x_{j}-x_{k}|}\right\\}=(\lambda^{o})^{|x_{j}-x_{k}|}$,
so we show
$(\lambda^{o})^{|x_{j}-x_{k}|}\leq\frac{1}{2}(\lambda^{o})^{|x_{i}-x_{k}|}+1$,
which is clear since $(\lambda^{o})^{|x_{i}-x_{k}|}\in[0,1]$. A similar
argument holds if $|x_{i}-x_{j}|>|x_{j}-x_{k}|$, and the result follows
immediately. $\square$

To transform kernel similarities into distances, we extend the metric
described in Phillips and Venkatasubramanian (2011) to the multivariate
setting, which uses a well-defined kernel function to measure similarity
between points $\mathbf{x}_{{\color[rgb]{0,0,0}i}}$ and
$\mathbf{x}_{{\color[rgb]{0,0,0}j}}$. The distance between
$\mathbf{x}_{{\color[rgb]{0,0,0}i}}$ and $\mathbf{x}_{{\color[rgb]{0,0,0}j}}$
is then defined as

$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}}).$
(10)

If a symmetric kernel function is elected, the formula reduces to
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-2\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})$.
Equation (10) represents the difference between the self-similarities of the
two points and their cross-similarity. The multiplicative factor of two
ensures that the distance between an object and itself equals zero and
satisfies the identity of indiscernibles.

Theorem 1: Equation (10) that satisfies (S1)-(S4) is a well-defined distance
metric where it satisfies the following distant metric properties (Chen et
al., 2009):
Proof: (D1) Nonnegativity
($d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})\geq
0)$: note by (S3) that
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})\geq
0$ and
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})\geq
0$. Adding yields
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})\geq
0$ and thus,
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})\geq
0$.

(D2) Symmetry
($d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=d(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})$):
note
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=d(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})$

(D3) Identity of indescernibles
($d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=0\iff\mathbf{x}_{{\color[rgb]{0,0,0}i}}=\mathbf{x}_{{\color[rgb]{0,0,0}j}}$):
suppose that
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=0$,
thus
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=0$,
implying
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})$
which is true if and only if
$\mathbf{x}_{{\color[rgb]{0,0,0}i}}=\mathbf{x}_{{\color[rgb]{0,0,0}j}}$ or
$\mathbf{x}_{{\color[rgb]{0,0,0}j}}=\mathbf{x}_{{\color[rgb]{0,0,0}i}}$ by
(S2). Conversely, suppose
$\mathbf{x}_{{\color[rgb]{0,0,0}j}}=\mathbf{x}_{{\color[rgb]{0,0,0}i}}$, then
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=2\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-2\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})=0$

(D4) Triangle inequality
($d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})\leq
d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+d(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})$):
note by (S4) that
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})\leq\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})$,
and
$\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})\leq\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})$.
Then,
$d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})=\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})\leq\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}i}})-\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}k}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+\mathcal{L}(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})=d(\mathbf{x}_{{\color[rgb]{0,0,0}i}},\mathbf{x}_{{\color[rgb]{0,0,0}j}})+d(\mathbf{x}_{{\color[rgb]{0,0,0}j}},\mathbf{x}_{{\color[rgb]{0,0,0}k}})$
$\square$

###  4.1 KDSUM: Kernel Dissimilarity Metric for Mixed-Type Data

The pairwise similarity between two observations $\mathbf{x}_{i}$ and
$\mathbf{x}_{j}$ is

$\displaystyle\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})=\prod_{k=1}^{p_{c}}\frac{1}{\lambda_{k}}k\left(\frac{x_{i,k}-x_{j,k}}{\lambda_{k}}\right)+\sum_{k=p_{c}+1}^{p_{u}}L(x_{i,k},x_{j,k},\lambda_{k})+\sum_{k={\color[rgb]{0,0,0}p_{c}+}p_{u}+1}^{p}l(x_{i,k},x_{j,k},\lambda_{k}).$
(11)

Using the positive, definite, symmetric kernel functions defined in Section 3,
$\psi(\cdot)$ satisfies the similarity properties (S1)-(S4) and is a
similarity function, thus we can set $\mathcal{L}(\cdot):=\psi(\cdot)$. We
demonstrate that the sum of two similarity functions satisfies the rules
(S1)-(S4) of being a similarity function, which can be extended to any number
of sums of similarity functions. The results are similar for the product of
similarity functions. We also note that since our similarity functions are
kernel functions, the sum and product of multiple kernel functions is also a
kernel function (see Bishop, 2006, pp 296).

Lemma 4: The sum of similarity functions are also similarity functions

Proof: Let
$\mathcal{L}^{(n)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n)}(x_{i},x_{j})+\ldots+\mathcal{L}_{n}^{(n)}(x_{1},x_{2})$
be the sum of $(n)$ similarity functions. We show each of the properties
(S1)-(S4) through induction or directly:
(S1): For the base case,
$\mathcal{L}^{(2)}(x_{i},x_{j})=\mathcal{L}_{1}^{(2)}(x_{i},x_{j})+\mathcal{L}_{2}^{(2)}(x_{i},x_{j})=\mathcal{L}_{1}^{(2)}(x_{j},x_{i})+\mathcal{L}_{2}^{(2)}(x_{j},x_{i})=\mathcal{L}^{(2)}(x_{j},x_{i})$.
Then, assuming
$\mathcal{L}^{(n)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n)}(x_{i},x_{j})+\ldots+\mathcal{L}_{n}^{(n)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n)}(x_{j},x_{i})+\ldots+\mathcal{L}_{n}^{(n)}(x_{j},x_{i})=\mathcal{L}^{(n)}(x_{j},x_{i})$
is true, we have
$\mathcal{L}^{(n+1)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n+1)}(x_{i},x_{j})+\ldots+\mathcal{L}_{n}^{(n)}(x_{i},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n+1)}(x_{j},x_{i})+\ldots+\mathcal{L}_{n}^{(n)}(x_{j},x_{i})+\mathcal{L}_{n+1}^{(n+1)}(x_{j},x_{i})=\mathcal{L}^{(n+1)}(x_{j},x_{i})$
(S2): If $x_{i}=x_{j}$, then their self-similarity values are maximum, and the
similarity values between them is also maximum:

$\displaystyle\mathcal{L}^{(n)}(x_{i},x_{i})$ $\displaystyle=\text{maximum
self-similarity value for the sum of $n$ similarity functions}$
$\displaystyle\mathcal{L}^{(n)}(x_{i},x_{j})$ $\displaystyle=\text{similarity
value between }x_{i}\text{ and }x_{j}\text{ or the sum of $n$ similarity
functions}$ $\displaystyle\mathcal{L}{(n)}(x_{j},x_{j})$
$\displaystyle=\text{maximum self-similarity value for the sum of $n$
similarity functions}$

Since both $\mathcal{L}^{(n)}(x_{i},x_{i})$ and
$\mathcal{L}^{(n)}(x_{j},x_{j})$ are maximum values, and the only way for
$\mathcal{L}^{(n)}(x_{i},x_{j})$ to be the same as both
$\mathcal{L}^{(n)}(x_{i},x_{i})$ and $\mathcal{L}^{(n)}(x_{j},x_{j})$ is if
$x_{i}=x_{j}$. Conversely, if $x_{i}\neq x_{j}$, then their self-similarity
values are not maximum, and the similarity value between them should be less
than the self-similarity values:

$\displaystyle\mathcal{L}^{(n)}(x_{i},x_{i})$ $\displaystyle=\text{self-
similarity value of }x_{i}\text{ for the sum of $n$ similarity functions (not
maximum)}$ $\displaystyle\mathcal{L}^{(n)}(x_{i},x_{j})$
$\displaystyle=\text{similarity value between }x_{i}\text{ and }x_{j}\text{
for the sum of $n$ similarity functions}$
$\displaystyle\mathcal{L}^{(n)}(x_{j},x_{j})$ $\displaystyle=\text{self-
similarity value of }x_{j}\text{ for the sum of $n$ similarity functions (not
maximum)}$

Since $\mathcal{L}^{(n)}(x_{i},x_{i})\neq\mathcal{L}^{(n)}(x_{i},x_{j})$, and
$\mathcal{L}^{(n)}(x_{j},x_{j})\neq\mathcal{L}^{(n)}(x_{i},x_{j})$, the only
way for $\mathcal{L}^{(n)}(x_{i},x_{j})$ to be the same as both
$\mathcal{L}^{(n)}(x_{i},x_{i})$ and $\mathcal{L}^{(n)}(x_{j},x_{j})$ is if
$x_{i}=x_{j}$. In both cases, the property holds.
(S3): For the base case, since based on properties of similarity,
$\mathcal{L}_{1}^{(2)}(x_{i},x_{i})\geq\mathcal{L}_{1}^{(2)}(x_{i},x_{j})\geq
0$ and
$\mathcal{L}_{2}^{(2)}(x_{i},x_{i})\geq\mathcal{L}_{2}^{(2)}(x_{i},x_{j})\geq
0$, then
$\mathcal{L}_{1}^{(2)}(x_{i},x_{i})+\mathcal{L}_{2}^{(2)}(x_{i},x_{i})\geq\mathcal{L}_{1}^{(2)}(x_{i},x_{j})+\mathcal{L}_{2}^{(2)}(x_{i},x_{j})\geq
0+0$, and thus
$\mathcal{L}^{(2)}(x_{i},x_{i})\geq\mathcal{L}^{(2)}(x_{i},x_{j})\geq 0$.
Now, assuming
$\mathcal{L}^{(n)}(x_{i},x_{i})\geq\mathcal{L}^{(n)}(x_{i},x_{j})\geq 0$, we
note
$\mathcal{L}_{k}^{(n+1)}(x_{i},x_{i})\geq\mathcal{L}_{k}^{(n+1)}(x_{i},x_{j})\geq
0$ for all $k\in\\{1,2,\ldots,n+1\\}$. Adding these $k$ sets of inequalities,
and using our inductive hypothesis
$\mathcal{L}^{(n+1)}(x_{i},x_{i})=\mathcal{L}_{1}^{(n+1)}(x_{i},x_{i})+\ldots+\mathcal{L}_{n}^{(n+1)}(x_{i},x_{i})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{i})\geq\mathcal{L}_{1}^{(n+1)}(x_{i},x_{j})+\ldots+\mathcal{L}_{n}^{(n+1)}(x_{i},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{j})=\mathcal{L}^{(n+1)}(x_{i},x_{j})$
and
$\mathcal{L}^{(n+1)}(x_{i},x_{j})=\mathcal{L}_{1}^{(n+1)}(x_{i},x_{j})+\ldots+\mathcal{L}_{n}^{(n+1)}(x_{i},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{j})\geq(n+1)\times
0$.
(S4): For the base case, since based on properties of similarity,
$\mathcal{L}_{1}^{(2)}(x_{i},x_{j})+\mathcal{L}_{1}^{(2)}(x_{j},x_{k})\leq\mathcal{L}_{1}^{(2)}(x_{i},x_{k})+\mathcal{L}_{1}^{(2)}(x_{j},x_{j})$,
and
$\mathcal{L}_{2}^{(2)}(x_{i},x_{j})+\mathcal{L}_{2}^{(2)}(x_{j},x_{k})\leq\mathcal{L}_{2}^{(2)}(x_{i},x_{k})+\mathcal{L}_{2}^{(2)}(x_{j},x_{j})$,
then
$\mathcal{L}_{1}^{(2)}(x_{i},x_{j})+\mathcal{L}_{1}^{(2)}(x_{j},x_{k})+\mathcal{L}_{2}^{(2)}(x_{i},x_{j})+\mathcal{L}_{2}^{(2)}(x_{j},x_{k})\leq\mathcal{L}_{1}^{(2)}(x_{i},x_{k})+\mathcal{L}_{1}^{(2)}(x_{j},x_{j})+\mathcal{L}_{2}^{(2)}(x_{i},x_{k})+\mathcal{L}_{2}^{(2)}(x_{j},x_{j})$,
which implies
$\mathcal{L}^{(2)}(x_{i},x_{j})+\mathcal{L}^{(2)}(x_{j},x_{k})\leq\mathcal{L}^{(2)}(x_{i},x_{k})+\mathcal{L}^{(2)}(x_{j},x_{j})$.
Now, assuming
$\sum_{N=1}^{n}\mathcal{L}_{N}^{(n)}(x_{i},x_{j})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n)}(x_{j},x_{k})\leq\sum_{N=1}^{n}\mathcal{L}_{N}^{(n)}(x_{i},x_{k})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n)}(x_{j},x_{j})$,
then

$\displaystyle\mathcal{L}^{(n+1)}(x_{i},x_{j})+\mathcal{L}^{(n+1)}(x_{j},x_{k})$
$\displaystyle=\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{i},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{j})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{j},x_{k})+\mathcal{L}_{n+1}^{(n+1)}(x_{j},x_{k})$
$\displaystyle\leq\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{i},x_{k})+\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{k})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{j},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{j},x_{j})$
$\displaystyle=\mathcal{L}^{(n+1)}(x_{i},x_{k})+\mathcal{L}^{(n+1)}(x_{j},x_{j}),$

which holds true by the inductive hypothesis
$\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{i},x_{j})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{j},x_{k})+\leq\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{i},x_{k})+\sum_{N=1}^{n}\mathcal{L}_{N}^{(n+1)}(x_{j},x_{j})$
and since
$\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{j})+\mathcal{L}_{n+1}^{(n+1)}(x_{j},x_{k})\leq\mathcal{L}_{n+1}^{(n+1)}(x_{i},x_{k})+\mathcal{L}_{n+1}^{(n+1)}(x_{j},x_{j})$
$\square$

Combining the similarity properties (S1)-(S4) and adapting the kernel distance
described by Phillips and Venkatasubramanian (2011) to the multivariate
setting, we define the kernel distance summation (KDSUM) metric between any
two data points $\mathbf{x}_{i}$, $\mathbf{x}_{j}$ of the dataset $X$ as

$d(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})=\psi(\mathbf{x}_{i},\mathbf{x}_{i}|\bm{\lambda})+\psi(\mathbf{x}_{j},\mathbf{x}_{j}|\bm{\lambda})-2\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda}).$
(12)

where
$d(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})=2\left(\psi(\mathbf{x}_{i},\mathbf{x}_{i}|\bm{\lambda})-\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})\right)$
as $\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})$ is symmetric.
Investigating the KDSUM metric asymptotics reveals that the bandwidth
selection methodology described above is a shrinkage methodology between
maximized dissimilarity and a fixed quantity of uniform dissimilarity between
all points. To see KDSUM as a shrinkage method, consider that when
$\mathbf{x_{i}}=\mathbf{x_{j}}$, then
$\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})$ is maximized and
$d(\mathbf{x}_{i},\mathbf{x}_{j})=0$ at any value of $\bm{\lambda}$. Consider
for continuous kernel types that:

$\displaystyle{\color[rgb]{0,0,0}\lim_{\lambda_{k}\to
0}\frac{1}{\lambda_{k}}k\left(\frac{x_{i,k}-x_{j,k}}{\lambda_{k}}\right)=\left\\{\begin{matrix}\infty,&x_{i,k}=x_{j,k},\\\
0,&x_{i,k}\neq x_{j,k},\end{matrix}\right.}$
$\displaystyle{\color[rgb]{0,0,0}\lim_{\lambda_{k}\to\infty}\frac{1}{\lambda_{k}}k\left(\frac{x_{i,k}-x_{j,k}}{\lambda_{k}}\right)=0,\>\forall\>x_{i,k},x_{j,k}.}$

where $x_{i,k},x_{i,k}\in(-\infty,\infty)$. For the Aitken unordered kernel in
Equation (3) with bandwidth support $\lambda_{k}=\left[0,1\right]$, then
$L(x_{i,k},x_{j,k},0)=\mathds{1}(x_{i,k}=x_{j,k})$ and
$L\left(x_{i,k},x_{j,k},1\right)=1$. For the Wang & Van Ryzin ordered kernel
in Equation (4) with bandwidth support $\lambda_{k}\in[0,1]$, then
$l(x_{i,k},x_{j,k},0)={\color[rgb]{0,0,0}\mathds{1}}(x_{i,k}=x_{j,k})$ and
$l(x_{i,k},x_{j,k},1)=0$. Thus, the asymptotics for
$d(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})$ when $x_{i,k}\neq
x_{j,k},\>\forall\>k$ are:

$\displaystyle{\color[rgb]{0,0,0}\lim_{\bm{\lambda}\to\mathbf{0}}d(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})=2\left(\prod_{k=1}^{p_{c}}\infty+\sum_{k=p_{c}+1}^{p_{u}}1+\sum_{k={\color[rgb]{0,0,0}p_{c}+}p_{u}+1}^{p}1-\prod_{k=1}^{p_{c}}0+\sum_{k=p_{c}+1}^{p_{u}}0+\sum_{k={\color[rgb]{0,0,0}p_{c}+}p_{u}+1}^{p}0\right)=\infty,}$

where the distance is clearly maximized. Alternatively, when all bandwidths
are large
$\mathbf{\lambda}_{\infty}=\left(\infty,\infty,\ldots,\infty,\frac{g_{1}-1}{g_{2}},\frac{g_{1}-1}{g_{2}},\ldots,\frac{g_{p_{u}}-1}{g_{p_{u}}},1,1,\ldots,1\right)$,
we find that

$\displaystyle{\color[rgb]{0,0,0}\lim_{\bm{\lambda}\to\mathbf{\lambda}_{\infty}}d(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})=2\left(\prod_{k=1}^{p_{c}}0+\sum_{k=p_{c}+1}^{p_{u}}0+\sum_{k={\color[rgb]{0,0,0}p_{c}+}p_{u}+1}^{p}0-\prod_{k=1}^{p_{c}}0+\sum_{k=p_{c}+1}^{p_{u}}0+\sum_{k={\color[rgb]{0,0,0}p_{c}+}p_{u}+1}^{p}0\right)=0,}$

where all distances are equal to zero. Thus, this methodology is a shrinkage
method between maximized differences and zero difference, depending on the
choice of bandwidth. To select bandwidths, we employ a maximized similarity
cross-validation (MSCV) approach similar to maximum likelihood cross-
validation (MLCV) (Stone, 1974; Geisser, 1975). The main difference is that we
replace the leave-one-out likelihood function
$\mathcal{L}_{(-1)}(\mathbf{x}_{i})$ with the leave-one-out similarity
function
$\psi_{(-1)}(\mathbf{x}_{i}|\bm{\lambda})=\frac{1}{n-1}\sum_{j=1,j\neq
i}^{n}\psi(\mathbf{x}_{i},\mathbf{x}_{j}|\bm{\lambda})$ yielding
$CV(\bm{\lambda})=\sum_{i=1}^{n}\ln\left(\psi_{(-i)}(\mathbf{x}_{i}|\bm{\lambda})\right).$
The advantage of this methodology is that we are minimizing the dissimilarity
between data points for continuous and categorical variables simultaneously,
which allows for the clustering of similar points, while smoothing out
irrelevant variables not important for similarity or clustering.

The algorithm to calculate the KDSUM metric is:

Algorithm 1 KDSUM

1:Given a dataset $X$, reorder as  continuous, unordered categorical, then
ordered categorical, and ensure that the variables are casted accordingly.

2:Select symmetric kernel functions $K,L,l$ from Equations (1)-(4), or any
symmetric kernels of choice.

3:Calculate optimal bandwidths for each $p_{i}$ using cross-validation
procedure outlined in Section 3.

4:i. Define $\psi_{-i}\textbf{x}_{i},\textbf{x}_{j},\bm{\lambda})$, which is
the updated leave-one-out pairwise similarity defined in Equation (11)
replacing $\mathcal{L}_{-i}$ in Equation (6), ensuring the kernels selected in
Step 2 are consistent.

5:ii. Optimize the function in Equation (6) to obtain the optimal bandwidths
$\bm{\lambda}$. To do a leave-one-out on $\psi_{-i}(\cdot)$, remove one
observation at a time and use the average to obtain $\bm{\hat{\lambda}}$.
Optimization is achieved through quadratic optimization subject to the
bandwidth range constraints.

6:iii. The obtained $\bm{\hat{\lambda}}$ is considered the optimal bandwidth,
and is the vector of minimal parameters to maximize the separation of
observations for each variable.

7:Calculate the pairwise distance between all observations $\mathbf{x}_{i}$
and $\mathbf{x}_{j}$ using Equation (12) and the selected kernels in Step 2,
with optimal bandwidth from Step 3, to obtain the $n\times n$ dissimilarity
matrix.

Consider the following toy example of a simulated mixed-type data matrix to
illustrate how distances are smoothed through bandwidth selection:

$X=\blockarray{cccc}&p_{c_{1}}p_{u_{1}}p_{o_{1}}\\\
\block{c(ccc)}\mathbf{x}_{1}1.513\\\ \mathbf{x}_{2}1.513\\\
\mathbf{x}_{3}1.500\\\ \mathbf{x}_{4}010\\\ \mathbf{x}_{5}003\\\ \>.$

The columns are the continuous $p_{c_{1}}$, unordered $p_{u_{1}}$, and order
$p_{o_{1}}$ variables.  The observered vectors $\mathbf{x}_{1}$ and
$\mathbf{x}_{2}$ are identical and thus the distance between them is assigned
0. The vectors $\mathbf{x}_{3}$, $\mathbf{x}_{4}$, and $\mathbf{x}_{5}$ each
contain one value in common with both $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$
but the rest of the observations are 0, and the variables in common between
$\mathbf{x}_{3}$, $\mathbf{x}_{4}$, and $\mathbf{x}_{5}$ and $\mathbf{x}_{1}$
and $\mathbf{x}_{2}$ are different for each vector.

Consider three cases for the bandwidth vectors: (1) A specified small
bandwidth vector  $\bm{\lambda}_{1}=[0.01,0,0]$, (2) a specified large
bandwidth vector $\bm{\lambda}_{2}=[10,1,1]$, and bandwidths selected using
maximum similarity cross-validation $\bm{\lambda}_{3}=[1.027,0.591,4.94\times
10^{-32}]$. We observe that the variable $p_{u_{1}}$ has nearly reached its
upper bounds and will contribute little to the overall distance based on the
data, while $p_{c_{1}}$ and $p_{o_{1}}$ will contribute more heavily. The
results are shown in case 3.

case 1: $d(X\;|\;\bm{\lambda}_{1})$

$\blockarray{cccccc}&\mathbf{x}_{1}\mathbf{x}_{2}\mathbf{x}_{3}\mathbf{x}_{4}\mathbf{x}_{5}\\\
\block{c(ccccc)}\mathbf{x}_{1}004.00081.78881.788\\\
\mathbf{x}_{2}04.00081.78881.788\\\ \mathbf{x}_{3}081.78881.788\\\
\mathbf{x}_{4}04.000\\\ \mathbf{x}_{5}0\\\ $

case 2: $d(X\;|\;\bm{\lambda}_{2})$

$\blockarray{cccccc}&\mathbf{x}_{1}\mathbf{x}_{2}\mathbf{x}_{3}\mathbf{x}_{4}\mathbf{x}_{5}\\\
\block{c(ccccc)}\mathbf{x}_{1}0000.0010.001\\\ \mathbf{x}_{2}000.0010.001\\\
\mathbf{x}_{3}00.0010.001\\\ \mathbf{x}_{4}00\\\ \mathbf{x}_{5}0\\\ $

case 3: $d(X\;|\;\bm{\lambda}_{3})$

$\blockarray{cccccc}&\mathbf{x}_{1}\mathbf{x}_{2}\mathbf{x}_{3}\mathbf{x}_{4}\mathbf{x}_{5}\\\
\block{c(ccccc)}\mathbf{x}_{1}002.8192.5101.328\\\
\mathbf{x}_{2}02.8192.5101.328\\\ \mathbf{x}_{3}01.3282.510\\\
\mathbf{x}_{4}02.819\\\ \mathbf{x}_{5}0\\\ $

##  5 Study Descriptions and Results

To evaluate the performance of the KDSUM metric in comparison to established
metrics for mixed-type data distance-based clustering, we analyzed simulated
and real datasets of continuous, categorical, and mixed-type attributes using
agglomerative hierarchical clustering techniques. We establish the performance
of the KDSUM metric relative to existing metrics for handling mixed-type data
and demonstrate the potential of the KDSUM metric to enhance CA. By comparing
the KDSUM metric to these advanced clustering techniques, we demonstrate the
flexibility of the KDSUM metric for usage in the clustering of mixed datasets.

###  5.1 Clustering algorithms

Mixed-type approaches offer a solution to the challenge of clustering datasets
that contain both continuous and categorical variables. One approach involves
selecting a distance metric that can handle both types of variables, and then
clustering the data using methods that depend on the distance function.

####  5.1.1 Clustering with Distance Metrics

A kernel distance metric can be utilized in any clustering algorithm that
accepts a dissimilarity metric. Additionally, this metric can be adapted to
centroid, medoid, or prototype-based methods. To test the KDSUM metric for
clustering, we follow previous literature that uses agglomerative hierarchical
clustering algorithms designed to cluster based on dissimilarity metrics (see,
for example, Day & Edelsbrunner, 1984; Murtagh & Contreras, 2012; Bouguettaya
et al., 2015; Sasirekha & Baby, 2013; Nielsen, 2016).

Single-linkage calculates the distance between two clusters as the shortest
distance between any two points in the two clusters. Similarly, Complete-
linkage (e.g., Macnaughton-Smith, 1965) calculates the distance between two
clusters as the maximum distance between any two points in the two clusters.
Average-linkage (e.g., Lance & Williams, 1967), on the other hand, considers
the average distance between all pairs of points in the two clusters. Ward’s
method (Ward, 1963) seeks to minimize the total variance within each cluster
as the criterion for merging clusters. Median linkage employs the median
distance between all pairs of points in the two clusters, while centroid
linkage (e.g., Sokal & Michener, 1958) relies on the distance between the
centroids of the two clusters.

For the simulated and empirical application that follow, the KDSUM metric with
Gaussian, Aitken, and Wang & van Ryzin kernels is used in a modified $k$-means
clustering algorithm and competing hierarchical clustering methods, including
single-, average-, and complete-linkages along with Ward’s method. We report
only the method with the highest CA and ARI is reported when utilizing the
KDSUM to compare to competing methods.

####  5.1.2 Clustering Evaluation

When evaluating and comparing the effectiveness and accuracy of clustering and
classification techniques, we use the two commonly used metrics of CA and the
ARI. We chose to evaluate our clustering results using both ARI and CA to
provide a comprehensive and well-rounded assessment of our proposed clustering
algorithm. While CA offers a straightforward measure of correct assignments,
the ARI considers both pairwise agreements and disagreements, normalized for
chance. This enables us to better understand the clustering performance in
scenarios where clusters may be of varying sizes and complexities, where CA
results may become more difficult to interpret.

The ARI is a statistic that quantifies the similarity between the true
classification of the data and the classification obtained by a given method
(Rand, 1971). The ARI is defined as

$ARI=\frac{\sum_{ij}{{n_{ij}}\choose{2}}-[\sum_{i}{{a_{i}}\choose{2}}\sum_{j}{{b_{j}}\choose{2}}]/{{n}\choose{2}}}{\frac{1}{2}[\sum_{i}{a_{i}\choose{2}}+\sum_{j}{{b_{j}}\choose{2}}]-[\sum_{i}{{a_{i}}\choose{2}}\sum_{j}{{b_{j}}\choose{2}}]/{{n}\choose{2}}},$

where $n_{ij}$ is the diagonal sum of the clustering contingency table, and
$a_{i}$, $b_{j}$ correspond to the row sums and column sums of the contingency
table, respectively. The contingency table is a visual depiction that
summarizes agreeance and disagreeance between the true class labels and the
classification class labels. The index considers the number of pairs of data
points that are labelled identically in both sets and labelled differently in
both sets. The ARI then adjusts for a chance agreement based on the expected
agreement between the two sets under a null model. The resulting ARI value
ranges from 0 to 1, where 0 indicates complete randomness and 1 indicates
perfect agreement in classification.

CA is also used to measure the percentage of data points correctly assigned to
their corresponding clusters. It is calculated by comparing the true
classification labels with those generated by the clustering algorithm,
defined as

$CA(y,\hat{y})=\frac{\sum_{i=1}^{n}{\color[rgb]{0,0,0}\mathds{1}}(\hat{y}_{i}=y_{i})}{n},$

where the indicator function
${\color[rgb]{0,0,0}\mathds{1}}({\color[rgb]{0,0,0}\hat{y}_{i}=y_{i}})=1$ if
the class label $\hat{y}_{i}=y_{i}$, and 0 otherwise. The CA ranges from 0 to
1, where 0 indicates that none of the data points are assigned to the correct
clusters, and 1 indicates that all data points are assigned to the correct
clusters.

###  5.2 Simulation Studies

This section describes the simulated data used to investigate the performance
of the KDSUM metric for clustering using the methodologies described in
Section 5.1. We analyze Monte Carlo simulations for each clustering algorithm
using the mixed-type metrics on continuous-only, categorical-only, and mixed-
type simulated datasets.

####  5.2.1 Continuous data

The first four continuous simulated datasets were adapted from Morbieu (2018)
to evaluate the ability of KDSUM to effectively handle data that exhibit
linear and nonlinear clustering patterns. In all instances, the simulated data
comprised two variables and two known classes. Specifically, the first dataset
(Sim 1) consisted of 373 observations simulated as in Figure 1, where each
Monte Carlo iteration allowed each observation to shift in in four directions.
The shift of each observation was drawn from a uniform distribution between
$\pm 0.5$. The second dataset (Sim 2) contained 2050 observations that were
simulated using a well-defined large cluster of 2000 observations with low
variance, and a small cluster of 50 observations with high variance. The third
dataset (Sim 3) consisted of 200 observations that were simulated with one
dense spherical cluster that was contained inside a sparse spherical cluster,
with both clusters having equal observations. Lastly, the fourth dataset (Sim
4) consisted of two equally-sized clusters that were spiralled within each
other. A visualization of the four simulated continuous datasets is presented
in Figure 1.

Figure 1: Variable distribution with respect to cluster assignment for four
continuous simulated datasets. From left to right: Sim 1, Sim 2, Sim 3, Sim 4.

####  5.2.2 Categorical data

A categorical-only dataset (Sim 5) consisted of $200$ observations, with $5$
unordered categorical variables and $3$ clusters. Two of the variables were
random binary noise variables, and the three unordered categorical variables
were randomly selected integers in the interval
${\color[rgb]{0,0,0}[}0{\color[rgb]{0,0,0},}30{\color[rgb]{0,0,0})}$, and the
first cluster consisted only of values in
${\color[rgb]{0,0,0}[}0{\color[rgb]{0,0,0},}10{\color[rgb]{0,0,0})}$ for each
of the three variables, while classes two and three consisted of values in
${\color[rgb]{0,0,0}[}10{\color[rgb]{0,0,0},}20{\color[rgb]{0,0,0})}$ and
${\color[rgb]{0,0,0}[}20{\color[rgb]{0,0,0},}30{\color[rgb]{0,0,0})}$,
respectively. Figure 2 shows a single simulation from this dataset, which
shows that there is some overlap in the cluster assignments.

Figure 2: Variable distribution with respect to cluster assignment for Sim 5.
$X_{1}$ and $X_{2}$ represent the binary noise variables, and $X_{3}$, $X_{4}$
and $X_{5}$ are the meaningful categorical variables, grouped in a 10 unit
interval for ease of interpretation.

####  5.2.3 Mixed-type data

Sim 6 was constructed with $373$ observations and $5$ variables, where $2$
continuous variables followed the same distribution as Sim 1 with the same
variation at each Monte Carlo iteration. The one unordered categorical
variable, $X_{3}$, was binary and generated randomly as noise at each
iteration. The two unordered categorical variables ranged from $0$ to $2$ for
the first cluster and $3$ to $4$ for the second, randomly drawn at each
iteration from a uniform distribution then rounded to an integer. Cluster 1
contained 97 observations, while cluster 2 contained 276.

####  5.2.4 Results

For each of the six data generating processes described in the previous
sections, we conducted 1000 Monte Carlo simulations and analyzed them using
KDSUM with hierarchical clustering and average-linkage compared to the
clustering algorithms in Section 5.1.1. Distributions and average values of
the CA and ARI for clustering Monte Carlo simulations are shown in Figure 3
and Table 2, respectively. For Sim 1, KDSUM hierarchical clustering
outperformed each of the other methods and had nearly perfect CA. For Sim 2,
GMM had the highest CA and ARI, slightly higher than KDSUM hierarchical
clustering. This is likely due to the two clusters being circular with some
overlap, where a linear mixture model is a correctly specified clustering
algorithm for this datatype. For Sim 3 and Sim 4, we see that KDSUM is
clustering well on these and demonstrates that the KDSUM metric is able to
estimate non-linear datasets. Sim 5 and Sim 6 both contain large values of CA
and ARI for KDSUM hierarchical clustering while in the presence of categorical
and continuous noise variables. We note for Sim 6 that Gower’s distance with
hierarchical clustering uses Euclidean distance and a simple matching
coefficient with a weight for distance measurement. Gower’s distance tends to
place more emphasis on the categorical variables as a result, and thus
performs well since there is low overlap between categorical variables in
terms of clustering. The bandwidths selected via MSCV for KDSUM were very
small; thus the KDSUM metric aligned with Gower’s distance in the metric
calculation.

Figure 3: Boxplots of ARI and CA for KDSUM with hierarchical clustering and average-linkage, compared against competing clustering algorithms for simulated continuous, categorical, and mixed-type data. Table 2: Classification results on Monte Carlo simulated data. The KDSUM metric with agglomerative hierarchical clustering was compared to Partitioning around Medoids (PAM-E / PAM-G), Euclidean or Gower’s distance with hierarchical clustering (HC-E / HC-G), $k-$means, $k-$modes, $k-$prototypes ($k-$proto), Gaussian Mixture Model (GMM), ROCK, and clustMD. For hierarchical clustering, the method is reported in brackets. The average ARI and CA of 1000 Monte Carlo simulations is reported for each clustering algorithm. Data | Model | CA | ARI | Data | Model | CA | ARI
---|---|---|---|---|---|---|---
Sim 1 | KDSUM (Average) | 0.990 | 0.960 | Sim 4 | KDSUM (Average) | 0.983 | 0.962
(cont.) | HC-E (Average) | 0.880 | 0.604 |  | HC-E (Average) | 0.580 | 0.033
| PAM-E | 0.752 | 0.253 | (cont.) | PAM-E | 0.599 | 0.038
|  $k-$means | 0.780 | 0.312 |  |  $k-$means | 0.599 | 0.038
| GMM | 0.577 | 0.038 |  | GMM | 0.592 | 0.035
Sim 2 | KDSUM (Average) | 0.989 | 0.929 | Sim 5 | KDSUM (Average) | 0.938 | 0.860
(cont.) | HC-E (Average) | 0.998 | 0.974 |  | HC-G (Average) | 0.594 | 0.311
| PAM-E | 0.817 | 0.543 | (cat.) | PAM-G | 0.648 | 0.230
|  $k-$means | 0.997 | 0.963 |  |  $k-$modes | 0.439 | 0.034
| GMM | 0.999 | 0.989 |  | ROCK | 0.787 | 0.498
Sim 3 | KDSUM (Average) | 0.913 | 0.811 | Sim 6 | KDSUM (Average) | 1.000 | 1.000
(cont.) | HC-E (Average) | 0.820 | 0.444 |  | HC-G (Average) | 1.000 | 1.000
| PAM-E | 0.869 | 0.545 | (mix.) | PAM-G | 0.523 | 0.000
|  $k-$means | 0.877 | 0.569 |  |  $k-$proto | 0.828 | 0.459
| GMM | 0.854 | 0.507 |  | clustMD | 0.802 | 0.363

###  5.3 Bandwidth Grid Search

In this section, we establish the effect of KDSUM bandwidth selection in
clustering. The choice of bandwidths can affect the distance metric
calculation, and we show that MSCV selects ideal bandwidths that are small for
variables relevant to clustering and large for variables that are irrelevant.
Clustering for this section was conducted using agglomerative hierarchical
clustering with single-linkage. To examine bandwidth selection influence on
clustering through CA and ARI, we analyze simulated data consisting of
continuous-only, categorical-only, and mixed-type data.

####  5.3.1 Continuous data

For the continuous-only data, we simulated two continuous variables and five
distinct clusters. The cluster centres are selected at random from a two-
dimensional uniform distribution spanning the interval $[0,12]\times[0,12]$,
with each cluster populated through a multivariate normal distribution, with
cluster sample sizes selected randomly from 50 to 200. A visual representation
of the data is shown in the left panel of Figure 4. A systematic grid search
was conducted, spanning bandwidth values from 0 to 10 and incremented in steps
of 0.05 and results from clustering using the modified $k-$means for distance
matrices algorithm, are shown in the right two panels of Figure 4. The MSCV
selected bandwidth values are $(0.443,0.483)$ for $X_{1}$ and $X_{2}$,
respectively. We can see that the performance metrics remain high at elevated
bandwidths; however, these two bandwidths must be balanced to allow KDSUM to
accurately measure dissimilarity and improve underlying clustering algorithm
accuracy. This plot demonstrates that MSCV preferentially selects the smallest
bandwidths for significant variables.

Figure 4: The left panel is the data generating process of two continuous
variables $X_{1}$ and $X_{2}$, with $k=5$ clusters. The middle and right
panels depict the CA and ARI, respectively, for the continuous bandwidth grid
search, where increments of bandwidths were 0.05 in the range $[0,10]$ for
both variables. The red dot on each panel indicates the optimal bandwidth
selected via MSCV for the KDSUM metric.

####  5.3.2 Categorical data

Next, we investigate a simulated categorical-only dataset. The data is
generated with three distinct clusters based on a binary noise term ($X_{1}$)
and two categorical variables ($X_{2}$ & $X_{3}$). The first cluster is
generated with random integers 1 through 5, the second with random integers 5
through 10. Other than the noise term, the overlap in the ranges of the
integers of each cluster allows for cluster overlap. The ratio of the three
clusters is 1:1, respectively, with 75 observations per cluster. All variables
are treated as unordered categorical. A visual representation of this data is
shown in the top three panels of Figure 5.

The resultant grid search entails increments of $0.05$ for each of the three
variables in the range $[0,\frac{3}{4}]$, resulting in $4,096$ permutations.
The results, presented in the bottom panel of Figure 5, show that clustering
performance is best when we use small bandwidths for relevant variables and
large bandwidths for irrelevant variables. The noise variable is shown to
provide poor performance (small ARI) when the bandwidth is small, and the
optimal bandwidth is a large value that effectively smooths out the noise
variable for distance calculations and thus becomes irrelevant to clustering.
The important variables for clustering are the two categorical where MSCV
selects small bandwidths and provides the highest ARI compared to any other
set of bandwidths.

Figure 5: The upper three panels are the data generating process with $k=2$
clusters, with binary noise term ($X_{1}$), and two unordered categorical
variables ($X_{2},X_{3}$). The bottom plot is a parallel coordinates plot for
the unordered categorical bandwidth grid search, where increments of
bandwidths were 0.05 in the range $[0,0.75]$ for all variables, coloured by
the ARI for each possible combination. The red lines indicate the optimal
bandwidth determined using maximum-likelihood cross-validation with the KDSUM
metric.

####  5.3.3 Mixed-type data

We extend this simulation to a mixed dataset that consists of a mixture of the
previous two datasets; 200 observations consisting of one continuous variable
generated from a normal mixture model, and two categorical variables (one
unordered and one ordered) generated from a multinomial mixture model. The
overlap between continuous and categorical variables is set to 5% for one
continuous and 35% for two categorical variables. The 200 observations are
portioned to a $40:60$ ratio among the two clusters. A visual representation
of this data is shown in the top three panels of Figure 6.

The resultant grid search entails varied bandwidth assignments: the continuous
variable’s ($X_{1}$) bandwidth is incremented in steps of 0.05 over the
interval $[0,10]$, the unordered categorical variable $X_{2}$ range in
$[0,\frac{3}{4}]$ at increments of 0.05, while the ordered categorical
variable $X_{3}$ in $[0,1]$, also in increments of 0.05, resulting in $67,536$
permutations. Clustering for this simulation was completed with the modified
$k-$means algorithm for distance matrices, and the results are presented in
the bottom two panels of Figure 6. The optimal set of bandwidths selected by
MSCV shows that each variable is relevant to the clustering algorithm, where
large bandwidths are shown to cause suboptimal ARI in clustering.

Figure 6: The upper three panels are the data generating process with $k=2$
cluster, with one continuous $(X_{1})$, unordered categorical ($X_{2}$), and
one ordered ($X_{3}$) variable. Each of the two categorical variables has four
levels. The parallel coordinates plots depicted below are the regular and
standardized version of the bandwidth values for each variable, for ease of
interpretation. The red lines indicate the regular and standardized version of
the optimal bandwidth determined using maximum-likelihood cross-validation in
conjunction with the KDSUM method.

###  5.4 Effect of Sample Size

Monte Carlo simulations were conducted to discern the performance of KDSUM
metric with the modified $k$-means algorithm for distance matrices for varying
cluster sizes. This iteration encompasses five clusters generated from a
multivariate normal distribution with fixed cluster centres spanning $[0,10]$.
500 simulations were conducted with sample sizes of 10, 25, 50, 100, 200, 500,
and 1000 observations, with single simulation examples shown in the upper
panels of Figure 7. Fixed cluster centres were maintained for all simulations.
We note that our implementation of the KDSUM metric methodology is
approximately 10 times slower than typical mixed-type metrics; however, with
improved coding, the KDSUM methodology execution time could be improved.

ARI, CA, and execution time were calculated for each iteration at sample sizes
of 10 to 1000 observations per cluster, and are shown in Figure 7. We can see
that the variability of CA decreases as sample size increases, while the
median value increases up to 500 observations. At 1000 observations, we see
that the median value decreases due to the increasing number of observations
in the overlap of clusters. A similar result in CA can be seen in the ARI
results. The execution time increases exponentially, where the median
execution time for 1000 observations per cluster simulation is approximately
390 seconds or 6.5 minutes.

Figure 7: The top row of seven panels are single simulations out of the 500
Monte Carlo Simulations with five cluster centres, each drawn from the numbers
of observations from 10 to 1000. The bottom left panel is a boxplot of the
clustering accuracies. The bottom centre panel is a boxplot of the ARIs
associated with each Monte Carlo simulation at each sample size. The bottom
right panel is a boxplot of the execution of time (in seconds) of each Monte
Carlo replication at each sample size.

As we demonstrated the performance of this algorithm for varying sample sizes
for continuous-only data, we conducted a simulation study on mixed-type
simulated data. The continuous variables are drawn from a normal mixture
model, whereas categorical variables follow a multinomial mixture model.
Overlap between two clusters for continuous variables is the area of the
overlapping region defined by their densities, and for categorical variables,
the summed height of overlapping segments is defined by their point masses.
The overlap for all variables is set to $20\%$, and the two cluster sizes
follow a $1:1$ ratio. The sample sizes span 25, 50, 100, 200, 500, and 1000
observations, where 500 Monte Carlo simulations were executed for each cluster
size. The empirical marginal distributions of variables for single simulations
are shown in the upper panels of Figure 8.

The results of clustering the mixed-type data Monte Carlo simulations are
shown in the lower panels of Figure 8. We see that the variability of CA and
ARI decreases as sample size increases, showing that the increase in
information improves the accuracy of clustering when using KDSUM. Similarly to
the continuous-only data, there is a slight decrease in the median accuracy
and ARI as the sample size increases for larger sample sizes caused by hard
partitioning for overlapped clusters. Further, the execution time grows
exponentially as sample size increases, where the total time for 1000
observations per cluster is approximately 225 seconds or 3.75 minutes. This
execution time is smaller than continuous-only, as there are only two clusters
for mixed-type data as opposed to the five clusters for the continuous-only
data, where continuous-only data had approximately 2.5 times the number of
observations.

Figure 8: The top row of four panels are the marginal distributions of a
single mixed-type data simulation out of the 500 Monte Carlo Simulations. The
bottom left panel is a boxplot of the clustering accuracies. The bottom centre
panel is a boxplot of the ARIs associated with each Monte Carlo simulation at
each sample size. The bottom right panel is a boxplot of the execution of time
(in seconds) of each Monte Carlo replication at each sample size.

##  6 Real Data Analysis

This study utilized a diverse range of data, including continuous,
categorical, and mixed-type datasets, to evaluate the KDSUM metric for
clustering algorithms. Unless otherwise noted, all datasets used in the study
are publicly available through the UCI Machine Learning Repository (Dua &
Graff, 2017). For each dataset, we removed any observation vectors containing
at least one NA value, as many of the clustering methods used (including KDSUM
hierarchical) are not designed for missing data.

Continuous-only datasets include the Body dataset with 24 continuous variables
and 507 observations with 2 classes, from R-package gclus (Hurley, 2019). Two
additional continuous-only datasets are the Wine dataset with 178 observations
of 13 continuous variables and three classes, and Iris dataset with 150
observations with four continuous variables and a classification column
containing three distinct classes.

Categorical-only datasets include the Soybean dataset (Soybean L.) was also
included, which contains 307 observations and a mix of 35 ordered and
unordered categorical variables and 18 classes, as well as its smaller version
(Soybean S.) consisting of four classes and 45 observations. The categorical
Breast Cancer (Breast) dataset with nine ordered categorical variables and two
classes, and the Congressional Vote dataset (Vote) was also used, with 435
observations and 15 variables, with two classes. Additionally, we use the Zoo
dataset with 101 observations consisting of twelve binary variables and one
ordered categorical variable.

Mixed-type variable datasets used include The Australian Credit (Credit) and
Auto MPG dataset (Auto), which have a mix of continuous and categorical
variables and two classes each. The Credit dataset consists of 690
observations and 14 variables, 8 of which are treated as unordered categorical
and 6 as continuous. The Auto dataset consists of 398 observations and 7
variables (after the car name variable was removed), 1 of which is treated as
unordered categorical, 1 as ordered categorical, and 5 as continuous. For the
Auto MPG dataset, the predicted class was a continuous variable (miles per
gallon), and was partitioned into 2 distinct classes with an approximately
even dispersion of observations into the two classes, namely, miles per gallon
$<22$ and $\geq 22$.

###  6.1 Results

We present the results of ten real datasets in Table 3. The results of the
experiments demonstrate the improvements of the KDSUM metric in terms of CA
and ARI. For the Body dataset, the Gaussian Mixture model outperformed KDSUM
by approximately $4.30\%$ in terms of CA and $0.159\%$ in terms of ARI, but
KDSUM outperformed the remaining three methods by at least $6.3\%$ in terms of
CA and $0.204\%$ for ARI. For the Wine dataset, KDSUM tied GMMs for highest CA
and ARI, and outperformed all other methods by at least $5.1\%$ for CA and
$0.139$ for ARI. For the Iris dataset, KDSUM did comparably well to PAM and
$k-$means, but was outperformed by the two other methods, which we discuss
after. For both the Soybean small dataset, all methods performed equally as
well, with the exception of PAM with Gower’s distance, which did slightly
worse. For the large version of the Soybean dataset, KDSUM outperformed all
other methods by at least $9.9\%$ in terms of CA and $0.201$ for ARI. For the
Zoo dataset, KDSUM outperformed all others by at least $3.0\%$ for CA, and
$0.082$ for ARI, while with the Breast dataset, KDSUM performed just slightly
poorer than hierarchical clustering with Gower’s distance, and outperformed
the other three methods by at least $0.2\%$ for CA and $0.011$ for ARI. For
the Vote dataset, KDSUM outperformed all other methods by at least $0.4\%$ for
CA and $0.019$ for ARI, while for the Auto dataset, KDSUM outpeformed all
other methods by at least $0.2\%$ for CA and $0.08$ for ARI. Lastly, for the
Credit dataset, KDSUM outperformed all method by at least $2.3\%$ for CA and
$0.056$ for ARI.

Table 3: Classification results on real data. The KDSUM metric with aggolomerative hierarchical clustering was compared to Euclidean or Gower’s distance with hierarchical clustering (HC-E / HC-G) and Partitioning around Medoids (PAM-E / PAM-G), $k-$means, $k-$modes, $k-$prototypes ($k-$proto), Gaussian Mixture Model (GMM), ROCK, and clustMD. For hierarchical clustering, the linkage that provides the best results is reported in parentheses. Data | Model | CA | ARI | Data | Model | CA | ARI
---|---|---|---|---|---|---|---
Body | KDSUM (Average) | 0.935 | 0.756 | Zoo | KDSUM (Complete) | 0.921 | 0.940
(cont.) | PAM-E | 0.872 | 0.552 | (cat.) | PAM-G | 0.813 | 0.662
|  $k-$means | 0.864 | 0.529 |  |  $k-$modes | 0.800 | 0.647
| HC-E (Ward) | 0.868 | 0.540 |  | HC-G (Complete) | 0.881 | 0.847
| GMM | 0.978 | 0.915 |  | ROCK | 0.891 | 0.858
Wine | KDSUM (Ward) | 0.978 | 0.929 | Breast | KDSUM (Ward) | 0.957 | 0.836
(cont.) | PAM-E | 0.708 | 0.371 | (cat.) | PAM-G | 0.955 | 0.825
|  $k-$means | 0.702 | 0.377 |  |  $k-$modes | 0.933 | 0.745
| HC-E (Ward) | 0.927 | 0.790 |  | HC-G (Ward) | 0.968 | 0.874
| GMM | 0.978 | 0.929 |  | ROCK | 0.686 | 0.041
Iris | KDSUM (Ward) | 0.887 | 0.718 | Vote | KDSUM (Ward) | 0.914 | 0.684
(cont.) | PAM-E | 0.893 | 0.730 | (cat.) | PAM-G | 0.867 | 0.535
|  $k-$means | 0.893 | 0.730 |  |  $k-$modes | 0.867 | 0.535
| HC-E (Ward) | 0.907 | 0.759 |  | HC-G (Average) | 0.910 | 0.665
| GMM | 0.967 | 0.904 |  | ROCK | 0.828 | 0.504
Soybean S. | KDSUM (Average) | 1.000 | 1.000 | Auto | KDSUM (Average) | 0.913 | 0.682
(cat.) | PAM-G | 0.936 | 0.820 | (mix.) | PAM-G | 0.829 | 0.431
|  $k-$modes | 1.000 | 1.000 |  |  $k-$Proto | 0.888 | 0.600
| HC-G (Complete) | 1.000 | 1.000 |  | HC-G (Average) | 0.911 | 0.674
| ROCK | 1.000 | 1.000 |  | clustMD | 0.880 | 0.557
Soybean L. | KDSUM (Ward) | 0.792 | 0.577 | Credit | KDSUM (Ward) | 0.817 | 0.401
(cat.) | PAM-G | 0.693 | 0.376 | (mix.) | PAM-G | 0.794 | 0.345
|  $k-$modes | 0.673 | 0.320 |  |  $k-$Proto | 0.793 | 0.342
| HC-G (Ward) | 0.628 | 0.315 |  | HC-G (Ward) | 0.746 | 0.241
| ROCK | 0.679 | 0.327 |  | clustMD | 0.564 | 0.004

For the Iris dataset, the KDSUM method did not perform as well as the
competing methods. It is worth mentioning that if we only consider one column
(petal width), KDSUM (Ward) achieved CA and ARI of $0.960$ and $0.886$,
respectively, which is the highest value obtained from any combination of
variables in this dataset. While the obvious cluster of the setosa species
class label was correctly identified, the overlapping nature of the remaining
two species, setosa and versicolor, led the KDSUM method to incorrectly
classify more than the other methods. Improving the effectiveness of the KDSUM
metric for handling overlapping clusters is an active area of consideration.

##  7 Conclusion

In this study, we proposed a novel kernel distance metric for effectively
handling mixed-type data. Specifically, we developed a metric based on using
kernel functions as similarity functions, where we proved that the Gaussian,
Aitken and Wang & van Ryzin kernels are similarity functions. To ensure the
viability of our KDSUM metric, we rigorously proved that it satisfies all
necessary properties of a distance metric, including non-negativity, symmetry,
the triangle inequality, and the identity of indiscernibles. In doing so, we
established the theoretical foundation for our KDSUM metric as a shrinkage
methodology and demonstrated its potential for accurately capturing the
distances between mixed-type data points.

We conducted extensive experiments on both simulated and real data to evaluate
the effectiveness of our KDSUM metric compared to existing mixed-type data
metrics and state-of-the-art clustering algorithms designed to handle mixed-
type data. Using agglomerative hierarchical clustering techniques, we assessed
the performance of our KDSUM metric in terms of CA and the ARI. The KDSUM
metric in hierarchical clustering outperformed existing mixed-type data
metrics and achieved competitive results compared to state-of-the-art
clustering algorithms. Although most existing metrics employ an additive
structure for each variable type, which is similar to the KDSUM method, none
of the methods analyzed utilize kernels or kernel smoothing techniques to
eliminate irrelevant variables for clustering. Instead, they rely on either
parametric approaches that require data transformations through importance
weighting of categorical variables that can be controlled by the user directly
or estimated using optimization techniques, or nonparametric approaches that
fail to adapt to the underlying data generating process for metric
calculations or clustering approach.

Early versions of this methodology used maximum cross-validated bandwidths
from a mixed-type joint kernel density estimated (Hall, Racine, and Li, 2004).
This approach demonstrated good results, but further investigation into
replacing the likelihood function with a similarity function demonstrated
increased improvements. Thus, the results of using a likelihood optimization
approach were not included.

This paper demonstrates the first steps towards a generalized distance for
mixed-type data. Some improvements to the methodology are possible. We have
calculated similarities and distances orthogonally to the clustering
algorithm. An investigation of a wider range of bandwidth selection procedures
for various distance-based clustering algorithms is also future work. While
agglomerative hierarchical clustering was preferred for this study, a new or
existing algorithm that incorporates kernels into the clustering loss function
may further enhance the classification and clustering of mixed-type data with
a kernel distance metric. A detailed analysis of clustering algorithms that
require dissimilarity matrices as input and determining the optimal clustering
algorithm that pairs with kernel distance metrics is also future work.
Moreover, we identified several promising directions for future research,
including applying investigating the effects of using various continuous and
categorical kernels on kernel metric calculations, developing numerical
methods for determining the optimal number of clusters, and using kernel
metrics for fuzzy clustering algorithms. By exploring these research
directions, we can further explore the applicability and effectiveness of our
KDSUM method for clustering mixed-type data.

## Data Availability

The datasets analyzed during the current study are publicly available in the
UCI Learning Repository.

## Code Availability

All code is available upon request from the contact author. The software used
for this research is described in Appendix A.

## Conflict of Interest

The authors declare they have no conflict of interest.

## References

  * [1] John Aitchison and Colin G. Aitken “Multivariate binary discrimination by the kernel method” In _Biometrika_ 63.3 Oxford University Press, 1976, pp. 413–420
  * [2] Bachir Bekka, Pierre de la Harpe and Alain Valette “Kazhdan’s Property (T)”, New Mathematical Monographs Cambridge University Press, 2008
  * [3] Christopher M. Bishop “Pattern recognition and machine learning” Springer, 2006
  * [4] Athman Bouguettaya et al. “Efficient agglomerative hierarchical clustering” In _Expert Systems with Applications_ 42.5 Elsevier, 2015, pp. 2785–2797
  * [5] Christian Buchta and Michael Hahsler “cba: Clustering for Business Analytics” R package version 0.2-23, 2022 URL: https://CRAN.R-project.org/package=cba
  * [6] Weksi Budiaji “kmed: Distance-based K-Medoids” In _R package version 0.4.2_ , 2022
  * [7] Shihyen Chen, Bin Ma and Kaizhong Zhang “On the similarity metric and the distance metric” In _Theoretical Computer Science_ 410.24-25 Elsevier, 2009, pp. 2365–2376
  * [8] Yihua Chen et al. “Similarity-based classification: Concepts and algorithms.” In _Journal of Machine Learning Research_ 10.3, 2009
  * [9] Seung-Seok Choi, Sung-Hyuk Cha and Charles C. Tappert “A survey of binary similarity and distance measures” In _Journal of systemics, cybernetics and informatics_ 8.1, 2010, pp. 43–48
  * [10] Michael Christoph and Quirin Stier “Fundamental clustering algorithms suite” In _SoftwareX_ 13 Elsevier, 2021, pp. 100642 URL: https://www.sciencedirect.com/science/article/pii/S2352711020303551
  * [11] Kevin R. Coombes “Thresher: Threshing and Reaping for Principal Components” R package version 1.1.3, 2019
  * [12] William H. Day and Herbert Edelsbrunner “Efficient algorithms for agglomerative hierarchical clustering methods” In _Journal of classification_ 1 Springer, 1984, pp. 7–24
  * [13] James Dougherty, Ron Kohavi and Mehran Sahami “Supervised and unsupervised discretization of continuous features” In _Machine learning proceedings 1995_ Elsevier, 1995, pp. 194–202
  * [14] Dheeru Dua and Casey Graff “UCI Machine Learning Repository”, 2017 URL: http://archive.ics.uci.edu/ml
  * [15] Vassiliy A. Epanechnikov “Non-parametric estimation of a multivariate probability density” In _Theory of Probability & Its Applications_ 14.1 SIAM, 1969, pp. 153–158
  * [16] Alex Foss, Marianthi Markatou, Bonnie Ray and Aliza Heching “A semiparametric method for clustering mixed data” In _Machine Learning_ 105 Springer, 2016, pp. 419–458
  * [17] Alexander H. Foss, Marianthi Markatou and Bonnie Ray “Distance metrics and clustering methods for mixed-type data” In _International Statistical Review_ 87.1 Wiley Online Library, 2019, pp. 80–109
  * [18] Alexander H. Foss and Marianthi Markatou “kamila: Clustering Mixed-Type Data in R and Hadoop” In _Journal of Statistical Software_ 83.13, 2018, pp. 1–45 DOI: \color{black}10.18637/jss.v083.i13
  * [19] Seymour Geisser “The predictive sample reuse method with applications” In _Journal of the American Statistical Association_ 70.350 Taylor & Francis, 1975, pp. 320–328
  * [20] John C. Gower “A general coefficient of similarity and some of its properties” In _Biometrics_ JSTOR, 1971, pp. 857–871
  * [21] Sudipto Guha, Rajeev Rastogi and Kyuseok Shim “ROCK: A robust clustering algorithm for categorical attributes” In _Information systems_ 25.5 Elsevier, 2000, pp. 345–366
  * [22] Peter Hall “On nonparametric multivariate binary discrimination” In _Biometrika_ 68.1 Oxford University Press, 1981, pp. 287–294
  * [23] John A. Hartigan and Manchek A. Wong “Algorithm AS 136: A k-means clustering algorithm” In _Journal of the royal statistical society. series c (applied statistics)_ 28.1 JSTOR, 1979, pp. 100–108
  * [24] Tristen Hayfield and Jeffrey S. Racine “Nonparametric econometrics: The np package” In _Journal of statistical software_ 27, 2008, pp. 1–32
  * [25] Christian Hennig, Marina Meila, Fionn Murtagh and Roberto Rocci “Handbook of cluster analysis” CRC press, 2015
  * [26] Zhexue Huang “Extensions to the k-means algorithm for clustering large data sets with categorical values” In _Data mining and knowledge discovery_ 2.3 Springer, 1998, pp. 283–304
  * [27] Lawrence Hubert and Phipps Arabie “Comparing partitions” In _Journal of classification_ 2 Springer, 1985, pp. 193–218
  * [28] Catherine Hurley “glust: CLustering Graphics” R package version 1.3.2, 2019 URL: https://CRAN.R-project.org/package=gclus
  * [29] Clifford M. Hurvich, Jeffrey S. Simonoff and Chih-Ling Tsai “Smoothing parameter selection in nonparametric regression using an improved Akaike information criterion” In _Journal of the Royal Statistical Society Series B: Statistical Methodology_ 60.2 Oxford University Press, 1998, pp. 271–293
  * [30] Frank Jäkel, Bernhard Schölkopf and Felix A. Wichmann “Similarity, kernels, and the triangle inequality” In _Journal of Mathematical Psychology_ 52.5 Elsevier, 2008, pp. 297–303
  * [31] Sarang Joshi, Raj Varma Kommaraji, Jeff M. Phillips and Suresh Venkatasubramanian “Comparing distributions and shapes using the kernel distance” In _Proceedings of the twenty-seventh annual symposium on Computational geometry_ , 2011, pp. 47–56
  * [32] Leonard Kaufman “Partitioning around medoids (program pam)” In _Finding groups in data_ 344 John Wiley & Sons, Inc., 1990, pp. 68–125
  * [33] Wojtek J. Krzanowski “Distance between populations using mixed continuous and categorical variables” In _Biometrika_ 70.1 Oxford University Press, 1983, pp. 235–243
  * [34] Godfrey N. Lance and William T. Williams “A general theory of classificatory sorting strategies: 1. Hierarchical systems” In _The computer journal_ 9.4 The British Computer Society, 1967, pp. 373–380
  * [35] Alexander R. Leon and K.. Carriere “A generalized Mahalanobis distance for mixed data” In _Journal of Multivariate Analysis_ 92.1 Elsevier, 2005, pp. 174–185
  * [36] Qi Li and Jeffrey S. Racine “Nonparametric econometrics: theory and practice” Princeton University Press, 2023
  * [37] Qi Li, Jeffrey S. Racine and Jeffrey M. Wooldridge “Estimating average treatment effects with continuous and discrete covariates: The case of Swan-Ganz catheterization” In _American Economic Review_ 98.2 American Economic Association, 2008, pp. 357–362
  * [38] Bruce G. Lindsay et al. “Quadratic distances on probabilities: a unified foundation” In _The Annals of Statistics_ 36.2 Citeseer, 2008, pp. 983–1006
  * [39] Clive R. Loader “Bandwidth selection: classical or plug-in?” In _The Annals of Statistics_ 27.2 Institute of Mathematical Statistics, 1999, pp. 415–438
  * [40] P… Macnaughton-Smith “Some Statistical and Other Numerical Techniques for Classifying Individuals” London,: H.M.S.O., 1965
  * [41] Martin Maechler et al. “cluster: Cluster Analysis Basics and Extensions”, 2022 URL: https://CRAN.R-project.org/package=cluster
  * [42] Damien McParland and Isobel C. Gormley “clustMD: Model Based Clustering for Mixed Data” R package version 1.2.1, 2017 URL: https://CRAN.R-project.org/package=clustMD
  * [43] Dharmendra S. Modha and W. Spangler “Feature weighting in k-means clustering” In _Machine learning_ 52 Springer, 2003, pp. 217–237
  * [44] Stanislas Morbieu “Generate datasets to understand some clustering algorithms behavior: R-bloggers”, 2018 URL: https://www.r-bloggers.com/2018/11/generate-datasets-to-understand-some-clustering-algorithms-behavior/
  * [45] Fionn Murtagh and Pedro Contreras “Algorithms for hierarchical clustering: an overview” In _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 2.1 Wiley Online Library, 2012, pp. 86–97
  * [46] Frank Nielsen “Hierarchical clustering” In _Introduction to HPC with MPI for Data Science_ Springer, 2016, pp. 195–211
  * [47] Emanuel Parzen “On estimation of a probability density function and mode” In _The annals of mathematical statistics_ 33.3 JSTOR, 1962, pp. 1065–1076
  * [48] Jeff M. Phillips and Suresh Venkatasubramanian “A gentle introduction to the kernel distance” In _arXiv preprint arXiv:1103.1625_ , 2011
  * [49] János Podani “Extending Gower’s general coefficient of similarity to ordinal characters” In _Taxon_ 48.2 Wiley Online Library, 1999, pp. 331–340
  * [50] R Core Team “R: A Language and Environment for Statistical Computing” ISBN 3-900051-07-0, 2013 R Foundation for Statistical Computing URL: http://www.R-project.org/
  * [51] Jeffrey S. Racine, Qi Li and Karen X. Yan “Kernel smoothed probability mass functions for ordered datatypes” In _Journal of Nonparametric Statistics_ 32.3 Taylor & Francis, 2020, pp. 563–586
  * [52] William M. Rand “Objective criteria for the evaluation of clustering methods” In _Journal of the American Statistical association_ 66.336 Taylor & Francis, 1971, pp. 846–850
  * [53] Murray Rosenblatt “Remarks on some nonparametric estimates of a density function” In _The annals of mathematical statistics_ JSTOR, 1956, pp. 832–837
  * [54] Stephan R. Sain, Keith A. Baggerly and David W. Scott “Cross-validation of multivariate densities” In _Journal of the American Statistical Association_ 89.427 Taylor & Francis, 1994, pp. 807–817
  * [55] K. Sasirekha and P. Baby “Agglomerative hierarchical clustering algorithm-a” In _International Journal of Scientific and Research Publications_ 83.3 Citeseer, 2013, pp. 83
  * [56] Luca Scrucca, Michael Fop, T. Murphy and Adrian E. Raftery “mclust 5: clustering, classification and density estimation using Gaussian finite mixture models” In _The R journal_ 8.1 NIH Public Access, 2016, pp. 289
  * [57] Bernard W. Silverman “Density estimation for statistics and data analysis” Routledge, 1986
  * [58] Robert R. Sokal and Charles D. Michener “A statistical method for evaluating systematic relationships” In _University of Kansas science bulletin_ 38, 1958, pp. 1409–1438 URL: https://api.semanticscholar.org/CorpusID:61950873
  * [59] Mervyn Stone “Cross-validatory choice and assessment of statistical predictions” In _Journal of the Royal Statistical Society: Series B (Methodological)_ 36.2 Wiley Online Library, 1974, pp. 111–133
  * [60] Gero Szepannek “clustMixType: User-Friendly Clustering of Mixed-Type Data in R” In _The R Journal_ , 2018, pp. 200–208
  * [61] Michel Van De Velden, Alfonso Iodice D’Enza, Angelos Markos and Carlo Cavicchia “A general framework for implementing distances for categorical variables” In _arXiv preprint arXiv:2301.02190_ , 2023
  * [62] Min-Chiang Wang and John Van Ryzin “A class of smooth estimators for discrete distributions” In _Biometrika_ 68.1 Oxford University Press, 1981, pp. 301–309
  * [63] Joe H. Ward Jr “Hierarchical grouping to optimize an objective function” In _Journal of the American statistical association_ 58.301 Taylor & Francis, 1963, pp. 236–244
  * [64] Claus Weihs, Uwe Ligges, Karsten Luebke and Nils Raabe “klaR Analyzing German Business Cycles” In _Data Analysis and Decision Support_ Berlin: Springer-Verlag, 2005, pp. 335–343
  * [65] David Wishart “K-means clustering with outlier detection, mixed variables and missing values” In _Exploratory Data Analysis in Empirical Research: Proceedings of the 25th Annual Conference of the Gesellschaft für Klassifikation eV, University of Munich, March 14–16, 2001_ , 2003, pp. 216–226 Springer

## Appendix

##  Appendix A Software and R-packages

All simulation were ran in $R$-Studio (R Core Team, 2023), using version
4.3.1.

The mixed-type metrics in Table 1 were calculated using the daisy function in
the package cluster (Maechler et al., 2022) for Gower’s distance, and the kmed
package (Budiaji, 2022) for the latter three distance metrics.

The package FCPS in R (Christoph & Stier, 2021) offers a modified version of
the traditional $k-$means algorithm (Hartigan & Wong, 1979) for clustering
using a distance matrix, which is also used in conjunction with KDSUM for some
experiments. For comparing clustering methods, continuous datasets are
compared against hierarchical clustering techniques with the same linkages,
using base package stats and function hclust in (R Core Team, 2023),
Partitioning Around Medoids (PAM) using function pam in package cluster
(Maechler et al., 2022), $k-$means in base package stats, and Gaussian Mixture
models using function Mclust in package mclust (Scrucca et al., 2016).
Categorical datasets are compared against hierarchical clustering techniques
with the same linkages, PAM with Gower’s distance, $k-$modes using function
kmodes in package klaR (Weihs et al., 2005), and ROCK using function
rockCluster in package cba (Buchta & Hahsler, 2022). Mixed datasets are
compared against hierarchical techniques with the same linkages, PAM with
Gower’s distance, $k-$prototypes using function kproto in package clustMixType
(Szepannek, 2018), and function / package clustMD (McParland & Gormley, 2017).
The $CA$ value is calculated with both base package stats and function
matchLabels in the package Thresher (Coombes, 2019). The ARI is calculated
using in using the package mclust (Scrucca et al., 2022). For each simulation
in Figures 6 and 8, the data are generated using genMixedData from the R
package kamila (Foss & Markatou, 2018), consisting of one continuous, one
unordered, and two ordered categorical variables.