基于CURE聚类算法改进的原型选择算法

针对传统K近邻分类器在大规模数据集中存在时间和空间复杂度过高的问题，可采取原型选择的方法进行处理，即从原始数据集中挑选出代表原型（样例）进行K近邻分类而不降低其分类准确率.本文在CURE聚类算法的基础上，针对CURE的噪声点不易确定及代表点分散性差的特点，利用共享邻居密度度量给出了一种去噪方法和使用最大最小距离选取代表点进行改进，从而提出了一种新的原型选择算法PSCURE （improved prototype selection algorithm based on CURE algorithm）.基于UCI数据集进行实验，结果表明：提出的PSCURE原型选择算法与相关原型算法相比，不仅能筛选出较少的原型，而且可获得较高的分类准确率.

Improved Prototype Selection Algorithm Based on CURE Algorithm

Since the traditional K-nearest neighbor classifier possesses large time and space complexity for larger-scale data sets, prototype selection is an effective processed method which selects representative prototypes (instances) from the original data set for K-nearest neighbor classifier without reducing the classification accuracy. At present, there exist many prototype selection methods. In this paper, based on the existing CURE algorithm, which is difficult to determine the noise points and has bad dispersed of representative points, the shared neighbor density metric is presented to delete noise points and the maximum and minimum distances are employed to obtain scattered representative points, which generates a novel prototype selection methods PSCURE (improved Prototype Selection algorithm based on CURE algorithm). Some numerical experiments are further conducted to show the performance of the proposed prototype selection algorithm compared with other related prototype selection algorithms. The experimental results show that the proposed algorithm not only can select fewer prototypes but also can achieve higher classifier accuracy for almost all the data sets.