C++KDTree 전체 코드 구현

간단 한 소개
*8195°k-d 트 리(k-dimensional)는 k 차원 데이터 공간 을 분할 하 는 데이터 구조(데이터 점 이 k 차원 공간 에서 분 단 된 데이터 구조)로 주로 다 차원 공간 핵심 데이터 검색(예 를 들 어 범위 검색 과 최근 인접 검색)에 사용 된다.
kdTree 개념
       kd-tree 나 k 차원 트 리 는 컴퓨터 과학 에서 사용 하 는 데이터 구조 로 k 차원 공간 중심 점 의 집합 을 조직 하 는 데 사용 된다.그것 은 다른 제약 조건 을 가 진 2 분 검색 트 리 이다.Kd-tree 는 구간 과 근린 검색 에 매우 유용 합 니 다.일반적으로 3 차원 공간 에 있 는 이웃 검색 은 kd-tree 를 자주 사용 하기 때문에 본 논문 의 모든 kd-tree 는 3 차원 kd-tree 입 니 다.
예 를 들다

『8195』위의 그림 은 kdtree 입 니 다.kdtree 는 이 진 트 리 의 변종 임 을 알 수 있 습 니 다.
『8195』kdtree 의 성질:
4.567917.kdtree 는 균형 적 인 특징 을 가지 고 두 나뭇잎 의 높이 차 이 는 1 을 초과 하지 않 는 다.나무 가 균형 을 이 룰 수록 평균 적 으로 나 눌 수록 검색 시간 이 적 다 는 뜻 이다)4.567917.데 이 터 는 잎 결점 에 만 저장 되 고 뿌리 결점 과 중간 결점 은 일부 공간 구분 정 보 를 저장 합 니 다(예 를 들 어 차원,구분 값)4.567917.모든 원 조 를 0 으로 정렬 합 니 다(첫 번 째 번 째 번 호 는 0 이 고 두 번 째 번 째 번 호 는 1 이 며 세 번 째 번 째 번 호 는 2 입 니 다).나무의 n 층,n%3 번 째 항목 은 굵 은 몸 으로 표 시 됩 니 다.이런 굵 은 몸 으로 표 시 된 나 무 는 바로 이 진 트 리 의 key 값 입 니 다.예 를 들 어 뿌리 노드 의 왼쪽 나무 중의 모든 노드 의 첫 번 째 항목 은 뿌리 노드 의 첫 번 째 항목 보다 작 습 니 다.오른쪽 서브 트 리 의 노드 중 첫 번 째 항목 은 모두 뿌리 노드 의 첫 번 째 항목 보다 크 고 서브 트 리 는 순서대로 유추 합 니 다분할 적 역할
일차 원
  하나의 표준 BSTree 에 대해 노드 마다 key 값 이 하나 밖 에 없다.

키 값 을 1 차원 좌표 축 에 대응 합 니 다.

  뿌리 노드 에 대응 하 는 것 은 바로 2 이다.왼쪽 나 무 는 모두 2 의 왼쪽 에 있 고 오른쪽 나 무 는 모두 2 의 오른쪽 에 있 으 며 전체 1 차원 공간 은 뿌리 노드 에 의 해 두 부분 으로 나 뉘 어 져 있다.결점 0 을 찾 으 려 면 2 의 왼쪽 이기 때문에 안심 하고 왼쪽 나무의 부분 만 검색 할 수 있다.전체 검색 과정 은 대상 노드 를 찾 을 때 까지 검색 구간 을 계속 분할 하 는 과정 으로 볼 수 있다.
2 차원
이러한 분할 은 2 차원,심지어 더 많은 차원 으로 확 대 될 수 있다.
그런데 문제 가 생 겼 어 요.2 차원 의 노드 는 어떻게 크기 를 비교 합 니까?
BSTree 에서 노드 가 1 차원 축 으로 나 뉘 면 2 차원 에서 평면 을 나 누 어야 합 니 다.이렇게:

노란색 의 점 은 뿌리 노드 로 서 위의 점 은 왼쪽 나무 로 되 어 있 고 아래 의 점 은 오른쪽 나무 로 되 어 있다.그 다음 에 계속 구분 하면 마지막 으로 나 무 는 유명한 BSPTree(binary space paritioning tree)이다.분 단 된 그 선 은 분할 초 평면(splitting hyperplane)이 라 고 하 는데 1 차원 에서 하나의 점 이 고 2 차원 에서 선 이 며 3 차원 은 면 이다.
n 차원
KDTree 는 초 평면 이 모두 축 에 수직 으로 있 는 BSPTree 다.같은 데이터 세트 를 KDTree 로 구분 하면 다음 과 같 습 니 다.

노란색 노드 는 루트 노드 이 고 다음 층 은 빨간색 이 며 다음 층 은 녹색 이 고 다음 층 은 파란색 이다.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;
}

전체 코드 다운로드 주소:KDTreeC++구현
참고:
https://blog.csdn.net/silangquan/article/details/41483689
https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html
C++구현 KDTree 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 KDTree 내용 은 이전 글 을 검색 하거나 아래 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!