Locally-Scaled Kernels and Confidence Voting

Abstract

Classification, the task of discerning the class of an unlabeled data point using information from a set of labeled data points, is a well-studied area of machine learning with a variety of approaches. Many of these approaches are closely linked to the selection of metrics or the generalizing of similarities defined by kernels. These metrics or similarity measures often require their parameters to be tuned in order to achieve the highest accuracy for each dataset. For example, an extensive search is required to determine the value of K or the choice of distance metric in K-NN classification. This paper explores a method of kernel construction that when used in classification performs consistently over a variety of datasets and does not require the parameters to be tuned. Inspired by dimensionality reduction techniques (DRT), we construct a kernel-based similarity measure that captures the topological structure of the data. This work compares the accuracy of K-NN classifiers, computed with specific operating parameters that obtain the highest accuracy per dataset, to a single trial of the here-proposed kernel classifier with no specialized parameters on standard benchmark sets. The here-proposed kernel used with simple classifiers has comparable accuracy to the ‘best-case’ K-NN classifiers without requiring the tuning of operating parameters.

1. Introduction

Discerning the label $y_{*}$ for an unlabeled data point ${\mathit{x}}_{*}$ using information from data points with known labels $({\mathit{x}}_j,y_j)$ is a question fundamentally based on ‘similarity’. It is expected that points of the same class are similar, so it is reasonable to map similar data points to the same class; thus, the label of ${\mathit{x}}_{*}$ could be determined using the class information of similar labeled data points. One way to interpret similarity is through a distance metric; if two points are ‘close’ by some distance metric then they are similar, and if they are far, then they are dissimilar. This leads to the concept of the K-nearest neighbors (K-NN) and the K-NN classifier.

The choice of distance metric has a significant impact on the accuracy of traditional K-NN classifiers. This impact has been explored in literature with [1,2,3,4,5,6] reporting the success of a variety of distance metrics used with a K-NN classifier on diverse sets of high-dimensional datasets. No singular distance metric performs superiorly across all datasets, but rather the best-performing distance metric is specific to each dataset.

The problem statement is thus, when presented with a labeled dataset $({\mathit{x}}_j,y_j)\in \mathcal{X}$ ($|\mathcal{X}|=J$) where ${\mathit{x}}_j\in {\mathbb{R}}^N$ with associated class label $y_j\in \{1,\dots ,C\}$, construct a function $\mathrm{class}({\mathit{x}}_j)$ that maps ${\mathit{x}}_j$ to its label $y_j$. Using this, the class of a ‘new’ unlabeled point ${\mathit{x}}_{*}$ can be discerned. This function should perform universally well across all datasets without requiring the tuning of its operating parameters.

A distance metric that, when used in classification, performs universally well across all datasets should adjust to the data on a local scale. Ideally, the distance between data points can be measured according to the topological structure of the data. From our previous experience in data mining, we understand the importance of feature extraction in classification [7]—even the best classifier will be unable to make meaningful classifications if the features of the data are indistinguishable. No distance metric can measure meaningful similarity if the feature space of the data does not separate data in a meaningful way. In machine learning, kernels are a tool used to pull the data to a new feature space called $\mathcal{H}$; this space is designed to better capture the similarities between points of the same class and vice versa [8]. Conveniently, the inner product (which induces a distance metric) in this space is a measure of similarity [9], making the kernel a natural extension of distance-based methods of classification.

Many approaches to classification only depend on the pairwise distance/similarity/correlation of the input data. As such, these algorithms can be kernelized, meaning the algorithm operates on the values of the kernel. This is further motivation for the use of a kernel to map to a new feature space that better captures similarity. Furthermore, kernel methods provide an advantage when working with high dimensional datasets as the Gram kernel matrix size is proportional to the number of data points J—once it is computed we no longer have to perform any calculations in the space of ${\mathbb{R}}^N$.

The success of traditional and weighted K-NN classifiers also depends on how confident ${\mathit{x}}_i$ is of its label $y_i$. It can be challenging to discern the label of ${\mathit{x}}_{*}$ using information from the surrounding neighbors when the neighbors are outliers or mislabeled data points, not uncommon in real-world datasets [10]. Thus, a secondary goal is to design a method of classification that diverges from the traditional K-NN classifier and introduces some measure of confidence to each ${\mathit{x}}_j$. This allows a trade-off between supervised classification (i.e., classification based on the known labels) and semi-supervised classification (i.e., classification based on some inferred class-structure of the data).

To evaluate the proposed approach, we perform tests using standard benchmark data sets from the University of California Irvine (UCI) Machine Learning Repository [11]. Using a leave-one-out testing strategy, we compare classifiers, based on the here-proposed similarity kernel with other weighted and non-weighted K-NN approaches. In contrast to approaches that study how to obtain the most accurate tuning for a classifier on a particular data set individually, we are interested in designing a similarity kernel that when used for classification requires one tuning that works well for many/all data sets.

2. Background

We begin by giving two motivations for the use of kernels in classification, one based on arguments generalizing K-NN, and the other based on mathematical arguments.

Classification has been a well-studied problem in the area of machine learning with myriad tools existing for a diverse array of applications. One popular classifier is called K-nearest neighbors [12], which uses the K nearest labeled points (by some distance metric d) of ${\mathit{x}}_{*}$ to draw conclusions about the label of ${\mathit{x}}_{*}$. For ease of notation, $n_K({\mathit{x}}_j,{\mathit{x}}_k)$ is a binary function that returns 1 if ${\mathit{x}}_k$ is one of the K-nearest neighbors of ${\mathit{x}}_j$ and 0 if it is not. A $J\times C$ matrix $\mathit{G}$ called the ‘class matrix’ stores the class information of the labeled samples such that ${\mathit{G}}_{j,c}=1$ if ${\mathit{x}}_j$ belongs to class c and zero; otherwise, classification can be performed as follows:

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J{\mathit{G}}_{j,c}{n}_K({\mathit{x}}_{*},{\mathit{x}}_j)$$

(1)

