אלגוריתם 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 בשנת 1975/1979 בכתב עת Fortran.

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

Nuvola apps edu mathematics blue-p.svg

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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