משתמש:Maria.levin/אשכולות מבוססי מרחק

*אשכולות מבוססי מרחק* - *שם המגדיר במה עוסק הערך, ומכאן מה חשיבותו של נושא הערך*

תיאור כללי

אלגוריתם אשכולות מבוססי מרחק היא שיטה של וקטור כימות, במקור מעיבוד אותות. שיטה פופולארית עבור ניתוח אשכולות בכריית נתונים. מטרתו לחלק את N תצפיות/קבוצות ל- K אשכולות לפי מרכזי כובד. לכל תצפית/קבוצה זהה יש "מרכז כובד". על ידי בחירה נכונה של מרכזי כובד ניתן לאתר את הקבוצות השונות. נדרשות תצפיות רבות לביצוע המודל. תוספת של תצפיות עשויה לחייב חישוב חוזר. מדובר באלגוריתם היוריסטי, המהווה טכניקה שנועדה לפתרון בעיה במהירות רבה יותר, שבד"כ משומש בכדי לבצע חישובים שמטרתם להוביל להתכנסות של פתרון מקומי. זהו מודל סטטיסטי, לא מתבסס על ידע הנדסי, רק על תצפיות בפועל. מדובר בשיטה אשר דומה אלגוריתמים מבוססים על נוסחאות גאוס. מודל זה – נוטה למצוא אשכולות בעלי מרחבי מידה הניתנים להשוואה. בעוד שמנגנון ציפייה-מיקסום מאפשר לאשכולות להיות בעלי צורות שונות. המודל לא לינארי, מכאן שמאפשר להתמודד עם כל סוגי ההתפלגויות האפשריות. תיאור: בהינתן קבוצה של תצפיות (x1, x2, ..., xn), כאשר כל תצפית היא וקטור אמיתי בעל מספר ממדים.

המודל שואף לחלק את תצפיות  n  ל- (k=<n) S={S1, S2,….Sk} כדי למזער את סכום  הריבועים בתוך האשכול.

ראה נוסחה.

μi הוא ממוצע של נקודות ב- Si

היסטוריה

על המונח K-means דובר לראשונה ע"י ג'יימס מקווין בשנת 1967, אף על פי שהרעיון התחיל עוד קודם לכן אצל הוגו סטיינהאוס בשנת 1957. האלגוריתם הבסיסי הוצע לראשונה ע"י סטוארט לויד בשנת 1957 כטכניקה של pulse-code modulation למרות שזה לא פורסם מחוץ למעבדות בל עד שנת 1982. בשנת 1965, פורגי (E.W FORgy) פירסם את אותה השיטה, ולכן היא נקראת לעיתים גם לויד-פורגי. גרסה יעילה יותר הוצעה ופורסמה ע"י Hartigan and Wong בשנת 1975/1979 בכתב עת Fortran.

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

אלגוריתם רקע מתמטי

A. אלגוריתם סטנדרטי האלגוריתם הנפוץ ביותר משתמש בטכניקת עידון איטרטיבי. לאור העובדה שמשתמשים בו בכל מקום, לעיתים קרובות הוא גם נקרא אלגוריתם k-means. זה גם נקרא האלגוריתם של לויד, במיוחד בקהילת מדעי מחשב. בהינתן קבוצה ראשונית של k מ- (1)M1 עד Mk(1) האלגוריתם ינוע לסירוגין בין שני שלבים הבאים: 1. שלב הקצאה: להקצות לכל תצפית באשכול, ממוצע שכולל באשכול את סכום הריבועים. לאור העובדה שסכום ריבועים הוא מרחק אוקלידי בריבוע, זה באופן אינטואיטיבי מרכז הכובד "הקרוב ביותר" (מבחינה מתמטית, זה אומר שמתקיימת חלוקת תצפיות לפי דיאגרמת וורונוי (Voronoi) נוצר על ידי ממוצע).

כל Xp , מוקצה בדיוק לSt מסוים. גם אם קיימות כמה נקודות. ראה נוסחה 2.

2. שלב עדכון: ראה נוסחה 3

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

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

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

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

B. שיטות אתחול: שיטות אתחול בשימוש הנפוצה הן פורג'י ( Forgy) וחלוקה אקראית. שיטת פורג'י בוחרת באופן אקראי k תצפיות מהמערך הנתונים ומשתמשת בהם כאמצעי הראשוני. שיטת החלוקה אקראית מבצעת באופן אקראי הקצאת אשכול לכל תצפית ולאחר מכן ממשיכה לשלב העדכון, ובכך שהחישוב הממוצע הראשוני מהווה מרכז כובד של הנקודות באופן אקראי. שיטת החלוקה אקראית היא בדרך כלל עדיפה לאלגוריתמים: K-means, K-harmonic ו-Fuzzy K-means.

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

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

C. דוגמא לחישוב אלגוריתם סטנדרטי:

1. בחירת מרכזי כובד אקראיים (סנטורואידים) (K). ראה דוגמא 1.

דוגמא 1

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

דוגמא 2

3. מחשבים מרכזי כובד חדשים. ראה דוגמא 3.

דוגמא 3

4. חישוב קבוצות חדשות ראה דוגמא 4.

