机器学习日志-04 最邻近规则分类（knn）算法（理论+python代码实现）

1.综述

1.1 over和Hat在1968年提出了最初的邻近算法

1.2分类( classification)算法

1.3输入基于实例的学习( nstar∩ce- based learning),懒惰学习( lazy learning)

2 例子

这里举个例子，假如我们有两个特征工程打斗次数与接吻次数，通过分析可以看到，我们接吻次数多的，我们归类为浪漫类型，打斗次数多的，我们归为动作片。

 

 

3.算法详述

3.1步骤:

为了判断未知实例的类别,以所有已知类别的实例作为参照

选择参数K（ K为决定参照实例的个数）

计算未知实例与所有已知实例的距离

选择最近 K个已知实例

根据少数服从多数的投票法则，让未知实例归类为K个最邻近样本中最多数的类别

3.2细节

关于K关于距离的衝量方法

3.2.1 euclidean Distance定义（欧式距离）

其他距衡量:余弦值,皮尔逊相关度,曼哈顿距离

这里用python简单写一下代码

# 求欧氏距离

import math

def ComputeEuclideanDistance(x1, y1, x2, y2):
    d = math.sqrt(math.pow((x1 - x2), 2) + math.pow((y1 - y2), 2))
    return d

其中pow函数pow（a,b）a代表函数，b代表这个函数式子的b次方

调用该函数计算前面《未知电影属于什么类型?》我们做好的特征工程，有

d_ag = ComputeEuclideanDistance(3, 104, 18, 90)
d_bg = ComputeEuclideanDistance(2, 100, 18, 90)
d_cg = ComputeEuclideanDistance(1, 81, 18, 90)
d_dg = ComputeEuclideanDistance(101, 10, 18, 90)
d_eg = ComputeEuclideanDistance(99, 5, 18, 90)
d_fg = ComputeEuclideanDistance(98, 2, 18, 90)
print("d_ag:", d_ag)
print("d_bg:", d_bg)
print("d_cg:", d_cg)
print("d_dg:", d_dg)
print("d_eg:", d_eg)
print("d_fg:", d_fg)

运行结果如下

d_ag: 20.518284528683193
d_bg: 18.867962264113206
d_cg: 19.235384061671343
d_dg: 115.27792503337315
d_eg: 117.41379816699569
d_fg: 118.92854997854805

所以结果印证了前面图片我们的测试数据

 

再举个例子

这里，蓝色代表动作类电影，红色代表爱情片，绿色是我们待分类的的测试数据

在实线圆圈内，有4个训练数据点，即K=4

根据少数服从多数原则，我们把绿点分为爱情片

假如我们扩大到虚线的圆圈，有9个训练数据点，即K=9，

同样根据少数服从多数原则，我们把绿点分为爱情片

但是假如K继续增大呢？

因此，我们可以总结KNN算法的优缺点

4.算法优缺点

4.1算法优点

简单

易于理解

容易实现

通过对K的选择可具备丢噪音数据的健壮性

4.2算法缺点

需要大量空间储存所有已知实例

算法复杂度高(需要比较所有已知实例与要分类的实例)

当其样本分布不平衡时,比如其中一类样本过大(实例数量过多)占主导的时候,新的未知实例容易被归类为这个主导样本,因为这类样本实例的数量过大,但这个新的未知实例实际并木接近目标样本

 

5.改进版本

考虑距离,根据距离加上权重（距离越近权值越大）

比如:1/d(d:距离)

 

6，代码实现

6.1数据集介绍

150个实例

萼片长度,萼片宽度,花瓣长度,花瓣宽度

类别：

6.2自行设计python程序实现knn

# 首先利用sklearn的库进行knn算法的建立与预测
# from sklearn import neighbors
# from sklearn import datasets
#
# knn = neighbors.KNeighborsClassifier()      # 调用分类器赋在变量knn上
#
# iris = datasets.load_iris()     # 返回一个数据库，赋值在iris上
#
# print iris      # 显示这个数据集
#
# knn.fit(iris.data, iris.target) # fit的第一个参数 是特征值矩阵，第二个参数是一维的向量
#
# predictedLabel = knn.predict([[0.1,0.2,0.3,0.4]])
#
# print predictedLabel

# 下面自己写一个程序实现knn算法
import csv
import random
import math
import operator



# loadDataSet函数作用，加载文件，并将文件通过随机数的方法分为训练集和测试集
# filename是指文件名,split是某一个数字，数字前的数据当做训练集，数字后的数据当做测试集
# trainingSet是训练集，testSet是测试集
def loadDataSet(filename,split,trainingSet=[] , testSet = []):
    with open(filename,"rU") as f:# 导入文件为f格式
        lines = csv.reader(f) # 读取所有的行 reader函数的作用
        dataSet = list(lines)# 将所有的行转换为list的数据节后
        for x in range(len(dataSet) -1):#x在总共的行数中遍历  ,通过控制阈值对数据集进行随机切割，分为测试集和训练集
            for y in range(4):
                dataSet[x][y] = float(dataSet[x][y])
            #将
            if random.random()<split:
                #random.random()返回随机生成的一个实数，它在[0,1)范围内
                #此函数实对每个训练集测试集split开，例如split为0.7，一般下来训练集约占0.7，测试集约占0.3
                trainingSet.append(dataSet[x])
            else:
                testSet.append(dataSet[x])

