Fuzzy k-NN classification with weights modified by most informative neighbors of nearest neighbors

1 Introduction

Even though it was introduced nearly seven decades ago as a simple non-parametric learning approach, k-Nearest-Neighbor (k-NN) rule [1] surpasses common classification and regression algorithms in many application domains. Recently, the optimization of convolutional neural network features for k-NN classification [2] suggested that k-NN could be an integral classification component of deep learning architectures.

The k-NN classification rule estimates the a posteriori density from the samples in the local neighborhood and assigns the most frequently observed class label to the unknown sample (sample with unknown class label). The error rate of the rule is no worse than twice the Bayes rate for dense datasets and asymptotically approaches the Bayes rate for large k [3].

The pioneering fuzzy k-NN learning approach [4] extends the k-NN rule by assigning class membership grades to the samples and determines the class membership grades of an unknown sample by using its nearest neighbors’ known class membership grades. A sequence of triples of membership vectors for the training samples, k and error rate are iteratively determined in three phases [4]. In [5], an interpretation of this method is presented and its performance is compared against the performances of two classifiers based on the Fuzzy C-means algorithm [6]. In the more general approach of [7], a soft voting for the class membership grades of an unknown sample is facilitated by weighting the known membership grades of each nearest neighbor of the unknown sample by the nearest neighbor’s normalized inverse distance to the unknown sample. The fuzzy k-NN rules of [7] are adopted as the basis of the current work.

The theoretical works of [8, 9] prove the performance bound and the convergence rate of the fuzzy generalized nearest neighbor rule.

In fuzzy rule based determination of the initial class membership grades of known samples [10], the parameters of the antecedent and consequent sets as well as feature weights are optimized with a genetic algorithm. In [11], the distance to a training sample is modified by dividing by the level of the subset to which the sample belongs and the class memberships are expressed as functions of numbers of neighbors of each class and the class memberships of the neighbors in a fuzzy decision rule. Assigning weights to neighbors based on initial membership values, distance as well as standard deviation of class membership values gives more credibility to neighbors located parallel to the vector connecting the class means [12]. The fuzzy k-NN voting scheme in [13] achieves the effect of automatically varying the effective number of nearest neighbors according to the local density of the known samples. An estimation theoretic approach [14] determines the weights used to emphasize the membership grades of the neighbors in fuzzy k-NN rule as the optimal weights of an unbiased linear mean squared error estimator for the feature vector of the unknown sample.

The intuitionistic fuzzy k-NN approach [15] thresholds both the membership and nonmembership functions to define a voting function as either the membership function, its negative, or zero. The voting functions for the k nearest neighbors are averaged and shifted to yield the class membership grades.

In the adaptable nearest neighbor selection method [16], prototype like neighbors (high membership in one class) are emphasized in deciding the final membership for the unknown sample. Pruning of the training set to a prototype set [17] has also been proposed to reduce the complexity of application of fuzzy k-NN. Similarly, the class membership grade estimates for each training vector can be computed by fuzzy k-NN and a training vector can be deleted if the difference of the actual and estimate vectors of the class membership grades has a large norm [18].

The uncertainty in the choice of initial k (no. nearest of neighbors) can be managed by extending membership grades for each known sample as interval type 2 fuzzy memberships [19]. Here, classification is performed by first assigning the weighted average of the interval type 2 fuzzy memberships of its nearest neighbors to the unknown sample and then performing type reduction. Another approach [20] is to optimize the k _init and p parameters by a genetic algorithm which has been extended [21] by allowing the k _init and p to assume sets of values where the set elements are determined by the CHCevolutionary optimization. This leads to intervals for both the class membership grades of nearest neighbors and the weights assigned to these grades. A lexicographic order is applied to the sums of intervals of the nearest neigbors for all classes to get the class label for the test sample.

In [22], basic belief masses are assigned to each subset of the set of classes for each of the k nearest neighbors of the unknown sample and combination of these masses using Dempster’s rule. Later, [23] optimizes the parameters of the classification rule of [22].

For numerical features, [24] generalized the fuzzy k-NN rule by modelling each feature as a linguistic variable using FCM [6] and strong fuzzy partitioning. Similarities of individual features and votes of training samples are then aggregated by using operators to construct the unknown sample’s membership grades.

In the literature, the notable fuzzy k-NN classifier application areas are bioinformatics, image processing and biomedical signal processing [25–28].

3 The Basic Method

