用python实现k近邻算法的示例代码

K近邻算法(或简称kNN)是易于理解和实现的算法,而且是你解决问题的强大工具。

什么是kNN

kNN算法的模型就是整个训练数据集。当需要对一个未知数据实例进行预测时,kNN算法会在训练数据集中搜寻k个最相似实例。对k个最相似实例的属性进行归纳,将其作为对未知实例的预测。

相似性度量依赖于数据类型。对于实数,可以使用欧式距离来计算。其他类型的数据,如分类数据或二进制数据,可以用汉明距离。

对于回归问题,会返回k个最相似实例属性的平均值。对于分类问题,会返回k个最相似实例属性出现最多的属性。

kNN如何工作

kNN属于基于实例算法簇的竞争学习和懒惰学习算法。

基于实例的算法运用数据实例(或数据行)对问题进行建模,进而做出预测决策。kNN算法算是基于实例方法的一种极端形式,因为其保留所有的训练集数据作为模型的一部分。

kNN是一个竞争学习算法,因为为了做出决策,模型内部元素(数据实例)需要互相竞争。 数据实例之间客观相似度的计算,促使每个数据实例都希望在竞争中“获胜”或者尽可能地与给定的未知数据实例相似,继而在预测中做出贡献。

懒惰学习是指直到需要预测时算法才建立模型。它很懒,因为它只在最后一刻才开始工作。优点是只包含了与未知数据相关的数据,称之为局部模型。缺点是,在大型训练数据集中会重复相同或相似的搜索过程,带来昂贵的计算开销。

最后,kNN的强大之处在于它对数据不进行任何假设,除了任意两个数据实例之间距离的一致计算。因此,它被称为成为无参数或者非线性的,因为它没有预设的函数模型。

用python写程序真的好舒服。

import numpy as np
def read_data(filename):
  '''读取文本数据,格式:特征1  特征2 …… 类别'''
  f=open(filename,'rt')
  row_list=f.readlines() #以每行作为列表
  f.close()
  data_array=[]
  labels_vector=[]
  while True:
    if not row_list:
      break
    row=row_list.pop(0).strip().split('\t') #去除换行号,分割制表符
    temp_data_row=[float(a) for a in row[:-1]] #将字符型转换为浮点型
    data_array.append(temp_data_row) #取特征值
    labels_vector.append(row[-1])  #取最后一个作为类别标签
  return np.array(data_array),np.array(labels_vector)

def classify(test_data,dataset,labels,k):
  '''分类'''
  diff_dis_array=test_data-dataset  #使用numpy的broadcasting
  dis_array=(np.add.reduce(diff_dis_array**2,axis=-1))**0.5  #求距离
  dis_array_index=np.argsort(dis_array)  #升序距离的索引
  class_count={}
  for i in range(k):
    temp_label=labels[dis_array_index[i]]
    class_count[temp_label]=class_count.get(temp_label,0)+1 #获取类别及其次数的字典
  sorted_class_count=sorted(class_count.items(), key=lambda item:item[1],reverse=True)  #字典的值按降序排列
  return sorted_class_count[0][0]  #返回元组列表的[0][0]

def normalize(dataset):
  '''数据归一化'''
  return (dataset-dataset.min(0))/(dataset.max(0)-dataset.min(0))

