אלגוריתם k-מרכזים

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

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

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

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

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

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

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

האלגוריתם עובד בהינתן קבוצה של תצפיות $(x_{1},x_{2},...,x_{n})$, כאשר כל תצפית היא וקטור ממשי היכול להיות בעל מספר ממדים. מטרת המודל היא לחלק את n התצפיות לk אשכולות, על מנת למזער את סכום המרחקים בין התצפיות בתוך האשכול.

האלגוריתם מאפשר להתמודד עם נתונים ללא התפלגות מוגדרת או ללא סיווג (קלספיקציה) וגם עם מצבים שבהם בתצפית מסוימת חסרות חלק מהמדידות של המשתנים.

האלגוריתם מאפשר לבצע למידה בלתי מונחית (Unsupervised learning) של סיווגים שונים של הנתונים.

היסטוריה

את המונח K-means טבע ג'יימס מקווין בשנת 1967, אף על פי שמקורות הרעיון היו קודם לכן אצל הוגו שטיינהאוס בשנת 1957.

האלגוריתם הבסיסי הוצע לראשונה על ידי סטוארט לויד בשנת 1957 כטכניקה של Pulse-code modulation אף על פי שהוא לא פרסם זאת מחוץ למעבדות בל עד שנת 1982.

בשנת 1965 פרסם אי. וו. פורגי (E.W Forgy) את אותה השיטה, ולכן היא נקראת לעיתים גם לויד-פורגי. גרסה יעילה יותר הוצעה ופורסמה על ידי הארטיגן ווונג (Hartigan and Wong) בשנת 1979 ב-Journal of the Royal Statistical Society.

האלגוריתם

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

האלגוריתם הבסיסי

נגדיר קבוצה ראשונית של k מרכזים $m_{1}^{(1)}...m_{k}^{(1)}$ ואז האלגוריתם ינוע לסירוגין בין שני שלבים הבאים:

שלב ההקצאה

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

למעשה נוודא שכל $x_{p}$ מקיים $S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},$ כך שלכל $x_{p}$ יותאם רק $S^{(t)}$ אחד גם אם יותר מאחד מתאים.

שלב העדכון

נחשב את המרכזים מחדש על פי המרחק האוקלידי מהנקודות שהוקצו אליהם (למעשה פורמלית נעדכן כל מרכז על פי הכלל הבא:$m_{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}$

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

שימוש בפונקציית מרחק שונה אחרת מאשר מרחק אוקלידי עלולה לגרום לאלגוריתם לא להתכנס^{[דרוש מקור]}.

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

שיטות אתחול שונות

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

שיקולים ביישום המודל

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

יתרונות וחסרונות

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

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

האלגוריתם תמיד ימצא פתרון כלשהו ולעיתים הפתרון אינו יציב או מייצג.

יישומים מוכרים בתוכנות חופשיות

• R (שפת תכנות) - מכילה מספר מימושים וגרסאות של האלגוריתם
• Scikit-learn - חבילה של שפת התכנות פייתון המשמשת ללמידת מכונה. מכילה גם היא מספר מימושים וגרסאות של האלגוריתם.

ראו גם

• למידה חישובית
• בעיית k המרכזים

קישורים חיצוניים

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

• אלגוריתם k-מרכזים (K-Means) סרטון הסבר ביוטיוב.