一看就懂的K近鄰算法(KNN)穿挨，K-D樹(shù)月弛，并實(shí)現(xiàn)手寫數(shù)字識(shí)別！

1. 什么是KNN

1.1 KNN的通俗解釋

何謂K近鄰算法科盛，即K-Nearest Neighbor algorithm帽衙，簡(jiǎn)稱KNN算法，單從名字來(lái)猜想贞绵，可以簡(jiǎn)單粗暴的認(rèn)為是：K個(gè)最近的鄰居厉萝，當(dāng)K=1時(shí)，算法便成了最近鄰算法，即尋找最近的那個(gè)鄰居谴垫。

用官方的話來(lái)說(shuō)章母，所謂K近鄰算法，即是給定一個(gè)訓(xùn)練數(shù)據(jù)集翩剪，對(duì)新的輸入實(shí)例乳怎，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例（也就是上面所說(shuō)的K個(gè)鄰居），這K個(gè)實(shí)例的多數(shù)屬于某個(gè)類前弯，就把該輸入實(shí)例分類到這個(gè)類中蚪缀。

image
image

如上圖所示，有兩類不同的樣本數(shù)據(jù)恕出，分別用藍(lán)色的小正方形和紅色的小三角形表示询枚，而圖正中間的那個(gè)綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類的數(shù)據(jù)。也就是說(shuō)浙巫，現(xiàn)在哩盲，我們不知道中間那個(gè)綠色的數(shù)據(jù)是從屬于哪一類（藍(lán)色小正方形or紅色小三角形），KNN就是解決這個(gè)問(wèn)題的狈醉。

如果K=3，綠色圓點(diǎn)的最近的3個(gè)鄰居是2個(gè)紅色小三角形和1個(gè)藍(lán)色小正方形惠险，少數(shù)從屬于多數(shù)苗傅，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類點(diǎn)屬于紅色的三角形一類班巩。

如果K=5渣慕，綠色圓點(diǎn)的最近的5個(gè)鄰居是2個(gè)紅色三角形和3個(gè)藍(lán)色的正方形，還是少數(shù)從屬于多數(shù)抱慌，基于統(tǒng)計(jì)的方法逊桦，判定綠色的這個(gè)待分類點(diǎn)屬于藍(lán)色的正方形一類。

于此我們看到抑进，當(dāng)無(wú)法判定當(dāng)前待分類點(diǎn)是從屬于已知分類中的哪一類時(shí)强经，我們可以依據(jù)統(tǒng)計(jì)學(xué)的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重寺渗，而把它歸為(或分配)到權(quán)重更大的那一類匿情。這就是K近鄰算法的核心思想。

1.2 近鄰的距離度量

我們看到信殊，K近鄰算法的核心在于找到實(shí)例點(diǎn)的鄰居炬称，這個(gè)時(shí)候，問(wèn)題就接踵而至了涡拘，如何找到鄰居玲躯，鄰居的判定標(biāo)準(zhǔn)是什么，用什么來(lái)度量。這一系列問(wèn)題便是下面要講的距離度量表示法跷车。

