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

סיווג בייסיאני נאיבי (באנגלית: 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 מספיק להשוות את המונים. בשל תכונה של ההסתברות המותנית, המונה שווה ל$p(C_{k},x_{1},\dots ,x_{n})$. לפי כלל השרשרת של הסתברות מותנית

${\begin{aligned}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{aligned}}$

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

${\begin{aligned}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{aligned}}$

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

דוגמה

ההנחה ה"נאיבית" של סיווג בייסיאני נאיבי

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

1/40 = (שפעת)p	39/40 = (לא-שפעת)p
1/2 = (שפעת|כאב-ראש)p	7/78 = (לא-שפעת|כאב-ראש)p
2/3 = (שפעת|משתעל)p	1/6 = (לא-שפעת|משתעל)p
3/4 = (שפעת|חום)p	1/30 = (לא-שפעת|חום)p

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

(משתעל)p < (חום|משתעל)p

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

(שפעת|משתעל)p = (שפעת, חום|משתעל)p

כאשר (שפעת|משתעל)p היא כאמור ההסתברות שאדם משתעל אם כבר ידוע שיש לו שפעת, ו (שפעת, חום|משתעל)p היא ההסתברות שאדם משתעל אם כבר ידוע שיש לו שפעת וגם חום.

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

הסתברות אפריורית ופוסטיריורית

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

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

מציאת הסיווג הסביר ביותר

נניח שמגיע נבדק עם כאב-ראש וחום אך ללא שיעול ואנחנו רוצים להשוות את ההסתברות שהוא חולה שפעת לעומת ההסתברות שאינו חולה שפעת ולבחור באפשרות עם ההסתברות המקסימלית. כדי לקצר את הנוסחאות נשתמש בשמות המשתנים הבאים: שפעת=F, לא-שפעת=F, כאב-ראש=A, חום=B, לא-משתעל=C. אנחנו מעוניינים למצוא את המקסימלי מבין $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(A,B,{\overline {C}}|F)\ p(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 (שפעת) גדולה מההסתברות לF (לא שפעת) בהתחשב בתכונות הנבדק.

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

בדוגמה שלמעלה (חיזוי שפעת על סמך תכונות) כל התכונות היו בדידות כלומר בעלות ערכים מתוך קבוצה סופית - למשל לתכונה "משתעל" היו שני ערכים אפשריים - "כן" או "לא". במצב כזה ניתן להעריך את ההסתברויות המותנות, כמו אלה המופיעות בטבלה 1, על ידי ספירת בעלי כל ערך של התכונה באוכלוסייה הנדגמת וחלוקה בגודל המדגם. דרך זאת אינה אפשריות עוד כאשר התכונות הן רציפות - למשל גובה. לתכונות כאלה יש אינסוף ערכים אפשריים ואי אפשר למלא טבלה כמו טבלה 1. במקום זאת, מעריכים לכל תכונה פונקציית התפלגות ומעריכים את הפרמטרים של הפונקציה בעזרת מדגם. למשל, בדרך כלל ללא מידע נוסף על התכונה הרציפה, מעריכים התפלגות נורמלית עבור התכונה ומעריכים את הממוצע $\mu _{k}$ ואת השונות (חסרת ההטיה) $\sigma _{k}^{2}$ של המדגם עבור כל קטגוריה $C_{k}$ אפשרית (קבוצת הקטגוריות היא בדידה בבעיות סיווג).

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

$p(x=v\mid C_{k})={\frac {1}{\sqrt {2\pi \sigma _{k}^{2}}}}\,e^{-{\frac {(v-\mu _{k})^{2}}{2\sigma _{k}^{2}}}}$

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

דוגמה

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

טבלה 2

מין	גובה (במטרים)	משקל (בק"ג)	כף רגל (בס"מ)
גבר	1.83	81.65	30.5
גבר	1.80	86.18	28
גבר	1.70	77.11	30.5
גבר	1.80	74.84	25.4
אישה	1.52	45.36	15.24
אישה	1.68	68.04	20.3
אישה	1.65	58.97	17.8
אישה	1.75	68.04	22.9

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

טבלה 3

מין	ממוצע (גובה)	שונות (גובה)	ממוצע (משקל)	שונות (משקל)	ממוצע (כף רגל)	שונות (כף רגל)
גבר	1.7825	10-33.225	79.945	25.29	28.6	5.94
אישה	1.65	10-39.266	60.10	115	19.1	10.82

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

טבלה 4

מין	גובה (במטרים)	משקל (בק"ג)	כף רגל (בס"מ)
?	1.83	59	20.3

כדי לקצר את הנוסחאות הבאות נשתמש בשמות המשתנים הבאים: גבר=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$ מעריכים בעזרת מדגם את $p(w_{i}|C)\,$ - ההסתברות המותנה שהמילה $w_{i}$ נמצאת במסמך בהנחה שהמסמך הוא מקטגוריה $C$. כלומר המילה היא התכונה והערכים שלה הם "נמצאת במסמך" ו-"לא נמצאת במסמך". ישנן גם גישות אחרות למידול הבעיה, כמו בהן התכונה היא המקום במסמך והערך הוא המילה, או בהן הערך הוא מספר ההופעות של המילה, או שקלול של מספר זה. ההסתברות לראות את כל המילים במסמך D בהנחה שמדובר במסמך מקטגוריה $C$ הוא

$p(D|C)=\prod _{i}p(w_{i}|C)$

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

$={\frac {p(C)\,p(D\mid C)}{p(D)}}$

$p(C|D)$

$={\frac {p(C)\,\prod _{i}p(w_{i}|C)}{p(D)}}$

ערך המכנה לא תלוי בקטגוריה ולכן כדי למצוא את הקטגוריה הסבירה ביותר מספיק להשוות את המונים, הניתנים לחישוב כיוון שאת ערכי $p(w_{i}|C)$ ו$p(C)$ ניתן כאמור לאמוד מתוך מדגם של מסמכים נתונים.

קישורים חיצוניים

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