Modified Euclidean-Canberra blend distance metric for kNN classifier

Abstract

In today’s world different data sets are available on which regression or classification algorithms of machine learning are applied. One of the classification algorithms is k-nearest neighbor (kNN) which computes distance amongst various rows in a dataset. The performance of kNN is evaluated based on $K$ -value and distance metric used, where $K$ is the total count of neighboring elements. Many different distance metrics have been used by researchers in literature, one of them is Canberra distance metric. In this paper the performance of kNN based on Canberra distance metric is measured on different datasets, further the proposed Canberra distance metric, namely, Modified Euclidean-Canberra Blend Distance (MECBD) metric has been applied to the kNN algorithm which led to improvement of class prediction efficiency on the same datasets measured in terms of accuracy, precision, recall, F1-score for different values of $k$ . Further, this study depicts that MECBD metric use led to improvement in accuracy value 80.4% to 90.3%, 80.6% to 85.4% and 70.0% to 77.0% for various data sets used. Also, implementation of ROC curves and auc for $k=$ 5 is done to show the improvement is kNN model prediction which showed increase in auc values for different data sets, for instance increase in auc values from 0.873 to 0.958 for Spine (2 Classes) dataset, 0.857 to 0.940, 0.983 to 0.983 (no change), 0.910 to 0.957 for DH, SL and NO class for Spine (3 Classes) data set and 0.651 to 0.742 for Haberman’s data set.

Keywords

Classification kNN Canberra distance metric accuracy precision recall F1-score MECBD ROC auc

1. Introduction

All the machine learning models are used to forecast the results based on previous data available. Based on some attribute values already known, the machine learning model is built and this model use these values to create a predicted output. Classification is a method which is used to constructs a model using data samples which called training data set. Classification is a supervised learning method which maps the attribute values into one or more response classes based on knowledge from an expert. In literature, classification methods such as Naïve Bayes, k-Nearest Neighbor, Logistic Regression, Decision Trees and Support Vector Machines have been used to solve many applications in the real world domain [1, 2].

K Nearest Neighbor (kNN) is a classifier that depends on the distance or similarity metric between test and training samples [3]. This method is simple, easy to implement and handles the noise satisfactorily. Thus, it has been used by many researchers to classify new inputs based on training data [4].

The relevant factors such as $K$ value and the distance measures, influence the performance of kNN classifier. $K$ value is a parameter that is used to determine the number of neighboring elements to be involved in predicting the class values. The distance metric is used to calculate the distance between two data points which is termed as distance measure. The performance of kNN classifier is evaluated in terms of accuracy, F1-score, precision etc. A number of distance measures have been used in literature namely Euclidean Distance, Manhattan Distance, Minkowski Distance, Canberra Distance etc, out of these measures the most commonly used one is Euclidean distance. There has been need for improving the distance metric so that the overall performance of kNN algorithm improves.

Pulungan and Zaris [5] compared the performance of kNN classifier using various distance metrics namely Canberra Distance, Euclidean Distance and Braycurtis Distance. The differentiation between each has been based on accuracy view point. It was observed from the results that the Braycurtis distance method had better outcome than Canberra Distance and Euclidean Distance technique, based on different costs of $K$ with accuracy values of 96%. Jiang et al. [6] summarized three shortcomings of kNN algorithm and solutions were given to overcome these shortcomings in terms of distance function, neighbour size and class probability estimation. This study worked on to improvise the Euclidean distance function in terms of weighted attribute implementation. Jaffar et al. [7] proposed a modified kNN classifier based on fuzzy-rule based methodology and barycenter neighbourhood with Mahalanobis distance. The increase in classification accuracy has been observed for modified kNN algorithm with classification rates up to 96%. Ehsani and Drablø [8] studied performance of kNN classifiers based on choice of different distance formulas and investigated how various distance measures behaved when biomedical data was analyzed. It was inferred that distance measures: Hassanat, Sobolev, and Manhattan depicted sturdy behaviour in kNN when applied on various data sets. Whereas, other measures: Euclidean, Canberra, Hamming exhibited satisfactory performance on designated datasets. Thus, it can be concluded that it is essential to choose the distance measure before the application of any classifier.

In literature, a plethora of research has been centered on kNN performance improvement using available distance metrics. But very less work has been carried out to modify existing distance formulas to make kNN technique more effective. In this paper, the use of the Modified Euclidean-Canberra Blend Distance formula (MECBD) is proposed, to quantify distance in the kNN classifier to get improvement, shown in terms of class prediction parameters. The remainder of the paper is organized as: Methodology used which includes discussion about kNN algorithm, original and proposed distance metrics, data sets and proposed method is presented in Section 2. The Section 3 presents the results of the application of the proposed metric. Conclusions and future work is presented in the last section.

