A new locally adaptive K-nearest centroid neighbor classification based on the average distance

Abstract

The classification performance of a k-nearest neighbour (KNN) method is dependent on the choice of the k neighbours of a query. However, it is difficult to optimise the performance of KNN by choosing appropriate neighbours and an appropriate value of k. Moreover, the performance of KNN suffers from the use of a simple majority voting method. To address these three issues, we propose a new locally adaptive k-nearest centroid neighbour classification based on the average distance (AD-LAKNCN) in this paper. First, the k neighbours of the query based on the nearest centroid neighbour (NCN) are found, and the discrimination classes with different k values are derived from the number and distribution of each class of neighbours considered in the query. Then, based on the distribution information in the discrimination class for each k, the adaptive k and the final classification result are obtained. The experimental results based on 24 real-world datasets show that the new method achieves better classification performance than nine other state-of-the-art KNN algorithms.

KEYWORDS:

• K-nearest neighbor
• k-nearest centroid neighbor
• average distance
• adaptive k value

1. Introduction

Classification is the core of pattern recognition, machine learning and data mining. Its essence is to determine which predefined target class to which an object belongs. Considerable attention has been focused on this field, and we have widely applied it in emotion classification (Wang et al., 2021; Wei et al., 2022; Zhang et al., 2022) and food nutrition matching (Zhu et al., 2020). At present, the main classification methods include support vector machines (SVMs), decision trees, Bayesian classification, k-nearest neighbour (KNN) classification, and neural networks. Among these methods, the KNN classification algorithm (Cover & Hart, 1967) is a simple, effective and nonparametric method. It is also considered one of the top ten algorithms in data mining (Wu et al., 2008). Additionally, in the Bayesian sense, it has been proven that under the constraint of $k/N\to 0$, its performance increases gradually with an increasing number of samples $N$ (Guo & Dyer, 2005).

While the KNN algorithm has many advantages, it still has some unavoidable problems. First, on small-scale datasets, sparse distribution, imbalance and noise problems (Wen et al., 2012) seriously affect the classification performance. Second, the classification effect is sensitive to the choice of $k$. If $k$ is too small, the classification result is susceptible to noise points. If $k$ is too large, there may be more samples with other classes in the neighbourhood, which may cause classification errors for the query point, especially for datasets with unbalanced samples (Gou et al., 2012). Third, when the $k$ neighbours of the query point are selected, only the distance is considered, and the distribution near the query point is not considered. Additionally, the majority voting method is generally used in neighbourhood classification; that is, the class of the query point is determined by the class of the majority of the $k$ neighbours. This decision mechanism is simple and rough and does not take into account the distribution of the remaining classes of the $k$ neighbours of the query point. To address the above problems, researchers have proposed many improved KNN-based methods. Next, some of the most advanced KNN-based algorithms are briefly introduced.

Because the KNN algorithm does not consider the weight of each neighbouring point, Dudani developed a weighted voting method called the distance-weighted KNN (WKNN) algorithm (Dudani, 1976). The basic idea is to give more weight to samples closer to the query point. Subsequently, Rastin et al. developed a k-nearest neighbour stacking method that uses a feature-weighted distance measure to reduce the effect of irrelevant classes in stacking (Rastin et al., 2021). Both of the above methods consider the weight of each neighbouring point, but the reality of choosing weights is that it is insufficient to only consider the distance information.

To solve the problem of the sensitivity of the KNN algorithm to noise points, Mitani et al. presented a local mean KNN (LMKNN) algorithm (Mitani & Hamamoto, 2006); this algorithm uses the local mean vector of $k$ neighbours from each class to determine the query point class. However, LMKNN does not consider the weight of each neighbouring point. On this basis, Zeng et al. considered the weighted sum of the distances of the neighbours in each class and presented a pseudonearest neighbour (PNN) rule (Zeng et al., 2009). Gou et al. extended the PNN algorithm and presented a local mean-based pseudonearest neighbour (LMPNN) algorithm (Gou et al., 2014); this algorithm eliminates the influence of outliers by using the $k$ local mean vectors of the neighbours in each class instead of themselves. Moreover, Gou et al. presented a local mean representation-based k-nearest neighbour algorithm (LMRKNN), which uses the multi-local mean vectors of the class-specific $k$ nearest neighbours to linearly represent the testing sample (2019). The above methods mainly use the local mean vectors to eliminate the influence of outliers and achieve satisfactory classification performance. However, the above methods are still sensitive to the selection of the $k$ value.

To address the sensitivity of the KNN algorithm to the choice of $k$, researchers have proposed different schemes to adaptively choose the appropriate $k$. Mullick et al. used the density and distribution information of the query point's neighbours and used neural networks to learn an appropriate $k$ (Mullick et al., 2018). Gou et al. proposed a generalised mean distance-based k-nearest neighbour classifier (GMDKNN) by introducing multiple generalised mean distances and the nested generalised mean distance (Gou et al., 2019). Moreover, a locally adaptive KNN based on discrimination classes (DC-LAKNN) was also proposed that can not only choose $k$ adaptively but also consider the role of the second-most-common class of neighbours in the classification process (Pan et al., 2020). In order to obtain more convincing and reliable local mean vectors, a globally adaptive k-nearest neighbour classifier based on local mean optimisation was developed (Pan et al., 2021). The above methods choose the $k$ value adaptively through different schemes and improve the classification performance of the KNN-based algorithm.

To address unreliability in the selection of the neighbour points, Chaudhuri presented the nearest centroid neighbour (NCN) method (Chaudhuri, 1996), which focuses on the neighbourhood of the query point and employs the ideas of distance and symmetry criteria. Based on the NCN, Sanchez et al. proposed a k-nearest centroid neighbour (KNCN) classification algorithm (Śanchez et al., 1997), which ensures the accuracy of classification and has been proven to be valid in many fields (Śanchez & Marqúes, 2006). To combine the robustness of LMKNN and the validity of KNCN, local mean-based k-nearest centroid neighbour (LMKNCN) was proposed, which uses the local average vectors of the neighbours of each class to determine the class of the query point (Gou et al., 2012). Furthermore, Ma et al. used the ideas of PNN and LMKNCN to propose the pseudo nearest centroid neighbour (PNCN) method, which not only considers the local mean vector of the NCN but also incorporates the weighted sum of the distances of the neighbours in each class (Ma et al., 2018). Moreover, Gou et al. proposed a representation coefficient-based k-nearest centroid neighbour (RCKNCN) method, which is able to capture both the proximity and the geometry of the k-nearest neighbours and learns to differentiate the contributions of the neighbours to the classification of a testing sample through a linear representation method (Gou et al., 2022). These KNN-based methods above mainly use the NCN to select the neighbour points and achieve excellent classification performance.

To further overcome the sensitivity to $k$ and improve the KNN-based classification performance, we present a new method for locally adaptive k-nearest centroid neighbour classification based on the average distance (AD-LAKNCN). First, $k$ neighbours of the query based on the NCN are found, and the discrimination classes with different $k$ are derived from the number and distribution of each class of the query's neighbours. Then, based on the distribution information in the discrimination class for each $k$, the adaptive $k$ and the final classification result are obtained.

The main contributions of this paper are as follows:

• The NCN method is applied to query point neighbour selection. The advantage of this method is that when selecting the query point's neighbours, the principle of neighbours and symmetry is followed so that the query point is surrounded by the selected neighbours.

• In AD-LAKNCN, the average distance based on multilocal mean vectors is used to select the discrimination class of the query point. The advantage is that when selecting a query point discrimination class, our method not only makes the number of discrimination class samples as large as possible but also makes the centroid of the discrimination class as close as possible to the query point.

• We propose a new adaptive $k$ value choice method. The choice of the $k$ value is determined by the number of neighbours of the discrimination class and the distance between the centroid of the discrimination class and the query at different $k$ values. This method can fully utilise the information of the discrimination class and diminish the sensitivity to the selection of the $k$ value.

The rest of this article is organised as follows. In section 2, we discuss the related methods. In section 3, we introduce the AD-LAKNCN algorithm in detail. To verify our proposed AD-LAKNCN algorithm, a large number of comparative experiments with nine other state-of-the-art KNN-based algorithms are presented in section 4, and the parameters and complexity are discussed. Finally, the conclusions are given in section 5.

2. Related work

In this section, we briefly discuss two related KNN-based classifiers. They are the KNCN and the DC-LAKNN.

