הרצאה 8

Report
1
‫‪( Unsupervised Learning‬למידה בלתי מפוקחת)‬
‫מה נתון? ומה המטרה?‬
‫‪ ‬נתונים מספר דוגמאות עם אטריבוטים‪ ,‬אבל ללא תגים‬
‫‪ ‬מטרה‪ :‬רוצים למצוא מבנה נסתר בתוך הדוגמאות שיש לנו‪.‬‬
‫‪ ‬איך?‬
‫‪ ‬יש הרבה שיטות‪ ,‬נלמד חלק‪...‬‬
‫‪ ‬דוגמה‪:‬‬
‫‪ ‬נתונים אטריבוטים של לקוחות בחברה‪ .‬האם אפשר להגדיר‬
‫קטגוריות של לקוחות כדי לאפשר פרסום מתאים לכל קטגוריה?‬
‫‪2‬‬
‫דוגמאות של מבנה נסתר‬
‫‪ ‬דוגמה ‪ :1‬סט הנתונים מורכב מ ‪ 14‬דוגמאות בעלי שני אטריבוטים‬
‫‪ ‬האם יש מבנה בנתונים?‬
‫‪ ‬כמה ‪( clusters‬אשכולות) יש?‬
‫‪ ‬דוגמה ‪ :2‬האתגר של ‪( Google Maps Street View‬הוסבר בכיתה)‬
‫‪ ‬דוגמה ‪ :3‬סט הנתונים מורכב מ ‪ 13‬דוגמאות בעלי שני אטריבוטים‬
‫‪ ‬כמה ממדים יש בנתונים? כמה ממדים חייבים כדי לתאר את הנתונים?‬
‫‪3‬‬
‫אלגוריתם ‪K-Means‬‬
‫‪ ‬אלגוריתם ‪ K-Means‬הינו אלגוריתם פשוט ויעיל לביצוע ניתוח‬
‫אשכולות כאשר ידוע לנו מספר אשכולות רצוי‬
‫‪ ‬מה הוא ניתוח אשכולות הרצוי?‬
‫‪ ‬כל דוגמה מסט אימון תשתייך לאשכול אחד בלבד‬
‫‪ ‬לכל אשכול נגדיר נקודה מייצגת‪ ,‬נקרא לה מרכז האשכול‬
‫‪‬‬
‫היא יכולה להיות אחת מהדוגמאות‪ ,‬או סתם נקודה‬
‫‪ ‬ממוצע המרחקים בין הדוגמאות למרכזי האשכולות יהיה קטן ככל‬
‫הניתן‬
‫‪ ‬קשה (במובן כמות החישוב הנדרש) לפתור את הבעיה באופן אופטימלי‬
‫‪ K-Means ‬נותן פתרון טוב (או אפילו אופטימלי) במקרים רבים‬
‫‪4‬‬
‫שלבי האלגוריתם ‪K-Means‬‬
‫בוחרים ‪ K‬מרכזים של אשכולות באופן רנדומלי‬
‫‪.1‬‬
‫‪‬‬
‫‪5‬‬
‫דוגמה (‪)K=2‬‬
‫‪ .2‬משייכים כל דוגמה לאשכול (כלומר‪ ,‬מרכז) הקרוב ביותר (כגון לפי‬
‫מרחק אוקלידי)‬
‫‪ .3‬מחשבים מרכז חדש עבור כל אשכול כממוצע של הדוגמאות‪:‬‬
‫‪6‬‬
‫‪ .4‬חוזרים לשלב ‪( 2‬כלומר‪ ,‬מבצעים שלבים ‪ 2-3‬פעמים רבות) ומשייכים‬
‫דוגמאות לאשכולות מחדש‬
‫‪ .5‬האלגוריתם נעצר כשאין שינוי בשלב ‪.2‬‬
‫‪ ‬עבור הדוגמה‪ ,‬האלגוריתם מסתיים באופן הבא‪:‬‬
‫‪7‬‬
‫חסרונות של ‪K-Means‬‬
‫‪ ‬ל ‪ K-Means‬יש מספר חסרונות‪:‬‬
‫‪ ‬אנו צריכים לדעת מהו מספר האשכולות ‪K‬‬
‫‪‬‬
‫‪‬‬
‫לפעמים אפשר להשתמש בחוק אצבע‪:‬‬
‫(‪ n‬הינו מספר דוגמאות בסט אימון)‬
‫מידע נוסף על הבעיה‪:‬‬
‫‪http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set‬‬
‫‪ ‬לפעמים ‪ K-Means‬נתקע בפתרון גרוע‪.‬‬
‫‪‬‬
‫‪8‬‬
‫דוגמה‪:‬‬
‫למידת חוקי אסוציאציה‬
‫‪9‬‬
‫מה זה ‪Association Rule Learning‬‬
‫‪ ‬המטרה של ‪ARL ,Association Rule Learning/Mining‬‬
‫(למידת\כריית חוקי אסוציאציה) היא מציאת קשרים‬
‫(אסוציאציות) מעניינים בין פריטים שונים באוספים גדולים של‬
‫נתונים (כמו בסיסי נתונים או מחסני נתונים)‬
‫‪ ‬למשל‪ :‬בנתונים של קניות‪ ,‬הפרטים יהיו מוצרים שנקנו‪.‬‬
‫‪ ‬אפשר להסתכל על ‪ ARL‬כסוג של ‪,Unsupervised Learning‬‬
‫כי ב ‪ ARL‬אנו מגלים מבנה נסתר בנתונים‪ :‬קשרים בין‬
‫אטריבוטים‬
‫‪10‬‬
‫יישומי ‪ARL‬‬
‫‪ ‬בשל ההצלחה של יישומי ‪ ARL‬עבור בעיות עסקיות‪ ,‬מכנים את‬
‫‪ ARL‬בשם ‪( Market Basket Analysis‬ניתוח סל קניות)‬
‫‪ ‬דוגמה‪ MBA :‬יכול לגלות שאם לקוח קונה מחשב וחבילת אנטי וירוס‪,‬‬
‫אזי ב ‪ 70%‬מהמקרים הוא קונה גם חבילה של תוספת אחריות‬
‫‪ ‬קיימים גם יישומים בתחומים אחרים‪:‬‬
‫‪ ‬גילוי קשרים בין סימפטומים למחלות‬
‫‪ ‬גילוי קשרים בין גֶנים לתפקידם‬
‫‪ ‬אנחנו נתרכז ב ‪Market Basket Analysis‬‬
‫‪11‬‬
‫הגדרה של ‪Market Basket Analysis‬‬
‫‪ ‬הקלט של ‪ Market Basket Analysis‬הוא רשימה של‬
‫טרנסקציות (עסקאות)‪ .‬דוגמה‪:‬‬
‫‪ ‬עבור מרכול‪ ,‬נניח קודי מוצרים‪:‬‬
‫‪ – 1 ‬לחם‪ – 2 ,‬חלב‪ – 3 ,‬חמאה‪ – 4 ,‬מים‬
‫‪ ‬קיימים נתונים עבור ‪ 6‬טרנסקציות‪:‬‬
‫מוצרים‬
‫‪12‬‬
‫מס' טרנסקציה‬
‫‪1, 2, 3, 4‬‬
‫‪1‬‬
‫‪2, 3, 4‬‬
‫‪2‬‬
‫‪2, 3‬‬
‫‪3‬‬
‫‪1, 2, 4‬‬
‫‪4‬‬
‫‪1, 2, 3, 4‬‬
‫‪5‬‬
‫‪2, 4‬‬
‫‪6‬‬
‫הגדרה של ‪Market Basket Analysis‬‬
‫‪ ‬הפלט של ‪ Market Basket Analysis‬הוא רשימה של‬
‫אסוציאציות בצורת ]‪X⇒Y [S%, C%‬‬
‫‪ ‬אסוציאציה לדוגמה‪:‬‬
‫[‪{ ]30% ,70%‬תוספת אחריות} ⇒ {חבילת אנטי וירוס‪ ,‬מחשב}‬
‫‪( Support – S% ‬תמיכה)‪ ,‬מספר (באחוזים) הטרנסקציות בהם כל‬
‫המוצרים באסוציאציה הופיעו ביחד‬
‫‪‬‬
‫‪‬‬
‫‪ Support‬הינה מדידה של חשיבות האסוציאציה‬
‫בדרך כלל קובעים תמיכה מינימלית ומוצאים רק אסוציאציות עם תמיכה לכל‬
‫הפחות כמו תמיכה מינימלית‬
‫‪( Confidence – C% ‬ודאות) ‪ ,‬מספר הפעמים (באחוזים) שכאשר‬
‫המוצרים ‪ X‬הופיעו בטרנסקציה‪ ,‬גם מוצרים ‪ Y‬הופיעו באותה‬
‫טרנסקציה‬
‫‪‬‬
‫‪13‬‬
‫‪ Confidence‬הינה מדידה של חוזק הקשר בין הפריטים באסוציאציה‬
‫שלבים בלמידת חוקי אסוציאציה‬
‫‪ ‬תהליך למידת חוקי אסוציאציה מורכב משני שלבים‪:‬‬
‫‪ .1‬מציאת קבוצות מוצרים בעלות תמיכה (‪ )support‬גבוה (≥‬
‫מהתמיכה המינימלית)‬
‫‪ .2‬הפקת חוקי אסוציאציה בין המוצרים בקבוצות בעלות תמיכה גבוהה‬
‫‪ ‬השלב השני הוא פשוט ממבט אלגוריתמי (אכן זמן החישוב‬
‫עלול להיות ממושך)‬
‫‪ ‬האלגוריתם שנלמד עכשיו מבצע את השלב הראשון‬
‫‪14‬‬
‫אלגוריתם ‪Apriori‬‬
‫‪ ‬אלגוריתם ‪ Apriori‬מחשב קבוצות מוצרים בעלות תמיכה‬
‫גבוהה (≥ מהתמיכה המינימלית)‬
‫‪ ‬שלבים של האלגוריתם‪:‬‬
‫מחשבים תמיכה של כל מוצר בנפרד (כלומר‪ ,‬תמיכה של קבוצות של‬
‫מוצר אחד)‬
‫‪.1‬‬
‫‪‬‬
‫עבור הדוגמה שלנו‪:‬‬
‫מוצרים‬
‫‪15‬‬
‫מס' טרנסקציה‬
‫‪1, 2, 3, 4‬‬
‫‪1‬‬
‫‪2, 3, 4‬‬
‫‪2‬‬
‫‪2, 3‬‬
‫‪3‬‬
‫‪1, 2, 4‬‬
‫‪4‬‬
‫‪1, 2, 3, 4‬‬
‫‪5‬‬
‫‪2, 4‬‬
‫‪6‬‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫קבוצת מוצרים‬
‫‪3‬‬
‫‪1‬‬
‫‪6‬‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪4‬‬
‫אלגוריתם ‪Apriori‬‬
‫‪ .2‬מוחקים את כל קבוצות המוצרים בעלות תמיכה קטנה מהתמיכה‬
‫המינימלית‬
‫‪‬‬
‫‪‬‬
‫עבור הדוגמה שלנו‪ ,‬נניח תמיכה מינימלית של ‪( 50%‬כלומר ‪ 3‬מתוך ‪6‬‬
‫טרנסקציות)‬
‫נבצע את השלב‪:‬‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫‪16‬‬
‫קבוצת מוצרים‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫קבוצת מוצרים‬
‫‪3‬‬
‫‪1‬‬
‫‪3‬‬
‫‪1‬‬
‫‪6‬‬
‫‪2‬‬
‫‪6‬‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪4‬‬
‫‪5‬‬
‫‪4‬‬
‫אלגוריתם ‪Apriori‬‬
‫‪ .3‬מחשבים קבוצות של שני מוצרים המבוססות על הקבוצות של מוצר‬
‫אחד שחישבנו ומוחקים אלו בעלות תמיכה נמוכה‬
‫מוצרים‬
‫‪1, 2, 3, 4‬‬
‫‪1‬‬
‫‪2, 3, 4‬‬
‫‪2‬‬
‫‪2, 3‬‬
‫‪3‬‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫קבוצת מוצרים‬
‫‪1, 2, 4‬‬
‫‪4‬‬
‫‪3‬‬
‫‪1, 2‬‬
‫‪1, 2, 3, 4‬‬
‫‪5‬‬
‫‪2‬‬
‫‪1, 3‬‬
‫‪2, 4‬‬
‫‪6‬‬
‫‪3‬‬
‫‪1, 4‬‬
‫‪4‬‬
‫‪2, 3‬‬
‫‪5‬‬
‫‪2, 4‬‬
‫‪3‬‬
‫‪3, 4‬‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫‪17‬‬
‫מס' טרנסקציה‬
‫קבוצת מוצרים‬
‫‪3‬‬
‫‪1‬‬
‫‪6‬‬
‫‪2‬‬
‫‪4‬‬
‫‪3‬‬
‫‪5‬‬
‫‪4‬‬
‫אלגוריתם ‪Apriori‬‬
‫‪ .4‬מחשבים קבוצות של שלושה מוצרים המבוססות על הקבוצות של‬
‫שני מוצרים שחישבנו ומוחקים את אלו בעלות תמיכה נמוכה‬
‫‪ .5‬ממשיכים באופן זה עד שמגיעים למצב שאין קבוצות של הגודל‬
‫הנוכחי בעלות תמיכה מספיקה‬
‫‪ ‬עבור הדוגמה‪ ,‬גודל האחרון של הקבוצות הוא ‪:3‬‬
‫מס' טרנסקציה‬
‫מוצרים‬
‫‪1, 2, 3, 4‬‬
‫‪1‬‬
‫‪2, 3, 4‬‬
‫‪2‬‬
‫‪2, 3‬‬
‫‪3‬‬
‫‪1, 2, 4‬‬
‫‪4‬‬
‫‪1, 2, 3, 4‬‬
‫‪5‬‬
‫‪2, 4‬‬
‫‪6‬‬
‫מס' טרנסקציות‬
‫‪18‬‬
‫מס' טרנסקציות‬
‫(תמיכה ללא‬
‫אחוזים)‬
‫קבוצת מוצרים‬
‫‪3‬‬
‫‪1, 2‬‬
‫‪3‬‬
‫‪1, 4‬‬
‫‪4‬‬
‫‪2, 3‬‬
‫‪5‬‬
‫‪2, 4‬‬
‫‪3‬‬
‫‪3, 4‬‬
‫קבוצת מוצרים‬
‫‪3‬‬
‫‪1, 2, 4‬‬
‫‪3‬‬
‫‪2, 3, 4‬‬
‫‪ ‬למדנו‪:‬‬
‫‪ ‬אלגוריתם ‪ K-Means‬עבור בעיית ניתוח אשכולות‬
‫‪ ‬אלגוריתם ‪ Apriori‬עבור ‪Association Rule‬‬
‫‪Learning‬‬
‫‪19‬‬

similar documents