有哪些距離度量的表示法(普及知識(shí)點(diǎn)棘利，可以跳過(guò))：

  1. 歐氏距離，最常見(jiàn)的兩點(diǎn)之間或多點(diǎn)之間的距離表示法姓赤，又稱之為歐幾里得度量赡译，它定義于歐幾里得空間中，如點(diǎn) x = (x1,...,xn) 和 y = (y1,...,yn) 之間的距離為：

    d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}

    • 二維平面上兩點(diǎn)a(x1,y1)與b(x2,y2)間的歐氏距離：

      d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

    • 三維空間兩點(diǎn)a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：

      d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}

    • 兩個(gè)n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的歐氏距離：

      d_{12}=\sqrt{\sum_{k=1}^{n}(x_{1k}-x_{2k})^2}

      也可以用表示成向量運(yùn)算的形式：

      d_{12}=\sqrt{(a-b)(a-b)^T}

  2. 曼哈頓距離不铆，我們可以定義曼哈頓距離的正式意義為L(zhǎng)1-距離或城市區(qū)塊距離蝌焚，也就是在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和。例如在平面上誓斥，坐標(biāo)（x1, y1）的點(diǎn)P1與坐標(biāo)（x2, y2）的點(diǎn)P2的曼哈頓距離為：|x_1-x_2|+|y_1-y_2|只洒，要注意的是，曼哈頓距離依賴座標(biāo)系統(tǒng)的轉(zhuǎn)度劳坑，而非系統(tǒng)在座標(biāo)軸上的平移或映射毕谴。

    通俗來(lái)講，想象你在曼哈頓要從一個(gè)十字路口開(kāi)車到另外一個(gè)十字路口距芬，駕駛距離是兩點(diǎn)間的直線距離嗎涝开？顯然不是，除非你能穿越大樓框仔。而實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”舀武，此即曼哈頓距離名稱的來(lái)源， 同時(shí)离斩，曼哈頓距離也稱為城市街區(qū)距離(City Block distance)银舱。

    • 二維平面兩點(diǎn)a(x1,y1)與b(x2,y2)間的曼哈頓距離

      d_{12}=|x_1-x_2|+|y_1-y_2|

    • 兩個(gè)n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的曼哈頓距離

      d_{12}=\sum_{k=1}^{n}|x_{1k}-x_{2k}|

  3. 切比雪夫距離，若二個(gè)向量或二個(gè)點(diǎn)p 跛梗、and q寻馏，其座標(biāo)分別為Pi及qi，則兩者之間的切比雪夫距離定義如下：

    D_{Chebyshev}(p,q)=max_i(|p_i-q_i|)

    這也等于以下Lp度量的極值：\lim_{x \to \infty}(\sum_{i=1}^{n}|p_i-q_i|^k)^{1/k}核偿，因此切比雪夫距離也稱為L(zhǎng)∞度量诚欠。

    以數(shù)學(xué)的觀點(diǎn)來(lái)看，切比雪夫距離是由一致范數(shù)（uniform norm）（或稱為上確界范數(shù)）所衍生的度量漾岳，也是超凸度量（injective metric space）的一種聂薪。

    在平面幾何中，若二點(diǎn)p及q的直角坐標(biāo)系坐標(biāo)為(x1,y1)及(x2,y2)蝗羊，則切比雪夫距離為：

    D_{Chess}=max(|x_2-x_1|,|y_2-y_1|)

    玩過(guò)國(guó)際象棋的朋友或許知道藏澳，國(guó)王走一步能夠移動(dòng)到相鄰的8個(gè)方格中的任意一個(gè)。那么國(guó)王從格子(x1,y1)走到格子(x2,y2)最少需要多少步耀找？翔悠。你會(huì)發(fā)現(xiàn)最少步數(shù)總是max( | x2-x1 | , | y2-y1 | ) 步 业崖。有一種類似的一種距離度量方法叫切比雪夫距離。

    • 二維平面兩點(diǎn)a(x1,y1)與b(x2,y2)間的切比雪夫距離 ：

      d_{12}=max(|x_2-x_1|,|y_2-y_1|)

    • 兩個(gè)n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的切比雪夫距離：

      d_{12}=max_i(|x_{1i}-x_{2i}|)

      這個(gè)公式的另一種等價(jià)形式是

      d_{12}=lim_{k\to\infin}(\sum_{i=1}^{n}|x_{1i}-x_{2i}|^k)^{1/k}

  4. 閔可夫斯基距離(Minkowski Distance)蓄愁，閔氏距離不是一種距離双炕，而是一組距離的定義。

    兩個(gè)n維變量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的閔可夫斯基距離定義為：

    d_{12}=\sqrt[p]{\sum_{k=1}^{n}|x_{1k}-x_{2k}|^p}

    其中p是一個(gè)變參數(shù)撮抓。
    當(dāng)p=1時(shí)妇斤，就是曼哈頓距離
    當(dāng)p=2時(shí)，就是歐氏距離
    當(dāng)p→∞時(shí)丹拯，就是切比雪夫距離
    根據(jù)變參數(shù)的不同站超，閔氏距離可以表示一類的距離。

  5. 標(biāo)準(zhǔn)化歐氏距離乖酬，標(biāo)準(zhǔn)化歐氏距離是針對(duì)簡(jiǎn)單歐氏距離的缺點(diǎn)而作的一種改進(jìn)方案死相。標(biāo)準(zhǔn)歐氏距離的思路：既然數(shù)據(jù)各維分量的分布不一樣，那先將各個(gè)分量都“標(biāo)準(zhǔn)化”到均值咬像、方差相等算撮。至于均值和方差標(biāo)準(zhǔn)化到多少，先復(fù)習(xí)點(diǎn)統(tǒng)計(jì)學(xué)知識(shí)县昂。

    假設(shè)樣本集X的數(shù)學(xué)期望或均值(mean)為m肮柜，標(biāo)準(zhǔn)差(standard deviation，方差開(kāi)根)為s倒彰，那么X的“標(biāo)準(zhǔn)化變量”X*表示為：(X-m）/s素挽，而且標(biāo)準(zhǔn)化變量的數(shù)學(xué)期望為0，方差為1狸驳。
    即，樣本集的標(biāo)準(zhǔn)化過(guò)程(standardization)用公式描述就是：

    X^*=\frac{X-m}{s}

    標(biāo)準(zhǔn)化后的值 = ( 標(biāo)準(zhǔn)化前的值 － 分量的均值 ) /分量的標(biāo)準(zhǔn)差　　
    經(jīng)過(guò)簡(jiǎn)單的推導(dǎo)就可以得到兩個(gè)n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的標(biāo)準(zhǔn)化歐氏距離的公式：

    d_{12}=\sqrt{\sum_{k=1}^{n}(\frac{x_{1k}-x_{2k}}{s_k})^2}

  6. 馬氏距離

    有M個(gè)樣本向量X1~Xm缩赛，協(xié)方差矩陣記為S耙箍，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：

    D(X)=\sqrt{(X-u)^TS^{-1}(X_i-X_j)}

    • 若協(xié)方差矩陣是單位矩陣（各個(gè)樣本向量之間獨(dú)立同分布）,則公式就成了,也就是歐氏距離了：

      D(X_i,X_j)=\sqrt{(X_i-X_j)^T(X_i-X_j)}

    • 若協(xié)方差矩陣是對(duì)角矩陣酥馍，公式變成了標(biāo)準(zhǔn)化歐氏距離辩昆。

    馬氏距離的優(yōu)缺點(diǎn)：量綱無(wú)關(guān)，排除變量之間的相關(guān)性的干擾旨袒。

  7. 巴氏距離

    在統(tǒng)計(jì)中汁针，巴氏距離距離測(cè)量?jī)蓚€(gè)離散或連續(xù)概率分布的相似性。它與衡量?jī)蓚€(gè)統(tǒng)計(jì)樣品或種群之間的重疊量的巴氏距離系數(shù)密切相關(guān)砚尽。巴氏距離距離和巴氏距離系數(shù)以20世紀(jì)30年代曾在印度統(tǒng)計(jì)研究所工作的一個(gè)統(tǒng)計(jì)學(xué)家A. Bhattacharya命名施无。同時(shí)，Bhattacharyya系數(shù)可以被用來(lái)確定兩個(gè)樣本被認(rèn)為相對(duì)接近的必孤，它是用來(lái)測(cè)量中的類分類的可分離性猾骡。

    對(duì)于離散概率分布 p和q在同一域 X瑞躺，它被定義為：

    D_B(p,q)=-ln(BC(p,q))

    其中：

    BC(p,q)=\sum_{x\in_{}X}\sqrt{p(x)q(x)}

    是Bhattacharyya系數(shù)。

  8. 漢明距離

    兩個(gè)等長(zhǎng)字符串s1與s2之間的漢明距離定義為將其中一個(gè)變?yōu)榱硗庖粋€(gè)所需要作的最小替換次數(shù)兴想。例如字符串“1111”與“1001”之間的漢明距離為2幢哨。應(yīng)用：信息編碼（為了增強(qiáng)容錯(cuò)性，應(yīng)使得編碼間的最小漢明距離盡可能大）嫂便。

  9. 夾角余弦

    幾何中夾角余弦可用來(lái)衡量?jī)蓚€(gè)向量方向的差異捞镰，機(jī)器學(xué)習(xí)中借用這一概念來(lái)衡量樣本向量之間的差異。

    • 在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：

      cos\theta=\frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}

    • 兩個(gè)n維樣本點(diǎn)a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角余弦：

      cos\theta=\frac{a*b}{|a||b|}

    夾角余弦取值范圍為[-1,1]毙替。夾角余弦越大表示兩個(gè)向量的夾角越小岸售，夾角余弦越小表示兩向量的夾角越大。當(dāng)兩個(gè)向量的方向重合時(shí)夾角余弦取最大值1蔚龙，當(dāng)兩個(gè)向量的方向完全相反夾角余弦取最小值-1冰评。

  10. 杰卡德相似系數(shù)

    兩個(gè)集合A和B的交集元素在A，B的并集中所占的比例木羹，稱為兩個(gè)集合的杰卡德相似系數(shù)甲雅，用符號(hào)J(A,B)表示。杰卡德相似系數(shù)是衡量?jī)蓚€(gè)集合的相似度一種指標(biāo)坑填。

    J(A,B)=\frac{|A\cap_{}B|}{|A\cup_{}B|}

    與杰卡德相似系數(shù)相反的概念是杰卡德距離：

    J_{\delta}(A,B)=1-J(A,B)=\frac{|A\cup_{}B|-|A\cap_{}B|}{|A\cup_{}B|}

  11. 皮爾遜系數(shù)

    在統(tǒng)計(jì)學(xué)中抛人，皮爾遜積矩相關(guān)系數(shù)用于度量?jī)蓚€(gè)變量X和Y之間的相關(guān)（線性相關(guān)），其值介于-1與1之間脐瑰。通常情況下通過(guò)以下取值范圍判斷變量的相關(guān)強(qiáng)度：

    0.8-1.0 極強(qiáng)相關(guān)
    0.6-0.8 強(qiáng)相關(guān)
    0.4-0.6 中等程度相關(guān)
    0.2-0.4 弱相關(guān)
    0.0-0.2 極弱相關(guān)或無(wú)相關(guān)

