Thuật toán và giải thuật - Hoàng Kiếm Part 13

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

83
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mở đầu về máy quang học thuật ngữ "học" theo nghĩa thông thường là tiếp thu tri thức để biêt cách vận dụng. Ở ngoài đời quá trình học diễn ra duois nhiều hình thức khác nhau như học thuộc lòng, học theo kinh nghiệm, học theo kiểu nghe nhìn

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 13

Dĩ nhiên là trong các frame trên còn r t nhi u thu c tính hóa h c khác. ây chúng tôi ch trình bày sơ lư c v m t ý tư ng b n c có cơ s b t u. Ý tư ng này ã ư c m t s sinh viên năm 4 c a khoa Công Ngh Thông Tin i H c Khoa H c T Nhiên TP. H Chí Minh cài t thành công. Chương trình ch y t t trong ph m vi các ph n ng trong sách giáo khoa l p 10, 11 và 12. 85 Sưu t m b i: www.daihoc.com.vn
Chương 3 M UV QUAN MÁY H C I. TH NÀO LÀ MÁY H C ? II. H C B NG CÁCH XÂY D NG CÂY NH DANH II.1. âm ch i II.2. Phương án ch n thu c tính phân ho ch II.2.1. Quinlan II.2.2. o h n lo n II.3. Phát sinh t p lu t II.4. T i ưu t p lu t II.4.1. Lo i b m nh th a II.4.2. Xây d ng m nh m c nh I. TH NÀO LÀ MÁY H C ? Thu t ng "h c" theo nghĩa thông thư ng là ti p thu tri th c bi t cách v n d ng. ngoài i, quá trì h c di n ra dư i nhi u hình th c khác nhau như h c thu c lòng (h c v t), h c theo kinh nghi m (h c d a theo trư ng h p), h c theo ki u nghe nhìn,... Trên máy tính cũng có nhi u thu t toán h c khác nhau. Tuy nhiên, trong ph m vi c a giáo trình này, chúng ta ch kh o sát phương pháp h c d a theo trư ng h p. Theo phương pháp này, h th ng s ư c cung c p m t s các trư ng h p "m u", d a trên t p m u này, h th ng s ti n hành phân tích và rút ra các quy lu t (bi u di n b ng lu t sinh). Sau ó, h th ng s d a trên các lu t này " ánh giá" các trư ng h p khác (thư ng không gi ng như các trư ng h p "m u"). Ngay c ch v i ki u h c này, chúng ta cũng ã có nhi u thu t toán h c khác nhau. M t l n n a, v i m c ích gi i thi u, chúng ta ch kh o sát m t trư ng h p ơn gi n. Có th khái quát quá trình h c theo trư ng h p dư i d ng hình th c như sau : D li u cung c p cho h th ng là m t ánh x f trong ó ng m t trư ng h p p trong t p h p P v i m t "l p" r trong t p R. f : P | R pr Tuy nhiên, t p P thư ng nh (và h u h n) so v i t p t t c các trư ng h p c n quan tâm P’ (P  P’). M c tiêu c a chúng ta là xây d ng ánh x f ’ sao cho có th ng 86 Sưu t m b i: www.daihoc.com.vn
m i trư ng h p p’ trong t p P’ v i m t "l p" r trong t p R. Hơn n a, f ’ ph i b o toàn f, nghĩa là : V i m i p  P thì f(p)  f ’(p) Hình 3.1 : H c theo trư ng h p là tìm cách xây d ng ánh x f’ d a theo ánh x f. f ư c g i là t p m u. Phương pháp h c theo trư ng h p là m t phương pháp ph bi n trong c nghiên c u khoa h c và mê tín d oan. C hai u d a trên các d li u quan sát, th ng kê t ó rút ra các quy lu t. Tuy nhiên, khác v i khoa h c, mê tín d oan thư ng d a trên t p m u không c trưng, c c b , thi u cơ s khoa h c. II. H C B NG CÁCH XÂY D NG CÂY NH DANH Phát bi u hình th c có th khó hình dung. c th h n, ta hãy cùng nhau quan sát m t ví d c . Nhi m v c a chúng ta trong ví d này là xây d ng các quy lu t có th k t lu n m t ngư i như th nào khi i t m bi n thì b cháy n ng. Ta g i tính ch t cháy n ng hay không cháy n ng là thu c tính quan tâm (thu c tính m c tiêu). Như v y, trong trư ng h p này, t p R c a chúng ta ch g m có hai ph n t {"cháy n ng", "bình thư ng"}. Còn t p P là t t c nh ng ngư i ư c li t kê trong b ng dư i (8 ngư i) Chúng ta quan sát hi n tư ng cháy n ng d a trên 4 thu c tính sau : chi u cao (cao, trung bình, th p), màu tóc (vàng, nâu, ) cân n ng (nh , TB, n ng), dùng kem (có, không),. Ta g i các thu c tính này g i là thu c tính d n xu t. Dĩ nhiên là trong th c t có th ưa ra ư c m t k t lu n như v y, chúng ta c n nhi u d li u hơn và ng th i cũng c n nhi u thu c tính d n xu t trên. Ví d ơn gi n này ch nh m minh h a ý tư ng c a thu t toán máy h c mà chúng ta s p trình bày. Tên Tóc Ch.Cao Cân Dùng K t qu N ng kem? Sarah Vàng T.Bình Nh Không Cháy 87 Sưu t m b i: www.daihoc.com.vn
Dana Vàng Cao T.Bình Có Không Alex Nâu Th p T.Bình Có Không Annie Vàng Th p T.Bình Không Cháy Emilie T.Bình N ng Không Cháy Peter Nâu Cao N ng Không Không John Nâu T.Bình N ng Không Không Kartie Vàng Th p Nh Có Không Ý tư ng u tiên c a phương pháp này là tìm cách phân ho ch t p P ban u thành các t p Pi sao cho t t c các ph n t trong t t c các t p Pi u có chung thu c tính m c tiêu. P = P1  P2  ...  Pn và  (i,j) i j : thì (Pi  Pj =  ) và  i,  k,l : pk  Pi và pl  Pj thì f(pk) = f(pl) Sau khi ã phân ho ch xong t p P thành t p các phân ho ch Pi ư c c trưng b i thu c tính ích ri (ri  R), bư c ti p theo là ng v i m i phân ho ch Pi ta xây d ng lu t Li : GTi  ri trong ó các GTi là m nh ư c hình thành b ng cách k t h p các thu c tính d n xu t. M t l n n a, v n hình th c có th làm b n c m th y khó khăn. Chúng ta hãy th ý tư ng trên v i b ng s li u mà ta ã có. Có hai cách phân ho ch hi n nhiên nh t mà ai cũng có th nghĩ ra. Cách u tiên là cho m i ngư i vào m t phân ho ch riêng (P1 = {Sarah}, P2 = {Dana}, … t ng c ng s có 8 phân ho ch cho 8 ngư i). Cách th hai là phân ho ch thành hai t p, m t t p g m t t c nh ng ngư i cháy n ng và t p còn l i bao g m t t c nh ng ngư i không cháy n ng. Tuy ơn gi n nhưng phân ho ch theo ki u này thì chúng ta ch ng gi i quy t ư c gì !! II.1. âm ch i Chúng ta hãy th m t phương pháp khác. Bây gi b n hãy quan sát thu c tính u tiên – màu tóc. N u d a theo màu tóc phân chia ta s có ư c 3 phân ho ch khác nhau ng v i m i giá tr c a thu c tính màu tóc. C th là : Pvàng = { Sarah, Dana, Annie, Kartie } Pnâu = { Alex, Peter, John } P = { Emmile } 88 Sưu t m b i: www.daihoc.com.vn
* Các ngư i b cháy n ng ư c g ch dư i và in m. Thay vì li t kê ra như trên, ta dùng sơ cây ti n mô t cho các bư c phân ho ch sau : Quan sát hình trên ta th y r ng phân ho ch Pnâu và P th a mãn ư c i u ki n "có chung thu c tính m c tiêu" (Pnâu ch a toàn ngư i không cháy n ng, P ch a toàn ngư i cháy n ng). Còn l i t p Pvàng là còn l n l n ngư i cháy năng và không cháy n ng. Ta s ti p t c phân ho ch t p này thành các t p con. Bây gi ta hãy quan sát thu c tính chi u cao. Thu c tính này giúp phân ho ch t p Pvàng thành 3 t p con : PVàng, Th p = {Annie, Kartie}, PVàng, T.Bình= {Sarah} và PVàng,Cao= { Dana } N u n i ti p vào cây hình trư c ta s có hình nh cây phân ho ch như sau : Quá trình này c th ti p t c cho n khi t t c các nút lá c a cây không còn l n l n gi a cháy n ng và không cháy n ng n a. B n cũng th y r ng, qua m i bư c phân ho ch cây phân ho ch ngày càng "phình" ra. Chính vì v y mà quá trình này ư c g i là quá trình " âm ch i". Cây mà chúng ta ang xây d ng ư c g i là cây nh danh. n ây, chúng ta l i g p m t v n m i. N u như ban u ta không ch n thu c tính màu tóc phân ho ch mà ch n thu c tính khác như chi u cao ch ng h n phân ho ch thì sao? Cu i cùng thì cách phân ho ch nào s t t hơn? II.2. Phương án ch n thu c tính phân ho ch 89 Sưu t m b i: www.daihoc.com.vn
V n mà chúng ta g p ph i cũng tương t như bài toán tìm ki m : " ng trư c m t ngã r , ta c n ph i i vào hư ng nào?". Hai phương pháp ánh giá dư i ây s giúp ta ch n ư c thu c tính phân ho ch t i m i bư c xây d ng cây nh danh. II.2.1. Quinlan Quinlan quy t nh thu c tính phân ho ch b ng cách xây d ng các vector c trưng cho m i giá tr c a t ng thu c tính d n xu t và thu c tính m c tiêu. Cách tính c th như sau : V i m i thu c tính d n xu t A còn có th s d ng phân ho ch, tính : VA(j) = ( T(j , r1), T(j , r2) , …, T(j , rn) ) T(j, ri) = (t ng s ph n t trong phân ho ch có giá tr thu c tính d n xu t A là j và có giá tr thu c tính m c tiêu là ri ) / ( t ng s ph n t trong phân ho ch có giá tr thu c tính d n xu t A là j ) * trong ó r1, r2, … , rn là các giá tr c a thu c tính m c tiêu * Như v y n u m t thu c tính A có th nh n m t trong 5 giá tr khác nhau thì nó s có 5 vector c trưng. M t vector V(Aj ) ư c g i là vector ơn v n u nó ch có duy nh t m t thành ph n có giá tr 1 và nh ng thành ph n khác có giá tr 0. Thu c tính ư c ch n phân ho ch là thu c tính có nhi u vector ơn v nh t. Tr l i ví d c a chúng ta, tr ng thái ban u (chưa phân ho ch) chúng ta s tính vector c trưng cho t ng thu c tính d n xu t tìm ra thu c tính dùng phân ho ch. u tiên là thu c tính màu tóc. Thu c tính màu tóc có 3 giá tr khác nhau (vàng, , nâu) nên s có 3 vector c trưng tương ng là : VTóc (vàng) = ( T(vàng, cháy n ng), T(vàng, không cháy n ng) ) S ngư i tóc vàng là : 4 S ngư i tóc vàng và cháy n ng là : 2 S ngư i tóc vàng và không cháy n ng là : 2 Do ó VTóc(vàng) = (2/4 , 2/4) = (0.5, 0.5) Tương t 90 Sưu t m b i: www.daihoc.com.vn
VTóc(nâu) = (0/3, 3/3) = (0,1) (vector ơn v ) S ngư i tóc nâu là : 3 S ngư i tóc nâu và cháy n ng là : 0 S ngư i tóc nâu và không cháy n ng là : 3 VTóc( ) = (1/1, 0/1) = (1,0) (vector ơn v ) T ng s vector ơn v c a thu c tính tóc vàng là 2 Các thu c tính khác ư c tính tương t , k t qu như sau : VC.Cao(Cao) = (0/2,2/2) = (0,1) VC.Cao(T.B) = (2/3,1/3) VC.Cao(Th p) = (1/3,2/3) VC.N ng (Nh ) = (1/2,1/2) VC.N ng (T.B) = (1/3,2/3) VC.N ng (N ng) = (1/3,2/3) VKem (Có) = (3/3,0/3) = (1,0) VKem (Không) = (3/5,2/5) Như v y thu c tính màu tóc có s vector ơn v nhi u nh t nên s ư c ch n phân ho ch. Sau khi phân ho ch theo màu tóc xong, ch có phân ho ch theo tóc vàng (Pvàng) là còn ch a nh ng ngư i cháy n ng và không cháy n ng nên ta s ti p t c phân ho ch t p này. Ta s th c hi n thao tác tính vector c trưng tương t i v i các thu c tính còn l i (chi u cao, cân n ng, dùng kem). Trong phân ho ch Pvàng, t p d li u c a chúng ta còn l i là : Tên Ch.Cao Cân Dùng K t qu N ng kem? Sarah T.Bình Nh Không Cháy Dana Cao T.Bình Có Không 91 Sưu t m b i: www.daihoc.com.vn