סיווג בייסיאני נאיבי

[שמאל|ממוזער|300px|דוגמה למודל בייסיאני נאיבי המיוצג כ[רשת בייסיאנית]]
**סיווג בייסיאני נאיבי** (באנגלית: **Naive Bayes classifier**) הוא שם כולל לאוסף שיטות סיווג בתחום של למידת מכונה, המבוססות על חוק בייס ועל הנחת אי-תלות בין תכונות האובייקטים המסווגים. הנחת אי-התלות לרוב אינה מייצגת נכונה את המידע, מאחר שלרוב יש תלות בין האובייקטים אשר מיועדים לסיווג, לפיכך שיטות מסוג זה מכונות 'תמימות' או 'נאיביות'.

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

## המודל הכללי
המשימה היא לסווג אובייקט לאחת מ-k קטגוריות כאשר האובייקט מאופיין על ידי וקטור התכונות \mathbf{x} = (x_1, \dots, x_n). ידועות ההסתברויות האפריוריות של הקטגוריות p(C_k) לכל k, וגם ידועות ההסתברויות המותנות של כל תכונה בנפרד בהינתן הקטגוריה. הסתברויות אלה ניתנות להערכה מתוך מדגם מייצג. בנוסף מניחים את ההנחה ה"נאיבית" שהתכונות אינן תלויות זו בזו בהינתן הקטגוריה.

כדי למצוא את הקטגוריה הסבירה ביותר משווים את ההסתברויות המותנות p(C_k|x) ובוחרים את C_k שמוביל להסתברות המותנית המקסימלית. לפי חוק בייס:


p(C_k|x) = \frac{p(C_k)\ p(x|C_k)}{p(x)}


המכנה לא תלוי ב-k, ולכן אם רק מחפשים את הקטגוריה הסבירה ביותר, כלומר למצוא את הקטגוריהC_k שעבורה p(C_k|x) מקסימלי, מספיק להשוות את המונים עבור ערכים שונים של k. בשל תכונה של ההסתברות המותנית, המונה שווה לp(C_k, x_1, \dots, x_n). לפי כלל השרשרת של הסתברות מותנית



\begin{align}
p(C_k, x_1, \dots, x_n) & = p(x_1, \dots, x_n, C_k) \\
 & = p(x_1 \mid x_2, \dots, x_n, C_k) p(x_2, \dots, x_n, C_k) \\
 & = p(x_1 \mid x_2, \dots, x_n, C_k) p(x_2 \mid x_3, \dots, x_n, C_k) p(x_3, \dots, x_n, C_k) \\
 & = \dots \\
 & = p(x_1 \mid x_2, \dots, x_n, C_k) p(x_2 \mid x_3, \dots, x_n, C_k) \dots p(x_{n-1} \mid x_n, C_k) p(x_n \mid C_k) p(C_k) \\
\end{align}



בשל ההנחה הנאיבית, הביטוי האחרון שווה ל


\begin{align}
 p(x_1 | C_k) \ p(x_2 | C_k) \ \cdots \ p(x_n | C_k) \ p(C_k) \ = p(C_k) \prod_{i=1}^n p(x_i \mid C_k)
\end{align}



כל המרכיבים של הביטוי האחרון כאמור נתונים ולכן ניתן להציבם, להשוות את התוצאות ל-k השונים, ולבחור את הקטגוריה C_k שנותנת תוצאה מקסימלית.

## דוגמה
### ההנחה ה"נאיבית" של סיווג בייסיאני נאיבי
נניח שברצוננו לסווג נבדקים לקטגורית "חולים בשפעת" או לקטגורית "לא חולים בשפעת" בהתבסס על התכונות "כאב-ראש", "משתעל", ו-"חום" הנתונות לכל נבדק. במקרה זה, התכונות הללו הן בעלות ערכים אפשריים של "כן" או "לא" (מה שהופך את הבעיה לבעיית סיווג מסוג ברנולי). נניח שכתוצאה מידע מוקדם ידוע לנו שההסתברות להיות חולה בשפעת היא 1/40 = (שפעת)p (כלומר אדם אחד מכל 40 באוכלוסייה חולה בשפעת) וההסתברות לא להיות חולה בשפעת היא לכן 39/40 = (לא-שפעת)p.

באוכלוסייה הכללית הגיוני שיש תלות בין היות בן אדם משתעל והיות אדם עם חום גבוה. כלומר העובדה שיש לאדם חום מעלה את ההסתברות שהוא גם משתעל. כלומר
 (משתעל)p p(F|A, B, \overline{C}) ו p(\overline{F}|A, B, \overline{C}).

שני ביטויים אלה שווים לפי חוק בייס לביטויים הבאים:

p(F|A, B, \overline{C})=\frac{p(A, B, \overline{C}|F) p(F)}{p(A, B, \overline{C})}

p(\overline{F}|A, B, \overline{C})=\frac{p(A, B, \overline{C}|\overline{F}) p(\overline{F})}{p(A, B, \overline{C})}


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


= p(A, B, \overline{C}|F)\ p(F)

= p(A, B, \overline{C}, F)

= p(A|B, \overline{C}, F)\ p(B, \overline{C}, F)

= p(A|B, \overline{C}, F)\ p(B|\overline{C}, F)\ p(\overline{C}, F)

= p(A|B, \overline{C}, F)\ p(B|\overline{C}, F)\ p(\overline{C}|F)\ P(F)

= p(A|F)\ p(B|F)\ p(\overline{C}|F)\ p(F)

= 1/2 \times 3/4 \times (1-2/3) \times 1/40 = 0.003125

