Árvores k-d

As árvores k-d (diminutivo de k-dimensional tree) são estruturas de dados de partição do espaço, para organização de pontos distribuídos em um espaço de \(k\) dimensões. São muito úteis em aplicações envolvendo chaves multidimensionais, e são um caso especial de árvores geradas por particionamento binário do espaço (BSP - Binary Space Partition).

Cada chave associada a um nó de uma árvore k-d é um ponto multidimensional, e cada nó de uma árvore k-d, cria uma divisão no hiperplano que divide o espaço em duas partes, onde pontos à esquerda do hiperplano são representados na sub-árvore esquerda, e os pontos à direita do hiperplano são representados na árvore à esquerda.

A formação de uma k-d tree cria uma árvore binária de pesquisa, onde a cada nível da árvore, uma dimensão da chave multidimensional é utilizada como critério de comparação, por exemplo, para um conjunto de pontos em um espaço tri-dimensional, representado por coordenadas cartesianas \((x,y,z)\), no primeiro nível da árvore, é utilizada a coordenada \(x\) para a divisão dos pontos, no segundo nível, a coordenada \(y\), no terceiro nível, a coordenada \(z\), e no quarto nível, novamente a coordenada \(x\), e assim por diante (Figura 1).

Árvore k-d Árvore k-d

Criação da árvore k-d

Existem várias formas de criar uma árvore k-d, porém a forma geral deve seguir duas restrições:

  • a cada nível da árvore, uma das dimensões é utilizada para dividir os dados (como explicado anteriormente);

  • os pontos devem ser inseridos selecionando o ponto mediano em relação à dimensão sendo avaliada (em uma situação ideal, onde todos os pontos estão disponíveis na criação da árvore).

Utilizando estas restrições, a árvore gerada é balanceada. Embora, para muitas aplicações, esta característica seja desejada, existem algumas aplicações onde uma árvore balanceada não é a estrutura ótima.

Para selecionar o ponto mediano do conjunto de pontos pode-se ordenar os pontos, utilizando a dimensão da chave apropriada. Como não é necessária uma ordenação completa, o uso de um algoritmo de seleção eficiente, como o quickselect é uma alternativa bastante eficaz em relação à ordenação total.

Note que o algoritmo deve agrupar todos os elementos com chaves iguais do mesmo lado da divisão, logo, essa divisão pode não ser realizada exatamente ao meio, e ao utilizar um algoritmo como o quickselect os devidos ajustes devem ser feitos. Uma alternativa, é utilizar o quickselect associado ao esquema de [particionamento de Dikjstra,] que agrupa os elementos iguais de forma contígua, facilitando a divisão correta da árvore.

Como a cada seleção os pontos são dividos ao meio, são executadas \(O(\lg N)\) iterações do algoritmo de seleção, que tem custo \(O(N)\), logo, a criação da árvore k-d, seguindo estes passos, tem custo de \(O(N\lg N)\), e a árvore criada será uma árvore balanceada.

O Algoritmo 1 realiza a criação de uma árvore k-d a partir de um conjunto de dados.

Criação de uma árvore k-d.

kdtree_create_node(points, dim):
    dim = dim % points[0].key.length
    median = points.length / 2
    partial_sort(points, median, dim)
    node = new Node(points[median], dim)
    node.left = kdtree_create_node(points[0:median], dim + 1)
    node.right = kdtree_create_node(points[median:points.length], dim + 1)  
    return node

Adição de elementos

A adição de novos elementos em uma árvore k-d (Algoritmo 2) segue o mesmo príncipo das árvores binárias de pesquisa, com a diferença que o valor comparado não é toda a chava, mas uma dimensão específica por nível da árvore. Uma vez que a busca chega a um ponto onde o novo valor pode ser inserido, um novo nó é criado.

Adição de elementos em uma árvore k-d.

add_node(node, level, key):
    if node == null
       return new Node(key)
    dim = level % key.dimensions
    if key[dim] <= node.key[dim]
        node.left = add_node(node.left, level + 1, key)
    else
        node.right = add_node(node.right, level + 1, key)

A inserção de elementos dessa forma, faz com que não seja garantido o balanceamento da árvore, o que pode diminuir a sua eficiência. Embora seja possível balancear árvores k-d, as rotações simples, aplicadas às árvores binárias de pesquisa auto-balanceáveis não são aplicáveis, pois não levam em consideração que cada nível da árvore é dividido utilizando uma dimensão diferente da chave.

Remoção de elementos

A remoção de elementos deve, assim como a rotação, levar em consideração que a chave é multi-dimensional, e para isso existem duas abordagens. A abordagem mais simples, é retirar toda a sub-árvore da qualo o nó a ser removido é a raiz, e adicionar os elementos que não devem ser removidos novamente (utilizando o Algoritmo 2). Outra abordagem é encontrar um elemento que possa substituir o elemento a ser removido e substituí-lo pelo elemento encontrado.

Nesta segunda abordagem, se o elemento a ser removido é uma folha, basta removê-lo da árvore. Caso contrário, procura-se o elemento com o maior valor para a dimensão que o elemento a ser removido divide a árvore, na sua sub-árvore à esquerda, ou o elemento com o menor valor para a mesma dimensão, na sub-árvore ào direita. Desta forma, a remoção é semelhante à remoção de elementos em uma [árvore binária de pesquisa].

Procura por um ponto específico

A busca por um ponto específico em uma árvore k-d é semelhante à busca em uma [árvore binária de pesquisa], no entanto, é necessário levar em consideração qual a dimensão o nó sendo avaliado está divindo a árvore (Algoritmo 3).

