knn
特征空间: 以各个特征作为坐标轴建立一个坐标系, 坐标系对应的空间就是特征空间. 每个样本为特征空间中的一个点.
定义: 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
n维空间点a(x11,…,x1n)与b(x21,…,x2n)的欧式距离(两个n维向量):
d_{12}=\sqrt{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{2}}
计算已知类别数据集中的点与当前点之间的距离, 统计前k个点所在类别中出现频率最高的类别.
k近邻算法sklearn的api的使用
sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm=’auto’)
- n_neighbors：
- int,可选（默认= 5），k_neighbors查询默认使用的邻居数
- algorithm：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}
- 快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，
- brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。
- kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。
- ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。
距离测量
- 欧式距离(一般只用这个) :
d_{12}=\sqrt{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{2}} -
曼哈顿距离:
$$
d_{12}=\sum_{k=1}^{n}\left|x_{1 k}-x_{2 k}\right|
$$
- 切比雪夫距离:
d_{12}=\max \left(\left|x_{1 i}-x_{2 i}\right|\right)
- 闵可夫斯基距离:
d_{12}=\sqrt[p]{\sum_{k=1}^{n}\left|x_{1 k}-x_{2 k}\right|^{p}}
p=2时为欧式距离, p=1时为曼哈顿距离, p为无穷大时为切比雪夫距离.
欧式距离和闵式距离的缺点:
(1)将各个分量的量纲(scale)，也就是“单位”相同的看待了; 需要标准化 归一化处理
(2)未考虑各个分量的分布（期望，方差等）可能是不同的。
- 标准化欧式距离:
实际工作中时 先标准化, 再使用欧式距离
标准化: 把特征的数据转化成这样的数据: 平均值=0, 标准差=1
X^{*}=\frac{X-m}{s}
(X为样本集, m为平均值, s为标准差)
- 余弦距离:
计算球面的点之间的距离
两个n维样本点的夹角余弦为:
\cos (\theta)=\frac{\sum_{k=1}^{n} x_{1 k} x_{2 k}}{\sqrt{\sum_{k=1}^{n} x_{1 k}^{2}} \sqrt{\sum_{k=1}^{n} x_{2 k}^{2}}} -
汉明距离: 两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。
编码, 密码应用较多
汉明重量：是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。因此，如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。
-
杰卡德距离:
杰卡德相似系数:
J(A, B)=\frac{|A \cap B|}{|A \cup B|}
杰卡德距离:
J_{\delta}(A, B)=1-J(A, B)=\frac{|A \cup B|-|A \cap B|}{|A \cup B|} -
马氏距离:
考虑了数据集的分布
解决了闵式距离的两个缺点
k值的选择
k值小的时候模型复杂 学习能力强 学习过头 容易过拟合 易受异常点影响 过拟合估计误差偏大
k值大的时候模型简单 学习能力弱 学习不到位 容易欠拟合
近似误差: 对现有训练集的训练误差，关注训练集，如果近似误差过小可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
估计误差: 可以理解为对测试集的测试误差，关注测试集，估计误差小说明对未知数据的预测能力好，模型本身最接近最佳模型。
kd树
使用特殊的结构(树)存储训练数据, 减少计算距离的次数, 保证能够找到所有样本中离预测点最近的k个样本.
kd树构造，多维数据构造kd树
查找点：1. 从根节点出发，记录比较过的节点search_path=[(根节点), 第二个节点, 第三个节点]
- nearest = (记录当前距离查找点最近的点) dist=到nearest的距离
- 空间回溯 对比nearest , 到nearest的距离小于dist, 则比对nearest划分轴另一侧的点的距离, 若小于dist更新nearest和dist, 若全部大于dist, 删除search_path的最后一个点, 继续比对search_path当前最后一个点. 直到回溯到search_path为空
k近邻算法总结
-
优点：
- 简单有效
- 重新训练的代价低
- 适合类域交叉样本
- KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
- 适合大样本自动分类
- 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
-
缺点：
- 惰性学习
- KNN算法是懒散学习方法（lazy learning,基本上不学习），一些积极学习的算法要快很多
- 类别评分不是规格化
- 不像一些通过概率评分的分类
- 输出可解释性不强
- 例如决策树的输出可解释性就较强
- 对不均衡的样本不擅长
- 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
- 计算量较大
- 目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。
