更多文章可以訪問我的博客Aengus | Blog

k近鄰法即kNN算法，是假設(shè)給定一個(gè)訓(xùn)練集，對(duì)于每個(gè)訓(xùn)練樣本的分類已經(jīng)確認(rèn)，當(dāng)對(duì)測(cè)試樣本分類時(shí)，根據(jù)其k個(gè)最近鄰的訓(xùn)練樣本的類別，通過多數(shù)表決的方式進(jìn)行預(yù)測(cè)。kNN算法沒有顯式的學(xué)習(xí)過程。

kNN算法

假設(shè)給定的訓(xùn)練集為 $\{(x_1, y_1), (x_2, y_2), \cdots,(x_N, y_N) \}$ ，其中 $x_i \in R^N$ ， $y_i \in \{c_1, c_2, \cdots, c_K\}$ ，步驟為：

（1）根據(jù)給定的距離度量（即距離計(jì)算方法），在訓(xùn)練集中找出與測(cè)試樣本 $x$ 的前 $k$ 個(gè)最近鄰的點(diǎn)，涵蓋這 $k$ 個(gè)點(diǎn)的 $x$ 的鄰域記作 $N_k(x)$ ；

（2）在 $N_k(x)$ 中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定 $x$ 的類別 $y$ ：
$y = \arg \max_{c_j}\sum_{x_i \in N_k(x)} I(y_i=c_j),i=1,2,\cdots,N;j=1,2,\cdots,K$
其中 $I$ 代表指示函數(shù)， $y_i=c_j$ 時(shí) $I=1$ ，否則為0；

當(dāng) $k=1$ 的時(shí)候稱為最近鄰算法。

距離度量

特征空間中兩個(gè)點(diǎn)的距離是兩個(gè)訓(xùn)練樣本相似程度的反映。kNN算法使用的距離一般是歐式距離，但也可以是更一般的 $L_p$ 距離或者M(jìn)inkowski距離。

設(shè)待測(cè)距離的兩個(gè)點(diǎn) $x_i,x_j \in R^N$ ，且 $x_i=(x_i^{(1)}, x_i^{(2)}, \cdots,x_i^{(N)})^T,x_j=(x_j^{(1)}, x_j^{(2)}, \cdots,x_j^{(N)})^T$ ，那么 $L_p$ 距離定義為：
$L_p(x_i, x_j) = (\sum^N_{k=1}|x_i^{(k)}-x_j^{(k)}|^{p})^{\frac{1}{p}},p \geq 1$
當(dāng) $p=2$ 時(shí)，稱為歐式距離； $p=1$ 時(shí)，稱為曼哈頓距離；當(dāng) $p= \infty$ 時(shí)，它是各個(gè)坐標(biāo)的最大值：
$L_{\infty}(x_i, x_j) = \max_{k}|x^{(k)}_i - x^{(k)}_j|$

k值的選擇

如果k值選擇的比較小，如果最近鄰的點(diǎn)恰好是噪點(diǎn)，那么預(yù)測(cè)就會(huì)出錯(cuò)，也就是說，k值的減小會(huì)導(dǎo)致模型變復(fù)雜，容易發(fā)生過擬合；

如果k值選擇的比較大，那么模型就比較簡(jiǎn)單。如果令 $k=N$ ，那么如果輸入什么點(diǎn)，預(yù)測(cè)的分類都會(huì)變成訓(xùn)練樣本最多的類別，模型喪失了可用性。

分類策略

$k$ 近鄰算法常用的決策規(guī)則往往是多數(shù)表決。

對(duì)于給定的測(cè)試樣本 $x$ ，其最近鄰的 $k$ 個(gè)訓(xùn)練樣本組成的集合為 $N_k(x)$ 。如果涵蓋 $N_k(x)$ 的區(qū)域類別是 $c_j$ ，那么誤分類率是
$\frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i \neq c_j) = 1 - \frac{1}{k}\sum_{x_i \in N_k(x)}I(y_i = c_j)$
要使誤分類率最小即經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，就要使 $\sum_{x_i \in N_k(x)}I(y_i= c_j)$ 最大，所以多數(shù)表決策略等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。

求解實(shí)現(xiàn)

kNN算法實(shí)現(xiàn)最簡(jiǎn)單的方法就是“線性掃描”，即計(jì)算每個(gè)訓(xùn)練點(diǎn)到測(cè)試樣本的距離，當(dāng)訓(xùn)練集很大且維度比較高的時(shí)候計(jì)算量很大。

還有一種方法叫作kd樹，利用特殊的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)，以減小計(jì)算距離的次數(shù)。

kd樹

kd樹是一種對(duì)k維空間中的訓(xùn)練樣本進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd樹是二叉樹，表示對(duì)k維空間的一個(gè)劃分。構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分，構(gòu)造一系列的k維超矩形區(qū)域。kd樹的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)k維超矩形結(jié)構(gòu)。

構(gòu)造算法

假設(shè)給定的訓(xùn)練集為 $\{(x_1, y_1), (x_2, y_2), \cdots,(x_N, y_N) \}$ ，其中 $x_i = (x_i^{(1)},x_i^{(2)}, \cdots, x_i^{(k)})^T$ ， $i=1, 2, \cdots,N$ ，則按照以下步驟進(jìn)行構(gòu)造：