k=3 #近邻数
test_data=[0,0] #待分类数据
data,labels=read_data('testdata.txt')
print('数据集:\n',data)
print('标签集:\n',labels)
result=classify(test_data,normalize(data),labels,k)
print('分类结果:',result)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python实现Dijkstra算法

    Dijkstra算法 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题.迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. 迪杰斯特拉算法是求从某一个起点到其余所有结点的最短路径,是一对多的映射关系,是一种贪婪算法 示例: 算法 算法实现流程思路: 迪杰斯特拉算法每次只找离起点最近的一个结点,并将之并入已经访问过结点的集合(以防重复访问,陷入死循环),然后将刚找到的

  • python实现随机漫步算法

    本文实例为大家分享了python实现随机漫步的具体代码,供大家参考,具体内容如下 编写randomwalk类 from random import choice class randomwalk(): def __init__(self,num_points=5000): self.num_points=num_points self.x_values=[0] self.y_values=[0] def fill_walk(self): while len(self.x_values)<self

  • python实现汉诺塔算法

    题目: 汉诺塔给出最优解,如果对汉诺塔的定义有不了解,请翻看数据结构教材. 除了最基本的之外,还有一题,给定一个数组,arr=[2,3,1,2,3],其含义是这是一个有5个圆盘的汉诺塔,每一个数字代表这个圆盘所在的位置,1代表左边的柱子,2代表中间,3代表右边.给出这个序列代表了汉诺塔移动的第几步,如果该步骤是错误的,则返回-1,所谓错误,是指该步骤不是最简便的得到汉诺塔序列的操作步骤. 分析: 1. 算法当然还是递归解了,即把n个汉诺塔盘子分解成 n - 1 个盘子的移动和一个底层盘子的移动,

  • python实现梯度下降算法

    梯度下降(Gradient Descent)算法是机器学习中使用非常广泛的优化算法.当前流行的机器学习库或者深度学习库都会包括梯度下降算法的不同变种实现. 本文主要以线性回归算法损失函数求极小值来说明如何使用梯度下降算法并给出python实现.若有不正确的地方,希望读者能指出. 梯度下降 梯度下降原理:将函数比作一座山,我们站在某个山坡上,往四周看,从哪个方向向下走一小步,能够下降的最快. 在线性回归算法中,损失函数为 在求极小值时,在数据量很小的时候,可以使用矩阵求逆的方式求最优的θ值.但当数

  • python 实现A*算法的示例代码

    A*作为最常用的路径搜索算法,值得我们去深刻的研究.路径规划项目.先看一下维基百科给的算法解释:https://en.wikipedia.org/wiki/A*_search_algorithm A *是最佳优先搜索它通过在解决方案的所有可能路径(目标)中搜索导致成本最小(行进距离最短,时间最短等)的问题来解决问题. ),并且在这些路径中,它首先考虑那些似乎最快速地引导到解决方案的路径.它是根据加权图制定的:从图的特定节点开始,它构造从该节点开始的路径树,一次一步地扩展路径,直到其一个路径在预定

  • Python实现的多叉树寻找最短路径算法示例

    本文实例讲述了Python实现的多叉树寻找最短路径算法.分享给大家供大家参考,具体如下: 多叉树的最短路径: 思想: 传入start 和 end 两个 目标值     1 找到从根节点到目标节点的路径     2 从所在路径,寻找最近的公共祖先节点,     3 对最近公共祖先根节点 拼接路径 Python代码: # -*- coding:utf-8 -*- import copy #节点数据结构 class Node(object): # 初始化一个节点 def __init__(self,v

  • 解读python如何实现决策树算法

    数据描述 每条数据项储存在列表中,最后一列储存结果 多条数据项形成数据集 data=[[d1,d2,d3...dn,result], [d1,d2,d3...dn,result], . . [d1,d2,d3...dn,result]] 决策树数据结构 class DecisionNode: '''决策树节点 ''' def __init__(self,col=-1,value=None,results=None,tb=None,fb=None): '''初始化决策树节点 args: col -

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • python实现排序算法解析

    本文实例为大家分享了python实现排序算法的具体代码,供大家参考,具体内容如下 一.冒泡排序 def bububle_sort(alist): """冒泡排序(稳定|n^2m)""" n = len(alist) for j in range(n-1): count = 0 for i in range(0,n-1-j): if alist[i]>alist[i+1]: count +=1 alist[i], alist[i+1] = a

  • 基于随机梯度下降的矩阵分解推荐算法(python)

    SVD是矩阵分解常用的方法,其原理为:矩阵M可以写成矩阵A.B与C相乘得到,而B可以与A或者C合并,就变成了两个元素M1与M2的矩阵相乘可以得到M. 矩阵分解推荐的思想就是基于此,将每个user和item的内在feature构成的矩阵分别表示为M1与M2,则内在feature的乘积得到M:因此我们可以利用已有数据(user对item的打分)通过随机梯度下降的方法计算出现有user和item最可能的feature对应到的M1与M2(相当于得到每个user和每个item的内在属性),这样就可以得到通

  • Python使用Dijkstra算法实现求解图中最短路径距离问题详解

    本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题.分享给大家供大家参考,具体如下: 这里继续前面一篇<Python基于Floyd算法求解最短路径距离问题>的内容,这里要做的是Dijkstra算法,与Floyd算法类似,二者的用途均为求解最短路径距离,在图中有着广泛的应用,二者的原理都是老生常谈了,毕竟本科学习数据结构的同学是不可能不学习这两个算法的,所以在这里我也不再累赘,只简单概述一下这个算法的核心思想: Dijkstra算法的输入有两个参数,一个是原始的数据矩

  • python实现换位加密算法的示例

    如下所示: def translationCipher(msg,key): result = [""]*key for i in range(key):#把每一列元素按照顺序相加组成新的字符序列 pointer = i while i<len(msg): result[pointer]+=msg[i] i+=key return ''.join(result) def main(): print translationCipher("hello,world",

随机推荐