终于要开始写自己的第一篇博客啦,真有点小激动(手足无措 =。=!)。因为最近正在琢磨机器学习,第一篇博客就从学的第一个算法开始:k-nearest neighbors algorithm即k近邻算法。
**************************************正文分界线***************************************
据wiki:在模式识别和机器学习领域,k近邻算法(k-nearest neighbors algorithm or k-NN for short)是应用于分类问题(classification )和回归问题(regression)的一种无参数方法。分类时,k-NN输出为所属分类(class membership);回归时,k-NN输出为属性值(property value)。
分类(classification),即识别出样本所属的类别。因为还没学到regression,所以只写classification(是只会好嘛,TAT)
首先,看一下数据的形式,比如下图“基于四种特征对鸟进行分类 ”
给定训练样本集(training set),我们知道其中每条数据的label(即所属类别,比如什么鸟)。关注两个key words:特征(feature)和目标变量(target variable),每条数据均看成“特征向量+目标变量”(比如[weight, wingspan, ..., ...]+species)的形式,在这里,数据的label即目标变量。当没有label的新数据“特征向量+?”到来时,我们将它和训练样本集中的每条数据进行比对,计算他们特征向量间的距离(相似程度的度量),挑选训练样本集中k个与之距离最近的数据,观察他们的label并计数,即进行“投票表决”,票数最高的label是新数据的label(分类,并不一定正确)。
General approach to kNN
Pros: High accuracy, insensitive to outliers, no assumptions about data
Cons: Computationally expensive, requires a lot of memory
Works with: Numeric values, nominal values
[1] Harrington, Peter. Machine learning in action. Manning Publications Co., 2012.
[2] http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm#cite_note-