knn算法java源代码 knn算法代码c语言

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Knn算法原理

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别knn算法java源代码，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。看下面这幅图knn算法java源代码：

KNN的算法过程是是这样的：从上图中knn算法java源代码我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形我们可以看到，KNN本质是基于一种数据统计的方法knn算法java源代码！其实很多机器学习算法也是基于数据统计的。 KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。

KNN算法的实现就是取决于，未知样本和训练样本的“距离”。我们计算“距离”可以利用欧式距离算法：

求出K个最相近的元组后，用这些元组对应的数值的平均值作为最终结果。

可以从K=1开始，逐步增加，用检验数据来分析正确率，从而选择最优K。这个结果要均衡考虑正确率与计算量，比如K=3时，正确率为90%，而K=10时，正确率为91%，则需要考虑计算量换来的1%提升是否合算了。

（1）如果可能的话先对样本数据进行排序，从而知道只需要与哪些数据进行比较。但对于高维数据，这几乎是不可行的。

（2）将样本数据划分为多个子集合，待分类数据只需要与其中的一个或者多个子集合进行比较。比如属性是经纬度，距离是2个经纬度点之间的距离，则可以将样本根据经纬度的整数部分将各个样本分到不同的子集合去，待分类元组只需要跟与自己整数部分相同的子集合进行比较即可，当子集合内的样本数据不足K时，再和邻近的集合进行比较。

（1）理论成熟，思想简单，既可以用来做分类又可以做回归

（2）可以用于非线性分类

（3）训练时间复杂度比支持向量机之类的算法低

（4）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

（5）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属的类别，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN方法较其他方法更为适合

（6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量比较小的类域采用这种算法比较容易产生误分类情况

（1）计算量大，尤其是特征数非常多的时候

（2）样本不平衡的时候，对稀有类别的预测准确率低

（3）KD树，球树之类的模型建立需要大量的内存

（4）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

（5）相比决策树模型，KNN模型的可解释性不强

注：图片来源于：

相关问答

Q1: 简单数字识别(knn算法)

knn算法，即k-NearestNeighbor，后面的nn意思是最近邻的意思，前面的k是前k个的意思，就是找到前k个离得最近的元素

离得最近这个词具体实现有很多种，我使用的是欧式几何中的距离公式

二维中两点x(x1,y1),y(x2,y2)间距离公式为sqrt( (x1-x2)^2+(y1-y2)^2 )

推广到n维就是

x(x1,x2, … ,xn),y(y1,y2, … ,yn)

sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)

knn算法是要计算距离的，也就是数字之间的运算，而图像是png，jpg这种格式，并不是数字也不能直接参与运算，所以我们需要进行一下转换

如图所示一个数字8，首先要确定的是这一步我做的是一个最简单的转换，因为我假定背景和图之间是没有杂物的，而且整个图只有一个数字（0-9）如果遇到其他情况，比如背景色不纯或者有其他干扰图像需要重新设计转换函数

接下来就是最简单的转换，将图片白色部分（背景）变0，有图像的部分变1。转换后的大小要合适，太小会影响识别准确度，太大会增加计算量。所以我用的是书上的32*32，转换后结果如图所示

这样一来，图片就变成了能进行计算的数字了。

接下来我们需要创建一个库，这个库里面存着0-9这些数字的各种类似上图的实例。因为我们待识别的图像要进行对比，选出前k个最近的，比较的对象就是我们的库。假定库中有0-9十个数字，每个数字各有100个这种由0和1表示的实例，那么我们就有了一共1000个实例。

最后一步就是进行对比，利用开头说的欧式几何距离计算公式，首先这个32*32的方阵要转换成一个1*1024的1024维坐标表示，然后拿这个待识别的图像和库中的1000个实例进行距离计算，选出前k个距离最近的。比如50个，这50个里面出现次数最多的数字除以50就是结果数字的概率。比如50个里面数字8出现40次，那么待识别数字是8的可能性就是40/50 = 80%

个人理解：

只能识别单个数字，背景不能有干扰。如果想多数字识别或者背景有干扰需要针对具体情况考虑具体的图像转01的方法。

数字识别非常依赖库中的图像，库中的图像的样子严重影响图像的识别（因为我们是和库中的一一对比找出距离最近的前k个），所以数字的粗细，高低，胖瘦等待都是决定性因素，建库时一定全面考虑数字的可能样子

计算量比较大，待识别图像要和库中所有实例一一计算，如果使用32*32，就已经是1024维了。如果库中有1000个，那就是1024维向量之间的1000次计算，图像更清晰，库更丰富只会使计算量更大

对于其他可以直接计算距离的数值型问题，可以用欧式距离，也可以用其他能代表距离的计算公式，对于非数值型的问题需要进行合适的转换，转换方式很重要，我觉得首先信息不能丢失，其次要精确不能模糊，要实现图片转换前后是一对一的关系

