License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06061.4
URN: urn:nbn:de:0030-drops-5985
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/598/
Go to the corresponding Portal

Cilibrasi, Rudi ; Vitany, Paul M. B.

A New Quartet Tree Heuristic for Hierarchical Clustering

pdf-format:
06061.VitanyiPaulB.Paper.598.pdf (0.2 MB)

Abstract

We present a new quartet heuristic for
hierarchical clustering
from a given distance matrix.
We determine a dendrogram (ternary tree)
by a new quartet
method and a fast heuristic to implement it.
We do not assume that there is a true ternary tree that generated the
distances and which we with to recover as closeley as possible.
Our aim is to model the distance matrix as faithfully as possible
by the dendrogram. Our algorithm is essentially
randomized hill-climbing, using
parallellized Genetic Programming, where
undirected trees evolve in a random walk
driven by a prescribed fitness function.
Our method is capable of handling up to 60--80
objects in a matter of hours, while no existing quartet heuristic
can directly compute a quartet tree of more than about 20--30 objects
without running for years.
The method is implemented and available as public software
at www.complearn.org. We present applications in many areas
like music, literature, bird-flu (H5N1) virus clustering, and automatic
meaning discovery using Google.

BibTeX - Entry

@InProceedings{cilibrasi_et_al:DagSemProc.06061.4,
  author =	{Cilibrasi, Rudi and Vitany, Paul M. B.},
  title =	{{A New Quartet Tree Heuristic for Hierarchical Clustering}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6061},
  editor =	{Dirk V. Arnold and Thomas Jansen and Michael D. Vose and Jonathan E. Rowe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/598},
  URN =		{urn:nbn:de:0030-drops-5985},
  doi =		{10.4230/DagSemProc.06061.4},
  annote =	{Keywords: Genetic programming, hierarchical clustering, quartet tree method}
}

Keywords: Genetic programming, hierarchical clustering, quartet tree method
Collection: 06061 - Theory of Evolutionary Algorithms
Issue Date: 2006
Date of publication: 07.07.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI