使用python演示knn算法

ASR/CV/ML 使用python演示knn算法

k近邻法(k-nearest neighbor, k-NN)。原理：
1.准备一个样本数据集合(训练样本集)，其中每个数据都对应1个标签。
2.要进行测试的新数据(没有标签)，与样本集合里的数据进行比较。
3.提取最相似的数据的标签，即结果。
一般第3步取前k个最相似的数据，即k-NN算法中k的出处。有文档说k通常不大于20。
取k个最值数据后，对这k个数据的标签再进行计数，取数量最多的标签。

import numpy as np
import operator

# 电影有2类：枪战片、文艺片。
# 要区分哪类电影，用2个特征表示：爆炸镜头数量、吃饭镜头数量。称为一个样本。
# 用一个序列保存样本，如某个枪战片[100, 1]，有100个爆炸镜头，只有1个吃饭的镜头。
# 这里准备4部电影的数据：
simpleDataArray = np.array([[0, 50], [3, 89], [118, 1], [66, 4]])
# 同时准备这4部电影对应的标签
simpleLabelArray = ['文艺片', '文艺片', '枪战片', '枪战片']
# 这是要用knn算法分析属于哪类影片的数据
testData = [39, 1]
# top n
k = 3

print("样本", simpleDataArray)
cols = simpleDataArray.shape[0]  # 返回simpleDataArray的数据量
print("样本量", cols)
tild = np.tile(testData, (cols, 1)) # 将原矩阵横向、纵向地复制。testData-目标矩阵，1-仅复制1行，cols-在1行里复制cols列。
print("测试集", tild)
diff = tild - simpleDataArray  # numpy数组可直接进行对应元素的减法
print("测试减去样本的差", diff)
sqDiff = diff**2  # 二维特征相减后平方
print("差集的平方", sqDiff)
sqDistances = sqDiff.sum(axis=1)  # 将第2维度元素相加
print("2级集合元素求和", sqDistances)
distances = sqDistances**0.5  # 开方，计算出测试集和样本集元素的距离。距离越小的越符合样本的标签
print("开方-距离", distances)
sortedDistIndices = distances.argsort()  # 返回索引序列，索引对应的元素是从小到大的
print("降序索引", sortedDistIndices)
classCount = {}  # 记录类别次数的字典
for i in range(k):
    sdi = sortedDistIndices[i]
    print("===", sdi)
    voteIlabel = simpleLabelArray[sdi]  # 取出前k个元素的类别
    print("标签", voteIlabel)
    classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1  # 计算类别次数
    print("计数", classCount)

# key=operator.itemgetter(1)根据字典的值进行排序
# key=operator.itemgetter(0)根据字典的键进行排序
# reverse降序排序字典
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
print("---", classCount)
# 返回次数最多的类别,即所要分类的类别
print("样本所属", sortedClassCount[0][0]) # 枪战片

import numpy as np

import operator

# 电影有2类：枪战片、文艺片。

# 要区分哪类电影，用2个特征表示：爆炸镜头数量、吃饭镜头数量。称为一个样本。

# 用一个序列保存样本，如某个枪战片[100, 1]，有100个爆炸镜头，只有1个吃饭的镜头。

# 这里准备4部电影的数据：

simpleDataArray = np.array([[0, 50], [3, 89], [118, 1], [66, 4]])

# 同时准备这4部电影对应的标签

simpleLabelArray = ['文艺片', '文艺片', '枪战片', '枪战片']

# 这是要用knn算法分析属于哪类影片的数据

testData = [39, 1]

# top n

k = 3

print("样本", simpleDataArray)

cols = simpleDataArray.shape[0] # 返回simpleDataArray的数据量

print("样本量", cols)

tild = np.tile(testData, (cols, 1)) # 将原矩阵横向、纵向地复制。testData-目标矩阵，1-仅复制1行，cols-在1行里复制cols列。

print("测试集", tild)

diff = tild - simpleDataArray # numpy数组可直接进行对应元素的减法

print("测试减去样本的差", diff)

sqDiff = diff**2 # 二维特征相减后平方

print("差集的平方", sqDiff)

sqDistances = sqDiff.sum(axis=1) # 将第2维度元素相加

print("2级集合元素求和", sqDistances)

distances = sqDistances**0.5 # 开方，计算出测试集和样本集元素的距离。距离越小的越符合样本的标签

print("开方-距离", distances)

sortedDistIndices = distances.argsort() # 返回索引序列，索引对应的元素是从小到大的

print("降序索引", sortedDistIndices)

classCount = {} # 记录类别次数的字典

for i in range(k):

sdi = sortedDistIndices[i]

print("===", sdi)

voteIlabel = simpleLabelArray[sdi] # 取出前k个元素的类别

print("标签", voteIlabel)

classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # 计算类别次数

print("计数", classCount)

# key=operator.itemgetter(1)根据字典的值进行排序

# key=operator.itemgetter(0)根据字典的键进行排序

# reverse降序排序字典

sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)

print("---", classCount)

# 返回次数最多的类别,即所要分类的类别

print("样本所属", sortedClassCount[0][0]) # 枪战片

除了距离公式(欧几里得距离)：

distance = √(a1-a2)^2 + (b1-b2)^2 + (c1-c2)^2 + (n..1-n..2)^2

ML中还常用到归一化公式：

normValue = (oldValue - minValue) / (maxValue - minValue)

示例代码：

