הדרכה לניתוח מעטפות נתונים

• פברואר 24, 2014
• וסיליס ווריניוטיס
• . 3 תגובות

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

עדכון: מסגרת הלמידה על מכונה של Datumbox היא כעת קוד פתוח וחינמית ל- להורדה. עיין בחבילה com.datumbox.framework.algorithms.dea כדי לראות את היישום של ניתוח מעטפות נתונים ב- Java.

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

מדוע ניתוח מעטפות נתונים מעניין?

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

התיאור וההנחות של ניתוח מעטפת נתונים

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

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

הרעיון הגאוני שמאחורי DEA

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

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

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

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

בוא נראה דוגמא

בוא נראה דוגמא בה נוכל להשתמש ב- DEA.

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

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

הגיע הזמן במתמטיקה!

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

יחס היעילות של רשומה i מסוימת עם כניסת x ויציאת y (שניהם וקטורי תכונה עם ערכים חיוביים) מוערך באמצעות הנוסחה הבאה:

כאשר u ו- v הם המשקלים של כל פלט וקלט של הרשומה, s הוא מספר מאפייני הפלט ו- m הוא מספר מאפייני הקלט.

ניתן למצוא את הבעיה במציאת המשקולות הטובות ביותר / האידיאליות עבור רשומה מסוימת i:

שוב האמור לעיל הוא רק הדרך המתמטית למצוא את המשקולות u ו- v שממקסמים את היעילות של הרשומה i, ובלבד שהמשקלים הללו לא יעשו את כל הרשומות האחרות ליעילות יותר מ- 100%.

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

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

ratio_scores = [];
for every record i {
    i_ratio = get_maximum_effectiveness();
    ratio_scores[i] = i_ratio;
}

מגבלות של ניתוח מעטפות נתונים

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

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

בעיה נוספת שעומדת בפני DEA היא שהיא לא עובדת טוב עם נתונים ממדיים גבוהים. כדי להשתמש ב- DEA מספר הממדים d = m + s חייב להיות נמוך משמעותית ממספר התצפיות. הפעלת DEA כאשר d קרוב מאוד או גדול מ- n אינה מספקת תוצאות שימושיות מכיוון שסביר להניח שכל הרשומות יימצאו אופטימליות. שים לב שכשאתה מוסיף משתנה פלט (ממד) חדש, כל הרשומות עם הערך המרבי בממד זה יימצאו אופטימליות.

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

במאמר הבא, אני אראה לך כיצד לפתח יישום של ניתוח מעטפות נתונים ב- JAVA ואנחנו נשתמש בשיטה כדי להעריך את הפופולריות של דפי אינטרנט ומאמרים ברשתות המדיה החברתית.

אם אתם אוהבים את המאמר, הקדישו לשתף אותו בטוויטר או בפייסבוק. 🙂