首页 > 代码库 > K-邻近(KNN)算法
K-邻近(KNN)算法
K近邻分类算法概述
K-近邻算法是机器学习之中最简单的分类算法之一，它采用测量不同特征值之间的距离方法进行分类。它的工作原理是：存在一个样本数量集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似或最近邻的分类标签。一般类说，我们只选择样本数据集中前K个最相似的数据，这就是K-近邻算法中K的出处，通常K是不大于20的整数，最后，选择前K个最相似数据中出现次数最多的分类，作为新数据的分类。
K近邻算法步骤
- 计算已知类别数据集中的电与当前点之间的距离
- 按照距离递增次数排列
- 选取与当前点距离最小的K个点
- 确定前K个点所在类别的出现频率
- 返回前K个点出现频率最高的类别作为当前点的预测分类
在计算点和点之间的距离时，我们使用欧几里得距离：
代码1-1实现K-近邻算法
# coding:utf-8
from numpy import *
import operator
# 生成数据集
def createDataSet():
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
lables = [‘A‘, ‘A‘, ‘B‘, ‘B‘]
return group, lables
def classify0(inX, dataSet, lables, k):
# 计算距离
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
sortedDistIndicies = distances.argsort()
classCount = {}
# 选取前K个距离最小的点
for i in range(k):
voteIlable = lables[sortedDistIndicies[i]]
classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
使用K-近邻算法改进社交网站的推荐效果
艾米在社交网站一直和来自天南地北的的人聊天，但并不是所有人她都喜欢与之交往，经过一番总结，她发现曾交往过三类人：
- 不善言谈的人
- 幽默感一般的人
- 极具幽默的人
艾米将他交往过的人形成数据并存储在datingTestSet2.txt文件中，每个样本数据占据一行，总共有1000行，每一行包含以下3种特征：
- 每年飞行程数
- 玩游戏时间所耗百分比
- 每周消费冰淇淋公升数
|
玩游戏时间所耗百分比 |
每年飞行程数 |
每周消费冰淇淋公升数 |
样本分类 | |
| 1 | 8.326976 | 40920 | 0.953952 | 3 |
| 2 | 7.153469 | 14488 | 1.673904 | 2 |
| 3 | 1.441871 | 26052 | 0.805124 | 1 |
数据集地址：http://pan.baidu.com/s/1hsvbxXE
归一化数值
表1-2给出了三组数据，如果想计算样本1和样本2之间的距离，用欧几里得公式[(8.326976-7.153469)2+(40920-14488)2+(0.953952-1.673904)2]1/2 ，可以很容易发现，方程中数字差值最大的属性对计算结果的影响最大，也就是说每年飞行程数对结果的影响远大于其他两个特征——玩游戏时间所耗百分比和每周消费冰淇淋公升数，然而，如果三个特征同等重要，每年飞行程数不应该严重影响到计算结果，在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围处理为0到1或-1到1之间，下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：
newVaule = (oldValue-min)/(max-min)
其中min和max分别是数据集中最小特征值和最大特征值。
代码1-3
# 读取文件
def fileMatrix(fileName):
fr = open(fileName)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines)
mat = zeros((numberOfLines, 3))
classLableVector = []
index = 0
for line in arrayOLines:
line = line.strip()
listFromLine = line.split("\t")
mat[index, :] = listFromLine[0:3]
classLableVector.append(int(listFromLine[-1]))
index += 1
return mat, classLableVector
# 归一化特征值
def autoNorm(dataSet):
# 从每一列选取最小值
minVals = dataSet.min(0)
# 从每一列选取最大值
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(dataSet.shape)
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m, 1))
normDataSet = normDataSet / tile(ranges, (m, 1))
return normDataSet, ranges, minVals
# 分类器测试数据集
def datingClassTest(fileName):
hoRatio = 0.10
datingDataMat, datingLabels = fileMatrix(fileName)
mat, ranges, minVals = autoNorm(datingDataMat)
m = mat.shape[0]
numTestVecs = int(m * hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(mat[i, :], mat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if classifierResult != datingLabels[i]: errorCount += 1.0
print "the total error rate is: %f" % (errorCount / float(numTestVecs))
代码1-3中，函数datingClassTest首先使用了fileMatrix和autoNorm函数从文件中读取数据，并将其转化为归一化特征值，接着划分mat数据中，哪些数据用于测试，哪些数据用于分类器的训练样本，然后将这两部分数据沮洳到分类器classify0中。最后函数计算错误率并输出结果，用上面的数据集测试，可以得到错误率是5%，这是一个还不错的结果，这个例子可以表明，我们可以正确的预测分类，而错误率仅5%，通过输入未知对象的属性信息，由分类算法可以帮助我们预测输入的对象是不善言谈的人、还是幽默感一般或极具幽默感的人
代码1-4为本章代码整合
# coding:utf-8
from numpy import *
import operator
# 生成数据集
def createDataSet():
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
lables = [‘A‘, ‘A‘, ‘B‘, ‘B‘]
return group, lables
def classify0(inX, dataSet, lables, k):
# 计算距离
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
sortedDistIndicies = distances.argsort()
classCount = {}
# 选取前K个距离最小的点
for i in range(k):
voteIlable = lables[sortedDistIndicies[i]]
classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
# 读取文件
def fileMatrix(fileName):
fr = open(fileName)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines)
mat = zeros((numberOfLines, 3))
classLableVector = []
index = 0
for line in arrayOLines:
line = line.strip()
listFromLine = line.split("\t")
mat[index, :] = listFromLine[0:3]
classLableVector.append(int(listFromLine[-1]))
index += 1
return mat, classLableVector
# 归一化特征值
def autoNorm(dataSet):
# 从每一列选取最小值
minVals = dataSet.min(0)
# 从每一列选取最大值
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(dataSet.shape)
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m, 1))
normDataSet = normDataSet / tile(ranges, (m, 1))
return normDataSet, ranges, minVals
# 分类器测试数据集
def datingClassTest(fileName):
hoRatio = 0.10
datingDataMat, datingLabels = fileMatrix(fileName)
mat, ranges, minVals = autoNorm(datingDataMat)
m = mat.shape[0]
numTestVecs = int(m * hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(mat[i, :], mat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
if classifierResult != datingLabels[i]: errorCount += 1.0
print "the total error rate is: %f" % (errorCount / float(numTestVecs))
K-邻近(KNN)算法