Busca em uma árvore k-d.

search(reference):
    search(reference, kdtree.node, 0)

search(reference, node, dimension):
    if reference == node.data
        return node
    if node == null
        return null
    d = (dimension + 1) % kdtree.dimensions
    if reference[dimension] <= node.data[dimension]
        return search(reference, node.left, d)
    else
        return search(reference, node.right, d)

Procura do vizinho mais próximo

O problema da procura dos vizinhos próximos (NN de Nearest Neighbor), é encontrado em diversas áreas de aplicação, incluindo reconhecimento de padrões, visão computacional, bancos de dados, robótica, sistemas de recomendação, e correção ortográfica, entre outras. O objetivo é, dado um ponto, encontrar o ponto mais próximo deste ponto em uma coleção de pontos.

Devido a forma coma a árvore k-d armazena os pontos, ele provê uma estrutura muito eficiente para a pesquisa por dados próximos geograficamente. A proximidade geográfica pode ser calculada a partir de uma medida de distância, como a distância euclidiana (baseada no teorema de Pitágoras), a distância de Manhatthan (Taxicab Geometry), ou a ortodromia (Great-circle distance, que utiliza a fórmula de Haversine). Baseado no cálculo de distância escolhido, é possível encontrar o ponto mais próximo de um outro ponto arbitrário com eficiência, utilizando as propriedades da árvore k-d para eliminar grandes porções do espaço de busca.

O processo de busca pelo vizinho mais próximo (Algoritmo 4) inicia a partir da raiz da árvore, e procura, na árvore pelo ponto de referência até que se encontre um ponto igual ao ponto de referência, pois nenhum outro ponto pode estar mais próximo que um ponto com distância "zero", ou até que se atinja uma folha da árvore. Esta folha será o "ponto candidato", ou seja, a resposta mais provável, até o momento.

Ao encontrar a folha que possívelmente seja a resposta correta, o algoritmo retorna, em direção à raiz da árvore, comparando a distância do melhor ponto até o momento, com a distância do ponto atual, caso o ponto atual seja mais próximo do ponto de referência, o ponto atual é considerado o novo ponto candidato.

Para verificar se o outro lado da árvore deve ser analizado, é comparada a melhor distância atual com a distância entre o ponto de referência e o hiperplano formado pela dimensão que o ponto atual divide o espaço. Ou seja, o valor absoluto da diferença da coordenada utilizada para dividir a árvore no ponto atual como a mesma coordenada do ponto de referência deve ser menor ou igual a melhor distância até o momento, e, nesse caso, o outro lado da árvore deve ser analisado, recursivamente, com o mesmo algoritmo.

Procura pelo ponto mais próximo em um árvore k-d.

closest(reference):
    d, node = search(reference, kdtree.node, 0)
    return (d, node.data)

closest(point, node, dimension):
    if point == node.data
        return (0,node)

    dim = (dimension + 1) % kdrtee.dimensions
    d = distance(refence, node.data)

    if point.left == null and point.right == null
        return  (d, node)
    else
        if point[dimension] <= node.data[dimension]
            dist, c = closest(reference, node.left, dim)
        else
            dist, c = closest(reference, node.right, dim)

    if abs(point[dimension] - node.data[dimension]) <= dist
        # Search other side of the tree.
        if point[dimension] <= node.data[dimension]
            dist, c = closest(reference, node.right, dim)
        else
            dist, c = closest(reference, node.left, dim)

    if d < dist
        return (d, node)
    else
        return (dist, c)

O custo médio para localizar o ponto mais próximo em uma árvore k-d com pontos uniformemente distribuídos no espaço é \(O(\lg N)\).

Procura dos k vizinhos mais próximos

Uma variante comum do problema da procura do vizinho mais próximo, é a procura pelos \(k\) vizinhos mais próximos, conhecida como k-nearest neighbors (kNN). Nesta variação, não apenas um vizinho mais próximo é encontrado, mas um conjunto dos \(k\) pontos mais próximo ao ponto de referência.

O Algoritmo 4 pode ser modificado para realizar a comparação da distância com o ponto candidato mais distante do conjunto de resposta até o momento, e se a distância for menor (ou, se o conjunto de resposta ainda não apresenta o número mínimo de pontos), adicionar o ponto atual ao conjunto de resposta.

O custo médio para localizar o ponto mais próximo em uma árvore k-d com pontos uniformemente distribuídos no espaço é \(O(k\lg N)\), onde \(k\) é o número de elementos desejados.

Outras aplicações das árvores k-d

Um prbolema semelhante a procura do vizinho mais próximo, é a procura por todos os pontos dentro de um raio pré-definido. Utilizando uma árvore k-d, e um algoritmo semelhante ao já apresentado, é possível obter um algoritmo bastante eficiente para este fim.

Outra aplicação é a pesquisa por dados dentro de intervalos definidos em mais de uma dimensão. Por exemplo, encontrar todos os registros de usuários com idades entre 30 e 40 anos, e salário entre 2.000,00 e 5.000,00. Como a árvore k-d divide os dados em múltiplas dimensões, este tipo de pesquisa pode ser executada de forma bastante eficiente.

A maldição da dimensionalidade

Quando uma árvore k-d é criada sobre dados que possuem muitas dimensões, a divisão dos pontos pode não ser muito eficiente, e as pesquisas na árvore exigirem a comparação de todos os elementos. Como regra geral, para obter uma árvore k-d eficiente, o número de elementos armazenados deve ser bem maior que o número de dimensões. Podemos ter como regra geral que \(N \gg 2^k\).