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

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

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

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

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

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

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

תיאור כללי של האלגוריתם[עריכת קוד מקור | עריכה]

האלגוריתם עובד בהינתן קבוצה של תצפיות , כאשר כל תצפית היא וקטור ממשי היכול להיות בעל מספר ממדים. מטרת המודל היא לחלק את 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[1].

האלגוריתם[עריכת קוד מקור | עריכה]

Nuvola apps edu mathematics blue-p.svg

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

האלגוריתם הבסיסי[עריכת קוד מקור | עריכה]

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

שלב ההקצאה[עריכת קוד מקור | עריכה]

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

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

שלב העדכון[עריכת קוד מקור | עריכה]

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

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

שיטות אתחול שונות[עריכת קוד מקור | עריכה]

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

שיקולים ביישום המודל[עריכת קוד מקור | עריכה]

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

יתרונות וחסרונות[עריכת קוד מקור | עריכה]

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

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

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

יישומים מוכרים בתוכנות חופשיות[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A K-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100&ndash, 108
  2. ^ R: K-Means Clustering, stat.ethz.ch
  3. ^ sklearn.cluster.KMeans — scikit-learn 0.19.2 documentation, scikit-learn.org