簡(jiǎn)單說(shuō)來(lái)妖枚，各種“距離”的應(yīng)用場(chǎng)景簡(jiǎn)單概括為，

  • 空間：歐氏距離苍在，
  • 路徑：曼哈頓距離绝页，國(guó)際象棋國(guó)王：切比雪夫距離，
  • 以上三種的統(tǒng)一形式:閔可夫斯基距離寂恬，
  • 加權(quán)：標(biāo)準(zhǔn)化歐氏距離续誉，
  • 排除量綱和依存：馬氏距離，
  • 向量差距：夾角余弦初肉，
  • 編碼差別：漢明距離酷鸦，
  • 集合近似度：杰卡德類似系數(shù)與距離，
  • 相關(guān)：相關(guān)系數(shù)與相關(guān)距離牙咏。

1.3 K值選擇

  1. 如果選擇較小的K值臼隔，就相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，“學(xué)習(xí)”近似誤差會(huì)減小妄壶，只有與輸入實(shí)例較近或相似的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用摔握，與此同時(shí)帶來(lái)的問(wèn)題是“學(xué)習(xí)”的估計(jì)誤差會(huì)增大，換句話說(shuō)丁寄，K值的減小就意味著整體模型變得復(fù)雜盒发，容易發(fā)生過(guò)擬合例嘱；
  2. 如果選擇較大的K值，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)宁舰，其優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計(jì)誤差拼卵，但缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大。這時(shí)候蛮艰，與輸入實(shí)例較遠(yuǎn)（不相似的）訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)器作用腋腮，使預(yù)測(cè)發(fā)生錯(cuò)誤，且K值的增大就意味著整體的模型變得簡(jiǎn)單壤蚜。
  3. K=N即寡，則完全不足取，因?yàn)榇藭r(shí)無(wú)論輸入實(shí)例是什么袜刷，都只是簡(jiǎn)單的預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中最多的累聪富，模型過(guò)于簡(jiǎn)單，忽略了訓(xùn)練實(shí)例中大量有用信息著蟹。