2. Methodology used

2.1 kNN algorithm

Since this research is based on datasets having classes, therefore classification technique has been required to be implemented here. As kNN is based on feature correlation and classification is carried out using several kNN classifiers, which consider some input data, feed it into the trained model and then the model predicts the output class [13]. This study uses kNN algorithm for its proposed distance formula. K-Nearest Neighbor classifier was proposed by Cover and Hart in 1968. kNN is called lazy learner classifier as it holds the class information from the training dataset till the testing data is provided [9, 18]. The K-nearest neighbor (kNN) classifier is a procedure for segregating data values of learning data that is in its neighbourhood [21, 23]. kNN classifies the given dataset into classes using a similarity measure [24].

It is analogous to the clustering methodology, where clustering is performed using distance of the new data to its neighbours. To identify the distance amidst two points, particularly the point on the training dataset ( $x$ ) and the point on the testing data ( $y$ ), distinct distance measuring approaches are used, in case of use of Euclidean formula, distance is calculated as shown in Eq. (1) below [17]:

$\displaystyle d(x,y)=\sqrt{\sum_{i=1}^{n}(|x_{i}-y_{i}|)^{2}}$ (1)

where $x$ and $y$ are two data with $n$ attributes. Normalization can also be done before calculating distances, which prevent attributes to have large range of values and convert these attributes with small range value [2].

2.1.1 How do we choose

K

kNN technique works on similarity distance measure for which taking the correct value is essential. This procedure is called parameter tuning which is significant for good accuracy. $K$ in kNN is a value that indicated the closest neighbors to be included in the most of the suggestion process, so if a new set of input rows or data points is added, and it is required to know who the neighbors are, now if let $K=$ 5 is considered, then a data item is distinguished depending on the predominance of its 5 adjascent neighbors. If the value of $k$ is chosen low then the classification prediction done is too noisy as many wrong predictions may be there. But if $k$ is too big, processing will take too much time [22].

2.1.2 How kNN algorithm works?

The main aim of kNN algorithm is to identify the nearest neighbor’s to a testing point, so that classification of testing point is done and it is categorized. To find the nearest neighbor based on the new data rows available as input to be predicted, it is needed to calculate the distance matrix. There are various types of similarity distance measures like Euclidean Distance, Manhattan Distance, Minkowski Distance, Canberra Distance and others but commonly used matrix is Euclidean distance. kNN algorithm calculates the Euclidean distance of unknown data value from all the point values (based on value of $K$ ) in a dataset. Then the class where the majority of neighbors are pointing to is considered and this class is then made the unknown data point under consideration.

2.2 Implementation of distance measure

Distance measure is widely used for degree of similarity and dissimilarity between two data rows. Some distance measures include: Euclidean distance, Chebyshev, angular separation, Canberra distance, Hamming distance, Sorensen distance and so on. This study of kNN algorithm, classification process utilizes the Canberra distance technique and also a modified version of it.

2.2.1 Canberra distance

The Canberra distance has been proposed by G.N Lance and W.T William in 1966 and 1967. Canberra distance is designed to get the distance from couple of points where the data is in the format of rows and columns using Eq. (2) [14, 15]. It is summation of subtraction of data points attribute values with the division of sum of their abstract attribute values.

$\displaystyle d(a,b)=\sum_{i=1}^{n}\frac{|a_{i}-b_{i}|}{|a_{i}|+|b_{i}|}$ (2)

2.2.2 Euclidean distance

Distance between two points on a straight line is termed as Euclidean distance. This distance mechanism uses principles of Pythagoras formula. This computation is primarily used in numerous machine learning processes [10]. The Euclidean distance procedure is stated in Eq. (3) as [16] summation of the square of subtraction of attribute values of data points under consideration.

$\displaystyle d(a,b)=\sqrt{\sum_{i=1}^{n}(|a_{i}-b_{i}|)^{2}}$ (3)

2.2.3 Modified Euclidean-Canberra blend distance (MECBD)

Based on the Euclidean and Canberra distance formulas, a modification of Canberra Distance formula is proposed in Eq. (4) which involves squaring the subtraction of vector absolute values followed by division of absolute values their sum, then finding the square root of the final result. Here, $a$ and $b$ are the rows of the data set. In the formula, $a_{i}$ and $b_{i}$ are the attribute values of the row $a$ and $b$ .

