מהו עץ החלטות?

מהו עץ החלטות?

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

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

פורמט של עץ החלטות

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

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

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

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

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

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

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

sum(y – חיזוי)^2

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

לגבי פונקציית העלות לסיווג, הפונקציה היא כדלקמן:

G = sum(pk * (1 – pk))

זהו ציון ג'יני, והוא מדידה של האפקטיביות של פיצול, על סמך כמה מקרים של מחלקות שונות יש בקבוצות הנובעות מהפיצול. במילים אחרות, הוא מכמת עד כמה הקבוצות מעורבות לאחר הפיצול. פיצול אופטימלי הוא כאשר כל הקבוצות הנובעות מהפיצול מורכבות רק מתשומות ממחלקה אחת. אם נוצר פיצול אופטימלי, הערך "pk" יהיה 0 או 1 ו-G יהיה שווה לאפס. אולי תוכל לנחש שהפיצול במקרה הגרוע ביותר הוא כזה שבו יש ייצוג של 50-50 של המחלקות בפיצול, במקרה של סיווג בינארי. במקרה זה, הערך "pk" יהיה 0.5 ו-G יהיה גם 0.5.

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

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

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

שיקולים לשימוש בעצי החלטה

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

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