For convenience of representation, the following notations are specified: Let$T=\left\{\right(x_i,c_i){\}}_{i=1}^N$ denote a training set with $N$ instances from $M$ classes, $x_i$ be a training sample in $d$-dimensional space, $c_i$ be the corresponding class label of $x_i$ and the $M$ classes be represented as $C=\{{\omega }_1,{\omega }_2,\dots ,{\omega }_M\}$.

2.1. KNCN

To address the unreliability in the selection of the neighbour points in KNN, Sanchez et al. proposed a KNCN classification algorithm (Śanchez et al., 1997). Its classification process considers the distance on the one hand and the distribution of the query point's neighbours on the other hand, which ensures the accuracy of classification. The KNCN predicts its class label as follows:

1. Find the nearest neighbour of $\overline{x}$, say $x_1^{NCN}$;

2. Find the $k$ nearest centroid neighbours of $\overline{x}$:

For $i=2$ to $k$ do $x_i^{NCN}=\arg \underset{\overline{T}}{min}f\left(\frac{1}{i}\right(\overline{T}+\sum _{j=1}^{i-1}{x}_j^{NCN}),\overline{x})$

EndFor

where $f$ is the Euclidean distance and $\overline{T}$ represents the remaining training samples yet to be chosen.

1. The majority voting rule is used to assign the query $\overline{x}$ to the class ${\omega }_c$: ${\omega }_c=\arg max\sum _{j=1}^k\delta ({\omega }_i=c_j^{NCN}),i=1,2,\dots ,M$

where $c_j^{NCN}$ is the class label of $x_j^{NCN}$ and $\delta$ is the Kronecker delta function.

Based on the rationale of the KNCN, it has proven to be an excellent classifier (Śanchez & Marqúes, 2006). However, directly taking the majority class as the classification decision result based on the majority voting rule is arbitrary. Moreover, the KNCN is still sensitive to the selection of the $k$ value.

2.2. DC-LAKNN

In the classification process of the KNN algorithm, only majority class neighbours in the $k$ neighbourhood are used, regardless of the role of all other remaining nearest neighbours. Additionally, KNN are sensitive to the selection of $k$. To address the above two issues, DC-LAKNN presents a new $k$ value selection method and considers the role of the second-most common class of neighbours in the classification process (Pan et al., 2020). Given a query $\overline{x}$, DC-LAKNN works as follows:

Stage 1: Selection of the discrimination class.

1. Use Euclidean distance metrics to choose the $k$ nearest neighbours $N{N}_k\left(\overline{x}\right)=\left\{\right(x_i^{NN},c_i^{NN}){\}}_{i=1}^k$ from the training set $T$.

2. Find the majority classes $\left\{\right(w_{1st,i}^k,r_{1st}^k){\}}_{i=1}^{nu{m}_{1st}^k}$ and secondary majority classes $\left\{\right(w_{2nd,i}^k,r_{2nd}^k){\}}_{i=1}^{nu{m}_{2nd}^k}$ in the $k$ neighbours, where $num$ and $r$ are the number of majority and secondary majority classes and the number of majority and secondary majority class neighbours, respectively.

3. Based on multiple local mean vectors, compute the centroids in the majority classes and secondary majority classes $\{cen{t}_{1st,i}^k{\}}_{i=1}^{nu{m}_{1st}^k}$, $\{cen{t}_{2nd,i}^k{\}}_{i=1}^{nu{m}_{2nd}^k}$.

4. Select the discrimination class $w_{disc}^k$ as follows:Case 1: If $nu{m}_{1st}^k=1$, then $w_{disc}^k=w_{1st,1}^k$ when $r_{1st}^k/r_{2nd}^k>\theta$; otherwise, $w_{disc}^k=\arg min\left\{d\right(\overline{x},cen{t}_{1st,1}^k),d(\overline{x},cen{t}_{2nd,i}^k\left)\right\},i=1,2,\dots ,nu{m}_{2nd}^k$; Case 2: If $nu{m}_{1st}^k>1$, then $w_{disc}^k=\arg \underset{w_{1st}^k,i=1,2,\dots ,nu{m}_{1st}^k}{min}d(\overline{x},cen{t}_{1st,i}^k)$.

5. Record the centroid of nearest neighbours $cen{t}_{disc}^k$ and the number $r_{disc}^k$ in the discrimination class.

Stage 2: Selection of the adaptive $k$ value and classification procedure.

1. Calculate the distance $d^k=d(\overline{x},cen{t}_{disc}^k)$ between $\overline{x}$ and each $cen{t}_{disc}^k$ to obtain$d=\{d^k{\}}_{k=1}^{kmax}$ and sort the $d$ values in ascending order to obtain $ran{k}_d=\{ran{k}_d^k{\}}_{k=1}^{kmax}$; calculate the $rati{o}^k=r_{disc}^k/k$ for the selected discrimination class for all neighbours to obtain $ratio=\{rati{o}^k{\}}_{k=1}^{kmax}$ and sort the $ratio$ values in descending order to obtain $ran{k}_{ratio}=\{ran{k}_{ratio}^k{\}}_{k=1}^{kmax}$.

2. Calculate the average rank of each $k$: $ran{k}_{ave}^k=(\frac{ran{k}_{ratio}^k}{{max}_{k=1,2,\dots ,kmax}ran{k}_{ratio}^k}+\frac{ran{k}_d^k}{{max}_{k=1,2,\dots ,kmax}ran{k}_d^k})/2,$$k=1,2,\dots ,kmax$. Choose the class corresponding to the $k$ with the smallest average rank as the class of the query point $w_c=c_{\arg min\left(ran{k}_{ave}^k\right)}$.

Based on the rationale of DC-LAKNN, considering the role of the second-most common class of neighbours based on the KNN and using the adaptive $k$ value selection method can achieve satisfactory classification performance. However, DC-LAKNN still has the following issues:

1. The nearest neighbour selection method based on the KNN method is unreliable because it considers only the distance and does not consider the distribution near the query point.

2. In the classification process, only the majority classes and secondary majority classes are considered, which is incomplete.

3. In the adaptive $k$ value selection process, directly using the mean of the two ranks to determine the final $k$ is arbitrary.

3. The proposed method

In section 3.1, we introduce the motivation for the AD-LAKNCN. In section 3.2, we describe the AD-LAKNCN algorithm in detail. In section 3.3, we present the pseudocode of the AD-LAKNCN algorithm. In section 3.4, we analyze the differences between the proposed AD-LAKNCN and the related methods.

3.1. Motivation

While the KNN algorithm has many benefits, it still has some issues. In the remainder of this section, we will elaborate on three issues and introduce our motivation.

Issue 1: The nearest neighbour selection method based on the nearest neighbourhood criterion is unreliable

In KNN-based methods, the nearest neighbourhood (NN) criterion is the only criterion for selecting neighbours. In contrast, the NCN criterion focuses on the distribution of the query point and employs the concepts of distance and symmetry criteria (Chaudhuri, 1996). Moreover, the NCN method has been proven to be effective in multiple KNN-based algorithms (Gou et al., 2012; Gou et al., 2022; Ma et al., 2018; Śanchez et al., 1997).

As an example, in Figure 1, the point set contained in the blue circle represents the set of neighbours of the query point obtained by the NN method, and the point set contained in the black circle represents the set of neighbours of the query point obtained by the NCN method. Although the blue circle contains the nearest neighbourhood set, the neighbour set obtained by the NCN method not only is near the query point but also surrounds the query point, which is more reasonable.

Figure 1. Three examples of the NN and NCN.

Therefore, we use the NCN method to select the nearest neighbour to improve the classification performance.

Issue 2: It is arbitrary to consider only the majority class

In the classification process of KNN, the majority class of the neighbours of the query is used directly as the result of the classification decision. That is, the classification process does not consider other classes of the neighbours of the query. For this reason, DC-LAKNN uses the information of the majority classes and the secondary majority classes to select the discrimination class, and it obtains satisfactory classification performance.

Inspired by the classification process of DC-LAKNN, we use the average distance between the query and the centroids of all classes of its $k$ neighbours to determine the discrimination class. This is advantageous for selecting a query point discrimination class because our method not only makes the number of discrimination class samples as large as possible but also makes the centroid of the discrimination class as close as possible to the query point.

Issue 3: The classification effect is sensitive to the choice of $k$

It is difficult to select an appropriate $k$ in KNN. If $k$ is too small, the classification result is susceptible to noise points. If $k$ is too large, there may be more samples with other classes in the neighbourhood, which may cause classification errors for the query point, especially for datasets with unbalanced samples. To address this problem, DC-LAKNN uses the ratio of the number of nearest neighbours in the discrimination class to the number of all nearest neighbours and the distances between the centroids of the nearest neighbours in the discrimination class and the query to adaptively select$k$. However, it is arbitrary to directly use the mean of the ratio rank and the distance rank to determine the final $k$. Thus, we redesign the $k$ value selection method to improve the classification performance.

