本篇內(nèi)容主要講解“如何用C++代碼實現(xiàn)KDTree”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“如何用C++代碼實現(xiàn)KDTree”吧!

創(chuàng)新互聯(lián)公司成立于2013年，先為彭水苗族土家族等服務(wù)建站，彭水苗族土家族等地企業(yè)，進行企業(yè)商務(wù)咨詢服務(wù)。為彭水苗族土家族企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

簡介

??k-d樹（k-dimensional），是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)（對數(shù)據(jù)點在k維空間中劃分的一種數(shù)據(jù)結(jié)構(gòu)），主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）。

kdTree概念

       kd-tree或者k維樹是計算機科學(xué)中使用的一種數(shù)據(jù)結(jié)構(gòu)，用來組織表示k維空間中點的集合。它是一種帶有其他約束條件的二分查找樹。Kd-tree對于區(qū)間和近鄰搜索十分有用。一般位于三維空間中的鄰域搜索常用kd-tree，因此本文中所有的kd-tree都是三維的kd-tree。

舉例

??上圖就是一顆kdtree，可以看出kdtree是二叉搜索樹的變種。
?kdtree的性質(zhì)：

1. kdtree具有平衡的特質(zhì)，兩樹葉的高度差不超過1。(樹越平衡代表著分割得越平均，搜索的時間越少)

2. 數(shù)據(jù)只存放在葉子結(jié)點，而根結(jié)點和中間結(jié)點存放一些空間劃分信息（例如劃分維度、劃分值）。

3. 將每一個元組按0排序（第一項序號為0，第二項序號為1，第三項序號為2），在樹的第n層，第 n%3 項被用粗體顯示，而這些被粗體顯示的樹就是作為二叉搜索樹的key值，比如，根節(jié)點的左子樹中的每一個節(jié)點的第一個項均小于根節(jié)點的的第一項，右子樹的節(jié)點中第一項均大于根節(jié)點的第一項，子樹依次類推。

分割的作用

一維

??對于一個標(biāo)準(zhǔn)的BSTree，每個節(jié)點只有一個key值。

??將key值對應(yīng)到一維的坐標(biāo)軸上。

??根節(jié)點對應(yīng)的就是2，左子樹都在2的左邊，右子樹都在2的右邊，整個一維空間就被根節(jié)點分割成了兩個部分，當(dāng)要查找結(jié)點0的時候，由于是在2的左邊，所以可以放心的只搜索左子樹的部分。整個搜索的過程可以看成不斷分割搜索區(qū)間的過程，直到找到目標(biāo)節(jié)點。

二維

這樣的分割可以擴展到二維甚至更多維的情況。

但是問題來了，二維的節(jié)點怎么比較大??？

在BSTree中，節(jié)點分割的是一維數(shù)軸，那么在二維中，就應(yīng)當(dāng)是分割平面了，就像這樣：

黃色的點作為根節(jié)點，上面的點歸左子樹，下面的點歸右子樹，接下來再不斷地劃分，最后得到一棵樹就是赫赫有名的BSPTree（binary space partitioning tree）. 分割的那條線叫做分割超平面（splitting hyperplane），在一維中是一個點，二維中是線，三維的是面。

n維

KDTree就是超平面都垂直于軸的BSPTree。同樣的數(shù)據(jù)集，用KDTree劃分之后就是這樣：

黃色節(jié)點就是Root節(jié)點，下一層是紅色，再下一層是綠色，再下一層是藍色。為了更好的理解KDTree的分割，我們在圖形中來看一下搜索的過程，假設(shè)現(xiàn)在需要搜尋右下角的一個點，首先要做的就是比較這個點的x坐標(biāo)和root點的x坐標(biāo)值，由于x坐標(biāo)值大于root節(jié)點的x坐標(biāo)，所以只需要在右邊搜尋，接下來，要比較該節(jié)點和右邊紅色節(jié)點y值得大小...后面依此類推。整個過程如下圖：
1.

2.

3.

關(guān)于kdtree的重要問題

一.樹的建立

1.節(jié)點的數(shù)據(jù)結(jié)構(gòu)

定義：
Node-data - 數(shù)據(jù)矢量， 數(shù)據(jù)集中某個數(shù)據(jù)點，是n維矢量（這里也就是k維）
Range - 空間矢量， 該節(jié)點所代表的空間范圍
split - 整數(shù)， 垂直于分割超平面的方向軸序號
Left - k-d樹， 由位于該節(jié)點分割超平面左子空間內(nèi)所有數(shù)據(jù)點所構(gòu)成的k-d樹
Right - k-d樹， 由位于該節(jié)點分割超平面右子空間內(nèi)所有數(shù)據(jù)點所構(gòu)成的k-d樹
parent - k-d樹， 父節(jié)點

