K-近邻算法Python实现


运用python通过计算距离来实现对某花的分类

算法解决的问题

已知样本集(此处的样本为某花的实例数据)、给定一未知样本的数据来断此样本的类别(此处为判断属于哪一类花)

解决步骤

特征抽取后计算出未知样本到所有已知样本的距离、根据给定参数K(最好为奇数便于投票)选出K个最近的样本点、统计出类别最多的样本点的类别、最终的的分类就是该类别
缺陷:数据的分布不均匀会导致结果的不准确
优化方法:根据距离的远近添加相应的权重来弱化数据分布不均匀的为题(下面代码还没实现权重的添加、、以后有空再加、、、)
个人脑洞:对于多维的数据、在二维分布上可能看不出任何规律、但在高维的空间中明显的可以分开好几个类别(如本例的某花数据在三维下就很明显了、还有支持向量机的划分方法太cool了)
此处的样本集(非常nice的数据集大全)
http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data
样本集示例:前四列为花的数据、最后为花的类别

5.1,3.5,1.4,0.2,Iris-setosa

5.0,3.3,1.4,0.2,Iris-setosa

7.0,3.2,4.7,1.4,Iris-versicolor

4.6,3.1,1.5,0.2,Iris-setosa

6.4,3.2,5.3,2.3,Iris-virginica

6.9,3.2,5.7,2.3,Iris-virginica

4.6,3.4,1.4,0.3,Iris-setosa

代码实现如下:用测试集测试可以达到96%的准确率

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import csv
import math
from collections import Counter

#导入样本集list
#导入测试集计算测试集到每个样本集的距离,结果保存为list
#根据distance排名取k个投票选出最多的这个类


#传递时要第二个参数要为空参否则会共用同一个地址
def readfile(local):
dataset=[]
with open(local) as file2:
csv_reader = csv.reader(file2)
for line in csv_reader:
dataset.append(line)
return dataset


def distance (test,train):
result=0.0
#此时每个test例如[1,2,3,4]每个train例如[1,2,3,4,a],-1除去标签
for i in range(len(test)-1):
result=result+math.sqrt(abs((float(test[i])-float(train[i]))*(float(test[i])+float(train[i]))))
return result

def sort(train,test,k=3):
result=[]
sortresult=[]
#计算每个样本集到样本的距离
for i in range(len(test)):
for m in range(len(train)):
#对于每个测试实例得到距离和对应的标签
result.append([distance(test[i],train[m]),train[m][-1]])
sortresult.append(findsort(result,k))#得到每一个测试集的分类结果
result=[] #将每个测试集的距离集合清空
return sortresult #最终结果
#得到结果集,每一个test到样本集的距离

#示例输入[[3.917258917468777, 'Iris-setosa'], [4.365595716195167, 'Iris-setosa']]
def findsort(data,k=3):
result={}
voat=[]
for x in range(len(data)):
result.update({data[x][0]:data[x][1]})
#对字典进行排序从小到大
a=sorted(result.items(), key=lambda d: d[0])
for m in range(k):
voat.append(a[m][-1])
#得到列表中出现次数最多的元素
b=Counter(voat).most_common(1)
return b[0][0]

#计算准确率
def correct(sample,predict):
flag=0
for a in range(len(sample)):
if(sample[a]==predict[a]):
flag=flag+1
return flag/len(sample)

def main():
testlist=[]
train=list(readfile("F:\\train.csv"))
test=list(readfile("F:\\test.csv"))
#k为最近邻的个数
output=sort(train,test,3)
#得到分类的结果集
print(output)
for a in range(len(test)):
testlist.append(test[a][-1])
#输出准确率
print(correct(testlist,output))
main()
文章目录
  1. 1. 算法解决的问题
  2. 2. 解决步骤