在實(shí)際應(yīng)用中墩蔓，K值一般取一個(gè)比較小的數(shù)值，例如采用交叉驗(yàn)證法（簡(jiǎn)單來(lái)說(shuō)萧豆，就是一部分樣本做訓(xùn)練集奸披，一部分做測(cè)試集）來(lái)選擇最優(yōu)的K值。

1.4 KNN最近鄰分類算法的過(guò)程

  1. 計(jì)算測(cè)試樣本和訓(xùn)練樣本中每個(gè)樣本點(diǎn)的距離（常見(jiàn)的距離度量有歐式距離涮雷，馬氏距離等）阵面；
  2. 對(duì)上面所有的距離值進(jìn)行排序；
  3. 選前 k 個(gè)最小距離的樣本洪鸭；
  4. 根據(jù)這 k 個(gè)樣本的標(biāo)簽進(jìn)行投票样刷，得到最后的分類類別；

2. KDD的實(shí)現(xiàn)：KD樹(shù)

Kd-樹(shù)是K-dimension tree的縮寫览爵，是對(duì)數(shù)據(jù)點(diǎn)在k維空間（如二維(x置鼻，y)，三維(x拾枣，y，z)盒让，k維(x1梅肤，y，z..)）中劃分的一種數(shù)據(jù)結(jié)構(gòu)邑茄，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）姨蝴。本質(zhì)上說(shuō)，Kd-樹(shù)就是一種平衡二叉樹(shù)肺缕。

首先必須搞清楚的是左医，k-d樹(shù)是一種空間劃分樹(shù)授帕，說(shuō)白了，就是把整個(gè)空間劃分為特定的幾個(gè)部分浮梢，然后在特定空間的部分內(nèi)進(jìn)行相關(guān)搜索操作跛十。想像一個(gè)三維(多維有點(diǎn)為難你的想象力了)空間，kd樹(shù)按照一定的劃分規(guī)則把這個(gè)三維空間劃分了多個(gè)空間秕硝，如下圖所示：

image

2.1 構(gòu)建KD樹(shù)

kd樹(shù)構(gòu)建的偽代碼如下圖所示：

image

再舉一個(gè)簡(jiǎn)單直觀的實(shí)例來(lái)介紹k-d樹(shù)構(gòu)建算法芥映。假設(shè)有6個(gè)二維數(shù)據(jù)點(diǎn){(2,3)，(5,4)远豺，(9,6)奈偏，(4,7)，(8,1)躯护，(7,2)}惊来，數(shù)據(jù)點(diǎn)位于二維空間內(nèi)，如下圖所示棺滞。為了能有效的找到最近鄰裁蚁，k-d樹(shù)采用分而治之的思想，即將整個(gè)空間劃分為幾個(gè)小部分检眯，首先厘擂，粗黑線將空間一分為二，然后在兩個(gè)子空間中锰瘸，細(xì)黑直線又將整個(gè)空間劃分為四部分刽严，最后虛黑直線將這四部分進(jìn)一步劃分。

image

