Tuesday, May 9, 2017

Naive Bayes Classifier

Supervised Machine Learning-ийн нэг classifier алгоритмын талаар. FB Note дээрээсээ шууд хуулж тавьсан учраас фонт нь өөр болсон байна.


Bayes-ийн онол

Энэ онолыг анх Thomas Bayes бий болгосон бөгөөд нөхцөлт магадлал дээр суурилдаг. Нөхцөлт магадлал бол ямар нэгэн зүйл аль хэдийн болсон тохиолдолд дараагаар нь дахин өөр ямар нэгэн зүйл болох магадлал юм. Нөхцөлт магадлалын жишээ - Аль хэдийн iPhone утас хэрэглэдэг хүн macbook худалдаж авах магадлал. - Кино театр дотор ундаа худалдаж авч уух магадлал. - Хүйтэн ундаа авчаад дараагаар нь самар худалдаж авах магадлал. - Буйдан дээр суусны дараа хүүхэлдэйн кино үзэх магадлал.
Нөхцөлт магадлалын томъёо P(A|B) = P(B|A) * P(A) / P(B) энд P(A) бол Macbook худалдаж авах магадлал. P(B) бол iPhone худалдаж авах магадлал. P(B|A) бол Macbook худалдаж авсны дараа iPhone худалдаж авах магадлал. P(A|B) бол iPhone худалдаж авсны дараагаар дахин Macbook-тэй болох магадлал. ерөнхийлсөн тайлбар P(A) бол A таамаг үнэн байх магадлал. Өмнөх магадлал гэдэг. P(B) бол баталгааны магадлал (таамгаас үл хамаарна). P(B|A) бол өгөгдсөн таамаг үнэн байх тохиолдолд гарах баталгааны магадлал. P(A|B) бол баталгаа нь байж байхад таамгийнх нь гарах магадлал. Жишээ асуудал Нэг лабортарт “D” нэртэй өвчнийг илрүүлэх тест хийж байна гэж үзье мэдээж хариу нь муу гарсан бол “Positive” харин гайгүй гарсан бол “Negative” үр дүнг үзүүлнэ. Тухайн өвчтөн “D” нэртэй өвчнөөр яг таг өвдсөн байна гэдгийг өөрөөр хэлбэл “Negative” хариуг зөв гаргах магадлал нь 99%, эсрэгээрээ өвдөөгүй байх тохиолдолд “Positive” гэсэн зөв хариуг мөн 99% магадлалтайгаар илрүүлдэг. Нийт тест өгсөн хүмүүсийн 3% нь энэ өвчнөөр өвдсөн буюу “Positive” үр дүнг үзүүлсэн бол таны энэ өвчнөөр өвдсөн байх магадлал хэд вэ? Энэ асуудлыг нөхцөлт магадлалын томъёололд оруулан шийдэж болно. - D өвчнөөр өвдсөн хүмүүсийн магадлал буюу P(D) = 0.03 = 3% - Тухайн тест өгсөн хүн D өвчнөөр үнэхээр өвдсөн байгаа үед “Positive” хариуг гаргах магадлал P(Pos | D) = 0.99 = 99% - D өвчнөөр өвдөөгүй хүмүүсийн магадлал P(~D) = 0.97 = 97% - Тест өгсөн хүн “Positive” хариу авсан бөгөөд энэ тохиолдолд D өвчнөөр өвдөөгүй байх тохиолдлын магадлал нь P(Pos | ~D) = 0.01 = 1% Тест өгсөн хүн D өвчнөөр өвдсөн байх магадлалыг буюу P(D | Pos) -г Bayes-ийн томъёонд оруулбал P(D | Pos) = P(Pos | D) * P(D) / P(Pos) болно. Эндээс P(Pos) магадлалын утгыг тооцон олох шаардлагатай. P(Pos) = P(D, pos) + P(~D, pos) = P(pos | D) * P(D) + P(pos | ~D) * P(~D) = 0.99 * 0.03 + 0.01 * 0.97 = 0.0297 + 0.0097 = 0.0394 P(D | Pos) = P(Pos | D) * P(D) / P(Pos) = 0.99 * 0.03 / 0.0394 = 0.753807107 Тэхээр ойролцоогоор D өвчнөөр өвдөх магадлал нь 75%-тай гэсэн хариу гарахнээ. Өөр нэг жишээ Өнөөдөр миний буйдан дээр тухалж амрах дээрээс нь амарсан даруйдаа күүкэлдэйн кино тааруулж үзэх магадлал хэд вэ? A үзэгдэл - өнөөдөр South Park хүүхэлдэйн кино үзэх B үзэгдэл - өнөөдөр буйдан дээр ялхайтал амарч суух P(A|B) = ? Энэ хоёр үзэгдлүүдийг bayes-ийн томъёоны бүрэлдэхүүн хэсгүүд болгон задлая : Өнгөрсөн 2 сарын турш буюу 60-н хоногт South Park хүүхэлдэйн киног 10-н удаа үзсэн. P(A) = P(Өнөөдөр South Park күүкэлдэй үзэх магадлал) = 10 / 60 = ~0.17 Би ихэнхидээ өдөр бүр буйдан дээр амарч суух дуртай бөгөөд өнгөрсөн 2 сарын дотор 14-н удаа гэрээсээ гадуур хоноглож шоудсан. Тэгвэл өнөөдөр буйдан дээр сууж тухлах магадлал P(B) = P(Өнөөдөр буйдан дээр амрах магадлал) = (60-14) / 60 = ~0.76 South Park хүүхэлдэйн киног 10-н удаа үзсэн хэдий ч 4-ийг нь найзындаа гэрээсээ гадуур үзсэн. Тэхээр би өнгөрсөн 2 сарын дотор 46 өдрийг гэртээ буйдан дээр зурагтын удирдлага сольж өнгөрөөсөн байхнээ, мөн гэртээ South Park-ийг 6/10-н удаа үзсэн болж таарч байна. P(B|A) = P(өнгөрсөн 2 сард South Park үзэнгээ буйдан дээр амарсан магадлал) = 6/10 = 0.60 Тэхээр миний өнөөдөр буйдан дээрээ суухаар шийдэх тэгээд дээрээс нь South Park күүкэлдэйн киног тохируулж үзэх магадлалыг Bayes-ийн аргаар тооцон бодож олох бүх шаардлагатай бүрэлдэхүүн хэсгүүд бүрджээ. P(A|B) = P(B|A) * P(A) / P(B) = (0.60 * 0.17) / 0.76 = 0.13 буюу P(Өнөөдөр буйдан дээр суухаар шийдэх мөн тэгээд South Park үзэх магадлал) = 0.13 = 13% ийн магадлалтай болж таарахнээ.

