טיוטה:מודל אשכולות

מודל אשכולות (Cluster analysis)

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

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

מלבד באשכולות טווח, ישנם מספר מונחים עם משמעויות דומות, כולל סיווג אוטומטי, טקסונומיה המספרי, botryology (מ βότρυς היוונית "ענבים") וניתוח טיפולוגי. את ההבדלים הדקים הם לעתים קרובות את השימוש של תוצאות: בעוד כריית נתונים, הקבוצות וכתוצאה מכך הם עניין של הריבית, סיווג אוטומטי הכוח מפלה המתקבל הוא של עניין. ניתוח אשכול היה מקורו באנתרופולוגיה על ידי נהג קרובר בשנת 1932 והציג לפסיכולוגיה של זובין ב -1938 ורוברט טריון ב -1939 ומשומש המפורסם על ידי Cattell החל בשנת 1943 לסיווג פסיכולוגיית תכונות בפסיכולוגיה אישית.

הגדרה

הרעיון של "אשכול" לא ניתן להגדיר במדויק, שהיא אחת הסיבות מדוע יש כל כך אלגוריתמי אשכולות רבים. יש מכנה משותף: קבוצה של אובייקטי נתונים. עם זאת, חוקרים שונים במודלי אשכול שונים, ולכל אחת מודלי האשכול האלה שוב אלגוריתמים שונים יכולים להינתן. הרעיון של אשכול, כפי שנמצא על ידי אלגוריתמים שונים, משנה באופן משמעותי את תכונותיו. הבנת "מודלי האשכול" היא מפתח להבנת ההבדלים בין האלגוריתמים השונים. מודלי אשכול אופייניים כוללים: מודלים קישוריות: למשל, אשכולות היררכי בונה מודלים המבוססים על קישוריות מרחוק. מודלים centroid: למשל, האלגוריתם- K אמצעי אלגוריתם k-מרכזים מייצג כל אשכול על-ידי וקטור הממוצעים יחיד. מודלי הפצה: מודל באמצעות הפצות סטטיסטיות, כגון התפלגות רב נורמאלית משתנה המשמשת את אלגוריתם ציפייה - מקסום . מודלי צפיפות: למשל, DBSCAN ו OPTICS - מגדירים אשכולות כאזורים צפופים מחוברים במרחב הנתונים. מודלי Subspace: ב Biclustering (הידוע גם בשם Co-אשכולות או שניים במצב אשכולות), אשכולות הם מודל עם שני בני אשכול ותכונות רלוונטיות. מודלי קבוצה: אלגוריתמים מסוימים אינם מספקים מודל מזוקק לתוצאות שלהם ופשוט לספק את מידע הקיבוץ. מודלים מבוססי גרף: תת-קבוצה של צמתים בגרף כך שכל שני צמתים בתת מחוברים באמצעות יתרון יכול להיחשב כצורה אבטיפוס של אשכול. הקלות של דרישת קישוריות מלאה (חלק של הקצוות יכול להיות חסר) ידועים כמו-קליקות מעין, כמו באלגוריתם אשכולות HCS. "אשכולות" הוא למעשה סדרה של אשכולות כאלה, בדרך כלל המכיל את כל האובייקטים של מערך הנתונים. בנוסף, הוא עשוי לציין את הקשר בין האשכולות זה לזה, למשל, היררכיה של אשכולות מוטבעים זה לזה. ניתן בצירופים בערך נבדל כמו: אשכולות קשים: כל אובייקט שייך לאשכול או לא אשכולות רכים (גם: אשכולות מטושטשים fuzzy clustering): כל אובייקט שייך לכל אשכול במידה מסוימת (למשל, סבירות שייכת לאשכול) ישנם גם הבחנות דקות אפשריות, למשל: אשכולות עם מחיצות קפדניות: כאן כל אובייקט שייך בדיוק באשכול אחד אשכולות מחיצות קפדנים עם חריגים: אובייקטים גם יכולים לא להשתייך לאשכול, ולכן נחשבים לחריגים. אשכולות חופפים (גם: אשכולות חלופיים, אשכולות רבים להציג): בעוד בדרך כלל אשכולות קשים, חפצים יכולים להשתייך ליותר מקבוצה אחת. אשכולות היררכיים: חפצים ששייכים אשכול ילד שייך גם לאשכול ההורה אשכולות subspace: בעוד אשכולות חופפים, בתוך subspace מוגדר באופן ייחודי, אשכולות אינם צפויים להיות חופפים.

אלגוריתמים

