《k近邻模型和算法》由会员分享，可在线阅读，更多相关《k近邻模型和算法（3页珍藏版）》请在金锄头文库上搜索。
1、k近邻模型和算法2.1 K近邻模型K近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素 一-距离度量、k值得选择和分类规则决定。2.1.1模型K近邻法中，当训练集、距离度量（如欧式距离X k值及分类决策规则（如 多数表决）确定后，对于任何一个新的输入实例，它所属的类唯一确定。这相当 于根据上述要素将特征空间划分为一些子空间，确定子空间里的每个点所述的 类。这一事实从最近邻算法中可以看得很清楚。特征空间中，对每个实例点土，距离该点比其他店更近的所有点组成一个区 域，叫做单元。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特 征空间的一个划分。最近邻法将实例七的类作为其单元中
2、所有点的类标记。这 样，每个单元的实例点的类别时确定的。下图是二维特征空间划分的一个例子。特征空间中两个实例点的距离是两个点相似程度的反映。K近邻模型的特征 空间一般是n维实数向量空间Rn。使用的距离是欧式距离，但也可以是其他距 离，如更一般的Lp或闽科夫斯基距离。设特征空间穴是n维实数向量空间Rn，X，Xj 5, 土 -(X.,七，一,七元X = (x ,x(2),.,X (n)T, x ,x 的L 距离定义为j j jji j 的 PL (x ,x )=尤卜，一xi p pP i j I i j ) l=1/这里p 2 L当p = 2时，称为欧式距离，即xil=1P = 1时，称为曼哈顿距
3、离，L(x.,x)=乎l=1x/ x l当P = 8时，它是各个距离坐标的最大值，即L (x , x ) = max xi 一 xi8 i j / i J2.1.3 K值的选择k值的选择会对k近邻法的结果产生重大影响。如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学 习”的近似误差会减小，只有与输入实例较近的(相似的)训练实例才会对预测 结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点 非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。换句话说，k值得减 小就意味着整体模型变得复杂，容易发生过拟合。如果选择较大的k值，就相当于用较大邻域中的训练实例进行
4、预测。其优点 是可以减少学习的估计误差。但缺点是学习的近似误差会增大。这时与输入实例 较远的(不相似的)训练实例也会对预测起作用，是预测发生错误。K值得增大 就意味着整体的模型变得简单。如果k=N，那么无论输入实例是什么，都将简单的预测它属于在训练实例中 最多的类。这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可 取的。K近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训 练实例中的多数类决定输入实例的类。多数表决规则有如下解释：如果分类的损失函数为0-1损失函数，分类函数 为f : Rn c , c，,c 12 k那么误分类的概率是P(Y 丰 f (X) = 1 P
5、(Y = f (X)对给定的实例1即，其最近邻的k个训练实例点构成集合Nk(。如果涵盖Nk (1)的区域的类别是C那么误分类概率是1 EI(yt。C,) = 1 一 1 ZI(y. =c.)土 wNK (1)Xi wNK (X)I KI KZ I (y = c )要使误分类概率最小即经验风险最小，就要使% wNk (x) 1 J最大，所以多数表决规则等价于经验风险最小化。2.2 K近邻算法输入：训练数据集T = (% ,y ),(x ,y )，(x ,y ) 1122N N其中 1 w* jRn为实例的特征向量 y wy =c，c，c为实例的类别 其中， i为实例 的特征向量， i1 2 k 为实例 的类别，i=1,2, . ,N;实例特征向量x；输出：实例x所属的类y。(1) 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这 k个点的x邻域记作Nk (1)；(2) 在Nk(1)中根据分类决策规则(如多数表决)决定x的类别y：y = arg max Z I(y. = c ), i = 1,2,. N; J = 1,2,., K cj X. wNk (X)该式中，I为指示函数，即当yi = cj时I为1，否则I为0。当k取1的特殊情况时，k近邻算法即为最近邻算法。对于输入的实例点或 是特征向量x，其分类由其最邻近的点的分类决定。
