כריית מידע — מרחב למידה אישי

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

מהו ניתוח אשכולות?

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

למידה בלתי מפוקחת (Unsupervised Learning): סוג של למידת מכונה שבה האלגוריתם לומד מדפוסים בנתונים ללא תוויות קלט/פלט קיימות מראש. ניתוח אשכולות הוא דוגמה קלאסית לכך.

אשכול (Cluster): קבוצה של אובייקטים דומים זה לזה, ושונים מאובייקטים באשכולות אחרים.

יישומים נפוצים של ניתוח אשכולות:

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

מושגי יסוד ואלגוריתמים עיקריים

מדידת דמיון/אי-דמיון

הבסיס לכל אלגוריתם אשכולות הוא היכולת למדוד עד כמה שני אובייקטים דומים או שונים זה מזה. לרוב, אנו משתמשים במדדי מרחק:

מרחק אוקלידי (Euclidean Distance): המרחק ה"ישר" בין שתי נקודות במרחב רב-ממדי. נפוץ מאוד.
מרחק מנהטן (Manhattan Distance): סכום ההבדלים המוחלטים בין הקואורדינטות. מכונה גם "מרחק עיר בלוקים".
מרחק קוסינוס (Cosine Similarity): מודד את זווית הוקטורים, נפוץ בנתוני טקסט (כמו וקטורי מילים) שבהם גודל הוקטור פחות חשוב מכיוונו.

צנטרואיד (Centroid): נקודת המרכז של אשכול, המחושבת לרוב כממוצע של כל הנקודות באשכול.

אלגוריתמים נפוצים לניתוח אשכולות

K-Means

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

אשכולות היררכיים (Hierarchical Clustering)

בונים עץ של אשכולות (דנדרוגרמה). יש שתי גישות: אגלומרטיבית (Agglomerative) – מתחילה מכל נקודה כאשכול נפרד וממזגת אשכולות קרובים ביותר עד שנותר אשכול אחד; דיביסיבית (Divisive) – מתחילה מכל הנתונים כאשכול אחד ומפצלת אותו שוב ושוב. מאפשרת גמישות בבחירת מספר האשכולות על ידי "חיתוך" הדנדרוגרמה, אך יקרה חישובית לנתונים גדולים.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

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

דנדרוגרמה (Dendrogram): תרשים עץ המציג את ההיררכיה של האשכולות באלגוריתם אשכולות היררכי.

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

אתגרים ושיקולים בניתוח אשכולות

בחירת מספר האשכולות (K): אחד האתגרים המרכזיים. שיטות נפוצות כוללות את שיטת המרפק (Elbow Method) וציון סילואט (Silhouette Score).
טיפול בנתונים: סקאלינג (Scaling) של תכונות חיוני כאשר התכונות הן בקני מידה שונים, כדי למנוע מתכונות בעלות טווח ערכים גדול לשלוט במדד המרחק.
קללת המימד (Curse of Dimensionality): בנתונים בעלי מימדים רבים, מושג המרחק הופך לפחות משמעותי, וכל הנקודות נוטות להיות "רחוקות" זו מזו. זה מקשה על זיהוי אשכולות.
הערכת איכות האשכולות: מכיוון שאין תוויות אמת, הערכה היא קשה. ניתן להשתמש במדדים פנימיים (Intrinsic Measures) כמו ציון סילואט או מדד דייויס-בולדין (Davies-Bouldin Index), המודדים את הלכידות בתוך האשכולות וההפרדה ביניהם.

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

שאלות לדיון

השווה בין אלגוריתם K-Means לאלגוריתם DBSCAN בהיבטים של הנחות יסוד, אופן פעולה, יתרונות וחסרונות.
כיצד ניתן לקבוע את מספר האשכולות האופטימלי (K) עבור אלגוריתם K-Means? תאר שתי שיטות לפחות.
מדוע הערכת איכות אשכולות היא משימה מאתגרת בהשוואה להערכת מודלי סיווג? אילו מדדים ניתן ליישם?
תן דוגמה למצב שבו אשכולות היררכיים יהיו עדיפים על K-Means, והסבר מדוע.

נקודות לתשובת מודל

השוואה K-Means vs. DBSCAN:
- K-Means: מבוסס מרחק, דורש K מראש, מניח אשכולות כדוריים, רגיש לרעש ונקודות חריגות, מהיר יחסית.
- DBSCAN: מבוסס צפיפות, אינו דורש K מראש, יכול לזהות אשכולות בצורות שרירותיות, מטפל ברעש באופן טבעי, רגיש לפרמטרי צפיפות (epsilon, MinPts).
קביעת K אופטימלי:
- שיטת המרפק (Elbow Method): מריצים K-Means עבור טווח ערכי K, ומחשבים את סכום ריבועי המרחקים של כל נקודה לצנטרואיד שלה (Within-Cluster Sum of Squares - WCSS). מחפשים את ה"מרפק" בגרף, המציין נקודה שבה הוספת אשכולות נוספים מביאה לירידה שולית ב-WCSS.
- ציון סילואט (Silhouette Score): מחשבים את ציון הסילואט הממוצע עבור טווח ערכי K. בוחרים את K שמניב את הציון הגבוה ביותר, המצביע על אשכולות קומפקטיים ומובחנים היטב.
אתגרי הערכת אשכולות:
- אין תוויות אמת (Ground Truth) זמינות מראש, ולכן לא ניתן להשתמש במדדים כמו דיוק (Accuracy) או F1-Score.
- מדדים פנימיים: ציון סילואט (לכידות והפרדה), מדד דייויס-בולדין (יחס בין פיזור פנימי לפיזור בין אשכולות). מדדים אלו מנסים להעריך את מבנה האשכולות הפנימי.
מתי אשכולות היררכיים עדיפים:
- כאשר אין לנו מושג לגבי מספר האשכולות הרצוי, ואנו רוצים לחקור מבנים היררכיים בנתונים.
- כאשר גודל הנתונים אינו גדול במיוחד (בגלל עלות חישובית גבוהה יותר).
- כאשר אנו מעוניינים להציג את הקשרים בין האשכולות באמצעות דנדרוגרמה, המאפשרת גמישות בבחירת רמת הפירוט של האשכולות.

מצאתם טעות או שחסר משהו?