The EvidentialK-Nearest Neighbor (EK-NN) classification rule provides a global treatment of uncertainty and imprecision in class labels, and has been widely used in pattern recognition. Nevertheless, EK-NN still suffers from the fixed presupposition of hyper-parameterKwithout prior knowledge, due to the different spatial distribution of neighbors of each pattern in Euclidean space. More concretely, neighbors of some patterns may provide confusing information and then derive wrong classification results. To address this issue, we propose a sparse reconstructive evidentialK-NN (SEK-NN) classifier, appropriately determining an individualKfor each pattern and mapping the correlations between patterns from Euclidean space to a sparse reconstructed space. To match with this sparse reconstructed space, SEK-NN supersedes the Euclidean distance by correlation coefficients to measure the dissimilarities between patterns. When handling high-dimensional data, a parallel version of SEK-NN is implemented under the Apache Spark to speed up the parameter estimation. We respectively test SEK-NN and parallel SEK-NN over 19 middle dimensional datasets, 1 middle volume and 4 high-dimensional datasets that are up to 100 thousand of dimensions. Experimental results show that SEK-NN has great prediction performance and parallel SEK-NN is able to appropriately tackle high-dimensional datasets.

Although many algorithms have been presented to tackle the curse of dimensionality in high-dimensional clustering, most of these algorithms require prior knowledge of the number of clusters. Besides, these existing algorithms create only a hard or fuzzy partition for high-dimensional objects, which are often located in highly overlapping areas. The adoption of hard/fuzzy partition ignores the ambiguity in the assignment of objects and may lead to performance degradation. To address these issues, we propose a novel self-reconstructive evidential clustering (SREC) algorithm. After learning the correlations between objects from a self-reconstruction process, SREC provides a human-readable chart. Through this chart, users can select several objects existing in the dataset as the cluster centers, instead of just detecting the number of clusters. Under the framework of evidence theory, SREC derives a more flexible credal partition that improves the fault tolerance of clustering. Ablation study demonstrates the benefits of the self-reconstruction and evidence theory. Comparison experiments on real-world datasets show that SREC consumes competitive running time and performs better than other state-of-the-art algorithms. We also apply SREC in a real-world application scenario to illustrate the rationality of selecting cluster centers by human intervention.

The performance of$K$-nearest neighbor (K-NN) classification depends significantly on the searched neighborhoods of test samples, namely, the neighborhood size$K$and the used distance metric. For the two issues, many methods either to acquire the adaptive$K$or to learn a variant metric have been presented and yielded appropriate performance. However, most of the existing methods ignore the fact that these two factors can be jointly learned. Besides, nearly all the metric learning methods aim to shrink intra-class distance while expanding inter-class distance. In this way, embedding the learned metric directly into the K-NN does not efficiently improve its accuracy. To address these issues, we propose a joint K-NN algorithm with the help of evidence theory, optimizing the joint learning of adaptive$K$and distance matrix based on the feedback from error function. Ablation study demonstrates the performance improvement from the joint learning, and comparison experiments on real-world datasets show that our approach consumes competitive running time and achieves better performance than other state-of-the-art algorithms.

A new clustering algorithm, based on Adaptive Local Density (ALD) and Evidential K-Nearest Neighbors (EKNN), is proposed here. In density peaks clustering, many other density metrics fail to detect cluster centers on multi-density datasets, however the ALD deals with the tasks very well since it can better utilize the local information. To assign the remaining points after detecting the cluster centers, an assigning strategy in the framework of evidential theory, named EKNN, is created. The advantage of EKNN is twofold. Firstly, by fusing the information of K-Nearest Neighbors, it can reduce the risk of a phenomenon named domino effect: the drawback of one classical clustering, i.e., clustering by fast search and find of density peaks (always named as DPC). Secondly, it can detect border and noise points simultaneously since a credal partition is derived which can mine ambiguity and uncertainty of data structure. Simulations on both synthetic and real-world datasets demonstrate the outstanding performance of ALD-EKNN compared with DPC and some of its successors.