【算法】K最近邻算法(K-NEAREST NEIGHBOURS,KNN)

K最近邻算法(k-nearest neighbours,KNN)

算法

  1. 对一个元素进行分类
  2. 查看它k个最近的邻居
  3. 在这些邻居中,哪个种类多,这个元素有更大概率是这个种类

使用

使用KNN来做两项基本工作——分类和回归:

  • 分类就是编组;
  • 回归就是预测结果(如一个数字)。

特征抽取

用于确定两个元素相似程度

方法

使用毕达哥拉斯公式

  1. 将可对比的类别转换为一组坐标
  2. 使用毕达哥拉斯公式

回归(regression)

回归可以预测结果

方法

  1. 对一元素分类(找寻影响因素)
  2. 查看其k个邻居
  3. 根据邻居的表现,计算平均值即可

挑选合适的特征

原则

  • 与要分析的元素紧密相关的特征;
  • 不偏不倚的特征(例如,如果只让用户给喜剧片打分,就无法判断他们是否喜欢动作片)

在挑选合适的特征方面,必须考虑到各种需要考虑的因素。

机器学习简介

机器学习旨在让计算机更聪明

OCR

光学字符识别(optical character recognition)

指的是拍摄印刷页面的照片,计算机将自动识别出其中的文字。

原理

使用KNN

(1) 浏览大量的数字图像,将这些数字的特征提取出来。

(2) 遇到新图像时,提取该图像的特征,再找出它最近的邻居都是谁!

一般而言, OCR算法提取线段、点和曲线等特征。

OCR的第一步是查看大量的数字图像并提取特征,这被称为训练(training)

朴素贝叶斯分类器(Naive Bayes classifier)

首先需要使用一些数据对这个分类器进行训练。

朴素贝叶斯分类器能计算出一些事件概率,其应用领域与KNN相似

小结

  • KNN用于分类和回归,需要考虑最近的邻居。
  • 分类就是编组。
  • 回归就是预测结果(如数字)。
  • 特征抽取意味着将物品(如水果或用户)转换为一系列可比较的数字。
  • 能否挑选合适的特征事关KNN算法的成败。
上一篇:《算法图解》——第十章 K最近邻算法


下一篇:6 - Python内置结构 - 字典