Seminar Clustering Algorithms

Sommersemester 2017

Übersicht

Allgemeines
Seminarleiter
Termine und Räume
Zusätzliche Unterlagen
Verweise
Fun Stuff

Aktuelles

Allgemeines

Auf dieser Seite finden Sie verschiedene Informationen zum Seminar "Clustering Algorithms", das im Sommersemester 2017 von Pascal Held und Christian Braune an der Otto-von-Guericke-Universität Magdeburg gehalten wird. Diese Seite wird im Laufe des Semesters aktualisiert.

Inhalte des Seminars

Clustering, also das unüberwachte Kategorisieren von Daten, ist ein Prozess, der in vielen Bereichen der Informatik Anwendung findet- die reine Datenanalyse ist dabei nur der offensichlichste. Viele verschiedene Klassen von Clusteringalgorithmen existieren heutzutage, die alle mehr oder weniger gut auf verschiedenen Arten von Daten funktionieren. Das Verständnis, was ein Cluster eigentlich ist, unterscheidet sich dabei von einem zum anderen Verfahren teilweise ebenso deutlich wie die Menge und Art von Vorwissen über die Daten, die als Parameter an den jeweiligen Algorithmus übergeben werden müssen.

In diesem Seminar sollen in der Gruppe verschiedene Clusteralgorithmen erarbeitet und beschrieben werden, sowie anhand von Beispielen Stärken und Schwächen der Algorithmen aufgezeigt werden. Dabei werden wir versuchen sowohl auf verschiedene Arten von Daten (statische, dynamische, ... ) einzugehen sowie verschiedene Klassen (prototypenbasiert, probabilistisch, dichtebasiert, hierarchisch, ...) von Clusteralgorithmen vorzustellen.

Voraussetzungen

Grundlagen der Informatik / Algorithmen und Datenstrukturen Kenntnisse in Vektorrechnung und Grundlagen der Stochastik sind sicherlich von Vorteil, aber nicht zwingend notwendig.

Teilnehmerkreis

Bis zu 18 Studenten der Informatik und interessierte Studierende anderer Fachrichtungen.

Alle Teilnehmer werden gebeten sich über den FIN Registration Service zu anzumelden. Sollte die Teilnehmergruppe bereits voll sein, bitte auf der Warteliste eintragen.

Seminarleiter

Bei Fragen schreibt uns einfach eine Email:

Christian Braune, cbraune@ovgu.de
Pascal Held, pheld@ovgu.de

Organisatorische Regelungen für den Teilnahmeschein

Je nach Wunsch des Studenten gibt es für das Seminar entweder 3 CP (Bachelor/Master: als wissenschaftliches Seminar) bzw. 5 oder 6 CP (Bachelor: FIN-SMK oder Master: als wissenschaftliches Seminar) (mit jeweils angepassten Anforderungen).

Anforderung 3 CP

Regelmäßige Teilnahme an den Seminarterminen
Aktive Mitarbeit während des Seminars
Halten eines Vortrags zu einem der unten genannten Themen

Anforderung 5/6 CP

Regelmäßige Teilnahme an den Seminarterminen
Aktive Mitarbeit während des Seminars
Halten eines Vortrags zu einem der unten genannten Themen
Implementierung eines Clustering-Algorithmus und Vorstellung der Funktionsweise

Beim ersten Termin werden die Themen (zu bearbeiten in 2er-Gruppen) vergeben. Wer sich zuerst angemeldet hat, darf zuerst ein Thema (s.u.) auswählen. Wer zum ersten Termin fehlt, geht evtl. leer aus, wenn sich ein Nachrücker den Platz schnappt.

Termine und Räume

	Wochentag	Zeit	Raum	Beginn	Dozent
Seminar	Dienstag	9.00-11.00	G29-336	04.04.2017	Christian Braune, Pascal Held

zurück zum Seitenanfang

Weitere Termine/Vorträge:

