Cluster-Cluster-

Projekt

Präsentiert von Dominik Henn & Torben Pastucham Seminar für Computerlinguistik der Uni Heidelberg

Datum: 28.01.2002

Was ist Cluster-X ?Was ist Cluster-X ?

ist eine Windows-Anwendung

Cluster-X...

fasst thematisch ähnliche Dokumente zu Clustern zusammen

verwendet hierzu den Oh!™ Algorithmus(Oh!™ = Orphan Hunting! & Topic Merging)

ermöglicht die Ausweitung einer bool´schen Suche

EntwicklungEntwicklung

Cluster-X wurde in C++ unter MS-Windows entwickeltEs wurde Wert auf kurze Laufzeiten gelegt

Verwendete Bibliotheken:

- MFC für die GUI- selbst entwickelte Matrix- & Vektorklassen

Die ArchitekturDie Architektur

Korpus IRPreProcess

DocTermMatrix

TermList

DocumentListIRCluster

Cluster

IRBoolSearch

SearchResults ClusterView

DisplayEngine

Die TechnikDie Technik

Oh!™ basiert auf dem k-Means AlgorithmusDieser wird durch verschiedene Elemente erweitert

TopicMerging OrphanHunting

k-Means

Oh!™

k-Meansk-Means

Erzeuge k ZV

Ordne DV zufälligden ZV zu

Berechne neue ZV

Ordne DV den jeweilsähnlichsten ZV zu

Neuzuordnung?Ja

Termination

Nein

ZV = Zentroidvektor

DV = Dokumentvektor

1

2 2

1 1

( , )

n

i ii

n n

i ii i

d cd c

sim d cd c

d c

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

1

n

ii

dc

n

FFFFFFFFFFFFFF

Orphan HuntingOrphan Hunting

Topic MergingTopic Merging

Oh!™-AlgorithmusOh!™-AlgorithmusErzeuge n ZV

(n = Anz. der Dok.)

Ordne jedem ZV genaueinen DV zu

Berechne neue ZV

Ordne DV den jeweilsähnlichsten ZV zu

Neuzuordnung?Ja

TerminationNein

ZV mit nureinem zug. DV?

Ordne DV dem nächstähnlichen ZV zu

Lösche dennun leeren ZV

Übertrage DV inähnlichen ZV

Lösche den nunleeren ZV

Exisitieren2 ähnliche ZV?

Nein

Ja

Ja

Nein

Diese beiden Vorgänge werden nur ausgeführt, wenn eine

festgesetzte Ähnlichkeit

überschritten wird

DatenstrukturenDatenstrukturen

Für Cluster-X wurden 3 angepasste Datentypen verwendet1) CVector<TYPE>

(Hilfsklasse für Operationen mit Vektoren)

2) CMatrix<TYPE>(Speicherung der Zentroiden)

3) CSparseDataMatrix<TYPE>(Speicherung der Dokument-Term-Matrix)

SparseDataMatrixSparseDataMatrix

CSparseDataMatrix<TYPE> ist auf Speicherung von Matrizen mit überwiegend nicht verwendeten Elementen zugeschnitten (0-Werte)

Originalmatrix

0 0 0 0 0 0 2 0

3 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 4 0 0 0 0 0

1 7 0 2 0

2 1 2 3 1

1 4 0 1 0

1 3 0 4 0

SparseDataMatrix

Beispielersparniss:Dokument-Term-Matrix (Bibel-Korpus)Originalmatrix: >10.000 KByte SparseDataMatrix: 880 KByte

Nun zur Praxis...Nun zur Praxis...

1) 1) Cluster-X starten

Ihre Optionen:Ihre Optionen:

2) 2) Zigarettenpause

Probleme & ToDoProbleme & ToDo

Extrem hohe Speicherbelastung Temporäre Berechnung der ZV Latent Semantic Indexing (SVD)

Korpusabhängige Idealparameterevtl. mashine learning Methoden (user feedback)

Parameterabhängige Laufzeiten (worst case: O(n²))

Lösung N/A (algorithmusinhärent)

The End...The End...

Dozentin: Priv.-Doz. Dr. Karin Haenelt

Ort: Seminar für Computerlinguistik / Uni Heidelberg

Veranstaltung: Information Retrieval (WS2001/02)