A common choice for the distance metric is the Euclidean metric $d_{\mathrm{EUC}}$. However, there are many possible choices of distance metrics for K-NN classification. An in-depth exploration of metrics can be found in the work of Abu Alfeilat et al. [1], which measures the classification accuracy, precision, and recall for a 1-NN classifier using 27 distance metrics from 13 distance metric families across 23 benchmark datasets from the UCI Machine Learning Repository [11]. From this study, it was apparent that the distance metric with the highest accuracy depends highly on the dataset, i.e., there is no single distance metric that proves to be the ‘best’ across all benchmark datasets. Some of the top-performing distance metrics from this work can be found below in

Table 1. A selection of distance metrics.

Equation	Name
$d_{\mathrm{EUC}}({\mathit{x}}_j,{\mathit{x}}_k)=\sqrt{{\sum }_{n=1}^N{({\mathit{x}}_{k,n}-{\mathit{x}}_{j,n})}^2}$	Euclidean
$d_{\mathrm{HAS}}({\mathit{x}}_j,{\mathit{x}}_k)={\sum }_{n=1}^N\left\{\begin{array}{cc}1-\frac{1+min({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})}{1+max({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})}\hfill & min({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})\ge 0\hfill \\ 1-\frac{1+min({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})+|min({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})|}{1+max({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})+min({\mathit{x}}_{j,n},{\mathit{x}}_{k,n})}\hfill & \mathrm{else}\hfill \end{array}\right.$	Hassanat
$d_{\mathrm{COS}}({\mathit{x}}_j,{\mathit{x}}_k)=1-\frac{2{\sum }_{n=1}^N{\mathit{x}}_{k,n}{\mathit{x}}_{j,n}}{\sqrt{{\sum }_{n=1}^N{\mathit{x}}_{k,n}^2}\sqrt{{\sum }_{n=1}^N{\mathit{x}}_{j,n}^2}}$	Cosine
$d_{\mathrm{MAN}}({\mathit{x}}_j,{\mathit{x}}_k)={\sum }_{n=1}^N|{\mathit{x}}_{k,n}-{\mathit{x}}_{j,n}|$	Manhattan

.

The paper concludes that the Hassanat distance [2] is the best-performing distance metric in general.

Notably, in the study by Abu Alfeilat et al., the authors only perform classification with a 1-NN classifier. This experimental design choice could have been influenced by the well-reported deterioration of K-NN classifiers as the number of neighbors increases [13]. For an unknown dataset, testing must be performed to find the most suitable distance metric and value of K. The authors were inspired to find a classifying technique that is metric-insensitive and stable with regard to operating parameters such as K.

Similar work in [9] found that computing the weights of a K-NN classifier on a local-scale can temper the classifier’s sensitivity to K.

Aside from exploring the effect of choice of distance metrics on K-NN classifier accuracy, another method of improving classification accuracy concerns changing the influence of the neighbors’ votes, following the idea that some neighbors might be more relevant to the classification of ${\mathit{x}}_{*}$ and therefore their vote should be weighted more heavily. Thus, weights w are introduced. The choice of weights can be guided using either combinatorial considerations or using metric/topological arguments.

An optimal weighting scheme based on a combinatorial argument is presented by Samworth in [13]. This technique compares the risk of a classification using weights $w_{n,m}$ to the optimal Bayesian classifier, and uses an asymptotic expansion to derive an optimality criterion. Samworth first determines the optimal value for $K^{*}$-nearest neighbors based on the dimension of the data N and the number of samples J: $K^{*}=\lfloor B^{*}{J}^{4/N+4}\rfloor$. The weight for the kth nearest neighbor is then

$$w_k^{*}=\frac{1}{K^{*}}\left[1+\frac{N}{2}-\frac{N}{2{K^{*}}^{2/N}}\{k^{1+2/N}-{(k-1)}^{1+2/N}\}\right].$$

Note that this weighting, while proven combinatorially optimal, is not local to each neighborhood, as all neighborhoods use the same weight for their kth nearest neighbor.

Kernels can be used as a generalization of distance metrics. We are operating in an inner product space (Hilbert space), with some scalar product ${\langle ·,·\rangle }_{\mathcal{H}}$. The scalar product is seen as a measure of similarity between two data points; it is 0 if the data points are dissimilar, usually called orthogonal, and it increases as the data ‘aligns’. The scalar product induces a norm in this space as $||\mathit{x}||={\langle \mathit{x},\mathit{x}\rangle }^{\frac{1}{2}}$, and the norm induces a distance metric $d({\mathit{x}}_j,{\mathit{x}}_k)=||{\mathit{x}}_k-{\mathit{x}}_j||$. Now, given a possible non-linear feature map $\mathsf{\Phi }$ that maps data into a new feature space, we define $\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)=\langle \mathsf{\Phi }({\mathit{x}}_j),\mathsf{\Phi }({\mathit{x}}_k)\rangle$ meaning the kernel gives the value of the scalar product. The mathematical machinery with the representation theorem and Mercer’s theorem at the center is extensively studied in reference [8]. Conveniently, we only need to define a good kernel, and the similarity measure is implied. The task of choosing the correct kernel is still regarded as an open problem [14].

Weights chosen following a metric argument are computed from a function of the distance $d_{jk}$ between ${\mathit{x}}_j$ and its kth nearest neighbor ${\mathit{x}}_k$, following the idea that points that measure closer to ${\mathit{x}}_j$ should have a more influential vote. Some examples of weights $w_{j|k}$ that are associated with each j-neighbor-k pair are outlined in Table 2. The use of the | symbol in $w_{j|k}$ is to emphasize that these weights are not symmetric, as they are all locally scaled in some way with respect to the defining point of the neighborhood ${\mathit{x}}_j$. The weights are applied in the classification function as follows:

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J{\mathit{G}}_{j,c}{w}_{*|j}.$$

(2)