6個(gè)二維數(shù)據(jù)點(diǎn){(2,3)避凝，(5,4)舞萄，(9,6)，(4,7)管削，(8,1)倒脓，(7,2)}構(gòu)建kd樹(shù)的具體步驟為：

  1. 確定：split域=x。具體是：6個(gè)數(shù)據(jù)點(diǎn)在x含思，y維度上的數(shù)據(jù)方差分別為39崎弃，28.63，所以在x軸上方差更大含潘，故split域值為x饲做；
  2. 確定：Node-data = （7,2）。具體是：根據(jù)x維上的值將數(shù)據(jù)排序遏弱，6個(gè)數(shù)據(jù)的中值(所謂中值盆均，即中間大小的值)為7，所以Node-data域位數(shù)據(jù)點(diǎn)（7,2）漱逸。這樣泪姨，該節(jié)點(diǎn)的分割超平面就是通過(guò)（7,2）并垂直于：split=x軸的直線x=7游沿；
  3. 確定：左子空間和右子空間。具體是：分割超平面x=7將整個(gè)空間分為兩部分：x<=7的部分為左子空間肮砾，包含3個(gè)節(jié)點(diǎn)={(2,3),(5,4),(4,7)}诀黍；另一部分為右子空間，包含2個(gè)節(jié)點(diǎn)={(9,6)唇敞，(8,1)}蔗草；
  4. 如上算法所述，kd樹(shù)的構(gòu)建是一個(gè)遞歸過(guò)程疆柔，我們對(duì)左子空間和右子空間內(nèi)的數(shù)據(jù)重復(fù)根節(jié)點(diǎn)的過(guò)程就可以得到一級(jí)子節(jié)點(diǎn)（5,4）和（9,6）咒精，同時(shí)將空間和數(shù)據(jù)集進(jìn)一步細(xì)分，如此往復(fù)直到空間中只包含一個(gè)數(shù)據(jù)點(diǎn)旷档。

與此同時(shí)模叙，經(jīng)過(guò)對(duì)上面所示的空間劃分之后，我們可以看出鞋屈，點(diǎn)(7,2)可以為根結(jié)點(diǎn)范咨，從根結(jié)點(diǎn)出發(fā)的兩條紅粗斜線指向的(5,4)和(9,6)則為根結(jié)點(diǎn)的左右子結(jié)點(diǎn)，而(2,3)厂庇，(4,7)則為(5,4)的左右孩子(通過(guò)兩條細(xì)紅斜線相連)渠啊，最后，(8,1)為(9,6)的左孩子(通過(guò)細(xì)紅斜線相連)权旷。如此替蛉，便形成了下面這樣一棵k-d樹(shù)：

image

對(duì)于n個(gè)實(shí)例的k維數(shù)據(jù)來(lái)說(shuō)，建立kd-tree的時(shí)間復(fù)雜度為O(knlogn)拄氯。**

k-d樹(shù)算法可以分為兩大部分躲查，除了上部分有關(guān)k-d樹(shù)本身這種數(shù)據(jù)結(jié)構(gòu)建立的算法，另一部分是在建立的k-d樹(shù)上各種諸如插入译柏，刪除镣煮，查找(最鄰近查找)等操作涉及的算法。下面鄙麦，咱們依次來(lái)看kd樹(shù)的插入典唇、刪除、查找操作胯府。

2.2 KD樹(shù)的插入

元素插入到一個(gè)K-D樹(shù)的方法和二叉檢索樹(shù)類似介衔。本質(zhì)上，在偶數(shù)層比較x坐標(biāo)值盟劫，而在奇數(shù)層比較y坐標(biāo)值夜牡。當(dāng)我們到達(dá)了樹(shù)的底部与纽，（也就是當(dāng)一個(gè)空指針出現(xiàn)）侣签，我們也就找到了結(jié)點(diǎn)將要插入的位置塘装。生成的K-D樹(shù)的形狀依賴于結(jié)點(diǎn)插入時(shí)的順序。給定N個(gè)點(diǎn)影所，其中一個(gè)結(jié)點(diǎn)插入和檢索的平均代價(jià)是O(log2N)蹦肴。

插入的過(guò)程如下:

image

應(yīng)該清楚，這里描述的插入過(guò)程中猴娩，每個(gè)結(jié)點(diǎn)將其所在的平面分割成兩部分阴幌。因比，Chicago 將平面上所有結(jié)點(diǎn)分成兩部分卷中，一部分所有的結(jié)點(diǎn)x坐標(biāo)值小于35矛双，另一部分結(jié)點(diǎn)的x坐標(biāo)值大于或等于35。同樣Mobile將所有x坐標(biāo)值大于35的結(jié)點(diǎn)以分成兩部分蟆豫，一部分結(jié)點(diǎn)的Y坐標(biāo)值是小于10议忽，另一部分結(jié)點(diǎn)的Y坐標(biāo)值大于或等于10。后面的Toronto十减、Buffalo也按照一分為二的規(guī)則繼續(xù)劃分栈幸。

2.3 KD樹(shù)的刪除

KD樹(shù)的刪除可以用遞歸程序來(lái)實(shí)現(xiàn)。我們假設(shè)希望從K-D樹(shù)中刪除結(jié)點(diǎn)（a,b）帮辟。如果（a,b）的兩個(gè)子樹(shù)都為空速址，則用空樹(shù)來(lái)代替（a,b）胯努。否則奶甘，在（a,b）的子樹(shù)中尋找一個(gè)合適的結(jié)點(diǎn)來(lái)代替它，譬如(c,d)僻弹，則遞歸地從K-D樹(shù)中刪除（c,d）荔棉。一旦(c,d)已經(jīng)被刪除闹炉，則用（c,d）代替（a,b）。假設(shè)(a,b)是一個(gè)X識(shí)別器润樱，那么渣触，它得替代節(jié)點(diǎn)要么是（a,b）左子樹(shù)中的X坐標(biāo)最大值的結(jié)點(diǎn)，要么是（a,b）右子樹(shù)中x坐標(biāo)最小值的結(jié)點(diǎn)壹若。

