Clustering
שיטות שונות למציאת דפוסים בדאטה.
מוטיבציה:
הדאטה לא תמיד קל לניתוח.
יש יותר מידי דפוסים או שלא שאין דפוס נראה לעין.
עובדים רק עם Xאין Yכלומר .unsupervised
:Hard Clusteringכל תצפית משויכת באופן דטרמיניסטי ) (xorלקסלטר מסוים.
:Soft Clusteringכל תצפית משויכת בהסתברות שונה לקלסטר מסוים ,ניתן לסווג סופית על ידי שיוך לאשכול עם
ההסתברות הגבוהה ביותר.
חישובי מרחקים
מרחק מנהטן מרחק אוקלידי
כללי כלומר עם משתנה p
הערה :ערכים זבליים משפיעים על חישוב המרחקים יותר כאשר ה Pבנוסחה לחישוב מרחק כללי גבוה יותר ,לכן אם
אנו פוחדים מפיצ'רים זבליים נשתמש ב Pנמוך.
כאשר Pשווה ל 0אנחנו נקבל ווקטור של 0ו 1כאשר 0זה פיצ'ר שהערכים בין הנקודות זהים
ו 1כאשר הם שונים.
שיטה נוספת לחישוב מרחקים :חישוב הזווית בין כל שתי ווקטורים)רשימת ערכי פיצ'רים של
תצפית( ,כדאי להשתמש בזה כאשר יש לנו דאטה שדומה בתוכן אבל שונה בכמות או בגודל
שלו ,למשל שני מסמכים שמכילים מילים דומות רק שאחד מכיל פי 4מילים מהשני)חישוב
מרחק בשיטות הקודמות יראה כנראה שהמסמכים שונים(ובחישוב זווית נראה שהם למעשה
דומים.ד
אלגוריתמים עם מספר אשכולות) (Clustersידוע מראש
– (Hard Clustering)Kmeansסיווג בצורה מוחלטת כל תצפית לקלסטר אחד ויחיד .עובד טוב על
קלסטרים בצורת עיגול ,אחרת ,פחות יעיל.
שלבי האלגוריתם:
מחליטים על Kאשכולות שרוצים ליצור)היפר פרמטר(.
.1הגרלת Kנקודות רנדומליות ,וסיווגן כ מרכזי האשכולות ).(centroieds
.2לכל שאר הנקודות מחשבים מרחק מכל מרכז אשכול.
.3עבור כל נקודה מרכז האשכול שהיא הכי קרובה אליו יסווג שאשכול שהיא שייכת אליו.
.4חישוב מרכזי אשכולות חדשים)הנקודה הממוצעת בכל אשכול(.
.5חזרה על שלבים 2-4שוב עד שהנקודות מפסיקות לעבור בין האשכולות השונים או שהשינוי במרכזי
האשכולות מאוד קטן או שהגענו למספר איטרציות מקסימלי שהגדרנו)היפר פרמטר(.
איך להגריל נקודות חכם?
לא נרצה להגריל נקודות שקרובות אחת לשנייה)כי הן כנראה שייכות לאותו אשכול( ,נבחר נקודה ראשונה
אקראית ואת השנייה נבחר כך שהיא תהיה רחוקה במרחק מסויים מהנקודה הראשונה ,ואת השלישית
שתהיה רחוקה מהשתיים הראשונות וכן הלאה .בנוסף ניתן לבצע את האלגוריתם מספר פעמים ובסוף לבחור
את האיטרציה שלו שנתנה את הסיווג לאשכולות הכי טוב.
פונקציית Lossלחישוב איכות הקלסטרינג )על מנת לשפר את בחירת :(k
תצפית – Xi
מרכז – )C(Xi עבור כל אשכול Cנחשב את סכום הריבועים של ההפרשים בין הנקודות
האשקול אליו שייכת
ששייכות אליו לבין מרכז האשכול ,נרצה למזער את ה Scoreהזה.
התצפית
ככל ש ) Kהיפר פרמטר למספר אשכולות( גדול Scoreיורד ,כיוון שיש יותר מרכזי אשכולות שכל נקודה יכולה
להיות שייכת לאחת מהן .תצפית תמיד תהיה שייכת לקלסטר שהכי קרוב אליה.
כאשר ) N = Kמספר הנקודות( אזי ה Score-שווה ל 0אך זה לא באמת טוב כי לא סביר שבמציאות כל
נקודה היא Clusterנפרד.
למה כדאי שמרכז כל אשכול יהיה הממוצע? כי הוא הכי ממזער את פונקציית ה Loss
הוכחה )גזירת הפונקציה והשוואה ל:(0
אילו החזקה הייתה )0מרחק עם (0 = Pבפונקציית Lossאז הממזער הכי טוב לפונקצייה
היה השכיח)בכל פיצ'ר( ובחזקה ששווה ל ) 1מרחק מנהטן( הממזער הכי טוב היה החציון.
בחירת Kאופטימלי – שיטת המרפק:
ננסה וריאציות שונות של kונחשב את פונקציית Lossעבור כל אשכול,
נבחר את ה Kשעבורו ה Scoreמתחיל לרדת ממש מעט )שיטת המפרק(.
במקרה הזה נבחר Kשווה .3
הערה :האלגוריתם האופטימלי זה לנסות את כל הוריאציות של שיוך
הנקודות ל Kאשכולות שונים אבל זה לא ריאלי כי מספר האפשרויות הוא
Kmeans ,K^Nמביא לנו קירוב טוב.
הבעיה באלגוריתם :ההנחה היא שהדאטה
מתחלק לאשכולות בצורה עגולה ואין לנו נקודות
הדאטה. מוזרות ,רגיש לסקאלינג )יחידות מידה( של
הערה:
ביניהן יצא באמת קטן. נרצה שלנקודות שדומות אחת לשנייה ,המרחק
ניתן לתת משקלים שונים לפיצ'רים שונים )בהתאם לחשיבות בדמיון בין נקודות בחישוב המרחקים(Wi .
זה המשקל שנתנו לפיצ'ר iמסוים ,ככל שהוא יותר גדול הפיצ'ר יותר חשוב.
(Soft Clustering) (Gaussian Mixture Model) GMM
מתאים לאשכולות שהם לא עגולים ,בנוסף מחשב את הצורה של o
כל אשכול.
לכל נקודה מחשב הסתברות להיות שייך לאשכול מסוים. o
פחות רגיש לסקאלינג של הדאטה. o
מניח התפלגות נורמלית של האשכולות. o
עבור כל אשכול נלמד את צורת ההתפלגות הנורמלית שלו.
שונה מ Kmeansבכך שחוץ מממוצע לכל אשכול נחשב גם את השונות שלו
)מאפשר לייצר את צורת ההתפלגות(.
פרמטרים )מחושבים תוך כדי הבניה ומתעדכנים באחריות האלגוריתם( של האלגוריתם לכל אשכול= 𝜇 :
מרכז האשכול )ממוצע( = 𝛴 ,השונות המשותפת של האשכול )מטריצת שונויות הפיצרים( זה השונות בריבוע,
𝜋 = אחוז התצפיות באשכול מתוך כל התצפיות.
האלגוריתם הוא וריאציה של אלגוריתם Expectationו ) Maximizationאלגוריתם סטטיסטי למציאת ערכים מתאימים
לפרמטרים(.
שלבי האלגוריתם:
.1תחילה ניצור אשכולות ראשוניים ,לרב ע״י . Kmeansלאחר מכן משערכים לכל אשכול ערכים לפרמטרים:
𝜋 . 𝜇, 𝜎 ,
– Expectation .2חישוב לכל תצפית את ההסתברות שלה להיות שייכת לכל אשכול:
= חישוב ההסתברויות לכל נקודה להיות שייכת לכל אשכול.
Maximization .3עדכון 𝜋 𝜇, 𝜎 ,עבור כל אשכול )בהתאם להתסברויות מסעיף :( 2
∑ ⋅) ( ∑ ) (
= 𝜇 )סכום ערכי ∑ ) (
= 𝜋 )מספר התצפיות באשכול חלקי מספר כל הצפיות(
הנקודות כפול ההסתברויות שלהן להיות שייכות לאשכול ,חלקי מספר הנקודות באשכול(
∑ () ( )
= 𝜎 )סכום ריבועי ההפרשים של הנקודות ומרכז האשכול כפול ההסתברות של ∑ ) (
הנקודה ,חלקי מספר התצפיות באשכול פחות .(1
הערה :עדכון השונות והתוחלת מתבסס על הסתברות הנקודות להיות שייכות לאשכול ,כלומר ככל
שלתצפית הסתברות גבוהה יותר להיות שייכת לאשכול כך היא תשפיע יותר על הערכים של השונות
והתוחלת של האשכול).כלומר בכך בא לידי ביטוי ההתחשבות בצורות לא עיגולית של אשכולות
והקטנת ההשפעה של תצפיות חריגות על ביצועים( .למעשה נקודות שסווגו לא נכון ,יקבלו הסתברות
גבוהה יותר להיות שייכים לקלסטרים האמיתיים שלהן ובכך באיטרציה הבאה ,הסיווג שלהן ישתנה .כך
מתאפשר מעבר נקודות בין אשכולות.
.4חזרה על שלבים 2ו 3עד שהנקודות לא זזות יותר בין האשכולות או שהגענו למצב שהשינוי בפרמטרים
קטן מערך מסוים )היפר פרמטר( או שהגענו למספר איטרציות מקסימלי שהגדרנו)היפר פרמטר(.
סוגי מטריצות שונות משותפת שמחשבים )היפר פרמטר של האלגוריתם(:
:Fullלכל אשכול מטריצת שונות משותפת ) (covarianceמשלו.
:Tiedלכל האשכולות מטריצה אחת.
:Diagלכל אשכול מטריצה אלכסונית אחת השונות המשותפת של כל פיצר עם עצמו.
:Sphericalלכל אשכול יש שונות אחת)הנחה שהאשכולות הם ספירלים(.
– (Soft Clustering and Expectation Maximization )Kmeansאין סיווג דטרמיניסטי של נקודה
לאשכול אלא וקטור של הסתברויות להיות שייכת לכל אשכול.
לכל נקודה מחשבים הסתברות להיות שייכת לכל אחד מהאשכולות השונים ,לשם כך נותנים לכל אשכול שונות
זהה.
נשייך כל תצפית לאשכול עם ההסתברות הגדולה ביותר, חישוב ההסתברות:
כלומר האשכול שהכי קרוב לתצפית ,בגרסת ה softלכל נקודה פשוט ניתן וקטור הסתברויות להיות שייכת לכל
אשכול.
על מנת לחשב הסתברות של נקודה להיות שייכת לקלסטר עלינו לדעת את ההתפלגות של הקלסטר כלומר לדעת את
) mתוחלת( ואת ) vשונות( .לכן ניתן שונות קבועה לכלל הקלסטרים ,vואת התחולת נחשב באותו אופן שחושבה ב-
kmeansהרגיל .לבסוף ,נחשב לכל תצפית את ההסתברות להיות שייכת לקלסטר מסויים ונשמור את המידע הזה
בוקטור )עבור כל תצפית( .נחזיר את כל התצפיות עם הוקטורים שלהן.
אלגוריתמים עם מספר אשכולות) (Clustersלא ידוע מראש
לא נותנים לאלגוריתם kומבקשים שיסווג ל k-קלסטרים אלא מבקשים ממנו לסווג ״כפי שחושב לנכון״
– (Hard Clustering)Agglomerative Clusteringאלגוריתם איטי
oמתבסס על השוואת דמיון בין כל זוג תצפיות.
oמספר האשכולות לא מוגדר מראש לרוב.
oמתחיל מכך שכל תצפית היא אשכול נפרד ,ואז מאחדים אותם כל פעם תצפית אחת לאשכול מסוים.
השלבים:
הגדרת כל תצפית כאשכול. .1
יצירת מטריצת דמיון שמבטאת את הדמיון של כל זוג אשכולות )תצפיות בהתחלה( )לפי חישוב מרחקים, .2
לרוב מרחק אוקלידי(.
חיבור אשכולות )בהתחלה תצפית( לאשכול שהכי דומים. .3
חזרה על שלבים 2-3עד שכל התצפיות באשכול אחד)ואז מפצלים אותם( או .4
שהגענו למספר אשכולות רצוי.
שיטות להשוואת דמיון):(Linkage methods
:Complete Linkage oחישוב המרחק בין שתי התצפיות הכי רחוקות מכל
אשכול.
:Single Linkage oחישוב מרחק בין שתי התצפיות הכי קרובות מכל
אשכול.
:Average Linkage oחישוב מרחק בין ממוצעי כל אשכול.
השיטה הנבחרת משפיעה על תוצאות האלגוריתם.
פיצול הנקודות לאשכולות סופיים אחרי שעשינו קיבוץ לאשכול אחד)נפצל/נחתוך לפי הפרש המרחקים הכי
גדול שיש לנו בגרף הקיבוצים(:
:Completeפה לדוגמה קודם קיבצנו את 1ו) 2מרחק ,(0.3אחרי זה
את 3ו ) 4מרחק (0.45ולבסוף את ) (1,2ו)) (3,4מרחק ,(0.8
אז הפרשי המרחקים של הקיבוצים הם (0.45-0.3)0.15 ,0.3 :ו 0.35
) ( 0.8-0.45לכן החיתוך יהיה לפי האיחוד האחרון ,כלומר נשאר עם 2
אשכולות ) (1,2ו ).(3,4
:Singleפה לדוגמה קודם קיבצנו את 1ו) 2מרחק ,(0.3אחרי זה את
) (1,2ו ) 3מרחק (0.4ולבסוף את ) (1,2,3ו) 4מרחק ,(0.45
אז הפרשי המרחקים של הקיבוצים הם (0.4-0.3) 0.1 ,0.3 :ו 0.05
) ( 0.45-0.4לכן החיתוך יהיה לפי האיחוד הראשון ,כלומר נשאר עם 4
אשכולות 1,2,3ו. 4
– (Hard Clustering)Divisive Clusteringעובד הפוך מ - Agglomerative Clusteringאלגוריתם
איטי
בשונה מהקודם מתחילים שכל התצפיות הן באשכול אחד ואז מפצלים.
השלבים:
.1הגדרת כל התצפיות באשכול אחד.
.2בניית מטריצת דמיון בין כל זוג תצפיות .כאשר דמיון בין 2נקודות I ,jמוגדר כך:
.3פיצול התצפיות לשני אשכולות כך שנמקסם את הביטוי הבא:
כאשר המונה זה סכום הדמיונות בין כל שתי תצפיות c ,זה גודל האשכול ואלפא זה היפר פרמטר בין
0ל.2
.4חזרה על שלבים 2ו 3עד שכל התצפיות באשכולות נפרדים ,או שהגענו למספר האשכולות הרצוי.
דוגמה עם 3תצפיות ואלפא שווה ל.0.5
אפשר לראות שהפיצול הראשון שממקסם את הביטוי זה 1ו 3באשכול אחד ו 2באשכול שני)שזה הגיוני כי לפי
מטריצת הדמיון הדמיון בין 1ל 3הכי גבוה ,האלכסון תמיד 1כי כל תצפית דומה לעצמה( .אם נרצה להמשיך
הפיצול הבא יהיה בין 1ל.3
בעיה :זמן ריצה מעריכי.
Mean Shift
מתאים גם לדאטה עם "רעש" ,מספר האשכולות לא נקבע מראש ,לא מניח צורה מסוימת של האשכולות
ומבוסס על צפיפות האשכולות.
שלבים:
.1הגדרת כל תצפית כאשכול נפרד והגדרת רדיוס מסוים bandwitch) hהיפר פרמטר( לכל תצפית.
.2קיבוץ תצפיות שנכנסות אחת לרדיוס של השנייה לאשכול אחד) .הכוונה אחד לספירה של השני בהתאם
לרדיוסים שהגדרנו(
.3חישוב מרכזי האשכולות החדשים.
.4חזרה על שלבים 2-3עד שאין שינוי באשכולות או שהגענו מספר איטרציות מקסימלי שהגדרנו.
סיווג נקודות לאשכולות בפועל :לחשב מרחקים בין הנקודות לכל מרכז אשכול זה יקר חישובית ,לכן מה נעשה בפועל
זה gradient decentולאן שהנגזרת תביא אותנו)היא תתאפס כשתגיע לשכיח)מרכז אשכול(( ,זה יהיה האשכול אליו
נסווג את הנקודה.
דוגמה להרצת האלגוריתם)הייתה
שאלה כזו במבחן(
השפעה של hשונים:
נרצה מהמנע מאחד משני המצבים הבאים:
:Under segmentationכמה תצפיות מאשכולות שונים בפועל ,סווגו לא נכון לאשכול אחד h) .גדול מידי(
:Over segmentationתצפיות מאשכול אחד בפועל ,סווגו לא נכון לאשכולות שונים h) .קטן מידי(
בעקרון ככל שה hיותר קטן נקבל יותר אשכולות ,אבל זה לא מחייב) .אם לא נקטין מספיק את hאז אין שינוי(
(Kernel Density Estimator) KDE
גם אלגוריתם מבוסס צפיפות ,ניתן לממש עם פונקציות Kernelשונות.
שימושים:
oויזואליזציה של התפלגות דאטה )מאין המקבילה הרציפה של היסטוגרמות(.
oקיבוץ לאשכולות ).(Clustering
בשונה מ GMMשאומד פרמטרים כמו שונות ותוחלת כדי לייצר את ההתפלגות של האשכולות ,האלגוריתם
KDEלא אומד ערכים של פרמטרים אלא מודד את הצפיפות של ההתפלגות על סמך מדגם הנתונים.
השיטה:
.1פונקציית הצפיפות של נקודה :X
עבור נקודה Xנחשב את ההסתברות שלה להיות בטווח h -+
כשהוא שואף ל h) .0לא היפר פרמטר אלא רק שואף ל (0
.2חישוב הפרופורציה של התצפיות שנכנסות לטווח -+
) hהיפר פרמטר( של תצפית Xכלשהי:
האינדיקטור מחזיר לי 1אם xiשייכת לטווח ו 0אם לא.
.3הגדרת פונקציית kernalמשקל:
עבור כל Xאם ערכו המוחלט קטן מ 1המשקל שווה 0.5אחרת .0
להיכתב כך :כלומר אם Xi למה? הפונקציה בסעיף 2יכולה
הביטוי בתוך Wקטן מ בטווח שהגדרתי ל X+-hאז
ופונקציית המשקל תחזיר )1כי X – xiיהיה קטן מ(h
0.5אחרת ,0ואז הביטוי בסעיף 3שקול לזה שב.2
. 4הפונקציה בסעיף הקודם לא רציפה לכן ניתן להפעיל
פונקציות Kernelאחרות בצורה הבאה:
מחזיר פונק )גאוסיינית בדוגמה בגרף( עבור כל תצפית
מה האלגוריתם עושה בפועל:
מגדיר פונקציית Kernelלכל תצפית ועבור כל נקודה מחשב bumpשזה סכום
הצפיפויות של כל תצפית באותה נקודה .נוכל להגיד שמספר השכיחים בbumps
הוא מספר האשכולות ,במקרה הזה .2כל גרף כזה הוא עבור פיצר מסויים .ניתן
להגדיר גם עבור פיצרים ,אך ויזואלית ניתן לייצג עד 2פיצרים.
סיווג נקודות לאשכולות בפועל :לחשב מרחקים בין הנקודות לכל מרכז אשכול זה
יקר חישובית ,לכן מה נעשה בפועל זה gradient decentולאן שהנגזרת תביא
אותנו)היא תתאפס כשתגיע לשכיח)מרכז אשכול(( ,זה יהיה האשכול אליו נסווג את
הנקודה.
השפעה של hשונים:
Hגדול מידי יתבטא ב Overs smoothingכלומר נקבל פחות אשכולות ממה שקיימים ,מחליקים יותר מידי את
הפונקציה.
Hקטן מידי יתבטא ב under smoothingכלומר נקבל יותר אשכולות ממה שקיימים.
במקרה שהממד יותר גבוה הפונקציה דומה פשוט לכל ממד יש hמשלו.
: Image Segmentationבידוד קבוצות פיקסלים) למשל לזהות מתוך תמונה כמה חזירי בר יש שם( ,איך להעריך
ביצועי מודל? לתת לאדם לסווג בעצמו ואז לבדוק את ה IOUשזה החיתוך)החזירים שהאלגוריתם( /כל החזירים שיש
באמת בתמונה.