Following the ideas of weights and kernels, we can construct a measure of similarity. Points that have a high measure of similarity are more likely to belong to the same class, and the inverse is true as well. To construct a measure of similarity, we look to dimensionality reduction algorithms such as UMAP [15], Laplacian Eigenmaps [16] and t-SNE [17]. These techniques are designed to capture a measure of similarity in high dimensional space and preserve that measure of similarity in an embedding of the data in a lower dimensional, primarily for the purpose of visualization. However, the measure of similarity can also be used for classification following the idea that similar data points should belong to the same class.

Table 2. A selection of K-NN weights.

Equation	Name
$w_{j|k}=\frac{d_{j(K+1)}-d_{jk}}{d_{j(K+1)}-d_{j1}}$	WKNN [18]
$w_{j|k}=\frac{d_{j(K+1)}-d_{jk}}{d_{j(K+1)}-d_{j1}}\times \frac{d_{j(K+1)}+d_{jk}}{d_{j(K+1)}+d_{j1}}$	DWKNN [19]
$w_{j|k}=e^{-d_{jk}/d_{jK}}$	EXPKNN
$w_{j|k}=e^{-{(d_{jk}/d_{jK})}^2}$	NORKNN

Table 2. A selection of K-NN weights.

Equation	Name
$w_{j|k}=\frac{d_{j(K+1)}-d_{jk}}{d_{j(K+1)}-d_{j1}}$	WKNN [18]
$w_{j|k}=\frac{d_{j(K+1)}-d_{jk}}{d_{j(K+1)}-d_{j1}}\times \frac{d_{j(K+1)}+d_{jk}}{d_{j(K+1)}+d_{j1}}$	DWKNN [19]
$w_{j|k}=e^{-d_{jk}/d_{jK}}$	EXPKNN
$w_{j|k}=e^{-{(d_{jk}/d_{jK})}^2}$	NORKNN

The ‘go-to’ choice for similarity measures in the literature is Gaussian measures [17,20]. Interestingly, the dimensionality reduction community (in techniques such as UMAP [15] and Laplacian Eigenmaps [16]) use Laplacian measures of the form $w_{j|k}=e^{ad({\mathit{x}}_j,{\mathit{x}}_k)}$. These techniques are based on the manifold hypothesis [21], which assumes that the data are distributed on a manifold $(\mathcal{M},g)$ embedded in the input space. Thus, the similarity measure—which measures similarity based on some distance—should use the geodesic distance g as it best represents the underlying structure of the data.

However, as the manifold is not explicitly defined, [15,17,22] explore different ways of approximating (or in the case of [15], capturing) that geodesic distance. Specifically, UMAP works on the assumption that the dataset is distributed uniformly upon a Riemannian manifold, allowing for the geodesic distance to be measured by the Euclidean distance in sufficiently small local neighborhoods. This allows UMAP to ‘capture’ the geodesic distance instead of approximating it.

Finally comes the question of evaluating the success of the classifier. When evaluating a method of classification with a benchmark dataset, one must partition the data into a training set and a testing set. The training set is used for training the classifier. The classifier will make predictions on the testing set, and those predictions are compared back to the ground truth labels. From this, metrics such as accuracy can be derived. In the literature, when documenting the efficacy of methods of classification, data are usually divided using a train–test partition, or the data are divided into n-folds where each fold takes a ‘turn’ being the test set and all other folds are combined to create the training set. In both these methods, the success metrics (e.g., accuracy) are averaged across all the folds, or in the case of the test–train partition, averaged across a few trials of random partitions. Some common train–test split ratios are 66:33 [1], 70:30 [2,3], and 80:20 [23], and some common folds are 5-fold [24] and 10-fold [5,6,25,26]. Regardless of the ratio of the partition, the randomness of how the data points are divided affects the performance of the classifier, which impacts the repeatability of the experiment [27]. Abu Alfeilat et al. report the common performance measures of accuracy, precision, and recall. The method of measuring multi-class accuracy varies across different sources [28,29,30], which is reviewed in Section 5.2 with Equations (8) and (9). We have found that studies of classifiers on benchmark datasets do not always publish their method of measuring accuracy, and the ambiguity of the success metrics and train–test split creates a challenge when comparing the results from different researchers.

3. The Similarity Kernel

A kernel is a positive semi-definite mapping, specifically a similarity kernel $\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)$, which maps two elements of the dataset to a value between zero and one (inclusive); the closer the value is to one, the more similar the data points are considered. However unlike the weights from Table 2, by Mercer’s theorem [8] kernels are required to be symmetric, meaning $\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)=\mathcal{k}({\mathit{x}}_k,{\mathit{x}}_j)$. Another way to view the kernel approach is to consider Hilbert spaces and metrics. A kernel is the generalized idea of a distance metric. Given a mapping $\mathsf{\Phi }$, mapping the input space $\mathcal{X}$ to a new space (often called the feature space ${\mathcal{X}}^{\prime }$) one automatically obtains a similarity measure by defining $\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)=\langle \mathsf{\Phi }({\mathit{x}}_j),\mathsf{\Phi }({\mathit{x}}_k)\rangle$ by Mercer’s theorem.

By the representation theorem [8], any function can be expressed as a linear combination of the kernel function, and classification functions are no exception. Thus, the classifier $\mathrm{class}({\mathit{x}}_j)$ constructed using the similarity measurement is

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J{a}_k\mathcal{k}({\mathit{x}}_{*},{\mathit{x}}_j).$$

The question then becomes: what kernel best captures the similarities (and dissimilarities) of the data’s classes?

3.1. Theoretical Framework—Preserving the Topology

Inspired by the work of dimensionality reduction techniques (DRT) such as UMAP [15], Laplacian Eigenmaps [16], and t-SNE [17], a similarity measure is designed to capture the local and global structure of the dataset, thereby preserving the topology of the data. This stands in contrast to much of the existing research, for example [13], which designs optimal weights for K-NN classifiers based on combinatorics, or [1,2], which select/design best-performing weights based on experimental success instead of using a mathematical framework for justifying their design choices. The similarity measures in UMAP [15] and Laplacian Eigenmaps [16] use a Laplacian distribution, in contrast to t-SNE [17], which uses a Gaussian distribution as a Laplacian distribution has a longer tail, which is necessary for capturing the distances between points in high-dimensional space [31]. The following describes a topological justification for the choice of similarity kernel $\mathcal{k}$, which preserves the topology of the dataset.

