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

1、從K近鄰算法、距離度量談到KD樹(shù)、SIFT+BBF算法    本文各部分內(nèi)容分布如下：1. 第一部分講K近鄰算法，其中重點(diǎn)闡述了相關(guān)的距離度量表示法，2. 第二部分著重講K近鄰算法的實(shí)現(xiàn)-KD樹(shù)，和KD樹(shù)的插入，刪除，最近鄰查找等操作，及KD樹(shù)的一系列相關(guān)改進(jìn)(包括BBF，M樹(shù)等)；3. 第三部分講KD樹(shù)的應(yīng)用：SIFT+kd_BBF搜索算法。    同時(shí)，你將看到，K近鄰算法同本系列的前兩篇文章所講的決策樹(shù)分類貝葉斯分類，及支持向量機(jī)SVM一樣，也是用于解決分類問(wèn)題的算法，      而本數(shù)據(jù)挖掘十大算法系列也會(huì)

2、按照分類，聚類，關(guān)聯(lián)分析，預(yù)測(cè)回歸等問(wèn)題依次展開(kāi)闡述。    OK，行文倉(cāng)促，本文若有任何漏洞，問(wèn)題或者錯(cuò)誤，歡迎朋友們隨時(shí)不吝指正，各位的批評(píng)也是我繼續(xù)寫下去的動(dòng)力之一。感謝。第一部分、K近鄰算法1.1、什么是K近鄰算法    何謂K近鄰算法，即K-Nearest Neighbor algorithm，簡(jiǎn)稱KNN算法，單從名字來(lái)猜想，可以簡(jiǎn)單粗暴的認(rèn)為是：K個(gè)最近的鄰居，當(dāng)K=1時(shí)，算法便成了最近鄰算法，即尋找最近的那個(gè)鄰居。為何要找鄰居？打個(gè)比方來(lái)說(shuō)，假設(shè)你來(lái)到一個(gè)陌生的村莊，現(xiàn)在你要找到與你有著相似特征的人群融入他們，所謂入伙。 

3、60; 用官方的話來(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è)類中。根據(jù)這個(gè)說(shuō)法，咱們來(lái)看下引自維基百科上的一幅圖：    如上圖所示，有兩類不同的樣本數(shù)據(jù)，分別用藍(lán)色的小正方形和紅色的小三角形表示，而圖正中間的那個(gè)綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類的數(shù)據(jù)。也就是說(shuō)，現(xiàn)在，我們不知道中間那個(gè)綠色的數(shù)據(jù)是從屬于哪一類（藍(lán)色小正方形or紅色小三角形），下面，我們就要解決這個(gè)問(wèn)題：給這個(gè)綠色的圓分類。    我們常說(shuō)，物以類

4、聚，人以群分，判別一個(gè)人是一個(gè)什么樣品質(zhì)特征的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識(shí)其人。我們不是要判別上圖中那個(gè)綠色的圓是屬于哪一類數(shù)據(jù)么，好說(shuō)，從它的鄰居下手。但一次性看多少個(gè)鄰居呢？從上圖中，你還能看到：· 如果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ú)

5、法判定當(dāng)前待分類點(diǎn)是從屬于已知分類中的哪一類時(shí)，我們可以依據(jù)統(tǒng)計(jì)學(xué)的理論看它所處的位置特征，衡量它周圍鄰居的權(quán)重，而把它歸為(或分配)到權(quán)重更大的那一類。這就是K近鄰算法的核心思想。1.2、近鄰的距離度量表示法    上文第一節(jié)，我們看到，K近鄰算法的核心在于找到實(shí)例點(diǎn)的鄰居，這個(gè)時(shí)候，問(wèn)題就接踵而至了，如何找到鄰居，鄰居的判定標(biāo)準(zhǔn)是什么，用什么來(lái)度量。這一系列問(wèn)題便是下面要講的距離度量表示法。但有的讀者可能就有疑問(wèn)了，我是要找鄰居，找相似性，怎么又跟距離扯上關(guān)系了？    這是因?yàn)樘卣骺臻g中兩個(gè)實(shí)例點(diǎn)的距離和反應(yīng)出兩個(gè)實(shí)例點(diǎn)之間的相似性程度。K近鄰模型

6、的特征空間一般是n維實(shí)數(shù)向量空間，使用的距離可以使歐式距離，也是可以是其它距離，既然扯到了距離，下面就來(lái)具體闡述下都有哪些距離度量的表示法，權(quán)當(dāng)擴(kuò)展。· 1. 歐氏距離，最常見(jiàn)的兩點(diǎn)之間或多點(diǎn)之間的距離表示法，又稱之為歐幾里得度量，它定義于歐幾里得空間中，如點(diǎn) x = (x1,.,xn) 和 y = (y1,.,yn) 之間的距離為：(1)二維平面上兩點(diǎn)a(x1,y1)與b(x2,y2)間的歐氏距離：(2)三維空間兩點(diǎn)a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：(3)兩個(gè)n維向量a(x11,x12,x1n)與 b(x21,x22,x2n)間的歐氏距離：也可以用表示成向

