A new data clustering algorithm based on the NEK-NN rule

In this paper, we investigate ways to learn efficiently from uncertain data using belief functions. In order to extract more knowledge from the imperfect and insufficient information and to improve classification accuracy, we first propose a variant of the evidential K-nearest neighbor rule, called NEK-NN, which can further improve the decision-making accuracy by using complementary information obtained during the classification process. Then, a new evidential clustering algorithm based on the NEK-NN rule (ECNEK-NN) is proposed. Starting from an initial partition, ECNEK-NN iteratively reassigns objects to clusters using the NEK-NN rule, until a stable partition is obtained. After convergence, the cluster membership of each object is described by a Dempster-Shafer mass function assigning a mass to each cluster and to the whole set of clusters. The mass assigned to the set of clusters can be used to identify outliers. Finally, several experiments based on a variety of synthetic and real datasets were performed to verify the effectiveness of ECNEK-NN in comparison with some other standard classification and clustering methods. The experimental results indicate that the proposed method generally performs better than other methods for finding a partition with an unknown number of clusters.