• It is assumed the data points ${\mathit{x}}_j$ are distributed uniformly on a Riemannian manifold $(\mathcal{M},g)$ embedded in the vector space ${\mathbb{R}}^N$. This manifold represents the underlying natural structure of the data.

Then, naturally, the geodesic distance $g({\mathit{x}}_j,{\mathit{x}}_m)$ along the manifold should be used to measure the closeness of neighbors, but g is not explicitly defined for real-world datasets. However, a Riemannian manifold is locally Euclidean. A lemma presented in [15] outlines a strategy for measuring geodesic distance on a ‘local neighborhood’ scale. The lemma states:

2.

If g is locally constant in an open neighborhood U, then within a ball $\mathcal{B}\subseteq U$ with radius r of volume $\frac{{\pi }^{\frac{N}{2}}{r}^N}{\mathsf{\Gamma }(N/2+1)}$ centered at point ${\mathit{x}}_j$ the geodesic distance from ${\mathit{x}}_j$ to any point ${\mathit{x}}_k\in {\mathcal{B}}_i$ is $\frac{1}{r}d({\mathit{x}}_j,{\mathit{x}}_k)$ where d is the Euclidean distance in ${\mathbb{R}}^N$. This is because the geodesic distance in the neighborhood is bound by the Euclidean distance on the tangent plane at ${\mathit{x}}_j$.

Around each point ${\mathit{x}}_j$ on the Riemannian manifold, there exists a tangent space that is spanned by the tangent vectors. The neighbors of ${\mathit{x}}_j$ can be projected onto the tangent space. The geodesic distances between ${\mathit{x}}_j$ and its neighbors are bound by the Euclidean metrics implied by the scalar product of the tangent vectors on the tangent space. If the data are contained on a Riemannian surface, the local neighborhood as defined by the geodesic distance is also the local neighborhood determined using Euclidean distance. Thus, for sufficiently small neighborhoods, the local metric can be captured by the Euclidean distance metric.

The question that then remains is how can this be used to compute similarity? The solution is to capture the topology of the data with a graph. The nodes of the graph represent the data points and the edges, weighted with neighborhood-local measurements measured using Lemma 1 from [15] and connecting neighbors together.

3.

A simplex is a generalized triangle. From algebraic topology, it is known that a simplicial approximation of a manifold can be used to capture the topological aspects of that manifold [32].

We use the topology captured by the graph to make inferences about similarity based on the geodesic distance of the manifold. This follows the principle that the geodesic distance is the most intuitive metric to use when measuring similarity, allowing for the measure of similarity to be based on geodesic distance without explicitly knowing $g({\mathit{x}}_j,{\mathit{x}}_m)$.

4.

Similarity is a symmetric property.

The result is a non-directed graph that can be used as a tool to represent the topology of the dataset. A kernel that captures similarity based on the topology of the data can then be constructed from the graph, the technical details of which are outlined in Section 3.2.

3.2. The Locally Scaled Symmetric Laplacian Diffusion Kernel

Based on points 1, 2, and 3 above, a weight is first constructed. The weight is based on a Laplacian distribution that has been locally scaled between ${\mathit{x}}_j$ and K of its nearest neighbors

$$w_{j|k}({\mathit{x}}_j,{\mathit{x}}_k)=\left\{\begin{array}{cc}{e}^{\frac{d_{j1}}{{\sigma }_j}}{e}^{\frac{-d_{jk}}{{\sigma }_j}}\hfill & \mathrm{if}{n}_K({\mathit{x}}_j,{\mathit{x}}_k)=1\hfill \\ 0\hfill & \mathrm{else}\hfill \end{array}\right..$$

(3)

where the local scaling factor $exp(\frac{d_{j1}}{{\sigma }_j})$ is locally scaled to the neighborhood of ${\mathit{x}}_j$, using $d_{j1}$ as the distance from ${\mathit{x}}_j$ to its first nearest neighbor, which shifts the weights such that they all decay relative to the first-nearest-neighbor of the neighborhood, and ${\sigma }_j$ is chosen such that ${\sum }_{k=1}^K{w}_{j|k}=\alpha$. Natural choices for the parameter $\alpha$ are 2, ${log}_2(K)$, which is used by UMAP following combinatorial arguments, or $\sqrt{K}$. Table 7 in Section 6 quantifies the effects of $\alpha$ on classification accuracy. These weights are non-symmetric because the selection of K nearest neighbors is non-symmetric. The selection and order of the neighbors do not change by this local metric when compared to the Euclidean distance metric.

Furthermore, following point 4 above, the weights are symmetrized using

$${\widehat{\mathcal{k}}}_{jk}=w_{j|k}+w_{k|j}-w_{j|k}{w}_{k|j}.$$

Symmetrizing $w_{j|k}$ is necessary to obtain a proper similarity kernel ${\widehat{\mathcal{k}}}_{jk}$. Note that this method of symmetrization follows fuzzy set intersection, as described in UMAP [15] and not the arithmetic mean like t-SNE [17]. Practically, this means that if $w_{i|j}=1$ and $w_{j|i}=0$, symmetrizing results in ${\widehat{\mathcal{k}}}_{ij}=1$. Without this, points in a tightly knit cluster might not be able to capture their location in the larger structure of the data, thereby losing important global structure information.

Finally, the weights are normalized with

$${\mathcal{k}}_{jk}=\frac{{\widehat{\mathcal{k}}}_{jk}}{{\sum }_{m=1}^K{\widehat{\mathcal{k}}}_{jm}}.$$

A kernel matrix $\mathit{K}$ is constructed where ${\mathit{K}}_{j,k}={\mathcal{k}}_{jk}$ and ${\mathit{K}}_{j,j}=1$. This is the locally scaled symmetric Laplacian diffusion (LSSLD) kernel $\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)$.

3.3. Kernel Computational Complexity