אלגוריתמי Clustering יכולים להיות מסווגים המבוססים על מודל האשכול שלהם, כפי שפורטו לעיל. הסקירה הבאה בלבד תפרט את הדוגמאות הבולטות של אלגוריתמים באשכולות, שכן ישנם מעל 100 אלגוריתמים באשכולות שפורסמו. סקירה של אלגוריתמים בויקיפדיה ניתן למצוא ברשימת אלגוריתמים סטטיסטיים. אין אובייקטיבי "נכון" באלגוריתם אשכולות, אבל כפי שהוא צוין, "אשכולות הם בעיני המתבונן". אלגוריתם האשכולות המתאים ביותר עבור בעיה מסוימת לעתים קרובות צריך להיבחר באופן ניסיוני, אלא אם קיימת סיבה מתמטית להעדיף מודל אשכול אחד על פני האחר. יצוין כי אלגוריתם אשר נועד עבור סוג אחד של מודל אין סיכוי שהוא יתאים לסט נתונים המכיל סוג שונה לחלוטין של המודל. לדוגמא, K- אמצעי לא יכול למצוא אשכולות שאינם קמורים.

קישוריות מבוססת אשכולות (אשכולות היררכיים)

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

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

Centroid מבוסס אשכולות

מאמר ראשי: אשכולות מבוססי מרחק באשכולות מבוססי centroid, אשכולות מיוצגים על ידי וקטור מרכזי, אשר לא בהכרח חבר בסט הנתונים. כאשר מספר אשכולות קבוע.,K אשכולות K- אמצעי נותן הגדרה פורמלית כמו בעיית האופטימיזציה: למצוא את מרכזי אשכול kולהקצות את האובייקטים למרכז האשכול הקרוב, כך המרחק בריבוע מן האשכול הוא מזערי. בעית אופטימיזציה עצמו ידועה להיות NP-קשיות, ולכן הגישה המקובלת היא רק לחפש פתרונות למידע. שיטה זו לא מדויקת במיוחד ידועה בשם האלגוריתם של לויד, לעתים קרובות למעשה מכונה "אלגוריתם k-אמצעי". עם זאת האלגוריתם מוצא רק אופטימום מקומי, והוא רץ מספר פעמים עם initializations אקראי שונה. וריאציות של K אמצעי לעתים קרובות כוללות אופטימיזציות כמו בחירה למיטב ריצות מרובות, אלא גם הגבלת centroids לחברי קבוצת הנתונים (k-medoids), בחירת חציונים (אשכולות k-חציונים), בחירת המרכזי הראשוני פחות אקראית ( K-אמצעי ++) או מתן אפשרות הקצאת אשכול מטושטש (c-אמצעי פאזי). רוב האלגוריתמים K- אמצעי מסוגים שונים דורשים מספר אשכולות - k - שיפורטו מראש, דבר אשר נחשב לאחד החסרונות הגדולים ביותר של אלגוריתמים אלה. יתר על כן, האלגוריתמים מעדיפים אשכולות עם גודל דומה, כדי שהם תמיד יוכלו להקצות אובייקט אל centroid הקרוב. דבר המוביל פעמים רבות לחתוך גבולות שגויים בין אשכולות. יש K-אמצעי של מספר מאפיינים תיאורטים מעניינים. ראשית, הוא מחלק את החלל נתונים לתוך מבנה המכונה דיאגרמת וורונוי שנית, היא קרובה רעיונית לסיווג השכן הקרוב ביותר, וככזה הוא פופולרי כלמידת מכונה. שלישית, ניתן לראות וריאציה של שיטת סיווג המבוססת מודל, והאלגוריתם של לויד כמו וריאציה של אלגוריתם ציפייה - מקסום עבור דגם זה נדון בהמשך.

חלוקה/פיזור מבוסס אשכולות

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

אלגוריתם מבוסס צפיפות