As a result, the main noteworthy characteristics of the proposed AD-LAKNCN are derived from the NCN method, the new discrimination class selection method and the new $k$ value selection method. In the next section, the AD-LAKNCN algorithm is described in detail.

3.2. The proposed AD-LAKNCN

In AD-LAKNCN, the classification process consists of two stages. Stage 1 selects the discrimination class of the query point under each $k$ value, and stage 2 adaptively selects the best $k$ value. Here, we describe the details of these two stages.

Stage 1: For $k=1$ to $kmax$, the best centroid $cen{t}_k$ for each $k$ is found as follows:

1. According to the NCN method, find $k$ neighbours $T_k^{NCN}\left(\overline{x}\right)=\{x_i^{NCN}{\}}_{i=1}^k$ of the query point $\overline{x}$ in the training set $T=\{x_i{\}}_{i=1}^N$;

2. Collate the point set $T_k^{NCN}\left(\overline{x}\right)=\{T_{kl}^{NCN}{\}}_{l=1}^M$ and the number set $nu{m}_k=\{nu{m}_{kl}{\}}_{l=1}^M$, where $nu{m}_{kl}$ and $M$ denote the number of samples of the $l$-th class in $T_k^{NCN}\left(\overline{x}\right)$ and the number of classes, respectively;

3. Calculate the centroid $U_k^{NCN}=\{U_{kl}^{NCN}{\}}_{l=1}^M$ for each class, where $U_{kl}^{NCN}=mean\left(T_{kl}^{NCN}\right(\overline{x}\left)\right)$;

4. For $l=1$ to $M$ doCalculate the distance $d_{kl}=d(\overline{x},U_{kl}^{NCN})$ from the query point $\overline{x}$to the centroid of the $l$-th class and calculate the average distance ${\overline{d}}_{kl}=d_{kl}/nu{m}_{kl}$;Endfor

5. Find the best centroid $cen{t}_k=U_k^{NCN}\left[\arg min\left({\overline{d}}_{kl}\right)\right]$ and record the corresponding class $c_k$ and the number of samples$r_k$.

First, $k$ neighbours of the query point are found iteratively according to the NCN method. Then, the number of samples and the centroid for each class among $k$ neighbours of the query point are calculated. Finally, the discrimination class of the query point is selected based on the average distance. Figure 2 shows three examples.

Figure 2. Examples of the selection of the discrimination class for $x_1$, $x_2$, and $x_3$.

For the query point $x_1$, the distance from $x_1$ to the centroid of class 1 is 0.45, and the number of points of class 1 is 5. Therefore, the average distance from $x_1$ to the centroid of class 1 is $0.45/5=0.09$. Similarly, the average distance from $x_1$ to the centroid of class 2 is $0.23/2\approx 0.12$; therefore, $x_1$ is classified as class 1. For the query point $x_2$, the distance from $x_2$ to the centroid of class 1 is 0.64, and the number of points of class 1 is 3. Therefore, the average distance from $x_2$ to the centroid of class 1 is $0.64/3\approx 0.21$. Similarly, the average distance from $x_2$ to the centroid of class 3 is $0.44/5\approx 0.09$; therefore, $x_2$ is classified as class 3. For the query point $x_3$, the distance from $x_3$ to the centroid of class 1 is 0.39, and the number of points of class 1 is 2. Therefore, the average distance from $x_3$ to the centroid of class 1 is $0.39/2\approx 0.20$. Similarly, the average distance from $x_3$ to class 2 is $0.58/4\approx 0.15$, and the average distance from $x_3$to class 3 is $1.06/5\approx 0.21$; therefore, $x_3$ is classified as class 2.

Stage 2: Find the adaptive $k$ for $\overline{x}$ and its corresponding class $c$.

1. Calculate the distance $d^k=d(\overline{x},cen{t}_k)$ between $\overline{x}$ and each $cen{t}_k$ to obtain $d=\{d^k{\}}_{k=1}^{kmax}$; calculate the $rati{o}^k=r^k/k$ for the selected discrimination class for all neighbours to obtain $rati{o}^k=\{rati{o}^k{\}}_{k=1}^{kmax}$.

2. Calculate the generalised mean distance $d_{ratio}^k$ of each $k$. $d_{ratio}^k=(d^k{)}^p/(rati{o}^k{)}^q,k=1,2,\dots ,kmax$, where $p$ and $q$ are hyperparameters. Choose the class corresponding to the $k$ with the smallest mean distances as the class of the query point $c=c_{\arg min}\left(d_{ratio}^k\right)$.

We first calculate the distance between the query point and the centroid for the discrimination class and the ratio of the number of nearest neighbours in the discrimination class to the number of all nearest neighbours of each $k$. Then, the final classification result is obtained according to the generalised mean distance.

Both DC-LAKNN and AD-LAKNCN use the distance between the query point and the centroid of the discrimination class and the ratio of the number of nearest neighbours in the discrimination class to the number of all nearest neighbours to adaptively select $k$, which does not exist in KNCN. However, unlike DC-LAKNN, which arbitrarily sorts the ratio and the distance, our method uses the generalised average distance to evaluate the ratio and the distance, which can better capture the local feature distribution of the discrimination class. Figure 3 shows three examples.

Figure 3. Examples of the selection of the adaptive $k$ for $x_1$, $x_2$, and $x_3$.

We take $p=2$ and $q=0.3$ . For the query point$x_1$, the distance from $x_1$ to the centroid of $c_5^{x_1}$ is 0.27, and the number of points of $c_5^{x_1}$ is 3 when $k=5$. Therefore, the generalised average distance from $x_1$ to the centroid of $c_5^{x_1}$ is $\left((0.27{)}^2\right)/(3/5{)}^{0.3})=0.08$. Similarly, the generalised average distance from $x_1$ to the centroid of $c_6^{x_1}$ is 0.05 when $k=6$, and the generalised average distance from $x_1$ to the centroid of $c_7^{x_1}$ is 0.10 when $k=7$. Therefore, $x_1$ is classified as $c_6^{x_1}$. For the query point $x_2$, the distance from $x_2$ to the centroid of $c_5^{x_2}$ is 0.36, and the number of points of $c_5^{x_2}$ is 2 when $k=5$. Therefore, the generalised average distance from $x_2$ to the centroid of $c_5^{x_2}$ is $\left((0.36{)}^2\right)/(2/5{)}^{0.3})=0.17$ . Similarly, the generalised average distance from $x_2$ to the centroid of $c_6^{x_2}$ is 0.25 when $k=6$, and the generalised average distance from $x_2$ to the centroid of $c_7^{x_2}$ is 0.10 when $k=7$. Therefore, $x_2$ is classified as $c_7^{x_2}$. For the query point $x_3$, the distance from $x_3$ to the centroid of $c_5^{x_3}$ is 0.31, and the number of points of $c_5^{x_3}$ is 4 when $k=5$. Therefore, the generalised average distance from $x_3$ to the centroid of $c_5^{x_3}$ is $\left((0.31{)}^2\right)/(4/5{)}^{0.3})=0.10$ . Similarly, the generalised average distance from $x_3$ to the centroid of $c_6^{x_3}$ is 0.12 when $k=6$, and the generalised average distance from $x_3$ to the centroid of $c_7^{x_3}$ is 0.05 when $k=7$. Therefore, $x_3$ is classified as $c_7^{x_3}$.

3.3. The algorithm

In this section, we describe the AD-LAKNCN algorithm in detail. The pseudocode for the AD-LAKNCN algorithm is shown in Algorithm 1.

Table

Algorithm 1 AD-LAKNCN

Input:

$\overline{x}$: A query pattern;

$kmax$: The max number of nearest neighbours;

$p,q$: Hyperparameters used in the selection of the adaptive $k$;

$T=\{x_i\in R^d{\}}_{i=1}^N$: Training set;

Output: $c$: The classification result for the query;

Step 1: Calculate the Euclidean distances $d\left(\overline{x},x_i\right)$ between $\overline{x}$ and the training samples;

Step 2: Search the $kmax$ nearest centroid neighbours $T_{kmax}^{NCN}\left(\overline{x}\right)=\{x_j^{NCN}\in R^d{\}}_{j=1}^{kmax}$ of $\overline{x}$;

Step 2.1: Find the nearest centroid neighbour of $\overline{x}$, say $x_1^{NCN}$;

