Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Algorithmen zum k-Center Problem
Hallo,
beim k-Center Problem wird für eine Punktmenge z.B. im 2d-Raum k Kreise bestimmt, welche die Punkte beinhalten (die Vereinigungsmenge dieser Kreise beinhaltet alle Punkte, d.h. jeder Punkt ist in mindestens einem Kreis enthalten), wobei der Radius dieser Kreise so klein wie möglich sein soll.
Algorithmen für das k-Center Problem werden in Anwendungen wie Data Mining, maschinelles Lernen und Bildverarbeitung verwendet.
Doch frage ich mich, inwieweit diese Algorithmen heute noch eingesetzt werden und nicht bereits durch andere Algorithmen für Clustering abgelöst wurden welche evtl. effizienter arbeiten.
Besonders im Bereich maschinelles Lernen und Bildverarbeitung stellt sich mir die Frage, inwieweit es sich heute noch lohnt, sich umfassender mit Algorithmen zum k-Center Problem zu beschäftigen?
Jede Meinung wäre willkommen
Das sind sehr allgemeine Fragen zu sehr speziellen Problemen. Das k-Center-Problem ist NP-Vollständig und damit gibt es vermutlich keine Algorithmen, die es effizient lösen. Es gibt natürlich unterschiedliche Algorithmen, die bei speziellen Problemstellungen effizienter arbeiten als andere - genau da kann man viel Zeit investieren und nach effizienten Algorithmen suchen. Manche Firmen zahlen sicher viel Geld dafür.
Ich würde also sagen ja, es kann sich durchaus lohnen, sich damit zu befassen. Für Ruhm, Ehre oder Geld muss man aber gut darin sein.
Das ist eher eine sehr spezielle Frage auf ein sehr allgemeines problem
ich habe Eure Antworten leider erst heute entdeckt.
Es würde sich um ein mögliches Abschlussthema handeln in welchem ich mehrere Algorithmen zur
Lösung des k-center Problems implementieren und anschließend bewerten müßte.
Zu welchen Bereich zählt eurer Meinung nach das k-center Problem, mehr zum maschinellen Lernen
da es ja ein Clusterverfahren (ähnlich wie k-means) ist oder mehr zur Algorithmischen Geometrie?
Oder kann man die Frage so beantworten das es zu den maschinellen Lernverfahren zählt, zur
Lösung aber Methoden aus der Algorithmischen Geometrie verwendet werden können?
Nur mal so zur generellen Einordnung dieses Problems.
Die Problembeschreibung von k-means impliziert nicht maschinelles Lernen. Es ist eine simple Minimierungsfunktion.
Der k-means-Algorithmus dagegen ist eine Variante von expectation–maximization (EM), eine Methode aus der Statistik, die dem maschinellen Lernen zugeordnet wird.
Ja, aber wie sieht es mit den anderen Cluster-Algorithmen aus, zählen diese ebenfalls zum maschinellen Lernen? Bisher habe ich jeden Algorithmus welcher eine gegebene Datenmenge in Cluster zerlegt zum maschinellen Lernen gezählt, hier eben zu den unüberwachten Lernverfahren.
In deinem Eingangspost hast du geschrieben “Anwendungen wie Data Mining, maschinelles Lernen und Bildverarbeitung”. Ich postuliere, maschinelles Lernen ist keine Anwendung, sondern eine Methodik. Welche Methodik am besten für k-center geeignet ist, ist mir nicht bekannt. Maschinelle Lernmethoden wie EM erscheinen zumindest opportun. Aber es könnte ja auch sehr gut mit anderen Optimierungsverfahren funktionieren, z.B. Metaheuristiken. Das kann ich mir persönlich sehr gut vorstellen, da der Suchraum kontinuierlich und klar eingegrenzt ist.
Wenn dann würde ich eher dafür postulieren das Maschinelles Lernen ein selbstadaptiver Algorithmus ist, Methodik finde ich zu allgemein.
Das kannst du postulieren wie du lustig bist.
2 „Gefällt mir“