如何用C++代碼實現KDTree

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

簡介

??k-d樹（k-dimensional），是一種分割k維數據空間的數據結構（對數據點在k維空間中劃分的一種數據結構），主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。

kdTree概念

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

舉例

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

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

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

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

分割的作用

一維

??對于一個標準的BSTree，每個節點只有一個key值。

??將key值對應到一維的坐標軸上。

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

二維

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

但是問題來了，二維的節點怎么比較大小？

在BSTree中，節點分割的是一維數軸，那么在二維中，就應當是分割平面了，就像這樣：

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

n維

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

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

2.

3.

關于kdtree的重要問題

一.樹的建立

1.節點的數據結構

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

2. 優化

1.切分維度優化

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

2.中值選擇優化

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

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

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

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

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

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

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

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

關鍵代碼

構建KDTree

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

    // 根據選定的切分屬性和切分值，將數據集分為兩個子集
    vector<vector<double> > subset1;
    vector<vector<double> > 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]);
        }
    }

    //子集遞歸調用buildKdTree函數
    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);
}

查詢目標點的最近鄰點

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

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

    //當前最近鄰與目標點的距離
    double currentDistance = measureDistance(goal, currentNearest, 0);

    //如果當前子kd樹的根結點是其父結點的左孩子，則搜索其父結點的右孩子結點所代表
    //的區域，反之亦反
    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;
    }

    //如果搜索區域對應的子kd樹的根結點不是整個kd樹的根結點，繼續回退搜索
    while (searchDistrict->parent != nullptr)
    {
        //搜索區域與目標點的最近距離
        double districtDistance = abs(goal[(d+1)%k] - searchDistrict->parent->root[(d+1)%k]);

        //如果“搜索區域與目標點的最近距離”比“當前最近鄰與目標點的距離”短，表明搜索
        //區域內可能存在距離目標點更近的點
        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++代碼實現KDTree”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！