基于近邻的分类方法

k-近邻法
对于新输入数据x，从训练样本集中找出k个与x最相近的样本，然后通过这k个样本的标记进行投票对x的标记给出预测。
可以采用Minkowski距离度量相似性：\[dist_p(x,y) = \lVert x-y\rVert_p = (\sum\limits_{i=1}^n |x^i-y^i|^p)^{\frac{1}{p}}\]
当\(p=1,2,\infty\)时，分别为曼哈顿距离、欧氏距离和切比雪夫距离。
如果各个维度特征的重要性不同，可以在\(|x^i-y^i|^p\)前加权重\(w_i\). 一般要求\(\sum w_i=1.\)

如果k值太小，则对噪声敏感；若k值太大，则与x无关的样本也会影响分类。一般从较小的k开始尝试，选择在验证集上错误率最小的k值。
特别地，\(k=1\)时为最近邻法。
在高维特征空间中，总能找到距离x任意小的样本比较困难。故最近邻法适合低维特征空间的分类任务。

基于K-means的分类方法
给定训练集\(D=\{(x_i,y_i)\}\). 用\(D_i\)表示属于类\(c_i\)的样本，\(i=1,2,\cdots,m.\)
K-means方法将每个\(D_i\)划分成K个单元，以属于每个单元的训练样本的特征向量均值作为该单元代表。
K-means方法的目标是寻找一个D的划分使得数据分布的方差最小，即\[(D_{i,1},\cdots,D_{i,K})=\arg\min\sum_{j=1}^K\sum_{(x_t,y_t)\in D_{i,j}}\lVert x_t - c_{i,j}\rVert _2^2.\]
一般采取近似划分方法：
1. 选择K个点\(c_{i,1},\cdots,c_{i,K}\)作为初始点；
2. 对每个\((x_t, y_t)\in D_i\), 选择与\(x_t\)最近的\(c_{i,j}\)，将\(x_t\)划分进对应的\(D_{i,j}\);
3. 此时根据已有的一组\(D_{i,j}\)更心其对应的均值\(c_{i,j}\);
4. 重复2-3，直到收敛。
对于新输入的数据点\(x\)，使用最近邻法，利用得到的\(M\times K\)个代表点进行分类。

学习向量量化方法
对每个类别\(c_m\)构建K个代表点，遵循代表点靠近同类样本且远离异类样本的原则来调整。
1. 对每个类随机选择K个点\(I_{m,1},\cdots, I_{m,k}\)作为其代表点向量的初始值；
2. 随机选择一个训练样本\((x,y)\in D\), 找到与\(x\)最近的代表点\(I_{m^*k^*}\).
3. 如果\(y=m^*\), 对\(I_{m^*k^*}\)如下更新：\[I_{m^*k^*}\leftarrow I_{m^*k^*} + \eta(x - I_{m^*k^*})\]否则：\[I_{m^*k^*}\leftarrow I_{m^*k^*} - \eta(x - I_{m^*k^*})\]4. 重复2-3直到收敛。
与K-means类似，对于新输入数据，采用最近邻法预测其类别。

    所属分类：机器学习     发表于2022-05-21