לימוד חוקיות אסוציאטיבי

מושגים שימושיים

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

תמיכה

תמיכה היא אינדיקציה לתדירות הופעת הפריט במאגר הנתונים.
בדוגמה של מאגר הנתונים, ל- itemset {חיתולים, בירה}=X יש תמיכה של 0.2 מאחר שהיא מתרחשת ב-20% מהעסקאות (1 מתוך 5 עסקאות). הארגומנט הוא קבוצה של תנאים מוקדמים, ובכך הופך להיות מגביל יותר ככל שהוא גדל.

ביטחון

ביטחון הוא אינדיקציה לכמות הפעמים שהחוק אומת.
ערך הביטחון של החוק,  ביחס לסט העסקאות , הוא היחס של העסקאות שמכיל X ושמכיל גם Y.
ביטחון מוגדר כ:
.
למשל, לחוק  יש ביטחון  של  בתוך מאגר הנתונים, שפירושו כי על 100% של עסקאות המכילות חמאה ולחם הכלל הוא נכון (100% מהפעמים בו הלקוח קונה חמאה, לחם, הוא קונה גם חלב).
שים לב כי  משמעו התמיכה של איחוד הפריטים ב-X ו-Y. ניסוח כזה קצת מקשה מכיוון שאנחנו בדרך כלל חושבים במונחים של הסתברויות של אירועים ולא של סט פריטים. אנחנו יכולים להתייחס למינוח  כהסתברות משותפת כאשר  , ו - ו- מציינים אירועי עסקאות המכיל סט פריטים  או , בהתאמה.
לפיכך ביטחון יכול להתפרש כ - " הערכה של ההסתברות המותנית , מה ההסתברות למצוא את RHS של כלל בעסקאות בתנאי עסקאות אלה מכילים גם את LHS.

הרמה

הרמה של חוק מוגדרת כ:
או היחס בין התמיכה בפועל לבין המשוערת אם X ו-Y היו בלתי תלויים.
למשל, לחוק {חלב, לחם}->{חמאה} יש הרמה של 
אם ערך ההרמה של החוק היה 1, הדבר היה רומז שההסתברות להתרחשות הקודמת והסוגר אינם תלויים אחד בשני. כאשר שני מאורעות הם בלתי תלויים אחד בשני, כלל לא ניתן להסיק שום חוק.
אם ההרמה  > 1, הדבר מאפשר לנו לדעת באיזו מידה שני המאורעות תלויים אחד בשני, והופך חוקים אלה להיות פוטנציאלים לשימוש עבור חיזוי הסוגר בעתיד.
התועלת של ההרמה היא בכך שהיא מביאה בחשבון את ביטחון החוק ואת סט המידע הכולל.

הרשעה

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

היסטוריה

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

אסוציאציות צליל סטטיסטיות

אחת מהמגבלות של הגישה הסטנדרטית לגילוי אסוציאציות זה על ידי חיפוש מספר גדול של אסוציאציות אפשריות לחיפוש אוספים של פריטים הנראים מקושרים, קיימת סכנה למציאת מספר רב של אסוציאציות מזויפות. קיימים אוספים של פריטים המתרחשים בתדירות בלתי צפויה בנתונים באופן מקרי. לדוגמה, נניח שאנו שוקלים אוסף של 10,000 פריטים ומחפשים כללים המכילים שני פריטים בצד שמאל, ופריט אחד בצד ימין. אם ניישם מבחן סטטיסטי לעצמאות עם רמת מובהקות של 0.05 זה אומר שיש רק סיכוי של 5% לקבלת החוק אם אין אסוציאציות. אם נניח שאין אסוציאציות אנחנו צריכים לצפות למצוא 50,000,000,00 חוקים. גילוי אסוציאציות צליל סטטיסטיות שולטות בסיכון. ברוב המקרים מורידות את הסיכון למציאת אסוציאציות משונות לקביעת רמת מובהקות עבור משתמש מסוים.

אלגוריתמים

הרבה אלגוריתמים ליצירת חוקים אסוציאטיביים הוצגה לאורך זמן.
חלק מהאלגוריתמים הידועים הם  Apriori, Eclat ו- FP-Growth, אבל הם עושים רק חצי מהעבודה, מאחר שהם אלגוריתמים לכריית תדירות סט פריטים. צעד נוסף צריך להתבצע לאחר מכן, ליצור חוקים מתדירות סט פריטים שנמצאו בבסיס הנתונים.

 אלגוריתם Apriori

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

 אלגוריתם Eclat

Eclat (ECLAT,, מסמלת טרנספורמציה מחלקת שקילות) הוא אלגוריתם חיפוש לרוחב המשתמש בסט הצטלבויות. זה הוא אלגוריתם אלגנטי באופן טבעי המתאים לשתי רציפויות כמו ביצוע מקבילי עם מאפייני שיפור מקומיים. הוא הוצג לראשונה על ידי Zaki,, Parthasarathy Li ו- Ogihara בסדרה של ניירות כתובים בשנת 1997.
מוחמד Javeed זכי, Srinivasan Parthasarathy, M. Ogihara, ווי לי:
אלגוריתמים חדשים עבור מהירות הגילוי של איגוד כללי. KDD 1997.
מוחמד Javeed זכי, Srinivasan Parthasarathy, Mitsunori Ogihara, ווי לי:
במקביל אלגוריתמים עבור גילוי של איגוד כללי. נתונים דקות. ידוע. וגילתה. 1(4): 343-373 (1997)

אלגוריתם צמיחה FP

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

AprioriDP

AprioriDP מנצל תכנות דינמי בתדירות כריית סט פריטים. עקרון העבודה היא להסיר את הדור המועמד כמו בעץ FP, אבל הוא מאחסן ספירת תמיכה במבנה נתונים מיוחד במקום העץ.

אלגוריתם הקשר המבוסס כריית חוק אסוציאטיבי

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

אלגוריתמים המבוססים על צומת סטים

FIN ,PrePost ו-PPV הם שלושה אלגוריתמים המבוססים על צומת סטים. הם משתמשים בצמתים לקידוד עץ FP לייצג סט פריטים, ומעסיקים אסטרטגיית חיפוש ראשוני עמוק לגילוי תדירות השימוש בסט פריטים בצומת סטים. 

הפולקלור

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