（1）構(gòu)造根結(jié)點(diǎn)，根結(jié)點(diǎn)對(duì)應(yīng)包含訓(xùn)練樣本的 $k$ 維空間的超矩形區(qū)域。選擇以 $x^{(1)}$ 為坐標(biāo)軸，以所有訓(xùn)練樣本的 $x^{(1)}$ 坐標(biāo)的中位數(shù)為切分點(diǎn)，將根結(jié)點(diǎn)對(duì)應(yīng)的超矩形區(qū)域切分為兩個(gè)不同區(qū)域，切分由通過切分點(diǎn)且與坐標(biāo)軸 $x^{(1)}$ 垂直的超平面實(shí)現(xiàn)；由此得到深度為1的左右子樹，左子樹是 $x^{(1)}$ 坐標(biāo)小于根結(jié)點(diǎn) $x^{(1)}$ 坐標(biāo)的所有訓(xùn)練樣本；右子樹是 $x^{(1)}$ 坐標(biāo)大于根結(jié)點(diǎn) $x^{(1)}$ 坐標(biāo)的所有訓(xùn)練樣本；

（2）對(duì)于所有深度為 $j$ 的結(jié)點(diǎn)，選擇 $x^{(l)}$ 為切分的坐標(biāo)軸， $l=j(\mod{k})+1$ ,然后重復(fù)類似上述構(gòu)造根結(jié)點(diǎn)的步驟進(jìn)行構(gòu)造；將落在切分超平面上的實(shí)例點(diǎn)保存在該結(jié)點(diǎn)；

（3）直到兩個(gè)子區(qū)域沒有實(shí)例存在時(shí)停止，從而形成kd樹的劃分。

如果中位數(shù)上沒有樣本點(diǎn)，可以選擇相鄰的點(diǎn)作為切分點(diǎn)。

搜索算法

輸入為kd樹以及測(cè)試樣本 $x$ ，按照以下步驟進(jìn)行搜索：

（1）從根結(jié)點(diǎn)出發(fā)，遞歸的往下訪問，如果測(cè)試樣本 $x$ 的當(dāng)前維度的坐標(biāo)小于切分點(diǎn)坐標(biāo)，則往左找，否則往右找。直到子結(jié)點(diǎn)為葉結(jié)點(diǎn)位置。這樣就找到了包含測(cè)試樣本 $x$ 的葉結(jié)點(diǎn)；

（2）以此葉結(jié)點(diǎn)作為“當(dāng)前最近點(diǎn)”；

（3）遞歸的往上回退，再每個(gè)結(jié)點(diǎn)進(jìn)行以下操作：

? （a）如果該結(jié)點(diǎn)包含的訓(xùn)練樣本比當(dāng)前最近點(diǎn)距離測(cè)試樣本更近，則以該樣本作為“當(dāng)前最近點(diǎn)”；

? （b）檢查另一子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否存在與以測(cè)試樣本為球心、以測(cè)試樣本與“當(dāng)前最近點(diǎn)”間距離為半徑的超球體相交，如果存在，可能在另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點(diǎn)更近的點(diǎn)，移動(dòng)到另一個(gè)子結(jié)點(diǎn)，進(jìn)行此搜索算法；否則，往上回退；

（4）當(dāng)回退到根結(jié)點(diǎn)時(shí)，搜索結(jié)束，最后的“當(dāng)前最近點(diǎn)”即為 $x$ 的最近鄰點(diǎn)；

如果訓(xùn)練點(diǎn)是隨機(jī)分布的，那么kd樹的平均復(fù)雜度為 $O(\log N)$ ， $N$ 為訓(xùn)練樣本的數(shù)量。kd樹更適用于訓(xùn)練樣本樹遠(yuǎn)遠(yuǎn)大于空間維數(shù)時(shí)的 $k$ 近鄰搜索，當(dāng)兩者相近時(shí)，它的效率會(huì)大大下降，幾乎接近線性掃描。

Python實(shí)現(xiàn)

下面是利用“線性掃描”的方法實(shí)現(xiàn)kNN算法：

import numpy as np


def knn(x_data, y_label, k, x):
    """
    kNN算法
    :param x_data: 訓(xùn)練集，形如[[1, 2, 3], [2, 3, 4]]
    :param y_label: 標(biāo)簽
    :param k: k值
    :param x: 測(cè)試集
    :return: 分類結(jié)果
    """
    m, n = x_data.shape
    # dist = [[距離1， 分類1], [距離2， 分類2], [距離3， 分類3], ...]
    dist = np.zeros((m, 2))
    # 計(jì)算每個(gè)點(diǎn)到測(cè)試點(diǎn)的距離
    for i in range(m):
        dist[i, 0] = sum(pow(x_data[i, j]-x[j], 2) for j in range(n))
        dist[i, 1] = y_label[i]
    sorted_dist = sorted(dist, key=lambda first: first[0], reverse=False)
    vote = {}
    for i in range(m):
        vote[y_label[i]] = 0
    for i in range(k):
        vote[sorted_dist[i][1]] += 1
    sorted_vote = sorted(vote, reverse=True)
    return sorted_vote[0]

參考

李航《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》第三章

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

統(tǒng)計(jì)學(xué)習(xí)方法筆記之k近鄰算法（附代碼實(shí)現(xiàn)）

統(tǒng)計(jì)學(xué)習(xí)方法筆記之k近鄰算法（附代碼實(shí)現(xiàn)）

kNN算法

距離度量

k值的選擇

分類策略

求解實(shí)現(xiàn)

kd樹

構(gòu)造算法

搜索算法

Python實(shí)現(xiàn)

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

統(tǒng)計(jì)學(xué)習(xí)方法筆記之k近鄰算法（附代碼實(shí)現(xiàn)）

kNN算法

距離度量

k值的選擇

分類策略

求解實(shí)現(xiàn)

kd樹

構(gòu)造算法

搜索算法

Python實(shí)現(xiàn)

參考

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av