taralino

k-Means-Algorithmus

Nachdem wir das Problem eindeutig formuliert haben, wollen wir nun einen Lösungsansatz vorstellen, nämlich den k-Means-Algorithmus. Es handelt sich dabei um ein sogennantes nicht-deterministische Verfahren: Dies bedeutet, dass zufällige Entscheidungen getroffen werden, sodass ein wiederholtes Durchführen des Verfahrens zu durchaus unterschiedlichen Ergebnissen führen kann. Der genaue Ablauf ist wie folgt:

Gegeben sei ein Datensatz (eine Punktmenge) sowie die Anzahl an Clustern, in die der Datensatz aufgeteilt werden soll.

Wähle zufällig unterschiedliche Objekte (bzw. Punkte) aus dem Datensatz aus und bezeichne diese mit bis .
Bilde die Cluster bis derart, sodass für der Cluster all diejenigen Objekte (bzw. Punkte) enthält, für die am nächsten ist:

Aktualisiere bis jeweils durch die Schwerpunkte der zugehörigen Cluster:

Falls sich die Cluster (und damit die Schwerpunkte) nicht verändert haben, beende das Verfahren. Anderenfalls gehe zu Schritt 2.

Du musst nicht beunruhigt sein, fass du die mathematischen Formulierungen zuvor nicht im Detail nachvollziehen kannst: Der Algorithmus wird anhand der folgenden Anwendung schrittweise veranschaulicht.

Genauer wird ein Datensatz bestehend aus 48 Objekten (Punkten) erstellt, die unter Verwendung des k-Means-Algorithmus in Cluster aufgeteilt werden sollen. Es werden zunächst zufällig unterschiedliche Objekte (bzw. Punkte) gewählt und die zugehörigen Cluster gebildet. Anschließend kannst du den Ablauf Schritt für Schritt durchführen und die Veränderungen beobachten.

Anwendung

Veranschaulichung des k-Means-Algorithmus: Es wird ein Datensatz bestehend aus 48 Objekten (Punkten) erstellt, die in drei Cluster aufgeteilt werden sollen.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

var m = 48;
var k = 3;
var X = [];
var c = [];
var T = [];
var w = 0;

function distance(A, B) {
  var t = 0;
  for (var j = 0; j < A.length; j++) {
    var h = A[j]-B[j];
    t += h*h;
  };
  return t;
};

function random_permutation(m) {
  var x = [];
  for (var k = 0; k < m; k++) x.push(k);
  for (var i = 0; i < m; i++) {
    var j = Math.floor(m*Math.random());
    var h = x[i];
    x[i] = x[j];
    x[j] = h;
  };
  return x;
};

function init_centroids(A, k) {
  var m = A.length;
  var n = A[0].length;
  var C = [];
  var p = random_permutation(m);
  for (var i = 0; i < k; i++) {
    C.push([]);
    for (var j = 0; j < n; j++) C[i].push(A[p[i]][j]);
  };
  return C;
};

function kmeans_cluster(A, k, C) {
  var m = A.length;
  var n = A[0].length;
  var b = [];
  for (var i = 0; i < m; i++) {
    var h = [];
    for (var s = 0; s < k; s++) h.push([s,distance(A[i],C[s])]);
    h.sort(function(x,y){return x[1]-y[1];});
    b.push(h[0][0]);
  };
  return b;
};

function wcss(A, k, C) {
  var m = A.length;
  var n = A[0].length;
  var y = 0;
  for (var i = 0; i < m; i++) {
    var h = [];
    for (var s = 0; s < k; s++) h.push(distance(A[i],C[s]));
    h.sort(function(x,y){return x-y;});
    y += h[0];
  };
  return y;
};

function kmeans_step(A, k, C) {
  var m = A.length;
  var n = A[0].length;
  var b = kmeans_cluster(A, k, C);
  var D = [];
  for (var i = 0; i < k; i++) {
    D.push([]);
    for (var j = 0; j < n; j++) D[i].push(0);
  };
  var h = [];
  for (var j = 0; j < k; j++) h.push(0);
  for (var i = 0; i < m; i++) {
    for (var j = 0; j < n; j++) D[b[i]][j] += A[i][j];
    h[b[i]]++;
  };
  for (var i = 0; i < k; i++) {
    for (var j = 0; j < n; j++) if (h[i] != 0) D[i][j] /= h[i];
  };
  return {b:b, c:D};
};

function draw() {
  Canvas.clear();
  for (var i = 0; i < X.length; i++) {
    Canvas.line(X[i][0], X[i][1], c[T[i]][0], c[T[i]][1], {stroke:"red"});
  };
  for (var i = 0; i < X.length; i++) {
    Canvas.circle(X[i][0], X[i][1], 0.1, {fill:"blue"});
  };
  Canvas.text(5, -0.4, w.toFixed(2));
};

function init_data() {
  X = [];
  for (var i = 0; i < m; i++) X.push([Math.random()*10,Math.random()*10]);
};

function init() {
  c = init_centroids(X, k);
  T = kmeans_cluster(X, k, c);
  w = wcss(X, k, c);
  draw();
};

function setup() {
  Canvas.init([-0.5,10.5], [-0.7,10.5], {width:400, background:"lightgrey"});
  Button.add("points", "Neue Punkte");
  Button.add("reset", "Neustart");
  Button.add("next", "Schritt");
  init_data();
  init();
};

function on_click(id) {
  if (id == "points") {
    init_data();
    init();
  };
  if (id == "reset") {
    init();
  };
  if (id == "next") {
    var Z = kmeans_step(X, k, c);
    c = Z.c;
    T = Z.b;
    w = wcss(X, k, c);
    draw();
  };
};

</script>
</body>
</html>

Vorschau Download Kopie speichern