Как реализовать классификацию K-NN из дерева kd? - PullRequest
Новая
       48

Как реализовать классификацию K-NN из дерева kd?

0 голосов
/ 11 февраля 2019

Я пытаюсь написать код для классификации K-NN с использованием дерева kd без использования каких-либо библиотек.До сих пор я был в состоянии написать код для дерева kd, но я не могу понять, как мне найти k ближайших соседей, как только дерево было сформировано из обучающего набора.код дерева кд: 

#include<bits/stdc++.h> 
using namespace std; 

const int k = 2; // 2-dimensions 

struct Node 
{ 
    int point[k]; 
    Node *left, *right; 
}; 

struct Node* newNode(int arr[]) 
{ 
    struct Node* temp = new Node; 

    for (int i=0; i<k; i++) 
    temp->point[i] = arr[i]; 

    temp->left = temp->right = NULL; 
    return temp; 
} 
// Inserts a new node and returns root of modified tree
Node *insertRec(Node *root, int point[], unsigned depth) 
{ 
    if (root == NULL) 
    return newNode(point);  
    unsigned cd = depth % k; 
    if (point[cd] < (root->point[cd])) 
        root->left = insertRec(root->left, point, depth + 1); 
    else
        root->right = insertRec(root->right, point, depth + 1); 

    return root; 
} 
// Function to insert a new point with given point and return new root
Node* insert(Node *root, int point[]) 
{ 
    return insertRec(root, point, 0); 
} 

// driver 
int main() 
{ 
    struct Node *root = NULL; 
    int points[][k] = {{3, 6}, {17, 15}, {13, 15}, {6, 12}, 
                    {9, 1}, {2, 7}, {10, 19}}; 
    int n = sizeof(points)/sizeof(points[0]); 
    for (int i=0; i<n; i++) 
    root = insert(root, points[i]); 
    return 0; 
}

1 Ответ

0 голосов
/ 11 февраля 2019

Сначала не используйте <bits/stdc++.h>.Это неправильно.

Чтобы найти k ближайших элементов, вам нужно пройти по дереву так, чтобы сначала пройти через самые близкие элементы.Затем, если вам не хватает элементов, идите и пройдитесь дальше.

Я не буду писать здесь код, просто псевдокод (потому что я уже создал один долгое времяназад ): 

list l; # list of the elements, sorted by distance
heap p; # heap of nodes to traverse, sorted by distance

p.push(root)
while (!p.empty())
{
    node = p.pop(); # Get a new node
    d = distance(point, node); # compute the closest distance from the point to the node
    if(l.empty() or distance(point, l.back()) > d)
    {
        add(node->left); # iteration on subnodes
        add(node->right);
        l.push(points); # Add points from the current node
    }
    l.pop_elements(k); # pop elements to keep only k
}
...