דף זה תורגם על ידי Cloud Translation API.

הרצת האלגוריתם של האשכול

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

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

כפי שמוצג, K-e אתם מוצאים אשכולות עגולים בערך. באופן עקרוני, פירוש הדבר הוא שכשמדובר ב-King, כלומר, נתונים מתייחסים בפועל למספר של חלוקות בקירוב מעגליות, ומנסים למצוא אשכולות המתאימים לחלוקות האלה. בפועל, יש בנתונים ממצאים יוצאי דופן וייתכן שהם לא יתאימו למודל הזה.

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

אלגוריתם K במשמעות של אשכול

כדי לקבץ נתונים באשכולות $k$ , k הוא הצעדים הבאים:

תרשים של K-הכוונה באתחול — **איור 1: משמעות k – אתחול.**

שלב ראשון

האלגוריתם בוחר באופן אקראי מרכז לכל אשכול. בדוגמה שלנו, אנחנו בוחרים $k$ תוך 3, ולכן האלגוריתם בוחר באופן אקראי שלושה.

שלב שני

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

חישוב מחדש של צנטריוד — **איור 3: חישוב מחדש של מרכזים.**

שלב שלישי

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

שלב רביעי

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

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

כדי להציג את המשוואה המתמטית, לוחצים על סמל הפלוס

ב- $n$ דוגמאות שמוקצות ל- $k$ אשכולות, צריך לצמצם את מרחק המרחקים של הדוגמאות לאנטואציות. איפה:

$A_{nk} = 1$ כשהדוגמה $n$מוקצית לאשכול $k$, ו-0 אחר
$\theta_k$ מרכז את האשכול $k$

אנחנו רוצים לצמצם את הביטוי הבא: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ בכפוף ל: $$A_{nk} \in \{0,1\} \forall n,k$$ וגם $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ כדי למזער את הביטוי ביחס למרכזים של האשכול $\theta_k$, יש לקבוע את הנגזר ביחס ל- $\theta_k$ ולשווה אותו ל-0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ הנובר הוא הסכום של כל המרחקים בסנטרים-אשכולים באשכול. המכנה הוא מספר הדוגמאות באשכול. לכן, המרכז באשכול $\theta_k$ הוא הממוצע של המרחקים באשכול של סנטרוס באשכול. לכן התברר.

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

סיכום

פירוש התוצאות