7、量運(yùn)算的形式：其上，二維平面上兩點(diǎn)歐式距離，代碼可以如下編寫：1. /unixfy：計(jì)算歐氏距離  2. double euclideanDistance(const vector<double>& v1, const vector<double>& v2)  3.   4.      assert(v1.size() = v2.size();  

8、5.      double ret = 0.0;  6.      for (vector<double>:size_type i = 0; i != v1.size(); +i)  7.        8.     

9、0;    ret += (v1i - v2i) * (v1i - v2i);  9.        10.      return sqrt(ret);  11.    · 2. 曼哈頓距離，我們可以定義曼哈頓距離的正式意義為L(zhǎng)1-距離或城市區(qū)塊距離，也就是在歐幾里得

10、空間的固定直角坐標(biāo)系上兩點(diǎn)所形成的線段對(duì)軸產(chǎn)生的投影的距離總和。例如在平面上，坐標(biāo)（x1, y1）的點(diǎn)P1與坐標(biāo)（x2, y2）的點(diǎn)P2的曼哈頓距離為：，要注意的是，曼哈頓距離依賴座標(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)。(1)二維平面

11、兩點(diǎn)a(x1,y1)與b(x2,y2)間的曼哈頓距離 (2)兩個(gè)n維向量a(x11,x12,x1n)與 b(x21,x22,x2n)間的曼哈頓距離                           · 3. 切比雪夫距離，若二個(gè)向量或二個(gè)點(diǎn)p 、and q，其座標(biāo)分別為及，則兩者之間的切比雪夫距離定義如下：，    這也等于以下Lp度量的極值：，因此切比雪夫距離也稱為L(zhǎng)度量。

12、    以數(shù)學(xué)的觀點(diǎn)來(lái)看，切比雪夫距離是由一致范數(shù)（uniform norm）（或稱為上確界范數(shù)）所衍生的度量，也是超凸度量（injective metric space）的一種。    在平面幾何中，若二點(diǎn)p及q的直角坐標(biāo)系坐標(biāo)為及，則切比雪夫距離為：。    玩過(guò)國(guó)際象棋的朋友或許知道，國(guó)王走一步能夠移動(dòng)到相鄰的8個(gè)方格中的任意一個(gè)。那么國(guó)王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？。你會(huì)發(fā)現(xiàn)最少步數(shù)總是max( | x2-x1 | , 

13、;| y2-y1 | ) 步 。有一種類似的一種距離度量方法叫切比雪夫距離。(1)二維平面兩點(diǎn)a(x1,y1)與b(x2,y2)間的切比雪夫距離 (2)兩個(gè)n維向量a(x11,x12,x1n)與 b(x21,x22,x2n)間的切比雪夫距離 這個(gè)公式的另一種等價(jià)形式是 · 4. 閔可夫斯基距離(Minkowski Distance)，閔氏距離不是一種距離，而是一組距離的定義。(1) 閔氏距離的定義      

14、; 兩個(gè)n維變量a(x11,x12,x1n)與 b(x21,x22,x2n)間的閔可夫斯基距離定義為： 其中p是一個(gè)變參數(shù)。當(dāng)p=1時(shí)，就是曼哈頓距離當(dāng)p=2時(shí)，就是歐氏距離當(dāng)p時(shí)，就是切比雪夫距離       根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離。 · 5. 標(biāo)準(zhǔn)化歐氏距離 (Standardized Euclidean distance )，標(biāo)準(zhǔn)化歐氏距離是針對(duì)簡(jiǎn)單歐氏距離的缺點(diǎn)而作的一種改進(jìn)方案。標(biāo)準(zhǔn)歐氏距離的思

15、路：既然數(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)用公式描述就是：標(biāo)準(zhǔn)化后的值 =  ( 標(biāo)準(zhǔn)化前的值   分量的均值 ) /分量的標(biāo)準(zhǔn)差經(jīng)過(guò)簡(jiǎn)單的推導(dǎo)就可以得到兩個(gè)n維

16、向量a(x11,x12,x1n)與 b(x21,x22,x2n)間的標(biāo)準(zhǔn)化歐氏距離的公式：如果將方差的倒數(shù)看成是一個(gè)權(quán)重，這個(gè)公式可以看成是一種加權(quán)歐氏距離(Weighted Euclidean distance)。 · 6. 馬氏距離(Mahalanobis Distance)（1）馬氏距離定義       有M個(gè)樣本向量X1Xm，協(xié)方差矩陣記為S，均值記為向量，則其中樣本向量X到u的馬氏距離表示為： （協(xié)方差矩陣中每個(gè)元素是各個(gè)矢量元素之間的協(xié)方差Cov(X,Y)，Cov

17、(X,Y) = E X-E(X) Y-E(Y)，其中E為數(shù)學(xué)期望）而其中向量Xi與Xj之間的馬氏距離定義為：    若協(xié)方差矩陣是單位矩陣（各個(gè)樣本向量之間獨(dú)立同分布）,則公式就成了：       也就是歐氏距離了。若協(xié)方差矩陣是對(duì)角矩陣，公式變成了標(biāo)準(zhǔn)化歐氏距離。(2)馬氏距離的優(yōu)缺點(diǎn)：量綱無(wú)關(guān)，排除變量之間的相關(guān)性的干擾。 微博上的seafood高清版點(diǎn)評(píng)道：原來(lái)馬氏距離是根據(jù)協(xié)方差矩陣演變，一直被老師誤導(dǎo)了，怪不得看Killian在05年NIPS發(fā)表的LMNN論文時(shí)候老是看到協(xié)方差矩陣和半正定，原來(lái)

18、是這回事· 7、巴氏距離（Bhattacharyya Distance），在統(tǒng)計(jì)中，Bhattacharyya距離測(cè)量?jī)蓚€(gè)離散或連續(xù)概率分布的相似性。它與衡量?jī)蓚€(gè)統(tǒng)計(jì)樣品或種群之間的重疊量的Bhattacharyya系數(shù)密切相關(guān)。Bhattacharyya距離和Bhattacharyya系數(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è)量中的類分類的可分離性。（1）巴氏距離的定義對(duì)于離散概率分布 p和q在同一域 X，它被定義為

