机器学习小结之KNN算法

news/2024/10/30 2:50:22/

文章目录

  • 前言
  • 一、概念
    • 1.1 机器学习基本概念
    • 1.2 k 值
    • 1.3 距离度量
    • 1.4 加权方式
  • 二、实现
    • 2.1 手写实现
    • 2.2 调库 Scikit-learn
    • 2.3 测试自己的数据
  • 三、总结
    • 3.1 分析
    • 3.2 KNN 优缺点
  • 参考

前言

KNN (K-Nearest Neighbor)算法是一种最简单,也是一个很实用的机器学习的算法,在《机器学习实战》这本书中属于第一个介绍的算法。它属于基于实例的有监督学习算法,本身不需要进行训练,不会得到一个概括数据特征的模型,只需要选择合适的参数 K 就可以进行应用。KNN的目标是在训练数据中发现最佳的 K 个近邻,并根据这些近邻的标签来预测新数据的标签。每次使用 KNN 进行预测时,所有的训练数据都会参与计算。

kNN有很多应用场景:

  • 分类问题,同时天然可以处理多分类问题,比如根据音乐的特征,将其归类到不同的类型。
  • 推荐系统,根据用户的历史行为,推荐相似的物品或服务
  • 图像识别,比如人脸识别、车牌识别等

一、概念

1.1 机器学习基本概念

机器学习是人工智能领域中非常重要的一个分支,它可以帮助我们从大量数据中发现规律并做出预测。

机器学习可以分为监督学习、无监督学习和半监督学习三种类型。

  • 监督学习是指在训练数据中已经标注了正确答案,通过这些数据来训练模型,然后对新数据进行预测。
  • 无监督学习是指在训练数据中没有标注正确答案,通过对数据的聚类、降维等操作来发现数据中的规律。
  • 半监督学习则是介于有监督学习和无监督学习之间的一种方法。

下表是对机器学习一些基本概念解释

概念解释备注
分类将数据集分为不同的类别属于监督学习
聚类将数据集分为由类似的对象组成多个类的过程属于无监督学习
回归指预测连续型数值数据属于监督学习
样本集一般指用于训练模型的数据集,一般分为训练集和测试集。在样本集中,每个样本都包含一个或多个特征和一个标签。
特征用于描述样本的属性或特点通常是训练样本集的列,他们是独立测量的结果,多个特征联系在一起共同组成一个训练样本
标签样本所属的类别或结果
模型从训练数据中学习到的规律或模式。在机器学习中,模型可以用于预测新数据的标签或值
梯度指函数在某一点处的变化率。在机器学习中,梯度可以用于以最小化损失函数优化模型参数

1.2 k 值

k值是指在多个邻居中,选择前k个最相似邻居的类别来决定当前样本的类别,通常 k 是不大于20的整数,常选择3或5

1.3 距离度量

距离度量是指在 kNN 算法中用来计算样本之间距离的方法。常用的距离度量有欧氏距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离等。

  • 欧式距离

    • 二维平面

      d = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} d=(x1x2)2+(y1y2)2

    • n维

      d = ∑ i = 1 n ∣ x i − y i ∣ 2 d=\sqrt{\sum_{i=1}^{n}{\left| x_{i}-y_{i} \right|^{2}}} d=i=1nxiyi2

  • 曼哈顿距离

    d = ∑ i = 1 n ∣ x i − y i ∣ d= \sum_{i=1}^{n}|x_i - y_i| d=i=1nxiyi

  • 切比雪夫距离

    d = m a x ( ∣ x 1 − x 2 ∣ , ∣ y 1 − y 2 ∣ , ⋯ , ∣ x i − y i ∣ ) d= max(|x_1 - x_2|, |y_1 - y_2|, \cdots, |x_i - y_i|) d=max(x1x2,y1y2,,xiyi)

  • 闵可夫斯基距离

    d = ∑ i = 1 n ( ∣ x i − y i ∣ ) p p d = \sqrt[p]{\sum_{i=1}^{n}(|x_i - y_i|)^p} d=pi=1n(xiyi)p

1.4 加权方式

KNN 算法中的加权方式指的是在计算距离时,对不同距离的样本使用不同的权重。这些权重可以是距离样本数据源的距离,也可以是不同样本之间的距离。加权的方式可以根据实际情况进行选择,以达到更好的分类或预测效果。

常用的数值数据加权方式如下:

  1. 加权平均值:将K个邻居的属性值加权平均后作为新数据点的预测值。
  2. 均值法:将K个邻居的属性值取平均值后作为新数据点的预测值。
  3. 最差值:将K个邻居的属性值取最小值和最大值,再取平均值作为新数据点的预测值。

常见的离散型数据加权方式如下:

  1. 反函数
  2. 高斯函数
  3. 多项式函数

不同的加权方式可以根据实际情况选择,以达到更好的分类或预测效果。

二、实现

手写数字数据集 为 《机器学习实战》第二章 提供的数据集:https://github.com/pbharrin/machinelearninginaction

2.1 手写实现

import numpy as np
from collections import Counter
import operator
import math
from os import listdir# inX 输入向量
# dataSet 训练集
# labels 训练集所代表的标签
# k 最近邻居数目
# output: label
def classify0(inX, dataSet, labels, k):sortedDistIndicies=euclideanDistance(inX, dataSet)classCount = {}for i in range(k):voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel, 0) +  1.0 * weight(sortedDistIndicies[i])sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)return sortedClassCount[0][0]def euclideanDistance(inX, dataSet):dataSetSize = dataSet.shape[0]diffMat = np.tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat ** 2sqDistances = sqDiffMat.sum(axis = 1)distances = sqDistances ** 0.5sortedDistIndicies = distances.argsort()return sortedDistIndiciesdef weight(dist):return 1def classify1(test, train, trainLabel, k):distances = []for i in range(len(train)):distance = np.sqrt(np.sum(np.square(test - train[i, :])))distances.append([distance, i])distances = sorted(distances)targets = [trainLabel[distances[i][1]] for i in range(k)]return Counter(targets).most_common(1)[0][0]def img2vector(filename):returnVect = np.zeros((1,1024))fr = open(filename)for i in range(32):lineStr = fr.readline()for j in range(32):returnVect[0,32*i+j] = int(lineStr[j])return returnVectdef handWritingDataSet(inputDir):hwLabels = []fileNames = []dataFileList = listdir(inputDir)           m = len(dataFileList)dataMat = np.zeros((m,1024))for i in range(m):fileNameStr = dataFileList[i]fileStr = fileNameStr.split('.')[0]     classNumStr = int(fileStr.split('_')[0])hwLabels.append(classNumStr)fileNames.append(fileStr)dataMat[i,:] = img2vector( inputDir + '/%s' % fileNameStr)return dataMat,hwLabels,fileNamestrainMat, trainLabels, _ = handWritingDataSet('digits/trainingDigits/')
testMat, testLabels,testFileNames = handWritingDataSet('digits/testDigits/')errorCount = 0
k = 3
for idx, testData in enumerate(testMat):prefictLabel = classify0(testData, trainMat, trainLabels, k)# prefictLabel = classify1(testData, trainMat, trainLabels, k)if testLabels[idx] != prefictLabel:errorCount+=1print("错误数据:%s.txt, 预测数字:%d" % (testFileNames[idx], prefictLabel))
print("k值:%d, 错误数量:%d, 错误率:%.3f%%" %(k, errorCount, errorCount / 1.0 / np.size(testMat, 0) * 100))

knn_classfi

2.2 调库 Scikit-learn

文档地址:https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier

from sklearn.neighbors import KNeighborsClassifiertrainMat, trainLabels, _ = handWritingDataSet('digits/trainingDigits/')
testMat, testLabels,testFileNames = handWritingDataSet('digits/testDigits/')errorCount = 0
k = 3neigh = KNeighborsClassifier(n_neighbors=k)
neigh.fit(trainMat, trainLabels)for idx, testData in enumerate(testMat):prefictLabel = neigh.predict([testData])if testLabels[idx] != prefictLabel:errorCount+=1print("错误数据:%s.txt, 预测数字:%d" % (testFileNames[idx], prefictLabel))
print("k值:%d, 错误数量:%d, 错误率:%.3f%%" %(k, errorCount, errorCount / 1.0 / np.size(testMat, 0) * 100))

knn_scikit-learn

2.3 测试自己的数据

