אשכולות מבוססי מרחק

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

בהינתן קבוצה של תצפיות (x_1, x_2,..., x_n), כל תצפית היא וקטור אמיתי בעל מספר ממדים.

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

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

אחרי שהוגדרו האשכולות ניתן לעבוד ללא נתוני המקור.

היסטוריה[עריכת קוד מקור | עריכה]

על המונח K-means דובר לראשונה על ידי ג'יימס מקווין בשנת 1967, אף על פי שהרעיון התחיל עוד קודם לכן אצל הוגו סטיינהאוס בשנת 1957.

האלגוריתם הבסיסי הוצע לראשונה על ידי סטוארט לויד בשנת 1957 כטכניקה של pulse-code modulation למרות שזה לא פורסם מחוץ למעבדות בל עד שנת 1982.

בשנת 1965, פורגי (E.W Forgy) פרסם את אותה השיטה, ולכן היא נקראת לעתים גם לויד-פורגי. גרסה יעילה יותר הוצעה ופורסמה על ידי Hartigan and Wong בשנת 1975/1979 בכתב עת Fortran.

רקע מתמטי - אלגוריתם סטנדרטי[עריכת קוד מקור | עריכה]

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

שלב הקצאה[עריכת קוד מקור | עריכה]

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

שלב עדכון[עריכת קוד מקור | עריכה]

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

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

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

שיטות אתחול:[עריכת קוד מקור | עריכה]

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

שיקולים ביישום המודל:[עריכת קוד מקור | עריכה]

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

דוגמה מספרית לאלגוריתם סטנדרטי:[עריכת קוד מקור | עריכה]

חישוב אשכולות בעזרת WEKA[עריכת קוד מקור | עריכה]

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

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

3. בחלון שקפץ אנו מכניסים את מספר האשכולות שבחרנו (ערך ברירת המחדל הוא 2) . בשדה SEED משאירים 10.

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

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

ניתן ללחוץ לחיצה ימנית על "Result list", ולהציג את התוצאות באשכולות בחלון נפרד.

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

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

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

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

קובץ דוגמה:

יתרונות המודל[עריכת קוד מקור | עריכה]

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

חסרונות המודל[עריכת קוד מקור | עריכה]

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

יישומים[עריכת קוד מקור | עריכה]

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

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

דוגמאות לכך כוללות את:

  • R (סביבת תוכנה פתוחה לחישובים סטטיסטיים, הכוללת מספר יישומים של CART, כמו rpart וחבילות randomForest).
  • Weka (חבילת תוכנת קוד-פתוח חינמית לכריית נתונים שמכילה אלגוריתמים רבים).
  • SciPy vector-quantization
  • KNIME
  • Microsoft SQL Server
  • scikit-learn (קוד פתוח חינמי ללמידת מכונה בשפת תכנות Python).

מקורות לא חינמיים:

  • IDL Cluster, Clust_Wts
  • Mathematica ClusteringComponents function
  • MATLAB kmeans
  • SAS FASTCLUS
  • Stata kmeans
  • VisuMap kMeans Clustering

ראו גם[עריכת קוד מקור | עריכה]