19、：其中：是Bhattacharyya系數(shù)。對(duì)于連續(xù)概率分布，Bhattacharyya系數(shù)被定義為：在這兩種情況下，巴氏距離并沒(méi)有服從三角不等式.（值得一提的是，Hellinger距離不服從三角不等式）。 對(duì)于多變量的高斯分布 ，和是手段和協(xié)方差的分布。需要注意的是，在這種情況下，第一項(xiàng)中的Bhattacharyya距離與馬氏距離有關(guān)聯(lián)。 （2）Bhattacharyya系數(shù)Bhattacharyya系數(shù)是兩個(gè)統(tǒng)計(jì)樣本之間的重疊量的近似測(cè)量，可以被用于確定被考慮的兩個(gè)樣本的相對(duì)接近。計(jì)算Bhattacharyya系數(shù)涉及集成的基本形式的兩個(gè)樣本的重疊的時(shí)間間隔的值

20、的兩個(gè)樣本被分裂成一個(gè)選定的分區(qū)數(shù)，并且在每個(gè)分區(qū)中的每個(gè)樣品的成員的數(shù)量，在下面的公式中使用考慮樣品a 和 b ，n是的分區(qū)數(shù)，并且，被一個(gè) 和 b i的日分區(qū)中的樣本數(shù)量的成員。更多介紹請(qǐng)參看：/wiki/Bhattacharyya_coefficient。· 8. 漢明距離(Hamming distance)， 兩個(gè)等長(zhǎng)字符串s1與s2之間的漢明距離定義為將其中一個(gè)變?yōu)榱硗庖粋€(gè)所需要作的最小替換次數(shù)。例如字符串“1111”與“1001”之間的漢明距離為2。應(yīng)用：信息編碼（為了

21、增強(qiáng)容錯(cuò)性，應(yīng)使得編碼間的最小漢明距離盡可能大）?；蛟S，你還沒(méi)明白我再說(shuō)什么，不急，看下上篇blog中第78題的第3小題整理的一道面試題目，便一目了然了。如下圖所示：1. /動(dòng)態(tài)規(guī)劃：    2.     3. /fi,j表示s0.i與t0.j的最小編輯距離。    4. fi,j = min  fi-1,j+1,  fi,j-1+1,  fi-1,j-1+(si=tj?0:1) 

22、60;   5.     6. /分別表示：添加1個(gè)，刪除1個(gè)，替換1個(gè)（相同就不用替換）。       與此同時(shí)，面試官還可以繼續(xù)問(wèn)下去：那么，請(qǐng)問(wèn)，如何設(shè)計(jì)一個(gè)比較兩篇文章相似性的算法？（這個(gè)問(wèn)題的討論可以看看這里：（上篇blog中第78題的第3小題給出了多種方法，讀者可以參看之。同時(shí)，程序員編程藝術(shù)系列第二十八章將詳細(xì)闡述這個(gè)問(wèn)題）· 9. 夾角余弦(Cosine) ，幾何中夾角余弦可用來(lái)衡量?jī)蓚€(gè)向量方向的差異，機(jī)器學(xué)習(xí)中借用這一概念來(lái)衡量

23、樣本向量之間的差異。(1)在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：(2) 兩個(gè)n維樣本點(diǎn)a(x11,x12,x1n)和b(x21,x22,x2n)的夾角余弦       類似的，對(duì)于兩個(gè)n維樣本點(diǎn)a(x11,x12,x1n)和b(x21,x22,x2n)，可以使用類似于夾角余弦的概念來(lái)衡量它們間的相似程度，即：       夾角余弦取值范圍為-1,1。夾角余弦越大表示兩個(gè)向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當(dāng)兩個(gè)向量的方向重合時(shí)夾角余弦取最大值1，當(dāng)兩

24、個(gè)向量的方向完全相反夾角余弦取最小值-1。 · 10. 杰卡德相似系數(shù)(Jaccard similarity coefficient)(1) 杰卡德相似系數(shù)       兩個(gè)集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個(gè)集合的杰卡德相似系數(shù)，用符號(hào)J(A,B)表示。杰卡德相似系數(shù)是衡量?jī)蓚€(gè)集合的相似度一種指標(biāo)。(2) 杰卡德距離       與杰卡德相似系數(shù)相反的概念是杰卡德距

25、離(Jaccard distance)。杰卡德距離可用如下公式表示：杰卡德距離用兩個(gè)集合中不同元素占所有元素的比例來(lái)衡量?jī)蓚€(gè)集合的區(qū)分度。(3) 杰卡德相似系數(shù)與杰卡德距離的應(yīng)用      可將杰卡德相似系數(shù)用在衡量樣本的相似度上。舉例：樣本A與樣本B是兩個(gè)n維向量，而且所有維度的取值都是0或1，例如：A(0111)和B(1011)。我們將樣本看成是一個(gè)集合，1表示集合包含該元素，0表示集合不包含該元素。M11 ：樣本A與B都是1的維度的個(gè)數(shù)M01：樣本A是0，樣本B是1的維度的個(gè)數(shù)M10：樣本A是1，樣

