Clustering Algorithmus (k-Means) mit großen Datensätzen?

Hallo,

ich möchte einen Cluster-Algorithmus programmieren. Der größte Datensatz enthält knapp 200.000 Vektoren der Länge 10. Bekomme ich bei dieser Größe Speicher- oder Performance-Probleme?

Ich muss ja in jedem Iterationsschritt die Mittelpunkte und die Zuordnung neu berechnen.
gespeichert werden die Daten in einer Liste.
Vielleicht hat jemand schon Erfahrungen damit gesammelt?

Naja ich poste mal den Code der zwei wesentlichen Funktionen:

schlechtes Coding

Diese Funktion berechnet die Mittelpunkte (als Durchschnitt) der zusammengehörenden Punkte. Per Linq transponiere ich die Daten und kann die Mittelpunkte einfach per .Average() berechnen.

Die zweite Funktion ordnet die Punkte den Clustern zu:

schlechtes Coding

Dabei wird die (quadrierte) Euklidische Distanz genommen. Über diese beiden Funktionen wird iteriert.

Für 6000 Datenpunkte mit je 10 Einträgen stellt das kein Problem dar (6 Sek.). Problematisch wird es dann ab 50.000 Datenpunkte mit je 10 Einträgen (>10 Min.). Bei 200.000 Datenpunkten beträgt die Laufzeit über 1 Std.. Anzahl der Zentren variiert zwischen 3 und 20 je nach Größe des Datensatzes.

Ich hatte versucht die beiden Funktionen zu parallelisieren, leider lief der Code dann nicht mehr durch.

Hi doemi,

also ich kenne den k-Means-Algorithmus nicht gut genug, um hier grundsätzliche Fragen über die Herangehensweise zu diskutieren. Was mir aber auffällt, ist, daß du zwar mit Linq arbeitest, aber immer alle Ergebnisse in Listen speicherst. Du solltest mal überlegen, an welchen Stellen du dir die Zwischenspeicherung sparen kannst, um dadurch einerseits Speicher zu sparen und andererseits Rechenleistung (z.B. für den GC, der die ganzen Listen auch wieder freigeben muß).

Christian

Ok, danke für den Hinweis.

Wenn ich z. B.

var rowList = daten.SelectMany(x => zuordnung[daten.IndexOf(x)] == i)
                              .Select((x, m) => new { V = x, Index = m })
                              .GroupBy(x => (x.Index + 1) % werte[0].Count)
                              .Select(g => g.Select(x => x.V).ToList())
                              .ToList();

schreibe, akzeptiert er das nicht. Warum?

Edit: Vom Prinzip her ist der Algorithmus recht einfach:

1. Startzentren vorgeben
2. Für jeden Punkt den Abstand zu allen (Start-)Zentren ausrechnen und demjenigen Zentrum mit dem geringstem Abstand zuordnen
3. Für die in 2. gebildeten Cluster die neuen Zentren als Durchschnitt aller Datenpunkte des jeweiligen Clusters berechnen.
4. Weiter mit 2. solange sich die Zuordnung ändert.

Leider versteh ich nicht ganz was deine Verschachtelte Select anweisung in der Ersten Funktion macht. Und ich bin auch mit dem Algorithmus nicht vertraut.

Jedoch kannst du das selbe mit diesem Code erreichen (spart dir einmal durchIterieren und eine Liste)

        private List<List<decimal>> Get_Centers(List<List<decimal>> data, List<int> mapping, int number)
        {
            var centers = new List<List<decimal>>();

            for (int i = 0; i < number; i++)
            {
                var values = data.Where(conditioner => mapping[data.IndexOf(conditioner)] == i);

                var averages = values.SelectMany(x => x)
                              .Select((x, m) => new { V = x, Index = m })
                              .GroupBy(x => (x.Index + 1) % values.ElementAt(0).Count)
                              .Select(g => g.Select(x => x.V))
                              .Select(selector => selector.Average()).ToList();

                centers.Add(averages);
            }
            return centers;
        }

Das Problem das ich sehe ist das IndexOf wieder durch die gesamte Collection iteriert:

Die Zweite funktion könnte so aussehen:

        private List<int> Mapping(List<List<decimal>> data, List<List<decimal>> centers)
        {
            var result = new List<int>();

            foreach (var point in data)
            {
                var collection = centers.Select(x => Euclidean_Distance(x, point));
                decimal min = collection.Min();

                int count = collection.Where(conditioner => conditioner == min).Count();

                result.Add(count);
            }
            return result;
        }

oder so: ob das jedoch sinn macht ist fraglich

        private List<int> Mapping(List<List<decimal>> data, List<List<decimal>> centers)
        {
            return data
                .Select(dataSelector => centers.Select(centerSelector => Euclidean_Distance(centerSelector, dataSelector))
                .Where(conditioner => conditioner == centers.Select(centerSelector => Euclidean_Distance(centerSelector, dataSelector)).Min()).Count()).ToList();
        }

Was mir hier aufgefallen ist das du für jeden schleifendurchlauf wieder das Minimum in der Collection suchst.

Danke für deine Antwort.

Die Select-Anweisung transponiert die List<List<>>, damit ich .Average() anwenden kann. Wenn man so will berechnet Average() ja den Durchschnitt der Zeilen, ich möchte aber den Durchschnitt der Spalten berechnen (für jede Koordinate den Durchschnitt).

Das Minimum muss ich jedesmal berechnen weil ich wissen will zu welchem Zentrum der jeweilige Punkt minimalen Abstand hat.