Step 2.2: Find $kmax$ nearest centroid neighbours of $\overline{x}$:

For $k=2$ to $kmax$ do

Find the $k-th$ NCN $x_k^{NCN}$; this is determined by $\overline{x}$ and all previous neighbour centroids $x_1^{NCN},\dots ,x_{k-1}^{NCN}$;

EndFor

Step 3: Selection of the discrimination class;

For $k=1$ to $kmax$ do

Collate the point set $T_k^{NCN}\left(\overline{x}\right)=\{T_{kl}^{NCN}{\}}_{l=1}^M$ and the number set $nu{m}_k=\{nu{m}_{kl}{\}}_{l=1}^M$, where $T_k^{NCN}\left(\overline{x}\right)$, $nu{m}_{kl}$ and $M$ denote the first $k$ elements of $T_{kmax}^{NCN}\left(\overline{x}\right)$, the number of samples of $l-th$ class in $T_k^{NCN}\left(\overline{x}\right)$ and the number of classes, respectively;

Compute the centroids of nearest neighbours $U_k^{NCN}=\{U_{kl}^{NCN}{\}}_{l=1}^M$ for each class in ${T_k}^{NCN}\left(\overline{x}\right)$ and select the best centroid $cen{t}^k$:

For $l=1$ to $M$ do

Compute the centroid of $T_{kl}^{NCN}$, say ${U_{kl}}^{NCN}$;

Compute the distance between $\overline{x}$ and $U_{kl}^{NCN}$, say $d_{kl}=d\left(\overline{x},U_{kl}^{NCN}\right)$;

Compute the average distance $\overline{d_{kl}}=d_{kl}/nu{m}_{kl}$;

EndFor

set $cen{t}^k=U_k^{NCN}\left[argmin\left(\overline{d_{kl}}\right)\right]$ and record its corresponding class $c^k$ and its number of samples $r^k$;

EndFor

Step 4: Compute the distance $d^k$ and the ratio $rati{o}^k$;

For $k=1$ to $kmax$ do

Compute the distance between $\overline{x}$ and $cen{t}^k$, say $d^k=d\left(\overline{x},cen{t}^k\right)$;

Compute the ratio $rati{o}^k=r^k/k$;

EndFor

Step 5: Classify $\overline{x}$ to the class $c$;

Step 5.1: Compute the generalised mean distance $d_{ratio}^k$:

For $k=1$ to $kmax$ do

$d_{ratio}^k=(d^k{)}^p/(rati{o}^k{)}^q,k=1,2,\dots ,kmax$

EndFor

Step 5.2: Classification result of $\overline{x}$: $c=c_{argmin\left(d_{ratio}^k\right)}.$

In Algorithm 1, the $kmax$ nearest centroid neighbours of the query point in the training set are computed in steps 1-2, which is the same as KNCN and does not exist in DC-LAKNN. In step 3, the proposed method uses the average distance method to select the discrimination class, which follows both the distance criterion and the quantity criterion. Finally, steps 4 and 5 adaptively select the $k$ value and its corresponding discrimination class as the final class of the query point. Unlike DC-LAKNN, which is arbitrary since it directly uses the mean of the ratio rank and the distance rank to determine the final $k$, our method uses the generalised average distance to use the ratio and the distance, which can better capture the local feature distribution of the discrimination class. The time complexity of this algorithm is $O(Ndkmax)$, where $N$, $d$, and $kmax$ denote the number of training sets, dimensions, and maximum $k$, respectively.

3.4. Differences between AD-LAKNN, KNCN and DC-LAKNN

In this section, we further analyze the differences between the proposed AD-LAKNCN and related methods, including KNCN and DC-LAKNN.

Both the KNCN and AD-LAKNCN use the NCN method to select the neighbour points. The advantage of this method is that when selecting the query point's neighbours, the principle of neighbours and symmetry is followed so that the query point is surrounded by the selected neighbours. However, in the KNCN, only the majority class is considered, and the sensitivity to the $k$ value degrades the classification performance. In the proposed AD-LAKNCN, the average distance between the query and the centroid of each class of the $k$ neighbours is used to determine the discrimination class, and a new adaptive $k$ value selection method is proposed to select the best $k$ value and is employed for good classification.

In DC-LAKNN, the quantity and distribution information of both majority class neighbours and secondary majority class neighbours are considered, and a adaptive $k$ value selection method is proposed. Unlike DC-LAKNN, AD-LAKNCN uses the NCN method to select the neighbour points and improves the adaptive $k$ value selection method. Moreover, AD-LAKNCN uses the average distance between the query and the centroid of each class of the $k$ neighbours to determine the discrimination class. In contrast to DC-LAKNN, the proposed AD-LAKNCN not only uses a more reliable nearest neighbour selection method but also incorporates the information of all $k$ nearest neighbours to fully use their distribution information.

4. Experiments

In this section, AD-LAKNCN is tested on real-world datasets to verify its performance. Additionally, we analyse AD-LAKNCN in terms of parameters and complexity. Section 4.1 provides basic information about the datasets. Section 4.2 offers five different indices and some details of the model design. Section 4.3 presents a comparison of the performance of ten algorithms on 24 datasets. Section 4.4 discusses the influence of the parameter $kmax$ on the classification performance. Section 4.5 introduces the complexity analysis of AD-LAKNCN. Section 4.6 introduces the experimental discussions of AD-LAKNCN.

4.1. Datasets

We conduct extensive experiments on 24 real-world datasets from the University ofCalifornia, Irvine (UCI) library (Dua & Graff, 2017) and knowledge extraction based on the evolutionary learning (KEEL) library (Alcaĺa-Fdez et al., 2011) to evaluate the performance of our proposed AD-LAKNCN algorithm. Tables 1 and 2 show the imbalance rate, classes, number of instances and dimensions of each dataset.

Table 1. The characteristics of 12 real-world datasets from the UCI repository.

Dataset	Ir	Classes	Instances	Dimensions
DNA	2.27	3	2000	180
Landsat	2.23	6	2000	36
Letter	1.35	26	5000	16
Msplice	2.16	3	3175	240
Segment	1.00	7	2310	18
Sonar	1.14	2	208	60
Spambase	1.54	2	4601	57
Vehicle	1.10	4	846	18
Wpbc	3.21	2	198	33
Liver	1.38	2	345	6
Ionosphere	1.79	2	351	34
German	2.33	2	1000	24

Table 2. The characteristics of 12 real-world datasets from the KEEL repository.

Dataset	Ir	Classes	Instances	Dimensions
Phoneme	2.41	2	5404	5
Optdigits	1.03	10	5620	64
Winequality-red	68.10	6	1599	11
Winequality-white	439.60	7	4898	11
Hayes-Roth	2.10	3	160	4
Monk-2	1.12	2	432	6
Pima	1.87	2	768	8
Ecoli	71.5	8	336	7
Tae	1.06	3	151	5
Texture	1.00	11	5500	40
Vowel	1.00	11	990	13
Yeast	92.60	10	1484	8

4.2. Experimental performance evaluation indices

We use the following five indices to evaluate the performance of the model.

1. $Accuracy$: In a C-class classification problem, we assume that the test set contains $m$ samples. We assume that the classifier correctly classifies $m^{\mathrm{\prime }}$ test set samples. Then, $Accuracy=m/m^{\mathrm{\prime }}$.

2. $F1$: In a binary classification problem, $f1$ is defined as $f1=2(precision\cdot recall)/(precision+recall)$, where $precision$ is the precision rate and $recall$ is the recall rate. We use the macro method to extend this method to a multiclass scenario, that is, to calculate metrics for each class and find their unweighted mean.

3. Kappa: The $accuracy$ index is not convincing for unbalanced datasets. The kappa coefficient represents the reduction rate of the current classification algorithm relative to random classification. It has excellent evaluation capabilities for unbalanced datasets, and it is calculated by the equation $kappa=\left(p_0-p_e\right)/\left(1-p_e\right)$, where $p_0$ is the accuracy and $p_e$ is the sum of the products of the actual and predicted quantities for all classes divided by the square of the total number of samples. In the experiment, we simulate datasets with $1.5<Ir$.

4. Gmeans: Gmeans is a new measure that considers the performance of classifiers on each class separately. In a C-class classification problem, it is assumed that the test set contains $m$ samples and that $m_c^{\mathrm{\prime }}$ is the number of samples in the class $c\left(c=1,2,\dots ,C\right)$. Assuming that the classifier correctly classifies $m_c^{\mathrm{\prime }}$ samples of class $c$, gmeans is calculated as $gmeans=({\prod }_{c=1}^C\left({m^{\mathrm{\prime }}}_c/m_c\right){)}^{\left(1/C\right)}$ . In the experiment, we simulate datasets with $1.5<Ir$.

