|
|
|
Im Rahmen von Forschungsprojekten zu Knowledge Disovery und Data Mining in sehr großen
Datenbanken wurden verschiedene Algorithmen entwickelt, die sog.. "arbitrary
shaped clusters" finden. "Arbitrary shaped clusters" sind
Mengen von dicht beieinander liegenden Punkten in einem mehrdimensionalen Raum. Das
Ergebnis der meisten dieser Algorithmen sind also Punktmengen.
Derartige Mengen hochdimensionaler Punkte sind jedoch äußerst unanschaulich und bieten
keine Möglichkeit, effizient zu überprüfen, ob andere Punkte z.B. innerhalb einer
bestimmten Menge liegen. Daher sind einfachere Beschreibungen der Punktmengen
wünschenswert.
Um eine solche einfache Beschreibung zu berechnen sollen Genetische Algorithmen (GAs)
eingesetzt werden. Das Prinzip der GAs orientiert sich an der Darwinschen Theorie der
Evolution aufgrund der Qualität bzgl. der Umwelt. Eine große Anzahl von Individuen
entwickelt sich und pflanzt sich fort, wobei das Bessere sein Erbgut öfter einbringen
darf. Dieses Prinzip wird auf die Informatik übertragen und simuliert. In unserem
konkreten Fall werden also eine große Menge von Beschreibungen durch die genetischen
Operationen (Kopieren, Mutationen, Verschmelzen etc.) berechnet, wobei eine Beschreibung
um so öfter als Grundlage verwendet wird, je besser sie die Punktmenge beschreibt.
In Rahmen dieser Projektarbeit sollen eine für GAs geeignete Repräsentation von
Beschreibungen der Mengen entwickelt werden, sowie entsprechenden Anpassungen der
genetischen Operationen.
Gegeben sei eine Punktmenge (Cluster) in einem mehrdimensionalen Raum. Diese einzelnen Punktmengen werden anfangs durch Beschreibungen (Rechtecke, Kreise, Ellipsen, Polygone...) durch eine Initialisierung am Bestmöglichsten beschrieben. Diese Beschreibungen sind sicherlich zum großen Teil noch sehr ungenau, jedoch besser als einfach eine zufällig generierte Position der Beschreibungen. Danach wird die Fitness dieser Beschreibungen untersucht (z.B.wieviele Punkte liegen ausserhalb der Beschreibung). Somit überleben die besten Beschreibungen und durchlaufen dann den Prozeß der Genetischen Algorithmen (Kopieren, Mutationen, Verschmelzen etc.) und die nächste Generation wird dann eine bessere Beschreibung der Punktmenge sein, wobei wiederum nur die Besten überleben und den nächsten Prozeß durchlaufen. Dies wird solange fortgeführt bis eine gewisse kleine Fehlermenge nicht mehr überschritten wird.
| Bearbeiter | Egon Gruber |
| Betreuer | Markus Breunig |
| Arbeitsabschnitt | Zeitbedarf |
Einarbeitung in:
|
2 Wochen |
| Algorithmusdesign | 3 Wochen |
| Kodierung und Implementierung | 3 Wochen |
| Testen des Codes und Optimierung des Algorithmus | 3 Wochen |
| Test des Gesamtsystems und Anwendung mit realen Daten | 2 Wochen |
| Auswertung der Experimente | 1 Woche |
DBS