Let us point out that time complexity is not equal to the time required to execute code, but rather the number of steps needed to solve the problem. Regardless of whether one is computing the time complexity of a covariance matrix, distance matrix, or kernel, all combinatorial pairs need to be generated and all dimensions visited. This results in a complexity of $O(J^{2}N)$, where J is the number of data points and N is the dimension of the input space. Computing the LSSLD kernel requires a normalization for each data point, and for this, we use Newton’s method, which is a constant time operation, to solve the non-linear equation.

4. Applications of Kernels in Classification

Many, if not most, of the commonly used machine learning algorithms (SVM, regression, ridge regression, random forest, etc.) can be kernelized; the algorithm takes as an input the values of the kernel evaluated on all pairs or mathematically, a dual space. We use the LSSLD kernel we defined in the previous section, Section 3.2, in the following methods of classification. Specifically, this research considers two methods of classification, the first is a blended-model of weighed K-NN and confidence voting (of which we consider three ratios of ‘blending’), and the second is kernel ridge regression.

The simplest approach to classification is a weighted K-NN classifier that utilizes the LSSLD kernel as weights

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J{\mathit{G}}_{j,c}\mathcal{k}({\mathit{x}}_{*},{\mathit{x}}_j).$$

(4)

4.1. Confidence Voting and the Blended-Model

Going one step further, the kernel could be used to measure the confidence of a point ${\mathit{x}}_j$ regarding its own class. Perhaps ${\mathit{x}}_j$ is an outlier, this can be assessed by measuring the similarity of ${\mathit{x}}_j$ to points of the same class. Confidence voting is closely linked with outlier detection [33]; if ${\mathit{x}}_j$ is similar to points that mostly belong to a different class, ${\mathit{x}}_j$ could be an outlier. To prevent misclassification of ${\mathit{x}}_{*}$, outliers should not be weighted heavily. Thus, confidences $c_{j,c}$ are assigned to each sample ${\mathit{x}}_j$ where $c_{j,c}={\sum }_{k=1}^J{\mathit{G}}_{k,c}\mathcal{k}({\mathit{x}}_j,{\mathit{x}}_k)$, such that the confidence reflects how certain ${\mathit{x}}_j$ is of belonging to class c. From this confidence matrix $\mathit{C}$, again a $J\times C$ matrix, can be constructed. Confidence voting can be used to curtail the negative effects from outliers with

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J{\mathit{C}}_{j,c}\mathcal{k}({\mathit{x}}_{*},{\mathit{x}}_j).$$

(5)

Confidence voting introduces a validation for each of the training points to determine if the labels implied from the similarity kernel are equivalent to the labels given in the training set, and the decision-making is based on these implied labels. As can be seen in Table 8, datasets known to contain outliers [34] (Heart, Wine, Balance, Australian, Ionosphere, Rice, Haberman) perform better with confidence voting.

A parameter $\beta$ represents the ‘trade-off’ between the proportion of the classification that is based on ${\mathit{G}}_{j,c}$ (the known labels of the class, or ground truth) and the proportion of the classification that is based on ${\mathit{C}}_{j,c}$ (the underlying structure of the data), leading to blended-model voting

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmax}}_c\sum _{j=1}^J\left((1-\beta ){\mathit{G}}_{j,c}+\beta {\mathit{C}}_{j,c}\right)\mathcal{k}({\mathit{x}}_{*},{\mathit{x}}_j).$$

(6)

Note that when $\beta =0$, the blended-model is equivalent to K-NN using the LSSLD weights, and when $\beta =1$, the blended-model is equivalent to confidence voting.

4.2. Regularization

This leads to the concept of regularization, a method that trades off, which effectively prevents over-fitting. The similarity kernel matrix $\mathit{K}$ that was defined in Section 3.2 can nicely be used in a regularization framework. A proposed regularization approach used in [35,36] based on kernel ridge regression (KRR) uses a locally scaled Gaussian kernel. The regularization framework in [35] learns a global classification as

$$\mathrm{class}({\mathit{x}}_{*})={\mathrm{argmin}}_{y_{*}}(1-\gamma ){(\mathit{I}-\gamma \mathit{K})}^{-1}\mathit{G}$$

(7)

where $\mathit{I}$ is the identity matrix, and $0<\gamma <1$ is the regularization parameter, assigned a value of $0.99$.

4.3. Classification Computational Complexity

For the classification complexity, we assume the weights or kernel have been pre-computed, and their complexity is outlined in Section 3.3. A weighted K-NN has a complexity of $O(J)$, independent of the dimension of the data N. Confidence voting requires the computation of the predicted class for each point resulting in a complexity of $O(J^2)$. Ridge regression is the most expensive method of classification as it requires the inversion of a matrix and has complexity $O(J^3)$.

5. Evaluation Methods

The following outlines our method of evaluating the LSSLD kernel-based classifiers. We could not directly compare the accuracy of the LSSLD kernel-based classifier to the accuracies of the classifiers in [1,18,19] as we found it challenging to reproduce their results. Some of the details surrounding their evaluation methods were ambiguous. Thus, we computed our own performance baseline of existing methods from [1,18,19] to compare the LSSLD kernel-based classifier against. Additionally, we describe our evaluations in detail below such that our results can be reproduced.

5.1. Datasets

This research uses 23 benchmark datasets from the UCI machine learning repository [11], as outlined in

Table 3. A summary of the datasets used in this research.

Dataset Name	Size	Dimensions	Num. Classes
Banknote	1372	4	2
Bioddeg	1055	41	2
Diabetes	768	8	2
EEG	14,980	14	2
Glass	214	9	7
Heart	270	13	2
Ionosphere	351	33	2
Iris	150	4	3
Lympho	148	18	4
Musk	6598	166	2
Parkinson	1040	27	2
Phoneme	5404	5	2
Rice	3810	7	2
Segmen	2310	19	7
Sonar	208	60	2
Vowel	528	10	11
Wine	178	13	3
Yeast	1484	8	10
Australian	690	14	2
Balance	625	4	3
Haberman	306	3	2
Monks	432	6	2
Vehicle	94	18	4

