Return to search

Aceleração de uma variação do problema k-nearest neighbors / Acceleration of a variation of the K-nearest neighbors problem

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T13:07:50Z
No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-25T14:42:09Z (GMT) No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-25T14:42:09Z (GMT). No. of bitstreams: 2
Dissertação - Jorge Peixoto de Morais Neto - 2014.pdf: 1582808 bytes, checksum: 3115f942e2c8a9cf83601835af3af1c5 (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2014-01-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Let M be a metric space and let P be a subset of M. The well known k-nearest neighbors
problem (KNN) consists in finding, given q 2 M, the k elements of P with are closest to
q according to the metric of M. We discuss a variation of KNN for a particular class of
pseudo-metric spaces, described as follows. Let m 2 N be a natural number and let d be
the Euclidean distance in Rm. Given p 2 Rm:
p := (p1; : : : ; pm)
let C (p) be the set of the m rotations of p’s coordinates:
C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm􀀀1)g
we define the special distance de as:
de(p;q) := min
p02C (p)
d(p0;q):
de is a pseudo-metric, and (Rm;de) is a pseudo-metric space. The class of pseudo-metric
spaces under discussion is
f(Rm;de) j m 2 N:g
The brute force approach is too costly for instances of practical size. We present a more
efficient solution employing parallelism, the FFT (fast Fourier transform) and the fast
elimination of unfavorable training vectors.We describe a program—named CyclicKNN
—which implements this solution.We report the speedup of this program over serial brute
force search, processing reference datasets. / Seja M um espaço métrico e P um subconjunto de M. O conhecido problema k vizinhos
mais próximos (k-neareast neighbors, KNN) consiste em encontrar, dado q 2 M, os k
elementos de P mais próximos de q conforme a métrica de M. Abordamos uma variação
do problema KNN para uma classe particular de espaços pseudo-métricos, descrita a
seguir. Seja m 2 N um natural e seja d a distância euclidiana em Rm. Dado um vetor
p 2 Rm:
p := (p1; : : : ; pm)
seja C (p) o conjunto das m rotações das coordenadas de p:
C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm􀀀1)g
definimos a distância especial de como:
de(p;q) := min
p02C (p)
d(p0;q):
de é uma pseudo-métrica, e (Rm;de) é um espaço pseudo-métrico. A classe de espaços
pseudo-métricos abordada é
(Rm;de) j m 2 N:
A solução por força bruta é cara demais para instâncias de tamanho prático. Nós apresentamos
uma solução mais eficiente empregando paralelismo, a FFT (transformada rápida
de Fourier) e a eliminação rápida de vetores de treinamento desfavoráveis. Desenvolvemos
um programa—chamado CyclicKNN—que implementa essa solução. Reportamos
o speedup desse programa em comparação com a força bruta sequencial, processando
bases de dados de referência.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3687
Date29 January 2014
CreatorsMorais Neto, Jorge Peixoto de
ContributorsMartins, Wellington Santos, Longo, Humberto José, Foulds, Leslie Richard, Longo, Humberto José, Rodrigues, Rosiane de Freitas, Silva, EdCarlos Domingos da
PublisherUniversidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG)
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG
Rightshttp://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess
Relation-3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571

Page generated in 0.0027 seconds