26、本B是0 的維度的個(gè)數(shù)M00：樣本A與B都是0的維度的個(gè)數(shù)依據(jù)上文給的杰卡德相似系數(shù)及杰卡德距離的相關(guān)定義，樣本A與B的杰卡德相似系數(shù)J可以表示為：這里M11+M01+M10可理解為A與B的并集的元素個(gè)數(shù)，而M11是A與B的交集的元素個(gè)數(shù)。而樣本A與B的杰卡德距離表示為J'：· 11.皮爾遜系數(shù)(Pearson Correlation Coefficient)    在具體闡述皮爾遜相關(guān)系數(shù)之前，有必要解釋下什么是相關(guān)系數(shù) ( Correlation coefficient )與相關(guān)距離(Correlation distance)。   

27、; 相關(guān)系數(shù) ( Correlation coefficient )的定義是：(其中，E為數(shù)學(xué)期望或均值，D為方差，D開(kāi)根號(hào)為標(biāo)準(zhǔn)差，E X-E(X) Y-E(Y)稱為隨機(jī)變量X與Y的協(xié)方差，記為Cov(X,Y)，即Cov(X,Y) = E X-E(X) Y-E(Y)，而兩個(gè)變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商則稱為隨機(jī)變量X與Y的相關(guān)系數(shù)，記為)   相關(guān)系數(shù)衡量隨機(jī)變量X與Y相關(guān)程度的一種方法，相關(guān)系數(shù)的取值范圍是-1,1。相關(guān)系數(shù)的絕對(duì)值越大，則表明X與Y相關(guān)度越高。當(dāng)X與Y線性相關(guān)時(shí)，相關(guān)系數(shù)取值為1（正線性相關(guān)）或-1（負(fù)

28、線性相關(guān)）。    具體的，如果有兩個(gè)變量：X、Y，最終計(jì)算出的相關(guān)系數(shù)的含義可以有如下理解：1. 當(dāng)相關(guān)系數(shù)為0時(shí)，X和Y兩變量無(wú)關(guān)系。2. 當(dāng)X的值增大（減?。?，Y值增大（減小），兩個(gè)變量為正相關(guān)，相關(guān)系數(shù)在0.00與1.00之間。3. 當(dāng)X的值增大（減?。琘值減?。ㄔ龃螅?，兩個(gè)變量為負(fù)相關(guān)，相關(guān)系數(shù)在-1.00與0.00之間。   相關(guān)距離的定義是：OK，接下來(lái)，咱們來(lái)重點(diǎn)了解下皮爾遜相關(guān)系數(shù)。    在統(tǒng)計(jì)學(xué)中，皮爾遜積矩相關(guān)系數(shù)（英語(yǔ)：Pearson product-moment correlation coefficie

29、nt，又稱作 PPMCC或PCCs, 用r表示）用于度量?jī)蓚€(gè)變量X和Y之間的相關(guān)（線性相關(guān)），其值介于-1與1之間。通常情況下通過(guò)以下取值范圍判斷變量的相關(guān)強(qiáng)度：相關(guān)系數(shù)     0.8-1.0     極強(qiáng)相關(guān)                 0.6-0.8     強(qiáng)相關(guān)   

30、;              0.4-0.6     中等程度相關(guān)                 0.2-0.4     弱相關(guān)        &#

31、160;        0.0-0.2     極弱相關(guān)或無(wú)相關(guān)在自然科學(xué)領(lǐng)域中，該系數(shù)廣泛用于度量?jī)蓚€(gè)變量之間的相關(guān)程度。它是由卡爾·皮爾遜從弗朗西斯·高爾頓在19世紀(jì)80年代提出的一個(gè)相似卻又稍有不同的想法演變而來(lái)的。這個(gè)相關(guān)系數(shù)也稱作“皮爾森相關(guān)系數(shù)r”。(1)皮爾遜系數(shù)的定義：兩個(gè)變量之間的皮爾遜相關(guān)系數(shù)定義為兩個(gè)變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商：以上方程定義了總體相關(guān)系數(shù), 一般表示成希臘字母(rho)。基于樣本對(duì)協(xié)方差和方差進(jìn)行估計(jì)，可以得到樣本標(biāo)準(zhǔn)差, 一

32、般表示成r：一種等價(jià)表達(dá)式的是表示成標(biāo)準(zhǔn)分的均值?；?Xi, Yi)的樣本點(diǎn)，樣本皮爾遜系數(shù)是               其中、 及 ，分別是標(biāo)準(zhǔn)分、樣本平均值和樣本標(biāo)準(zhǔn)差?；蛟S上面的講解令你頭腦混亂不堪，沒(méi)關(guān)系，我換一種方式講解，如下：假設(shè)有兩個(gè)變量X、Y，那么兩變量間的皮爾遜相關(guān)系數(shù)可通過(guò)以下公式計(jì)算：· 公式一：注：勿忘了上面說(shuō)過(guò)，“皮爾遜相關(guān)系數(shù)定義為兩個(gè)變量之間的協(xié)方差和標(biāo)準(zhǔn)差的商”，其中標(biāo)準(zhǔn)差的計(jì)算公式為：· 公式二：· 公式三：· 公式四