Fig. 1 a) illustrates the essential mechanism of the proposed method on a 2-D example involving two linearly separable classes of known samples. The class boundaries are indicated by dotted lines and the unknown sample has an equal number of known nearest neighbors of each class (a total of k = 4) by design. Feature vectors of known data samples of each class are contained in an envelope (convex hull) that can be formed by interpolating these vectors. Rather than using the distance d _j of j-th nearest neighboring known sample to the unknown sample, the proposed approach uses the distance, d j ′ , of the envelope of c (x _j ) to the unknown sample. In the example of Fig. 1 a), the unknown sample is labelled as class B by the original fuzzy k-NN rule (crisp initialization) since it is closer to the two known nearest neighboring samples of class B than the two known nearest neighboring samples of class A. However, using d j ′ in place of d _j in the fuzzy rule changes the classification result in favor of the more meaningful label of class A. Had the set of samples been denser in the feature space, the original fuzzy rule would also have yielded label A as the classification result. Put differently, the geometric structures of class regions are exploited to compensate for the sparseness of the dataset by using d j ′ in place of d _j . OPEN IN VIEWER

As illustrated in Fig. 1 b), for an unknown sample outside the envelope of a particular class, d j ′ = ∥ v j ′ ∥ = d j sin ( α j ) where α _j is the smallest angle that v j = x ˆ - x j makes with a line segment l j ′ connecting the nearest neighbor x _j to another labelled sample x j ′ of the same class. The proposed distance d ˜ j = 0.5 ( d j + d j ′ )(5) replaces the original distance d _j in the fuzzy rule.

The proposed distance d ˜ j is meaningful only if x ˆ , the feature vector of the unknown sample, lies outside the envelope of each class (see Section 4). When the convex hull condition is satisfied, d j ′ could be interpreted as the shortest distance of x ˆ to a fictitious sample x _P of the same class as x _j and x j ′ , assumed to lie on the line containing l j ′ , i.e. x P = x j + proj x j x j ′ → v j . In order for x j ′ to provide the largest information on the class identity of x ˆ , it is required to be of the same class as x _j even though it can be a far off neighbor of x _j .

It is possible for min ( ∥ x P - x j ∥ , ∥ x P - x j ′ ∥ ) to be large or x P ∉ l j ′ . While the former necessitates interpolation of class identity using distant samples, the latter relies on extrapolation of the class identity from x j ′ to x _P if α _j  < π/2, and x _j to x _P if α _j  > π/2. To handle such cases with unreliable d j ′ , d ˜ j is opted as a more robust estimate than d j ′ .

In the general D dimensional case, the proposed fuzzy k-NN rule with crisp initialization is μ i ( x ˆ ) = ∑ j : j ∈ K i d ˜ j - p ∑ j : j ∈ K d ˜ j - p(6)

where d ˜ j = 0.5 d j ( 1 + α j ) and α _j is defined as in the 2-D example discussed above. The use of (1 + α _j ) in place of (1 + sin (α _j )) effectively increases the weight given to neighbors with small angles since sin ( α ) α is a strictly decreasing function of α _j . This modification of the proposed distance yields slightly more robust performance in the D dimensional feature space for D > 2. One can argue for this modification by referring to the 3-D drawing in Fig. 2. While for small α _j , the shortest distance of the unknown sample’s feature vector to a vector interpolated from feature vectors of the same class as x _j is possibly much shorter than that predicted by its distance to the line l j ′ , for large α _j , the difference between the two is negligible.

OPEN IN VIEWER

Fig. 2

Left: If α _j , the angle between v _j and l j ′ is large, the difference between d j ′ = ∥ v j ′ ∥ and the magnitude of v _j ’s projection onto the normal of the shaded face (the shortest distance to a vector interpolated from feature vectors of the same class as x _j ) is relatively small. Right: If α _j is small, it is likely that d j ′ is much larger than the magnitude of v _j ’s projection onto the normal of the shaded face.

OPEN IN VIEWER

Fig. 3

Two classes of samples uniformly distributed on [0,1]x[0,0.5] and [0,1]x[0.5,1]. Known samples: +, unknown samples: •, nearest neighbors: □. The colors indicate the classification decisions for k = 3 nearest neighbors. Left: Classification using d _j , Right: Classification using d ˜ j . The blown up sections show the correction of a classification decision for one unknown sample by use of d ˜ j .

For the fuzzy k-NN rule with fuzzy initialization, each nearest neighbor x _j could have multiple class memberships. Again, let v j = x ˆ - x j . For each class i with μ _i  (x _j ) >0, the smallest angle α_j,i that v _j makes with the line segment l j , i ′ connecting x _j to a sample of assigned class i, x j , i ′ , is determined. Based on the proposed distance d ˜ j , i = d j ( 1 + α j , i ) , the class membership grade of x ˆ is determined as μ i ( x ˆ ) = ∑ j : j ∈ K μ i ( x j ) d ˜ j , i - p ∑ j : j ∈ K d ˜ j , i - p(7)

In this case, the proposed distance d ˜ j , i depends on the class index as well as the nearest neighbor index.

Assuming that the density of the known samples is fairly high, the feature space position of an unknown sample relative to the convex hull of the known samples of a certain class offers a simple means for assessing the confidence in employing the proposed distance.

Specifically, three cases can be identified.

i) x ˆ ∉ conv ( S c ( x j ) ) ∀j where S _i is the set of known samples of class i (as in Fig. 1 a), b)). In this case, d j ′ correlates with the inverse of the confidence in c (x _j ).

ii) x ˆ ∈ conv ( S i 0 ) for one class i₀ s.t. c (x _j ) = i₀ ∀j even for a sparse distribution of samples in local neighborhood of x ˆ . Since the unanimous voting in the fuzzy rule yields the same classification result when d ˜ j replace d _j , d ˜ j need not replace d _j .

iii) | {i : ∃ j s . t . c (x _j ) = i} |>1 and ∃i s.t. x ˆ ∈ conv ( S i ) . Fig. 1 c) suggests that the derived distance d j ′ need not correlate with the inverse of the confidence in the class c (x _j ). Hence, in this case, d _j is employed instead of d ˜ j to determine the class of x ˆ .

Therefore, the first case is distinguished from the other two by testing x ˆ ∉ conv ( S c ( x j ) ) ∀j. If the test returns false, the proposed distance d ˜ j is not used and Equation 1 is employed with d _j as a fallback solution.

In the case of crisp initialization, the conditionally modified distance d ˆ j replaces d ˜ j in Equation 6 where d ˆ j = { d ˜ j if x ˆ ∉ conv ( S c ( x j ) ) d j otherwise(8)

For fuzzy initialization, for each class i that nearest neighbor x _j has nonzero membership grade, the inclusion of x ˆ in the convex hull of S _i is tested separately. The conditionally modified distance d ˆ j , i replaces d ˜ j , i in Equation 7 where d ˆ j , i = { d ˜ j , i if x ˆ ∉ conv ( S i ) d j otherwise(9)

In Section 5.1, a figure of merit called the grade advantage is reported alongside accuracy for each classification task. It reflects the confidence in the classification decision-making by comparing the grades of the correct class c x ˆ * and the class c x ˆ † through γ = ∑ x ˆ μ c x ˆ * ( x ˆ ) μ c x ˆ * ( x ˆ ) + μ c x ˆ † ( x ˆ )(10) where c x ˆ † = arg max i : i ¬ = c x ˆ * μ i ( x ˆ ) . Each unknown sample contributes a value between 0 and 1 to γ. The larger the γ is, the better the fuzzy k-NN rule is performing in terms of assigning grades to the classes. For a small size sample (small dataset), γ is a better predictor of the classifier performance on the population (larger dataset) than accuracy is.

In the next two subsections, all performance figures reported are based on five fold cross-validation, and the tested fuzzy k-NN rules employ unnormalized attributes and the Euclidean distance metric for selecting the nearest neighbors. The parameters of the fuzzy k-NN rules are set as k _init  = k and p = 2.

This paper has presented a new fuzzy k-NN rule based classifier. The soft voting process for the class of the unknown sample employs its shortest distance to the line passing through the nearest neighbor and a neighbor of this nearest neighbor of the same class. It is also proposed that the new distance be employed only when, for each nearest neighbor, the unknown sample lies outside of the convex hull of the set of known samples of the same class as the nearest neighbor. The proposed fuzzy k-NN rule has a significantly higher classification accuracy than the original fuzzy k-NN rule and most other fuzzy nearest neighbor type algorithms, albeit a modestly higher complexity.

In future work, it might be of interest to see if the proposed classifier can benefit from denoising and despeckling methods (e.g. [35, 36]) to improve its performance on noisy (image) data.