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

熱線電話：13121318867

登錄
首頁(yè)精彩閱讀KD樹的構(gòu)建_數(shù)據(jù)分析師
KD樹的構(gòu)建_數(shù)據(jù)分析師
2014-11-30
收藏

KD樹的構(gòu)建_數(shù)據(jù)分析師

KD樹的構(gòu)建

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

    再舉一個(gè)簡(jiǎn)單直觀的實(shí)例來(lái)介紹k-d樹構(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樹采用分而治之的思想，即將整個(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樹的具體步驟為：

  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)的分割超平面就是通過（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樹的構(gòu)建是一個(gè)遞歸過程，我們對(duì)左子空間和右子空間內(nèi)的數(shù)據(jù)重復(fù)根節(jié)點(diǎn)的過程就可以得到一級(jí)子節(jié)點(diǎn)（5,4）和（9,6），同時(shí)將空間和數(shù)據(jù)集進(jìn)一步細(xì)分，如此往復(fù)直到空間中只包含一個(gè)數(shù)據(jù)點(diǎn)。

    與此同時(shí)，經(jīng)過對(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)的左右孩子(通過兩條細(xì)紅斜線相連)，最后，(8,1)為(9,6)的左孩子(通過細(xì)紅斜線相連)。如此，便形成了下面這樣一棵k-d樹：

 

    k-d樹的數(shù)據(jù)結(jié)構(gòu)

    針對(duì)上表給出的kd樹的數(shù)據(jù)結(jié)構(gòu)，轉(zhuǎn)化成具體代碼如下所示(注，本文以下代碼分析基于Rob Hess維護(hù)的sift庫(kù))：

  1. /** a node in a k-d tree */  
  2. struct kd_node  
  3. {  
  4.     int ki;                      /**< partition key index *///關(guān)鍵點(diǎn)直方圖方差最大向量系列位置  
  5.     double kv;                   /**< partition key value *///直方圖方差最大向量系列中最中間模值  
  6.     int leaf;                    /**< 1 if node is a leaf, 0 otherwise */  
  7.     struct feature* features;    /**< features at this node */  
  8.     int n;                       /**< number of features */  
  9.     struct kd_node* kd_left;     /**< left child */  
  10.     struct kd_node* kd_right;    /**< right child */  
  11. };  

    也就是說，如之前所述，kd樹中，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. 隨著樹的深度增加，循環(huán)的選取坐標(biāo)軸，作為分割超平面的法向量。對(duì)于3-d tree來(lái)說，根節(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è)為劃分的作為左右兩子樹。

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

    以下是構(gòu)建k-d樹的代碼：

  1. struct kd_node* kdtree_build( struct feature* features, int n )  
  2. {  
  3.     struct kd_node* kd_root;  
  4.   
  5.     if( ! features  ||  n <= 0 )  
  6.     {  
  7.         fprintf( stderr, "Warning: kdtree_build(): no features, %s, line %d\n",  
  8.                 __FILE__, __LINE__ );  
  9.         return NULL;  
  10.     }  
  11.   
  12.     //初始化  
  13.     kd_root = kd_node_init( features, n );  //n--number of features,initinalize root of tree.  
  14.     expand_kd_node_subtree( kd_root );  //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* features, int n )  
  2. {                                     //n--number of features  
  3.     struct kd_node* kd_node;  
  4.   
  5.     kd_node = (struct kd_node*)(malloc( sizeof( struct kd_node ) ));  
  6.     memset( kd_node, 0, sizeof( struct kd_node ) ); //0填充  
  7.     kd_node->ki = -1; //???????  
  8.     kd_node->features = features;  
  9.     kd_node->n = n;  
  10.   
  11.     return kd_node;  
  12. }  
  1. static void expand_kd_node_subtree( struct kd_node* kd_node )  
  2. {  
  3.     /* base case: leaf node */  
  4.     if( kd_node->n == 1  ||  kd_node->n == 0 )  
  5.     {   //葉節(jié)點(diǎn)               //偽葉節(jié)點(diǎn)  
  6.         kd_node->leaf = 1;  
  7.         return;  
  8.     }  
  9.   
  10.     assign_part_key( kd_node ); //get ki,kv  
  11.     partition_features( kd_node ); //creat left and right children,特征點(diǎn)ki位置左樹比右樹模值小,kv作為分界模值  
  12.                                  //kd_node中關(guān)鍵點(diǎn)已經(jīng)排序  
  13.     if( kd_node->kd_left )  
  14.         expand_kd_node_subtree( kd_node->kd_left );  
  15.     if( kd_node->kd_right )  
  16.         expand_kd_node_subtree( kd_node->kd_right );  
  17. }  

    構(gòu)建完kd樹之后，如今進(jìn)行最近鄰搜索呢？從下面的動(dòng)態(tài)gif圖中，你是否能看出些許端倪呢？

    k-d樹算法可以分為兩大部分，除了上部分有關(guān)k-d樹本身這種數(shù)據(jù)結(jié)構(gòu)建立的算法，另一部分是在建立的k-d樹上各種諸如插入，刪除，查找(最鄰近查找)等操作涉及的算法。

數(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ù)說明請(qǐng)參見：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); }