33、：以上列出的四個(gè)公式等價(jià)，其中E是數(shù)學(xué)期望，cov表示協(xié)方差，N表示變量取值的個(gè)數(shù)。(2)皮爾遜相關(guān)系數(shù)的適用范圍當(dāng)兩個(gè)變量的標(biāo)準(zhǔn)差都不為零時(shí)，相關(guān)系數(shù)才有定義，皮爾遜相關(guān)系數(shù)適用于：1. 兩個(gè)變量之間是線性關(guān)系，都是連續(xù)數(shù)據(jù)。2. 兩個(gè)變量的總體是正態(tài)分布，或接近正態(tài)的單峰分布。3. 兩個(gè)變量的觀測(cè)值是成對(duì)的，每對(duì)觀測(cè)值之間相互獨(dú)立。(3)如何理解皮爾遜相關(guān)系數(shù)rubyist：皮爾遜相關(guān)系數(shù)理解有兩個(gè)角度其一, 按照高中數(shù)學(xué)水平來(lái)理解, 它很簡(jiǎn)單, 可以看做將兩組數(shù)據(jù)首先做Z分?jǐn)?shù)處理之后, 然后兩組數(shù)據(jù)的乘積和除以樣本數(shù)，Z分?jǐn)?shù)一般代表正態(tài)分布中, 數(shù)據(jù)偏離中心點(diǎn)的距離.等于變量減掉平均數(shù)再

34、除以標(biāo)準(zhǔn)差.(就是高考的標(biāo)準(zhǔn)分類似的處理)樣本標(biāo)準(zhǔn)差則等于變量減掉平均數(shù)的平方和，再除以樣本數(shù)，最后再開(kāi)方，也就是說(shuō)，方差開(kāi)方即為標(biāo)準(zhǔn)差，樣本標(biāo)準(zhǔn)差計(jì)算公式為：所以, 根據(jù)這個(gè)最樸素的理解,我們可以將公式依次精簡(jiǎn)為:其二, 按照大學(xué)的線性數(shù)學(xué)水平來(lái)理解, 它比較復(fù)雜一點(diǎn),可以看做是兩組數(shù)據(jù)的向量夾角的余弦。下面是關(guān)于此皮爾遜系數(shù)的幾何學(xué)的解釋，先來(lái)看一幅圖，如下所示：回歸直線： y=gx(x) 紅色 和 x=gy(y) 藍(lán)色如上圖，對(duì)于沒(méi)有中心化的數(shù)據(jù), 相關(guān)系數(shù)與兩條可能的回歸線y=gx(x) 和 x=gy(y) 夾角的余弦值一致。對(duì)于沒(méi)有中心化的數(shù)據(jù) (也就是說(shuō), 數(shù)據(jù)移動(dòng)一個(gè)樣本平均值以

35、使其均值為0), 相關(guān)系數(shù)也可以被視作由兩個(gè)隨機(jī)變量 向量 夾角 的 余弦值（見(jiàn)下方）。舉個(gè)例子，例如，有5個(gè)國(guó)家的國(guó)民生產(chǎn)總值分別為 10, 20, 30, 50 和 80 億美元。 假設(shè)這5個(gè)國(guó)家 (順序相同) 的貧困百分比分別為 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分別為包含上述5個(gè)數(shù)據(jù)的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。利用通常的方法計(jì)算兩個(gè)向量之間的夾角  (參見(jiàn) 數(shù)量積), 未中心化 的相關(guān)系數(shù)是:我們發(fā)現(xiàn)以上的數(shù)據(jù)特意選定為完全相關(guān): y =

36、0.10 + 0.01 x。 于是，皮爾遜相關(guān)系數(shù)應(yīng)該等于1。將數(shù)據(jù)中心化 (通過(guò)E(x) = 3.8移動(dòng) x 和通過(guò) E(y) = 0.138 移動(dòng) y ) 得到 x = (2.8, 1.8, 0.8, 1.2, 4.2) 和 y = (0.028, 0.018, 0.008, 0.012, 0.042), 從中(4)皮爾遜相關(guān)的約束條件從以上解釋, 也可以理解皮爾遜相關(guān)的約束條件:· 1 兩個(gè)變量間有線性關(guān)系· 2 變量是連續(xù)變量· 3 變量均符合正態(tài)分布,且二元分布也符合正態(tài)分布· 4 兩變量獨(dú)立在實(shí)踐統(tǒng)計(jì)中,一般只輸出兩個(gè)系數(shù),一個(gè)是相關(guān)系數(shù),也

37、就是計(jì)算出來(lái)的相關(guān)系數(shù)大小,在-1到1之間;另一個(gè)是獨(dú)立樣本檢驗(yàn)系數(shù),用來(lái)檢驗(yà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.2節(jié)如何定義鄰居的問(wèn)題之外，還有一個(gè)選擇多少個(gè)鄰居，即K值定義為多大的問(wèn)題。不要小看了這個(gè)K值選擇問(wèn)題，因?yàn)樗鼘?duì)K近鄰算法

38、的結(jié)果會(huì)產(chǎn)生重大影響。如李航博士的一書(shū)統(tǒng)計(jì)學(xué)習(xí)方法上所說(shuō)：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ú)論輸