下面來(lái)舉一個(gè)實(shí)際的例子(來(lái)源：中國(guó)地質(zhì)大學(xué)電子課件嗅钻，原課件錯(cuò)誤已經(jīng)在下文中訂正)，如下圖所示店展，原始圖像及對(duì)應(yīng)的kd樹(shù)养篓，現(xiàn)在要?jiǎng)h除圖中的A結(jié)點(diǎn)，請(qǐng)看一系列刪除步驟：

image

要?jiǎng)h除上圖中結(jié)點(diǎn)A赂蕴，選擇結(jié)點(diǎn)A的右子樹(shù)中X坐標(biāo)值最小的結(jié)點(diǎn)柳弄，這里是C，C成為根，如下圖：

image

從C的右子樹(shù)中找出一個(gè)結(jié)點(diǎn)代替先前C的位置碧注，

image

這里是D嚣伐，并將D的左子樹(shù)轉(zhuǎn)為它的右子樹(shù)，D代替先前C的位置萍丐，如下圖：

image

在D的新右子樹(shù)中轩端，找X坐標(biāo)最小的結(jié)點(diǎn)，這里為H逝变，H代替D的位置基茵，

image

在D的右子樹(shù)中找到一個(gè)Y坐標(biāo)最小的值，這里是I壳影，將I代替原先H的位置拱层，從而A結(jié)點(diǎn)從圖中順利刪除，如下圖所示：

image

從K-D樹(shù)中刪除一個(gè)結(jié)點(diǎn)是代價(jià)很高的宴咧，很清楚刪除子樹(shù)的根受到子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的限制舱呻。用TPL（T）表示樹(shù)T總的路徑長(zhǎng)度∮破可看出樹(shù)中子樹(shù)大小的總和為TPL（T）+N箱吕。 以隨機(jī)方式插入N個(gè)點(diǎn)形成樹(shù)的TPL是O(N*log2N),這就意味著從一個(gè)隨機(jī)形成的K-D樹(shù)中刪除一個(gè)隨機(jī)選取的結(jié)點(diǎn)平均代價(jià)的上界是O(log2N) 。

2.4 KD樹(shù)的最近鄰搜索算法

k-d樹(shù)查詢算法的偽代碼如下所示：

image

我寫了一個(gè)遞歸版本的二維kd tree的搜索函數(shù)你對(duì)比的看看：

image

舉例

星號(hào)表示要查詢的點(diǎn)查詢點(diǎn)（2柿冲，4.5）茬高。通過(guò)二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點(diǎn)假抄。而找到的葉子節(jié)點(diǎn)并不一定就是最鄰近的怎栽，最鄰近肯定距離查詢點(diǎn)更近，應(yīng)該位于以查詢點(diǎn)為圓心且通過(guò)葉子節(jié)點(diǎn)的圓域內(nèi)宿饱。為了找到真正的最近鄰熏瞄，還需要進(jìn)行相關(guān)的‘回溯'操作。也就是說(shuō)谬以，算法首先沿搜索路徑反向查找是否有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)强饮。

  1. 二叉樹(shù)搜索：先從（7,2）查找到（5,4）節(jié)點(diǎn)，在進(jìn)行查找時(shí)是由y = 4為分割超平面的为黎，由于查找點(diǎn)為y值為4.5邮丰，因此進(jìn)入右子空間查找到（4,7），形成搜索路徑<(7,2)铭乾，(5,4)剪廉，(4,7)>，但（4,7）與目標(biāo)查找點(diǎn)的距離為3.202炕檩，而（5,4）與查找點(diǎn)之間的距離為3.041斗蒋，所以（5,4）為查詢點(diǎn)的最近點(diǎn)；
  2. 回溯查找：以（2，4.5）為圓心泉沾，以3.041為半徑作圓骤星，如下圖所示”疲可見(jiàn)該圓和y = 4超平面交割，所以需要進(jìn)入（5,4）左子空間進(jìn)行查找舆吮，也就是將（2,3）節(jié)點(diǎn)加入搜索路徑中得<(7,2)揭朝，(2,3)>；于是接著搜索至（2,3）葉子節(jié)點(diǎn)色冀，（2,3）距離（2,4.5）比（5,4）要近潭袱，所以最近鄰點(diǎn)更新為（2，3）锋恬，最近距離更新為1.5屯换；
  3. 回溯查找至（5,4），直到最后回溯到根結(jié)點(diǎn)（7,2）的時(shí)候与学，以（2,4.5）為圓心1.5為半徑作圓彤悔，并不和x = 7分割超平面交割，如下圖所示索守。至此晕窑，搜索路徑回溯完，返回最近鄰點(diǎn)（2,3）卵佛，最近距離1.5杨赤。