def autoNorm(featureMat):
    # featureMat是numpy矩阵，每行有3列：
    # [ [4.0920000e+04 8.3269760e+00 9.5395200e-01] 行0
    #   [1.4488000e+04 7.1534690e+00 1.6739040e+00] 行1
    #   [2.6052000e+04 1.4418710e+00 8.0512400e-01] 行2
    #   ...
    #   [2.6575000e+04 1.0650102e+01 8.6662700e-01]   行n-2
    #   [4.8111000e+04 9.1345280e+00 7.2804500e-01]   行n-1
    #   [4.3757000e+04 7.8826010e+00 1.3324460e+00] ] 行n
    # 通常值最大的数据对计算结果影响最大，如上面 第1列远大于其它两列。
    # 如果希望3个列的值是同等重要的，特别大或特别小的值不会严重地影响计算结果，
    # 就需要归一化处理，即把值压缩到0-1之间。
    # 
    minList = featureMat.min(0)    # 获得每列数据的最小值，组成序列 [a b c]
    maxList = featureMat.max(0)    # 每列最大特征值序列 [o p q]
    diffList = maxList - minList   # 每个特征值(最大值和最小值的范围)长度/距离 [o-a, p-b, q-c]
    rowCount = featureMat.shape[0] # 返回原矩阵行数 (n+1)
    minTmpMat = np.tile(minList, (rowCount, 1))    # 创建同样大小的临时矩阵，每行都是最小值序列 [[a b c], [a b c],..., [a b c], [a b c]]
    trimMinMat = featureMat - minTmpMat            # 原矩阵每个元素都减去最小特征值 [[4.09x-a  8.x2x-b  9.53x-c], [1.44x-a  7.15x-b  1.67x-c],..., [4.37x-a  7.88x-b  1.33x-c]]
    distanceMat = np.tile(diffList, (rowCount, 1)) # 创建同样大小的临时矩阵，每行都是特征值长度的序列[[o-a, p-b, q-c], [o-a, p-b, q-c], ..., [o-a, p-b, q-c], [o-a, p-b, q-c]]
    normMat = trimMinMat / distanceMat             # 归一化数据。normValue = (oldValue - minValue) / (maxValue - minValue)，对应位置的元素进行除法运算
    return normMat 
    # [ [0.44832535 0.39805139 0.56233353]
    #   [0.15873259 0.34195467 0.98724416]
    #   [0.28542943 0.06892523 0.47449629]
    #   ...
    #   [0.29115949 0.50910294 0.51079493]
    #   [0.52711097 0.43665451 0.4290048 ]
    #   [0.47940793 0.3768091  0.78571804] ]

def autoNorm(featureMat):

# featureMat是numpy矩阵，每行有3列：

# [ [4.0920000e+04 8.3269760e+00 9.5395200e-01] 行0

# [1.4488000e+04 7.1534690e+00 1.6739040e+00] 行1

# [2.6052000e+04 1.4418710e+00 8.0512400e-01] 行2

# ...

# [2.6575000e+04 1.0650102e+01 8.6662700e-01] 行n-2

# [4.8111000e+04 9.1345280e+00 7.2804500e-01] 行n-1

# [4.3757000e+04 7.8826010e+00 1.3324460e+00] ] 行n

# 通常值最大的数据对计算结果影响最大，如上面第1列远大于其它两列。

# 如果希望3个列的值是同等重要的，特别大或特别小的值不会严重地影响计算结果，

# 就需要归一化处理，即把值压缩到0-1之间。

minList = featureMat.min(0) # 获得每列数据的最小值，组成序列 [a b c]

maxList = featureMat.max(0) # 每列最大特征值序列 [o p q]

diffList = maxList - minList # 每个特征值(最大值和最小值的范围)长度/距离 [o-a, p-b, q-c]

rowCount = featureMat.shape[0] # 返回原矩阵行数 (n+1)

minTmpMat = np.tile(minList, (rowCount, 1)) # 创建同样大小的临时矩阵，每行都是最小值序列 [[a b c], [a b c],..., [a b c], [a b c]]

trimMinMat = featureMat - minTmpMat # 原矩阵每个元素都减去最小特征值 [[4.09x-a 8.x2x-b 9.53x-c], [1.44x-a 7.15x-b 1.67x-c],..., [4.37x-a 7.88x-b 1.33x-c]]

distanceMat = np.tile(diffList, (rowCount, 1)) # 创建同样大小的临时矩阵，每行都是特征值长度的序列[[o-a, p-b, q-c], [o-a, p-b, q-c], ..., [o-a, p-b, q-c], [o-a, p-b, q-c]]

normMat = trimMinMat / distanceMat # 归一化数据。normValue = (oldValue - minValue) / (maxValue - minValue)，对应位置的元素进行除法运算

return normMat

# [ [0.44832535 0.39805139 0.56233353]

# [0.15873259 0.34195467 0.98724416]

# [0.28542943 0.06892523 0.47449629]

# ...

# [0.29115949 0.50910294 0.51079493]

# [0.52711097 0.43665451 0.4290048 ]

# [0.47940793 0.3768091 0.78571804] ]

- end

声明

本文由 cuiweiyou 原创，转载请注明出处：http://www.gaohaiyan.com/3343.html

承接App定制、企业web站点、办公系统软件设计开发，外包项目，毕设

使用python knn交友预测示例
使用python演示朴素贝叶斯分类相关概念
使用python knn数字识别示例
使用python演示决策树中的几个概念