נבחן במהירות את הסוגים של אלגוריתמים באשכול ומתי כדאי לבחור כל אחד מהם.
כשאתם בוחרים אלגוריתם של אשכולות, עליכם לקחת בחשבון אם האלגוריתם מותאם למערך הנתונים. למערכי נתונים בלמידה חישובית יכולות להיות מיליוני דוגמאות, אבל לא כל האלגוריתמים של קיבוץ הנתונים מתרחבים ביעילות. אלגוריתמים של אשכולות רבים פועלים על ידי חישוב הדמיון בין כל זוג הדוגמאות. פירוש הדבר הוא שזמן הריצה שלהם הולך וגדל בכיכר של מספר הדוגמאות \(n\), שמכונה \(O(n^2)\) בסימון מורכבות. \(O(n^2)\) האלגוריתמים אינם מעשיים כאשר מספר הדוגמאות הוא במיליונים. הקורס מתמקד באלגוריתם k-medium, שכולל מתחם של \(O(n)\). כלומר, האלגוריתם לינארי בהתאם ל- \(n\).
סוגי הקיבוץ
יש כמה גישות לאשכולות. רשימה חלקית של התוצאות: סקר מקיף של אלגוריתמים של אשכולות Xu, D. וטיאן, י. א. נתונים. מדע בדיוני (2015) 2: 165. כל גישה מתאימה במיוחד להפצת נתונים מסוימת. בהמשך תוכלו למצוא דיון קצר על ארבע גישות נפוצות, שמתמקדות באשכולות המבוססים על מרכז ובאמצעים של K.
אשכול המבוסס על מרכז
אשכולות המבוססים על צנטריוד מארגנים את הנתונים לאשכולות היררכיות, בניגוד לאשכולות היררכיות המוגדרות בהמשך. K-=המשמעות של k-=הוא האלגוריתם הנפוץ ביותר לאשכולות בסנטרואיד. אלגוריתמים המבוססים על סנטרואידים הם יעילים אך רגישים בתנאים הראשוניים ובחריגות שלהם. בקורס הזה מתמקדים באלגוריתמים המבוססים על K, כי אלגוריתם של אשכולות יעיל, אפקטיבי ופשוט.
אשכול מבוסס צפיפות
אשכולות מבוססי דחיסות מקשרים בין אזורים עם צפיפות דוגמה גבוהה לאשכולות. זה מאפשר התפלגות שרירותית, כל עוד אפשר לחבר אזורים צפופים. האלגוריתמים האלה מקשים על נתונים בעלי דחיסות שונות ומאפיינים גבוהים. מלבד זאת, העיצוב של האלגוריתמים האלה לא מקצה חריגות לאשכולות.
אשכול מבוסס הפצה
הגישה הזו של אשכולות מבוססת על חלוקה, למשל הפצות גאוס. באיור 3, האלגוריתם המבוסס על הפצה מקבץ את הנתונים לשלוש התפלגויות גאוסיאניות. ככל שהמרחק ממרכז ההפצה עולה, ההסתברות לכך שנקודה שייכת להתפלגות יורדת. התדרים מראים שירידה בהסתברות. אם אינכם יודעים מהו סוג ההפצה בנתונים שלכם, עליכם להשתמש באלגוריתם אחר.
אשכול היררכי
אשכולות היררכיות יוצר עץ של אשכולות. אשכולות היררכיות, באופן לא מפתיע, מתאימים לנתונים היררכיים, כמו טקסונומיות. כדי לראות דוגמה, אפשר לעיין בהשוואה בין 61 הרצפים של Escherichia coli Genums. דוגמה: אוקסנה לוקז'נקו, טרודי וואסנאר ודייב אוסארי. כמו כן, יתרון נוסף הוא שאפשר לבחור כל מספר של אשכולות על ידי חיתוך העץ ברמה המתאימה.
