מבוא לתלות פונקציונלית

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

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

לדוגמה, בטבלה למעלה, (בנסון, M, M איבר) הוא אוסף של תכונות (מטופל, פול, דוקטור).
באופן רשמי יותר, זה כתוב כך: [מטופל, מין, רופא] = (בנסון, איבר M, M).
כעת אנו יכולים להציג את המושג של תלות תפקודית (FD):

הגדרה 1. היחס R עומד בחוק הפדרלי X → Y (כאשר X, Y ⊆ R) אם ורק אם עבור tuples כלשהם , ∈ R מחזיקה: אם [X] = [X], אז [Y] = [Y]. במקרה זה, אנו אומרים ש-X (הקובע, או קבוצת התכונות המגדירה) קובע פונקציונלית את Y (הקבוצה התלויה).

במילים אחרות, נוכחותו של חוק פדרלי X → Y זה אומר שאם יש לנו שני tuples R והם תואמים בתכונות X, אז הם יתאימו בתכונות Y.
ועכשיו, לפי הסדר. בואו נסתכל על התכונות סבלני и פול שלגביו אנו רוצים לברר האם יש ביניהם תלות או לא. עבור קבוצה כזו של תכונות, ייתכן שקיימות התלות הבאה:

1. מטופל → מגדר
2. מגדר → מטופל

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

לפיכך, תלות פונקציונלית מאפשרת לקבוע את הקשרים הקיימים בין קבוצות של תכונות טבלה. מכאן ואילך נשקול את הקשרים המעניינים ביותר, או יותר נכון כאלה X → Yמה שהם:

• לא טריוויאלי, כלומר, הצד הימני של התלות אינו תת-קבוצה של השמאל (Y ̸⊆ X);
• מינימלי, כלומר, אין תלות כזו Z → Yכי Z ⊂ X.

התלות שנחשבו עד נקודה זו היו קפדניות, כלומר, הן לא סיפקו הפרות כלשהן על השולחן, אך בנוסף להן, ישנן גם כאלה המאפשרות חוסר עקביות בין ערכי הטפולים. תלות כזו ממוקמת בכיתה נפרדת, הנקראת משוערת, ומותר להפר אותן עבור מספר מסוים של tuples. סכום זה מוסדר על ידי מחוון השגיאה המקסימלי emax. לדוגמה, שיעור השגיאות = 0.01 עשויה לומר שניתן להפר את התלות על ידי 1% מהטפולים הזמינים בקבוצת התכונות הנחשבת. כלומר, עבור 1000 רשומות, מקסימום 10 טפולים יכולים להפר את החוק הפדרלי. נשקול מדד שונה במקצת, המבוסס על ערכים שונים בזוגיות של הטפולים שמשווים. בשביל התמכרות X → Y על היחס r זה נחשב כך:

בואו לחשב את השגיאה עבור רופא → מטופל מהדוגמה למעלה. יש לנו שני tuples שהערכים שלהם שונים בתכונה סבלני, אבל חופפים ל דוֹקטוֹר: [רופא, מטופל] = (רובין, אליס) ו [רופא, מטופל] = (רובין, גרהם). בעקבות ההגדרה של שגיאה, עלינו לקחת בחשבון את כל הזוגות המתנגשים, מה שאומר שיהיו שניים מהם: (, ) וההיפוך שלו (, ). בואו נחליף אותו בנוסחה ונקבל:

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

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

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

דוגמה לשגיאת נתונים:

דוגמה לכפילויות בנתונים:

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

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

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

תחום נוסף שבו התלות מצאה את היישום שלהן הוא הפחתת הממדיות של מרחב התכונה במשימות כגון בניית מסווג Bayes נאיבי, זיהוי תכונות משמעותיות ופרמטר מחדש של מודל רגרסיה. במאמרים המקוריים, משימה זו נקראת קביעת רלוונטיות מיותרת ותכונה [5, 6], והיא נפתרת באמצעות שימוש פעיל במושגי מסד נתונים. עם הופעתן של עבודות כאלה, ניתן לומר שכיום יש ביקוש לפתרונות המאפשרים לנו לשלב את מסד הנתונים, הניתוח והיישום של בעיות האופטימיזציה הנ"ל לכלי אחד [7, 8, 9].

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

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

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


אתה יכול לקרוא עוד על סיווג זה [4]. להלן דוגמאות לאלגוריתמים לכל סוג:

