knn - k近邻算法，是一种利用相似度来对测试样本做出预测的非参数方法。knn基本算法非常简单，这里主要分析knn算法的不足改进方法。这里用Python实现了一下，并在minist数据集上测试。
1. 算法实现
# -*- coding: utf-8 -*-
"""
create_train_test_data & get_all_data: 处理minist数据
analysis_date_data: 解析date数据
"""
import os
import numpy as np
def analysis_date_data():
""" 解析date数据 """
with open("../data/date_data/datingTestSet.txt", "r") as f:
rows_data = f.readlines()
length = len(rows_data)
data = np.zeros((length, 4))
for i in range(length):
data[i,:] = rows_data[i].strip().split("\t")
# norm the date data
for i in range(0,3):
data_col0_max = data[:,i].max(axis=0)
data_col1_min = data[:,i].min(axis=0)
data[:,i] = (data[:,i] - data_col1_min) / (data_col0_max - data_col1_min)
return data
def create_train_test_data(filesName):
""" 生成(train_x,train_y), (test_x,test_y) """
filesNum = len(filesName)
data = np.zeros((filesNum, 1024), np.int)
label = []
for i in range(filesNum):
label.append(int(filesName[i][0]))
with open("../data/trainingDigits/" + filesName[i], "r") as f:
for j in range(32):
each_file_row = f.readline().strip("\n")
for k in range(32):
data[i, 32*j+k] = int(each_file_row[k])
return data, label
def get_all_data():
""" get训练所需的所有数据, train_x, train_y, test_x """
train_files_dir = os.listdir("../data/trainingDigits")
test_files_dir = os.listdir("../data/testDigits")
train_x, train_y = create_train_test_data(train_files_dir)
test_x, test_y = create_train_test_data(test_files_dir)
return np.array(train_x), np.array(train_y), np.array(test_x), np.array(test_y)
if __name__ == "__main__":
train_x, train_y, test_x, test_y = get_all_data()
# -*- coding: utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
from model.prepare_data import get_all_data
class KNN(object):
def __init__(self, k):
""" 1. 初始化参数, k代表近邻个数 """
self.k = k;
def compute_label(self, k_distance):
""" 在长度为k的列表中寻找出现次数组多的数, 作为预测的label """
class_label = {}
length = len(k_distance)
for i in range(length):
class_label[k_distance[i]] = class_label.get(k_distance[i], 0) + 1
return sorted(class_label.items(), key=lambda x: x[1], reverse=True)[0][0]
def predict(self, train_x, train_y, test_x):
""" 2. predict
test_rows: test dataset的样本个数
prediction: 预测值
distance: 一个test样本与所有train样本的距离
argsort_distance: 对distance进行argsort结果
k_distance
"""
if isinstance(train_x, np.ndarray) and isinstance(train_y, np.ndarray) and isinstance(test_x, np.ndarray):
pass
else:
raise(Exception("numpy.ndarray is required for input parameters."))
test_rows = test_x.shape[0]
prediction = np.zeros((test_rows,), np.int)
for i in range(test_rows):
distance = np.sum((test_x[i, :] - train_x)**2, axis=1)
argsort_distance = np.argsort(distance)
k_distance = train_y[argsort_distance[0:self.k]]
prediction[i] = self.compute_label(k_distance)
return prediction
def compute_precision(self, prediction, test_y):
""" 3. 计算预测的正确率 """
if isinstance(test_y, np.ndarray):
pass
else:
raise(Exception("numpy.ndarray is required for input parameters."))
precision = 1 - np.abs(prediction - test_y).sum() / len(prediction)
return precision
def draw_precision(self, precision):
""" 4. 画出预测的正确率 """
plt.figure()
plt.plot(range(1,len(precision)+1), precision, "y")
plt.title("precision")
plt.xlabel("k")
plt.ylabel("precision")
plt.ylim((0,1.1))
return plt
if __name__ == "__main__":
train_x, train_y, test_x, test_y = get_all_data()
precision = []
for k in range(1,10):
obj = KNN(k)
prediction = obj.predict(train_x, train_y, test_x)
precision.append(obj.compute_precision(prediction, test_y))
obj.draw_precision(precision).show()
2. 优点 & 缺点
2.1 优点
算法原理简单易懂，估计是最简单又流行的机器学习算法。
2.2 缺点
1）普通knn算法，极易受到不平衡数据影响。如果某一类本身数据就很少，利用knn进行相似度搜索的时候，几乎无可避免的会将其他类别数据计算进当前类别。
2）最近邻算法易受噪声数据，脏数据影响，knn避开了这个问题。
3）需要一次性加载所有数据进内存。
4）计算量大，由于knn是非参数学习算法，对于每一个测试样本，都要遍历所有训练样本来计算相似度，这对大数据是不可接受的。
5）不适合大数据处理。
3. 改进方式
1）调整不平衡数据。
2）kd树改进，可以提高搜索效率。