python实现kNN算法

kNN(k-nearest neighbor)是一种基本的分类与回归的算法。这里我们先只讨论分类中的kNN算法。

k邻近算法的输入为实例的特征向量,对对应于特征空间中的点;输出为实例的类别,可以取多类,k近邻法是建设给定一个训练数据集,其中的实例类别已定,分类时,对于新的实例,根据其k个最邻近的训练实例的类别,通过多数表决等方式进行预测。所以可以说,k近邻法不具有显示的学习过程。k临近算法实际上是利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”

k值的选择,距离的度量和分类决策规则是k近邻算法的三个基本要素。

这里需要说明的是,对于距离的度量,我们有很多种度量方法可以选择,如欧氏距离(2-范数),曼哈顿距离(1-范数),无穷范数等,根据不同的实例,我们可以选择不同的距离度量方法。

下面给出了利用python和sklearn库实现的kNN算法的过程及部分注释:

# coding=utf-8 

# 首先利用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 

# filename是指文件名,split是某一个数字,数字前的数据当做训练集,数字后的数据当做测试集
# trainingSet是训练集,testSet是测试集
# 函数作用,加载文件,并将文件通过随机数的方法分为训练集和测试集
def loadDataset(filename, split, trainingSet=[], testSet=[]):
  with open(filename, 'rb') as csvfile:  # 导入文件为csvfile格式
    lines = csv.reader(csvfile)   # 读取所有的行 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:
        trainingSet.append(dataset[x])
      else:
        testSet.append(dataset[x]) 

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

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

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.iteritems(),key=operator.itemgetter(1),reverse=True)
  return sortedVotes[0][0] 

# 用来检验预测结果的正确率
def getAccuracy(testSet,predictions):
  correct = 0
  for x in range(len(testSet)):
    if testSet[x][-1] == predictions[x]:    # [-1]值的是最后一个值,也就是每行的最后的值,即为花的分类
      correct += 1
  return (correct/float(len(testSet))) * 100.00 

def main():
  # prepare data
  trainingSet = []
  testSet = []
  split = 0.67
  loadDataset('irisdata.txt',split,trainingSet,testSet) # r的作用是防止错误字符串意思
  print 'Train Set' + repr(len(trainingSet))
  print 'Test Set' + repr(len(testSet)) 

  # generate predicitions
  predicitions = []
  k = 3
  for x in range(len(testSet)):
    neighbors = getNeigthbors(trainingSet,testSet[x],k)
    result = getResponse(neighbors)
    predicitions.append(result)
    print('> predicition = ' + repr(result) + ', actual = ' +repr(testSet[x][-1]))
  accuracy = getAccuracy(testSet,predicitions)
  print('Accuracy:' + repr(accuracy) + '%') 

main()

程序执行后,相应的输出如下:

时间: 2017-12-17

Python代码实现KNN算法

kNN算法是k-近邻算法的简称,主要用来进行分类实践,主要思路如下: 1.存在一个训练数据集,每个数据都有对应的标签,也就是说,我们知道样本集中每一数据和他对应的类别. 2.当输入一个新数据进行类别或标签判定时,将新数据的每个特征值与训练数据集中的每个数据进行比较,计算其到训练数据集中每个点的距离(下列代码实现使用的是欧式距离). 3.然后提取k个与新数据最接近的训练数据点所对应的标签或类别. 4.出现次数最多的标签或类别,记为当前预测新数据的标签或类别. 欧式距离公式为: distance=

使用python实现knn算法

本文实例为大家分享了python实现knn算法的具体代码,供大家参考,具体内容如下 knn算法描述 对需要分类的点依次执行以下操作: 1.计算已知类别数据集中每个点与该点之间的距离 2.按照距离递增顺序排序 3.选取与该点距离最近的k个点 4.确定前k个点所在类别出现的频率 5.返回前k个点出现频率最高的类别作为该点的预测分类 knn算法实现 数据处理 #从文件中读取数据,返回的数据和分类均为二维数组 def loadDataSet(filename): dataSet = [] labels

kNN算法python实现和简单数字识别的方法

本文实例讲述了kNN算法python实现和简单数字识别的方法.分享给大家供大家参考.具体如下: kNN算法算法优缺点: 优点:精度高.对异常值不敏感.无输入数据假定 缺点:时间复杂度和空间复杂度都很高 适用数据范围:数值型和标称型 算法的思路: KNN算法(全称K最近邻算法),算法的思想很简单,简单的说就是物以类聚,也就是说我们从一堆已知的训练集中找出k个与目标最靠近的,然后看他们中最多的分类是哪个,就以这个为依据分类. 函数解析: 库函数: tile() 如tile(A,n)就是将A重复n次

Python语言描述KNN算法与Kd树

最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

以Python代码实例展示kNN算法的实际运用

邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一.所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表. kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性.该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别. kNN方法在类别决策时,只与极少量的相邻样本有关.由于kNN方法主

python机器学习实战之最近邻kNN分类器

