Nghiên c u và cài đt các thu t toán phân l p d li u v i Mapleứ ặ ậ ớ ữ ệ ớ
TR NG ĐI H C CÔNG NGH THÔNG TINƯỜ Ạ Ọ Ệ
CAO H C CÔNG NGH THÔNG TIN QUAỌ Ệ
M NGẠ
L P TRÌNH SYMBOLIC VÀ NG D NGẬ Ứ Ụ
BÀI THU HO CH:Ạ
NGHIÊN C U VÀ CÀI ĐT CÁC THU TỨ Ặ Ậ
TOÁN PHÂN L P D LI U V I MAPLEỚ Ữ Ệ Ớ
Gi ng viên:ả
PGS. TS. Đ Văn Nh nỗ ơ
H c viên th c hi n:ọ ự ệ
Hu nh Tu n Anhỳ ấ
CH1101004
Khóa 6
GV: PGS. TS. Đ Văn Nh nỗ ơ HVTH: Hu nh Tu n Anhỳ ấ
Nghiên c u và cài đt các thu t toán phân l p d li u v i Mapleứ ặ ậ ớ ữ ệ ớ
TpHCM, 02/2013
L i cám n.ờ ơ
Em xin chân thành cám n PGS. TS. Đ Văn Nh n đã t n tình h ng d n, ch b oơ ỗ ơ ậ ướ ẫ ỉ ả
chúng em trong su t th i gian h c chuyên đ này.ố ờ ọ ề
Xin chân thành cám n quý th y cô trong Tr ng Đi H c Công Ngh Thông Tin,ơ ầ ườ ạ ọ ệ
Đi H c Qu c Gia Tp.HCM đã t n tình gi ng d y, trang b cho em nh ng ki n th c quýạ ọ ố ậ ả ạ ị ữ ế ứ
báu, t o m i đi u ki n t t cho chúng em h c t p và nghiên c u.ạ ọ ề ệ ố ọ ậ ứ
Xin chân thành cám n gia đình và b n bè đã ng h , giúp đ và đng viên em trongơ ạ ủ ộ ỡ ộ
th i gian h c t p và nghiên c u.ờ ọ ậ ứ
M c dù đã c g ng hoàn thành bài lu n nh ng ch c ch n không tránh kh i thi u sót.ặ ố ắ ậ ư ắ ắ ỏ ế
Em kính mong nh n đc s thông c m và t n tình ch b o c a quý th y cô.ậ ượ ự ả ậ ỉ ả ủ ầ
H c viên th c hi nọ ự ệ
Hu nh Tu n Anhỳ ấ
TpHCM, 02/2013
GV: PGS. TS. Đ Văn Nh nỗ ơ HVTH: Hu nh Tu n Anhỳ ấ
Nghiên c u và cài đt các thu t toán phân l p d li u v i Mapleứ ặ ậ ớ ữ ệ ớ
M c L cụ ụ
GV: PGS. TS. Đ Văn Nh nỗ ơ HVTH: Hu nh Tu n Anhỳ ấ
Nghiên c u và cài đt các thu t toán phân l p d li u v i Mapleứ ặ ậ ớ ữ ệ ớ
Ch ng 1: THU T TOÁN FIND-Sươ Ậ
1. H C KHÁI NI M VÀ BÀI TOÁN C THỌ Ệ Ụ Ể
Theo Tom M.Mitchell: “Nhi u v n đ h c đòi h i các khái ni m t ng quát thu đc ề ấ ề ọ ỏ ệ ổ ượ
t các ví d hu n luy n. … V n đ t đng k t lu n v s xác đnh t ng quát nh t c a ừ ụ ấ ệ ấ ề ự ộ ế ậ ề ự ị ổ ấ ủ
m t vài khái ni m, các ví d cho tr c đc ghi nhãn có ph i là b ph n c a khái ni m ộ ệ ụ ướ ượ ả ộ ậ ủ ệ
hay không, nhi m v đó th ng đc xem nh là ệ ụ ườ ượ ư h c khái ni m.ọ ệ ”
1.1. H c khái ni mọ ệ
-Cho tr c các ví d hu n luy n. m i ví d hu n luy n cho bi t có thu c khái ướ ụ ấ ệ ỗ ụ ấ ệ ế ộ
ni m hay không? (thu c: positive; không: negative)ệ ộ
-Đa ra khái ni m t ng quát phân lo i t p hu n luy n. Khái ni m t ng quát là ư ệ ổ ạ ậ ấ ệ ệ ổ
hàm boolean đc đnh nghĩa trên t p cá th .ượ ị ậ ể
-“H c khái ni m là đa ra m t hàm boolean t t p input và putput c a các ví dọ ệ ư ộ ừ ậ ủ ụ
hu n luy n” (Tom M.Mitchell – ấ ệ Machine Learning)
Ví d :ụ
o(Input) Các ví d hu n luy n:ụ ấ ệ
T p các animal cùng thu c tính c a nó.ậ ộ ủ
o(Output) Khái ni m đc trích ra:ệ ượ
Bird
Cat
…
1.2. Bài toán c thụ ể
-(Input) T p ví d hu n luy n g m 4 cá th sau:ậ ụ ấ ệ ồ ể
oT p này nói v nh ng ngày (nh th nào đó) mà Aldo thích ch i ậ ề ữ ư ế ơ
môn th thao d i n c c a anh ta ể ướ ướ ủ (Table 2.1 – Positive and
negative training examples gor thw target concept EnjoySport, Machine
Learning – Tom M.Mitchell, 2003).
Exampl
e
Sky
AirTem
p
Humidity Wind Water Forecast EnjoySport
1 Sunny Warm Normal Strong Warm Same Positive
2 Sunny Warm High Strong Warm Same Positive
3 Rainy Cold High Strong Warm Change Negative
GV: PGS. TS. Đ Văn Nh nỗ ơ 4HVTH: Hu nh Tu n Anhỳ ấ
Nghiên c u và cài đt các thu t toán phân l p d li u v i Mapleứ ặ ậ ớ ữ ệ ớ
4 Sunny Warm High Strong Cool Change Positive
B ng 1.1 – ảCác ví d hu n luy n thu c và không thu c khái ni m đíchụ ấ ệ ộ ộ ệ EnjoySport
-(Output) Khái ni m đc h c: “ệ ượ ọ EnjoySport”
1.3. Gi thi tả ế
-Cũng đc hi u là khái ni m. Là h i c a các ràng bu c trên thu c tính c a cá ượ ể ệ ộ ủ ộ ộ ủ
th .ể
-X là cá th , và X tho mãn t t c các ràng bu c trên gi thi t h thì h [hân lo i ể ả ấ ả ộ ả ế ạ
X là positive (h(X) = 1)
-Ví d : Gi thi t là Aldo thích môn th thao d i n c vào nag “cold days ụ ả ế ể ướ ướ ỳ
with high humidity”, gi thi t đc ghi là:ả ế ượ
o<?, Clod, High, ?, ?, ?>
-Gi thi t t ng quát nh t:ả ế ổ ấ
o<?, ?, ?, ?, ?, ?>
-Gi thi t c th nh t:ả ế ụ ể ấ
o<Ø, Ø, Ø, Ø, Ø, Ø>
1.4. Ký hi uệ
-T p cá th (set of instances)ậ ể
oT p đc dùng đ trích khái ni m t đóậ ượ ể ệ ừ
oKý hi u: Xệ
oVí d trên: t p cá th = t p ngày, m i ngày có 6 thu c tính.ụ ậ ể ậ ỗ ộ
-Khái ni m đích (target concep)ệ
oKhái ni m (hàm) đc h c.ệ ượ ọ
oKý hi u: cệ
c: X {0,1}
Ví d trên: c(X) = 1 n u EnjoySport = Yesụ ế
Ví d trên: c(X) = 0 n u EnjoySport = Noụ ế
-Các ví d hu n luy n, g m có:ụ ấ ệ ồ
oM t cá th thu c X.ộ ể ộ
oKhái ni m đích c(X).ệ
Vi t là: <X, x(X)>ế
GV: PGS. TS. Đ Văn Nh nỗ ơ 5HVTH: Hu nh Tu n Anhỳ ấ