היתרונות והחסרונות של K

ניתוח קבוצות (K-means) הוא שימושי ויעיל בהרבה הקשרים של למידת מכונה, אבל יש לו כמה נקודות חולשה ייחודיות.

היתרונות של k-means

קל יחסית להטמיע.

מתאים לקבוצות נתונים גדולות.

תמיד מתכנסת.

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

התאמה חלקה לדוגמאות חדשות

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

הכללה של k-means

הטמעה פשוטה של k-means יכולה להיתקל בקשיים בטיפול באשכולות עם צפיפות וגדלים שונים. בצד ימין של איור 1 מוצגים האשכולות שצפויים להופיע, ובצד שמאל מוצגים האשכולות שהוצעו על ידי k-means.

איור 1: דוגמה ל-k-means לא כללי.

כדי לשפר את הביצועים באשכולות לא מאוזנים כמו אלה שמוצגים באיור 1, אפשר להכליל, כלומר להתאים, את k-means. באיור 2 מוצגות שלוש מערכי נתונים שונים שמקובצים בשתי הכללות שונות. מערך הנתונים הראשון מציג ניתוח k-means ללא הכללה, ואילו השני והשלישי מאפשרים לגודל האשכולות להשתנות.

איור 2: קיבוץ לפי k-means עם הכללה ובלי הכללה.

הקורס הזה לא מכיל הסבר על הכללתה של k-means, אבל מי שמעוניין יכול לקרוא את המאמר Clustering – k-means Gaussian mixture models של Carlos Guestrin מאוניברסיטת Carnegie Mellon.

החסרונות של k-means

$k$ צריך לבחור באופן ידני.

התוצאות תלויות בערכים הראשוניים.

אם הערך של $k$נמוך, אפשר לצמצם את התלות הזו על ידי הפעלת k-means כמה פעמים עם ערכים ראשוניים שונים ובחירה בתוצאה הטובה ביותר. ככל ש- $k$עולה, צריך להשתמש בהזרמה של זרעים ל-k-means כדי לבחור צנטרואידים ראשוניים טובים יותר. לסקירה מלאה על הזרמה של זרעים ל-k-means, אפשר לעיין במאמר A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm (מחקר השוואתי של שיטות יעילות לטעינה ראשונית של אלגוריתם הקיבוץ K-means) מאת M. Emre Celebi, ‏ Hassan A. Kingravi ו-Patricio A. Vela.

קשה לקבץ נתונים בגדלים ובצפיפויות שונים בלי להכליל.

קשה לקבץ חריגים באשכול.

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

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

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

קללת המאפיינים והקיבוץ הספקטרלי

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

איור 3: הדגמה של קללת המאפיינים. בכל תרשים מוצגים המרחקים בין 200 נקודות אקראיות.

אפשר למנוע את הירידה בביצועים באמצעות קיבוץ ספקטרלי, שמוסיף לאלגוריתם שלבים לפני הקיבוץ. כדי לבצע קיבוץ ספקטרלי:

1. הפחתת המאפיינים של נתוני המאפיינים באמצעות PCA.
2. הקרנה של כל נקודות הנתונים למרחב המשנה בעל הממדים הנמוכים יותר.
3. מקצים את הנתונים במרחב המשנה הזה לאשכולות באמצעות האלגוריתם שבחרתם.

למידע נוסף על קיבוץ ספקטרלי, אפשר לעיין במאמר A Tutorial on Spectral Clustering מאת Ulrike von Luxburg.

מונחי מפתח:

• אשכול ספקטרלי