המספרים המוצבים בסוף באים מטבלה 1. השוויון שלפניהם מתקיים בגלל ההנחה "הנאיבית" שאם נתונה הקטגוריה (F במקרה זה) אזי ההסתברות של תכונה לא תלויה בתכונות האחרות. כך למשל אם ידוע F אז A לא תלוי עוד ב B וב-C ולכן p(A|B, \overline{C}, F) = p(A|F).

באותה דרך אפשר לחשב את המונה השני:

= ... = p(A|\overline{F})\ p(B|\overline{F})\ p(\overline{C}|\overline{F})\ p(\overline{F})

p(A, B, \overline{C}|\overline{F})\ p(\overline{F})

= 7/78 \times 1/30 \times (1-1/6) \times 39/40 = 0.002431

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

## סיווג בייסיאני נאיבי גאוסיאני
בדוגמה שלמעלה (חיזוי שפעת על סמך תכונות) כל התכונות היו בדידות כלומר בעלות ערכים מתוך קבוצה סופית - למשל לתכונה "משתעל" היו שני ערכים אפשריים - "כן" או "לא". במצב כזה ניתן להעריך את ההסתברויות המותנות, כמו אלה המופיעות בטבלה 1, על ידי ספירת בעלי כל ערך של התכונה באוכלוסייה הנדגמת וחלוקה בגודל המדגם. דרך זאת אינה אפשריות עוד כאשר התכונות הן רציפות - למשל גובה. לתכונות כאלה יש אינסוף ערכים אפשריים ואי אפשר למלא טבלה כמו טבלה 1. במקום זאת, מעריכים לכל תכונה פונקציית התפלגות ומעריכים את הפרמטרים של הפונקציה בעזרת מדגם. למשל, בדרך כלל ללא מידע נוסף על התכונה הרציפה, מעריכים התפלגות נורמלית עבור התכונה ומעריכים את הממוצע \mu_k ואת השונות (חסרת ההטיה) \sigma^2_k של המדגם עבור כל קטגוריה C_k אפשרית (קבוצת הקטגוריות היא בדידה בבעיות סיווג).

פונקציית התפלגות נורמלית היא בצורת פעמון גאוס וצפיפות ההסתברות כאשר לתכונה x יש את הערך v אם מניחים קטגוריה C_k היא:



p(x=v \mid C_k)=\frac{1}{\sqrt{2\pi\sigma^2_k}}\,e^{ -\frac{(v-\mu_k)^2}{2\sigma^2_k} }



פונקציה זאת מחליפה את טבלת ההסתברויות המותנות (דוגמת טבלה 1). ראו דוגמה להלן.

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

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

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

כדי לקצר את הנוסחאות הבאות נשתמש בשמות המשתנים הבאים: גבר=M, אישה=F, גובה=H, משקל=W, כף-רגל=L.
נניח שידוע שההסתברויות האפריוריות של להיות גבר או אישה הם שווים, כלומר: p(M)=p(F)=0.5.
ההסתברות שהנבדק הוא גבר היא:
 \frac{p(M)\ p(H=1.83|M)\ p(W=59|M)\ p(L=20.3|M)}{p(H=1.83, W=59, L=20.3)}
ההסתברות שהנבדק היא אישה היא:
 \frac{p(F)\ p(H=1.83|F)\ p(W=59|F)\ p(L=20.3|F)}{p(H=1.83, W=59, L=20.3)}

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

p(H=1.83|M) = \frac{1}{\sqrt{2\pi \sigma^2}}\exp\left(\frac{-(1.83-\mu)^2}{2\sigma^2}\right) \approx 4.951


כש- \sigma^2 = 3.225\ 10^-3 ו- \mu = 1.7825 (מספרים הלקוחים מטבלה 3).

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

p(W=59|M) = 1.357\ 10^-5

p(L=20.3|M) = 4.962\ 10^-4


ולכן המונה הראשון (עבור גבר) שווה

0.5 \times 4.951 \times 1.357\ 10^-5 \times 4.962\ 10^-4 = 1.667\ 10^-8 


עבור האישה:

p(H=1.83|F) = 0.721

p(W=59|F) = 0.037

p(L=20.3|F) = 0.1135

0.5 \times 0.721 \times 0.037 \times 0.1135 = 5.135\ 10^-3 


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

## סיווג מסמכים
סיווג בייסיאני נאיבי הניב תוצאות יפות בתחום של סיווג טקסט לקטגוריות - למשל סיווג דואר אלקטרוני ל"ספאם" או "לא-ספאם", על סמך המילים הכלולות בטקסט. כל מסמך מאופיין על ידי אוסף המילים שבו. מכינים מראש את טבלת ההסתברויות המותנות (בדומה לטבלה 1): לכל מילה w_i וקטגוריה C_k מעריכים בעזרת מדגם את p(w_i | C_k)\, - ההסתברות המותנה שהמילה w_i נמצאת במסמך בהנחה שהמסמך הוא מקטגוריה C_k. כלומר המילה היא התכונה והערכים שלה הם "נמצאת במסמך" ו-"לא נמצאת במסמך". ישנן גם גישות אחרות למידול הבעיה, כמו בהן התכונה היא המקום במסמך והערך הוא המילה, או בהן הערך הוא מספר ההופעות של המילה, או שקלול של מספר זה. ההסתברות לראות את כל המילים במסמך D בהנחה שמדובר במסמך מקטגוריה C_k הוא

: p(D|C_k)=\prod_i p(w_i | C_k)

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

: p(C_k|D)=\frac{p(C_k)\,p(D\mid C_k)}{p(D)} = \frac{p(C_k)\,\prod_i p(w_i | C_k)}{p(D)}

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

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

## הערות שוליים

קטגוריה:למידת מכונה
קטגוריה:מדעי המחשב
קטגוריה:סטטיסטיקה בייסיאנית