AlgoVerse

خوشه‌بندی k-میانگین

نقطه‌ها را به k خوشه تقسیم می‌کند: هر نقطه به نزدیک‌ترین مرکز می‌پیوندد و هر مرکز به میانگین نقطه‌هایش می‌رود، تا وقتی هیچ نقطه‌ای خوشه‌اش را عوض نکند. هزینه هر دور کم می‌شود، ولی جواب ممکن است بهینه‌ی موضعی باشد.

n نقطه داریم و می‌خواهیم آن‌ها را به k خوشه تقسیم کنیم و برای هر خوشه یک مرکز بگذاریم، طوری که مجموع مربع فاصله‌ی هر نقطه تا مرکز خوشه‌اش کمینه شود. پیدا کردن جواب بهینه NP-سخت است.

ادامه‌ی توضیح ↓
ورودی:
P 8×2 · k=2خروجی PDF

هشت نقطه در دو گروه روشن؛ با k = ۲ و شروع از دو نقطه‌ی اول (که هر دو در یک گروه‌اند)، مرکزها در دو سه دور جای درستشان را پیدا می‌کنند.

  1. def k_means(P, k):
  2. # P: points (x, y). Lloyd's algorithm, starting from the first k points as centres so the run is deterministic.
  3. n = len(P)
  4. if k > n:
  5. return None
  6. centres = [[P[i][0], P[i][1]] for i in range(k)]
  7. rows = [[i + 1, P[i][0], P[i][1], "·"] for i in range(n)] # for the picture: point, x, y, cluster
  8. cluster = [-1] * n
  9. rounds = 0
  10. changed = True
  11. while changed:
  12. changed = False
  13. rounds = rounds + 1
  14. # Assignment step: every point joins its nearest centre.
  15. for i in range(n):
  16. best = 0
  17. for c in range(k):
  18. if dist2(P[i], centres[c]) < dist2(P[i], centres[best]):
  19. best = c
  20. if best != cluster[i]:
  21. cluster[i] = best
  22. changed = True
  23. rows[i][3] = best + 1
  24. # Update step: every centre moves to the mean of its points.
  25. for c in range(k):
  26. members = [P[i] for i in range(n) if cluster[i] == c]
  27. if members:
  28. centres[c] = [round(sum(p[0] for p in members) / len(members), 2),
  29. round(sum(p[1] for p in members) / len(members), 2)]
  30. cost = round(sum(dist2(P[i], centres[cluster[i]]) for i in range(n)), 2)
  31. return cluster
  34. def dist2(p, q):
  35. return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

ناوردا: مجموع مربع فاصله‌ی نقطه‌ها تا مرکزشان هیچ دوری بیشتر نمی‌شود؛ چون تعداد تقسیم‌بندی‌ها متناهی است، الگوریتم تمام می‌شود.

شروع اجرا

centres—
cost—

جدول هنوز خالی است.

متغیرهای محلی

k2

نارنجی = در همین گام عوض شد

P list

[1, 1][2, 1][1, 2][2, 2][8, 8][9, 8][8, 9][9, 9]

Call stack

  1. k_means()خط 1
گام ۱ از ۵۴۰
خط سیاه = round_done · خط نارنجی = گام کلیدیassign: 0/10 · move: 0/6 · round_done: 0/3
    توضیح

    مسئله

    n نقطه داریم و می‌خواهیم آن‌ها را به k خوشه تقسیم کنیم و برای هر خوشه یک مرکز بگذاریم، طوری که مجموع مربع فاصله‌ی هر نقطه تا مرکز خوشه‌اش کمینه شود. پیدا کردن جواب بهینه NP-سخت است.

    الگوریتم لوید

    با k مرکز اولیه شروع کن (اینجا k نقطه‌ی اول، تا اجرا تکرارپذیر باشد)، و این دو گام را تکرار کن:

    1. انتساب: هر نقطه به خوشه‌ی نزدیک‌ترین مرکز برود.
    2. به‌روزرسانی: هر مرکز به میانگین نقطه‌های خوشه‌اش برود.

    هر گام هزینه را کم می‌کند یا ثابت نگه می‌دارد (میانگین، نقطه‌ای است که مجموع مربع فاصله‌ها را کمینه می‌کند). وقتی هیچ نقطه‌ای خوشه‌اش را عوض نکند، تمام است.

    محدودیت

    جواب به مرکزهای اولیه بستگی دارد و ممکن است فقط بهینه‌ی موضعی باشد (پیش‌تنظیم «بهینه‌ی موضعی»). در عمل چند بار با شروع‌های مختلف اجرا می‌کنند، یا مرکزهای اولیه را هوشمندانه انتخاب می‌کنند (k-means++).

    ورودی

    هر سطر P یک نقطه (x, y) است و k تعداد خوشه‌ها.