Python KNN算法

 

　　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 operator

def 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:  A

Your input is: [ 0.1  0.1] and classified to class:  B