כריית מידע — מרחב למידה אישי

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

מהם חוקי קשר ומדוע הם חשובים?

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

חוק קשר (Association Rule): ביטוי מהצורה X → Y, כאשר X ו-Y הן קבוצות של פריטים (itemsets) ו-X ∩ Y = ∅. החוק מציין כי אם הפריטים ב-X נמצאים בעסקה, סביר להניח שגם הפריטים ב-Y יימצאו בה.

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

מדדים מרכזיים להערכת חוקי קשר

כדי להעריך את ה"מעניינות" או ה"חוזק" של חוק קשר, אנו משתמשים בשלושה מדדים עיקריים: תמיכה (Support), בטחון (Confidence) והרמה (Lift). מדדים אלו קריטיים להבנת המשמעות של חוקי הקשר ולסינון חוקים לא רלוונטיים.

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

בטחון (Confidence): מדד להסתברות ש-Y יופיע בעסקה, בהינתן ש-X כבר הופיע בה. עבור חוק X → Y, הבטחון מוגדר כיחס בין התמיכה של X ∪ Y לתמיכה של X. זהו מדד לחוזק ההשלכה של X על Y.

הרמה (Lift): מדד למידת התלות בין X ל-Y. הוא מוגדר כיחס בין הבטחון של החוק X → Y לתמיכה של Y. ערך Lift הגדול מ-1 מצביע על קשר חיובי (X ו-Y מופיעים יחד יותר מהצפוי במקרה של אי-תלות), ערך קרוב ל-1 מצביע על אי-תלות, וערך קטן מ-1 מצביע על קשר שלילי.

תמיכה (Support)

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

בטחון (Confidence)

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

הרמה (Lift)

מציין את מידת התלות האמיתית. מעל 1 = קשר חיובי אמיתי. קרוב ל-1 = אי-תלות. מתחת ל-1 = קשר שלילי.

אלגוריתם Apriori: הגישה הקלאסית

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

קבוצת פריטים שכיחה (Frequent Itemset): קבוצת פריטים שתמיכתה גבוהה מסף תמיכה מינימלי (min_support) שהוגדר מראש.

אלגוריתם Apriori: זהו נושא מרכזי בבחינות. חשוב להבין את שני השלבים העיקריים שלו: 1. יצירת קבוצות פריטים שכיחות: האלגוריתם סורק את הנתונים מספר פעמים, ויוצר קבוצות פריטים שכיחות בגדלים הולכים וגדלים (k-itemsets). הוא משתמש בעקרון האנטי-מונוטוניות כדי לגזום מועמדים לא שכיחים. 2. יצירת חוקי קשר מקבוצות פריטים שכיחות: לאחר זיהוי כל קבוצות הפריטים השכיחות, האלגוריתם מייצר מהן חוקי קשר פוטנציאליים ובודק את הבטחון שלהם מול סף בטחון מינימלי (min_confidence) שהוגדר.

אתגרים ושיקולים ביישום חוקי קשר

למרות יעילותם, לכריית חוקי קשר ישנם מספר אתגרים:

סילומיות (Scalability): עם מערכי נתונים גדולים מאוד ומספר רב של פריטים, מספר קבוצות הפריטים האפשריות גדל באופן אקספוננציאלי, מה שהופך את החישובים ליקרים מבחינה חישובית.
מספר רב של חוקים: לעיתים קרובות, האלגוריתמים מפיקים אלפי ואף מיליוני חוקי קשר, שרבים מהם עשויים להיות טריוויאליים, מיותרים או לא מעניינים. סינון ודירוג חוקים אלו הוא אתגר בפני עצמו.
נתונים דלילים (Sparse Data): במערכי נתונים שבהם רוב הפריטים אינם מופיעים יחד, קשה למצוא קבוצות פריטים שכיחות משמעותיות.
הגדרת ספים: בחירת ספי ה-min_support וה-min_confidence משפיעה באופן דרמטי על כמות ואיכות החוקים המתגלים. בחירה לא נכונה עלולה להוביל לחוקים מעטים מדי או רבים מדי.

שאלות לדיון

הסבר את ההבדל בין מדד התמיכה למדד הבטחון בחוקי קשר, ומתי עדיף להשתמש בכל אחד מהם?
כיצד עקרון האנטי-מונוטוניות מסייע לאלגוריתם Apriori להתמודד עם אתגר הסילומיות?
תאר מצב שבו חוק קשר בעל תמיכה ובטחון גבוהים עדיין אינו מעניין, וכיצד מדד ה-Lift יכול לעזור לזהות זאת?
אילו שיקולים יש לקחת בחשבון בעת בחירת סף תמיכה מינימלי (min_support) וסף בטחון מינימלי (min_confidence) ביישום מעשי?

נקודות לתשובת מודל

תמיכה ובטחון: תמיכה מודדת שכיחות כללית (X ו-Y יחד), בטחון מודד את חוזק ההשלכה (X גורר Y). תמיכה חשובה לסינון ראשוני של קבוצות פריטים שכיחות, בטחון חשוב להערכת מהימנות החוק.
אנטי-מונוטוניות: אם קבוצת פריטים (למשל {A,B}) אינה שכיחה, אין צורך לבדוק קבוצות גדולות יותר המכילות אותה (למשל {A,B,C}), מכיוון שגם הן לא יהיו שכיחות. זה מקטין משמעותית את מרחב החיפוש.
חוק לא מעניין: חוק שבו X ו-Y מופיעים יחד רק בגלל שכל אחד מהם שכיח מאוד בפני עצמו (למשל, "לחם" → "חלב"). במקרה כזה, ה-Lift יהיה קרוב ל-1, מה שמצביע על אי-תלות או תלות מקרית.
בחירת ספים: סף תמיכה נמוך מדי יוביל למספר עצום של קבוצות פריטים שכיחות וחוקים; גבוה מדי יפספס קשרים חשובים אך נדירים. סף בטחון נמוך מדי יוביל לחוקים לא אמינים; גבוה מדי יפספס חוקים מעניינים עם הסתברות נמוכה יחסית. יש למצוא איזון בהתאם למטרת הניתוח ולאופי הנתונים.

מצאתם טעות או שחסר משהו?