,想象一下,对于一个千万级别的数据集,使用蛮力运算意味着对每一个待分类的新样本,你都需要进行数千万次的平方和开根号,这实在是一件很愚蠢的事,于是便有了如下几种快速方法;
KD树(KD-tree)
KD...nkm的样本,将其划入左子树,对于在nk上大于等于nkm的样本,将其划入右子树,接着,对于左子树和右子树,我们采用类似的方法计算方差——挑选最大方差对应的特征——根据该特征的中位数建立左右子树,重复这个过程...,以递归的方式生成我们需要的KD树,更严谨的流程图如下:
下面以一个非常简单的例子来更形象的展现这个过程:
我们构造数据集{(1,3),(2.5,4),(2,3.4),(4,5),(6.3,4),...球树法(ball tree)
KD树法虽然快捷高效,但在遇到维度过高的数据或分布不均匀的数据集时效率也不太理想,譬如,以我们上面使用过的例子:
在这一轮中,图中X距离左边上部矩形内的实例点已经非常之近...,数据框或矩阵形式
test:待预测的新样本,数据框或矩阵形式
cl:训练集的特征对应的真实类别
k:整数型,控制KNN的近邻数
prob:逻辑型参数,默认为F,设置为T时,输出的结果里还会包含每个样本点被归类的概率大小