机器学习小结之KNN算法

这篇具有很好参考价值的文章主要介绍了机器学习小结之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)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis = 1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    return sortedDistIndicies

def weight(dist):
    return 1


def 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 returnVect

def 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,fileNames

trainMat, 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+=1
        print("错误数据:%s.txt, 预测数字:%d" % (testFileNames[idx], prefictLabel))
print("k值:%d, 错误数量:%d, 错误率:%.3f%%" %(k, errorCount, errorCount / 1.0 / np.size(testMat, 0) * 100))

机器学习小结之KNN算法

2.2 调库 Scikit-learn

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

from sklearn.neighbors import KNeighborsClassifier

trainMat, trainLabels, _ = handWritingDataSet('digits/trainingDigits/')
testMat, testLabels,testFileNames = handWritingDataSet('digits/testDigits/')

errorCount = 0
k = 3

neigh = KNeighborsClassifier(n_neighbors=k)
neigh.fit(trainMat, trainLabels)

for idx, testData in enumerate(testMat):
    prefictLabel = neigh.predict([testData])
    if testLabels[idx] != prefictLabel:
        errorCount+=1
        print("错误数据:%s.txt, 预测数字:%d" % (testFileNames[idx], prefictLabel))
print("k值:%d, 错误数量:%d, 错误率:%.3f%%" %(k, errorCount, errorCount / 1.0 / np.size(testMat, 0) * 100))

机器学习小结之KNN算法

2.3 测试自己的数据

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

import cv2
import os

def img2txt(inputDir):
    dataFileList = os.listdir(inputDir)

    for file in dataFileList:
        if not file.endswith('png'):
            continue
        img = 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像素,再用鼠标手写实现。

机器学习小结之KNN算法

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

机器学习小结之KNN算法文章来源地址https://www.toymoban.com/news/detail-457234.html

三、总结

3.1 分析

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

3.2 KNN 优缺点

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

参考

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

到了这里,关于机器学习小结之KNN算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 李飞飞计算机视觉k-Nearest Neighbor

    给计算机很多数据,然后实现学习算法,让计算机学习到每个类的外形 输入:输入是包含N个图像的集合,每个图像的标签是K种分类标签中的一种。这个集合称为训练集。 学习:这一步的任务是使用训练集来学习每个类到底长什么样。一般该步骤叫做训练分类器或者学习一个

    2024年02月17日
    浏览(38)
  • 机器学习小结之KNN算法

    ​ KNN (K-Nearest Neighbor)算法是一种最简单,也是一个很实用的机器学习的算法,在《 机器学习实战 》这本书中属于第一个介绍的算法。它属于基于实例的 有监督学习 算法,本身不需要进行训练,不会得到一个概括数据特征的 模型 ,只需要选择合适的参数 K 就可以进行应用。

    2024年02月06日
    浏览(77)
  • 【k近邻】 K-Nearest Neighbors算法汇总

    目录 k近邻算法思想 k近邻算法原理 k近邻算法流程 距离度量的选择 数据维度归一化 k值的选择 k近邻算法优缺点 少数服从多数 K近邻算法,即是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例 最邻近 的K个实例, 这K个实例的多数属于某个类 ,就把该输

    2024年02月22日
    浏览(40)
  • 算法笔记 近似最近邻查找(Approximate Nearest Neighbor Search,ANN)

    精准最近邻搜索中数据维度一般较低,所以会采用穷举搜索,即在数据库中依次计算其中样本与所查询数据之间的距离,抽取出所计算出来的距离最小的样本即为所要查找的最近邻。 当数据量非常大的时候,搜索效率急剧下降。 ——近似最近邻查找(Approximate Nearest Neighbor

    2024年02月09日
    浏览(40)
  • 机器学习——KNN算法实例

    目录 1.项目背景 2.流程步骤  3.代码部分 3.1导入可能需要用的包  3.2准备数据:从文本文件中解析数据  3.3分析数据:用Matplotlib创建散点图  3.4准备数据:数据归一化 3.5 测试算法:作为完整程序验证分类器  【关于K值的选择】 3.6使用算法:构建完整可用系统 4.总结    关

    2024年02月11日
    浏览(59)
  • 机器学习——KNN算法

    机器学习笔记 KNN的算法原理,可以简单如下描述: 一个数据集中存在多个已有标签的样本值,这些样本值共有的n个特征构成了一个多维空间N。当有一个需要预测/分类的样本x出现,我们把这个x放到多维空间n中,找到离其距离最近的k个样本,并将这些样本称为最近邻(nea

    2024年02月06日
    浏览(44)
  • 【机器学习】KNN 算法介绍

    KNN 算法,或者称 k-最近邻算法,是 有监督学习 中的 分类算法 。它可以用于分类或回归问题,但它通常用作分类算法。 KNN 的全称是 K Nearest Neighbors,意思是 K 个最近的邻居。该算法用 K 个最近邻来干什么呢?其实,KNN 的原理就是:当预测一个新样本的类别时, 根据它距离

    2023年04月24日
    浏览(84)
  • 【机器学习笔记】7 KNN算法

    欧几里得度量(Euclidean Metric)(也称欧氏距离)是一个通常采用的距离定义,指在𝑚维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。 想象你在城市道路里,要从一个十字路口开车到

    2024年02月21日
    浏览(39)
  • 【机器学习实战】K- 近邻算法(KNN算法)

    K-近邻算法 ,又称为  KNN 算法 ,是数据挖掘技术中原理最简单的算法。 KNN  的工作原理:给定一个已知类别标签的数据训练集,输入没有标签的新数据后,在训练数据集中找到与新数据最临近的 K 个实例。如果这 K 个实例的多数属于某个类别,那么新数据就属于这个类别。

    2023年04月20日
    浏览(57)
  • 机器学习KNN最邻近分类算法

    KNN (K-Nearest Neighbor) 最邻近分类算法,其核心思想“近朱者赤,近墨者黑”,由你的邻居来推断你的类别。 图中绿色圆归为哪一类? 1、如果k=3,绿色圆归为红色三角形 2、如果k=5,绿色圆归为蓝色正方形 参考文章 knn算法实现原理:为判断未知样本数据的类别,以所有已知样

    2024年04月10日
    浏览(68)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包