MST Construction with Metric Matrix for Clustering
Masahiro Ishikawa, Yi Liu, Kazutaka Furuse, Hanxiong Chen, Nobuo Ohbo · 2000
Clustering is one of the most important topics in the field of knowledge discovery from databases. Specifically, hierarchical clustering is useful because it can be used to interactively guide users in browsing a huge database. In many cases, database clustering can be modeled as a graph partitioning problem, because a database with a distance function defined on it can be regarded as an edge weighted graph. So process of MST(Minimal Spanning Tree) construction is a possible solution to this problem. In this paper, we propose an efficient MST construction method for a database with an arbitrary distance function on it. Our method utilizes a metric index to reduce the number of distance calculations needed to construct an MST. For this purpose, we introduce a new metric index named metric matrix . Experimental results show that our method can reduce the number of distance calculations needed in comparison with the classical method.