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

לימוד חוקיות אסוציאטיבי הוא כלל המבוסס על למידה חישובית למטרת גילוי יחסים מעניינים בין משתנים במאגרי מידע גדולים. תפקידו לזהות חוקיות חזקה במאגרי המידע תוך שימוש במדידות ענייניות ^[1]. בהתבסס על רעיונות החוקיות החזקה של ראקש ארגוואל, תומאס למילנסקי וארון סוואמי מוצגים חוקים אסוציאטיביים לגילוי תדירויות בין מוצרים המופיעים בנתוני עסקאות הנאספות בנקודות המכירה (Point Of Sale - POS) בסופרמרקטים. למשל, החוק ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$ כפי שמוצאים בנתוני המכירות בסופרמרקטים יצביעו על כך שאם לקוח ירכוש בצל ותפוח אדמה יחד, רוב הסיכויים שירצה לרכוש גם בשר טחון. מידע כזה יכול לשמש בסיס לקבלת החלטות לגבי פעילויות שיווקיות כגון, קידום מכירות, תמחור או מיקום מוצרים. בנוסף לדוגמה הנ"ל מתחום ניתוח סל מכירות, חוקיות אסוציאטיבית מיושמת כיום בהרבה ענפים כגון ייצור רציף וביואינפורמטיקה. בניגוד לרצף כרייה, חוקיות אסוציאטיבית בדרך כלל אינה מחשיבה את הסדר של פריטים בתוך העסקה או בעסקאות המעבר.

הגדרה

דוגמה: מאגר נתונים עם 5 עסקאות ו-5 פריטים
תעודת זהות עסקית	חלב	לחם	חמאה	בירה	חיתולים
1	1	1	0	0	0
2	0	0	1	0	0
3	0	0	0	1	1
4	1	1	1	0	0
5	0	1	0	0	0

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

נגדיר ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}$ קבוצה של תכונות בינאריות הנקראות פריטים.

נגדיר ${\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}}$ קבוצה של עסקאות הנקראות מאגר הנתונים.

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

כל חוק מורכב על ידי שני סטים של פריטים, הידועים גם בשם סט פריטים (itemsets).

$X\Rightarrow Y,where{\displaystyle X,Y\subseteq I}X,Y\subseteq I.$

כדי להמחיש את המושגים, נשתמש בדוגמה קטנה מתחום הסופרמרקטים. סט הפריטים הם {חיתולים, בירה, חמאה, לחם, חלב} $I=$ ובטבלה מוצג מאגר נתונים קטן המכיל את הפריטים, כאשר בכל תא הערך 1 מציין את נוכחותו של הפריט בעסקה, והערך 0 מייצג את העדר הפריט בעסקה.

דוגמה לחוק עבור סופרמרקט יכול להיות {חמאה, לחם} $\Leftarrow$ {חלב} ופירושו: אם הלקוח רכש חמאה ולחם אזי הוא ירכוש גם חלב.

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

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

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

נגדיר $X$ להיות סט פריטים, $X\Rightarrow Y$ כחוק אסוציאטיבי ו- $T$ כסט של עסקאות של מאגר נתונים נתון.

תמיכה

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

${\displaystyle \mathrm {supp} (X)={\frac {|\{t\in T;X\subseteq t\}|}{|T|}}}$

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

ביטחון

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

ערך הביטחון של החוק, $,{\displaystyle X\Rightarrow Y}$ ביחס לסט העסקאות $T$ , הוא היחס של העסקאות שמכיל X ושמכיל גם Y.

ביטחון מוגדר כ:

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)}$ .

למשל, לחוק ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$ יש ביטחון של $0.2/0.2=1.0$ בתוך מאגר הנתונים, שפירושו כי על 100% של עסקאות המכילות חמאה ולחם הכלל הוא נכון (100% מהפעמים בו הלקוח קונה חמאה, לחם, הוא קונה גם חלב).