2. 優(yōu)化

1.切分維度優(yōu)化

構(gòu)建開始前，對比數(shù)據(jù)點在各維度的分布情況，數(shù)據(jù)點在某一維度坐標(biāo)值的方差越大分布越分散，方差越小分布越集中。從方差大的維度開始切分可以取得很好的切分效果及平衡性。

2.中值選擇優(yōu)化

第一種，算法開始前，對原始數(shù)據(jù)點在所有維度進行一次排序，存儲下來，然后在后續(xù)的中值選擇中，無須每次都對其子集進行排序，提升了性能。

第二種，從原始數(shù)據(jù)點中隨機選擇固定數(shù)目的點，然后對其進行排序，每次從這些樣本點中取中值，來作為分割超平面。該方式在實踐中被證明可以取得很好性能及很好的平衡性。

2.最近鄰域搜索（Nearest-Neighbor Lookup）

給定一個KDTree和一個節(jié)點，求KDTree中離這個節(jié)點最近的節(jié)點.(這個節(jié)點就是最臨近點)

這里距離的求法用的是歐式距離。

基本的思路很簡單：首先通過二叉樹搜索（比較待查詢節(jié)點和分裂節(jié)點的分裂維的值，小于等于就進入左子樹分支，等于就進入右子樹分支直到葉子結(jié)點），順著“搜索路徑”很快能找到最近鄰的近似點，也就是與待查詢點處于同一個子空間的葉子結(jié)點；然后再回溯搜索路徑，并判斷搜索路徑上的結(jié)點的其他子結(jié)點空間中是否可能有距離查詢點更近的數(shù)據(jù)點，如果有可能，則需要跳到其他子結(jié)點空間中去搜索（將其他子結(jié)點加入到搜索路徑）。重復(fù)這個過程直到搜索路徑為空。

這里還有幾個細(xì)節(jié)需要注意一下，如下圖，假設(shè)標(biāo)記為星星的點是 test point， 綠色的點是找到的近似點，在回溯過程中，需要用到一個隊列，存儲需要回溯的點，在判斷其他子節(jié)點空間中是否有可能有距離查詢點更近的數(shù)據(jù)點時，做法是以查詢點為圓心，以當(dāng)前的最近距離為半徑畫圓，這個圓稱為候選超球（candidate hypersphere），如果圓與回溯點的軸相交，則需要將軸另一邊的節(jié)點都放到回溯隊列里面來。

判斷軸是否與候選超球相交的方法可以參考下圖：

關(guān)鍵代碼

構(gòu)建KDTree

void KDTree::buildKdTree(KDTree *tree, vector> data, unsigned int depth)
{
    //樣本的數(shù)量
    unsigned long samplesNum = data.size();
    //終止條件
    if (samplesNum == 0)
    {
        return;
    }
    if (samplesNum == 1)
    {
        tree->root = data[0];
        return;
    }
    //樣本的維度
    unsigned long k = data[0].size();//坐標(biāo)軸個數(shù)
    vector > transData = Transpose(data);
    //選擇切分屬性
    unsigned splitAttribute = depth % k;
    vector splitAttributeValues = transData[splitAttribute];
    //選擇切分值
    double splitValue = findMiddleValue(splitAttributeValues);
    //cout << "splitValue" << splitValue  << endl;

    // 根據(jù)選定的切分屬性和切分值，將數(shù)據(jù)集分為兩個子集
    vector > subset1;
    vector > subset2;
    for (unsigned i = 0; i < samplesNum; ++i)
    {
        if (splitAttributeValues[i] == splitValue && tree->root.empty())
            tree->root = data[i];
        else
        {
            if (splitAttributeValues[i] < splitValue)
                subset1.push_back(data[i]);
            else
                subset2.push_back(data[i]);
        }
    }

    //子集遞歸調(diào)用buildKdTree函數(shù)
    tree->left_child = new KDTree;
    tree->left_child->parent = tree;
    tree->right_child = new KDTree;
    tree->right_child->parent = tree;
    buildKdTree(tree->left_child, subset1, depth + 1);
    buildKdTree(tree->right_child, subset2, depth + 1);
}

查詢目標(biāo)點的最近鄰點

