一种面向不确定标签样本的K-近邻高效决策算法

基于案例的决策是一种直接依据过去的历史案例对当前案例进行分类或者指标预测的方法，K-近邻方法就是一种广泛应用的基于案例的决策模型。在K-近邻方法中，历史案例上需要有标签，而在现实应用中，标签本身有一定的不确定性.文章详细地讨论了现有的基于K-近邻的决策方法忽略了样本标签不确定性这一问题，并基于Dempster-Shafer证据理论对标签不确定性进行建模以改善预测的性能，在此基础上结合边界树模型提高模型的运行效率.文中介绍了边界树算法的作用与原理，对如何结合传统边界树算法与样本标签的不确定性对边界树算法的节点转移策略以及决策过程进行了优化.文章最后对边界树算法的计算规模与准确率做了详细的实验论证.结果表明，文中提出的方法一方面考虑了标签的不确定性，另一方面提高了传统的K-近邻模型的决策效率.

An Efficient K-Nearest Neighbor Decision Algorithm for Samples with Uncertain Labels

Case-based decision-making is a method to directly classify or predict current cases based on past historical cases. The K-nearest neighbor method is a widely used casebased decision-making model. In the K-nearest neighbor method, historical cases need to be labeled. But in practical applications, the labels themselves have uncertainties. This article discusses the problem of label uncertainty which has been ignored in existing casebased decision-making methods in detail, and setups a label uncertainty model based on Dempster-Shafer evidence theory for improving prediction performance. In addition, in order to improve the operation efficiency, a new boundary tree algorithm by combining the traditional boundary tree algorithm and the label uncertainty is proposed. This paper introduces the function and principle of the boundary tree algorithm, and optimizes the node transfer strategy and decision process of the new boundary tree algorithm. Experimental demonstration shows that the proposed method not only takes the label uncertainty into consideration, but also improves the decision efficiency of the traditional K-nearest neighbor model.