מערכי נתונים של למידת מכונה יכולים לכלול מיליוני דוגמאות, אבל לא כל אלגוריתמי הקיבוץ מתאימים להתאמה לעומס. הרבה אלגוריתמים של קיבוץ מחושבים את הדמיון בין כל זוגות הדוגמאות, כלומר זמן הריצה שלהם גדל כמספר הריבועים של מספר הדוגמאות \(n\), שמצוין כ- \(O(n^2)\) בסימן המורכבות. \(O(n^2)\) אלגוריתמים לא מעשיים למערכי נתונים עם מיליוני דוגמאות.
לאלגוריתם k-means יש מורכבות של \(O(n)\), כלומר האלגוריתם משתנה באופן לינארי עם \(n\). זהו האלגוריתם שבו נתרכז בקורס הזה.
סוגי אשכולות
רשימה מקיפה של גישות שונות לקיבוץ מופיעה במאמר A Comprehensive Survey of Clustering Algorithms (סקירה מקיפה של אלגוריתמים לקיבוץ), Xu, D. & Tian, Y. נתונים שנתיים. Sci. (2015) 2: 165. כל גישה מתאימה במיוחד לחלוקה מסוימת של נתונים. בקורס הזה נדון בקצרה בארבעה גישות נפוצות.
קיבוץ מבוסס-נקודת מרכז
המוקד של אשכול הוא הממוצע האריתמטי של כל הנקודות באשכול. קיבוץ מבוסס-מרכז מאפשר לארגן את הנתונים באשכולות לא היררכיים. אלגוריתמים של קיבוץ שמבוססים על מרכז כובד יעילים, אבל הם רגישים לתנאים ראשוניים ולערכים חריגים. מבין השיטות האלה, השיטה k-means היא הנפוצה ביותר. כדי להשתמש בשיטה הזו, המשתמשים צריכים להגדיר את מספר מרכזי הכובד, k, והיא מתאימה במיוחד לאשכולות בגודל דומה.
אשכולות מבוססי-צפיפות
בצבירה מבוססת-צפיפות, אזורים סמוכים עם צפיפות גבוהה של דוגמאות מחוברים לצבירות. כך אפשר לגלות מספר בלתי מוגבל של אשכולות בכל צורה. ערכים חריגים לא מוקצים לאשכולות. לאלגוריתמים האלה קשה לעבוד עם אשכולות בצפיפות שונה ועם נתונים עם מאפיינים רבים.
קיבוץ מבוסס-הפצה
הגישה הזו ליצירת אשכולות מבוססת על ההנחה שהנתונים מורכבים מהתפלגויות פרובאבליסטיות, כמו התפלגויות גאוסיאניות. באיור 3, האלגוריתם מבוסס-ההפצה מקבצ את הנתונים לשלוש התפלגויות גאוסיות. ככל שהמרחק ממרכז ההתפלגות גדל, כך פוחתת ההסתברות שלפיה נקודה מסוימת שייכת להתפלגות. ההפחתה הזו באפשרות מופיעה בפסגות. אם אתם לא בטוחים בהנחה לגבי ההתפלגות הבסיסית של הנתונים, כדאי להשתמש באלגוריתם אחר.
אשכול היררכי
אשכולות היררכיים יוצרים עץ של אשכולות. לא מפתיע שצבירת עצים מתאימה במיוחד לנתונים היררכיים, כמו טקסונומיות. לדוגמה, אפשר לעיין במאמר Comparison of 61 Sequenced Escherichia coli Genomes של Oksana Lukjancenko, Trudy Wassenaar ו-Dave Ussery. אפשר לבחור כל מספר של אשכולות על ידי חיתוך העץ ברמה המתאימה.