$\displaystyle d(a,b)=\sqrt{\sum_{i=1}^{n}\frac{(|a_{i}-b_{i}|)^{2}}{|a_{i}|+|b% _{i}|}}$ (4)

2.3 Datasets used

Data sets are basically collection of data. Classification techniques work on the data sets whose dependent attribute is divided into classes [25]. The datasets involved in the proposed study are of classification technique type. In this study three data sets are used, two related to Spine and one related to life expectancy (Haberman’s dataset) from UCI machine learning repository with details shown in Table 1[11, 12]. One data set is Spine which has 6 attributes (pelvic incidence, pelvic tilt, lumbar lordosis angle, sacral slope, pelvic radius and grade of spondylolisthesis) and 2 classes (AB-abnormal spine, NO-normal spine) and other data set related to spine is having same 6 attributes but 3 classes (DH-disc hernia, NO-normal spine, SL-spondylolisthesis). The Haberman’s data is having 3 attributes (Age of patient at time of operation, Patient’s year of operation, Number of positive axillary nodes detected and Survival status) and 2 classes (Sur-survived, Non-Sur-not survived). All the datasets are having more than 300 rows of data.

Table 1
Summary of datasets used in study

Datasets	Classes	Attributes	Training	Test	Total
Spine (2 classes)	2	6	248	62	310
Spine (3 classes)	3	6	248	62	310
Haberman’s survival	2	3	244	62	306

2.4 Proposed method

The proposed technique is based on the modification of distance metric used in kNN algorithm. As it is observed that kNN algorithm works on the distance allying the actual training row of data and test row [30]. Therefore, the value of distance plays a pivotal role in class prediction using kNN. In this paper, kNN is implemented using Canberra distance metric (Algorithm 1) and then using proposed MECBD metric (Algorithm 2). Then the performance of Algorithm 1 and Algorithm 2 is compared in terms of accuracy, precision, recall, F1-score and confusion matrix. Following Fig. 1 shows the flow chart which summarizes the methodology followed in this research. The flowchart in Fig. 1 depicts the receiving of data set by application and then splitting the data set into test and training sub sets further more kNN is implemented using both MECBD and Canberra distance metrics. Based on implementation accuracy, precision, recall and f1-score, are calculated and confusion matrix is displayed.

Figure 1.

Flowchart of the methodology used.

Classification refers to the distribution of data based on classes in a data set [29]. In Fig. 2, for class prediction kNN algorithm is used for predicting the classes based on the training dataset with Canberra distance formula based on Eq. (2) as distance metric. The complete data set is given as input to the model, which is further split into training dataset D (80%) and test data set (20%). A row of data T from the test data set is picked. And for each attribute $a_{i}$ in each row R of D and $b_{i}$ attribute in T, distance (dt) among R and T is calculated using Canberra Metric. These values of $d t$ are stored in set S. Then kNN algorithm is used for class prediction based on $k$ and $d t$ values and the class of T is predicted.

Figure 2.

Algorithm 1; kNN implementation using Canberra distance metric.

In Fig. 3, kNN algorithm is used for predicting the classes based on the training dataset with MCEBD formula based on Eq. (4) as distance metric. The complete data set is given as input to the model, which is further split into training dataset D (80%) and test data set (20%). A row of data T from the test data set is picked. And for each attribute $a_{i}$ in each row R of D and $b_{i}$ attribute in T, distance (dt) among R and T is calculated using MCEBD metric. These values of $d t$ are stored in set S. Then kNN algorithm is used for class prediction based on $k$ and $d t$ values and the class of T is predicted.

This process of Algorithm 1 and Algorithm 2 repeats itself till all the rows of testing data set are processed and their classes are predicted.

Figure 3.

Algorithm 2; kNN implementation using MECBD metric.

3. Results and evaluation

To evaluate the performance of an algorithm Confusion matrix is generally used. Confusion matrix consists of actual and predicted data values in matrix representation [28]. In acquiring the accuracy value of kNN algorithm, the operational steps are as follows:

a.
Identification of test data, training data and values of $K$ on kNN.
b.
Establishing the categorization with the kNN classifier to compute the kNN model.
c.
Conduct training and framework testing processes using distinct distance calculation mechanisms.
d.
Deriving a confusion matrix and classification report.
e.
Computing the accuracy.

Machine learning methods have been used to collate classifier conduct involving supervised algorithms [31]. Different parameters were used to show improvement of kNN algorithm for class prediction when modified distance formula has been used. They were accuracy, precision, recall and F1-score [19]. Their formulas are

