Bài giảng Khai mở dữ liệu - Phương pháp học Bayes - Đỗ Thanh Nghị

Khoa Công Nghệ Thông Tin Trường Đại Học Cần Thơ Đỗ Thanh Nghị dtnghi@cit.ctu.edu.vn Cần Thơ 02-12-2008 Phương pháp học Bayes Bayesian classification Nội dung  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  Kết luận và hướng phát triển 2 Nội dung  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  Kết luận và hướng phát triển 3 Bayesian classification  lớp các giải thuật học  dựa trên theorem Bayes  mạng Bayes và naive Bayes  kết quả sinh ra có thể dịch được  giải quyết các vấn đề về phân loại, gom nhóm, etc.  được ứng dụng thành công : phân tích dữ liệu, phân loại text, spam, etc. 4  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển Kỹ thuật DM thành công trong ứng dụng thực (2004) 5  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển Nội dung  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  Kết luận và hướng phát triển 6 Giải thuật naive Bayes  ngây thơ  các thuộc tính (biến) có độ quan trọng như nhau  các thuộc tính (biến) độc lập thống kê  nhận xét  giả thiết các thuộc tính độc lập không bao giờ đúng  nhưng trong thực tế, naive Bayes cho kết quả khá tốt  7  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển Dữ liệu weather, dựa trên các thuộc tính (Outlook, Temp, Humidity, Windy), quyết định (play/no) 8  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển NoTrueHighMildRainy YesFalseNormalHotOvercast YesTrueHighMildOvercast YesTrueNormalMildSunny YesFalseNormalMildRainy YesFalseNormalCoolSunny NoFalseHighMildSunny YesTrueNormalCoolOvercast NoTrueNormalCoolRainy YesFalseNormalCoolRainy YesFalseHighMildRainy YesFalseHighHot Overcast NoTrueHigh Hot Sunny NoFalseHighHotSunny PlayWindyHumidityTempOutlook Dữ liệu weather, dựa trên các thuộc tính (Outlook, Temp, Humidity, Windy), quyết định (play/no) NoTrueHighMildRainy YesFalseNormalHotOvercast YesTrueHighMildOvercast YesTrueNormalMildSunny YesFalseNormalMildRainy YesFalseNormalCoolSunny NoFalseHighMildSunny YesTrueNormalCoolOvercast NoTrueNormalCoolRainy YesFalseNormalCoolRainy YesFalseHighMildRainy YesFalseHighHot Overcast NoTrueHigh Hot Sunny NoFalseHighHotSunny PlayWindyHumidityTempOutlook 9  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển 5/14 5 No 9/14 9 Yes Play 3/5 2/5 3 2 No 3/9 6/9 3 6 Yes True False True False Windy 1/5 4/5 1 4 NoYesNoYesNoYes 6/9 3/9 6 3 Normal High Normal High Humidity 1/5 2/5 2/5 1 2 2 3/9 4/9 2/9 3 4 2 Cool2/53/9Rainy Mild Hot Cool Mild Hot Temperature 0/54/9Overcast 3/52/9Sunny 23Rainy 04Overcast 32Sunny Outlook Dữ liệu weather, dựa trên các thuộc tính (Outlook, Temp, Humidity, Windy), quyết định (play/no) 5/14 5 No 9/14 9 Yes Play 3/5 2/5 3 2 No 3/9 6/9 3 6 Yes True False True False Windy 1/5 4/5 1 4 NoYesNoYesNoYes 6/9 3/9 6 3 Normal High Normal High Humidity 1/5 2/5 2/5 1 2 2 3/9 4/9 2/9 3 4 2 Cool2/53/9Rainy Mild Hot Cool Mild Hot Temperature 0/54/9Overcast 3/52/9Sunny 23Rainy 04Overcast 32Sunny Outlook 10  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển ?TrueHighCoolSunny PlayWindyHumidityTemp.Outlook  quyết định (play=yes/no) Likelihood(yes) = 2/9 x 3/9 x 3/9 x 3/9 x 9/14 = 0.0053 Likelihood(no) = 3/5 x 1/5 x 4/5 x 3/5 x 5/14 = 0.0206 Xác suất : P(yes) = 0.0053 / (0.0053 + 0.0206) = 0.205 P(no) = 0.0206 / (0.0053 + 0.0206) = 0.795 Luật Bayes 11  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  Probability of event H given evidence E :  A priori probability of H : Pr[H]  Probability of event before evidence is seen  A posteriori probability of H : Pr[H | E]  Probability of event after evidence is seen ]Pr[ ]Pr[]|Pr[ ]|Pr[ E HHE EH  Luật Bayes 12  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  học phân lớp khi có dữ liệu đến  Evidence E = dữ liệu  Event H = giá trị lớp của dữ liệu  naïve : ]Pr[ ]Pr[]|Pr[]|Pr[]|Pr[ ]|Pr[ 21 E HHEHEHE EH n   Luật Bayes 13  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển ?TrueHighCoolSunny PlayWindyHumidityTemp.Outlook Evidence E xác suất của lớp “yes” ]|Pr[]|Pr[ yesSunnyOutlookEyes  ]|Pr[ yesCooleTemperatur  ]|Pr[ yesHighHumidity  ]|Pr[ yesTrueWindy  ]Pr[ ]Pr[ E yes  ]Pr[ 14 9 9 3 9 3 9 3 9 2 E   Xác suất = 0 14  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  giá trị của thuộc tính không xuất hiện trong tất cả các lớp (“Humidity = high” của lớp “yes”)  Probability will be zero!  A posteriori probability will also be zero!  sử dụng Laplace estimator  xác suất không bao giờ có giá trị 0 0]|Pr[ Eyes 0]|Pr[  yesHighHumidity Laplace estimator 15  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  ví dụ : thuộc tính outlook cho lớp yes  trọng số có thể không bằng nhau, nhưng tổng phải là 1     9 3/2     9 3/4     9 3/3 Sunny Overcast Rainy     9 2 1p     9 4 2p     9 3 3p Sunny Overcast Rainy Giá trị thuộc tính nhiễu 16  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  học : bỏ qua dữ liệu nhiễu  phân lớp : bỏ qua các thuộc tính nhiễu  ví dụ : ?TrueHighCool? PlayWindyHumidityTemp.Outlook Likelihood(yes) = 3/9  3/9  3/9  9/14 = 0.0238 Likelihood(no) = 1/5  4/5  3/5  5/14 = 0.0343 P(yes) = 0.0238 / (0.0238 + 0.0343) = 41 P(no) = 0.0343 / (0.0238 + 0.0343) = 59 Dữ liệu liên tục 17  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  giả sử các thuộc tính có phân phối Gaussian  hàm mật độ xác suất được tính như sau  mean   standard deviation   hàm mật độ xác suất f(x)    n i ix n 1 1       n i ix n 1 22 )( 1 1  2 2 2 )( 2 1 )(       x exf Karl Gauss, 1777-1855 great German mathematician Dữ liệu liên tục 18  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  ví dụ : 0340.0 2.62 1 )|66( 2 2 2.62 )7366(     eyesetemperaturf  Dữ liệu liên tục 19  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển  phân lớp ?true9066Sunny PlayWindyHumidityTemp.Outlook Likelihood(yes) = 2/9  0.0340  0.0221  3/9  9/14 = 0.000036 Likelihood(no) = 3/5  0.0291  0.0380  3/5  5/14 = 0.000136 P(yes) = 0.000036 / (0.000036 + 0. 000136) = 20.9 P(no) = 0.000136 / (0.000036 + 0. 000136) = 79.1 Nội dung  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  Kết luận và hướng phát triển 20 Kết luận  naïve Bayes  cho kết quả tốt trong thực tế mặc dù chịu những giả thiết về tính độc lập thống kê của các thuôc tính  phân lớp không yêu cầu phải ước lượng một cách chính xác xác suất  dễ cài đặt, học nhanh, kết quả dễ hiểu  sử dụng trong phân loại text, spam, etc  tuy nhiên khi dữ liệu có nhiều thuộc tính dư thừa thì naïve Bayes không còn hiệu quả  dữ liệu liên tục có thể không tuân theo phân phối chuẩn (=> kernel density estimators) 21  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển Hướng phát triển  naïve Bayes  chọn thuộc tính con từ các thuộc tính ban đầu  chỉ sử dụng các thuộc tính con để học phân lớp  mạng Bayes : mối liên quan giữa các thuộc tính  tìm kiếm thông tin (ranking) 22  Giới thiệu về Bayesian classification  Giải thuật học của naive Bayes  kết luận và hướng phát triển