针对传统K最近邻（KNN）算法没有学习过程，进行分类预测时需要遍历全部学习样本、时效性差且对k值敏感的缺点，本文提出了两种带学习过程的随机KNN算法（RKNN），包括对样本Bootstrap抽样的SRKNN算法和对样本特征Bootstrap抽样的ARKNN算法，均属于Bagging集成学习，学习多个简单KNN后投票输出结果。算法对样本的特征进行组合得到组合特征，简单KNN基于组合特征得到。重点研究了如何选取特征的最优组合系数，得到了取得最好分类精度时的特征最优组合系数选取规则和公式。RKNN算法在构造简单KNN时引入学习，分类时不再遍历全部学习样本而只需要用二分查找法即可，其分类时间复杂度比传统KNN算法分类时间复杂度低一个数量级。RKNN算法的分类精度比传统KNN算法的分类精度有大幅提升，解决了使用KNN算法难以选取k值的问题。理论分析和实验结果均验证了本文RKNN算法的有效性。