$\displaystyle\text{1. {{Precision}}}=\frac{\text{TrueP}}{\text{TrueP}+\text{% FalseP}}$ $\displaystyle\text{2. {{Recall}}}=\frac{\text{TrueP}}{\text{TrueP}+\text{% FalseN}}$ $\displaystyle\text{3. {{Accuracy}}}=\frac{\text{TrueP}+\text{TrueN}}{\text{% TrueP}+\text{TrueN}+\text{FalseP}+\text{FalseN}}$

where,

•
TrueP: True Positive
•
TrueN: True Negative
•
FalseP: False Positive
•
FalseN: False Negative

$\displaystyle\text{4. {{F1-Score}}}=\frac{2(\text{Precision.Recall})}{\text{% Precision}+\text{Recall}}$

To predict the classes for different datasets used, kNN algorithm technique is considered. Two different distance metrics were used, one is original Canberra distance formula and other is proposed MECBD metric. When applied on different datasets it has been observed that performance parameters values improved for proposed MECBD matrix. Performance evaluation parameters include accuracy, precision, recall and F1-score. Accuracy determines whether the model predicted the class correctly and up to which level. Precision is measure of quality which tells about the correct results returned by the algorithm [27]. Whereas, recall is the measure of quantity which tells that algorithm returned most correct results [20]. Recall tells about the in numeral of true positive predictions made out of all positive predictions that could have been guessed, recall also gives a clue of overlooked positive predictions. F1 score is computed based on mean of precision and recall [26]. The performance parameters results are summarized in Tables 2–4.

Table 2
Comparison of performance between original Canberra distance metric and MECBD metric for Spine (2 Classes) dataset for $k=$ 5, 10 and 15 values

Parameter Canberra (original) MECBD

$k=$ 5

Accuracy 0.804 0.903

Precision AB 0.87 0.93

NO 0.70 0.86

Recall AB 0.83 0.93

NO 0.76 0.86

F1-Score AB 0.85 0.93

NO 0.73 0.86

$k=$ 10

Accuracy 0.834 0.903

Precision AB 0.86 0.91

NO 0.79 0.89

Recall AB 0.90 0.95

NO 0.71 0.81

F1-Score AB 0.88 0.93

NO 0.75 0.85

$k=$ 15

Accuracy 0.853 0.872

Precision AB 0.92 0.95

NO 0.75 0.76

Recall AB 0.85 0.85

NO 0.86 0.90

F1-Score AB 0.89 0.90

NO 0.80 0.83

Table 3
Comparison of performance between original Canberra distance metric and MECBD metric for Spine (3 Classes) dataset for for $k=$ 5, 10 and 15 values

Parameter Canberra (original) MECBD

$k=$ 5

Accuracy 0.806 0.854

Precision DH 0.50 0.62

NO 0.70 0.80

SL 1.0 1.0

Recall DH 0.55 0.73

NO 0.70 0.84

SL 0.97 0.94

F1-Score DH 0.52 0.67

NO 0.70 0.80

SL 0.98 0.97

$k=$ 10

Accuracy 0.834 0.887

Precision DH 0.54 0.62

NO 0.79 0.94

SL 1.0 1.0

Recall DH 0.64 0.91

NO 0.75 0.75

SL 0.97 0.97

F1-Score DH 0.58 0.74

NO 0.77 0.83

SL 0.98 0.98

$k=$ 15

Accuracy 0.830 0.834

Precision DH 0.60 0.58

NO 0.73 0.76

SL 1.0 1.0

Recall DH 0.55 0.64

NO 0.80 0.80

SL 0.97 0.94

F1-Score DH 0.57 0.61

NO 0.76 0.78

SL 0.98 0.97

Table 4
Comparison of performance between original Canberra distance metric and MECBD metric for Haberman’s dataset dataset for $k=$ 5, 10 and 15 values

Parameter Canberra (original) MECBD

$k=$ 5

Accuracy 0.70 0.77

Precision Sur 0.77 0.78

Non-Sur 0.46 0.71

Recall Sur 0.84 0.95

Non-Sur 0.35 0.29

F1-Score Sur 0.80 0.86

Non-Sur 0.40 0.24

$k=$ 10

Accuracy 0.751 0.751

Precision Sur 0.77 0.77

Non-Sur 0.62 0.62

Recall Sur 0.93 0.93

Non-Sur 0.29 0.29

F1-Score Sur 0.85 0.85

Non-Sur 0.40 0.40

$k=$ 15

Accuracy 0.772 0.785

Precision Sur 0.78 0.80

Non-Sur 0.71 0.70

Recall Sur 0.95 0.93

Non-Sur 0.29 0.41

