KNN

https://www.cnblogs.com/ybjourney/p/4702562.html

机器学习实战之kNN算法

     机器学习实战这本书是基于python的,如果我们想要完成python开发,那么python的开发环境必不可少:

(1)python3.52,64位,这是我用的python版本

(2)numpy 1.11.3,64位,这是python的科学计算包,是python的一个矩阵类型,包含数组和矩阵,提供了大量的矩阵处理函数,使运算更加容易,执行更加迅速。

(3)matplotlib 1.5.3,64位,在下载该工具时,一定要对应好python的版本,处理器版本,matplotlib可以认为是python的一个可视化工具

好了,如果你已经完成了上述的环境配置,下面就可以开始完成真正的算法实战了。

一,k近邻算法的工作原理:

存在一个样本数据集,也称作训练数据集,并且样本集中每个数据都存在标签,即我们知道样本集中每个数据与所属分类的对应关系。当输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似的数据的分类标签。一般来水,我们只选择样本数据集中最相似的k个数据(通常k不大于20),再根据多数表决原则,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

k近邻算法的一般流程:
(1)收集数据:可以采用公开的数据源

(2)准备数据:计算距离所需要的数值

(3)分析数据:剔除垃圾信息

(4)测试算法:计算错误率

(5)使用算法:运用在实际中,对实际情况进行预测

二,算法具体实施过程

(1)使用python导入数据,代码解析如下:

#-------------------------1 准备数据-------------------------------
#可以采用公开的数据集,也可以利用网络爬虫从网站上抽取数据,方式不限
#-------------------------2 准备数据------------------------------- 
#确保数据格式符合要求
#导入科学计算包(数组和矩阵)
from numpy import *
from os import listdir
#导入运算符模块
import operator

#创建符合python格式的数据集
def createDataSet():
    #数据集 list(列表形式)   
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    #标签
    labels=['A','A','B','B']
    return group, labels

(2)我们可以使用matplotlib 对数据进行分析

在python命令环境中,输入如下命令:

当输入如下命令时:

#导入制图工具
import matplotlib
import matplotlib.pyplot as plt
fig=plt.figure()
ax=fig.add_subplot(111)

ax.scatter(datingDataMat[:,1],datingDataMat[:,2])
plt.show()

最近在看《机器学习实战》这本书,因为自己本身很想深入的了解机器学习算法,加之想学python,就在朋友的推荐之下选择了这本书进行学习。

一 . K-近邻算法(KNN)概述

最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来,当测试对象的属性和某个训练对象的属性完全匹配时,便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢,其次就是存在一个测试对象同时与多个训练对象匹配,导致一个训练对象被分到了多个类的问题,基于这些问题呢,就产生了KNN。

KNN是通过测量不同特征值之间的距离进行分类。它的的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。

接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

 

二 .python实现

首先呢,需要说明的是我用的是python3.4.3,里面有一些用法与2.7还是有些出入。

建立一个KNN.py文件对算法的可行性进行验证,如下:

复制代码
#coding:utf-8

from numpy import *
import operator

##给出训练数据以及对应的类别
def createDataSet():
    group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    labels = ['A','A','B','B']
    return group,labels

