A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Minimal Spanning Tree Construction with MetricMatrix Construção mínima de árvore geradora com MetricMatrix

Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Clustering é um dos tópicos mais importantes no campo da descoberta de conhecimento em bancos de dados. Especialmente, o clustering hierárquico é útil porque fornece uma visão hierárquica de um banco de dados inteiro e pode ser usado para orientar os usuários na navegação em um banco de dados enorme. Em muitos casos, o clustering pode ser modelado como um problema de particionamento de grafos. Quando uma função de distância apropriada entre objetos de banco de dados é fornecida, um banco de dados pode ser visto como um gráfico completo ponderado por arestas, onde os vértices são objetos de banco de dados e os pesos das arestas são as distâncias entre eles. Então, um processo de construção MST (Minimal Spanning Tree) pode ser visto como um processo de clustering aglomerativo de ligação única para objetos de banco de dados. Neste artigo, propomos um método eficiente de construção de MST para um grande gráfico métrico completo, que é derivado de um banco de dados com uma função de distância métrica definida nele. Nosso método utiliza um índice métrico para reduzir o número de cálculos de distância. A ideia básica é excluir aquelas arestas com menor probabilidade de fazerem parte de um MST usando o postulado métrico. Para este propósito, introduzimos um novo índice métrico denominado Matriz Métrica. Resultados experimentais mostram que nosso método pode reduzir drasticamente o número de cálculos de distância necessários para a construção do MST em comparação com o método clássico.

Publicação
IEICE TRANSACTIONS on Information Vol.E85-D No.2 pp.362-372
Data de publicação
2002/02/01
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Bases de dados

autores

Palavra-chave