F1-Score Sur 0.86 0.86

Non-Sur 0.42 0.52

From the above tables, which are based on original Canberra metric and proposed MECBD metric comparison, it is inferred that for $k=$ 5 class prediction accuracy for kNN algorithm based on MECBD metric technique for Spine (2 classes) dataset increased from 0.804 to 0.903, Spine (3 classes) dataset increased from 0.806 to 0.854 and Haberman’s dataset increased from 0.70 to 0.77. Also, for $k=$ 5 the values of precision for data sets classes increased, for instance, Spine (2 classes) data set has been increased from 0.87 to 0.93 for AB class. An increase in values for recall has also been observed for the class prediction in data sets for $k=$ 5, for instance, values of DH class increased from 0.55 to 0.73 for Spine (3 classes) data set. Further, increase in F1-score has also been observed for data sets for $k=$ 5 upon implementation MECBD technique, for instance, there was increase in values for Sur class from 0.80 to 0.86 in Haberman’s dataset.

Figure 4.
Original Canberra distance confusion matrix (a) and MECBD confusion matrix (b) for Spine (2 Classes) dataset comparison for $k=$ 5.

Figure 5.
Original Canberra distance confusion matrix (a) and MECBD confusion matrix (b) for Spine (3 Classes) dataset comparison for $k=$ 5.

Figure 6.
Original Canberra Distance confusion matrix (a) and MECBD confusion matrix (b) for Haberman’s (2 Classes) dataset comparison for $k=$ 5.

All the confusion matrix in Figs 4–6 shows increase in true predicted values when MECBD has been applied in kNN algorithm for data sets under consideration for $k=$ 5 which can be seen as increase in true positive and true negative values of class.

For example, for Spine (2 Classes) dataset the accurate class prediction count, for AB class increased from 34 to 38 and for NO increased from 16 to 18 for testing part of dataset.

Figure 7.
Prediction accuracy comparison based on distance formulas for $k=$ 5.

The Fig. 7 shows comparison of kNN prediction accuracy values for original and modified distance formulas for $k=$ 5. It is observed from the graph that prediction accuracy increases on implementation of modified distance formula on the datasets under consideration. The performance evaluation of the distance metrices has been also done using precision, recall and F1-score which is shown in Figs 8–10 respectively.

Figure 8.
Precision comparison based on distance formulas for $k=$ 5.

The Fig. 8 shows precision comparison of kNN algorithm for original and modified distance formulas. It is observed from the graph that precision for AB class increases marginally (from 0.87 to 0.96) for Spine (2 classes) dataset but for NO class precision value increased considerably (from 0.70 to 0.86). Similarly, for Spine (3 classes) dataset the precision value increased for DH (from 0.50 to 0.62) and NO (from 0.70 to 0.80) classes but remained unchanged for SL (i.e. 1) class. Also, for Haberman’s dataset the Sur class had a marginal increase (from 0.77 to 0.78) in precision but Non-Sur class had a significant increase (from 0.46 to 0.71) in precision values.

Figure 9.
Recall comparison based on distance formulas for $k=$ 5

The Fig. 9 shows recall comparison of kNN algorithm for original and MECBD formulas. It is observed from the graph that recall value increased for AB class (from 0.83 to 0.93) for Spine (2 classes) dataset and for NO class (from 0.76 to 0.86). Similarly, for Spine (3 classes) dataset the recall value increased for DH (from 0.55 to 0.73) and NO (from 0.70 to 0.84) classes but fell for SL (from 0.97 to 0.94) class. Also, for Haberman’s dataset the Sur class had a marginal increase (from 0.84 to 0.95) in recall but Non-Sur class had a drop (from 0.35 to 0.29) in recall values.

Figure 10.
F1-Score comparison based on distance formulas for $k=$ 5.

The Fig. 10 shows F1-score comparison of kNN algorithm for original and MECBD formulas. It is observed from the graph that F1-score value increased for AB class (from 0.85 to 0.93) for Spine (2 classes) dataset and for NO class (from 0.73 to 0.86). Similarly, for Spine (3 classes) dataset the F1-score value increased for DH (from 0.52 to 0.67) and NO (from 0.70 to 0.80) classes but fell marginally for SL class (from 0.98 to 0.97). Also, for Haberman’s dataset the Sur class had a marginal increase (from 0.80 to 0.86) in F1-score values but Non-Sur class had a less increase (from 0.40 to 0.42).

Figure 11.
ROC curve and auc values for Spine (2 classes) dataset showing comparison between normal Canberra distance and MECBD metric implementation for $k=$ 5.