39、入實(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值。第二部分、K近鄰算法的實(shí)現(xiàn)：KD樹(shù)2.0、背景    之前blog內(nèi)曾經(jīng)介紹過(guò)SIFT特征匹配算法，特征點(diǎn)匹配和數(shù)據(jù)庫(kù)查、圖像檢索本質(zhì)上是同一個(gè)問(wèn)題，都可以歸結(jié)為一個(gè)通過(guò)距離函數(shù)在高維矢量之間進(jìn)行相似性檢索的問(wèn)題，如何快速而準(zhǔn)確地找到查詢點(diǎn)的近鄰，不少人提出了很多高維空間索引結(jié)構(gòu)和近似查詢的算法。  

40、0; 一般說(shuō)來(lái)，索引結(jié)構(gòu)中相似性查詢有兩種基本的方式：1. 一種是范圍查詢，范圍查詢時(shí)給定查詢點(diǎn)和查詢距離閾值，從數(shù)據(jù)集中查找所有與查詢點(diǎn)距離小于閾值的數(shù)據(jù)2. 另一種是K近鄰查詢，就是給定查詢點(diǎn)及正整數(shù)K，從數(shù)據(jù)集中找到距離查詢點(diǎn)最近的K個(gè)數(shù)據(jù)，當(dāng)K=1時(shí)，它就是最近鄰查詢。    同樣，針對(duì)特征點(diǎn)匹配也有兩種方法：· 最容易的辦法就是線性掃描，也就是我們常說(shuō)的窮舉搜索，依次計(jì)算樣本集E中每個(gè)樣本到輸入實(shí)例點(diǎn)的距離，然后抽取出計(jì)算出來(lái)的最小距離的點(diǎn)即為最近鄰點(diǎn)。此種辦法簡(jiǎn)單直白，但當(dāng)樣本集或訓(xùn)練集很大時(shí)，它的缺點(diǎn)就立馬暴露出來(lái)了，舉個(gè)例子，在物體識(shí)別的問(wèn)題中，可

41、能有數(shù)千個(gè)甚至數(shù)萬(wàn)個(gè)SIFT特征點(diǎn)，而去一一計(jì)算這成千上萬(wàn)的特征點(diǎn)與輸入實(shí)例點(diǎn)的距離，明顯是不足取的。· 另外一種，就是構(gòu)建數(shù)據(jù)索引，因?yàn)閷?shí)際數(shù)據(jù)一般都會(huì)呈現(xiàn)簇狀的聚類形態(tài)，因此我們想到建立數(shù)據(jù)索引，然后再進(jìn)行快速匹配。索引樹(shù)是一種樹(shù)結(jié)構(gòu)索引方法，其基本思想是對(duì)搜索空間進(jìn)行層次劃分。根據(jù)劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒(méi)有重疊，其代表就是k-d樹(shù)；后者劃分空間相互有交疊，其代表為R樹(shù)。    而關(guān)于R樹(shù)本blog內(nèi)之前已有介紹(同時(shí)，關(guān)于基于R樹(shù)的最近鄰查找，還可以看下這篇文章：    19

42、75年，來(lái)自斯坦福大學(xué)的Jon Louis Bentley在ACM雜志上發(fā)表的一篇論文：Multidimensional Binary Search Trees Used for Associative Searching 中正式提出和闡述的了如下圖形式的把空間劃分為多個(gè)部分的k-d樹(shù)。2.1、什么是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ù)

43、。    首先必須搞清楚的是，k-d樹(shù)是一種空間劃分樹(shù)，說(shuō)白了，就是把整個(gè)空間劃分為特定的幾個(gè)部分，然后在特定空間的部分內(nèi)進(jìn)行相關(guān)搜索操作。想像一個(gè)三維(多維有點(diǎn)為難你的想象力了)空間，kd樹(shù)按照一定的劃分規(guī)則把這個(gè)三維空間劃分了多個(gè)空間，如下圖所示：2.2、KD樹(shù)的構(gòu)建    kd樹(shù)構(gòu)建的偽代碼如下圖所示：    再舉一個(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ù)采用分而治之的思想

44、，即將整個(gè)空間劃分為幾個(gè)小部分，首先，粗黑線將空間一分為二，然后在兩個(gè)子空間中，細(xì)黑直線又將整個(gè)空間劃分為四部分，最后虛黑直線將這四部分進(jìn)一步劃分。    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）。這

45、樣，該節(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)；    如上算法所述，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ì)上面所示的空間劃分之后，我們可

46、以看出，點(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ù)：     k-d樹(shù)的數(shù)據(jù)結(jié)構(gòu)    針對(duì)上表給出的kd樹(shù)的數(shù)據(jù)結(jié)構(gòu)，轉(zhuǎn)化成具體代碼如下所示(注，本文以下代碼分析基于Rob Hess維護(hù)的sift庫(kù))：1. /* a node in a k-d tree

47、60;*/  2. struct kd_node  3.   4.     int ki;                      /*< partition key index */關(guān)鍵點(diǎn)直方圖方差最大向量系列

48、位置  5.     double kv;                   /*< partition key value */直方圖方差最大向量系列中最中間模值  6.     int leaf;  

49、;                  /*< 1 if node is a leaf, 0 otherwise */  7.     struct feature* features;    /*<

50、 features at this node */  8.     int n;                       /*< number of features */  9.

51、     struct kd_node* kd_left;     /*< left child */  10.     struct kd_node* kd_right;    /*< right child */  11. ;     