参考资料：机器学习实战 [美] Peter Harrington 人民邮电出版社

python源码

import numpy

import os

from PIL import Image

import heapq

from collections import Counter

def pictureconvert(filename1,filename2,size=(32,32)):

#filename1待识别图像，filename2 待识别图像转换为01txt文件输出，size图像大小，默认32*32

image_file = Image.open(filename1)

image_file = image_file.resize(size)

width,height = image_file.size

f1 = open(filename1,'r')

f2 = open(filename2,'w')

for i in range(height):

for j in range(width):

pixel = image_file.getpixel((j,i))

pixel = pixel[0] + pixel[1] + pixel[2]

if(pixel == 0):

pixel = 0

elif(pixel != 765 and pixel != 0):

pixel = 1

# 0代表黑色（无图像），255代表白色（有图像）

# 0/255 = 0,255/255 = 1

f2.write(str(pixel))

if(j == width-1):

f2.write('\n')

f1.close()

f2.close()

def imgvector(filename):

#filename将待识别图像的01txt文件转换为向量

vector = numpy.zeros((1,1024),numpy.int)

with open(filename) as f:

for i in range(0,32):

linestr = f.readline()

for j in range(0,32):

vector[0,32*i+j] = int(linestr[j])

return vector

def compare(filename1,filename2):

#compare直接读取资源库识别

#filename1资源库目录，filename2 待识别图像01txt文档路径

trainingfilelist = os.listdir(filename1)

m = len(trainingfilelist)

labelvector = []

trainingmatrix = numpy.zeros((m, 1024), numpy.int8)

for i in range(0,m):

filenamestr = trainingfilelist[i]

filestr = filenamestr.split('.')[0]

classnumber = int(filestr.split('_')[0])

labelvector.append(classnumber)

trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)

textvector = imgvector(filename2)

resultdistance = numpy.zeros((1,m))

result = []

for i in range(0,m):

resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])

resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)

for i in resultindices:

result.append(labelvector[i])

number = Counter(result).most_common(1)