In the ROC curve shown in the Fig. 11, comparison curves plotted the predicted values of kNN model using Normal Canberra distance (blue line) and MECBD metric (orange line). By the values of area under curve (auc) for both the ROC curves it has been observed that auc value (0.958) for MECBD metric curve is more than auc value (0.873) for Normal Canberra distance curve. Since, higher value of auc tell about better performance of the model in distinguishing between the classes hence, MECBD metric has improved the prediction of the kNN algorithm for Spine (2 Classes) dataset.

Figure 12.
ROC curve and auc values for Spine (3 classes) dataset for Normal Canberra distance implementation for $k=$ 5.

Figure 13.
ROC curve and auc values for Spine (3 classes) dataset for MECBD metric implementation for $k=$ 5.

Figure 14.
ROC curve and auc values for Haberman’s dataset showing comparison between Normal Canberra distance and MECBD implementation for $k=$ 5

In Fig. 12, ROC curves for 3 classes for Spine (3 Classes) data set is shown for normal Canberra metric implementation in kNN classifier. Different values of auc is also shown for DH class (0.857), SL class (0.983) and NO class (0.910). A classifier is considered to be perfect if the true positive value is near 1.0. In the auc, more the area under the curve value better is the classifier.

In Fig. 13, ROC curves for 3 classes for Spine (3 Classes) data set is shown for MECBD metric implementation in kNN classifier. Different values of auc are also shown for DH class (0.940), SL class (0.983) and NO class (0.957). On comparing the auc values of Figs 12 and 13 it is inferred that MECBD implementation results is increased values of auc hence indicating improved prediction performance of kNN classifier.

In the ROC curve shown in the Fig. 14, comparison curves plotted the predicted values of kNN model using Normal Canberra distance (blue line) and MECBD metric (orange line). By the values of area under curve (auc) for both the ROC curves it has been observed that auc value (0.742) for MECBD metric curve is more than auc value (0.651) for Normal Canberra distance curve. It is inferred through higher value of auc that MECBD metric has improved the prediction of the kNN algorithm for Haberman’s survival dataset.
4. Conclusions and future work

Parameter	Canberra (original)	MECBD
Accuracy	0.804	0.903
Precision	AB	0.87	0.93
	NO	0.70	0.86
Recall	AB	0.83	0.93
	NO	0.76	0.86
F1-Score	AB	0.85	0.93
	NO	0.73	0.86
$k=$ 10
Accuracy	0.834	0.903
Precision	AB	0.86	0.91
	NO	0.79	0.89
Recall	AB	0.90	0.95
	NO	0.71	0.81
F1-Score	AB	0.88	0.93
	NO	0.75	0.85
$k=$ 15
Accuracy	0.853	0.872
Precision	AB	0.92	0.95
	NO	0.75	0.76
Recall	AB	0.85	0.85
	NO	0.86	0.90
F1-Score	AB	0.89	0.90
	NO	0.80	0.83

Parameter	Canberra (original)	MECBD
Accuracy	0.806	0.854
Precision	DH	0.50	0.62
	NO	0.70	0.80
	SL	1.0	1.0
Recall	DH	0.55	0.73
	NO	0.70	0.84
	SL	0.97	0.94
F1-Score	DH	0.52	0.67
	NO	0.70	0.80
	SL	0.98	0.97
$k=$ 10
Accuracy	0.834	0.887
Precision	DH	0.54	0.62
	NO	0.79	0.94
	SL	1.0	1.0
Recall	DH	0.64	0.91
	NO	0.75	0.75
	SL	0.97	0.97
F1-Score	DH	0.58	0.74
	NO	0.77	0.83
	SL	0.98	0.98
$k=$ 15
Accuracy	0.830	0.834
Precision	DH	0.60	0.58
	NO	0.73	0.76
	SL	1.0	1.0
Recall	DH	0.55	0.64
	NO	0.80	0.80
	SL	0.97	0.94
F1-Score	DH	0.57	0.61
	NO	0.76	0.78
	SL	0.98	0.97

Parameter	Canberra (original)	MECBD
Accuracy	0.70	0.77
Precision	Sur	0.77	0.78
	Non-Sur	0.46	0.71
Recall	Sur	0.84	0.95
	Non-Sur	0.35	0.29
F1-Score	Sur	0.80	0.86
	Non-Sur	0.40	0.24
$k=$ 10
Accuracy	0.751	0.751
Precision	Sur	0.77	0.77
	Non-Sur	0.62	0.62
Recall	Sur	0.93	0.93
	Non-Sur	0.29	0.29
