k-NearestNeighbor

KNN 近邻算法的初次实现和做法

KNN 概述

k-近邻(kNN, k-NearestNeighbor)算法是一种基本分类与回归方法,我们这里只讨论分类问题中的 k-近邻算法。

一句话总结: 近朱者赤近墨者黑!

k 近邻算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。 k 值的选择、距离度量以及分类决策规则是 k 近邻算法的三个基本要素。

KNN 场景

电影可以按照题材分类,那么如何区分 动作片爱情片 呢?

  1. 动作片: 打斗次数更多
  2. 爱情片: 亲吻次数更多

基于电影中的亲吻、打斗出现的次数,使用 k-近邻算法构造程序,就可以自动划分电影的题材类型。

KNN 原理

KNN 工作原理
  1. 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序(从小到大,越小表示越相似)。
    3. 取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 通俗理解

给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k 个实例,这 k 个实例的多数属于某个类,就把该输入实例分为这个类。

KNN 算法的特点
1
2
3
优点: 精度高、对异常值不敏感、无数据输入假定
缺点: 计算复杂度高、空间复杂度高
适用数据范围: 数值型和标称型

KNN 算法初次实验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from numpy import *
import operator
from os import listdir
from collections import Counter

#导入必要模块

def createDataSet():
#创建数据集和标签
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group,labels

def classify0(inX,dataSet,labels,k):
#获取源数据矩阵的大小
dataSetSize = dataSet.shape[0]
print(dataSetSize)
print(tile(inX,(dataSetSize,1)))
#生成矩阵差的值
diffMat = tile(inX,(dataSetSize,1)) - dataSet
#取平方
sqDiffMat = diffMat ** 2
#对每一行都求和
sqDistances = sqDiffMat.sum(axis = 1)
#对求和进行根号
distances = sqDistances ** 0.5
#根据距离进行排序从小到大进行排序,并且返回排序后的index
sortedDisINdicies = distances.argsort()
classCount = {}
for i in range(k):
#获取该元素的标签是什么
voteIlabel = labels[sortedDisINdicies[i]]
#每出现一次,将这个标签+1
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 利用max函数直接返回字典中value最大的key
maxClassCount = max(classCount,key = classCount.get)
# 返回类型
return maxClassCount

def test1():
group,labels = createDataSet()
display(group)
display(labels)
print(classify0([0.1,0.1],group,labels,3))
test1()

image.png

部分文章出自https://github.com/apachecn/AiLearning/blob/master/docs/ml/2.md

作者

Codecat

发布于

2021-09-26

更新于

2021-09-26

许可协议

评论