K-Means та DBSCAN — дві філософії кластеризації

1. Алгоритм K-Means

K-Means мінімізує внутрішньокластерну суму квадратів відстаней (інерцію) за допомогою EM-подібної ітерації Ллойда:

2. Ініціалізація K-Means++

Випадкова ініціалізація центроїдів часто призводить до поганих локальних мінімумів. K-Means++ обирає початкові центроїди з імовірністю, пропорційною квадрату відстані від уже обраних центроїдів:

3. Вибір K: метод ліктя та силует

4. Алгоритм DBSCAN

DBSCAN визначає кластери як щільні ділянки, розділені розрідженими. Два параметри: ε (радіус околу) та MinPts (поріг щільності):

5. Налаштування ε та MinPts

6. Порівняння та коли який використовувати

7. Реалізація на JavaScript

// ── K-Means ────────────────────────────────────────
function kMeans(points, K, maxIter = 300) {
  const n = points.length, d = points[0].length;
  // Ініціалізація K-Means++
  const centroids = [points[Math.floor(Math.random()*n)].slice()];
  while (centroids.length < K) {
    const dists = points.map(p => Math.min(...centroids.map(c => dist2(p, c))));
    const sum = dists.reduce((a, b) => a + b, 0);
    let r = Math.random() * sum;
    const idx = dists.findIndex(d => (r -= d) <= 0);
    centroids.push(points[idx < 0 ? n-1 : idx].slice());
  }

  let labels = new Int32Array(n);
  for (let iter = 0; iter < maxIter; iter++) {
    // E-крок: призначення
    let changed = 0;
    for (let i = 0; i < n; i++) {
      let best = 0, bestD = Infinity;
      for (let k = 0; k < K; k++) {
        const dd = dist2(points[i], centroids[k]);
        if (dd < bestD) { bestD = dd; best = k; }
      }
      if (labels[i] !== best) { labels[i] = best; changed++; }
    }
    if (!changed) break;
    // M-крок: перерахунок центроїдів
    for (let k = 0; k < K; k++) centroids[k].fill(0);
    const counts = new Int32Array(K);
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < d; j++) centroids[labels[i]][j] += points[i][j];
      counts[labels[i]]++;
    }
    for (let k = 0; k < K; k++)
      if (counts[k]) for (let j = 0; j < d; j++) centroids[k][j] /= counts[k];
  }
  return {labels, centroids};
}

// ── DBSCAN ────────────────────────────────────────
function dbscan(points, eps, minPts) {
  const n = points.length;
  const labels = new Int32Array(n).fill(-1); // -1 = невідвідано
  let cluster = 0;
  const eps2 = eps * eps;

  function neighbours(i) {
    return points.reduce((acc, p, j) =>
      (dist2(points[i], p) <= eps2 ? acc.push(j) : 0, acc), []);
  }

  for (let i = 0; i < n; i++) {
    if (labels[i] !== -1) continue;
    const nb = neighbours(i);
    if (nb.length < minPts) { labels[i] = 0; continue; } // шум (0)
    const c = ++cluster;
    labels[i] = c;
    const Q = [...nb];
    while (Q.length) {
      const q = Q.pop();
      if (labels[q] === 0) labels[q] = c; // гранична точка, перепризначити
      if (labels[q] !== -1) continue;
      labels[q] = c;
      const qNb = neighbours(q);
      if (qNb.length >= minPts) Q.push(...qNb);
    }
  }
  return labels; // 0 = шум, 1…K = ідентифікатори кластерів
}

function dist2(a, b) {
  let s = 0;
  for (let i = 0; i < a.length; i++) s += (a[i]-b[i])**2;
  return s;
}

8. HDBSCAN та спектральна кластеризація