###通过KNN进行分类
def classify(input,dataSe t,label,k):
    dataSize = dataSet.shape[0]
    ####计算欧式距离
    diff = tile(input,(dataSize,1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff,axis = 1)###行向量分别相加,从而得到新的一个行向量
    dist = squareDist ** 0.5
    
    ##对距离进行排序
    sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序,返回下标

    classCount={}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        ###对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1
    ###选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes
复制代码

接下来,在命令行窗口输入如下代码:

复制代码
#-*-coding:utf-8 -*-
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为:",output)
复制代码

回车之后的结果为:

测试数据为: [ 1.1  0.3] 分类为: A

答案符合我们的预期,要证明算法的准确性,势必还需要通过处理复杂问题进行验证,之后另行说明。

 

这是第一次用python编的一个小程序,势必会遇到各种问题,在此次编程调试过程中遇到了如下问题:

1 导入.py文件路径有问题,因此需要在最开始加如下代码:

  •   import sys

sys.path.append(“文件路径”),这样就不会存在路径有误的问题了;

2 在python提示代码存在问题时,一定要及时改正,改正之后保存之后再执行命令行,这一点跟MATLAB是不一样的,所以在python中最好是敲代码的同时在命令行中一段一段的验证;

3 在调用文件时函数名一定要写正确,否则会出现:’module’ object has no attribute ‘creatDataSet’;

4 ‘int’ object has no attribute ‘kclassify’,这个问题出现的原因是之前我讲文件保存名为k.py,在执行

output = K.classify(input,dataSet,labels,K)这一句就会出错。根据函数式编程的思想,每个函数都可以看为是一个变量而将K赋值后,调用k.py时就会出现问题。


三 MATLAB实现

   之前一直在用MATLAB做聚类算法的一些优化,其次就是数模的一些常用算法,对于别的算法,还真是没有上手编过,基础还在,思想还在,当然要动手编一下,也是不希望在学python的同时对MATLAB逐渐陌生吧,走走停停,停很重要。
   首先,建立KNN.m文件,如下:
复制代码
%% KNN
clear all
clc
%% data
trainData = [1.0,2.0;1.2,0.1;0.1,1.4;0.3,3.5];
trainClass = [1,1,2,2];
testData = [0.5,2.3];
k = 3;

%% distance
row = size(trainData,1);
col = size(trainData,2);
test = repmat(testData,row,1);
dis = zeros(1,row);
for i = 1:row
    diff = 0;
    for j = 1:col
        diff = diff + (test(i,j) - trainData(i,j)).^2;
    end
    dis(1,i) = diff.^0.5;
end

%% sort
jointDis = [dis;trainClass];
sortDis= sortrows(jointDis');
sortDisClass = sortDis';

%% find
class = sort(2:1:k);
member = unique(class);
num = size(member);

max = 0;
for i = 1:num
    count = find(class == member(i));
    if count > max
        max = count;
        label = member(i);
    end
end

disp('最终的分类结果为:');
fprintf('%d\n',label)
复制代码

运行之后的结果是,最终的分类结果为:2。和预期结果一样。

总而言之,用MATLAB的时间相对长点,自然也就得心应手点,不过还是希望早点能将python运用自如吧!

 

三 实战

 

之前,对KNN进行了一个简单的验证,今天我们使用KNN改进约会网站的效果,个人理解,这个问题也可以转化为其它的比如各个网站迎合客户的喜好所作出的推荐之类的,当然,今天的这个例子功能也实在有限。

 

在这里根据一个人收集的约会数据,根据主要的样本特征以及得到的分类,对一些未知类别的数据进行分类,大致就是这样。

 

我使用的是python 3.4.3,首先建立一个文件,例如date.py,具体的代码如下:

 

复制代码
#coding:utf-8

from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt


###导入特征数据
def file2matrix(filename):
    fr = open(filename)
    contain = fr.readlines()###读取文件的所有内容
    count = len(contain)
    returnMat = zeros((count,3))
    classLabelVector = []
    index = 0
    for line in contain:
        line = line.strip() ###截取所有的回车字符
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]###选取前三个元素,存储在特征矩阵中
        classLabelVector.append(listFromLine[-1])###将列表的最后一列存储到向量classLabelVector中
        index += 1
    
    ##将列表的最后一列由字符串转化为数字,便于以后的计算
    dictClassLabel = Counter(classLabelVector)
    classLabel = []
    kind = list(dictClassLabel)
    for item in classLabelVector:
        if item == kind[0]:
            item = 1
        elif item == kind[1]:
            item = 2
        else:
            item = 3
        classLabel.append(item)
    return returnMat,classLabel#####将文本中的数据导入到列表

##绘图(可以直观的表示出各特征对分类结果的影响程度)
datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))
plt.show()

