שאלה | אלגוריתם למציאת שאלות

שלום למומחים,

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

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

ובהתאם לכך שתי שאלות:
1. האם יש אלגוריתם שיודע לרוץ על טבלה/טבלאות ולמצוא את כל הקשרים הקיימים בין העמודות השונות?
2. במידה וכן, אילו כלים מוכרים עושים שימוש באותו אלגוריתם?

ישי, שלום

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

זוהי בדיוק הנקודה! 

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

הכנתי מצגת בענין הזה, והפתרון שלי: GT alternative to statistics


-אדית

הי ישי,

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

כלים שמיישמים אלגוריתמים מסוג זה: Analysis Servises של SQL Server 2005 (או 2008). תוכנה בשם wizrule (חפש בגוגל, נראה לי שניתן להוריד גרסת התנסות).

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

ביי,
שחר

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

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

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

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

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

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

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


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

ישי, שלום

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

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

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


- אדית

users.actcom.co.il/~edith#GT

ישי, שלום

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


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

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

- אדית

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

ישי, שלום

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

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

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

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

- אדית

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

ישי, שלום

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

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

אם יש לך שיטה אחרת, יהיה מענין להוסיף אותה להתיחסות.

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

- אדית