机器学习系列--KNN分类算法

一.机器学习简介

机器学习（Machine Learning, ML）是一门多领域交叉学科，涉及概率论，统计学，逼近论，凸分析、算法复杂度理论等多门学科。专门研究计算机怎么模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能。

它是人工智能的核心，是使计算机具有智能的根本途径，其应用遍及人工智能的各个领域。目前，世界上共有几百种不同的机器学习算法。 

二.类别

1.分类

给定一堆样本数据，以及这些数据所属的类别标签，通过算法来对预测新数据的类别。有先验知识。

常用分类算法：k-最近邻法(k-nearest neighbor，kNN)，决策树分类法，朴素贝叶斯分类算法(native Bayesian classifier)、支持向量机(SVM)的分类器，神经网络法，模糊分类法等等。

2.聚类

事先并不知道一堆数据可以被划分到哪些类，通过算法来发现数据之间的相似性，从而将相似的数据划入相应的类，简单地说就是把相似的东西分到一组。没有先验知识。

常用聚类算法： K均值(K-means clustering)聚类算法、K-MEDOIDS算法、CLARANS算法；BIRCH算法、CURE算法、CHAMELEON算法等；基于密度的方法：DBSCAN算法、OPTICS算法、DENCLUE算法等；基于网格的方法：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

3.监督学习与无监督学习 

监督学习，无监督学习，半监督学习。

监督式学习技术需要关于结果的先验知识。

无监督学习技术不需要先验知识。

三.KNN分类算法

K最近邻（k-Nearest Neighbor，KNN），由你的邻居来推断出你的类别。

机器学习，算法本身不是最难的，最难的是：1.数学建模：把业务中的特性抽象成向量的过程；2.选取适合模型得数据样本。

要点：

步骤：

1.距离：计算它与训练集中每个对象的距离

二维距离

2.找邻居：固定距离最近的k个训练对象，作为测试对象的近邻

3.做分类：根据这个k个近邻归属的主要类别，来对测试对象分类：

k太小，分类结果易受到噪声点影响；k太大，近邻中又可能包含太多其它类别的点。对距离加权，可以降低k值设定的影响。k值通常是采用交叉检验来确定（以k=1为基准） 经验规则：k一般低于训练样本数的平方根。

相似度衡量：1.距离近，属于一个分类可能性大，但距离不能代表一切，有些数据的相似度衡量并不适合用距离。2.相似度衡量方法：包括欧式距离、夹角余弦等。简单应用中，一般使用欧氏距离，但对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。

类别判断：

简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。

加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类。加权更靠谱一些，根据业务和数据特性来探索。

不足之处：

样本不平衡：如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。改善方法：对此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。 

计算量较大 ：因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。改善方法：事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该方法比较适用于样本容量比较大的类域的分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

距离衡量：高维度对距离衡量的影响：变量数越多，欧式距离区分能力越差。变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化（归一化）。

性能：kNN是一种懒惰算法。（笛卡尔积）扫描全部样本计算距离。提高计算效率：压缩训练样本，浓缩技术，编辑技术（清理数据）。