5. AUROC: AUROC is the area under receiver operating characteristics curve where has excellent evaluation capabilities for unbalanced datasets (Maloof, 2003). This index is defined as $auroc=\left(1+tpr-fpr\right)/2$, where $tpr$ is the true positive rate and $fpr$ is the false positive rate. In the experiment, we simulate datasets with $1.5<Ir$.

We further compare the new algorithm with the KNN-based algorithms KNN, WKNN, MKNN, LMKNN, PNN, KNCN, LMKNCN, AdaKNN2, and DC-LAKNN in terms of the above five indices.

4.3. Experimental procedure

The experiments described below are performed to determine the maximum classification accuracy of KNN (Cover & Hart, 1967), WKNN (Dudani, 1976), MKNN (Liu & Zhang, 2012), LMKNN (Mitani & Hamamoto, 2006), PNN (Zeng et al., 2009), KNCN (Śanchez et al., 1997), LMKNCN (Gou et al., 2012), AdaKNN2 (Mullick et al., 2018), DC-LAKNN (Pan et al., 2020), and AD-LAKNCN.

To ensure a fair comparison, the principle of the maximum classification accuracy is used in the selection of $k$ and $kmax$; that is, the best performance in $\left\{1,2\dots ,K\right\}$ is selected as the final $k$ or $kmax$ selection of each algorithm, where we set $K=20$. In addition, in the DC-LAKNN algorithm, we take $\theta =2.5$. In our proposed AD-LAKNCN, according to prior experimental experience, we take $p=2$ and $q=0.3$.

To eliminate the effect of variable ranges, the features are standardised by removing the mean and scaling to unit variance. In other words, the standard score of a sample $\overline{x}$ is calculated as $z=(\overline{x}-u)/s$, where $u$ and $s$ are the mean and standard deviation of the training samples, respectively.

To eliminate the impact of randomness in the partitioning of the training and test sets on model evaluation, the classification algorithm for each dataset is validated using a tenfold cross-validation method.

The results are shown in Tables 3–7. Note that the optimised values of $k$ or $kmax$ for all the methods are listed in parentheses, and the best classification results on each dataset are shown in bold.

Table 3 shows the accuracy of each model on 24 datasets. On the one hand, AD-LAKNCN achieved the best results on 12 datasets, while LMKNCN ranked second and achieved the best results on only 6 datasets. On the other hand, the average accuracy of AD-LAKNCN was more than $1\mathrm{\%}$ higher than those of the other nine algorithms. Table 4 shows the $f1$ of the ten models on 24 datasets. AD-LAKNCN achieved the best results on 12 datasets, while LMKNCN ranked second and achieved the best results on only four datasets. Additionally, the average $f1$ of AD-LAKNCN on the 24 datasets was more than $1.2\mathrm{\%}$ higher than those of the other methods. From the above conclusions, the robustness and effectiveness of the proposed method are proven.

Table 3. Comparisons with nine KNN-based algorithms on 24 real-world datasets in terms of accuracy (%).

Datasets	knn	wknn	mknn	lmknn	pnn	kncn	lmkncn	adaknn2	dc-laknn	ad-lakncn
wpbc	78.45	80.45	78.37	78.34	79.42	79.92	80.92	78.87	78.89	83.45
	(9)	(20)	(4)	(16)	(13)	(10)	(11)	(5)	(12)	(16)
vehicle	71.86	71.87	67.86	76.96	71.64	77.78	78.85	71.87	74.23	77.31
	(5)	(9)	(1)	(8)	(6)	(13)	(4)	(15)	(19)	(20)
spambase	91.76	92.18	91.48	92.28	93.18	93.35	92.94	91.76	93.11	94.15
	(1)	(15)	(2)	(10)	(19)	(12)	(3)	(1)	(20)	(12)
sonar	87.57	87.10	83.26	88.98	86.62	90.38	87.98	88.02	90.45	91.88
	(4)	(3)	(1)	(2)	(2)	(3)	(2)	(7)	(8)	(4)
segment	96.28	96.28	94.72	96.49	96.28	96.28	96.67	96.28	96.67	97.19
	(1)	(1)	(1)	(3)	(1)	(1)	(2)	(1)	(10)	(10)
msplice	82.52	81.04	68.98	84.44	81.20	86.55	91.97	81.01	89.20	91.91
	(20)	(20)	(1)	(18)	(20)	(10)	(9)	(19)	(20)	(13)
liver	65.46	67.22	65.47	68.62	66.61	70.39	70.68	62.87	64.90	69.26
	(20)	(9)	(1)	(15)	(10)	(17)	(19)	(4)	(8)	(14)
letter	89.66	90.02	87.02	91.30	90.54	89.66	91.82	89.66	92.02	92.40
	(1)	(3)	(1)	(3)	(3)	(1)	(2)	(1)	(20)	(17)
landsat	88.65	88.85	87.70	90.60	89.40	90.05	90.50	88.75	90.25	90.65
	(1)	(19)	(1)	(6)	(3)	(8)	(4)	(5)	(11)	(9)
ionosphere	86.60	86.60	83.76	90.87	86.89	95.71	94.29	86.32	88.60	94.00
	(1)	(1)	(1)	(7)	(4)	(11)	(6)	(1)	(19)	(10)
german	74.10	74.10	71.40	74.50	74.30	74.60	75.20	72.40	72.40	74.20
	(20)	(17)	(3)	(15)	(19)	(14)	(18)	(15)	(16)	(18)
dna	82.35	82.30	69.95	89.80	82.50	87.45	90.10	79.10	87.85	89.85
	(20)	(20)	(2)	(20)	(20)	(9)	(9)	(18)	(20)	(16)
yeast	59.84	59.98	58.76	58.29	59.98	59.77	58.76	56.95	56.47	58.29
	(15)	(18)	(6)	(14)	(19)	(15)	(17)	(19)	(18)	(19)
winequality-white	65.76	65.76	59.25	65.76	67.82	65.76	65.76	65.76	68.42	69.29
	(1)	(1)	(2)	(1)	(7)	(1)	(1)	(1)	(20)	(17)
winequality-red	64.79	64.79	61.04	64.79	68.04	64.79	64.79	64.60	68.60	69.85
	(1)	(1)	(2)	(1)	(19)	(1)	(1)	(1)	(19)	(6)
vowel	99.19	99.19	98.79	99.19	99.19	99.19	99.19	99.19	99.29	99.29
	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(9)	(3)
texture	98.91	98.91	98.53	99.13	98.91	99.47	99.51	98.91	99.09	99.49
	(1)	(1)	(1)	(3)	(1)	(19)	(2)	(1)	(15)	(17)
tae	65.71	65.71	57.08	63.71	63.71	65.04	63.71	65.04	66.38	67.67
	(1)	(1)	(6)	(1)	(1)	(1)	(1)	(1)	(19)	(9)
optdigits	98.04	98.13	97.97	98.58	98.27	98.63	98.74	98.04	98.52	98.86
	(1)	(8)	(1)	(7)	(2)	(14)	(4)	(1)	(17)	(14)
ecoli	82.75	83.65	82.49	82.44	82.78	83.03	80.39	81.89	81.85	82.47
	(7)	(12)	(1)	(12)	(2)	(8)	(4)	(10)	(12)	(7)
phoneme	90.60	90.60	88.95	90.60	90.69	90.60	90.60	90.62	91.34	90.95
	(1)	(1)	(1)	(1)	(2)	(1)	(1)	(1)	(7)	(5)
hayes-roth	75.00	75.62	64.38	77.50	77.50	75.00	77.50	70.62	77.50	80.62
	(1)	(2)	(2)	(1)	(1)	(3)	(1)	(1)	(17)	(3)
monk-2	95.90	91.97	82.30	95.21	90.38	96.58	91.97	94.95	97.27	96.35
	(3)	(3)	(5)	(3)	(12)	(5)	(4)	(10)	(8)	(6)
pima	75.92	75.54	74.36	76.95	74.10	76.96	76.32	73.85	73.83	75.53
	(20)	(14)	(2)	(17)	(19)	(18)	(19)	(17)	(17)	(12)
average	81.99	81.99	78.08	83.14	82.08	83.62	83.71	81.14	83.21	84.79

Table 4. Comparisons with nine KNN-based algorithms on 24 real-world datasets in terms of $f1$ (%).