באשכולות מבוססי צפיפות, אשכול מוגדר כאזורי צפיפות גבוהה יותר מאשר שאר סט הנתונים. אובייקטים באזורים הדלילים- נדרשים להפריד אשכולות - בדרך כלל נחשבים לגבול נקודות רעש. שיטת אשכולות מבוססת צפיפות הפופולארית ביותר היא DBSCAN. בניגוד לשיטות רבות חדשות יותר, השיטה כוללת מודל אשכול מוגדר היטב שנקרא "reachability בצפיפות". בדומה אשכולות מבוססת הצמדה, הוא מבוסס על חיבור נקודות בתוך סף מרחק מסוים. עם זאת, הוא מקשר נקודות העונות על קריטריון צפיפות, בחלופה המקורית הוגדרה מספר מינימאלי של אובייקטים אחרים ברדיוס זה. אשכול מורכב מכל האובייקטים מחוברי הצפיפות (אשר יכול ליצור אשכול של צורה שרירותית, בניגוד לרבי שיטות אחרות) בתוספת כל האובייקטים שנמצאים בטווח של האובייקטים האלה. עוד תכונה מעניינת של DBSCANהיא כי המורכבות שלה נמוכה למדי - זה דורש מספר ליניארי של שאילתות טווח על מסד הנתונים - וכי יגלה בעצם את אותן תוצאות (זה דטרמיניסטי עבור נקודות ליבה ורעש, אבל לא עבור נקודות גבול) בכל ריצה, ולכן אין צורך להפעיל אותו מספר פעמים. OPTICS היא הכללה של DBSCAN שמסירה את הצורך לבחור ערך מתאים עבור פרמטר בטווח ומייצרת מכך אשכול היררכי הקרוב לזה של אשכול הצמדה. DeLi-Clu, צפיפות-Link-Clustering משלב רעיונות אשכולות חד הצמדה ו- OPTICSמבטל את הפרמטר לגמרי ומציע שיפור ביצועים מעל OPTICS באמצעות מדד R-tree.

חסרון המפתח שלDBSCAN ואופטיקה הוא שהם מצפים לאיזשהי ירידה בצפיפות לגבולות האשכול. יתר על כן, הם לא יכולים לזהות מבני אשכולות מהותיים אשר נפוץ ברוב הנתונים בחיים האמיתיים. וריאציה שלDBSCAN , EnDBSCAN מזהה ביעילות סוגים של מבנים מהותיים. למשל מערכי נתונים כמו פיזור גאוס חופף – שימוש נפוץ בנתונים מלאכותיים - גבולות האשכול המיוצרים על ידי אלגוריתמים אלה תהיינה לעתים קרובות שרירותיות, כי צפיפות האשכול יורדת ברציפות. על ערכת נתונים המורכבים מתערובות של גאוס, אלגוריתמים אלה כמעט תמיד עם ביצועים טובים יותר מאשר שיטת קיבוץ EM אלגוריתם ציפייה - מקסום כי הם מסוגלים לבנות מודל מדיוק מסוג זה של נתונים.

Mean-shift היא גישת אשכולות שבו כל אובייקט מועבר לאזור הצפוף ביותר בקרבתו, על סמך הערכת צפיפות קרנל בסופו של דבר, אובייקטים מתכנסים למקסימום מקומי של צפיפות. בדומה לאשכולות מבוססי מרחק, "מושכי צפיפות" יכולים לשמש כנציגים של מערך הנתונים, אך Mean shift יכולה לזהות אשכולות שרירותיים בצורה דומה ל-DBSCAN. בשל ההליך האיטרטיבי יקר, , Mean shift בדרך כלל איטי יותר מאשר DBSCAN או k-Means .

התפתחויות אחרונות

בשנים האחרונות מאמץ ניכר כבר הכניס שיפור בביצועים של אלגוריתמים קיימים. ביניהם CLARANS (נג האן, 1994), BIRCH (Zhang et al., 1996). עם הצורך לעבד ערכות נתונים גדולות יותר ויותר (ידוע גם כBig Data ), התפתחו שיטות קדם אשכולות כגון קיבוץ חופה (canopy clustering), אשר יכול לעבד ערכות נתונים ענקיות ביעילות, אבל וכתוצאה מכך "אשכולות" הם רק מחיצות המחולקות באופן גס של הנתונים מוגדרים ולאחר מכן לנתח את המחיצות עם שיטות איטיות קיימות כאלה כמו שיטת k means אלגוריתם k-מרכזים . גישות שונות ומגוונות לאשכולות נוסו כגון קיבוץ מבוסס זרעים.

מקורות

1. Bailey, Ken (1994). "Numerical Taxonomy and Cluster Analysis". Typologies and Taxonomies. p. 34. ISBN 9780803952591.

2. Filipovych, Roman; Resnick, Susan M.; Davatzikos, Christos (2011). "Semi-supervised Cluster Analysis of Imaging Data". NeuroImage. 54 (3): 2185–2197. doi:10.1016/j.neuroimage.2010.09.074. PMC 3008313Freely accessible. PMID 20933091.

3. Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation [1]

4. Bewley, A.; et al. "Real-time volume estimation of a dragline payload". IEEE International Conference on Robotics and Automation. 2011: 1571–1576.

5. Huth, R.; et al. (2008). "Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications". Ann. N.Y. Acad. Sci. 1146: 105–152.