kd - tree 의 python 구현

본문 의 주요 내용
[kd - tree 의 C 언어 실현] 몇 년 전에 쓴 kd - tree 블 로그 입 니 다.당시 이 항 선생님 의 '통계 학습 방법' 이라는 책 을 읽 고 있 었 는데 kNN 알고리즘 과 kd - tree 간 의 관 계 를 보고 깊이 있 게 이해 하 는 데 관심 이 많아 서 자 료 를 모 았 는데 그 뒤에 실제 작업 에 사용 되 지 않 아 내 려 놓 았 다.최근 에 이 선생님 의 이 책 을 다시 뒤 져 보 니 지금의 이해 가 예전 보다 훨씬 깊 어 졌 다. 그리고 이런 경전 은 항상 새로운 것 을 보고 한 번 더 뒤 집 을 때마다 한 푼 더 얻 는 것 이다.
본 논문 의 주요 내용: - kNN 알고리즘 과 kd - tree 의 관계 - kd - tree 의 구축 - kd - tree 의 근린 찾기
kNN 알고리즘 과 kd - tree 의 관계
K 최근 이웃 (kNN, k - NearestNeighbor) 분류 알고리즘 은 데이터 발굴 분류 기술 에서 가장 간단 한 방법 중 하나 이다.K 최근 이웃 이란 K 개 가장 가 까 운 이웃 이라는 뜻 으로 모든 견본 이 가장 가 까 운 k 개 이웃 으로 대표 할 수 있다 는 뜻 이다.kNN 알고리즘 의 핵심 사상 은 만약 에 하나의 견본 이 특징 공간 에서 k 개의 가장 인접 한 견본 중 대부분이 특정한 유형 에 속 하면 이 견본 도 이 유형 에 속 하고 이 유형 에서 견본 의 특성 을 가진다.이 방법 은 분류 결정 을 확정 하 는 데 있어 서 가장 가 까 운 하나 또는 몇 개의 견본 의 유형 에 따라 샘플 이 속 한 유형 을 결정 한다.kNN 방법 은 유형 결정 을 할 때 아주 적은 양의 인접 견본 과 만 관련 이 있다.kNN 방법 은 주로 주변 에 제 한 된 인접 견본 에 의존 하기 때문에 유형 을 판별 하 는 방법 으로 소속 유형 을 확정 하 는 것 이 아니 라 유형 역 의 교차 또는 중첩 이 많은 미 분 견본 집 에 있어 kNN 방법 은 다른 방법 보다 더욱 적합 하 다.그러나 KNN 알고리즘 은 선형 스 캔 을 사용 해 계산 복잡 도와 공간 복잡 도가 높다.사실 실제 데이터 가 집 중 된 점 은 보통 떨 기 모양 으로 분포 되 어 있 기 때문에 우 리 는 전혀 옮 겨 다 닐 필요 가 없다. 색인 트 리 의 방법 은 검색 할 점 을 공간 적 으로 구분 하 는 것 이다. 공간 구분 이 겹 칠 수도 있 고 겹 치지 않 을 수도 있다.kd - tree 는 공간 을 나 누 어 중첩 되 지 않 은 색인 트 리 kd - tree 는 k 차원 공간의 인 스 턴 스 점 을 저장 하여 빠 른 검색 을 할 수 있 는 트 리 데이터 구조 입 니 다.주로 다 차원 공간 핵심 데이터 검색 (예 를 들 어 범위 검색 과 최근 인접 검색) 에 사 용 됩 니 다.
구조 kd - tree
kd - tree 각 노드 에 포 함 된 데이터 구 조 는 다음 과 같다.
도 메 인 이름
유형
묘사 하 다.
dom_elt
kd 차원 벡터
kd 차원 공간의 견본 점
split
정수
분열 차원 의 번호 도 분할 초 면 에 수직 으로 있 는 방향 축 번호 이다.
left
kd-tree
이 노드 분할 초 면 왼쪽 공간 에 있 는 모든 데이터 점 으로 구 성 된 kd - tree
right
kd-tree
이 노드 분할 초 면 오른쪽 하위 공간 에 있 는 모든 데이터 점 으로 구 성 된 kd - tree
대응 하 는 python 정의:

class  KD_node:
    def __init__(self, elt=None, split=None, LL=None, RR=None):
        '''  
        elt:     
        split:     
        LL, RR:            
        '''
        self.elt = elt
        self.split = split
        self.left = LL
        self.right = RR
    def createKDTree(root, data_list):
        '''
        root:         
        data_list:      (  )  
        return:   KDTree     
        '''
        LEN = len(data_list)
        if LEN == 0:
            return
        #       
        dimension = len(data_list[0])
        #   
        max_var = 0
        #         
        split = 0
        for i in range(dimension):
            items = []
            for t in data_list:
                items.append(t[i])
            var = computeVariance(items)
            if var > max_var:
                max_var = var
                split = i
        #                 
        data_list.sort(key=lambda x: x[split])
        #     len / 2       
        elt = data_list[LEN/2]
        root = KD_node(elt,split)
        root.left = createKDTree(root.left, data_list[0:LEN/2])
        root.right = createKDTree(root.right, data_list[(LEN/2+1):LEN])
        return root