F1-Score	Sur	0.85	0.85
	Non-Sur	0.40	0.40
$k=$ 15
Accuracy	0.772	0.785
Precision	Sur	0.78	0.80
	Non-Sur	0.71	0.70
Recall	Sur	0.95	0.93
	Non-Sur	0.29	0.41
F1-Score	Sur	0.86	0.86
	Non-Sur	0.42	0.52

In this paper, a method to improve the kNN algorithm performance for accurate class prediction by use of modified Canberra distance metric named MECBD metric has been proposed. The data sets considered in the paper are based on Spine diseases (Spine (2 classes) and Spine (3 classes) datasets) and patient survival (Haberman’s dataset). The main work includes modification of Canberra distance metric by blending it with Euclidean distance metric and then applying this modified formula on kNN algorithm, which lead to improvement in accuracy, precision, recall and F1-score upon comparison with normal Canberra distance metric and MECBD metric implementation on kNN algorithm. It is inferred that class prediction accuracy for kNN algorithm based on MECBD metric technique for Spine (2 classes) dataset increased from 0.804 to 0.903, Spine (3 classes) dataset increased from 0.806 to 0.854 and Haberman’s dataset increased from 0.70 to 0.77. Further, ROC curves and auc were also calculated and compared for k=5 for all the data sets which showed increase in prediction performance of kNN algorithm. The future work will comprise of implementation of feature selection concepts and introduce weighted attributes to improve class prediction accuracy further.

References

Mulak

Talhar

. Analysis of distance measures using k-nearest neighbor algorithm on kdd dataset. Int J Sci Res. 2015; 4(7): 2319-7064.

Sagala

. Algorithm Modified K-Nearest Neighbor (M-KNN) for Classification of Attention Deficit Hyperactive Disorder (ADHD) in Children. Login: Jurnal Teknologi Komputer. 2019 Jun 29; 13(1): 11-8.

Surya

Haneen

Ahmad

Omar

Ahmad

. Effects of Distance Measure Choice on KNN Classifier Performance-A Review. Mary Ann Liebert. 2019.

Gazalba

Reza

. Comparative analysis of k-nearest neighbor and modified k-nearest neighbor algorithm for data classification. In: 2017 2nd International conferences on Information Technology, Information Systems and Electrical Engineering (ICITISEE). IEEE; 2017 Nov 1. pp. 294-298.

Pulungan

Zarlis

Suwilo

. Analysis of braycurtis, canberra and euclidean distance in knn algorithm. Sinkron: jurnal dan penelitian teknik informatika. 2019 Sep 26; 4(1): 74-7.

Jiang

Cai

Wang

Jiang

. Survey of improving K-nearest-neighbor for classification. In: Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007). 2007.

Jaafar

Ramli

Nasir

. An improvement to the k-nearest neighbor classifier for ECG database. In: IOP Conference Series: Materials Science and Engineering. IOP Publishing: 2018 Mar 1, Vol. 318, No. 1. pp. 012046.

Ehsani

Drabløs

. Robust Distance Measures for k NN Classification of Cancer Data. Cancer informatics. 2020 Oct; 19: 1176935120965542.

Alamri

Bin-Sama

Bin-Habtoor

. Satellite image classification by using distance metric. International Journal of Computer Science And Information Security. 2016 Mar.

10.

Viriyavisuthisakul

Sanguansat

Charnkeitkong

Haruechaiyasak

. A comparison of similarity measures for online social media Thai text classification. In: 2015 12th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON). IEEE; 2015 Jun 24. pp. 1-6.

11.

Lim

T-S

. Haberman’s Survival Data Set.

12.

de Alencar Barreto

da Rocha Neto

da Mota Filho

HAF

. Vertebral Column Data Set. 2011; Available at: http://archive.ics.uci.edu/ml/datasets/vertebral+column.

13.

Liang

Pan

Yuan

Jia

Huang

. Surrogate modeling for long-term and high-resolution prediction of building thermal load with a metric-optimized KNN algorithm. Energy and Built Environment. 2022 Jun 25.

14.

Emran

. Robustness of canberra metric in computer intrusion detection. In: Proc IEEE Workshop on Information Assurance and Security. West Point, NY, USA: 2001 Jun 5. pp. 80-84.

15.

Jurman

Riccadonna

Visintainer

Furlanello

. Canberra distance on ranked lists. In: Proceedings of Advances in Panking NIPS 09 Workshop. Citeseer; 2009 Dec 11. pp. 22-27.

16.

Bouhmala