נכון לעכשיו, מופיעים אלגוריתמים חדשים המשלבים מספר גישות למציאת תלות פונקציונלית. דוגמאות לאלגוריתמים כאלה הם Pyro [2] ו-HyFD [3]. ניתוח של עבודתם צפוי במאמרים הבאים של סדרה זו. במאמר זה נבחן רק את המושגים והלמה הבסיסיים הדרושים להבנת טכניקות זיהוי תלות.

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

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

על מנת להציג את המושג סריג, יש צורך להגדיר קבוצה מסודרת חלקית (או קבוצה מסודרת חלקית, בקיצור כ-poset).

הגדרה 2. אומרים שקבוצה S מסודרת חלקית לפי היחס הבינארי ⩽ אם עבור כל a, b, c ∈ S המאפיינים הבאים מתקיימים:

1. רפלקסיביות, כלומר, a ⩽ א
2. אנטי-סימטריה, כלומר אם a ⩽ b ו-b ⩽ a, אז a = b
3. טרנזיטיביות, כלומר, עבור a ⩽ b ו- b ⩽ c נובע ש- a ⩽ c

יחס כזה נקרא יחס סדר חלקי (רופף), והקבוצה עצמה נקראת קבוצה מסודרת חלקית. סימון רשמי: ⟨S, ⩽⟩.

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

דוגמה יותר משמעותית. שקול את קבוצת כל תת-הקבוצות {1, 2, 3}, מסודרות לפי יחס ההכללה ⊆. ואכן, יחס זה עונה על כל תנאי הסדר החלקי, ולכן ⟨P ({1, 2, 3}), ⊆⟩ הוא קבוצה מסודרת חלקית. האיור שלהלן מציג את המבנה של קבוצה זו: אם ניתן להגיע לאלמנט אחד באמצעות חצים לאלמנט אחר, אז הם נמצאים ביחסי סדר.

נזדקק לשתי הגדרות פשוטות נוספות מתחום המתמטיקה - עליונה ואינפימום.

הגדרה 3. תן ⟨S, ⩽⟩ להיות קבוצה מסודרת חלקית, A ⊆ S. הגבול העליון של A הוא אלמנט u ∈ S כך ש- ∀x ∈ S: x ⩽ u. תן U להיות קבוצת כל הגבולות העליונים של S. אם יש אלמנט הכי קטן ב-U, אז הוא נקרא העליון והוא מסומן sup A.

הרעיון של גבול תחתון מדויק מוצג באופן דומה.

הגדרה 4. תן ⟨S, ⩽⟩ להיות קבוצה מסודרת חלקית, A ⊆ S. האינפיום של A הוא אלמנט l ∈ S כך ש- ∀x ∈ S: l ⩽ x. תן L להיות קבוצת כל הגבול התחתון של S. אם יש אלמנט הגדול ביותר ב-L, אז הוא נקרא infimum והוא מסומן כ-inf A.

שקול כדוגמה את הסט המסודר בחלקו לעיל ⟨P ({1, 2, 3}), ⊆⟩ ומצא בו את העליונה והאינפימום:

כעת נוכל לנסח את ההגדרה של סריג אלגברי.

הגדרה 5. תן ⟨P,⩽⟩ להיות קבוצה מסודרת חלקית כך שלכל תת-קבוצה של שני אלמנטים יש גבול עליון ותחתון. ואז P נקרא סריג אלגברי. במקרה זה, sup{x, y} נכתב כ-x ∨ y, ו-inf {x, y} כ-x ∧ y.

בוא נבדוק שדוגמה העבודה שלנו ⟨P ({1, 2, 3}), ⊆⟩ היא סריג. ואכן, עבור כל a, b ∈ P ({1, 2, 3}), a∨b = a∪b, ו-a∧b = a∩b. לדוגמה, שקול את הקבוצות {1, 2} ו-{1, 3} ומצא את ה-Infimum והעליון שלהם. אם נחתוך אותם, נקבל את הסט {1}, שיהיה האינפימום. אנו מקבלים את העליונה על ידי שילובם - {1, 2, 3}.

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

האיור שלהלן מראה כיצד ניתן להשתמש בסריג אלגברי בבעיה של מציאת FZ. כאן כל קצה (X, XY) מייצג תלות X → Y. למשל, עברנו את השלב הראשון ויודעים שההתמכרות נשמרת א → ב (נציג זאת כחיבור ירוק בין הקודקודים A и B). משמעות הדבר היא שבהמשך, כאשר אנו נעים לאורך הסריג, ייתכן שלא נבדוק את התלות A, C → B, כי זה כבר לא יהיה מינימלי. באופן דומה, לא היינו בודקים זאת אם התלות הייתה מתקיימת ג → ב.