## 归一化数据,保证特征等权重
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))##建立与dataSet结构一样的矩阵
    m = dataSet.shape[0]
    for i in range(1,m):
        normDataSet[i,:] = (dataSet[i,:] - minVals) / ranges
    return normDataSet,ranges,minVals

##KNN算法
def classify(input,dataSet,label,k):
    dataSize = dataSet.shape[0]
    ####计算欧式距离
    diff = tile(input,(dataSize,1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff,axis = 1)###行向量分别相加,从而得到新的一个行向量
    dist = squareDist ** 0.5
    
    ##对距离进行排序
    sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序,返回下标

    classCount={}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        ###对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1
    ###选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key
    return classes

##测试(选取10%测试)
def datingTest():
    rate = 0.10
    datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    testNum = int(m * rate)
    errorCount = 0.0
    for i in range(1,testNum):
        classifyResult = classify(normMat[i,:],normMat[testNum:m,:],datingLabels[testNum:m],3)
        print("分类后的结果为:,", classifyResult)
        print("原结果为:",datingLabels[i])
        if(classifyResult != datingLabels[i]):
                                  errorCount += 1.0
    print("误分率为:",(errorCount/float(testNum)))
                                  
###预测函数
def classifyPerson():
    resultList = ['一点也不喜欢','有一丢丢喜欢','灰常喜欢']
    percentTats = float(input("玩视频所占的时间比?"))
    miles = float(input("每年获得的飞行常客里程数?"))
    iceCream = float(input("每周所消费的冰淇淋公升数?"))
    datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet2.txt')
    normMat,ranges,minVals = autoNorm(datingDataMat)
    inArr = array([miles,percentTats,iceCream])
    classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3)
    print("你对这个人的喜欢程度:",resultList[classifierResult - 1])
复制代码

 

新建test.py文件了解程序的运行结果,代码:

 

复制代码
#coding:utf-8

from numpy import *
import operator
from collections import Counter
import matplotlib
import matplotlib.pyplot as plt

import sys
sys.path.append("D:\python\Mechine learing in Action\KNN")
import date
date.classifyPerson()
复制代码

 

运行结果如下图:

 

这样就算是成功了吧,当然,在这其中也遇到了很多的问题,我看的《机器学习实战》这本书主要还是针对于python2.7的,理所应当的我遇到了不少问题。有在学习这本书的朋友咱们可以交流下哈~

1.什么是k近邻法

k近邻法是一种基本的多分类和回归的算法,常常简称为kNN。kNN在李航的《统计学习方法》中的描述如下:

给定一个训练数据集,对新的输入实例,在数据集中找到与该实例最近邻的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。

可以用一个简单的例子说明一下kNN,二维坐标下有一些点,如图所示:

数据集包含A、B两类数据,具体如下表所示:

x y label
0 0.03 A
0.01 0 A
1 1.05 B
1 0.95 B

现有新的实例(0.1,0.1),要求将其分类。
第一步,计算输入实例和数据集各个数据的欧氏距离:[0.12, 0.01, 1.31, 1.24]
第二步,将计算的距离按照从小到大排序,统计前k个数据的类别,这里假设k为3,则前3个距离最近的数据类为AAB
第三步,将输入实例判断为频率最高的类,本例中A的频率最高(为2),即输入实例是A类数据

2.kNN三要素

kNN的三要素是k,距离度量和分类决策规则。

2.1k

如果选择小的k值,则只有和输入实例比较近的点才会对预测结果产生影响,这样做会导致分类系统的抗噪声能力弱,如果输入实例附近恰好有噪声,分类就极大地可能出错,导致过拟合。

如果选择大的k值,相当于在较大领域进行预测,假设k值和数据集数据的个数一样,则无论输入什么实例,都将分类为数据集中数量最多的类别。

一般情况下,k值选取一个比较小的数值。通常使用交叉验证法选取最优k值。

2.2距离度量