image
image

2.5 kd樹(shù)近鄰搜索算法的改進(jìn)：BBF算法

實(shí)例點(diǎn)是隨機(jī)分布的，那么kd樹(shù)搜索的平均計(jì)算復(fù)雜度是O（logN）截汪，這里的N是訓(xùn)練實(shí)例樹(shù)疾牲。所以說(shuō)，kd樹(shù)更適用于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時(shí)的k近鄰搜索衙解，當(dāng)空間維數(shù)接近訓(xùn)練實(shí)例數(shù)時(shí)阳柔，它的效率會(huì)迅速下降，一降降到“解放前”：線性掃描的速度蚓峦。

也正因?yàn)樯鲜鰇最近鄰搜索算法的第4個(gè)步驟中的所述：“回退到根結(jié)點(diǎn)時(shí)盔沫，搜索結(jié)束”，每個(gè)最近鄰點(diǎn)的查詢比較完成過(guò)程最終都要回退到根結(jié)點(diǎn)而結(jié)束枫匾，而導(dǎo)致了許多不必要回溯訪問(wèn)和比較到的結(jié)點(diǎn)架诞，這些多余的損耗在高維度數(shù)據(jù)查找的時(shí)候，搜索效率將變得相當(dāng)之地下干茉，那有什么辦法可以改進(jìn)這個(gè)原始的kd樹(shù)最近鄰搜索算法呢谴忧？

從上述標(biāo)準(zhǔn)的kd樹(shù)查詢過(guò)程可以看出其搜索過(guò)程中的“回溯”是由“查詢路徑”決定的，并沒(méi)有考慮查詢路徑上一些數(shù)據(jù)點(diǎn)本身的一些性質(zhì)。一個(gè)簡(jiǎn)單的改進(jìn)思路就是將“查詢路徑”上的結(jié)點(diǎn)進(jìn)行排序沾谓，如按各自分割超平面（也稱bin）與查詢點(diǎn)的距離排序委造，也就是說(shuō)，回溯檢查總是從優(yōu)先級(jí)最高（Best Bin）的樹(shù)結(jié)點(diǎn)開(kāi)始均驶。

還是以上面的查詢（2,4.5）為例昏兆，搜索的算法流程為：

  1. 將（7,2）壓人優(yōu)先隊(duì)列中；
  2. 提取優(yōu)先隊(duì)列中的（7,2）妇穴，由于（2,4.5）位于（7,2）分割超平面的左側(cè)爬虱，所以檢索其左子結(jié)點(diǎn)（5,4）。
  3. 同時(shí)腾它，根據(jù)BBF機(jī)制”搜索左/右子樹(shù)跑筝，就把對(duì)應(yīng)這一層的兄弟結(jié)點(diǎn)即右/左結(jié)點(diǎn)存進(jìn)隊(duì)列”，將其（5,4）對(duì)應(yīng)的兄弟結(jié)點(diǎn)即右子結(jié)點(diǎn)（9,6）壓人優(yōu)先隊(duì)列中
  4. 此時(shí)優(yōu)先隊(duì)列為{（9,6）}瞒滴，最佳點(diǎn)為（7,2）曲梗；然后一直檢索到葉子結(jié)點(diǎn)（4,7），此時(shí)優(yōu)先隊(duì)列為{（2,3）妓忍，（9,6）}虏两，“最佳點(diǎn)”則為（5,4）；
  5. 提取優(yōu)先級(jí)最高的結(jié)點(diǎn)（2,3）世剖，重復(fù)步驟2碘举，直到優(yōu)先隊(duì)列為空。
image

2.6 KD樹(shù)的應(yīng)用

SIFT+KD_BBF搜索算法搁廓，詳細(xì)參考文末的參考文獻(xiàn)引颈。

3. 關(guān)于KNN的一些問(wèn)題

  1. 在k-means或kNN，我們是用歐氏距離來(lái)計(jì)算最近的鄰居之間的距離境蜕。為什么不用曼哈頓距離蝙场？

    答：我們不用曼哈頓距離，因?yàn)樗挥?jì)算水平或垂直距離粱年，有維度的限制售滤。另一方面，歐式距離可用于任何空間的距離計(jì)算問(wèn)題台诗。因?yàn)橥曷幔瑪?shù)據(jù)點(diǎn)可以存在于任何空間，歐氏距離是更可行的選擇拉队。例如：想象一下國(guó)際象棋棋盤弊知，象或車所做的移動(dòng)是由曼哈頓距離計(jì)算的，因?yàn)樗鼈兪窃诟髯缘乃胶痛怪狈较虻倪\(yùn)動(dòng)粱快。

  2. KD-Tree相比KNN來(lái)進(jìn)行快速圖像特征比對(duì)的好處在哪里?

    答：極大的節(jié)約了時(shí)間成本．點(diǎn)線距離如果 >　最小點(diǎn)秩彤，無(wú)需回溯上一層叔扼，如果<,則再上一層尋找。

4. 參考文獻(xiàn)

從K近鄰算法漫雷、距離度量談到KD樹(shù)瓜富、SIFT+BBF算法

5. 手寫數(shù)字識(shí)別案例

KNN手寫數(shù)字識(shí)別系統(tǒng)

【機(jī)器學(xué)習(xí)通俗易懂系列文章】

3.png

作者：@mantchs

GitHub：https://github.com/NLP-LOVE/ML-NLP

歡迎大家加入討論！共同完善此項(xiàng)目降盹！群號(hào)：【541954936】點(diǎn)擊加入

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末与柑，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子蓄坏，更是在濱河造成了極大的恐慌价捧，老刑警劉巖，帶你破解...
    沈念sama閱讀 206,378評(píng)論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件剑辫，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡渠欺，警方通過(guò)查閱死者的電腦和手機(jī)妹蔽，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,356評(píng)論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)挠将，“玉大人胳岂，你說(shuō)我怎么就攤上這事√蛳。” “怎么了乳丰？”我有些...
    開(kāi)封第一講書人閱讀 152,702評(píng)論 0贊 342
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)内贮。 經(jīng)常有香客問(wèn)我产园，道長(zhǎng)，這世上最難降的妖魔是什么夜郁？ 我笑而不...
    開(kāi)封第一講書人閱讀 55,259評(píng)論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任什燕，我火速辦了婚禮，結(jié)果婚禮上竞端，老公的妹妹穿的比我還像新娘屎即。我一直安慰自己，他們只是感情好事富，可當(dāng)我...
    茶點(diǎn)故事閱讀 64,263評(píng)論 5贊 371
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布技俐。 她就那樣靜靜地躺著，像睡著了一般统台。 火紅的嫁衣襯著肌膚如雪雕擂。 梳的紋絲不亂的頭發(fā)上，一...
    開(kāi)封第一講書人閱讀 49,036評(píng)論 1贊 285
  • 城市分裂傳說(shuō)
    那天贱勃，我揣著相機(jī)與錄音捂刺，去河邊找鬼谣拣。 笑死，一個(gè)胖子當(dāng)著我的面吹牛族展，可吹牛的內(nèi)容都是我干的森缠。 我是一名探鬼主播，決...
    沈念sama閱讀 38,349評(píng)論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼仪缸，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼贵涵！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起恰画，我...
    開(kāi)封第一講書人閱讀 36,979評(píng)論 0贊 259
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤宾茂，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后拴还，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體跨晴，經(jīng)...
    沈念sama閱讀 43,469評(píng)論 1贊 300
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,938評(píng)論 2贊 323
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年片林，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了端盆。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,059評(píng)論 1贊 333
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡费封，死狀恐怖焕妙，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情弓摘，我是刑警寧澤焚鹊，帶...
    沈念sama閱讀 33,703評(píng)論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站韧献，受9級(jí)特大地震影響末患，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜锤窑，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,257評(píng)論 3贊 307
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一阻塑、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧果复，春花似錦陈莽、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 30,262評(píng)論 0贊 19
  • 一樁弒父案走搁，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至迈窟，卻和暖如春私植，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背车酣。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 31,485評(píng)論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工曲稼， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留索绪，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 45,501評(píng)論 2贊 354
  • 代替公主和親
    正文 我出身青樓贫悄，卻偏偏與公主長(zhǎng)得像瑞驱，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子窄坦，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,792評(píng)論 2贊 345

推薦閱讀更多精彩內(nèi)容

  • k-近鄰算法（kNN）：采用測(cè)量不同特征值之間的距離方法進(jìn)行分類 優(yōu)點(diǎn)：簡(jiǎn)單好用唤反，容易理解，精度高鸭津，理論成熟彤侍，既可...
    山霧幻華閱讀 663評(píng)論 0贊 2
  • K-近鄰算法采用測(cè)量不同特征值之間的距離方法進(jìn)行分類盏阶。 kNN近鄰分類算法的原理(來(lái)源網(wǎng)絡(luò)): 從上圖...
    蠟筆小虎_007閱讀 770評(píng)論 1贊 1
  • 一.樸素貝葉斯 1.分類理論 樸素貝葉斯是一種基于貝葉斯定理和特征條件獨(dú)立性假設(shè)的多分類的機(jī)器學(xué)習(xí)方法，所...
    wlj1107閱讀 3,072評(píng)論 0贊 5
  • k 近鄰法 k 近鄰算法 k 近鄰模型 k 近鄰法的實(shí)現(xiàn)：kd 樹(shù) 搜索 kd 樹(shù) k 近鄰模型實(shí)現(xiàn) k 近鄰模型...
    千與千與閱讀 561評(píng)論 0贊 3
  • 騎天大勝焦點(diǎn)少年班堅(jiān)持分享第187天 星期日闻书。2018.1.28 田啟瑞 我們今天結(jié)束了緊張的復(fù)習(xí)名斟，老師現(xiàn)在讓自...
    騎天大勝閱讀 107評(píng)論 0贊 0