Datasets	knn	wknn	mknn	lmknn	pnn	kncn	lmkncn	adaknn2	dc-laknn	ad-lakncn
wpbc	63.21	63.97	58.08	65.16	64.62	63.21	63.21	64.08	66.67	68.79
	(1)	(17)	(1)	(6)	(4)	(1)	(1)	(1)	(15)	(16)
vehicle	71.57	71.30	66.71	76.57	70.99	77.36	78.54	71.38	73.94	77.14
	(5)	(8)	(1)	(8)	(6)	(13)	(4)	(15)	(19)	(15)
spambase	91.34	91.74	91.01	91.90	92.80	92.97	92.56	91.34	92.76	93.81
	(1)	(15)	(2)	(10)	(19)	(12)	(3)	(1)	(20)	(12)
sonar	87.19	86.62	82.39	88.49	86.29	90.01	87.36	87.63	90.12	91.52
	(4)	(3)	(1)	(2)	(12)	(3)	(2)	(7)	(8)	(4)
segment	96.17	96.17	94.58	96.37	96.17	96.17	96.58	96.17	96.55	97.11
	(1)	(1)	(1)	(3)	(1)	(1)	(2)	(1)	(10)	(10)
msplice	82.50	81.11	69.32	84.74	81.26	84.94	91.32	80.88	88.93	91.14
	(20)	(20)	(1)	(18)	(20)	(10)	(9)	(19)	(20)	(19)
liver	63.55	65.84	63.64	64.14	64.24	68.35	68.03	61.79	62.58	67.35
	(20)	(9)	(1)	(15)	(10)	(18)	(8)	(4)	(3)	(14)
letter	89.53	89.90	86.85	91.23	90.47	89.53	91.71	89.53	91.92	92.26
	(1)	(3)	(1)	(3)	(3)	(1)	(2)	(1)	(20)	(17)
landsat	87.41	87.66	86.36	89.31	88.15	88.50	89.04	87.47	89.03	89.45
	(1)	(3)	(1)	(5)	(3)	(8)	(4)	(2)	(11)	(9)
ionosphere	83.99	83.99	79.84	88.99	83.99	95.15	93.63	83.63	86.44	93.00
	(1)	(1)	(1)	(14)	(1)	(11)	(6)	(1)	(19)	(11)
german	64.06	62.85	58.86	65.99	64.23	68.05	63.99	63.99	63.72	65.81
	(8)	(17)	(2)	(15)	(11)	(10)	(15)	(15)	(16)	(18)
dna	81.86	81.69	69.19	88.74	81.89	85.82	89.09	78.45	86.99	88.57
	(20)	(20)	(2)	(20)	(20)	(9)	(9)	(18)	(20)	(16)
yeast	55.18	55.31	53.16	52.97	54.34	53.59	53.36	54.25	53.51	54.02
	(7)	(14)	(2)	(20)	(12)	(8)	(4)	(10)	(18)	(19)
winequality-white	45.55	45.55	34.28	45.55	46.38	45.55	45.55	45.55	47.94	48.31
	(1)	(1)	(2)	(1)	(2)	(1)	(1)	(1)	(20)	(15)
winequality-red	36.52	36.52	29.66	36.52	37.73	36.52	36.52	36.09	38.11	40.26
	(1)	(1)	(2)	(1)	(2)	(1)	(1)	(1)	(19)	(6)
vowel	99.19	99.19	98.78	99.19	99.19	99.19	99.19	99.19	99.29	99.29
	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(9)	(3)
texture	98.91	98.91	98.53	99.13	98.91	99.47	99.51	98.91	99.09	99.49
	(1)	(1)	(1)	(3)	(1)	(19)	(2)	(1)	(15)	(17)
tae	64.71	64.71	55.18	62.59	62.59	63.99	62.59	63.89	65.59	66.85
	(1)	(1)	(6)	(1)	(1)	(1)	(1)	(1)	(19)	(9)
optdigits	98.04	98.13	97.97	98.58	98.27	98.63	98.74	98.04	98.52	98.86
	(1)	(8)	(1)	(7)	(2)	(14)	(4)	(1)	(17)	(14)
ecoli	72.72	74.14	72.10	69.78	74.76	72.51	71.47	71.61	71.87	70.69
	(9)	(12)	(1)	(11)	(4)	(7)	(4)	(10)	(9)	(9)
phoneme	88.44	88.44	86.32	88.44	88.53	88.44	88.44	88.47	89.37	88.94
	(1)	(1)	(1)	(1)	(2)	(1)	(1)	(1)	(7)	(5)
hayes-roth	74.03	76.79	60.43	77.19	75.63	78.05	75.63	68.82	79.74	83.29
	(1)	(4)	(2)	(2)	(1)	(3)	(1)	(4)	(17)	(3)
monk-2	95.79	91.74	81.72	95.16	90.25	96.53	91.89	94.90	97.25	96.30
	(3)	(3)	(5)	(3)	(12)	(5)	(4)	(10)	(8)	(6)
pima	70.52	71.75	69.59	74.64	69.65	72.63	72.91	68.99	70.46	71.91
	(19)	(14)	(2)	(17)	(19)	(9)	(19)	(17)	(17)	(15)
average	77.58	77.67	72.69	78.72	77.56	79.38	79.26	76.88	79.18	80.59

Furthermore, we can see that AD-LAKNCN, KNCN and LMKNCN perform better than the other methods. The reason may be that these three methods employ the NCN method to select the neighbours of the query point, which iteratively selects the neighbours around the query point. On some datasets, such as vehicle and dna, LMKNCN performs better than KNCN and AD-LAKNCN. The reason may be that LMKNCN employs multiple local mean vectors of $k$ nearest neighbours per class, which uses the information of all the classes. However, most importantly, it can be clearly seen that AD-LAKNCN achieved the best results on 12 datasets because the average distance can fully use the distribution of all neighbours and the $k$ value selection method can focus on the more reliable $k$ value.

We also explore the effect of AD-LAKNCN on unbalanced datasets. As shown in Table 5, on 13 datasets with $1.5<Ir$, AD-LAKNCN also achieved the best results for kappa on 6 datasets, and the average kappa exceeded those of the other algorithms by more than $2.5\mathrm{\%}$. From Table 6, comparing the gmeans of the 13 unbalanced datasets, AD-LAKNCN achieved the best results on three datasets, which was less than the four of DC-LAKNN. However, for the average g-means, AD-LAKNCN still ranked first and exceeded those of the other algorithms by at least $0.7\mathrm{\%}$. From Table 7, AD-LAKNCN also achieved the best results for the area under the receiver operating characteristic curve (AUROC) on 6 datasets, and the average AUROC exceeded those of the other algorithms by more than $1\mathrm{\%}$.

Table 5. Comparisons with nine KNN-based algorithms on 13 real-world datasets in terms of kappa (%).

Datasets	knn	wknn	mknn	lmknn	pnn	kncn	lmkncn	adaknn2	dc-laknn	ad-lakncn
wpbc	27.52	32.11	18.94	31.25	31.80	27.52	28.90	29.81	35.17	41.60
	(1)	(17)	(1)	(6)	(4)	(1)	(7)	(5)	(15)	(16)
spambase	82.68	83.49	82.02	83.80	85.61	85.95	85.13	82.68	85.52	87.64
	(1)	(15)	(2)	(10)	(19)	(12)	(3)	(1)	(20)	(12)
msplice	73.38	71.27	54.68	72.89	71.47	77.09	86.61	71.03	83.05	86.59
	(20)	(20)	(1)	(18)	(20)	(10)	(9)	(19)	(20)	(13)
landsat	86.02	86.27	84.86	88.41	86.95	87.72	88.29	86.15	87.98	88.47
	(1)	(19)	(1)	(5)	(3)	(8)	(4)	(5)	(11)	(9)
ionosphere	68.40	68.40	60.87	78.18	68.62	90.31	87.27	67.69	73.23	86.03
	(1)	(1)	(1)	(7)	(4)	(11)	(6)	(1)	(19)	(11)
german	29.04	28.38	20.28	33.07	30.17	36.45	32.14	28.73	28.45	32.55
	(12)	(17)	(2)	(15)	(19)	(10)	(10)	(15)	(16)	(18)
dna	72.49	72.37	53.92	82.84	72.76	78.99	83.21	67.78	80.51	82.81
	(20)	(20)	(2)	(20)	(20)	(9)	(9)	(18)	(20)	(16)
winequality-white	49.03	49.03	37.51	49.03	50.91	49.03	49.03	49.03	51.96	52.70
	(1)	(1)	(2)	(1)	(7)	(1)	(1)	(1)	(15)	(17)