52、; 也就是說(shuō)，如之前所述，kd樹(shù)中，kd代表k-dimension，每個(gè)節(jié)點(diǎn)即為一個(gè)k維的點(diǎn)。每個(gè)非葉節(jié)點(diǎn)可以想象為一個(gè)分割超平面，用垂直于坐標(biāo)軸的超平面將空間分為兩個(gè)部分，這樣遞歸的從根節(jié)點(diǎn)不停的劃分，直到?jīng)]有實(shí)例為止。經(jīng)典的構(gòu)造k-d tree的規(guī)則如下：1. 隨著樹(shù)的深度增加，循環(huán)的選取坐標(biāo)軸，作為分割超平面的法向量。對(duì)于3-d tree來(lái)說(shuō)，根節(jié)點(diǎn)選取x軸，根節(jié)點(diǎn)的孩子選取y軸，根節(jié)點(diǎn)的孫子選取z軸，根節(jié)點(diǎn)的曾孫子選取x軸，這樣循環(huán)下去。2. 每次均為所有對(duì)應(yīng)實(shí)例的中位數(shù)的實(shí)例作為切分點(diǎn)，切分點(diǎn)作為父節(jié)點(diǎn)，左右兩側(cè)為劃分的作為左右兩子樹(shù)。    對(duì)于n個(gè)實(shí)例的k維數(shù)

53、據(jù)來(lái)說(shuō)，建立kd-tree的時(shí)間復(fù)雜度為O(k*n*logn)。    以下是構(gòu)建k-d樹(shù)的代碼：1. struct kd_node* kdtree_build( struct feature* features, int n )  2.   3.     struct kd_node* kd_root;  4.   5.    

54、; if( ! features  |  n <= 0 )  6.       7.         fprintf( stderr, "Warning: kdtree_build(): no features, %s, line %dn&qu

55、ot;,  8.                 _FILE_, _LINE_ );  9.         return NULL;  10.       11.   12.  

56、   /初始化  13.     kd_root = kd_node_init( features, n );  /n-number of features,initinalize root of tree.  14.     expand_kd_node_subtree( kd_root ); &

57、#160;/kd tree expand  15.   16.     return kd_root;  17.       上面的涉及初始化操作的兩個(gè)函數(shù)kd_node_init，及expand_kd_node_subtree代碼分別如下所示：1. static struct kd_node* kd_node_init( struct feature* featur

58、es, int n )  2.                                      /n-number of features 

59、 3.     struct kd_node* kd_node;  4.   5.     kd_node = (struct kd_node*)(malloc( sizeof( struct kd_node ) );  6.     memset( kd_node, 0, si

60、zeof( struct kd_node ) ); /0填充  7.     kd_node->ki = -1; /?  8.     kd_node->features = features;  9.     kd_node->n = n;  10. 

61、0; 11.     return kd_node;  12.   1. static void expand_kd_node_subtree( struct kd_node* kd_node )  2.   3.     /* base case: leaf node */  4. &#

62、160;   if( kd_node->n = 1  |  kd_node->n = 0 )  5.        /葉節(jié)點(diǎn)               /偽葉節(jié)點(diǎn)  6.   

63、      kd_node->leaf = 1;  7.         return;  8.       9.   10.     assign_part_key( kd_node ); /get ki,kv  

64、;11.     partition_features( kd_node ); /creat left and right children,特征點(diǎn)ki位置左樹(shù)比右樹(shù)模值小,kv作為分界模值  12.                       &#

65、160;          /kd_node中關(guān)鍵點(diǎn)已經(jīng)排序  13.     if( kd_node->kd_left )  14.         expand_kd_node_subtree( kd_node->kd_left );  15.  

66、60;  if( kd_node->kd_right )  16.         expand_kd_node_subtree( kd_node->kd_right );  17.       構(gòu)建完kd樹(shù)之后，如今進(jìn)行最近鄰搜索呢？從下面的動(dòng)態(tài)gif圖中，你是否能看出些許端倪呢？    k-d樹(shù)算法可以分為兩大部分，除了上部分有關(guān)k

67、-d樹(shù)本身這種數(shù)據(jù)結(jié)構(gòu)建立的算法，另一部分是在建立的k-d樹(shù)上各種諸如插入，刪除，查找(最鄰近查找)等操作涉及的算法。下面，咱們依次來(lái)看kd樹(shù)的插入、刪除、查找操作。2.3、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)。    下面4副圖(來(lái)源：中國(guó)地質(zhì)大學(xué)電子課件)說(shuō)明了插入順序?yàn)?a) C

68、hicago, (b) Mobile, (c) Toronto, and (d) Buffalo，建立空間K-D樹(shù)的示例：    應(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.4、KD樹(shù)的刪除    KD樹(shù)的刪除可以用

69、遞歸程序來(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)。    也就是說(shuō)，跟普通二叉樹(shù)(包括如下圖所示的紅黑樹(shù))結(jié)點(diǎn)的刪除是同樣的思想：用被刪除節(jié)點(diǎn)A的左子樹(shù)的最右節(jié)點(diǎn)或者A的右子樹(shù)的最左節(jié)點(diǎn)作為替代A的節(jié)點(diǎn)(比如，下

70、圖紅黑樹(shù)中，若要?jiǎng)h除根結(jié)點(diǎn)26，第一步便是用23或28取代根結(jié)點(diǎn)26)。   當(dāng)(a,b)的右子樹(shù)為空時(shí)，找到（a,b）左子樹(shù)中具有x坐標(biāo)最大的結(jié)點(diǎn)，譬如（c,d），將(a,b)的左子樹(shù)放到(c,d)的右子樹(shù)中，且在樹(shù)中從它的上一層遞歸地應(yīng)用刪除過(guò)程（也就是（a,b）的左子樹(shù)） 。    下面來(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)看一系列刪除步驟：    要?jiǎng)h除上圖中結(jié)點(diǎn)A，選擇結(jié)點(diǎn)A的右子樹(shù)中X坐標(biāo)值最小的結(jié)點(diǎn)，這里是C，C成為根，