vector KDTree::searchNearestNeighbor(vector goal, KDTree *tree)
{
    /*第一步：在kd樹中找出包含目標(biāo)點的葉子結(jié)點：從根結(jié)點出發(fā)，
    遞歸的向下訪問kd樹，若目標(biāo)點的當(dāng)前維的坐標(biāo)小于切分點的
    坐標(biāo)，則移動到左子結(jié)點，否則移動到右子結(jié)點，直到子結(jié)點為
    葉結(jié)點為止,以此葉子結(jié)點為“當(dāng)前最近點”
    */
    unsigned long k = tree->root.size();//計算出數(shù)據(jù)的維數(shù)
    unsigned d = 0;//維度初始化為0，即從第1維開始
    KDTree* currentTree = tree;
    vector currentNearest = currentTree->root;
    while(!currentTree->is_leaf())
    {
        unsigned index = d % k;//計算當(dāng)前維
        if (currentTree->right_child->is_empty() || goal[index] < currentNearest[index])
        {
            currentTree = currentTree->left_child;
        }
        else
        {
            currentTree = currentTree->right_child;
        }
        ++d;
    }
    currentNearest = currentTree->root;

    /*第二步：遞歸地向上回退， 在每個結(jié)點進行如下操作：
    (a)如果該結(jié)點保存的實例比當(dāng)前最近點距離目標(biāo)點更近，則以該例點為“當(dāng)前最近點”
    (b)當(dāng)前最近點一定存在于某結(jié)點一個子結(jié)點對應(yīng)的區(qū)域，檢查該子結(jié)點的父結(jié)點的另
    一子結(jié)點對應(yīng)區(qū)域是否有更近的點（即檢查另一子結(jié)點對應(yīng)的區(qū)域是否與以目標(biāo)點為球
    心、以目標(biāo)點與“當(dāng)前最近點”間的距離為半徑的球體相交）；如果相交，可能在另一
    個子結(jié)點對應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點更近的點，移動到另一個子結(jié)點，接著遞歸進行最
    近鄰搜索；如果不相交，向上回退*/

    //當(dāng)前最近鄰與目標(biāo)點的距離
    double currentDistance = measuredistance(goal, currentNearest, 0);

    //如果當(dāng)前子kd樹的根結(jié)點是其父結(jié)點的左孩子，則搜索其父結(jié)點的右孩子結(jié)點所代表
    //的區(qū)域，反之亦反
    KDTree* searchDistrict;
    if (currentTree->is_left())
    {
        if (currentTree->parent->right_child == nullptr)
            searchDistrict = currentTree;
        else
            searchDistrict = currentTree->parent->right_child;
    }
    else
    {
        searchDistrict = currentTree->parent->left_child;
    }

    //如果搜索區(qū)域?qū)?yīng)的子kd樹的根結(jié)點不是整個kd樹的根結(jié)點，繼續(xù)回退搜索
    while (searchDistrict->parent != nullptr)
    {
        //搜索區(qū)域與目標(biāo)點的最近距離
        double districtDistance = abs(goal[(d+1)%k] - searchDistrict->parent->root[(d+1)%k]);

        //如果“搜索區(qū)域與目標(biāo)點的最近距離”比“當(dāng)前最近鄰與目標(biāo)點的距離”短，表明搜索
        //區(qū)域內(nèi)可能存在距離目標(biāo)點更近的點
        if (districtDistance < currentDistance )//&& !searchDistrict->isEmpty()
        {

            double parentDistance = measureDistance(goal, searchDistrict->parent->root, 0);

            if (parentDistance < currentDistance)
            {
                currentDistance = parentDistance;
                currentTree = searchDistrict->parent;
                currentNearest = currentTree->root;
            }
            if (!searchDistrict->is_empty())
            {
                double rootDistance = measureDistance(goal, searchDistrict->root, 0);
                if (rootDistance < currentDistance)
                {
                    currentDistance = rootDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->left_child != nullptr)
            {
                double leftDistance = measureDistance(goal, searchDistrict->left_child->root, 0);
                if (leftDistance < currentDistance)
                {
                    currentDistance = leftDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
            if (searchDistrict->right_child != nullptr)
            {
                double rightDistance = measureDistance(goal, searchDistrict->right_child->root, 0);
                if (rightDistance < currentDistance)
                {
                    currentDistance = rightDistance;
                    currentTree = searchDistrict;
                    currentNearest = currentTree->root;
                }
            }
        }//end if

        if (searchDistrict->parent->parent != nullptr)
        {
            searchDistrict = searchDistrict->parent->is_left()?
                            searchDistrict->parent->parent->right_child:
                            searchDistrict->parent->parent->left_child;
        }
        else
        {
            searchDistrict = searchDistrict->parent;
        }
        ++d;
    }//end while
    return currentNearest;
}

到此，相信大家對“如何用C++代碼實現(xiàn)KDTree”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！