Neuer Algorithmus liefert schnelle, hochwertige Anticlustering in großen Datensätzen

Das Anticlustering‑Problem besteht darin, eine Menge von Objekten in K gleich große Anticlusters aufzuteilen, sodass die Summe der Abstände innerhalb der Anticlusters maximiert wird. In euklidischen Räumen, wo jedes Objekt als D‑dimensionaler Feature‑Vektor dargestellt wird, wird die Distanz als quadratischer euklidischer Abstand gemessen. Das Problem ist NP‑schwer, weshalb effiziente Lösungsansätze besonders gefragt sind.

Anticlustering findet breite Anwendung in den Sozialwissenschaften, etwa in der Psychologie, sowie in der K‑Fold‑Cross‑Validation, wo jede Falte die gesamte Datenmenge repräsentieren soll. Auch bei der Bildung von Mini‑Batches für den Gradientenabstieg in neuronalen Netzen und bei der balancierten K‑Cut‑Partitionierung von tabellarischen Daten spielt es eine zentrale Rolle. Besonders in der maschinellen Lernpraxis, wo Millionen von Objekten und sehr große K‑Werte vorkommen, sind skalierbare Algorithmen unverzichtbar.

Aktuelle Verfahren reichen von exakten Methoden, die nur kleine Instanzen lösen können, bis hin zu heuristischen Ansätzen wie fast_anticlustering, dem derzeit skalierbarsten Verfahren. Der neue Assignment‑Based Anticlustering‑Algorithmus (ABA) wurde entwickelt, um diese Grenzen zu überwinden und auch bei sehr großen Datensätzen effizient zu arbeiten.

Eine umfangreiche Rechenstudie zeigt, dass ABA sowohl in der Lösungsqualität als auch in der Laufzeit fast_anticlustering übertrifft. Der Algorithmus skaliert problemlos auf Instanzen mit Millionen von Objekten und Hunderttausenden von Anticlusters und erreicht dabei Laufzeiten, die fast_anticlustering nicht erreichen kann. Damit stellt ABA die beste Methode für balancierte K‑Cut‑Partitionierungen von tabellarischen Daten dar.