. These datasets are used as benchmarks in many areas of classification research [1,23,24,25,26,37,38] and vary in the number of points J, number of input dimensions N, and number of classes C. There are some notable remarks about the datasets that must be stated for the purpose of repeatability. To begin, for the Ionosphere dataset ($J=351,N=33$), either the 1st or 34th attribute can be interpreted as the label. This research uses the 34th attribute as the label, and the 1st attribute is included in the feature vector for $\mathit{x}$. The smallest dataset, Vehicle, has $J=94$, which prevents exploring values of $K>94$ in Tables 4 and 6 in Section 6 as K cannot exceed J in these classification methods. Additionally, some datasets such as Glass suffer from extremely unbalanced classes. In the case of Glass, classes 0 and 1 have approximately 70 elements, while classes 2 and 4 have less than 20. For class 5 with 9 elements, after partitioning the train–test sets, the training set has an insufficient 5 elements. In these cases, specifically, the train–test partition must be carefully selected to ensure all classes are represented in both sets.

5.2. Accuracy

Figure 1 is an example of a multi-class confusion matrix. Accuracy is a common metric of classifier success. Generally accuracy A can be described as

$$A=\frac{\mathrm{Number}\mathrm{of}\mathrm{correct}\mathrm{classifications}}{\mathrm{Total}\mathrm{number}\mathrm{of}\mathrm{test}\mathrm{samples}}.$$

The question is, what is considered a correct classification? In the two-class case, the answer is obvious and well-agreed upon. The ‘number of correct classifications’ in the two-class case is the sum of the two diagonal entries in the confusion matrix (true positives and true negatives). This is independent of the class one considers as ‘positive’, and thus accuracy is also independent of class:

$$A=\frac{\mathrm{TP}+\mathrm{TN}}{\mathrm{TP}+\mathrm{TN}+\mathrm{FP}+\mathrm{FN}}.$$

(8)

However, if there are more than two classes, what is considered a ‘correct classification’ varies depending on the source. Following the work in [29,30], this work considers both true positives and true negatives as ‘correct’ in the multi-class case, thus the accuracy $A_c$ depends on the class:

$$A_c=\frac{{\mathrm{TP}}_c+{\mathrm{TN}}_c}{{\mathrm{TP}}_c+{\mathrm{TN}}_c+F{P}_c+F{N}_c}.$$

In this research, to produce a single accuracy measurement the accuracies are averaged across all classes.

$$A=\frac{{\sum }_{c=1}^C\frac{{\mathrm{TP}}_c+{\mathrm{TN}}_c}{{\mathrm{TP}}_c+{\mathrm{TN}}_c+{\mathrm{FP}}_c+{\mathrm{FN}}_c}}{C}.$$

(9)

As stated, not all sources agree on this method of calculating multi-class accuracy, for example, ref. [28] does not include true negatives as ‘correct classifications’ and thus when measuring accuracy only considers entries on the diagonal of the confusion matrix as ‘correct’. This results in an entirely different measure of accuracy. In examples using UCI datasets where the method of calculating accuracy is ambiguous [1,24,25,37], it is not possible to compare the accuracy of a new method of classification to their published baseline. A consistent and clear definition of accuracy is essential for establishing a repeatable baseline. Therefore, the method of calculating accuracy in this research is made explicitly clear in Equation (9).

5.3. Train–Test Split

The question of how to partition the data into a training set and testing set is also an important consideration. In the literature, a common approach is to split the benchmark datasets with a 66:33 [1], 70:30 [2,3] or 80:20 [23] train–test partition. The success of the classifier is partially dependent on which data are in the training set and which data are in the testing set, especially in small datasets or datasets with under-represented classes. When the partitions are not published, it can be difficult to reproduce the results.

The histogram in Figure 2a illustrates classification accuracy on 100 random 60:40 partitions of the ‘smaller’ dataset Heart. From this histogram, it is clear that the choice of partition can significantly impact the accuracy. Here, the accuracy varies by $20\%$.

To obtain more objective, repeatable, and accurate metrics of success, n-fold testing is often used, which divides the data into n sets and iterates through the train–test process n times, each time reserving one of the n sets for testing and using the others for training, before averaging the success metrics of all n iterations. Averaging across n folds improves the consistency of the success metrics but still relies on a random partitioning of the n sets that could lead to inconsistencies when the experiment is reproduced. Figure 2b illustrates the distribution of accuracy for 100 randomly selected fold partitions for folds-of-10 trials. The accuracy varies by $6\%$ even with the 10-fold method. In many cases of comparing two or more classifiers, the reported gain in accuracy is only 1 or 2 percent, well within this range of variance.

Additionally, for both the train–test partitioning and the n-fold testing, the effect of the distribution of the classes between the train–test partition can have a very significant impact on accuracy, as picking 10 samples at random in a multi-class problem does not ensure each class is represented appropriately in the test and training sets. We illustrate that the problems we encounter with the train–test partition or n-fold method are not related to the ratios of the partitions themselves but to the randomness in determining which data points belong to which set. It was observed during experimentation that it is very easy to overestimate the success of a classifier by selecting partitions that favor higher accuracy results.

To create an objective and repeatable baseline, this research uses leave-one-out testing, which means each sample is to be tested against all other samples, resulting in a 1:J train–test ratio. It is commonly agreed in the validation literature that leave-one-out testing, while computationally more expensive, has a consistent performance [39]. Leaving every sample in the dataset out exactly once results in a consistent metric of success. Leave-one-out testing is efficient to compute for blended-model classification as the kernel is only computed once for all data points, and the matrix G, the known labels, is updated in place for each test.

5.4. Pre-Processing

Finally, the method of preparing the data must be addressed in order to reproduce these results. All datasets were scaled dimension-wise between $[0,1]$. No feature extraction or reduction (e.g., PCA) is performed on the data in this experiment.

6. Experimental Results

We implemented a classification system using C++ with the Eigen library [40], and an additional system was implemented in Python to verify consistency across languages. The system performs classification on datasets using methods including K-NN with distances from Table 1, weighted K-NN with weights from Table 2, and the LSSLD kernel techniques outlined in Section 4.

