מה זה אשכולות k?

כפי שצוין קודם, הרבה אלגוריתמים של קיבוץ לא מתאימים למערכי הנתונים שבהם נעשה שימוש בלמידת מכונה, שבדרך כלל מכילים מיליוני דוגמאות. לדוגמה, אלגוריתמים של אשכול היררכי אגרגטיבי או מפצל בוחנים את כל הצמדים של הנקודות, והמורכבות שלהם היא $O(n^2 log(n))$ ו- $O(n^2)$, בהתאמה.

הקורס הזה מתמקד ב-k-means כי הוא מתאים לעומס לפי $O(nk)$, כאשר $k$הוא מספר האשכולות שבחר המשתמש. האלגוריתם הזה מקבצ נקודות ל-$k$ אשכולות על ידי צמצום המרחקים בין כל נקודה לבין מרכז הכובד של האשכול שלה (ראו איור 1).

כתוצאה מכך, ה-k-means מתייחס לנתונים כאל מספר התפלגויות עגולות בערך, ומנסה למצוא אשכולות שתואמים להתפלגויות האלה. אבל נתונים מהעולם האמיתי מכילים חריגים וצבירים שמבוססים על צפיפות, ויכול להיות שהם לא יתאימו להנחות שעומדות בבסיס של k-means.

אלגוריתם של קיבוץ לפי k-means

האלגוריתם פועל לפי השלבים הבאים:

1. מציינים שער ראשוני ל- $k$, שאפשר לשנות מאוחר יותר. בדוגמה הזו, בוחרים ב- $k = 3$.

2. בוחרים באופן אקראי $k$ נקודות מרכזיות.

   

   איור 1: ניתוח k-means בשלב האתחול.

3. מקצים כל נקודה למרכז המסה הקרוב ביותר כדי לקבל $k$ אשכולות ראשוניים.

   

   איור 2: אשכולות ראשוניים.

4. לכל אשכול, מחשבים מרכז כובד חדש על ידי חישוב המיקום הממוצע של כל הנקודות באשכול. החצים באיור 4 מציגים את השינוי במיקומי מרכזי הכובד.

   

   איור 3: מרכזי מסה מחושבים מחדש.

5. מקצים מחדש כל נקודה למרכז המסה החדש הקרוב ביותר.

   

   איור 4: אשכולות אחרי ההקצאה מחדש.

6. חוזרים על שלבים 4 ו-5, ומחשבים מחדש את מרכזי הכובד ואת החברות באשכול עד שהנקודות לא משנות אשכולות. במקרה של מערכי נתונים גדולים, אפשר לעצור את האלגוריתם לפני ההתכנסות על סמך קריטריונים אחרים.

מכיוון שמיקומי מרכזי הכובד נבחרים בהתחלה באופן אקראי, יכול להיות שהמודל k-means יחזיר תוצאות שונות באופן משמעותי בהרצות עוקבות. כדי לפתור את הבעיה הזו, מריצים את k-means כמה פעמים ובוחרים את התוצאה עם מדדי האיכות הטובים ביותר. (נתאר את מדדי האיכות בהמשך הקורס). כדי לבחור מיקומי מרכז כובד ראשוניים טובים יותר, תצטרכו גרסה מתקדמת של k-means.

אין צורך בהבנה מעמיקה של המתמטיקה, אבל למקרה שזה מעניין אתכם, k-means הוא מקרה מיוחד של אלגוריתם למיקסום הציפיות. הערות על הנושא מ-UPenn.