1. 如何理解kNN中的k的取值？

Ans ：①選取較小的k值時(shí)，相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，“學(xué)習(xí)”近似誤差會(huì)減小，只有與輸入實(shí)例很相近的樣本才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用。但是，“學(xué)習(xí)”的估計(jì)誤差會(huì)增大，整體模型會(huì)變得復(fù)雜，容易過(guò)擬合。
②選取較大的k值是，相當(dāng)于用較大的領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，可以減少學(xué)習(xí)的估計(jì)誤差，但是近似誤差會(huì)增大，因?yàn)殡x輸入實(shí)例較遠(yuǎn)的樣本也對(duì)預(yù)測(cè)結(jié)果起作用，容易使預(yù)測(cè)發(fā)生錯(cuò)誤。k過(guò)大導(dǎo)致模型變得簡(jiǎn)單。
③在選取k上，一般取比較小的值，并采用交叉驗(yàn)證法進(jìn)行調(diào)優(yōu)。

2. 在kNN的樣本搜索中，如何進(jìn)行高效的匹配查找？

Ans ：①線性掃描(數(shù)據(jù)多時(shí)，效率低)
②構(gòu)建數(shù)據(jù)索引——Clipping和Overlapping兩種。前者劃分的空間沒(méi)有重疊，如k-d樹(shù)；后者劃分的空間相互交疊，如R樹(shù)。

3. 那什么是KD樹(shù)？怎么構(gòu)建的？

Ans：kd樹(shù)是對(duì)數(shù)據(jù)點(diǎn)在k維空間中劃分的一種數(shù)據(jù)結(jié)構(gòu)，主要用于多維空間關(guān)鍵數(shù)據(jù)的搜索。本質(zhì)上，kd樹(shù)就是一種平衡二叉樹(shù)。
思想：先對(duì)計(jì)算各個(gè)維度的方差，選取最大方差的維度作為候選劃分維度(方差越大，表示此維度上數(shù)據(jù)越分散)；對(duì)split維度上的值進(jìn)行排序，選取中間的點(diǎn)為node-data；按照split維度的node-data對(duì)空間進(jìn)行一次劃分；對(duì)上述子空間遞歸以上操作，直到空間只包含一個(gè)數(shù)據(jù)點(diǎn)。分而治之，且循環(huán)選取坐標(biāo)軸

4. 能簡(jiǎn)單介紹一下KD樹(shù)的查找，以及增、刪、改的實(shí)現(xiàn)流程嗎？

Ans：先二叉查找，找到候選最近點(diǎn)；沿著路徑進(jìn)行回溯，畫(huà)圓，是否父節(jié)點(diǎn)平面交割，以判斷是否需要進(jìn)入另一個(gè)平面進(jìn)行查找；依次回溯，畫(huà)圓，尋找最近點(diǎn)。
KD樹(shù)更適合用于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時(shí)的k近鄰搜索。當(dāng)維數(shù)超過(guò)20維時(shí)，KD數(shù)的檢索效率急劇下降，幾乎接近貪婪的線性掃描。因此出現(xiàn)對(duì)KD樹(shù)的改進(jìn)——BBF算法，M樹(shù)，VP樹(shù)，MVP樹(shù)等高維空間索引樹(shù)。