In the traditional K-NN classifiers, distances can be computed on-demand during or prior to testing. However, using a LSSLD kernel requires the kernel to be computed prior to testing as it has a local scaling factor that must be precomputed. The local scaling factor computation requires solving a non-linear equation with Newton’s method, which is efficient and converges quickly. Specifically, the solver computed for a maximum of 10 iterations or until a tolerance of $\pm 0.001$ was reached. In addition to computing the nearest neighbors of each data point, confidence voting requires the normalization of each row and symmetrizing the kernel weights, both constant in the number of data points.

In place of using a boldface font to indicate the highest accuracy of each dataset, we have chosen to present the results with a fuchsia gradient. The highest accuracy for each dataset is highlighted with a $100\%$ saturation, and correspondingly decreasing to a zero percent saturation for accuracies with a difference of $0.02$ or less from the best.

6.1. Baselines

To establish a baseline, we ran K-NN classifier using four of the distance metrics from Table 1: the Euclidean distance, Hassanat distance (as it was presented to be the best option in general, as reported in [1]), cosine distance, and Manhattan distance. Their accuracy from leave-one-out testing is presented in

Table 4. Accuracy of 4 popular distance metrics for a K-NN classifier from Equation (1). The metrics for both $K=1$ and the best K (i.e., the K that results in the best accuracy) are presented, with the best K in brackets. The final column is the range that the accuracies from different distance metrics span, considering only the four best K columns presented here.

. Note that the optimal K is presented in brackets for each metric, as searched for in the range of $[1,99]$. This is computationally expensive and creates a tough baseline for the LSSLD kernel classifier to compare with. In a few cases (e.g., EEG ), the classification accuracy is consistent across all metrics; however, for most datasets, there is at least one metric that outperforms the others. In some cases, choosing an ill-suited distance metric for a particular dataset can result in a greater than $20\%$ loss of accuracy. Furthermore, only using 1-NN for any one distance metric (such as in [1]) could result in a $10\%$ loss of accuracy or greater. It is evident from the last column that the accuracy of the classifier varies greatly with the choice of metric, and either significant computation effort should be made to determine the best operating parameters for each dataset or a method that achieves consistent accuracy regardless of operational parameters should be used.

Figure 3 shows, as is well known, that the accuracy of a K-NN classifier is very sensitive to the value of K and in most cases degenerates as K increases, varying substantially in the process. In contrast, the proposed LSSLD KRR and LSSLD kernel confidence vote classifiers have a nearly flat curve, the dependence on K is minimal, and the accuracy is consistent with increasing K.

Table 5. Accuracy of a weighted K-NN classifier using popular choices of weights from Table 2 and best K from $K=5,10,20,50$.

presents the baseline accuracy results of four popular weighted K-NN techniques. It is evident that most datasets tend to achieve good accuracy with the WKNN/WDKNN weights or the EXPKNN/NORKNN weights but usually not both. Interestingly, WDKNN [19], which was presented as an improvement on WKNN, reports identical accuracy to WKNN when comparing accuracy using leave-one-out testing. The authors interpret this as support for the use of leave-one-out testing to achieve consistent evaluation metrics that consistently capture the accuracy of the classifier.

6.2. One Tuning for All

One key objective was to design a kernel-based classifier for which one value for each operating parameter (in this case K, $\alpha$, and $\beta$) would work well for all datasets. Without this insensitivity, the operating parameters would have to be selected using trial and error, which is a computationally expensive task and not practical in application.

Table 6. Accuracy of different LSSLD kernel-based classifiers (LSSLD K-NN, confidence voting, kernel ridge regression) with $\alpha =2$ and varying K.

presents the accuracy of three LSSLD classifiers: K-NN weighted with LSSLD weights (i.e., blended-model with $\beta =0$), confidence voting (i.e., blended-model with $\beta =1$), and KRR. As in Table 5, the accuracies of the kernel-based classifiers are quite stable with respect to K but do vary across the three methods of classification. Notably, the most computationally expensive method, KRR, does not significantly outperform the other less computationally expensive methods; for most datasets, it does not outperform the other methods at all.

Table 7. Accuracy of a LSSKD K-NN classifier (4) using LSSLD weights and varying parameter $\alpha$, here $K=20$.

demonstrates the effect of $\alpha$ on the kernel-based classifier’s accuracy. From this, it is clear that the best choice for $\alpha$ varies across datasets, but in most cases, the choice of $\alpha$ has little impact on the classification accuracy.

Finally,

Table 8. Accuracy of a blended-model classifier (6) using LSSLD weights and varying parameter $\beta$, here $K=20$ and $\alpha =2$.

reports the accuracy of the blended-model classifier. The trend seems to indicate that the kernel-based classifier has higher accuracy on some datasets with $\beta =0$, indicating the given labels of the data are preferred to make successful classifications, whereas the kernel-based classifier has higher accuracy on other datasets when $\beta =1$, indicating the labels inferred by the kernel are preferred to make successful classifications. One interpretation of this phenomenon is that datasets that report a higher accuracy with $\beta =1$ might have more outliers or mislabeled points. From Table 8 $\beta$ of $0.5$ produces the most consistently high accuracy.

6.3. LSSLD Kernel Comparison

Table 9. Comparing three LSSLD classifiers ($\alpha =2$, $K=10$) to the most accurate K-NN distance metric with the most accurate K.

	LSSLD K-NN ($\mathit{\beta }=0$)	Blended ($\mathit{\beta }=0.5$)	Confidence Vote ($\mathit{\beta }=1$)	Best K-NN	Difference to Best
