机器学习-K近邻(kNN)

KNN 原理

KNN特点

• 近邻分类器：一种懒惰学习器，即把未标记的案例归类为与它们最相似的带有标记的案例所在的类。当一个概念很难定义，但你看到它时知道它是什么，就适合用KNN分类。
• 优点：简单有效；数据分布无要求；训练快
• 缺点：不产生模型（发现特征间关系能力有限）；分类慢；内存大；名义变量和缺失值需要处理
• KNN算法将特征处理为一个多维特征空间内的坐标。如标记配料为水果、蔬菜和蛋白3种类型，每种配料有脆度crunshiness和甜度sweetness 2个维度特征，体现在坐标内就是x轴、y轴。

计算步骤

1. 计算距离

距离函数度量：如欧氏距离（最短的直线距离），曼哈顿距离（类似城市街区路线）。欧氏距离公式:

$$d = \sqrt{(q_1 - p_1)^2 + (q_2 - p_2)^2 + \dots + (q_n - p_n)^2}$$

因此给出具体分类的n维特征，即可计算特定样本与分类标准之间的距离，之后判断分类

2. 选择K

偏差-方差权衡：过拟合与欠拟合之间的平衡。选择一个大的K会减少噪音数据对模型的影响，但过大会导致模型总是预测数量占大多数的那个类（几乎每个训练案例都会投票表决），而非最近的邻居；较小的K值会给出更复杂的决策边界，可更精细的拟合训练数据，但K过小则会使得噪音数据或异常值过度影响案例的分类（比如贴错标签）。

实际上，K的选取取决于学习概念的难度和训练集中案例的数量。一般，K为3-10。

• 常见的方法是将k设为训练集中案例数量的平方根。
• 另一种方法是基于多个测试数据集来测试多个K值，选择一个最好分类性能的K值（有点类似于一致性聚类选择K）。
• 还有一种不常见的方法就是选择一个较大的K，再按距离远近来给一个权威投票。

3. 数据准备

• 特征标准化：将特征转换为一个标准范围内，使得特征对距离公式的贡献相对平均。如不转换，距离度量会被较大的特征值支配
• min-max标准化（0-1范围）：特征的每一个值 (x-min(x))/(max(x)-min(x))
• z-score标准化（mean=0，sd=1）：(x-mean(x))/(sd(x))
• 名义变量的距离计算：利用哑变量编码，如男/女=1/0，不需要标准化（若是有序且步长相等的名义特征，则需要转换）