בנוסף, ככלל, כל האלגוריתמים המודרניים לחיפוש חוקים פדרליים משתמשים במבנה נתונים כגון מחיצה (במקור המקורי - מחיצה חשופה [1]). ההגדרה הרשמית של מחיצה היא כדלקמן:

הגדרה 6. תן X ⊆ R להיות קבוצה של תכונות ליחס r. אשכול הוא קבוצה של מדדים של tuples ב-r בעלי אותו ערך עבור X, כלומר, c(t) = {i|ti[X] = t[X]}. מחיצה היא קבוצה של אשכולות, לא כולל אשכולות באורך יחידה:

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

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

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

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

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

בואו נסתכל על דוגמה:

במקרה הראשון, קיבלנו מחיצה ריקה. אם אתה מסתכל מקרוב על הטבלה, אז אכן, אין ערכים זהים עבור שתי התכונות. אם נשנה מעט את הטבלה (המקרה מימין), כבר נקבל צומת לא ריקה. יתר על כן, שורות 1 ו-2 מכילות למעשה את אותם ערכים עבור התכונות פול и רופא.

לאחר מכן, נצטרך מושג כזה כמו גודל מחיצה. רִשְׁמִית:

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

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

למה 1. התלות A, B → C מתקיימת אם ורק אם

על פי הלמה, כדי לקבוע אם מתקיימת תלות, יש לבצע ארבעה שלבים:

1. חשב את המחיצה עבור הצד השמאלי של התלות
2. חשב את המחיצה עבור הצד הימני של התלות
3. חשב את המכפלה של השלב הראשון והשני
4. השווה את הגדלים של המחיצות שהתקבלו בשלב הראשון והשלישי

להלן דוגמה לבדיקה האם התלות מתקיימת על פי הלמה זו:

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

הפניות:

1. חוהטלה י' ואח'. TANE: אלגוריתם יעיל לגילוי תלות פונקציונלית ומשוערת // יומן המחשב. – 1999. – ת' 42. – מס'. 2. – עמ' 100-111.
2. Kruse S., Naumann F. גילוי יעיל של תלות משוערת // Proceedings of the VLDB Endowment. – 2018. – ת' 11. – מס'. 7. – עמ' 759-772.
3. Papenbrock T., Naumann F. גישה היברידית לגילוי תלות תפקודית //הליכי הכנס הבינלאומי 2016 לניהול נתונים. – ACM, 2016. – עמ' 821-833.
4. Papenbrock T. et al. גילוי תלות תפקודית: הערכה ניסיונית של שבעה אלגוריתמים //Proceedings of the VLDB Endowment. – 2015. – ת' 8. – מס'. 10. – עמ' 1082-1093.
5. קומאר א' ואח'. להצטרף או לא להצטרף?: חושבים פעמיים על הצטרפות לפני בחירת תכונה //הליכי הכנס הבינלאומי 2016 לניהול נתונים. – ACM, 2016. – עמ' 19-34.
6. אבו חמיס מ' ואח'. למידה בתוך מסד נתונים עם טנזורים דלילים //הליכים של סימפוזיון ACM SIGMOD-SIGACT-SIGAI ה-37 על עקרונות מערכות מסדי נתונים. – ACM, 2018. – עמ' 325-340.
7. Hellerstein JM et al. ספריית האנליטיקה של MADlib: או כישורי MAD, ה-SQL //Proceedings של ה-VLDB Endowment. – 2012. – ת' 5. – מס'. 12. – עמ' 1700-1711.
8. Qin C., Rusu F. קירובים ספקולטיביים עבור אופטימיזציה של ירידה בדרגת שיפוע מבוזרת בטרה-סקאלה //הליכי הסדנה הרביעית בנושא ניתוח נתונים בענן. – ACM, 2015. – P. 1.
9. מנג X. et al. Mllib: Machine learning in apache spark //The Journal of Machine Learning Research. – 2016. – ת' 17. – מס'. 1. – עמ' 1235-1241.

מחברי המאמר: אנסטסיה ביריו, חוקר ב מחקר JetBrains, תלמיד מרכז מדעי המחשב и ניקיטה בוברוב, חוקר ב מחקר JetBrains

מקור: www.habr.com