返回主頁(yè)

k 最近鄰算法（k-nearest neighbor, k-NN）是一種基本的分類方法（二分類 / 多分類），由 Cover 和 Hart 于1968年提出。它的輸入為特征向量，通過(guò)距離度量與多數(shù)表決，輸出類別標(biāo)記。該算法不具有顯式的學(xué)習(xí)過(guò)程，且 k 值的選擇對(duì)結(jié)果會(huì)產(chǎn)生重大的影響，因此對(duì)于 k-NN 而言，k 的選擇至關(guān)重要。

1、定義數(shù)據(jù)集

數(shù)據(jù)集

特征空間

2、假設(shè)空間

每個(gè)樣本的預(yù)測(cè)類別 = 該樣本所屬的以 k 為范圍的鄰域內(nèi)所有訓(xùn)練樣本類別的投票值

關(guān)于距離的度量一般有曼哈頓距離和歐氏距離等等：

3、目標(biāo)函數(shù)

目標(biāo)函數(shù)的任務(wù)是使所有訓(xùn)練樣本的鄰域內(nèi)誤分類率最低，所以 k 是待估計(jì)的參數(shù)

4、優(yōu)化算法
k-NN 不具有顯式的學(xué)習(xí)過(guò)程，一般在預(yù)測(cè)的過(guò)程中通過(guò)線性掃描或KD樹的方法執(zhí)行判斷

手寫 k-NN 算法并與 Sklearn 作比較

# -*- coding: utf-8 -*-
from __future__ import (absolute_import, division, print_function)
import numpy as np
import pandas as pd
import scipy.spatial.distance as dist
from sklearn.utils import shuffle
from sklearn.model_selection import train_test_split
#import random as rd
#import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier


class KnnModel(object):
    @staticmethod
    def check_k(K, x_train):
        if not isinstance(K, np.ndarray):
            raise TypeError("K must be as type of np.ndarray")
            
        if (min(K) <= 0) or (max(K) > len(x_train)):
            raise ValueError("K must be in range [1, N]")
            
        for k in K:
            if not isinstance(k, np.int32):
                raise TypeError("the element of K must be as type of np.int32")
        return None
        
    
    def __init__(self, K, metric):
        self.K = K
        self.metric = metric
    
    
    def z_scale(self, x_train):
        '''z標(biāo)準(zhǔn)化，在動(dòng)用距離度量的算法中，必須先進(jìn)行標(biāo)準(zhǔn)化以消除數(shù)據(jù)量綱的影響'''
        mu = np.mean(x_train, axis=0)
        std = np.std(x_train, axis=0)
        return mu, std
    
    
    def data_transform(self, mu, std, x_train, x_test):
        '''數(shù)據(jù)變換，執(zhí)行標(biāo)準(zhǔn)化操作'''
        x_train_scale = (x_train - mu) / std
        x_test_scale = (x_test - mu) / std
        return x_train_scale, x_test_scale
    
    
    def l1(self, x1, x2):
        '''曼哈頓距離'''
        return np.sum(np.abs(x1 - x2))
    
    
    def l2(self, x1, x2):
        '''歐氏距離'''
        return np.sqrt(np.sum((x1 - x2)**2))
    
    
    def cosine(self, x1, x2):
        '''余弦距離'''
        return 1 - x1.dot(x2) / (np.sqrt(np.sum(x1**2)) * np.sqrt(np.sum(x2**2)))
    
    
    def fit(self, x_train_scale, y_train):
        '''模型訓(xùn)練，針對(duì)KNN，其實(shí)沒有顯示的學(xué)習(xí)過(guò)程，所謂的訓(xùn)練其主要目的就是選擇合適的k值'''
        # 訓(xùn)練樣本量
        N = len(x_train_scale)
        # 適配距離函數(shù)
        if self.metric == "l1":
            m = self.l1
        elif self.metric == "l2":
            m = self.l2
        elif self.metric == "cosine":
            m = self.cosine
        else:
            raise ValueError("metric must be 'l1', 'l2' or 'cosine'")
        # 計(jì)算樣本兩兩距離，形成距離方陣
        #dist_train = dist.cdist(x_train_scale, x_train_scale, metric="euclidean")
        dist_train = dist.cdist(x_train_scale, x_train_scale, metric=m)
        dist_train = pd.DataFrame(dist_train)
        # 迭代，選擇最優(yōu)的k值
        loss_list = []
        for k in K:
            loss_res = 0
            for idx in dist_train.index:
                # 為每個(gè)樣本計(jì)算k近鄰索引
                k_nearest_idx = dist_train.iloc[idx, :].sort_values(ascending=True)[1:k+1].index
                # 得到k近鄰的類別標(biāo)記
                c = y_train[k_nearest_idx]
                # 計(jì)算誤分類率
                loss = sum(y_train[idx] != c) / k
                loss_res += loss
            # 總體誤分類率
            loss_res /= N
            loss_list.append(loss_res)
        # 取誤分類率最小的k為最優(yōu)值
        k_best = K[np.argmin(loss_list)]
        print(f"誤分類率列表：\n{loss_list} \n最優(yōu)的k：{k_best}")
        return k_best
    
    
    def predict(self, x_train_scale, x_test_scale, y_train, k_best):
        '''模型預(yù)測(cè)，每個(gè)樣本的預(yù)測(cè)類別 = 該樣本所屬的以 k 為范圍的鄰域內(nèi)所有訓(xùn)練樣本類別的投票值'''
        # 適配距離函數(shù)
        if self.metric == "l1":
            m = self.l1
        elif self.metric == "l2":
            m = self.l2
        elif self.metric == "cosine":
            m = self.cosine
        else:
            raise ValueError("metric must be 'l1', 'l2' or 'cosine'")
        # 計(jì)算測(cè)試集樣本與訓(xùn)練集樣本的兩兩距離
        dist_test = dist.cdist(x_test_scale, x_train_scale, metric=m)
        dist_test = pd.DataFrame(dist_test)
        # 執(zhí)行預(yù)測(cè)，找到以 k 為范圍的鄰域內(nèi)所有訓(xùn)練樣本類別的投票值
        y_pred = []
        for i in range(len(dist_test)):
            k_nearest_idx = dist_test.iloc[i, :].sort_values(ascending=True)[0:k_best].index
            c = y_train[k_nearest_idx]
            label, label_count = np.unique(c, return_counts=True)
            y_hat = label[np.argmax(label_count)]
            y_pred.append(y_hat)
        return y_pred
    
    
    def get_score(self, y_true, y_pred):
        '''模型評(píng)估'''
        score = sum(y_true == y_pred) / len(y_true)
        return score
        