Naive Bayes Classifier

Энэ бол Bayes-ийн онолыг хэрэглэдэг classifier буюу Machine Learning-ийн Supervised Learning төрлийн алгоритм юм. Энэ алгоритмаар тухайн өгөгдөл ямар нэгэн class-д хамаарагдах магадлалыг олдог. Хамгийн өндөр магадлалтай class-д энэ өгөгдөл хамаарагдана гэж үзнэ. Үүнийг өөрөөр Maximum A Posteriori (MAP) гэдэг. Таамганд зориулсан MAP : MAP(H) = max(P(H|E)) = max((P(E|H) * P(H)) / P(E)) = max(P(E|H) * P(H)) Энд P(E) бол баталгааны магадлал бөгөөд үр дүнг нормчилоход хэрэглэдэг. Утга нь өөрчлөгдөхгүй тул үүнийг хасахад нээх нөлөө байхгүй. Naive Bayes classifier алгоритмд бүх feature-үүдийг нэг нэгнээсээ хамааралгүй байна гэж үздэг. Тухайн feature-ийн байгаа болон байхгүй эсэх нь бусад feature-ийн байгаа болон байхгүй эсэхэд нөлөө үзүүлэхгүй гэсэн үг. Жишээлбэл: Хэрэв тухайн жимс нь улаан өнгөтэй бөгөөд 4 инчийн диаметртэй бол үүнийг алим гэж тодорхойлж болох юм. Энэ хоёр feature нэг нэгнээсээ хамаардаг аль эсвэл бусад өөр feature-ээс хамааралтай байлаа ч naive bayes classifier алгоритмд эдгээр шинж чанаруудыг энэ жимс бол алим юм гэдгийг тодорхойлох магадлалд тус тусдаа оролцдог гэж үздэг байна. Бодит өгөгдөлд тухайн таамгийг олон баталгаа буюу feature ашиглан шалгадаг. H - hypothesis буюу таамаг Multiple Evidences - Олон баталгаанууд P(H | Multiple Evidences) = P(E1|H) * P(E2|H) .... * P(En|H) * P(H) / P(Multiple Evidences) Naive Bayes Classifier алгоритмын жишээ 1500-н ширхэг бичлэг болон 3-н class бүхий сургалын өгөгдөл байгаа гэж үзье. Амьтны төрлийг илгэх 3-н класс : - Тоть - Нохой - Загас Таамаглагч feature-үүд нь 4-н ширхэг байна гэж үзье : - Сэлдэг - Нисдэг - Ногоон өнгөтэй - Шүд нь аюултай Эдгээр feature-үүдийг (T)True болон (F)False гэсэн хоёр ангилалын утгатайгаар ашиглаж болно. -------------------------------------------------------------------------------------- | Сэлдэг | Нисдэг | Ногоон | Шүдтэй | Амьтны төрөл | -------------------------------------------------------------------------------------- | 50 | 500/500 | 400/500 | 0 | Тоть | | 450/500 | 0 | 0 | 500/500 | Нохой | | 500/500 | 0 | 100/500 | 50/500 | Загас | -------------------------------------------------------------------------------------- Энэ хүснэгтэнд өгөгдлүүдийн давтамжийг харуулсан байна. Жишээ нь - Тотьнууд сэлэх тал дээр 50(10%) утгатай. Нийт тотьнуудын 10% нь сэлэх чадвартай, 500-н тотьноос 500 нь буюу 100% далавчтай, 500-н тотьны 400 нь ногоон өнгөтэй, 0(0%) буюу ямар ч тотинд аюултай шүд байхгүй. - Нохой гэсэн амьтны төрлөөс 500-ны 450 нь (90%) нь сэлж чадна, 0% буюу далавч байхгүй, 0% буюу ногоон өнгөтэй нохой байхгүй, 500-аас 500 буюу 100% аюултай шүдтэй. - Загас гэсэн амьтны төрлөөс 500-аас 500 буюу 100% бүгдээрээ сэлж чадна, 0% буюу ямар загасанд далавч байхгүй, 100-н ширхэг загас буюу 20% нь ногоон өнгөтэй, 500-аас 50-н ширхэг нь буюу 10% нь аюултай шүдтэй болно. Одоо эдгээр сургалтын утганууд дээр суурьлан Naive Bayes моделиор class таамаглая. Хоёр ширхэг өгөгдлийг feature-үүдтэй харвал ---------------------------------------------------------------------- | | Сэлдэг | Нисдэг | Ногоон | Шүдтэй | ---------------------------------------------------------------------- | 1. | True | False | True | False | ---------------------------------------------------------------------- | 2. | True | False | True | True | ---------------------------------------------------------------------- Эдгээр feature-үүд болон утгуудыг ашиглан class-ийг нь урьдчилан таамаглах буюу тухайн бичлэг ямар амьтны төрөлд хамаарагдах вэ өөрөөр хэлбэл нохой, тоть, загас гурвын аль нь вэ гэдгийг урьдчилан тааварлая. Naive Bayes аа санавал P(H|Multiple Evidences) = P(E1|H) * P(E2|H) * .... * P(En|H) * P(H) / P(Multiple Evidences) 1-р бичлэгийг авч үзье. Сэлдэг болон ногоон өнгө гэсэн feature-тэй байна, таамаглавал энэ бичлэг нь нохой, тоть, загас гурвын аль нэг нь байх бололцоотой. Энэ бичлэг нь нохой ангилалд байх таамгийг шалгая : P(Нохой | Сэлдэг, Ногоон) = P(Сэлдэг | Нохой) * P(Ногоон | Нохой) * P(Нохой) / P(Сэлдэг, Ногоон) = 0.9 * 0 * 0.333 / P(Сэлдэг, Ногоон) = 0 Энэ бичлэг тоть ангилалд байх таамгийг шалгая : P(Тоть | Сэлдэг, Ногоон) = P(Сэлдэг | Тоть) * P(Ногоон | Тоть) * P(Тоть) / P(Сэлдэг, Ногоон) = 0.1 * 0.80 * 0.333 / P(Сэлдэг, Ногоон) = 0.0264 / P(Сэлдэг, Ногоон) Мөн энэ бичлэг загас ангилалд байх таамгийг шалгая : P(Загас | Сэлдэг, Ногоон) = P(Сэлдэг | Загас) * P(Ногоон | Загас) * P(Загас) / P(Сэлдэг, Ногоон) = 1 * 0.2 * 0.333 / P(Сэлдэг, Ногоон) = 0.0666 / P(Сэлдэг, Ногоон) Дээрхи гурван тооцооллууд бүгд ижилхэн P(Сэлдэг, Ногоон) гэсэн ерөнхий хуваагчтай. P(Загас | Сэлдэг, Ногоон) -ны утга нь P(Тоть | Сэлдэг, Ногоон) -ны утгаас их байна. Ингээд Naive Bayes хэрэглэн энэ бичлэг нь загас гэсэн ангилалд хамаарах юм байна гэдгийг мэдэж авлаа. 2-р бичлэгийг авч үзье. True утгатай feature-үүд гэвэл сэлдэг, ногоон өнгөтэй, аюултай шүдтэй гэдгийг мэдэж болно. Таамаг нь тэхээр нохой, тоть, загас гурвын аль нэг нь байх бололцоотой. Нохой ангилалд байх таамгийг шалгая : P(Нохой | Сэлдэг, Ногоон, Шүдтэй) = P(Сэлдэг | Нохой) * P(Ногоон | Нохой) * P(Шүдтэй | Нохой) * P(Нохой) / P(Сэлдэг, Ногоон, Шүдтэй) = 0.9 * 0 * 1 *0.333 / P(Сэлдэг, Ногоон, Шүдтэй) = 0 Тоть ангилалд байх таамгийг шалгая : P(Тоть | Сэлдэг, Ногоон, Шүдтэй) = P(Сэлдэг | Тоть) * P(Ногоон | Тоть) * P(Шүдтэй | Тоть) * P(Тоть) / P(Сэлдэг, Ногоон, Шүдтэй) = 0.1 * 0.80 * 0 * 0.333 / P(Сэлдэг, Ногоон, Шүдтэй) = 0 Загас ангилалд байх таамгийг шалгая : P(Загас | Сэлдэг, Ногоон, Шүдтэй) = P(Сэлдэг | Загас) * P(Ногоон | Загас) * P(Шүдтэй | Загас) * P(Загас) / P(Сэлдэг, Ногоон, Шүдтэй) = 1 * 0.2 * 0.1 * 0.333 / P(Сэлдэг, Ногоон, Шүдтэй) = 0.00666 / P(Сэлдэг, Ногоон, Шүдтэй) Бүгд ижилхэн P(Сэлдэг, Ногоон, Шүдтэй) хуваагчтай. Ганцхан P(Загас | Сэлдэг, Ногоон, Шүдтэй) -ийнх нь утга л 0-ээс их 0.00666 гэсэн утгатай байна. Тиймээс энэ бичлэг class нь Загас гэдгийг мэдэж авлаа гэсэн үг. Эдгээр бодож олсон магадлалуудын утгууд маш бага тиймээс эдгээр утгуудыг нормчилох хэрэгтэй болдог, үүний тулд хуваагч утга ашигладаг.
Naive Bayes алгоритмын давуу талууд : - Хурдтай, тэлэх боломж сайтай. - Хоёртын болон олон класстай classification-д хэрэглэгдэх боломжтой бөгөөд GaussianNB, MultinomialNB, BernoulliNB гэх мэтийн NB алгоритмууд бий. - Тоолох үйл ажиллагаа нь олон байдаг, тун энгийн алгоритм. - Текс болон документ ангилах асуудалд маш сайн тохирдог мөн и-мэйл ангилж спам шүүдэг асуудлуур их хэрэглэгддэг. - Цөөн хэмжээний сургалтын өгөгдөл дээр хялбархаан сургах боломжтой Дутагдалтай тал : - Бүх feature-үүдийг хоорондоо хамааралгүй гэж үздэг, тийм болохоор feature хоорондын харилцан хамаарлын талаар суралцаж чадахгүй. Жишээ нь Батаа үдэшлэгрүү явах гэж байгаа гэж үзь. Үдэшлэгт зориулж хувцсаа сонгохын тулд шүүгээгээ онгичив, тэрээр цагаан өнгийн цамцанд дуртай, жеансны хувьд бор өнгөнд дуртай, гэвч цагаан цамц болон бор жеансийг нэг дор өмсөх дургүй. Naive Bayes feature тус бүрийн хувьд суралцаж чадахч эдгээр feature-үүдийн хоорондох хамаарлыг тодорхойлж чаддаггүй байна.