2 minute read

一、KNN

  1. 介绍
    • K-近邻（K Nearest Neighbor），1968年由Cover 和 Hart 提出1；
    • 是一种用于分类和回归的非参数统计方法2；
    • k-近邻算法是最简单的机器学习算法之一；

  2. 定义
    在特征空间 M 中给定一个点集 S 和一个目标点 q ∈ M，在 S 中找到与 q 相似度最高的 K 个点；
    M 一般为多维的欧几里得空间，相似度为欧几里得距离或曼哈顿距离；

  3. 属性
    随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍1；对于一些 K 值，K 近邻保证错误率不会超过贝叶斯的；

  4. 决策边界
    KNN 隐式地计算了决策边界，也可以显示计算；3

  5. 应用
    计算机视觉，如图像检索；

二、 KNN 的实现

对于给定数据集的最优算法是一个复杂的选择, 并且取决于多个因素:

  • 样本数量 N(i.e. n_samples) 和维度(例如. n_features).
  • Brute force 查询时间以 O[DN]增长
  • Ball tree 查询时间大约以 O[Dlog(N)]增长
  • KD tree 的查询时间 D 的变化是很难精确描述的.对于较小的D(小于20) 的成本大约是O[Dlog(N)], 并且 KD 树更加有效.对于较大的D成本的增加接近O[DN], 由于树结构引起的开销会导致查询效率比暴力还要低
    对于小数据集 (N小于30),log(N)相当于N, 暴力算法比基于树的算法更加有效.KDTree 和 BallTree 通过提供一个 leaf size 参数来解决这个问题:这控制了查询切换到暴力计算样本数量. 使得两种算法的效率都能接近于对较小的N的暴力计算的效率.

三、 实践

python 实现

四、 思考

:o: KNN 分类和 KNN 回归有什么不同？
分类结果来源于投票表决，回归结果来源于均值啥东西

:o: KNN 被用于分类时，怎么解决多数表决策略在样本分布不均衡时的缺陷？
不同类别的样本出现频率不同时，该频率主导了预测结果；
a. 使用与相似度/距离成反比的权重；
b. 或者通过数据表示形式的抽象；
例如，在自组织映射（SOM）中，取每个类别的中心作为该类别的节点，这就可以避免密度带来的影响；

:o: 使用欧氏距离作为相似度度量时，它只适用于连续变量，那么针对文本分类等离散变量的情况怎么办？
可以使用重叠度量，又叫海明距离(Hamming distance)）；

:o: KNN 的缺点是什么？
计算密集，当训练样本集变大时，计算量成倍增大；

:o: 如何减少 KNN 的计算量？ a. KD-Tree
b. Ball-Tree
c. TCFP（text categorization using feature projection）
 针对文本分类，利用特征投影法来降低与分类无关的特征，分类效果与 KNN 相近，但耗时是原来的五十分之一；

:o: 如何提升 KNN 精度？
运用一些特殊的算法来计算度量的话，k近邻分类精度可显著提高，如运用大间隔最近邻居或者邻里成分分析法；

:o: 如何避免不相关的特征带来的准确度的降低？
a. 利用进化算法优化功能扩展4；
b. 利用训练样本的互信息进行选择特征；

:o: K 如何选取？
K 值的选择取决于数据；K通常是不大于20的整数；一般情况下，在分类时较大的 K 值能够减小噪声的影响，5 但会使类别之间的界限变得模糊；一个较好的 K 值能通过各种启发式技术（超参数优化）来获取；
在二分类问题中，k取奇数有助于避免两个分类平票的情形；在此问题下，选取最佳经验k值的方法是自助法；6

TOP

附录

A. 基本概念

1. 欧几里得距离
又叫欧氏距离

2. 曼哈顿距离

3. KNN 分类
样本库中每一个样本都有标签，查询样本的类别就由距离他最近的 K 个样本（的类别）投票决定；这个策略常被用于检索；
具体过程：

  • 计算查询样本距离库中所有样本的距离；
  • 对距离进行升序排序；
  • 取前 K 个样本进行投票，得到票数最多的类别，就是查询样本的类别；
    （可以看代码）

4. KNN 回归
输出的是查询样本距离库中 K 个样本的距离的均值；
有什么用呢、取前 K 个样本的均值好，还是取前 K 个中票数最高的类别的距离均值好

B. 代码实现

1. Python 实现

#coding:utf-8

from numpy import *

class KNN():
    ##给出训练数据以及对应的类别
    def createDataSet():
        group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
        labels = ['A','A','B','B']

        for g,l in zip(group, labels):
            print(l, ":", g)
        return group,labels

    ###通过KNN进行分类
    def classify(input,dataSet,label,k):
        dataSize = dataSet.shape[0]
        ####计算欧式距离
        diff = tile(input,(dataSize,1)) - dataSet
        sqdiff = diff ** 2
        squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
        dist = squareDist ** 0.5

        ##对距离进行排序
        sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标

        classCount={}
        for i in range(k):
            voteLabel = label[sortedDistIndex[i]]
            ###对选取的K个样本所属的类别个数进行统计
            classCount[voteLabel] = classCount.get(voteLabel,0) + 1
        ###选取出现的类别次数最多的类别
        maxCount = 0
        for key,value in classCount.items():
            if value > maxCount:
                maxCount = value
                classes = key

        return classes


dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("test item:",input,"\nclass:",output)

C. 资料

  1. When Is “Nearest Neighbor” Meaningful?
  2. Belur V. Dasarathy (编). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. 1991. ISBN 0-8186-8930-7.
  3. Shakhnarovish, Darrell, and Indyk (编). Nearest-Neighbor Methods in Learning and Vision. MIT Press. 2005. ISBN 0-262-19547-X.
  4. Mäkelä H Pekkarinen A. Estimation of forest stand volumes by Landsat TM imagery and stand-level field-inventory data. Forest Ecology and Management. 2004-07-26, 196 (2–3): 245–255. doi:10.1016/j.foreco.2004.02.049.
  5. Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
  6. Scholarpedia article on k-NN
  7. google-all-pairs-similarity-search
  8. 十大经典算法 https://wizardforcel.gitbooks.io/dm-algo-top10/content/knn.html
  9. KD-Tree https://blog.csdn.net/pipisorry/article/details/52186307 https://isilic.iteye.com/blog/1831396
  10. FLANN https://blog.csdn.net/jinxueliu31/article/details/37768995

参考资料

  1. Cover TM, Hart PE (1967). “Nearest neighbor pattern classification”. IEEE Transactions on Information Theory 13 (1): 21–27. doi:10.1109/TIT.1967.1053964. ↩ ↩2

  2. Altman, N. S. An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. ↩

  3. Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). “Output-sensitive algorithms for computing nearest-neighbor decision boundaries”. Discrete and Computational Geometry 33 (4): 593–604. doi:10.1007/s00454-004-1152-0. ↩

  4. Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). “Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization”. Journal of Chemical Information and Modeling 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183. ↩

  5. Everitt, B. S., Landau, S., Leese, M. and Stahl, D.（2011）Miscellaneous Clustering Methods, in Cluster Analysis, 5th Edition, John Wiley & Sons, Ltd, Chichester, UK. ↩

  6. Hall P, Park BU, Samworth RJ. Choice of neighbor order in nearest-neighbor classification. Annals of Statistics. 2008, 36 (5): 2135–2152. doi:10.1214/07-AOS537. ↩

Comments

You May Also Enjoy