原生python实现knn分类算法
一、题目分析
K最近邻（k-Nearest Neighbor，KNN）分类算法是最简单的机器学习算法。 KNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别。本质上，KNN算法就是用距离来衡量样本之间的相似度。
二、算法设计
2.1、计算步骤
1）算距离：给定测试对象，计算它与训练集中的每个对象的距离
2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻
3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类
2.2、相似度的衡量
距离越近应该意味着这两个点属于一个分类的可能性越大。
但，距离不能代表一切，有些数据的相似度衡量并不适合用距离
相似度衡量方法：欧式距离
2.3、类别的判定
简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。
加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）
三、源代码
import numpy as np
import operator
1.处理训练数据集
filename:
训练数据文件
return:
returnMat - 处理得到的每一个训练样本的数据集合
returnLabel - 每一个训练样本所属的类别标签集合
def trainingFile2Matrix(filename):
"""
函数说明：
处理训练数据集
:param filename:
训练数据文件
:return:
returnMat - 处理得到的每一个训练样本的数据集合
returnLabel - 每一个训练样本所属的类别标签集合
"""
file = open(filename)
content = file.readlines()
lineCount = len(content)
returnMat = np.zeros((lineCount, 4))
returnLabel = []
index = 0
for line in content:
line = line.strip()
example = line.split(',')
returnMat[index, : ] = example[0 : 4]
index += 1
returnLabel.append(example[4])
return returnMat, returnLabel
2.处理测试数据集
filename:
测试数据文件
return:
returnMat - 处理得到的每一个测试样本的数据集合
def testFile2Matrix(filename):
"""
函数说明：
处理测试数据集
:param filename:
测试数据文件
:return:
returnMat - 处理得到的每一个测试样本的数据集合
"""
file = open(filename)
content = file.readlines()
lineCount = len(content)
returnMat = np.zeros((lineCount, 4))
index = 0
for line in content:
line = line.strip()
example = line.split(',')
returnMat[index, : ] = example[0 : 4]
index += 1
return returnMat
- 计算训练样本和测试样本之间的欧几里德距离
train_example:
训练样本的数据
test_example:
测试样本的数据
example_length:
样本的属性长度
return:
distance - 训练样本和测试样本之间的欧几里德距离
def calculateDistance(train_example, test_example, example_length):
"""
函数说明：
计算训练样本和测试样本之间的欧几里德距离
:param train_example:
训练样本的数据
:param test_example:
测试样本的数据
:param example_length:
样本的属性长度
:return:
distance - 训练样本和测试样本之间的欧几里德距离
"""
distance = 0.0
for i in range(example_length):
distance += pow(train_example[i] - test_example[i], 2)#欧几里得距离
return distance
4取得与测试样本距离最近的k个训练样本
trainingSet:
训练样本数据集
trainingLabel:
训练样本标签集
test_example:
测试样本
k:
即参数k
return:
kNeighbors - 与测试样本最近的k个训练样本的集合
def get_K_Neighbors(trainingSet, trainingLabel, test_example, k):
"""
函数说明：
取得与测试样本距离最近的k个训练样本
:param trainingSet:
训练样本数据集
:param trainingLabel:
训练样本标签集
:param test_example:
测试样本
:param k:
即参数k
:return:
kNeighbors - 与测试样本最近的k个训练样本的集合
"""
length = len(test_example)
distances = []
for i in range(len(trainingSet)):
dis = calculateDistance(trainingSet[i], test_example, length)
distances.append((trainingLabel[i], dis))
distances.sort(key=operator.itemgetter(1))
kNeighbors = []
for i in range(k):
kNeighbors.append(distances[i][0])
return kNeighbors
- 取得与测试样本距离最近的k个训练样本中的最公共类别
kNeighbors:
与测试样本最近的k个训练样本的集合
return:
sortedLabel[0][0] - 预测该测试样本所属的类别
def getReasult(kNeighbors):
"""
函数说明：
取得与测试样本距离最近的k个训练样本中的最公共类别
:param kNeighbors:
与测试样本最近的k个训练样本的集合
:return:
sortedLabel[0][0] - 预测该测试样本所属的类别
"""
classLabel = {}
for i in range(len(kNeighbors)):
temp = kNeighbors[i]
if temp in classLabel:
classLabel[temp] += 1
else:
classLabel[temp] = 1
sortedLabel = sorted(classLabel.items(), key=operator.itemgetter(1), reverse=True)
return sortedLabel[0][0]
- 计算预测的准确率
testLabel:
测试数据所属的真实类别
predictions:
预测测试数据所属的类别
return:
(cnt / float(len(testLabel))) * 100.0 - 准确率
def getAccuracy(testLabel, predictions):
"""
函数说明：
计算预测的准确率
:param testLabel:
测试数据所属的真实类别
:param predictions:
预测测试数据所属的类别
:return:
(cnt / float(len(testLabel))) * 100.0 - 准确率
"""
cnt = 0
for i in range(len(testLabel)):
if(testLabel[i] == predictions[i]):
cnt += 1
return (cnt / float(len(testLabel))) * 100.0
7.对数据进行归一化
dataSet:
数据集合
return:
normDataSet - 归一化后的数据集合
def getNormolization(dataSet):
"""
函数说明：
对数据进行归一化
:param dataSet:
数据集合
:return:
normDataSet - 归一化后的数据集合
"""
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m,1))
normDataSet = normDataSet / np.tile(ranges, (m,1))
return normDataSet
- 将测试结果写入文件
filename:
要写入的文件
resultSet:
测试结果集合
def write2File(filename, resultSet):
"""
函数说明：
将测试结果写入文件
:param filename:
要写入的文件
:param resultSet:
测试结果集合
"""
with open(filename, "r", encoding="utf-8") as f_read:
content = f_read.readlines()
#print(content)
index = 0
length = len(resultSet)
with open(filename, "w", encoding="utf-8") as f_write:
for i in range(length):
str = ''
temp = content[i].strip('\n')
str = temp + ',' + resultSet[i] + '\n'
index += 1
f_write.write(str)
9.综合调用前面的功能函数，实现KNN算法的所有步骤
def classify():
"""
函数说明：
综合调用前面的功能函数，实现KNN算法的所有步骤
"""
#自定义测试
trainingMat, trainingLabel = trainingFile2Matrix("train.txt")
testMat = testFile2Matrix("test.txt")
norm_trainingMat = getNormolization(trainingMat)
norm_testMat = getNormolization(testMat)
#print(norm_trainingMat)
#print()
#print(norm_testMat)
result = []
for i in range(len(testMat)):
kNeighbors = get_K_Neighbors(norm_trainingMat, trainingLabel, norm_testMat[i], 3)
#print(kNeighbors)
#print()
result.append(getReasult(kNeighbors))
print("knn分类结果为：")
print(result)
print("长度为：")
print(len(result))
print("预测准确率：" + str(getAccuracy(result,result)))
#print()
write2File("test.txt", result)
if __name__ == "__main__":
classify()
四、测试及调试
1.测试代码：
trainingMat,trainingLabel=trainingFile2Matrix(“train.txt”)
testMat = testFile2Matrix(“test.txt”)
norm_trainingMat = getNormolization(trainingMat)
norm_testMat = getNormolization(testMat)
print(norm_trainingMat)
print()
print(norm_testMat)
2.测试调试截屏
五、总结
KNN的缺点
1：效率低下，每个数据都需要O(n*m)
2：高度数据相关
3：预测结果不具有可解释性
4： 维数灾难，随着维度的增加，“看似相近”的两个点之间的距离越来越大,解决方法：降维
KNN的优点
1.简单，易于理解，易于实现，无需估计参数，无需训练；
2.适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好