假设数据有n维,则距离的定义为:

Lp(xi,xj)=(l=1n|x(l)ix(l)j|p)1p

这里p>=1,当p=1时,称为曼哈顿距离;当p=2时,称为欧氏距离,一般都使用欧氏距离。

2.3分类决策规则

kNN的分类策略规则是多数表决规则,即前k个最小距离中数量最多的类别决定输入实例的类别。

3.使用kNN对iris数据集中的花进行分类

3.1iris数据集

iris以鸢尾花的特征作为数据来源,常用在分类操作中。该数据集由3种不同类型的鸢尾花的50个样本数据构成。其中的一个种类与另外两个种类是线性可分离的,后两个种类是非线性可分离的。
该数据集包含了5个属性:
& Sepal.Length(花萼长度),单位是cm;
& Sepal.Width(花萼宽度),单位是cm;
& Petal.Length(花瓣长度),单位是cm;
& Petal.Width(花瓣宽度),单位是cm;
& 种类:Iris Setosa(山鸢尾)、Iris Versicolour(杂色鸢尾),以及Iris Virginica(维吉尼亚鸢尾)。

由于花瓣宽度变化很小,将其省略后根据前三维数据画出散点图,如下所示:

3.2载入数据

def file2matrix(fileName):
    file = open(fileName)
    allLines = file.readlines()
    row = len(allLines)
    dataSet = zeros((row, 4))
    labels = []
    index = 0
    for line in allLines:
        line = line.strip()
        listFromLine = line.split(',')
        dataSet[index, :] = listFromLine[0:4]
        labels.append(listFromLine[-1]) #取最后一维为标签
        index += 1        
    return dataSet, labels #数据集和标签分开

3.3kNN算法

def kNN(x, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    distance1 = tile(x, (dataSetSize,1)) - dataSet #欧氏距离计算开始
    distance2 = distance1 ** 2 #每个元素平方
    distance3 = distance2.sum(axis=1) #矩阵每行相加
    distance4 = distance3 ** 0.5 #欧氏距离计算结束
    sortedIndex = distance4.argsort() #返回从小到大排序的索引
    classCount = {}
    for i in range (k): #统计前k个数据类的数量
        label = labels[sortedIndex[i]]
        classCount[label] = classCount.get(label,0) + 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) #从大到小按类别数目排序
    return sortedClassCount[0][0]

3.3kNN算法测试

def kNN_test():
    testRatio = 0.1 #取数据集的前0.1为测试数据
    dataSet, labels = file2matrix('irisdata_test.txt')
    row = dataSet.shape[0]
    testNum = int(row * testRatio)
    error = 0.0 #判断错误的个数
    for i in range (testNum):
        result = kNN(dataSet[i, :], dataSet[testNum:row, :], labels[testNum:row], 3)
        print 'the result came back with: %s, the real answer is: %s' % (result, labels[i])
        if (result != labels[i]):
            error += 1.0
    print 'error rate is: %f' % (error/float(testNum))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.4小结

  • 输出结果如下:

    分类效果还是不错的,但是由于后两种花是非线性可分离的,故在交界处的数据很可能分类错误,可以使用SVM等方法将非线性可分离的数据分离
  • 当有部分维数的数值较大的时候,会较大的影响距离计算,可以使用(xmin)/(maxmin)对该维度进行归一化处理

4.总结

  • 欢迎在我的GitHub中下载源代码,MachineLearningAction仓库里面有常见的机器学习算法处理常见数据集的各种实例
  • kNN没有明显的学习过程,属于惰性学习方法
  • kNN适合于多分类问题,当维数较大时,比SVM快
  • k值过小导致对局部数据敏感,抗噪能力差;k值过大,会因为数据集中实例不均衡导致分类出错
  • 当数据集较大时,计算量较大,因为每次分类要进行一次全局运算
  • kNN多应用于文本分类、模式识别、聚类分析,多分类领域

Leave a Reply

Your email address will not be published. Required fields are marked *