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
클러스터링은 데이터베이스 지식 발견 분야에서 가장 중요한 주제 중 하나입니다. 특히, 계층적 클러스터링은 전체 데이터베이스에 대한 계층적 보기를 제공하고 사용자가 거대한 데이터베이스를 검색할 때 안내하는 데 사용할 수 있으므로 유용합니다. 많은 경우 클러스터링은 그래프 분할 문제로 모델링될 수 있습니다. 데이터베이스 개체 간의 적절한 거리 함수가 주어지면 데이터베이스는 정점이 데이터베이스 개체이고 가장자리의 가중치가 이들 사이의 거리인 가장자리 가중치 완전 그래프로 볼 수 있습니다. 그렇다면 MST(Minimal Spanning Tree) 구축 과정은 데이터베이스 객체에 대한 단일 연결 응집 클러스터링 과정으로 볼 수 있다. 본 논문에서는 메트릭 거리 함수가 정의된 데이터베이스로부터 파생된 대규모 완전한 메트릭 그래프를 위한 효율적인 MST 구성 방법을 제안합니다. 우리의 방법은 거리 계산 횟수를 줄이기 위해 미터법 지수를 활용합니다. 기본 아이디어는 미터법 가정을 사용하여 MST의 일부일 가능성이 낮은 가장자리를 제외하는 것입니다. 이를 위해 우리는 메트릭 매트릭스. 실험 결과는 우리의 방법이 기존 방법에 비해 MST 구축에 필요한 거리 계산 횟수를 대폭 줄일 수 있음을 보여줍니다.
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.
부
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
부
@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},}
부
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 -