99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀什么是KD樹(shù)_數(shù)據(jù)分析師
什么是KD樹(shù)_數(shù)據(jù)分析師
2014-11-30
收藏

什么是KD樹(shù)_數(shù)據(jù)分析師

       之前曾經(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)和近似查詢的算法。

    一般說(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)題中，可能有數(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)簇狀的聚類(lèi)形態(tài)，因此我們想到建立數(shù)據(jù)索引，然后再進(jìn)行快速匹配。索引樹(shù)是一種樹(shù)結(jié)構(gòu)索引方法，其基本思想是對(duì)搜索空間進(jìn)行層次劃分。根據(jù)劃分的空間是否有混疊可以分為Clipping和Overlapping兩種。前者劃分空間沒(méi)有重疊，其代表就是k-d樹(shù)；后者劃分空間相互有交疊，其代表為R樹(shù)。

 1975年，來(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的縮寫(xiě)，是對(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è)空間，如下圖所示：

數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼，搜微信號(hào)：CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1：配置參數(shù) // 參數(shù)2：回調(diào)，回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象，之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須，不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式，包括：float，popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn)：http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'！'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'！'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }