1. 前言

k-鄰近算法(kNN)是機(jī)器學(xué)習(xí)中非常簡潔并且易于掌握的算法，是一種用于分類和回歸的非參數(shù)統(tǒng)計算法。
　　 本文首先介紹k-鄰近算法思想及過程，隨后介紹了kNN的Python實現(xiàn)。全文基于機(jī)器學(xué)習(xí)實戰(zhàn)，著重闡述作者自己的理解。此外，還參考了Scipy Lecture Notes、維基百科以及許多博客。

2. 描述

2.1 工作原理

存在一個訓(xùn)練樣本集 (x,y)，每個樣本 x^(i)都有對應(yīng)的標(biāo)簽 y^(i)，也就是說，對于每個訓(xùn)練樣本，我們都知道該樣本的所屬分類。此后，輸入一個不帶標(biāo)簽的測試樣本數(shù)據(jù) x_new，選取訓(xùn)練樣本集中與 x_new 歐氏距離(*)最近的 $k$ 個點(diǎn)，獲取這k個樣本的標(biāo)簽，其中出現(xiàn)次數(shù)最多的標(biāo)簽即作為 x_new的標(biāo)簽 y_new ，即：將 x_new 歸為 y_new 類。其中，k <=20，y_new屬于y。

• 歐氏距離：即幾何距離。如：$(0, 0, 0)$ 與 $(1, 2, 3)$ 的歐氏距離為$d = \sqrt{(1-0)^2 + (2-0)^2 + (3-0)^2}$

2.2 算法描述

1. 計算分類未知數(shù)據(jù) x_new 與訓(xùn)練樣本集數(shù)據(jù) x 的歐氏距離 distance
2. 將 distance 遞增排序
3. 選取 distance 的前 k 個點(diǎn)
4. 選取前 k 個點(diǎn)中，出現(xiàn)頻率最高的類別 y 作為 x_new的分類

3. Python實現(xiàn)

import numpy as np
import os
from collections import Counter

3.1 數(shù)據(jù)導(dǎo)入

3.1.1 使用NumPy導(dǎo)入數(shù)據(jù)

使用np.loadtxt()可以讀取被空格隔開的數(shù)據(jù)。

def read_file(file_path):
    file = np.loadtxt(file_path) # 讀取txt文件
    feature = file[:, :-1]  # 前n-1列構(gòu)成特征矩陣
    label = file[:, -1]     # 最后一列構(gòu)成標(biāo)簽向量
    return feature, label

3.1.2 將32*32的文本格式照片轉(zhuǎn)換為向量

def img_to_vector(file_path):
    lines = 32 # 像素大小
    with open(file_path) as f: # 用這種形式，將自動執(zhí)行f.close()
        data = list() # 生成一個空的list
        # 使用f.readline()逐行遍歷文本，添加到data后
        for i in range(lines):
            data.append(list(f.readline())[:lines])
        # 循環(huán)結(jié)束后，生成一個32*32矩陣
        return_vector = np.array(data).ravel() # 將矩陣扁平化為一個向量
    return return_vector

3.1.3 讀取文件夾，生成訓(xùn)練樣本矩陣

def read_digits(file_path):
    file_lists = os.listdir(file_path) # 讀取文件夾下所有文件名，生成list
    file_num = file_lists.__len__() # 文件數(shù)m
    matrix = np.zeros((file_num, 1024), dtype=np.int) # 生成矩陣(m*2014)
    for i in range(file_lists.__len__()):
        abs_file_path = file_path + file_lists[i] # 文件絕對路徑
        vector = img_to_vector(abs_file_path) # 獲取文件生成的向量
        matrix[i] = vector # 為矩陣(m*2014)賦值
    return matrix

3.2 歸一化數(shù)據(jù)

樣本歸一化的作用，是將任意取值范圍的特征值轉(zhuǎn)換為0到１區(qū)間內(nèi)的值。
　　new_value = (old_value - min) / (max - min)

def auto_norm(data_mat):
    min_column = np.min(data_mat, axis=0) # 獲取每一列的最小值
    max_column = np.max(data_mat, axis=0) # 獲取每一列的最大值
    range_column = max_column - min_column # 獲取每一列的取值范圍(max - min)
    data_mat = data_mat - min_column # (old_value - min)
    norm_feature_mat = np.true_divide(data_mat, range_column)
    return norm_feature_mat

3.3 計算距離

# x為待測試點(diǎn)，point為訓(xùn)練樣本集中的點(diǎn)
# NumPy數(shù)組可以進(jìn)行許多便捷的操作
def cal_distance(x, point):
    temp = (point - x)**2
    return temp.sum(axis=1)

3.4 分類

# in_x 測試數(shù)據(jù)，可以不止一組
# data_set, labels 分別為訓(xùn)練集和訓(xùn)練集標(biāo)簽
# k 不必贅述
def classify(in_x, data_set, labels , k):
    result_labels = np.zeros((in_x.shape[0], ), dtype=np.int) # 分類結(jié)果向量
    for i in range(in_x.shape[0]):
        distance = cal_distance(in_x[i], data_set) # 計算距離
        mask = distance.argsort()[:k] # 選取前k個點(diǎn)
        k_array = labels[mask] # 利用掩碼獲取k個點(diǎn)的標(biāo)簽
        result_labels[i] = Counter(k_array).most_common(1)[0][0] # 獲取出現(xiàn)頻率最高的標(biāo)簽
    return result_labels

作者郵箱： mr.yxj@foxmail.com
轉(zhuǎn)載請告知作者，感謝！