winequality-red	45.00	45.00	37.56	45.00	48.34	45.00	45.00	44.67	50.09	52.13
	(1)	(1)	(2)	(1)	(19)	(1)	(1)	(1)	(19)	(6)
pima	42.16	43.85	39.97	49.38	39.93	45.71	46.08	38.83	41.09	44.15
	(20)	(14)	(2)	(17)	(19)	(9)	(19)	(17)	(17)	(15)
phoneme	76.9	76.90	72.67	76.90	77.08	76.90	76.90	76.95	78.74	77.88
	0(1)	(1)	(1)	(1)	(2)	(1)	(1)	(1)	(7)	(5)
hayes-roth	59.71	61.03	41.59	63.60	63.60	60.58	63.60	52.64	64.23	69.72
	(1)	(4)	(2)	(1)	(1)	(3)	(1)	(1)	(17)	(12)
ecoli	75.72	77.12	75.76	75.42	76.03	76.19	73.10	74.49	74.84	75.65
	(7)	(12)	(1)	(12)	(2)	(8)	(4)	(10)	(9)	(7)
average	60.62	61.17	52.36	63.83	61.79	64.42	65.02	59.27	64.22	67.53

Table 6. Comparisons with nine KNN-based algorithms on 13 real-world datasets in terms of gmeans (%).

Datasets	knn	wknn	mknn	lmknn	pnn	kncn	lmkncn	adaknn2	dc-laknn	ad-lakncn
wpbc	57.56	57.56	46.67	58.58	57.56	57.56	57.56	58.09	59.08	57.56
	(1)	(1)	(1)	(6)	(1)	(1)	(1)	(1)	(15)	(1)
spambase	91.22	91.51	90.71	91.86	92.59	92.79	92.38	91.22	92.68	93.41
	(1)	(15)	(2)	(10)	(19)	(6)	(3)	(1)	(20)	(12)
msplice	86.35	85.10	73.71	79.02	85.20	82.69	89.55	84.57	91.39	89.76
	(20)	(20)	(1)	(2)	(20)	(3)	(4)	(19)	(20)	(13)
landsat	86.98	86.98	85.70	88.43	87.81	87.52	88.02	87.20	88.31	88.37
	(2)	(3)	(1)	(5)	(3)	(4)	(4)	(2)	(11)	(9)
ionosphere	81.26	81.26	75.56	86.85	81.26	94.97	93.67	80.77	83.77	92.08
	(1)	(1)	(1)	(14)	(1)	(11)	(6)	(1)	(19)	(11)
german	62.75	57.92	50.28	60.47	57.92	65.11	59.73	61.42	59.04	61.31
	(4)	(3)	(2)	(15)	(6)	(10)	(3)	(4)	(3)	(4)
dna	84.55	84.42	72.00	86.81	84.69	84.26	86.66	81.77	88.33	86.57
	(20)	(20)	(2)	(18)	(20)	(7)	(8)	(18)	(19)	(9)
winequality-white	5.70	5.70	0.00	5.70	5.70	5.70	5.70	5.70	5.86	5.91
	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(6)	(7)
winequality-red	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00
	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)	(1)
pima	67.17	69.32	66.35	74.35	67.37	70.04	70.96	65.59	68.87	69.78
	(7)	(14)	(1)	(17)	(4)	(9)	(19)	(1)	(17)	(15)
phoneme	87.48	87.48	84.98	87.48	87.52	87.48	87.48	87.52	88.72	88.20
	(1)	(1)	(1)	(1)	(10)	(1)	(1)	(1)	(15)	(5)
hayes-roth	65.97	74.22	47.68	74.99	66.62	75.36	73.58	64.24	77.61	82.45
	(1)	(4)	(2)	(2)	(1)	(3)	(2)	(4)	(17)	(11)
ecoli	46.05	46.82	46.48	45.48	61.33	45.48	46.73	46.28	45.55	45.62
	(9)	(16)	(1)	(1)	(5)	(1)	(4)	(11)	(3)	(7)
average	63.31	63.71	56.93	64.62	64.27	65.3	65.54	62.64	65.32	66.23

Table 7. Comparisons with nine KNN-based algorithms on 13 real-world datasets in terms of AUROC (%).

Datasets	knn	wknn	mknn	lmknn	pnn	kncn	lmkncn	adaknn2	dc-laknn	ad-lakncn
wpbc	78.45	80.45	78.37	78.34	79.42	79.92	80.92	78.87	78.89	83.45
	(9)	(20)	(4)	(16)	(13)	(10)	(11)	(5)	(12)	(16)
spambase	91.76	92.18	91.48	92.28	93.18	93.35	92.94	91.76	93.11	94.15
	(1)	(15)	(2)	(10)	(19)	(12)	(3)	(1)	(20)	(12)
msplice	86.89	85.78	76.73	88.33	85.90	89.91	93.98	85.76	91.90	93.93
	(20)	(20)	(1)	(18)	(20)	(10)	(9)	(19)	(20)	(13)
landsat	93.19	93.31	92.62	94.36	93.64	94.03	94.30	93.25	94.15	94.39
	(1)	(19)	(1)	(5)	(3)	(8)	(4)	(5)	(11)	(9)
ionosphere	86.60	86.60	83.76	90.87	86.89	95.71	94.29	86.32	88.60	94.00
	(1)	(1)	(1)	(7)	(4)	(11)	(6)	(1)	(19)	(10)
german	74.10	74.10	71.40	74.50	74.30	74.60	75.20	72.40	72.40	74.20
	(20)	(17)	(3)	(15)	(19)	(14)	(18)	(15)	(16)	(18)
dna	86.76	86.72	77.46	92.35	86.88	90.59	92.58	84.32	90.89	92.39
	(20)	(20)	(2)	(20)	(20)	(9)	(9)	(18)	(20)	(16)
winequality-white	79.75	79.75	75.90	79.75	80.97	79.75	79.75	79.75	81.32	81.84
	(1)	(1)	(2)	(1)	(7)	(1)	(1)	(1)	(20)	(17)
winequality-red	78.87	78.87	76.62	78.87	80.83	78.87	78.87	78.76	81.16	81.91
	(1)	(1)	(2)	(1)	(19)	(1)	(1)	(1)	(19)	(6)
pima	75.92	75.54	74.36	76.95	74.10	76.96	76.32	73.85	73.83	75.53
	(20)	(14)	(2)	(17)	(19)	(18)	(19)	(17)	(17)	(12)
phoneme	90.60	90.60	88.95	90.60	90.69	90.60	90.60	90.62	91.34	90.95
	(1)	(1)	(1)	(1)	(2)	(1)	(1)	(1)	(7)	(5)
hayes-roth	81.25	81.72	73.28	83.12	83.12	81.25	83.12	77.97	83.12	85.47
	(1)	(2)	(2)	(1)	(1)	(3)	(1)	(1)	(17)	(3)
ecoli	89.59	90.18	89.48	89.45	89.64	89.75	88.22	89.10	89.08	89.51
	(7)	(12)	(1)	(12)	(2)	(8)	(2)	(10)	(12)	(7)
average	84.03	84.18	80.73	85.21	84.48	85.58	85.99	83.17	85.22	87.06

Furthermore, we can see that AD-LAKNCN, LMKNCN, KNCN and DC-LAKNN performed better than the other methods. The reason may be that AD-LAKNCN, LMKNCN and KNCN employ the NCN method to select the neighbours of the query point, and DC-LAKNN considers the secondary majority class of the query point's neighbours. On some datasets, such as msplice, LMKNCN performs better than KNCN and AD-LAKNCN. The reason may be that LMKNCN employs multiple local mean vectors of $k$ nearest neighbours per class, which uses the information of all the classes. However, most importantly, it can be clearly seen that AD-LAKNCN achieved the best results in most cases because the average distance can fully use the distribution of all neighbours and the $k$ value selection method can focus on the more reliable $k$ value.

Based on the above conclusions, the new method achieves a state-of-the-art effect on not only conventional datasets but also unbalanced datasets, which proves the validity of the new method.

4.4. Analysis of the kmax sensitivity

To explore the influence of the value of $kmax$ on the classification results of AD-LAKNCN and determine the optimal value of $kmax$, we select different $kmax$ and carry out simulation experiments on the UCI and KEEL datasets. Here, we take $kmax=1,2,\dots ,20$.

Figures 4 and 5 show that on 24 datasets from the University of California, Irvine (UCI) and Knowledge Extraction based on Evolutionary Learning (KEEL) repositories, except for the sonar dataset, where the accuracy and $f1$ slowly decreased after reaching a maximum at $kmax=4$, the accuracy and $f1$ of the new method increased with the increase of $kmax$ and fluctuated slightly near the highest point.