. How good is the euclidean distance metric for the clustering problem. In: 2016 5th IIAI international congress on advanced applied informatics (IIAI-AAI). IEEE; 2016 Jul 10. pp. 312-315.

17.

Bailey

. An efficient euclidean distance transform. In: International Workshop on Combinatorial Image Analysis. Berlin, Heidelberg: Springer; 2004 Dec 1. pp. 394-408.

18.

Guo

Wang

Bell

Greer

. KNN model-based approach in classification. In: OTM Confederated International Conferences On the Move to Meaningful Internet Systems. Berlin, Heidelberg: Springer; 2003 Nov 3. pp. 986-996.

19.

DeVries

Locke

Hoda

Moravek

Phan

Stratton

Kingwell

Wai

Phan

. Using a national surgical database to predict complications following posterior lumbar surgery and comparing the area under the curve and F1-score for the assessment of prognostic capability. The Spine Journal. 2021 Jul 1; 21(7): 1135-42.

20.

Prokopowicz

Mikołajewski

. Fuzzy-based computational simulations of brain functions–preliminary concept. Bio-Algorithms and Med-Systems. 2016 Sep 1; 12(3): 99-104.

21.

Xing

Bei

. Medical health big data classification based on KNN classification algorithm. IEEE Access. 2019 Nov 25; 8: 28808-19.

22.

Hassanat

Abbadi

Altarawneh

Alhasanat

. Solving the problem of the K parameter in the KNN classifier using an ensemble learning approach. arXiv preprint arXiv:1409.0919. 2014 Sep 2.

23.

Adeniyi

Wei

Yongquan

. Automated web usage data mining and recommendation system using K-Nearest Neighbor (KNN) classification method. Applied Computing and Informatics. 2016 Jan 1; 12(1): 90-108.

24.

Luo

Yang

Zhang

. Spatiotemporal traffic flow prediction with KNN and LSTM. Journal of Advanced Transportation. 2019 Feb 27; 2019.

25.

Sethi

Mittal

. A new feature selection method based on machine learning technique for air quality dataset. Journal of Statistics and Management Systems. 2019 May 19; 22(4): 697-705.

26.

Huang

Peng

Wang

Cao

Gao

Zhang

. A probabilistic method for emerging topic tracking in microblog stream. World Wide Web. 2017 Mar; 20(2): 325-50.

27.

Peng

Zeng

Sun

Huang

Wang

Tian

. Personalized app recommendation based on app permissions. World Wide Web. 2018 Jan; 21(1): 89-104.

28.

Sethi

Mittal

. Ambient air quality estimation using supervised learning techniques. EAI Endorsed Transactions on Scalable Information Systems. 2019 Jul 29; 6(22): e8.

29.

Murugappan

. Human emotion classification using wavelet transform and KNN. In: 2011 International Conference on Pattern Analysis and Intelligence Robotics. IEEE; 2011 Jun 28, Vol. 1. pp. 148-153.

30.

Zhao

Xiong

Tian

Xiang

Zhou

. K-means clustering and kNN classification based on negative databases. Applied Soft Computing. 2021 Oct 1; 110: 107732.

31.

AlZoman

Alenazi

. A comparative study of traffic classification techniques for smart city networks. Sensors. 2021 Jul 8; 21(14): 4677.

32.

Hand

Christen

Kirielle

. F*: an interpretable transformation of the F-measure. Machine Learning. 2021 Mar; 110(3): 451-6.

Parameter		Canberra (original)	MECBD
$k=$ 5
Accuracy		0.804	0.903
Precision	AB	0.87	0.93
	NO	0.70	0.86
Recall	AB	0.83	0.93
	NO	0.76	0.86
F1-Score	AB	0.85	0.93
	NO	0.73	0.86
$k=$ 10
Accuracy		0.834	0.903
Precision	AB	0.86	0.91
	NO	0.79	0.89
Recall	AB	0.90	0.95
	NO	0.71	0.81
F1-Score	AB	0.88	0.93
	NO	0.75	0.85
$k=$ 15
Accuracy		0.853	0.872
Precision	AB	0.92	0.95
	NO	0.75	0.76
Recall	AB	0.85	0.85
	NO	0.86	0.90
F1-Score	AB	0.89	0.90
	NO	0.80	0.83

Modified Euclidean-Canberra blend distance metric for kNN classifier

Abstract

Keywords

1. Introduction

2. Methodology used

2.1 kNN algorithm

2.1.2 How kNN algorithm works?

2.2 Implementation of distance measure

2.2.1 Canberra distance

Table 1 Summary of datasets used in study

References

Table 1
Summary of datasets used in study