Edit: Kennt jemand eine Lösung, in der ich IndexOf vermeiden kann? Um die Punkte zuzuordnen brauche ich ja den Index. Vielleicht durch ein Dictionary?

Hallo doemi,

für den Schritt, zu einem/jedem Vektor, das nächste Zentrum zu finden, siehe Aus großer Menge von vieldimensionalen Vektoren die ähnlichsten finden.

herbivore

Hallo,

@Console32: Die von dir gepostete Funktion scheint noch nicht so ganz richtig zu sein (ich brauche nicht die Anzahl der Elemente die gleich dem min sind, sondern den Index des ersten Elementes das gleich dem min ist). Bleibt noch das Problem mit IndexOf, vielleicht kann man das durch ein Dictionary ersetzen, d.h. zu jedem Punkt gibt es eine Clusternummer?

Hallo,

wenn ich den Algorithmus nicht schneller bekomme...

...kann ich eventuell CUDA benutzen um den Algorithmus auf der GPU zu rechnen? Weiß leider nicht wie das geht. Wahrscheinlich muss ich irgendwas von CUDA installieren oder?

Es gibt doch schon fertige Bibliotheken für nummerische Berechnungen. Unter Fast. Faster …. Performance Comparison: C# (ILNumerics), FORTRAN, MATLAB and numpy – Part II | ILNumerics Developer Blogs findest du z.B. eine KMeans-Implementierung mit ILNumerics.

Danke für den Hinweis. ILNumerics klingt interessant. D.h. ich muss meine Daten lediglich in eine Matrix

ILInArray<double> X

packen und die kMeansClust Methode aufrufen.

Lediglich zwei Dinge stören mich an dieser Implementierung:

1. Das Distanzmaß ist fix
2. Ich muss eine maximale Anzahl an Iterationen vorgeben

Vielleicht könnte ich ILNumerics in meine beiden Funktionen einbauen?

Habe gerade gesehen, dass die Lizenz für ILNumerics recht teuer ist. Somit fällt diese Alternative weg.

Hat jemand noch eine Idee wie ich das Problem mit IndexOf und den unzähligen Iterationen durch die Listen lösen kann?

Hi doemi,

da das von dir beschriebene Vorgehen

2. Für jeden Punkt den Abstand zu allen (Start-)Zentren ausrechnen und demjenigen Zentrum mit dem geringstem Abstand zuordnen
3. Für die in 2. gebildeten Cluster die neuen Zentren als Durchschnitt aller Datenpunkte des jeweiligen Clusters berechnen.

natürlich datenzentriert ist, kannst du es auch komplett als LINQ-Sequenz formulieren.

Das ist nicht nur kürzer, lazy-er (weniger temporäre Zwischenlisten), sondern ermöglicht am Ende durch ein simples .AsParallel() auch die parallele Ausführung ohne weiteren Aufwand.

Hier der Code:

List<List<decimal>> Get_Centers(List<List<decimal>> data, List<int> mapping, int number)
{
	return Get_Centers(data, mapping, number,
						(p, q) => p.Zip(q, Decimal.Add).ToList(), // Addition von zwei Datenpunkten
						(p, divisor) => p.Select(x => x / divisor).ToList()); // Skalierung eines Datenpunkts
}

// T ist hier dein d-dimensionaler Punkt
List<T> Get_Centers<T>(List<T> data, List<int> mapping, int number, Func<T, T, T> add, Func<T, decimal, T> divide)
{
	return data
		.AsParallel()
		.Select((point, index) => new {Point = point, Index = index})
		.GroupBy(indexed_point => mapping[indexed_point.Index], // nach dem Cluster-Index gruppieren
				indexed_point => indexed_point.Point,
				(cluster_index, cluster) => divide(cluster.Aggregate(add), cluster.Count())) // Cluster-Mittelpunkt berechnen
		.ToList();
}

List<int> Mapping(List<List<decimal>> data, List<List<decimal>> centers)
{
	return data
		.AsParallel()
		.Select(point => centers.MinIndex(x => Euclidean_Distance(x, point))) // Index des naehsten Clusters
		.ToList();
}

wobei noch folgende Hilfs-Extensionmethode benötigt wird:

static class Extensions
{
	public static int MinIndex<T>(this IEnumerable<T> xs, Func<T, decimal> valueSelector)
	{
		decimal min_value = 0;
		int min_index = -1;
		int index = 0;
		foreach (T x in xs)
		{
			decimal value = valueSelector(x);
			if (value < min_value || min_index == -1)
			{
				min_value = value;
				min_index = index;
			}
			index++;
		}
		return min_index;
	}
}

Für 6.000 Datensätze mit 10-dimensionalen Punkten und 20 gewünschten Clustern, bekomme ich folgende Zeiten:

Bisher: 13,3137736s
Linq: 1,0174442s [COLOR]ohne AsParallel
[/color]
PLinq: 0,3275538s [COLOR]mit AsParallel
[/color]

Die Zahlen gelten für eine KMeans-Iteration - bei dir auch so? Man muss ja eigentlich zahlreiche durchführen! Aber bleiben wir mal bei einer Iteration.
Bei 200.000 Datensätzen habe ich folgende Zeiten:

Bisher: abgebrochen, da zu lange
Linq: 34,3662025s [COLOR]ohne AsParallel
[/color]
PLinq: 7,0759584s [COLOR]mit AsParallel
[/color]

Ich hoffe, ich habe keinen Fehler gemacht. Aber du müsstest mal die Algorightmus-Ergebnisse verifizieren.

beste Grüße
zommi

Danke.

Edit: Code funktioniert.