Figure 4. The accuracy of AD-LAKNCN for each $kmax$ on 24 real-world datasets.

Figure 5. The $f1$ of AD-LAKNCN for each $kmax$ on 24 real-world datasets.

Figures 6–8 show that on the 13 unbalanced datasets, except for the gmeans of the wpbc dataset, which decreased with the increase in $kmax$, the kappa, gmeans and AUROC of each dataset appeared to increase with the increase in $kmax$.

Figure 6. The kappa of AD-LAKNCN for each $kmax$ on 13 unbalanced real-world datasets.

Figure 7. The gmeans of AD-LAKNCN for each $kmax$ on 13 unbalanced real-world datasets.

Figure 8. The AUROC of AD-LAKNCN for each $kmax$ on 13 unbalanced real-world datasets.

From the above experiments, the following observations can be made: (1) In most cases, AD-LAKNCN can achieve the best performance when $kmax>10$. (2) Selecting a larger $kmax$ does not reduce the performance. (3) AD-LAKNCN is insensitive to the choice of $kmax$ and has excellent classification performance.

4.5. Analysis of computational complexity

To explore the computational complexity of the new method, we further analysed the increase in the computational cost of the new method compared with those of KNN and KNCN.

We specify the following notation related to in the computational complexity: $N$, $d$, $kmax$ and $M$ denote the number of training sets, dimensions, maximum $k$ and number of classes, respectively.

The main computational costs of the KNN algorithm are the calculation of the Euclidean distance between the query and all training samples and the determination of the neighbours; combined with the class calculation of the query point, the computational complexity of KNN is $O\left(Nd+Nk+k\right)$ . For KNCN, the calculation of each nearest centroid neighbour requires no more than $N$ centroid calculations and distance calculations and $N$ comparison calculations; therefore, the computational cost of the $k$ nearest centroid neighbours is approximately $O\left(2Ndk+Nk\right)$ . Combined with the class calculation of the query point, the computational complexity of KNCN is approximately $O\left(2Ndk+Nk+k\right)$.

Table 8 shows the increased computational costs of the new method over those of KNN and KNCN. In step 2, the new method and KNCN execute $2Ndkmax$ more computations than KNN when finding the nearest centroid neighbours. In step 3, the new method executes $3Mkmax$ more computations than KNN and KNCN when selecting the best discrimination class. In step 4, the distance from the query point to the centroid of each $k$ and the ratio of the selected discrimination class in all neighbours need to be calculated when selecting the best $k$. Compared with those of KNN and KNCN, the increase computation is approximately $2kmax$. In step 5, the average rank calculation increases the number of computations by $kmax$ times to determine the class of the query point.

Table 8. The increased computation of the AD-LAKNCN algorithm compared to the KNN and KNCN algorithms.

Step	KNN/KNCN	Increased computations	Increased computation cost
Step1	KNN	–	–
	KNCN	–	–
Step2	KNN	Nearest centroid neighbour computation	$2Ndkmax$
	KNCN	–	–
Step3	KNN	Selection computation	$3Mkmax$
	KNCN	Selection computation	$3Mkmax$
Step4	KNN	Distance and ratio computation	$2kmax$
	KNCN	Distance and ratio computation	$2kmax$
Step5	KNN	Average rank computation	$kmax$
	KNCN	Average rank computation	$kmax$

In addition to the computational complexity analysis above, the running times for classifying all the testing samples on the three UCI datasets and three KEEL datasets are provided in Table 9 when $k=3$ or $kmax=3$. Note that the numbers of the training set, testing set, dimensions and classes are listed in parentheses. All the methods were implemented using Python 3.6.8, and all the experiments were run on a 64-bit Windows 11 operating system with an Intel(R) Core (TM) i5-11600KF central processing unit (CPU) @3.90 GHz with 16 GB of memory.

Table 9. The computational time (s) of actually classifying all the testing samples.

Datasets	knn	kncn	ad-lakncn
DNA (1800,20,180,3)	0.3196	2.7116	2.6870
Landsat (1800,20,36,6)	0.0441	0.6472	0.6873
Letter (4500,20,16,26)	0.1015	0.8715	0.9171
Msplice (2857,20,240,3)	0.7542	5.6208	5.5064
Segment (2079,20,18,7)	0.0525	0.4340	0.4776
Sonar (188,20,60,2)	0.0159	0.1022	0.1738
Spambase (4140,20,57,2)	0.2595	2.1746	2.2751
Vehicle (761,85,18,4)	0.0179	0.1800	0.2146
Wpbc (178,20,33,2)	0.0157	0.0557	0.1407
Liver (311,20,6,2)	0.0214	0.0336	0.0831
Ionosphere (316,20,34,2)	0.0164	0.1200	0.1728
German (900,20,24,2)	0.0355	0.2483	0.2954
Phoneme (4864,20,5,2)	0.1663	0.6658	0.7172
Optdigits (5058,20,64,10)	2.2206	4.4229	4.6406
Winequality-red (1439,20,11,6)	0.1106	0.3278	0.3910
Winequality-white (4408,20,11,7)	0.3298	1.0170	1.0750
Hayes-Roth (144,20,4,3)	0.0169	0.0168	0.0712
Monk-2 (389,20,6,2)	0.0175	0.0547	0.1258
Pima (691,20,8,2)	0.0369	0.1165	0.1859
Ecoli (302,20,7,8)	0.0267	0.0343	0.1046
Tae (136,20,5,3)	0.0282	0.0171	0.0801
Texture (4950,20,40,11)	1.1911	2.8623	2.8904
Vowel (891,20,13,11)	0.0883	0.2069	0.2660
Yeast (1336,20,8,10)	0.0867	0.2223	0.2917

The following conclusions can be drawn from the results in Table 9: (1) The KNN algorithm achieved the fastest running speed because it is simple. (2) NCN-based methods, including KNCN and AD-LAKNCN, require a somewhat longer running time due to the iterative calculations. (3) Compared with KNCN, the running times of AD-LAKNCN do not increase much.

In summary, since $kmax$ and $M$ are generally smaller than $N$ and $d$, the higher computational costs of the new method are due to calculating the nearest centroid neighbours, which is the same as in the KNCN, so the new method does not greatly increase the computational costs compared with those of the KNCN. Overall, although the computational costs of the new method increase, they are fully acceptable due to the excellent classification performance of the algorithm.

4.6. Discussion of experimental results

The conclusions of the above experimental results are summarised as follows:

1. The experimental results on all the evaluation indices show that the proposedAD-LAKNCN method obtains satisfactory classification performance.

2. The methods (i.e. AD-LAKNCN, LMKNCN and KNCN) that use the NCN method to select the neighbours generally perform better than other KNN-based methods.

3. The average distance can make full use of the distribution of all neighbours to select the best discrimination class. This is because when selecting a query point discrimination class, using the average distance not only makes the number of discrimination class samples as large as possible but also makes the centroid of the discrimination class as close as possible to the query point.

4. AD-LAKNCN is insensitive to the choice of $kmax$, which shows that our new adaptive $k$ value selection method is effective. Thus, a larger $kmax$ value can be chosen in AD-LANKCN, which usually has excellent classification performance.

5. Compared with KNN, KNCN and AD-LAKNCN require more computation due to the iterative calculations.

5. Conclusions

This paper combines the NCN and DC-LAKNN algorithms and uses the number and distribution information of each class of neighbours to propose a new adaptive KNN method called AD-LAKNCN. First, the nearest neighbours of the query point are selected by the NCN method. Next, the discrimination class under each $k$ value is determined by comparing the average distances of different classes. Last, the optimal discrimination class for the query point is determined by using the number and distribution information of the discrimination class under each $k$ value.

The new method is compared with nine other KNN-based classification algorithms on 24 real datasets. The experimental results show that the new classifier performs better than other classifiers in terms of accuracy, $f1$, kappa, gmeans and AUROC.

The main computational cost of AD-LAKNCN is to iteratively find $k$ nearest centroid neighbours, which is the same as KNCN. Compared with the KNN algorithm, the KNCN and AD-LAKNCN require more computation, which limits their application to large-scale data. In future work, we plan to explore parallel computing methods to reduce the computation of finding $k$ nearest centroid neighbours. Moreover, we plan to apply the proposed method to practical applications. For example, we can use average distance as a classification measure to deal with the multilabel classification, which means that some queries should be classified into multiple classes. In addition, the proposed method can be integrated with the other methods for good classification performance.

Disclosure statement

No potential conflict of interest was reported by the author(s).