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

רקע מתמטי - אלגוריתם סטנדרטי

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

שלב הקצאה

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

שלב עדכון

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

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

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

שיטות אתחול

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

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

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

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

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

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

תוכנות

• R (סביבת תוכנה פתוחה לחישובים סטטיסטיים, הכוללת מספר יישומים של CART, כמו rpart וחבילות randomForest).
• Weka (חבילת תוכנת קוד-פתוח חינמית לכריית נתונים שמכילה אלגוריתמים רבים).
• SciPy vector-quantization
• KNIME
• Microsoft SQL Server
• scikit-learn
• IDL Cluster, Clust_Wts
• Mathematica ClusteringComponents function
• MATLAB kmeans
• SAS FASTCLUS
• Stata kmeans
• VisuMap kMeans Clustering

ראו גם

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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