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

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