#计算欧氏距离：
# 函数的输入是两个实例和他们的维度
def euclideanDistance(vec1,vec2,length):
    distance = 0
    for x in range(length):
        distance +=pow(vec1[x] - vec2[x],2) # 对于每一个维度内进行一个差的计算，计算出所有维度的平方和
    return math.sqrt(distance)

#
# 函数作用：返回最近的k的neightbor ,即选取最近的k个训练数据集：
# 也就是返回在trainingSet中距离testInstance最近的k个邻居
def getNeighbors(trainingSet,testInstance,k):
    distances = []  # 距离的容器，用来存放所有的距离值
    length = len(testInstance) - 1 # 用来存放testInstance的维度(个数/向量的长度)
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance,trainingSet[x],length)   # 对于每一个x 计算训练集中的数据与实例的距离
        distances.append((trainingSet[x],dist))
    distances.sort(key = operator.itemgetter(1)) # 把这些距离从小到大排起来
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors # 返回最近的邻居


#通过少数服从多数进行投票，决定test数据的分类
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] +=1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.items(),key=operator.itemgetter(1))
    return sortedVotes[0][0]

#计算精确度：

def getAccuracy(testSet,predictions):
    correct = 0
    for x in range(len(testSet)):
        if str(testSet[x][-1]) == str(predictions[x]):  # [-1]值的是最后一个值，也就是每行的最后的值，即为花的分类
            correct +=1
        else:
            print ('real:',testSet[x][-1],'pre:',predictions[x])
    return (correct/float(len(testSet)))*100.0

def main():
    #print ("read data")
    trainingSet = []
    testSet = []
    split = 0.67
    #加载数据集并切割为训练集与测试集
    loadDataSet(r"D:\Machine_learning\knn\iris.txt",split,trainingSet,testSet) # r的作用是防止错误字符串意思
    #repr（）是一个非常好用的函数，该函数可以将任意数据结构直接转化为str类型
    print ('train set:'+repr(len(trainingSet)))
    print ('test set:'+repr(len(testSet)))
    print ('predictions')
    predictions = []
    k = 3
    for x in range(len(testSet)):

        neighbors = getNeighbors(trainingSet,testSet[x],k)
        result = getResponse(neighbors)
        predictions.append(result)
        
        print('>>prediction='+repr(result)+',actual'+repr(testSet[x][-1]))
    accuracy = getAccuracy(testSet,predictions)

    print('Accuracy: ' + repr(accuracy) + '%')

main()

 

6.3利用Python机器学习库sklearn实现

from sklearn import datasets
# 导入内置数据集模块
from sklearn.neighbors import KNeighborsClassifier
# 导入sklearn.neighbors模块中KNN类
import numpy as np

np.random.seed(0)
# 设置随机种子，不设置的话默认是按系统时间作为参数，因此每次调用随机模块时产生的随机数都不一样设置后每次产生的一样
iris = datasets.load_iris()
# 导入鸢尾花的数据集，iris是一个类似于结构体的东西，内部有样本数据，如果是监督学习还有标签数据
iris_x = iris.data
# 样本数据150*4二维数据，代表150个样本，每个样本4个属性分别为花瓣和花萼的长、宽
iris_y = iris.target
# 长150的以为数组，样本数据的标签
print(iris)
indices = np.random.permutation(len(iris_x))
# permutation接收一个数作为参数(150),产生一个0-149一维数组，只不过是随机打乱的，当然她也可以接收一个一维数组作为参数，结果是直接对这个数组打乱
iris_x_train = iris_x[indices[:-10]]
# 随机选取140个样本作为训练数据集
iris_y_train = iris_y[indices[:-10]]
# 并且选取这140个样本的标签作为训练数据集的标签
iris_x_test = iris_x[indices[-10:]]
# 剩下的10个样本作为测试数据集
iris_y_test = iris_y[indices[-10:]]
# 并且把剩下10个样本对应标签作为测试数据及的标签

knn = KNeighborsClassifier()
# 定义一个knn分类器对象
knn.fit(iris_x_train, iris_y_train)
# 调用该对象的训练方法，主要接收两个参数：训练数据集及其样本标签

iris_y_predict = knn.predict(iris_x_test)
# 调用该对象的测试方法，主要接收一个参数：测试数据集
probility = knn.predict_proba(iris_x_test)
# 计算各测试样本基于概率的预测
neighborpoint = knn.kneighbors(iris_x_test[-1].reshape(1, -1), 5, False)
# 计算与最后一个测试样本距离在最近的5个点，返回的是这些样本的序号组成的数组
score = knn.score(iris_x_test, iris_y_test, sample_weight=None)
# 调用该对象的打分方法，计算出准确率

print('iris_y_predict = ')
print(iris_y_predict)
# 输出测试的结果

print('iris_y_test = ')
print(iris_y_test)
# 输出原始测试数据集的正确标签，以方便对比
print('Accuracy:', score)
# 输出准确率计算结果
print('neighborpoint of last test sample:', neighborpoint)

print('probility:', probility)