顶级数据挖掘会议ICDM于2006年12月评选出了数据挖掘领域的十大经典算法:C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Na¨ıve Bayes与 CART。 以前看过关于这些数据挖掘算法,但对背后数学原理也为过多探究,因而借此整理以更深入地理解这些算法。
本文讨论的kNN算法是监督学习中分类方法的一种。所谓监督学习与非监督学习,是指训练数据是否有标注类别,若有则为监督学习,若否则为非监督学习。监督学习是根据输入数据(训练数据)学习一个模型,能对后来的输入做预测。在监督学习中,输入变量与输出变量可以是连续的,也可以是离散的。若输入变量与输出变量均为连续变量,则称为 回归 ;输出变量为有限个离散变量,则称为 分类 ;输入变量与输出变量均为变量序列,则称为 标注 [2]。
kNN算法的核心思想非常简单:在训练集中选取离输入的数据点最近的k个邻居,根据这个k个邻居中出现次数最多的类别(最大表决规则),作为该数据点的类别。
训练集$T = /lbrace (x_1,y_1),(x_2,y_2), /cdots ,(x_N,y_N)/rbrace $,其类别$y_i /in /lbrace c_1,c_2, /cdots ,c_K/rbrace $,则训练集中样本点数为$N$,类别数为$K$。输入待预测数据$x$,则预测类别
/begin{equation}
y = /arg /mathop {/max }/limits_{c_j} /sum/limits_{x_i /in N_k(x)} I(y_i = c_j),/ i = 1,2, /cdots ,N; / j = 1,2, /cdots ,K
/label{eq:obj}
/end{equation}
其中,涵盖$x$的k邻域记作$N_k(x)$,当$y_i = c_j$时指示函数$I=1$,否则$I=0$。
kNN学习模型:输入$X$输出$Y$,通过学习得到决策函数$Y=f(X)$。假设分类损失函数为0-1损失函数,即分类正确时损失函数值为0,分类错误时则为1。假如给$x$预测类别为$c_j$,即$f(X)=c_j$;同时由式子/ref{eq:obj}可知k邻域的样本点对学习模型的贡献度是均等的,则kNN学习模型误分类率为
/begin{equation}
{1 /over k}/sum/limits_{x_i /in N_k(x)} {I(y_i /ne f(x_i)} = {1 /over k}/sum/limits_{xi /in N_k(x)} {I(y_i /ne c_j)} = 1 - {1 /over k}/sum/limits_{xi /in N_k(x)} {I(y_i = c_j)}
/end{equation}
若要最小化误分类率,则应$$/mathop {/max }/limits_{{c_j}} /sum/limits_{{x_i} /in {N_k}(x)} I ({y_i} = {c_j})$$
所以,最大表决规则等价于经验风险最小化。
k值得选取对kNN学习模型有着很大的影响。若k值过小,预测结果会对噪音样本点显得异常敏感。特别地,当k等于1时,kNN退化成最近邻算法,没有了显示的学习过程。若k值过大,会有较大的邻域训练样本进行预测,可以减小噪音样本点的减少;但是距离较远的训练样本点对预测结果会有贡献,以至于造成预测结果错误。下图给出k值的选取对于预测结果的影响:
前面提到过,k邻域的样本点对预测结果的贡献度是相等的;但距离更近的样本点应有更大的相似度,其贡献度应比距离更远的样本点大。可以加上权值$w_i = 1//left/| {x_i - x} /right/|$进行修正,则最大表决原则变成:$$/mathop {/max }/limits_{{c_j}} /sum/limits_{{x_i} /in {N_k}(x)} w_i*I ({y_i} = {c_j})$$
[1] Xindong Wu, Vipin Kumar, The Top Ten Algorithms in Data Mining.[2] 李航,《统计学习方法》.