71、如下圖：     從C的右子樹(shù)中找出一個(gè)結(jié)點(diǎn)代替先前C的位置，    這里是D，并將D的左子樹(shù)轉(zhuǎn)為它的右子樹(shù)，D代替先前C的位置，如下圖：    在D的新右子樹(shù)中，找X坐標(biāo)最小的結(jié)點(diǎn)，這里為H，H代替D的位置，    在D的右子樹(shù)中找到一個(gè)Y坐標(biāo)最小的值，這里是I，將I代替原先H的位置，從而A結(jié)點(diǎn)從圖中順利刪除，如下圖所示：    從一個(gè)K-D樹(shù)中刪除結(jié)點(diǎn)(a,b)的問(wèn)題變成了在(a,b)的子樹(shù)中尋找x坐標(biāo)為最小的結(jié)點(diǎn)。不幸的是尋找最小x坐標(biāo)值的結(jié)點(diǎn)比二叉

72、檢索樹(shù)中解決類似的問(wèn)題要復(fù)雜得多。特別是雖然最小x坐標(biāo)值的結(jié)點(diǎn)一定在x識(shí)別器的左子樹(shù)中，但它同樣可在y識(shí)別器的兩個(gè)子樹(shù)中。因此關(guān)系到檢索，且必須注意檢索坐標(biāo)，以使在每個(gè)奇數(shù)層僅檢索2個(gè)子樹(shù)中的一個(gè)。    從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.5、KD樹(shù)的最近鄰搜索算法   

73、現(xiàn)實(shí)生活中有許多問(wèn)題需要在多維數(shù)據(jù)的快速分析和快速搜索，對(duì)于這個(gè)問(wèn)題最常用的方法是所謂的kd樹(shù)。在k-d樹(shù)中進(jìn)行數(shù)據(jù)的查找也是特征匹配的重要環(huán)節(jié)，其目的是檢索在k-d樹(shù)中與查詢點(diǎn)距離最近的數(shù)據(jù)點(diǎn)。在一個(gè)N維的笛卡兒空間在兩個(gè)點(diǎn)之間的距離是由下述公式確定：2.5.1、k-d樹(shù)查詢算法的偽代碼    k-d樹(shù)查詢算法的偽代碼如下所示：1. 算法：k-d樹(shù)最鄰近查找  2. 輸入：Kd，    /k-d tree類型  3.      tar

74、get  /查詢數(shù)據(jù)點(diǎn)  4. 輸出：nearest， /最鄰近數(shù)據(jù)點(diǎn)  5.      dist      /最鄰近數(shù)據(jù)點(diǎn)和查詢點(diǎn)間的距離  6.   7. 1. If Kd為NULL，則設(shè)dist為infinite并返回  8. 2. /進(jìn)行二叉查找，生成搜索路徑  9.   

75、0;Kd_point = &Kd；                   /Kd-point中保存k-d tree根節(jié)點(diǎn)地址  10.    nearest = Kd_point -> Node-data；  /初始化最近鄰點(diǎn)  11.

76、  12.    while（Kd_point）  13.    push（Kd_point）到search_path中； /search_path是一個(gè)堆棧結(jié)構(gòu)，存儲(chǔ)著搜索路徑節(jié)點(diǎn)指針  14.   15.       If Dist（nearest，target） > Dist（Kd_point -> Node-data，

77、target）  16.    nearest  = Kd_point -> Node-data；    /更新最近鄰點(diǎn)  17.    Min_dist = Dist(Kd_point，target）；  /更新最近鄰點(diǎn)與查詢點(diǎn)間的距離  */  18.    s = K

78、d_point -> split；                       /確定待分割的方向  19.   20.    If targets <= Kd_point -> Node-datas 

79、    /進(jìn)行二叉查找  21.    Kd_point = Kd_point -> left；  22.    else  23.    Kd_point = Kd_point ->right；  24.    End while  25. &#

80、160; 26. 3. /回溯查找  27.    while（search_path != NULL）  28.    back_point = 從search_path取出一個(gè)節(jié)點(diǎn)指針；   /從search_path堆棧彈棧  29.    s = back_point -> split； 

81、60;                    /確定分割方向  30.   31.    If Dist（targets，back_point -> Node-datas） < Max_dist   /判斷還需進(jìn)入的子空間 &#

82、160;32.    If targets <= back_point -> Node-datas  33.    Kd_point = back_point -> right；  /如果target位于左子空間，就應(yīng)進(jìn)入右子空間  34.    else  35.    Kd_point&

83、#160;= back_point -> left;    /如果target位于右子空間，就應(yīng)進(jìn)入左子空間  36.    將Kd_point壓入search_path堆棧；  37.   38.    If Dist（nearest，target） > Dist（Kd_Point -> Node-data，target）  39.    nearest  = Kd_point -> Node-data；                 /更新最近鄰點(diǎn)  40.    Min_dist = Dist（Kd_point -> Node-data,ta