תמונה 7

התהליך ממשיך עד שסף הסטיות מתכנס לערך קבוע.

יתרונות המודל

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

חסרונות המודל

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

דוגמא מספרית

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

נקודה חדשה לחישוב: 38,12,57

חישוב ממרכז כובד 1 : 63.84= ²(57-39.36) +²(12-70.36) +² (38-57.47) √

חישוב ממרכז כובד 2 : 125.77= ²(57-81.07 ) +²(12-105.43) +² (38-118.68) √

חישוב ממרכז עובד 3 : 97.43= ²(57-126.31) +²(12-58.2) +² (38-88.57) √ נקודה זו שייכת למרכז כובד מספר 1 – הערך המינימאלי שהתקבל.

חישוב אשכולות בעזרת WEKA

1. תחילה יש לטעון קובץ מנורמל לweka. לצורך כך, נשתמש בקובץ נתונים שכולל 600 מקרים. כהמחשה לביצוע אשכולות בWeka, בערכת הנתונים של בנק כלשהוא, ולאפיין את מגזרי הלקוחות וכתוצאה מכך. איור 1.

Weka תבצע סינון של פילטרים למשתנים.

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

איור 1

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

איור 2

3. בחלון שקפץ, אנו מכניסים את מספר האשכולות שלנו. (ערך ברירת מחדל הוא 2) משאירים 10 בשדה seed. שדה זה משמש ביצירה מספרים אקראיים, המשמש להכנת המשימה הראשונית של מקרים לאשכולות. שים לב כי, באופן כללי, K-means הוא די רגיש למספר האשכולות המוקצים בתחילת החישוב. לכן, לעתים קרובות יש צורך לנסות ערכים שונים ולהעריך את התוצאות. ראה איור 3.

4. ברגע שכבר צוינו באפשרויות, אנחנו יכולים להפעיל את האלגוריתם באשכולות. כאן אנו מוודאים כי בפנל "Cluster Mode", באפשרות "Use training set" נבחרה, וללחוץ על "Start". ניתן ללחוץ לחיצה ימנית על "Result list", ולהציג את התוצאות באשכולות בחלון נפרד. תהליך זה והחלון מוצגים באיורים 3 ו4. ראה תמונה 12.

5. חלון התוצאה מראה את מרכז הכובד של כל אשכול וכן נתונים סטטיסטיים על המספר ואחוז המקרים שהוקצו לאשכולות שונים. המרכז הכובד הם הווקטורים הממוצעים לכל אשכול (כל כך, כל ערך במימד מייצג את ממוצע הערך עבור מימד שבאשכול). לפיכך, ניתן להשתמש בם כדי לאפיין מרכז י כובד של האשכולות. לדוגמא, מרכז כובד לאשכול 1 מראה כי מדובר בקטע של מקרים המייצג בגיל עמידה לצעיר (כ 38) נקבות המתגוררות בעיר פנימית עם הכנסה ממוצעת של כ. $ 28,500, שהם נשוי ואב לילד אחד וכו', יתר על כן, יש בממוצע בקבוצה זו אמרה כן למוצר PEP.

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

6. ניתן לבחור את מספר האשכול וכל אחד התכונות האחרות לכל אחת משלושת הממדים השונים הזמינים (ציר ה-x, ציר ה-Y, וצבע). שילובים שונים של בחירות יביאו לעיבוד חזותי של מערכות יחסים שונות בתוך כל אשכול. בדוגמא לעיל, בחרנו מספר האשכול כציר ה-x, המספר, למשל (שהוקצה על ידי Weka) כציר ה-Y, ותכונת "מין" כממד הצבע. זה יגרום להדמיה של ההתפלגות של זכרים ונקבות בכל אשכול. למשל, יש לשים לב כי אשכולות 2 ו -3 נשלטים על ידי גברים, ואילו אשכולות 4 ו -5 נשלטים על ידי נקבות. במקרה זה, על ידי שינוי ממד הצבע לתכונות אחרות, אנו יכולים לראות את התפלגותם בתוך כל אחד מהאשכולות. ראה איור 6.

איור 6

לבסוף, אנו עשויים להיות מעוניינים בשמירת ערכת הנתונים וכתוצאה מכך שכללה כל מופע יחד עם האשכול שהוקצה לו. לשם כך, אנו לוחצים על הכפתור "Save" בחלון ההדמיה ולשמור את התוצאה כקובץ. החלק העליון של קובץ מתואר באיור 6.

יישומים

חישוב ע"י אלגוריתם במיוחד כאשר משתמשים לפי K-historic כמו לויד אלגוריתם, קל יותר להשתמש בבסיסי נתונים גדולים. למשל, בתחומים של פילוח שוק, חיזוי של פרמטרים, אסטרונומיה ובחקלאות. הוא משמש לעתים קרובות שלב מקדים לאלגוריתמים אחרים, למשל כאשר רוצים למצוא נקודות התחלתיות.

קישורים חיצוניים

• למידה חישובית, באתר (wikipedia)

הערות שוליים

[[קטגוריה:ויקיפדיה: ערכים של משתמשים חדשים|תבנית:יוני תבנית:2014]]