print('此数字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))

def distinguish(filename1,filename2,filename3,size=(32,32)):

# filename1 png，jpg等格式原始图像路径，filename2 原始图像转换成01txt文件路径，filename3 资源库路径

pictureconvert(filename1,filename2,size)

compare(filename3,filename2)

url1 = "/Users/wang/Desktop/number.png"

url2 = "/Users/wang/Desktop/number.txt"

traininglibrary = "/Users/wang/Documents/trainingDigits"

distinguish(url1,url2,traininglibrary)

Q2: kNN（k-NearestNeighbor）算法

参考《数据挖掘10大算法》对kNN算法进行基本总结，附有一个Python3的简例。

基本思想

从训练集中找出 k 个最接近测试对象的训练对象，再从这 k 个对象中找出居于主导的类别，将其赋给测试对象。

定位

由于这种总体占优的决策模式，对于类域的交叉、重叠较多的或者多模型、多标签的待分样本集来说，kNN方法较其他方法更为适合。kNN算法属于有监督学习的分类算法。

避开了两个问题

（1）分类时对象之间不可能完全匹配（kNN方法计算的是对象之间的距离）；

（2）具有相同属性的对象有不同的类别（kNN方法依据总体占优的类别进行决策，而不是单一对象的类别进行决策）。

需要考虑几个关键要素

（1）训练集；

（2）用于计算对象之间临近的程度或者其他相似的指标；

（3）最近邻的个数 k；

（4）基于 k 个最近邻及其类别对目标对象类别进行判定的方法。

kNN方法很容易理解和实现，在一定条件下，其分类错误率不会超过最优贝叶斯错误率的两倍。一般情况下，kNN方法的错误率会逐渐收敛到最优贝叶斯错误率，可以用作后者的近似。

基本算法

算法的存储复杂度为O(n)，时间复杂度为O(n)，其中 n 为训练对象的数量。

影响kNN算法性能的几个关键因素

（1）k 值的选择；

如果 k 值选得过小，结果就会对噪声点特别敏感；k 值选得过大就会使得近邻中包含太多别的类的点。最佳 k 值的估计可以使用交叉验证的方法。通常，使用 k=1会有一个比较好的结果（特别是对于小数据集的情况）。但是，在样本很充足的情况下，选择较大的 k 值可以提高抗噪能力。

（2）类别决策时的综合方法；

对目标对象的类别进行决策，最简单的就是使用总体占优方法（简单投票，票数最多的一类胜出）。稍微复杂一点，考虑近邻中每个点与目标对象的距离不同，对决策的份量进行加权考虑。

（3）距离测量标准的选择。

距离测量的标准一般选择欧几里得距离或者曼哈顿距离。

简单例子

Q3: 怎样在spark里跑java版的knn算法

将KNN算法调用Spark的api进行重写。然后就可以在sparkshell里运行了

Q4: 发现公司里的大数据开发挣得很多，想转行，

转行这个词汇，一直是职场上此起彼伏的一个热门话题，相信很多朋友都想过或已经经历过转行。工作可谓是我们生存乃至生活的主要收入来源，谁都希望拥有一份高薪又稳定的工作，以此来改善自己的生活和实现自己的大大小小的梦想!但又担心转行后的工作待遇达不到自己的预期，顾虑重重……

不少想进入大数据分析行业的零基础学员经常会有这样一些疑问：大数据分析零基础应该怎么学习?自己适合学习大数据分析吗?人生，就是在不断地做选择，然后在这个选择过程中成长，让自己从一棵小树苗变成参天大树。就是我们每个对大数据充满幻想终于下定决心行动的学员的选择，我们给了自己4个月的时间，想要在大数据分析这个领域汲取养分，让自己壮大成长。

【明确方向】

通过国家的战略规划，看到BAT的大牛们都在大数据行业布局，新闻媒体追捧这大数据分析行业的项目和热点，我想如果我还没有能力独立判断的时候，跟着国家政策和互联网大佬们的步调走，这应该是错不了的。

【付诸行动】

明确了方向之后，我就整装待发，刚开始是在网络上购买了很多的视频教程，也买了很多书籍，但是最大的问题就在于，我不知道怎么入手，没关系，有信心有耐心肯定能战胜困难，我坚持了一个月，学习的节奏越来越乱，陆陆续续出现了很多的问题，没人指导，请教了几个业内的朋友，但对方工作繁忙，问了几次之后就不好意思了，自学陷入了死循环。

意识到我学习效率的低下，以及无人指导的问题想想未来的康庄大道，咬咬牙告诉自己，一定好好好学，不然就浪费太多时间最后还会是一无所获。最后找到组织(AAA教育)一起学习进步!

大数据分析零基础学习路线，有信心能坚持学习的话，那就当下开始行动吧!

一、大数据技术基础

1、linux操作基础

linux系统简介与安装

linux常用命令–文件操作

linux常用命令–用户管理与权限

linux常用命令–系统管理

linux常用命令–免密登陆配置与网络管理

linux上常用软件安装

linux本地yum源配置及yum软件安装

linux防火墙配置

linux高级文本处理命令cut、sed、awk

linux定时任务crontab

2、shell编程

shell编程–基本语法

shell编程–流程控制

shell编程–函数

shell编程–综合案例–自动化部署脚本

3、内存数据库redis

redis和nosql简介

redis客户端连接

redis的string类型数据结构操作及应用-对象缓存

redis的list类型数据结构操作及应用案例-任务调度队列

redis的hash及set数据结构操作及应用案例-购物车

redis的sortedset数据结构操作及应用案例-排行榜

4、布式协调服务zookeeper

zookeeper简介及应用场景

zookeeper集群安装部署

zookeeper的数据节点与命令行操作

zookeeper的java客户端基本操作及事件监听

zookeeper核心机制及数据节点

zookeeper应用案例–分布式共享资源锁

zookeeper应用案例–服务器上下线动态感知

zookeeper的数据一致性原理及leader选举机制

5、java高级特性增强

Java多线程基本知识

Java同步关键词详解

java并发包线程池及在开源软件中的应用

Java并发包消息队里及在开源软件中的应用

Java JMS技术

Java动态代理反射

6、轻量级RPC框架开发

RPC原理学习

Nio原理学习

Netty常用API学习

轻量级RPC框架需求分析及原理分析

轻量级RPC框架开发

二、离线计算系统

1、hadoop快速入门

hadoop背景介绍

分布式系统概述

离线数据分析流程介绍

集群搭建

集群使用初步

2、HDFS增强

HDFS的概念和特性

HDFS的shell(命令行客户端)操作

HDFS的工作机制

NAMENODE的工作机制

java的api操作

案例1：开发shell采集脚本

3、MAPREDUCE详解

自定义hadoop的RPC框架

Mapreduce编程规范及示例编写

Mapreduce程序运行模式及debug方法

mapreduce程序运行模式的内在机理

mapreduce运算框架的主体工作流程

自定义对象的序列化方法

MapReduce编程案例

4、MAPREDUCE增强

Mapreduce排序

自定义partitioner

Mapreduce的combiner

mapreduce工作机制详解

5、MAPREDUCE实战

maptask并行度机制-文件切片

maptask并行度设置

倒排索引

共同好友

6、federation介绍和hive使用

Hadoop的HA机制

HA集群的安装部署

集群运维测试之Datanode动态上下线

集群运维测试之Namenode状态切换管理

集群运维测试之数据块的balance

HA下HDFS-API变化

hive简介

hive架构

hive安装部署

hvie初使用

7、hive增强和flume介绍

HQL-DDL基本语法

HQL-DML基本语法

HIVE的join

HIVE 参数配置

HIVE 自定义函数和Transform

HIVE 执行HQL的实例分析

HIVE最佳实践注意点

HIVE优化策略

HIVE实战案例

Flume介绍

Flume的安装部署

案例：采集目录到HDFS

案例：采集文件到HDFS

三、流式计算

1、Storm从入门到精通

Storm是什么

Storm架构分析

Storm编程模型、Tuple源码、并发度分析

Storm WordCount案例及常用Api分析

Storm集群部署实战

Storm+Kafka+Redis业务指标计算

Storm源码下载编译

Strom集群启动及源码分析

Storm任务提交及源码分析

Storm数据发送流程分析

Storm通信机制分析

Storm消息容错机制及源码分析

Storm多stream项目分析

编写自己的流式任务执行框架

2、Storm上下游及架构集成

消息队列是什么

Kakfa核心组件

Kafka集群部署实战及常用命令

Kafka配置文件梳理

Kakfa JavaApi学习

Kafka文件存储机制分析

Redis基础及单机环境部署

Redis数据结构及典型案例

Flume快速入门

Flume+Kafka+Storm+Redis整合

四、内存计算体系Spark

1、scala编程

scala编程介绍

scala相关软件安装

scala基础语法

scala方法和函数

scala函数式编程特点

scala数组和集合

scala编程练习(单机版WordCount)

scala面向对象

scala模式匹配

actor编程介绍

option和偏函数

实战：actor的并发WordCount

柯里化

隐式转换

2、AKKA与RPC

Akka并发编程框架

实战：RPC编程实战

3、Spark快速入门

spark介绍

spark环境搭建

RDD简介

RDD的转换和动作

实战：RDD综合练习

RDD高级算子

自定义Partitioner

实战：网站访问次数

广播变量

实战：根据IP计算归属地

自定义排序

利用JDBC RDD实现数据导入导出

WorldCount执行流程详解

4、RDD详解

RDD依赖关系

RDD缓存机制

RDD的Checkpoint检查点机制

Spark任务执行过程分析

RDD的Stage划分

5、Spark-Sql应用

Spark-SQL

Spark结合Hive

DataFrame

实战：Spark-SQL和DataFrame案例

6、SparkStreaming应用实战

Spark-Streaming简介

Spark-Streaming编程

实战：StageFulWordCount

Flume结合Spark Streaming

Kafka结合Spark Streaming

窗口函数

ELK技术栈介绍

ElasticSearch安装和使用

Storm架构分析

Storm编程模型、Tuple源码、并发度分析

Storm WordCount案例及常用Api分析

7、Spark核心源码解析

Spark源码编译

Spark远程debug

Spark任务提交行流程源码分析

Spark通信流程源码分析

SparkContext创建过程源码分析

DriverActor和ClientActor通信过程源码分析

Worker启动Executor过程源码分析

Executor向DriverActor注册过程源码分析

Executor向Driver注册过程源码分析

DAGScheduler和TaskScheduler源码分析

Shuffle过程源码分析

Task执行过程源码分析

五、机器学习算法

1、python及numpy库

机器学习简介

机器学习与python

python语言–快速入门

python语言–数据类型详解

python语言–流程控制语句

python语言–函数使用

python语言–模块和包

phthon语言–面向对象

python机器学习算法库–numpy

机器学习必备数学知识–概率论

2、常用算法实现

knn分类算法–算法原理

knn分类算法–代码实现

knn分类算法–手写字识别案例

lineage回归分类算法–算法原理

lineage回归分类算法–算法实现及demo

朴素贝叶斯分类算法–算法原理

朴素贝叶斯分类算法–算法实现

朴素贝叶斯分类算法–垃圾邮件识别应用案例

kmeans聚类算法–算法原理

kmeans聚类算法–算法实现

kmeans聚类算法–地理位置聚类应用

决策树分类算法–算法原理

决策树分类算法–算法实现

时下的大数据分析时代与人工智能热潮，相信有许多对大数据分析师非常感兴趣、跃跃欲试想着转行的朋友，但面向整个社会，最不缺的其实就是人才，对于是否转行大数据分析行列，对于能否勇敢一次跳出自己的舒适圈，不少人还是踌躇满志啊!毕竟好多决定，一旦做出了就很难再回头了。不过如果你已经转行到大数据分析领域，就不要后悔，做到如何脱颖而出才是关键。因此本文给出一些建议，针对想要转行大数据分析行列且是零基础转行的小伙伴们，希望对你们有所裨益，也希望你们将来学有所成，不后悔，更不灰心!