Thema	Termin	Vortragende
Einführung	04.04.2017	Christian, Pascal
--- frei ---	11.04.2017	--- frei ---
k-means, k-median, k-medoid, fuzzy-c-means	18.04.2017	Daniel, Philipp
hierarchisches Clustering	25.04.2017	Arne, Simon
dichtebasiertes Clustern	02.05.2017	Jan-Ole, Tetiana
probabilistisches Clustern	09.05.2017	Hans-Martin, Markus
Affinity Propagation	16.05.2017	David, John
graphbasiertes Clustern	23.05.2017	Corny, Tim
MeanShift	30.05.2017	Kilian, Lydia
Time Series Clustering	06.06.2017	Dustin, Till
TriClust	13.06.2017	Robert, Viola
Finalrunde Clustern	20.06.2017	--- alle ---
Projektvorstellung (Termin 1)	27.06.2017	Teams 1, 2, 3 und 4
Projektvorstellung (Termin 2)	04.07.2017	Teams 5, 6 und 7

zurück zum Seitenanfang

Zusätzliche Unterlagen

Api-Programmierprojekt

Ihr könnt euer Programmierprojekt entweder als Python Funktion oder als ausführbares Konsolenprogramm implementieren.

Python-Funktion

def einfaches_clustering(data, arg1, arg2, ...):
    foo()
    bar()
    dark_magic()
    return list_of_labels

def tolles_clustering_mit_visualisierung(data, arg1, arg2, ...):
    foo()
    bar()
    dark_magic()
    return list_of_labels, list_of_image_filenames

data ist dabei eine übergebene numpy-Matrix, wobei jede Spalte einem Attribut und jede Zeile einem Datenitem entspricht. Mit data[0,0] kann darauf zugegriffen werden. Alle weiteren Parameter könnt ihr beliebig wählen und uns dann entsprechend mitteilen, so dass wir die zugehörigen Eingaben im System hinterlegen können.

Wenn ihr eine Visualisierung anbieten wollt, könnt ihr diese in Grafikdateien (vorzugsweise PNG) in den temporären Ordner schreiben und die Pfade zu den Bildern als String-Liste mit zurückgeben.

Kommandozeilentool

Aufruf:

[euer Programmaufruf] [ARFF-File] [Arg1] [Arg2] ...

Den gewünschten Programmaufruf könnt ihr uns mitteilen. Die Argumente brauchen wir natürlich auch, damit wir die Oberfläche entsprechen konfigurieren können.

ARFF-Files sind CSV-Dateien mit ein paar Header Informationen. Eine Beispieldatei stellen wir gerne zur Verfügung.

Da in der letzten Spalte die Ground-Truth-Label stehen, dürft ihr diese Spalte in eurem Algorithmus natürlich nicht benutzen. ;)

erwartete Programmausgaben

Liste der Labelzuordnung (ein Label, dann neue Zeile, dann nächstes Label ...)
eventuell erzeugte Bilder mit: # Image: [Pfad]

Beispiel:

1
1
2
2
3
3
3
# Image: /tmp/foo/bar.png

Themen

Programmierprojekte:

Fuzzy-DBSCAN
Super Paramagnetic Clustering
Clusterverfahren, die auf Triangulationen beruhen
parameterfreies Clustern
...

Liste von "verbotenen" Algorithmen (im wesentlichen die, die zu den Terminen besprochen werden):

k-means, k-median, k-medoid, fuzzy-c-means
alles hierarchische, was crisp clustert
SpectralClustering
minimum-spanning-tree-clustering
Gaussian Mixture Models
Affinity Propagation
DBSCAN
OPTICS
MeanShift
TRICLUST

Bisherige Gruppen/Themen:

ID	Mitglieder	Thema
Team 1	Corny, Tim	irgendwas mit Triangulationen
Team 2	Jan-Ole, Tetiana	irgendwas mit EAs
Team 3	Arne, Dustin	FLAME
Team 4	Simon, Viola	Self-Organizing Maps
Team 5	Hans-Martin, Markus	KHOPCA clustering algorithm
Team 6	David, John	BIRCH
Team 7	Daniel, Philipp	CURE

zurück zum Seitenanfang

Fun Stuff

Verweise auf andere Webseiten

zurück zum Seitenanfang