在K近邻的原始算法中,没有对K近邻的方法进行优化,还是遍历训练集,找到与输入实例最近的K个训练实例,统计他们的类别,以此作为输入实例类别的判断。具体的模型理论见:统计学习方法——K近邻法(原始方法)
在算法实现的过程中,利用的是欧氏距离进行点与点之间的距离度量。在进行数据运算的时候,没有利用numpy,而是利用Python中自带的list来进行数据的计算。
def knn(x,dataSet,labels,k):
distanceMemories = {
} # 利用字典来记录距离
for i in range(len(dataSet)):
distance = euDis(x,dataSet[i])
distanceMemories[i] = distance
sortResult = sorted(distanceMemories.items(),key = lambda x:x[1])
distance_min_k = sortResult[:k]
classCount = {
} # 用来记录前k个中各个类出现的次数
for i in range(len(distance_min_k)):
if labels[distance_min_k[i][0]] not in classCount:
classCount[labels[distance_min_k[i][0]]] = 0
classCount[labels[distance_min_k[i][0]]] += 1
result = sorted(classCount.items(),key = lambda x:x[1],reverse = True)
# 对统计结果,按照字典中的各个值,进行降序排序
return result[0][0]
def euDis(x,y): # 欧式距离的计算
dim = len(x)
temp = 0
for i in range(dim):
temp += (x[i] - y[i]) ** 2
return temp ** 0.5
dataSet = [[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]
# 这是机器学习实战一书上的小例子
labels = ["爱情片","爱情片","爱情片","动作片","动作片","动作片"]
print(knn([18,90],dataSet,labels,3))
# 输出结果:爱情片