近邻法参考样本集的最优选择

Optimal Selection of Reference Subset for Nearest Neighbor Classification

为克服近邻分类法需要大量计算和存储的缺点 ,本文利用Tabu搜索来求解满足一定错误率条件的最小参考样本集 .当错误率阈值设为 0时 ,可以得到原训练集的一致子集 .当错误率阈值设为适当的非零值时 ,可以较好地克服近邻估计的偏置 .通过在Tabu搜索中引入适当的激活 (aspiration)条件 ,避免了在可行和不可行解区间无意义的来回搜索 ,加快了收敛的速度 .实验结果表明 ,本文算法在压缩比和分类性能上都优于经典的算法 .本文还证明了Dasarathy的算法[6] 得到的最小一致子集 (MinimalConsistentSet:MCS)不是最小的 。

A new approach is presented for tackling the problem of requiring a lot of memory and computational demand for nearest neighbor classification.Tabu search is used to find the optimal condensed reference set, which has minimal sample size and satisfies a certain error rate.When the error rate threshold is set to zero,the algorithm obtains a near minimal consistent subset of a given training set.While the threshold is set to a small appropriate value,the obtained reference set may compensate the bias of the nearest neighbor estimate.An aspiration criterion for Tabu Search is introduced which aims to prevent the search process from the inefficient wandering between feasible and infeasible regions in the search space and speed up the convergence.Experimental results based on a number of typical data sets are presented and analyzed to illustrate the benefits of the proposed method.Compared to conventional methods, such as CNN and Dasarathy’s algorithm,the size of the reduced reference sets is much smaller,and the nearest neighbor classification performance is better,especially when the error rate thresholds are set to nonzero appropriate values.The experimental results also illustrate that the MCS (minimal consistent set) of Dasarathy’s algorithm is not minimal,and his candidate consistent set is not always ensured to be reducing monotonically.A counter example is also given to confirm this claim.