מבוא ל-K-Means

שיעור 9 מתוך 19 בקורס מבוא ללמידת מכונה של Coddy.

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

Incheol, CC BY-SA 4.0, דרך Wikimedia Commons

איך K-Means עובד?

האלגוריתם פועל לפי תהליך איטרטיבי פשוט ויעיל לחלוקת מערך נתונים ל־k אשכולות.

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

בחנו את עצמכם

השיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.

בחנו את עצמכם

השיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.

בחנו את עצמכם

השיעור הזה כולל חידון קצר. התחילו את השיעור כדי לענות עליו ולעקוב אחרי ההתקדמות.

אתגר

קל

קביעת מספר האשכולות האופטימלי, k, היא שלב מכריע. יש לכך שיטות שונות, כששיטת המרפק היא אחת הפופולריות ביותר.

בשיטה זו מריצים את K-means שוב ושוב עבור k=1 עד k=n. עבור כל ערך של k, מחשבים את סכום ריבועי המרחקים בתוך האשכולות (WCSS).

לכל אשכול יש מרכז, ו-WCSS הוא סכום כל המרחקים בריבוע מהמרכז.

צרו פונקציה בשם wcss שמקבלת רשימה של נקודות נתונים (מאותו אשכול) ומחזירה את ה-WCSS של האשכול. פעלו לפי השלבים הבאים:

מצאו את המרכז — המרכז הוא נקודה שמייצגת את המיקום הממוצע של כל הנקודות באשכול:

לדוגמה, הנה רשימה של שתי נקודות תלת־ממדיות: (1, 2 ,3), (4, 5, 6). המרכז הוא:
```
(1 + 4) / 2 = 2.5,
(2 + 5) / 2 = 3.5,
(3 + 6) / 2 = 4.5,
>> (2.5, 3.5, 4.5)
```
חשבו את המרחק האוקלידי בין כל נקודה למרכז
החזירו את סכום כל המרחקים חלקי מספר הנקודות

נסו בעצמכם

def euclidian_distance(point_a, point_b):
    return (sum([(point_a[i] - point_b[i])**2 for i in range(len(point_a))]))**0.5

def wcss(points):
    # כתבו כאן קוד