本文主要介绍一个被广泛使用的机器学习 分类算法 ,K-nearest neighbors(KNN), 中文叫 K 近邻算法.
KNN
k 近邻算法是一种基本分类和回归方法.
KNN 实际上也可以用于回归问题, 不过在工业界使用得比较广泛的还是分类问题
KNN 的核心思想也非常简单, 如果一个样本在特征空间中的 k 个最相邻的样本中的大多数属于某一个类别, 则该样本也属于这个类别 , 比如下图, 当 K=3 时, 节点会被预测属于红色椭圆类. 有点 "近朱者赤, 近墨者黑" 的感觉.
算法的原理非常简单, 但这其中隐藏了一些值得被探讨的点:
k 该如何取值?
距离最近中的 "距离" 是什幺, 怎幺计算会更好?
如果对于一个数据要计算它与模型中所有点的距离, 那当数据量很大的时候性能会很差, 怎幺改善?
在一些情况下明明数据离某一个点特别近, 但有另外两个同类的点离得很远但被 K 包含在内了, 这种情况把数据划为这两个点的同类是不是不太合理?
如果训练数据不均衡 (Imbalance data) 怎幺办?
特征的纬度量纲跨越很大 (比如 10 和 10000) 怎幺办?
特征中含有类型 (颜色: 红黄蓝绿) 怎幺处理?
下面我们一一来解决与 KNN 相关的一些问题
一些机器学习共通的内容(Feature engineering,Imbalance Data,Normalization 留待后续博客详细介绍).
超参数(Hyperparameter)K 的选取
超参数是在开始学习过程之前设置值的参数, 而不是通过训练得到的参数数据. 比如:
训练神经网络的学习速率.
学习速率
用于支持向量机的 C 和 sigma 超参数.
K 最近邻的 K.
KNN 中, K 越大则类与类的分界会越 平缓 ,K 越小则会越 陡峭 . 当 K 越小时整个模型的错误率 (Error Rate) 会越低(当然过拟合的可能就越大).
- The Validation Set Approach
- Cross-Validation
- K-d tree
- K-d trees are a wonderful invention that enable ( log ) (expected) lookup times for the nearest points to some point . This is extremely useful, especially in cases where an ( ) lookup time is intractable already.
来源: http://www.tuicool.com/articles/fEZJRzN