K近邻法是有监督学习方法,原理很简单,假设我们有一堆分好类的样本数据,分好类表示每个样本都一个对应的已知类标签,当来一个测试样本要我们判断它的类别是, 就分别计算到每个样本的距离,然后选取离测试样本最近的前K个样本的标签累计投票, 得票数最多的那个标签就为测试样本的标签. 源代码详解: #-*- coding:utf-8 -*- #!/usr/bin/python # 测试代码 约会数据分类 import KNN KNN.datingClassTest1() 标签为字符串 KNN.datingC

python机器学习实战之K均值聚类

本文实例为大家分享了python K均值聚类的具体代码,供大家参考,具体内容如下 #-*- coding:utf-8 -*- #!/usr/bin/python ''''' k Means K均值聚类 ''' # 测试 # K均值聚类 import kMeans as KM KM.kMeansTest() # 二分K均值聚类 import kMeans as KM KM.biKMeansTest() # 地理位置 二分K均值聚类 import kMeans as KM KM.clusterClu

python机器学习实战之树回归详解

本文实例为大家分享了树回归的具体代码,供大家参考,具体内容如下 #-*- coding:utf-8 -*- #!/usr/bin/python ''''' 回归树 连续值回归预测 的 回归树 ''' # 测试代码 # import regTrees as RT RT.RtTreeTest() RT.RtTreeTest('ex0.txt') RT.RtTreeTest('ex2.txt') # import regTrees as RT RT.RtTreeTest('ex2.txt',ops=(

python机器学习案例教程——K最近邻算法的实现

K最近邻属于一种分类算法,他的解释最容易,近朱者赤,近墨者黑,我们想看一个人是什么样的,看他的朋友是什么样的就可以了.当然其他还牵着到,看哪方面和朋友比较接近(对象特征),怎样才算是跟朋友亲近,一起吃饭还是一起逛街算是亲近(距离函数),根据朋友的优秀不优秀如何评判目标任务优秀不优秀(分类算法),是否不同优秀程度的朋友和不同的接近程度要考虑一下(距离权重),看几个朋友合适(k值),能否以分数的形式表示优秀度(概率分布). K最近邻概念: 它的工作原理是:存在一个样本数据集合,也称作为训练样本集,并

Python机器学习logistic回归代码解析

本文主要研究的是Python机器学习logistic回归的相关内容,同时介绍了一些机器学习中的概念,具体如下. Logistic回归的主要目的:寻找一个非线性函数sigmod最佳的拟合参数 拟合.插值和逼近是数值分析的三大工具 回归:对一直公式的位置参数进行估计 拟合:把平面上的一些系列点,用一条光滑曲线连接起来 logistic主要思想:根据现有数据对分类边界线建立回归公式.以此进行分类 sigmoid函数:在神经网络中它是所谓的激励函数.当输入大于0时,输出趋向于1,输入小于0时,输出趋向0

机器学习实战之knn算法pandas

开始学习机器学习实战这本书,打算看完了再回头看 周志华的 机器学习.机器学习实战的代码都是用numpy写的,有些麻烦,所以考虑用pandas来实现代码,也能回顾之前学的 用python进行数据分析.感觉目前章节的测试方法太渣,留着以后学了更多再回头写. # coding: gbk import pandas as pd import numpy as np def getdata(path): data = pd.read_csv(path, header=None, sep='\t') cha

Python机器学习之scikit-learn库中KNN算法的封装与使用方法

本文实例讲述了Python机器学习之scikit-learn库中KNN算法的封装与使用方法.分享给大家供大家参考,具体如下: 1.工具准备,python环境,pycharm 2.在机器学习中,KNN是不需要训练过程的算法,也就是说,输入样例可以直接调用predict预测结果,训练数据集就是模型.当然这里必须将训练数据和训练标签进行拟合才能形成模型. 3.在pycharm中创建新的项目工程,并在项目下新建KNN.py文件. import numpy as np from math import s

python机器学习之KNN分类算法

本文为大家分享了python机器学习之KNN分类算法,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距离,一

Python机器学习k-近邻算法(K Nearest Neighbor)实例详解

本文实例讲述了Python机器学习k-近邻算法.分享给大家供大家参考,具体如下: 工作原理 存在一份训练样本集,并且每个样本都有属于自己的标签,即我们知道每个样本集中所属于的类别.输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后提取样本集中与之最相近的k个样本.观察并统计这k个样本的标签,选择数量最大的标签作为这个新数据的标签. 用以下这幅图可以很好的解释kNN算法: 不同形状的点,为不同标签的点.其中绿色点为未知标签的数据点.现在要对绿色点进行预测.由图不难得出

python机器学习库常用汇总

汇总整理一套Python网页爬虫,文本处理,科学计算,机器学习和数据挖掘的兵器谱. 1. Python网页爬虫工具集 一个真实的项目,一定是从获取数据开始的.无论文本处理,机器学习和数据挖掘,都需要数据,除了通过一些渠道购买或者下载的专业数据外,常常需要大家自己动手爬数据,这个时候,爬虫就显得格外重要了,幸好,Python提供了一批很不错的网页爬虫工具框架,既能爬取数据,也能获取和清洗数据,也就从这里开始了: 1.1 Scrapy 鼎鼎大名的Scrapy,相信不少同学都有耳闻,课程图谱中的很多课