Banknote	0.999	0.999	0.999	0.999	$\phantom{-}$0.000
Biodeg	0.863	0.871	0.851	0.867	−0.004
Diabetes	0.760	0.764	0.753	0.759	−0.005
EEG	0.985	0.981	0.970	0.982	−0.003
Glass	0.924	0.925	0.904	0.923	−0.002
Heart	0.789	0.807	0.804	0.826	$\phantom{-}$0.019
Ionosphere	0.875	0.889	0.897	0.906	$\phantom{-}$0.009
Iris	0.964	0.969	0.969	0.978	$\phantom{-}$0.009
Lympho	0.905	0.912	0.895	0.929	$\phantom{-}$0.017
Musk	0.972	0.968	0.960	0.975	$\phantom{-}$0.003
Parkinson	0.926	0.921	0.901	0.931	$\phantom{-}$0.005
Phoneme	0.900	0.899	0.882	0.913	$\phantom{-}$0.013
Rice	0.909	0.918	0.927	0.929	$\phantom{-}$0.002
Segman	0.991	0.990	0.988	0.993	$\phantom{-}$0.002
Sonar	0.865	0.856	0.837	0.875	$\phantom{-}$0.010
Vowel	0.999	0.998	0.994	0.999	$\phantom{-}$0.000
Wine	0.974	0.978	0.981	0.989	$\phantom{-}$0.008
Yeast	0.910	0.915	0.921	0.920	−0.001
Australian	0.832	0.838	0.851	0.875	$\phantom{-}$0.024
Balance	0.881	0.906	0.958	0.991	$\phantom{-}$0.033
Haberman	0.706	0.706	0.735	0.775	$\phantom{-}$0.040
Monks	0.933	0.884	0.792	0.998	$\phantom{-}$0.065
Vehicle	0.793	0.771	0.755	0.819	$\phantom{-}$0.026

compares the accuracies of the LSSLD kernel-based classifier methods to the accuracy of the K-NN classifier from Table 4 with the highest accuracy (selected across all distance metrics and values of K). As the accuracies of the three LSSLD classifiers do not vary much with respect to their operating parameters, the parameters have been set to $K=10$, $\alpha =2$, and $\beta =0.5$ where applicable. Additionally, running the LSSLD classifier with three different values of $\beta$ ($\beta =0,0.5,1$) only requires one computation of the kernel matrix as the kernel matrix does not depend on $\beta$. Table 9 demonstrates that the LSSLD classifier techniques have comparable, if not better, accuracies than the best K-NN metric-K combination, with the additional benefit of requiring significantly less computational effort, as the specific operating parameters do not have a major influence on the accuracy.

The LSSLD methods are less accurate on datasets that violate the manifold hypothesis [21] (Vehicle, Australian, Balance) and especially on data that are artificial (Haberman) or combinatorial (Monks). For that reason, those datasets have been listed at the bottom of Table 9 and

Table 10. Comparing three LSSLD classifiers ($\alpha =2$, $K=10$) to the most accurate weighted K-NN classifier.

	LSSLD K-NN ($\mathit{\beta }=0$)	Blended ($\mathit{\beta }=0.5$)	Confidence Vote ($\mathit{\beta }=1$)	Best Weighted K-NN	Difference to Best
Banknote	0.999	0.999	0.999	0.999	0.000
Biodeg	0.863	0.871	0.851	0.847	−0.016
Diabetes	0.760	0.764	0.753	0.742	−0.002
EEG	0.985	0.981	0.970	0.982	−0.003
Glass	0.924	0.925	0.904	0.915	−0.010
Heart	0.789	0.807	0.804	0.822	0.015
Ionosphere	0.875	0.889	0.897	0.897	0.000
Iris	0.964	0.969	0.969	0.973	0.004
Lympho	0.905	0.912	0.895	0.902	−0.010
Musk	0.972	0.968	0.960	0.963	−0.009
Parkinson	0.926	0.921	0.901	0.913	−0.013
Phoneme	0.900	0.899	0.882	0.908	0.008
Rice	0.909	0.918	0.927	0.927	0.000
Segman	0.991	0.990	0.988	0.993	0.002
Sonar	0.865	0.856	0.837	0.875	0.010
Vowel	0.999	0.998	0.994	0.999	0.000
Wine	0.974	0.978	0.981	0.981	0.000
Yeast	0.910	0.915	0.921	0.918	−0.003
Australian	0.832	0.838	0.851	0.862	0.011
Balance	0.881	0.906	0.958	0.966	0.008
Haberman	0.706	0.706	0.735	0.755	0.020
Monks	0.933	0.884	0.792	0.988	0.055
Vehicle	0.793	0.771	0.755	0.803	0.010

.

Table 10 compares the accuracies of the LSSLD kernel-based classifier methods to the accuracy of the weighted K-NN classifier from Table 5 with the highest accuracy (selected across all weights and values of K). Again, the LSSLD methods have comparable, if not better, accuracies than the weighted K-NN techniques but require significantly less computation effort thanks to their consistency in accuracy over the operating parameters.

7. Conclusions

Determining the best choice of operating parameters, the first step in many methods of classification, is critical for the the accuracy of the classifier used. The dimensionality reduction community developed methods aimed at capturing/learning the topological structure of the training data. We present a kernel approach, using a Laplacian kernel with local scaling.

Experiments using benchmark data sets demonstrate that the LSSLD kernel achieves comparable leave-one-out prediction accuracy scores using one single tuning/set of parameters for all data sets to weighted and non-weighted K-NN classifiers tuned over a variety of metrics or weights and neighborhood sizes tuned for each data set individually. Using confidence voting, representing a trade-off between the given labels and the labels implied by the kernel further confirms that the presented kernel is a promising step towards a ‘one tuning for all’ classifier.

8. Future Work

Inspired by the success of the LSSLD kernel, we want to further research the methods of kernel construction that capture similarity. The accuracy of the LSSLD kernel was satisfactory, but we believe accuracy could be improved further, especially regarding datasets that did not satisfy the manifold hypothesis (Vehicle, Australian, Balance, Haberman, Monks), as mentioned in Section 6.3. One way the classification accuracy might be improved is by utilizing the label information of the dataset in the construction of a kernel. As kernels can be linearly combined to construct ‘new’ kernels, the LSSLD kernel could be enhanced with ‘supervised’ kernels constructed with the information provided by the labels to create ‘semi-supervised’ kernels. We also could continue to explore the relationship between functions of classification and kernels, and how the classifier decisions could be encapsulated in the kernel.