上面的手写数据集,训练集有1934个,测试集有946个,都是32x32的图片转的文本。如果想测试自己的手写数字,那就需要将手写数字图片先转成32x32像素格式的图片,然后再转成文本,下面是一个图片转文本代码

import cv2
import osdef img2txt(inputDir):dataFileList = os.listdir(inputDir)for file in dataFileList:if not file.endswith('png'):continueimg = cv2.imread(inputDir + file, cv2.IMREAD_GRAYSCALE)fr = open(inputDir + file.split('.')[0] + '.txt', 'w')height, width = img.shape[0:2]for row in range(height):line = ''for col in range(width):if img[row, col] > 250:line+='0'else:line+='1'fr.write(line)fr.write('\n')fr.close()
if __name__ == '__main__':img2txt('img/')

下面准备自己手写的0-9 十个数字进行测试,下面数字是用windows画图工具,先裁剪为32x32像素,再用鼠标手写实现。

self-digits

将10个数字转成文本进行测试,结果错误率在30%

self_knn

三、总结

3.1 分析

  • 识别测试集手写数字时,总是有一些样本不能正确识别,通过观察发现是因为与其他类别特征比较接近
  • 使用自身手写数字识别,识别错误的样本并不是因为相类似,例如4被识别为7,这个不太明白,可能与样本特征有关

3.2 KNN 优缺点

  • 优点
    1. 思想简单,理论成熟,既可以用来做分类也可以用来做回归
    2. 由于选择距离最近的 k 个,对异常值不敏感
  • 缺点
    1. KNN 需要计算每个测试样本与所有训练样本之间的距离,时间复杂度很高,计算成本也很高
    2. 无法给出数据任何的基础结构信息
    3. 算法比较简单,当训练数据较小时,对于一些很相似的不同类数据很难区分

参考

  1. https://github.com/pbharrin/machinelearninginaction

http://www.ppmy.cn/news/58664.html

相关文章

【C++】特殊类设计+单例模式+类型转换

目录 一、设计一个类,不能被拷贝 1、C98 2、C11 二、设计一个类,只能在堆上创建对象 1、将构造设为私有 2、将析构设为私有 三、设计一个类,只能在栈上创建对象 四、设计一个类,不能被继承 1、C98 2、C11 五、设计一个…

Redis-集合(Set)

Redis集合(Set) Redis set对外提供的功能与list类似是一个列表的功能,特殊之处在于set是可自动排重的,当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在一个set…

2023年第二届材料科学与工程国际会议(CoMSE 2023) | IOP-JPCS出版

会议简介 Brief Introduction 2023年第二届材料科学与工程国际会议(CoMSE 2023) 会议时间:2023年7月21日-23日 召开地点:中国泰州 大会官网:www.icomse.org CoMSE 2023由四川大学、华南理工大学亚热带建筑科学国家重点实验室、国际电气电子和…

JavaScript:栈和对列

文章目录 栈和对列Js 有栈与队列吗20. 有效的括号 - 力扣(LeetCode)思路 1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)思路代码分析array.join() 操作打印const s of str 操作遍历 150. 逆波兰表达式求值 - 力扣&#xf…

Linux操作系统CentOS7安装Nginx[详细版]

Linux操作系统CentOS7安装Nginx[详细版] Nginx安装 1. 官网下载 Nginx 2. 使用 XShell 和 Xftp 将压缩包上传到 Linux 虚拟机中 3. 解压文件 nginx-1.20.2.tar.gz 4. 配置nginx 5. 启动 nginx 6. 拓展(修改端口和常用命令) (一)修…

第二十一章 光源

光源是每个场景必不可少的部分,光源除了能够照亮场景之外,还可以产生阴影效果。 Unity中分为四种光源类型: 1. 方向光:Directional Light 用于模拟太阳光,方向光任何地方都能照射到。 2. 点光源:Point L…

Oracle中按天、周、月、季、年统计数据

简介: oracle实现按照天、周、月、季、年进行数据统计,在实际业务场景中如 "报表之类" 、"财务业务的往来" 等等,业务往往需要我们统计整年 或 整月的数据等,下面我们直入主题。 说明: 原始数据 一、按天查询 1、片段 …

BeautifulSoup4学习笔记

.string–获取文本内容 html <html><head><title>The Dormouses story</title></head><body><p class"title" name"dromouse"><b>The Dormouses story</span></b></p>><p cla…