שים לב כי ${\displaystyle \mathrm {supp} (X\cup Y)}$ משמעו התמיכה של איחוד הפריטים ב-X ו-Y. ניסוח כזה קצת מקשה מכיוון שאנחנו בדרך כלל חושבים במונחים של הסתברויות של אירועים ולא של סט פריטים. אנחנו יכולים להתייחס למינוח ${\displaystyle \mathrm {supp} (X\cup Y)}$ כהסתברות משותפת כאשר ${\displaystyle P(E_{X}\wedge E_{Y})}$ , ו - ${\displaystyle E_{X}}$ ו- $E_{Y}$ מציינים אירועי עסקאות המכיל סט פריטים $X$ או $Y$ , בהתאמה.^[3]

לפיכך ביטחון יכול להתפרש כ - " הערכה של ההסתברות המותנית $P(E_{Y}|E_{X})$ , מה ההסתברות למצוא את RHS של כלל בעסקאות בתנאי עסקאות אלה מכילים גם את LHS.

הרמה

הרמה של חוק מוגדרת כ:

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}}$

או היחס בין התמיכה בפועל לבין המשוערת אם X ו-Y היו בלתי תלויים.

למשל, לחוק {חלב, לחם} $\Leftarrow$ {חמאה} יש הרמה של ${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$

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

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

התועלת של ההרמה היא בכך שהיא מביאה בחשבון את ביטחון החוק ואת סט המידע הכולל.

הרשעה

הרשעה של חוק מוגדרת כ:

${\mathrm {conv} }(X\Rightarrow Y)={\frac {1-{\mathrm {supp} }(Y)}{1-{\mathrm {conf} }(X\Rightarrow Y)}}$ .

למשל, לחוק ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ יש הרשעה של ${\frac {1-0.4}{1-0.5}}=1.2$ , ויכולה להתפרש כיחס בין התדירות הצפויה ש-X יתרחש ללא Y (ובמילים אחרות, התדירות שהחוק יוצר תחזית שגויה) אם X ו-Y היו מחולקים באופן בלתי תלוי על ידי התדירות הנצפית של התחזיות השגויות. בדוגמה זו, ערך ההרשעה 1.2 מראה כי החוק ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ יהיה שגוי ביותר מ-20% (1.2 פעמים) אם הקשר בין X ו-Y יהיה לגמרי מקרי.

תהליך

סריג itemset תדיר, כאשר צבע התיבה מציין את כמות העסקאות המכילות שילוב של פריטים. שים לב כי רמות נמוכות יותר של הסריג יכולות להכיל לכל היותר את המספר המינימלי של פריטים מהם מורכבים; למשל {ac} יכול לקבל לכל היותר $min(a,c)$ פריטים. ידוע בשם downward-closure property.

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

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

בעוד שהשלב השני הוא יחסית פשוט, הצעד הראשון מצריך תשומת לב רבה יותר.

קיים קושי במציאת כל הסטים של הפריטים התכופים במאגר הנתונים מאחר שהדבר כרוך בחיפוש כל הסטים של הפריטים האפשריים (שילובים של פריטים). סט הפריטים האפשריים הוא קבוצת החזקה של $I$ וגודלו ${\displaystyle 2^{n}-1}$ (לא כולל קבוצה ריקה). אף על פי שערכו גדל באופן אקספוננציאלי, חיפוש יעיל יהיה אפשרי באמצעות downward-closure property עבור התמיכה,^[4] אשר מבטיח כי עבור סט פריטים תדיר, כל תתי הקבוצות שלו יהיו גם כן בתדירות גבוהה ולכן, לא יוצר מצב של סט פריטים שאינו תדיר יהיה תת-קבוצה עם תדירות גבוהה.

היסטוריה

רעיון החוקיות האסוציאטיבית הפך לפופולרי בעיקר בשל פרסום המאמר אגראוול, בשנת 1993, ונחשב לאחר המאמרים המצוטטים ביותר בתחום כריית הנתונים. עם זאת, קיימת אפשרות כי מה שמכונה כיום "חוקים אסוציאטיביים", דומה לערך שפורסם בשנת 1966 בדבר שיטת כריית הנתונים הכללית שפותחה על ידי פטר האג'ק.^[5]

שימוש מוקדם (circa 1989) של מינימום תמיכה וביטחון למציאת כל חוקי האסוציאציות היא תכונה מבוססת מודלי מסגרת, שמוצאת את כל החוקים עם ${\displaystyle \mathrm {supp} (X)}$ ו ${\displaystyle \mathrm {conf} (X\Rightarrow Y)}$ יותר גבוהים מהאילוצים שהגדיר המשתמש.

אמצעים חלופיים של ענייניות

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

כל-אמון^[6]
כוח קולקטיבי ^[7]
הרשעה^[8]
מינוף^[9]
הרמה ^[10]

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

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

אחת מהמגבלות של הגישה הסטנדרטית לגילוי אסוציאציות זה על ידי חיפוש מספר גדול של אסוציאציות אפשריות לחיפוש אוספים של פריטים הנראים מקושרים, קיימת סכנה למציאת מספר רב של אסוציאציות מזויפות. קיימים אוספים של פריטים המתרחשים בתדירות בלתי צפויה בנתונים באופן מקרי. לדוגמה, נניח שאנו שוקלים אוסף של 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 מייצג דפוס תדירות.^[12]

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

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

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

אחרים

AprioriDP

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

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

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

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

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

הפולקלור

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

ראו גם

למידת מכונה

קישורים חיצוניים

ביבליוגרפיות

נרחב ביבליוגרפיה על כללי התאגדות על ידי J. M. לונה
מבואר ביבליוגרפיה על כללי התאגדות על ידי מ Hahsler
Statsoft אלקטרוני סטטיסטיקה לימוד: כללי התאגדות(הקישור אינו פעיל) על ידי Dell תוכנה

הערות שוליים

^ Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
^ Hahsler, Michael (2005). "Introduction to arules – A computational environment for mining association rules and frequent item sets" (PDF). Journal of Statistical Software.
^ Michael Hahsler (2015).
^ Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). "Chapter 6. Association Analysis: Basic Concepts and Algorithms" (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.
^ Hájek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004, מסת"ב 978-3-540-22479-2
^ Omiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003
^ Aggarwal, Charu C.; and Yu, Philip S.; A new framework for itemset generation, in PODS 98, Symposium on Principles of Database Systems, Seattle, WA, USA, 1998, pages 18-24
^ Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 255-264
^ Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248
^ Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 265-276
^ Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004
^ Han (2000). "Mining Frequent Patterns Without Candidate Generation". Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. SIGMOD '00: 1–12. doi:10.1145/342009.335372.
^ Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[piatetsky-1] Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.

[הערה_מספר_20170222045944:0-2] Hahsler, Michael (2005). "Introduction to arules – A computational environment for mining association rules and frequent item sets" (PDF). Journal of Statistical Software.

[michael.hahsler.net-3] Michael Hahsler (2015).

[4] Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). "Chapter 6. Association Analysis: Basic Concepts and Algorithms" (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7.

[pospaper-5] Hájek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004, מסת"ב 978-3-540-22479-2

[allconfidence-6] Omiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003

[collectivestrength-7] Aggarwal, Charu C.; and Yu, Philip S.; A new framework for itemset generation, in PODS 98, Symposium on Principles of Database Systems, Seattle, WA, USA, 1998, pages 18-24

[brin-dynamic-itemset1-8] Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 255-264

[leverage-9] Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248

[brin-dynamic-itemset2-10] Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 265-276

[measurescomp-11] Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004

[12] Han (2000). "Mining Frequent Patterns Without Candidate Generation". Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. SIGMOD '00: 1–12. doi:10.1145/342009.335372.

[13] Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]