def computeVariance(arrayList):
    '''
    arrayList:        
    return:          
    '''
    for ele in arrayList:
        ele = float(ele)
    LEN = float(len(arrayList))
    array = numpy.array(arrayList)
    sum1 =  array.sum()
    array2 = array * array
    sum2 = array2.sum()
    mean = sum1 / LEN
    #    D[X] = E[x^2] - (E[x])^2  
    variance = sum2 / LEN - mean**2
    return variance      

각 노드 마다 견본 점 을 표시 합 니 다. domelt 는 바로 이 견본 점 의 벡터 를 나타 낸다.이 견본 점 은 결점 의 분할 초 평면 에 따라 견본 공간 을 두 개의 키 공간 으로 나 누 었 다.왼쪽 공간 에서 의 견본 점 집합 은 왼쪽 나무 left 로 표시 되 고 오른쪽 공간 에서 의 견본 점 집합 은 오른쪽 나무 right 로 표시 된다.분할 초 평면 은 통과 점 domelt 는 split 가 가리 키 는 방향 축의 평면 에 수직 으로 있다.분 단 차원 split 에 대한 선택 은 여러 가지 방법 이 있 습 니 다. 통계 기계 학습 에서 언급 한 방법 에 비해 더욱 광범 위 하 게 응용 되 는 것 은 분산 을 바탕 으로 하 는 선택 방법 입 니 다. 즉, 가능 한 한 비슷 한 점 을 하나의 서브 트 리 에 넣 기 때문에 kd - tree 가 취 하 는 사상 은 모든 노드 가 각 차원 에서 의 수치의 분산 을 계산 하 는 것 입 니 다.그 다음 에 방 차 의 가장 큰 차원 은 현재 노드 의 구분 차원 으로 한다.이렇게 하 는 원 리 는 바로 분산 이 클 수록 이 차원 의 데이터 변동 이 크다 는 것 을 의미한다. 즉, 그들 이 같은 공간 에 속 하지 않 을 수록 이 차원 에서 점 을 구분 해 야 한 다 는 것 을 의미한다. 이것 이 바로 kd - tree 노드 가 차원 을 구분 하 는 원 리 를 선택 하 는 것 이다.
kd - tree 의 최근 이웃 찾기
기본 적 인 검색 방향 은 다음 과 같다.
두 갈래 찾기
잎 사 귀 노드 까지 뿌리 노드 부터 찾기;이 과정 에서 가장 짧 은 거리 와 대응 하 는 데이터 점 을 기록한다.동시에 스 택 을 유지 하고 지나 간 노드 를 저장 합 니 다.
거 슬러 올라가다
계산 을 통 해 검색 점 에서 분할 평면 까지 의 거리 (이 거 리 는 분할 차원 의 값 의 차 이 를 비교 하 는 것 이지 분할 노드 에서 분할 평면 까지 의 거리 가 아니 라 이들 의 값 이 같 지만) 와 현재 의 최 단 거 리 를 비교 하여 노드 의 인접 서브 공간 에 들 어가 서 찾 아야 하 는 지 여 부 를 결정 한다.

def findNN(root, query):
    '''
    root:KDTree     
    query:     
    return:    data    NN，        min_dist  
    '''

    NN = root.elt
    min_dist = computeDist(query,NN)
    nodeList = []
    temp_root = root

    ##         
    while temp_root:
        nodeList.append(temp_root)
        dist = computeDist(query,temp_root.elt)
        if min_dist > dist:
            NN = temp_root.elt
            min_dist = dist

        #         
        splt = temp_root.split
        if query[splt] <= temp_root.elt[splt]:
            temp_root = temp_root.left
        else:
            temp_root = temp_root.right

        #         
        while nodeList:
            #  list   ，       
            back_elt = nodeList.pop()
            splt = back_elt.split
            print("back.elt = ", back_elt.elt)
            ##                      
            if abs(query[splt] - back_elt.elt[splt]) < min_dist:
                if(query[splt] <= back_elt.elt[splt]):
                    temp_root = back_elt.right
                else:
                    temp_root = back_elt.left

            if temp_root:
                nodeList.append(temp_root)
                curDist = computeDist(query,temp_root.elt)
                if min_dist > curDist:
                    min_dist = curDist
                    NN = temp_root.elt
    return NN, min_dist

def computeDist(pt1, pt2):
    '''
              
    return：pt1 pt2     
    '''
    sum = 0.0
    for i in range(len(pt1)):
        sum = sum + (pt1[i]-pt2[i]) * (pt1[i]-pt2[i])
    return math.sqrt(sum)