首页 > 代码库 > Python KNN算法
Python KNN算法
机器学习新手，接触的是《机器学习实战》这本书，感觉书中描述简单易懂，但对于python语言不熟悉的我，也有很大的空间。今天学习的是k-近邻算法。
1. 简述机器学习
在日常生活中，人们很难直接从原始数据本身获得所需信息。而机器学习就是把生活中无序的数据转换成有用的信息。例如，对于垃圾邮件的检测，侦测一个单词是否存在并没有多大的作用，然而当某几个特定单词同时出现时，再辅以考虑邮件的长度及其他因素，人们就可以更准确地判定该邮件是否为垃圾邮件。
机器学习分为监督学习和无监督学习，其中：
（1）监督学习：包含分类和回归。分类，是将实例数据划分到合适的分类中。回归，主要用于预测数值形数据。因为这类算法必须知道预测什么，即目标变量的分类信息，所以称为监督学习。
（2）无监督学习：此时数据没有类别信息，不能给定目标值。在无监督学习中，将数据集合分成由类似的对象组成的多个类的过程称为聚类，将寻找描述数据统计值的过程称为密度估计，此外，无监督学习还可以减少数据特征的维度，以便我们可以使用二维或三维图形更加直观地展示数据信息。
以下是机器学习的主要算法：
监督学习：k-近邻算法（KNN），朴素贝叶斯算法，支持向量机（SVM），决策树
线性回归，局部加权线性回归，Ridge回归，Lasso最小回归系数估计
无监督学习：K-均值，DBSCAN，最大期望算法，Parzen窗设计
2. K-近邻算法
k-近邻算法（KNN），是最基本的分类算法，其基本思想是采用测量不同特征值之间的距离方法进行分类。
算法原理：存在一个样本数据集合（训练集），并且样本集中每个数据都存在标签（即每一数据与所属分类的关系已知）。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较（计算欧氏距离），然后提取样本集中特征最相似数据（最近邻）的分类标签。一般会取前k个最相似的数据，然后取k个最相似数据中出现次数最多的标签（分类）最后新数据的分类。
算法伪码：
对未知类别属性的数据集中的每个点依次执行以下操作：1）计算已知类别数据集中的点与当前点之间的距离；2）按照距离递增次序排序；3）选取与当前点距离最小的k个点；4）确定前k个点所在类别的出现频率；5）返回前k个点出现频率最高的类别作为当前点的预测分类。欧氏距离计算：
(1).二维平面上两点xA(x1,y1)与xB(x2,y2)间的欧氏距离：
(2).三维空间两点xA(x1,y1,z1)与xB(x2,y2,z2)间的欧氏距离：
(3).两个n维向量xA(x11,x12,…,x1n)与 xB(x21,x22,…,x2n)间的欧氏距离：
算法实现如下：
#-*- coding: utf-8 -*-from numpy import *import operatordef classify(inputPoint,dataSet,labels,k): dataSetSize = dataSet.shape[0] #已知分类的数据集（训练集）的行数 #先tile函数将输入点拓展成与训练集相同维数的矩阵，再计算欧氏距离 diffMat = tile(inputPoint,(dataSetSize,1))-dataSet #样本与训练集的差值矩阵 sqDiffMat = diffMat ** 2 #差值矩阵平方 sqDistances = sqDiffMat.sum(axis=1) #计算每一行上元素的和 distances = sqDistances ** 0.5 #开方得到欧拉距离矩阵 sortedDistIndicies = distances.argsort() #按distances中元素进行升序排序后得到的对应下标的列表 #选择距离最小的k个点 classCount = {} for i in range(k): voteIlabel = labels[ sortedDistIndicies[i] ] classCount[voteIlabel] = classCount.get(voteIlabel,0)+1 #按classCount字典的第2个元素（即类别出现的次数）从大到小排序 sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) return sortedClassCount[0][0]
测试例子：
if __name__ == "__main__" : dataset = array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1]]) labels = [‘A‘, ‘A‘, ‘B‘, ‘B‘] X = array([1.2, 1.1]) Y = array([0.1, 0.1]) k = 3 labelX = classify(X,dataset,labels,k) labelY = classify(Y,dataset,labels,k) print "Your input is:", X, "and classified to class: ", labelX print "Your input is:", Y, "and classified to class: ", labelY
结果如下：
Your input is: [ 1.2 1.1] and classified to class: AYour input is: [ 0.1 0.1] and classified to class: B
参考资料：
1.《机器学习实战》