Evaluating the Quality of Clustering Algorithms using Cluster Path Lengths

Faraz Zaidi 1, 2, * Guy Melançon 2, 1
* Auteur correspondant
2 GRAVITE - Graph Visualization and Interactive Exploration
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : Many real world systems can be modeled as networks or graphs. Clustering algorithms that help us to organize and understand these networks are usually referred to as, graph based clustering algo- rithms. Many algorithms exist in the literature for clustering network data. Evaluating the quality of these clustering algorithms is an impor- tant task addressed by different researchers. An important ingredient of evaluating these clustering techniques is the node-edge density of a clus- ter. In this paper, we argue that evaluation methods based on density are heavily biased to networks having dense components, such as social net- works, but are not well suited for data sets with other network topologies where the nodes are not densely connected. Example of such data sets are the transportation and Internet networks. We justify our hypothesis by presenting examples from real world data sets. We present a new metric to evaluate the quality of a clustering algorithm to overcome the limitations of existing cluster evaluation techniques. This new metric is based on the path length of the elements of a cluster and avoids judging the quality based on cluster density. We show the effectiveness of the proposed metric by comparing its results with other existing evaluation methods on artificially generated and real world data sets.
Type de document :
Communication dans un congrès
10th Industrial Conference, ICDM, 2010, Berlin, Germany. Springer, 6171/2010, pp.42-56, 2010, ADVANCES IN DATA MINING. APPLICATIONS AND THEORETICAL ASPECTS. 〈10.1109/BIBM.2010.5706558〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00542690
Contributeur : Faraz Zaidi <>
Soumis le : vendredi 3 décembre 2010 - 12:36:50
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : vendredi 4 mars 2011 - 03:29:04

Fichier

icdm2010ClusterPathCamera.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Faraz Zaidi, Guy Melançon. Evaluating the Quality of Clustering Algorithms using Cluster Path Lengths. 10th Industrial Conference, ICDM, 2010, Berlin, Germany. Springer, 6171/2010, pp.42-56, 2010, ADVANCES IN DATA MINING. APPLICATIONS AND THEORETICAL ASPECTS. 〈10.1109/BIBM.2010.5706558〉. 〈inria-00542690〉

Partager

Métriques

Consultations de la notice

411

Téléchargements de fichiers

1370