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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO, "Minimal Spanning Tree Construction with MetricMatrix" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 2, pp. 362-372, February 2002, doi: .
Abstract: Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_2_362/_p
Copiar
@ARTICLE{e85-d_2_362,
author={Masahiro ISHIKAWA, Kazutaka FURUSE, Hanxiong CHEN, Nobuo OHBO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimal Spanning Tree Construction with MetricMatrix},
year={2002},
volume={E85-D},
number={2},
pages={362-372},
abstract={Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.},
keywords={},
doi={},
ISSN={},
month={February},}
Copiar
TY - JOUR
TI - Minimal Spanning Tree Construction with MetricMatrix
T2 - IEICE TRANSACTIONS on Information
SP - 362
EP - 372
AU - Masahiro ISHIKAWA
AU - Kazutaka FURUSE
AU - Hanxiong CHEN
AU - Nobuo OHBO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2002
AB - Clustering is one of the most important topics in the field of knowledge discovery from databases. Especially, hierarchical clustering is useful since it gives a hierarchical view of a whole database and can be used to guide users in browsing a huge database. In many cases, clustering can be modeled as a graph partitioning problem. When an appropriate distance function between database objects is given, a database can be viewed as an edge-weighted complete graph, where vertices are database objects and weights of edges are distances between them. Then a process of MST (Minimal Spanning Tree) construction can be viewed as a process of a single-linkage agglomerative clustering process for database objects. In this paper, we propose an efficient MST construction method for a large complete metric graph, which is derived from a database with a metric distance function defined on it. Our method utilizes a metric index to reduce the number of distance calculations. The basic idea is to exclude those edges less probable to be a part of an MST by using the metric postulate. For this purpose, we introduce a new metric index named MetricMatrix. Experimental results show that our method can drastically reduce the number of distance calculations needed for MST construction in comparison with the classical method.
ER -