if __name__ == "__main__":
    # 構(gòu)造多分類數(shù)據(jù)集
    n1 = 20
    x1 = np.random.uniform(low=1, high=5, size=[n1, 4]) + np.random.randn(n1, 4)*0.01
    y1 = np.tile(0, n1)
    
    n2 = 10
    x2 = np.random.uniform(low=6, high=10, size=[n2, 4]) + np.random.randn(n2, 4)*0.01
    y2 = np.tile(1, n2)
    
    n3 = 30
    x3 = np.random.uniform(low=8, high=20, size=[n3, 4]) + np.random.randn(n3, 4)*0.01
    y3 = np.tile(2, n3)
    
    x = np.concatenate([x1, x2, x3], axis=0)
    y = np.concatenate([y1, y2, y3])
    
    x, y = shuffle(x, y, random_state=0)
    x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2)
    
    K = np.array([3, 5, 7, 9, 11, 15, 20]).astype(np.int32)
    
    # 手寫 k-NN
    model = KnnModel(K=K, metric="l2")
    model.check_k(K, x_train)
    
    mu, std = model.z_scale(x_train)
    x_train_scale, x_test_scale = model.data_transform(mu, std, x_train, x_test)
    k_best = model.fit(x_train_scale, y_train)
    
    y_pred = model.predict(x_train_scale, x_test_scale, y_train, k_best)
    score = model.get_score(y_test, y_pred)
    print(f"KnnModel 預(yù)測(cè)準(zhǔn)確率：{score}")
    
    # sklearn
    scale = StandardScaler(with_mean=True, with_std=True)
    scale.fit(x_train)
    x_train_scale = scale.transform(x_train)
    x_test_scale = scale.transform(x_test)
    
    clf = KNeighborsClassifier(n_neighbors=5, algorithm="kd_tree", metric="euclidean")
    clf.fit(x_train_scale, y_train)
    y_pred = clf.predict(x_test_scale)
    score = sum(y_test == y_pred) / len(y_test)
    print(f"KnnSklearn 預(yù)測(cè)準(zhǔn)確率：{score}")

誤分類率列表：
[0.020833333333333332, 0.024999999999999998, 0.029761904761904757, 0.05324074074074075, 0.0890151515151515, 0.14444444444444446, 0.25]
最優(yōu)的k：3
KnnModel 預(yù)測(cè)準(zhǔn)確率：1.0

KnnSklearn 預(yù)測(cè)準(zhǔn)確率：1.0

返回主頁(yè)