כפי שצוין קודם, אלגוריתמים רבים של אשכולות לא מותאמים למערכי הנתונים שבהן נעשה שימוש בלמידת מכונה, שיש להן לעיתים קרובות מיליוני דוגמאות. לדוגמה, אלגוריתמים של אשכולות היררכיים מחלקים או אגרגטיביים בוחנים את כל הצמדים של נקודות ובמורכבות של \(O(n^2 log(n))\) וגם \(O(n^2)\), בהתאמה.
הקורס הזה מתמקד ב-k-כלומר כי הוא מדורג כ- \(O(nk)\), ו- \(k\) הוא מספר האשכולות שהמשתמש בחר. האלגוריתם הזה מקבץ נקודות \(k\) אשכולות על ידי צמצום המרחקים בין כל נקודה את מרכז האשכול (ראו איור 1).
כתוצאה מכך, k-כלומר מתייחס לנתונים ביעילות שהם מורכבים מכמה ומנסה למצוא אשכולות שמתאימים להפצה דיגיטלית. אבל נתונים מהעולם האמיתי מכילים חריגים חריגים ואשכולות שמבוססים על צפיפות ועשויים לא להתאים להנחות שבבסיסן k-כלומר.
אלגוריתם קיבוץ לאשכולות k-
האלגוריתם מבצע את השלבים הבאים:
עליך לספק ניחוש ראשוני עבור \(k\), ואפשר לשנות אותו מאוחר יותר. בשביל זה לדוגמה, אנחנו בוחרים ב- \(k = 3\).
בוחרים מרכזי \(k\) באופן אקראי.
איור 1: המשמעות של k באתחול. צריך להקצות כל נקודה למרכז העיר הקרוב ביותר כדי לקבל \(k\) אשכולות ראשוניים.
איור 2: אשכולות ראשוניים. חשבו מרכז חדש לכל אשכול באמצעות המיקום הממוצע של את כל הנקודות באשכול. החיצים באיור 4 מראים את השינוי במיקומי מרכזי נתונים.
איור 3: מרכזים מחושבים מחדש. מקצים מחדש כל נקודה למרכז החדש הקרוב ביותר.
איור 4: אשכולות אחרי הקצאה מחדש. חזרה על שלבים 4 ו-5, וחישוב מחדש של מרכזים וחברות באשכול, עד נקודות כבר לא משנות אשכולות. במקרה של מערכי נתונים גדולים, אפשר לעצור את האלגוריתם לפני ההתכנסות על סמך קריטריונים אחרים.
מכיוון שמיקומי המרכז נבחרים באקראי, המשמעות היא k- יחזירו תוצאות שונות באופן משמעותי בהפעלות עוקבות. כדי לפתור את הבעיה בעיה, מריצים את k-כמה פעמים ובוחרים את התוצאה עם האיכות הטובה ביותר מדדים. (נתאר את מדדי האיכות בהמשך הקורס). צריך המשמעות של גרסה מתקדמת של k-לבחור מיקומים ראשוניים טובים יותר.
אומנם אין צורך בהבנה עמוקה של המתמטיקה, אבל אלה כלומר, K-פירוש הדבר הוא מקרה מיוחד אלגוריתם למיקסום ציפיות. צפייה הערות של הרצאה בנושא מ-UPenn.