Correlation clustering [Elektronische Ressource] / vorgelegt von Arthur Zimek

Arthur Zimek

Sujets

• Mathematics

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

Correlation Clustering
Arthur Zimek
Munc¨ hen 2008Correlation Clustering
Arthur Zimek
Dissertation
an der Fakult¨at fur¨ Mathematik, Informatik und
Statistik
der Ludwig–Maximilians–Universit¨at
Munc¨ hen
vorgelegt von
Arthur Zimek
Munc¨ hen, den 06.05.2008Erstgutachter: Prof. Dr. Hans-Peter Kriegel,
Ludwig-Maximilians-Universit¨at Munc¨ hen
Zweitgutachter: Prof. Dr. Thomas Seidl,
Rheinisch-Westf¨alische Technische Hochschule Aachen
Tag der mundlic¨ hen Prufung¨ : 30.06.2008v
Abstract
Knowledge Discovery in Databases (KDD)isthenon-trivialprocessofidenti-
fyingvalid, novel, potentiallyuseful, andultimatelyunderstandablepatterns
in data. The core step of the KDD process is the application of a Data Min-
ing algorithm in order to produce a particular enumeration of patterns and
relationships in large databases. Clustering is one of the major data mining
techniques and aims at grouping the data objects into meaningful classes
(clusters) such that the similarity of objects within clusters is maximized,
and the similarity of objects from different clusters is minimized. This can
servetogroupcustomerswithsimilarinterests,ortogroupgeneswithrelated
functionalities.
Currently,achallengeforclustering-techniquesareespeciallyhighdimen-
sional feature-spaces. Due to modern facilities of data collection, real data
sets usually contain many features. These features are often noisy or exhibit
correlations among each other. However, since these effects in different parts
ofthedatasetaredifferentlyrelevant,irrelevantfeaturescannotbediscarded
in advance. The selection of relevant features must therefore be integrated
into the data mining technique.
Since about 10 years, specialized clustering approaches have been devel-
oped to cope with problems in high dimensional data better than classic
clustering approaches. Often, however, the different problems of very differ-
ent nature are not distinguished from one another. A main objective of this
thesis is therefore a systematic classification of the diverse approaches devel-
oped in recent years according to their task definition, their basic strategy,
and their algorithmic approach. We discern as main categories the searchvi
for clusters (i) w.r.t. closeness of objects in axis-parallel subspaces, (ii) w.r.t.
common behavior (patterns) of objects in axis-parallel and (iii)
w.r.t. closeness of objects in arbitrarily oriented subspaces (so called corre-
lation cluster).
For the third category, the remaining parts of the thesis describe novel
approaches. A first approach is the adaptation of density-based cluster-
ing to the problem of correlation clustering. The starting point here is the
firstdensity-basedapproachinthisfield,thealgorithm4C.Subsequently,en-
hancementsandvariationsofthisapproacharediscussedallowingforamore
robust, more efficient, or more effective behavior or even find hierarchies of
correlation clusters and the corresponding subspaces. The density-based ap-
proach to correlation clustering, however, is fundamentally unable to solve
some issues since an analysis of local neighborhoods is required. This is a
problem in high dimensional data. Therefore, a novel method is proposed
tackling the correlation clustering problem in a global approach. Finally, a
method is proposed to derive models for correlation clusters to allow for an
interpretation of the clusters and facilitate more thorough analysis in the
corresponding domain science. Finally, possible applications of these models
are proposed and discussed.vii
Zusammenfassung
Knowledge Discovery in Databases (KDD)istderProzessderautomatischen
Extraktion von Wissen aus großen Datenmengen, das gultig, bisher unbe-¨
kannt und potentiell nutzlic¨ h fur¨ eine gegebene Anwendung ist. Der zentrale
Schritt des KDD-Prozesses ist das Anwenden von Data Mining-Techniken,
um nutzliche Beziehungen und Zusammenhange in einer aufbereiteten Da-¨ ¨
tenmenge aufzudecken. Eine der wichtigsten Techniken des Data Mining ist
die Cluster-Analyse (Clustering). Dabei sollen die Objekte einer Datenbank
in Gruppen (Cluster) partitioniert werden, so dass Objekte eines Clusters
m¨oglichst ¨ahnlich und Objekte verschiedener Cluster m¨oglichst un¨ahnlich zu
einander sind. Hier konnen beispielsweise Gruppen von Kunden identifiziert¨
werden,dieahnlicheInteressenhaben,oderGruppenvonGenen,dieahnliche¨ ¨
Funktionalit¨aten besitzen.
Eine aktuelle Herausforderung fur¨ Clustering-Verfahren stellen hochdi-
mensionaleFeature-Raumedar.RealeDatensatzebeinhaltendankmoderner¨ ¨
Verfahren zur Datenerhebung haufig sehr viele Merkmale (Features). Teile¨
dieser Merkmale unterliegen oft Rauschen oder Abh¨angigkeiten und k¨onnen
meist nicht im Vorfeld ausgesiebt werden, da diese Effekte in Teilen der Da-
tenbank jeweils unterschiedlich ausgepragt sind. Daher muss die Wahl der¨
Features mit dem Data-Mining-Verfahren verknupft¨ werden.
Seit etwa 10 Jahren werden vermehrt spezialisierte Clustering-Verfahren
entwickelt, die mit den in hochdimensionalen Feature-Raumen auftretenden¨
Problemenbesserumgehenk¨onnenalsklassischeClustering-Verfahren.Hier-
bei wird aber oftmals nicht zwischen den ihrer Natur nach im Einzelnen sehr
unterschiedlichen Problemen unterschieden. Ein Hauptanliegen der Disser-viii
tation ist daher eine systematische Einordnung der in den letzten Jahren
entwickelten sehr diversen Ansatze nach den Gesichtspunkten ihrer jeweili-¨
genProblemauffassung,ihrergrundlegendenLosungsstrategieundihreralgo-¨
rithmischen Vorgehensweise. Als Hauptkategorien unterscheiden wir hierbei
die Suche nach Clustern (1.) hinsichtlich der Nahe von Cluster-Objekten in¨
achsenparallelen Unterraumen, (2.) hinsichtlich gemeinsamer Verhaltenswei-¨
sen (Mustern) von Cluster-Objekten in achsenparallelen Unterr¨aumen und
(3.) hinsichtlich der Nahe von Cluster-Objekten in beliebig orientierten Un-¨
terraumen (sogenannte Korrelations-Cluster).¨
Fur die dritte Kategorie sollen in den weiteren Teilen der Dissertation in-¨
novativeL¨osungsans¨atzeentwickeltwerden.EinersterL¨osungsansatzbasiert
auf einer Erweiterung des dichte-basierten Clustering auf die Problemstel-
lungdesKorrelations-Clustering.DenAusgangspunktbildetdererstedichte-
basierte Ansatz in diesem Bereich, der Algorithmus 4C. Anschließend wer-
den Erweiterungen und Variationen dieses Ansatzes diskutiert, die robuste-
res, effizienteres oder effektiveres Verhalten aufweisen oder sogar Hierarchien
von Korrelations-Clustern und den entsprechenden Unterr¨aumen finden. Die
dichtebasierten Korrelations-Cluster-Verfahren konnen allerdings einige Pro-¨
bleme grundsatzlich nicht losen, da sie auf der Analyse lokaler Nachbarschaf-¨ ¨
ten beruhen. Dies ist in hochdimensionalen Feature-R¨aumen problematisch.
Daher wird eine weitere Neuentwicklung vorgestellt, die das Korrelations-
Cluster-Problem mit einer globalen Methode angeht. Schließlich wird eine
Methode vorgestellt, die Cluster-Modelle fur¨ Korrelationscluster ableitet, so
dass die gefundenen Cluster interpretiert werden konnen und tiefergehen-¨
de Untersuchungen in der jeweiligen Fachdisziplin zielgerichtet moglich sind.¨
M¨ogliche Anwendungen dieser Modelle werden abschließend vorgestellt und
untersucht.CONTENTS ix
Contents
Abstract v
Zusammenfassung vii
I Preliminaries 1
1 Introduction 3
1.1 Knowledge Discovery in Databases . . . . . . . . . . . . . . . 3
1.2 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 SampleApplicationsforClusteringinHighDimensionalData 9
2.1 Gene Expression Analysis . . . . . . . . . . . . . . . . . . . . 9
2.2 Metabolic Screening . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Customer Recommendation Systems . . . . . . . . . . . . . . 11
2.4 Text Documents. . . . . . . . . . . . . . . . . . . . . . . . . . 12
II TypicalProblemsandSolutionsinClusteringHigh
Dimensional Data 13
3 Finding Clusters in High Dimensional Data 17
4 Finding Clusters in Axis-parallel Subspaces 23
4.1 A Problem-Oriented Categorization . . . . . . . . . . . . . . . 24x CONTENTS
4.2 An Algorithmic-Oriented Categorization . . . . . . . . . . . . 25
4.3 Survey and Categorization of Existing Approaches . . . . . . . 27
4.3.1 Projected Clustering Algorithms . . . . . . . . . . . . . 27
4.3.2 Subspace Algorithms . . . . . . . . . . . . . 29
4.3.3 Hybrid Clustering Algorithms . . . . . . . . . . . . . . 31
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5 Finding Clusters Based on Patterns in the Data Matrix 37
5.1 General Aim and Basic Approaches of Pattern-based Cluster-
ing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.1.1 Constant Biclusters . . . . . . . . . . . . . . . . . . . . 40
5.1.2 Biclusters with Constant Values on Rows or Columns . 40
5.1.3 B with Coherent Values . . . . . . . . . . . . . 42
5.1.4 Biclusters with Coherent Evolutions . . . . . . . . . . . 45
5.2 Pattern Based Clustering Algorithms . . . . . . . . . . . . . . 50
5.2.1 Constant Biclusters . . . . . . . . . . . . . . . . . . . . 50
5.2.2 Biclusters with Constant Values in Ro