Ờ L I CAM ĐOAN
ậ ồ ố ớ ề ệ Em xin cam đoan: Khóa lu n văn đ án t ứ t nghi p v i đ tài “Nghiên c u
ử ụ ậ ệ thu t toán Knearest neighbor và s d ng iris flowers dataset đánh giá hi u qu
̃ ́ ể ủ ả ế ậ ả ừ ư ứ thu t toán” là k t qu nghiên c u, tìm hi u c a b n thân em t ả ́ ư nh ng kiên th c
̀ ̃ ̀ ̀ ượ ệ ữ ̣ ̣ ̣ c thây, cô trong Vi n Ky thuât va Công nghê truyên day trong nh ng năm
́ ệ ồ ̣ ̃ đa đ qua và môt sô ngu n tài li u khác liên quan.
ủ ệ ề ậ ọ ị Em xin ch u m i trách nhi m v khóa lu n văn c a mình!
̣ Nghê An, ngày 01 tháng 05 năm 2019
ự ệ Sinh viên th c hi n
ị ượ Phan Th Ph ng
Ụ
Ụ
M C L C
2
Ụ Ừ Ế Ắ DANH M C T VI T T T
ừ ế ắ STT T vi t t t Ý nghĩa
1 AI Artificial Intelligence
2 ML Machine learning
3 SVM Support Vector Machine
3
4 KNN K nearest neighbor
Ụ Ả Ể DANH M C B NG BI U
ộ STT Tên b ngả N i dung
ả 1 B ng 1 Thông tin loài hoa Setosa
ả 2 B ng 2 Thông tin loài hoa Versicolor
4
ả 3 B ng 3 Thông tin loài hoa virginica
Ụ Ả Ồ Ị DANH M C HÌNH NH, Đ TH
ộ STT ồ N i dung
ả Tên hình nh, đ thị
ố 1 Hình 1
ệ ữ M i quan h gi a AI, Machine Learning và Deep Learning
ụ ề ớ 2 Hình 1.1.2 Ví d v mô hình phân l p
ụ ọ 3 Hình 2.1.3 ậ Ví d minh h a thu t toán KNN
ễ ả ồ ọ ớ 4 Hình 2.1.4 B n đ minh h a knn nhi u v i k=1
5 Hình 2.2.2
Norm 1 và norm 2 trong không gian hai chi uề
ả 6 Hình 3.1.1 ọ ề Hình nh minh h a v Iris flower dataset
ụ ủ ọ 7 Hình 3.1.2
ơ ồ S đ minh h a phân c m c a Iris flower datasets
8 Hình 3.2.2 Mô hình bài toán
5
Ờ Ả Ơ L I C M N
ờ ầ ử ờ ả ơ ắ ớ ể ầ L i đ u tiên cho phép em g i l i c m n sâu s c t i toàn th các th y cô
ệ ệ ậ ỹ ườ ạ ọ ữ giáo trong Vi n K thu t và Công ngh – Tr ng Đ i h c Vinh, nh ng ng ườ i
ỉ ẫ ữ ứ ữ ề ế ế ạ đã h t mình truy n đ t và ch d n cho chúng em nh ng ki n th c, nh ng bài
ọ ừ ổ ọ ố h c quý báu và b ích trong su t 5 năm h c v a qua.
ể ượ ồ ặ ệ ượ ỏ ự Đ hoàn thành đ c đ án này, đ c bi t em xin đ c bày t s tri ân và xin
ả ơ ễ ậ ả ườ ự ế ướ chân thành c m n gi ng viên ThS. Nguy n Bùi H u ng i tr c ti p h ẫ ng d n,
ứ ể ọ ậ ỉ ả ố ồ ch b o em trong su t quá trình h c t p và nghiên c u đ hoàn thành đ án này.
ắ ớ ả ạ ử Sau n a, ữ em xin g i tình c m sâu s c t i gia đình và b n bè vì đã luôn bên
ỡ ả ề ậ ấ ẫ ế ầ ộ ố ạ c nh khuy n khích, đ ng viên, giúp đ c v v t ch t l n tinh th n em trong su t
ọ ậ ể ố quá trình h c t p đ em hoàn thành t ệ ủ t công vi c c a mình.
ứ ự ứ ế Trong quá trình nghiên c u và làm báo cáo do năng l c, ki n th c, trình đ ộ
ữ ẹ ế ạ ỏ ậ ả b n thân còn h n h p nên không tránh kh i nh ng thi u sót. Em kính mong nh n
ượ ự ữ ủ ế ầ ạ ả đ c s thông c m và nh ng ý ki n đóng góp c a quý th y cô và các b n.
ả ơ Em xin chân thành c m n!
ệ Ngh An, ngày 01 tháng 05 năm 2019
ự ệ Sinh viên th c hi n
ị ượ Phan Th Ph ng
6
Ở Ầ M Đ U
ề ặ ấ 1. Đ t v n đ
ư ộ ằ ữ ứ ủ ầ ổ ộ ạ Nh ng năm g n đây, AI n i lên nh m t b ng ch ng c a cu c cách m ng
ệ ầ ứ ư ể ượ ị ư ộ ệ ạ công nghi p l n th t . Trí tu nhân t o có th đ c đ nh nghĩa nh m t nghành
ệ ự ộ ế ọ ủ c a khoa h c máy tính liên quan đ n vi c t đ ng hóa các hành vi thông minh. Trí
ộ ộ ả ượ ủ ệ ậ tu nhân t o ọ ạ là m t b ph n c a khoa h c máy tính và do đó nó ph i đ ặ c đ t
ế ữ ữ ứ ụ ắ ả ượ ủ trên nh ng nguyên lý lý thuy t v ng ch c, có kh năng ng d ng đ c c a lĩnh
Ở ờ ệ ạ ữ ậ ườ ể ế
.
ự v c này ể th i đi m hi n t i, thu t ng này th ng dùng đ nói đ n các máy
ấ ị ụ ứ ề ọ ế tính có m c đích không nh t đ nh và ngành khoa h c nghiên c u v các lý thuy t
ụ ứ ệ ạ ủ và các ng d ng c a trí tu nhân t o.
ệ ứ ủ ụ ể ệ ạ Theo đà phát tri n c a công ngh , ng d ng trí tu nhân t o luôn là xu
ướ ệ ươ ế ớ ệ h ng công ngh t ng lai mà các hãng công ngh trên toàn th gi i đua nhau
ề ả ệ ạ ạ ố ố ủ sáng t o, nó là n n t ng c t lõi c a cu c cách m ng công ngh 4.0.
ự ủ ệ ạ ộ ượ ML (Machine Learning) là m t lĩnh v c c a trí tu nhân t o, đ c sinh ra
ệ ậ ẫ ừ ể ọ ế ừ ả t kh năng nh n di n m u và t ầ lý thuy t các máy tính có th h c mà không c n
ụ ụ ể ả ậ ể ử ệ ph i l p trình đ x lý các nhi m v c th nào đó.
ế ệ ệ ầ ọ ớ ượ H u h t m i nghành công nghi p đang làm vi c v i hàm l ớ ng l n d ữ
ủ ữ ệ ề ệ ậ ầ ọ li u đ u nh n ra t m quan tr ng c a công ngh ML. Nh ng cái nhìn sáng su t t ố ừ
ữ ệ ủ ế ự ẽ ồ ờ ổ ứ ậ ạ ngu n d li u này – ch y u d ng th i gian th c – s giúp các t ch c v n hành
ặ ạ ợ ả ơ ệ ế ạ ớ ố hi u qu h n ho c t o l ủ i th c nh tranh so v i các đ i th .
ứ ụ ủ ộ ớ ườ ự Các ng d ng c a ML đã quá quen thu c v i con ng i: xe t ủ hành c a
ệ ố ự ệ ố ặ ợ Google và Tesla, h th ng t ả tag khuôn m t trên Facebook, h th ng g i ý s n
ệ ố ủ ủ ẩ ợ ộ ỉ ph m c a Amazon, h th ng g i ý phim c a Netflix…, ch là m t vài trong vô
7
ữ ứ ụ ể ụ ủ ệ ạ vàn nh ng ng d ng c a trí tu nhân t o và c th là ML.
ệ ữ
ố
Hình 1. M i quan h gi a AI, Machine Learning và Deep Learning
ướ ể ệ ớ Xu h ng phát tri n công ngh thông tin ngày càng tăng, song song v i nó
ữ ệ ượ ữ ệ ộ ớ ể ử ầ ậ ượ l ng d li u đ c sinh ra cũng ngày m t l n. Vì v y nhu c u đ x lý d li u
ầ ớ ơ ả ế ấ ữ ề ậ ộ cũng l n h n, ML đang góp ph n gi i quy t v n đ này. M t trong nh ng thu t
ườ toán th ậ ng dùng trong ML đó là thu t toán K nearest neighbor.
Ứ ủ ụ ậ ượ ử ụ ề ấ ộ ng d ng c a thu t toán này đ c s d ng r t nhi u và r ng rãi trong các
bài toán phân l p.ớ
2. M c đích nghiên c u
ụ ứ
Nghiên c u, tìm hi u thu t toán KNN.
ứ ể ậ
Đánh giá hi u qu c a thu t toán.
ả ủ ệ ậ
3. Ph m vi và đ i t
ố ượ ạ ứ ng nghiên c u
Ph m vi nghiên c u: Th nghi m trên Iris flower dataset.
8
ứ ử ệ ạ
Đ i t
ố ượ ứ ậ ộ ng nghiên c u: Thu t toán KNN và b Iris flower dataset.
4. N i dung th c hi n
ự ộ ệ
Tìm hi u thu t toán KNN.
ể ậ
Làm quen v i b d li u Iris.
ớ ộ ữ ệ
S d ng b d li u vào th nghi m và đánh giá.
ộ ữ ệ ử ụ ử ệ
5. C u trúc đ án
ồ ấ
M đ u
ở ầ
Ch
ươ ơ ở ế ng 1: C s lý thuy t
Ch
ươ ậ ng 2: Thu t toán Knearest neighbor
Ch
ươ ệ ử ng 3: Th nghi m
Ch
9
ươ ậ ế ng 4: K t lu n
1.1. Machine Learning
1.1.1.
ƯƠ Ơ Ở Ế CH NG 1. C S LÝ THUY T
ị Đ nh nghĩa
ự ủ ứ ế ệ ệ ạ ộ Là m t lĩnh v c c a trí tu nhân t o liên qua đ n vi c nghiên c u và xây
kĩ thu t cho phép các h th ng h c t
ệ ố ọ ự ộ ậ ể ả ự d ng các đ ng t ừ ữ ệ đ gi d li u ế i quy t các
ề ụ ể ư ệ ử ể ọ ụ ạ ả ấ v n đ c th . Ví d các máy có th h c cách phân lo i th đi n t có ph i th ư
ự ộ ư ụ ươ ứ ế ắ rác hay không và t đ ng s p x p vào các th m c t ng ng.
Machine Learning có liên quan đ n th ng kê vì c hai lĩnh v c đ u nghiên
ự ề ế ả ố
ữ ệ ư ệ ậ ọ ớ ố ứ c u vi c phân tích d li u, nh ng khác v i th ng kê, h c máy t p trung vào
ả ệ ự ứ ạ ủ s ph c t p c a các gi i thu t ự ậ trong vi c th c thi tính toán.
Machine Learning có hi n nay đ
ệ ượ ụ ộ c áp d ng r ng rãi bao g m ồ máy truy tìm
ị ườ ứ ậ ạ ữ ệ d li u, máy phân tích th tr ng ch ng khoán, ế nh n d ng ti ng nói và ch ữ
vi t…ế
1.1.2. M t s ph
ộ ố ươ ứ ủ ng th c c a Machine Learning
H c có giám sát:
Thu t toán d đoán đ u ra c a m t d li u m i (new
ọ ộ ữ ệ ự ủ ậ ầ ớ
10
ự ặ input) d a trên các c p ( ặ input, outcome) đã bi ế ừ ướ tr t t ữ ệ c. C p d li u này còn
ượ ọ ữ ệ đ c g i là ( data, label), t c (ứ d li u, nhãn ). Supervised learning là nhóm phổ
ế ấ ậ bi n nh t trong các thu t toán Machine Learning.
ọ ượ ạ H c có giám sát đ c chia thành hai lo i chính:
ớ ộ ố ượ ớ ữ ệ Classification (phân l p): L à quá trình phân l p m t đ i t ộ ng d li u vào m t
ề ớ ướ ờ ộ hay nhi u l p đã cho tr ớ c nh m t mô hình phân l p (model). Mô hình này đ ượ c
ữ ệ ộ ậ ự ự ượ ự ướ xây d ng d a trên m t t p d li u đ c xây d ng tr c đó có gán nhãn (hay còn
ệ ấ ậ ớ ố ượ ọ g i là t p hu n luy n). Quá trình phân l p là quá trình gán nhãn cho đ i t ng d ữ
ụ ề
ớ Hình 1.1.2: Ví d v mô hình phân l p
li u.ệ
ư ề ớ ớ ớ ớ ị ớ Có nhi u bài toán phân l p nh phân l p nh phân, phân l p đa l p, phân l p đa
11
ặ ạ ớ ộ ớ ị ị ệ ủ ớ ớ tr . Trong đó phân l p nh phân là m t lo i phân l p đ c bi t c a phân l p đa l p.
Ứ ớ ượ ử ụ ư ậ ụ ủ ề ấ ộ ng d ng c a bài toán phân l p đ ạ c s d ng r t nhi u và r ng rãi nh nh n d ng
ữ ế ặ ạ ư ệ ậ ạ ọ ậ khuôn m t, nh n d ng ch vi t, nh n d ng gi ng nói, phát hi n th rác…
ồ ượ ộ Regression (h i quy): N u ế không đ c chia thành các nhóm mà là m t giá tr ị
ự ụ ể ẽ ằ ủ ủ ể ể ầ ầ ộ ữ ệ th c c th . Đ u ra c a m t đi m d li u s b ng chính đ u ra c a đi m d ữ
ệ ế li u đã bi t.
ọ ậ ủ ằ ộ ộ H c không giám sát: ọ là m t kĩ thu t c a máy h c nh m tìm ra m t mô hình
ữ ệ ị ẩ ấ ượ ướ ơ ậ hay c u trúc b n b i t p d li u không đ c gán nhãn cho tr ớ c. UL khác v i
ể ị ướ ừ ậ ữ ệ ệ ấ ượ SL là không th xác đ nh tr c output t t p d li u hu n luy n đ c. Tùy
ệ ế ẽ ả ậ ấ ộ ượ ớ thu c vào t p hu n luy n k t qu output s khác nhau. Trái ng ậ c v i SL, t p
ệ ủ ấ ườ ẽ ữ ệ d li u hu n luy n c a UL không do con ng i gán nhãn, máy tính s ph i t ả ự
ẽ ụ ị ầ ể ộ ọ ọ h c hoàn toàn. Có th nói, h c không giám sát thì giá tr đ u ra s ph thu c vào
ậ ổ ế ủ ọ Ứ ụ ớ thu t toán UL . ng d ng l n ph bi n c a h c không giám sát là bài toán phân
c m.ụ
H c bán giám sát: Các bài toán khi có m t s l
ộ ố ượ ọ ớ ữ ệ ư ỉ ng l n d li u nh ng ch
ầ ộ ượ ữ ữ ằ ươ m t ph n trong chúng đ c dán nhãn. Nh ng bài toán này n m gi a ph ng
1.2.
ư ọ ọ th c h c giám sát và h c không giám sát.
1.2.1.
ớ ữ ệ Bài toán phân l p d li u
ớ ữ ệ Quá trình phân l p d li u
ự ể ượ ả ủ ệ ầ ớ Đ xây d ng đ c mô hình phân l p và đánh giá hi u qu c a mô hình c n
ự ệ ả ph i th c hi n quá trình sau đây:
ị ậ ữ ệ ướ ư ệ ấ ặ ẩ B c 1: Chu n b t p d li u hu n luy n và rút trích đ c tr ng.
ượ ề ạ ọ ạ Công đo n này đ c xem là công đo n quan tr ng trong các bài toán v ML. vì
ệ ọ ẻ ủ ả ế ầ đây là input cho vi c h c đ tìm ra mô hình c a bài toán. Chúng ta ph i bi t c n
ữ ư ặ ọ ố ủ ữ ệ ượ ỏ ữ ư ố ủ ch n ra nh ng đ c tr ng t t c a d li u, l ặ c b nh ng đ c tr ng không t t c a
ễ Ướ ượ ề ủ ữ ệ ố ố ữ ệ d li u, gây nhi u. c l ng s chi u c a d li u bao nhiêu là t t hay nói cách
12
ế ố ề ệ ọ ớ khác là ch n bao nhiêu feature. N u s nhi u quá l n gây khó khăn cho vi c tính
ề ủ ữ ệ ư ẫ ả ả ố ữ ượ ộ toán thì ph i gi m s chi u c a d li u nh ng v n gi c đ chính xác c a d ủ ữ đ
li u.ệ
ị ộ ữ ệ ể ẩ Ở ướ b c này chúng ta cũng chu n b b d li u đ test trên mô hình.
ườ ẽ ử ụ ể ể ậ Thông th ng s s d ng crossvalidation (ki m tra chéo) đ chia t p dataset
ầ ầ ộ ạ ụ ụ ụ ụ thành hai phàn, m t ph n ph c v cho training và ph n còn l ụ i ph c v cho m c
ườ ử ụ đích testing trên mô hình. Có hai cách th ng s d ng trong crossvalidation là
splitting và kfold.
ướ ớ ự B c 2: Xây d ng mô hình phân l p
ụ ủ ệ ấ M c đích c a mô hình hu n luy n là tìm ra hàm F(x) và thông qua hàm f tìm
ượ ữ ệ ướ ể ườ ượ ọ ọ đ c đ chúng ta gán nhãn cho d li u. B c này th ng đ c g i là h c hay
training.
F(x)= y
ầ ủ ữ ệ Trong đó: x là các feature hay input đ u vào c a d li u
ầ ớ Y là nhãn dán l p hay output đ u ra
ườ ự ể ớ Thông th ng đ xây d ng mô hình phân l p cho bài toán này chúng ta s ử
ậ ọ ư dungjcacs thu t toán h c giám sát nh KNN, NN, SVM, Decision tree, Navie
Bayers.
B c 3: Ki m tra d li u v i mô hình
ữ ệ ướ ể ớ
ượ ướ Sau khi tìm đ c mô hình phân l p ớ ở ướ b c hai, thì b ẽ ư c này chúng ta s đ a
ớ ẻ ể ữ ệ ớ vào các d li u m i đ ki m tra trên mô hình phân l p.
B c 4: Đánh giá mô hình phân l p và ch n ra mô hình t
ướ ớ ọ ố ấ t nh t
ướ ẽ ằ ố B c cu i cùng chúng ta s đánh giá mô hình b ng cách đánh giá m c đ l ứ ộ ỗ i
ữ ệ ữ ệ ượ ế ủ c a d li u testing và d li u training thông qua mô hình tìm đ c. N u không
ủ ế ả ả ố ổ ạ ượ đ t đ ố ủ c k t qu mong mu n c a chúng ta thì ph i thay đ i các tham s c a
ể ậ ọ ố ơ ể ạ thu t toán h c đ tìm ra các mô hình t t h n và ki m tra, đánh giá l i mô hình
ớ ố ớ ố ủ ấ ọ phân l p. và cu i cùng ch n ra mô hình phân l p t t nh t cho bài toán c a chúng
13
ta.
14
ƯƠ Ậ CH NG 2: THU T TOÁN KNEAREST NEIGHBOR
ậ 2.1. Thu t toán knearest neighbor
ị 2.1.1. Đ nh nghĩa
ữ ậ ọ ộ Knearest neighbor (KNN) là m t trong nh ng thu t toán h c có giám sát
ấ ả ưở ủ ơ đ n gi n nh t trong Machine Learning. Ý t ng c a KNN là tìm ra output c a d ủ ữ
ệ ự ữ ệ ủ ầ ấ ữ ki u d a trên thông tin c a nh ng d li u training g n nó nh t.
ệ ủ ậ 2.1.2. Quy trình làm vi c c a thu t toán KNN
ướ ề ầ ấ ố ị ố B c 1: xác đ nh tham s K= s láng gi ng g n nh t.
B c 2: tính kho ng cách đ i t
ố ượ ướ ả ớ ấ ả ầ ớ ng c n phân l p v i t t c các đ i t ố ượ ng
trong training data.
B c 3: s p x p kho ng cách theo th t
ứ ự ướ ế ả ắ ầ ị tăng d n và xác đ nh K láng
ấ ớ ố ượ ề ầ ầ ớ gi ng g n nh t v i đ i t ng c n phân l p
B c 4: l y t
ấ ấ ả ớ ủ ướ ề ấ ầ t c các l p c a K láng gi ng g n nh t.
B c 5: d a vào ph n l n l p c a K đ xác đ nh l p cho đ i t
ầ ớ ớ ố ượ ướ ủ ự ể ớ ị ầ ng c n
phân l p.ớ
15
ụ ọ 2.1.3. Ví d minh h a
ụ
ậ
ọ
Hình 2.1.3. ví d minh h a thu t toán KNN
ả ử ượ ặ ớ ộ ườ ạ Gi s bài toán đ c đ t ra: mình m i quen m t ng i b n, tuy nhiên
ủ ầ ậ ế ườ ạ ả mình là fan c a UsUk v y nên mình c n bi t ng ủ i b n này có ph i là fan c a
ể ậ ờ ượ KPop hay không. Qua th i gian tìm hi u mình đã thu th p đ ộ ố ữ ệ c m t s d li u
ệ ướ ạ ẽ ể và đã bi u hi n d i d ng hình v trên.
ễ ễ ể ạ ấ Ta d dàng nhìn th y có hai lo i: hình vuông màu xanh bi u di n cho
ữ ườ ỏ ể ủ ữ ễ nh ng ng i là fan c a Kpop, tam giác màu đ bi u di n cho nh ng ng ườ i
ủ ườ ạ ố ế không là fan c a Kpop, hình tròn màu xanh là ng i b n mình mu n bi ả t có ph i
ữ ể ấ ả ạ là fan Kpop hay không, kho ng cách gi a ch m tròn và các đi m còn l ể i bi u
ễ ế ủ ạ ữ ớ ườ ạ ộ di n đ thân thi t c a b n đó v i nh ng ng i b n.
ươ ấ ể ể ạ ả ơ ớ ơ Ph ng pháp đ n gi n nh t đ ki m tra xem b n đó ch i thân v i ng ườ i
ấ ứ ể ấ ầ ộ ạ b n nào nh t, t c là tìm xem đi m g n ch m xanh thu c class nào (hình vuông
ừ ể ễ ấ ấ ấ ầ ậ hay tam giác). T hình trên ta d dàng nh n th y đi m g n ch m xanh nh t là
ẽ ượ ỏ ớ hình tam giác màu đ , do đó nó s đ ỏ c phân vào l p tam giác màu đ .
ộ ấ ề ươ ấ ấ Có m t v n đ trong ph ệ ng pháp trên, xung quanh c m xanh xu t hi n
ư ề ể ầ ấ ả ệ ấ r t nhi u hình vuông màu xanh nên vi c xét đi m g n nh t là ch a kh thi. Vì
16
ể ẽ ấ ầ ả ử ự ễ ấ ậ v y, ta s xét k đi m g n nh t. Gi s , ta l y K=3, d a theo hình trên ta d dàng
ả ậ ỏ ầ ộ nh n ra có hai hình tam giác đ và m t hình vuông xanh có kho ng cách g n
ấ ấ ấ ượ ỏ ấ ớ ch m xanh nh t, do đó ch m xanh đ c phân vào l p tam giác đ . L y K=7, ta có
ấ ỏ ượ ế năm hình vuông xanh và hai hình tam giác đ , lúc này ch m xanh đ c x p vào
ườ ợ ấ ẽ ấ ậ ớ l p hình vuông xanh. Tr ng h p l y K=4, ta nh n th y s có hai hình vuông
ỏ ườ ể ằ ợ xanh và hai hình tam giác đ , đây là tr ng h p có đi m b ng nhau, v i tr ớ ườ ng
ẽ ử ủ ả ằ ổ ầ ợ h p này KNN s x lý b ng cách so sánh t ng kho ng cách c a các hình g n
ấ ớ ể nh t v i đi m ta đang xét.
ệ ườ ể ậ ợ ườ ườ ấ Do xu t hi n tr ằ ng h p có đi m b ng nhau, vì v y ng i ta th ọ ng ch n k là
ưở ủ ố ẻ s l . Đó cũng là ý t ng c a KNN.
ễ ớ
ả
ọ
ồ Hình 2.1.4. B n đ minh h a knn nhi u v i k=1
ễ ụ ề 2.1.4. Ví d v Knn nhi u
ụ ể ớ ỏ ỗ ớ ớ ữ ệ Hình trên là bài toán phân l p v i ba l p: đ , lam, l c. M i đi m d li u
ớ ẽ ượ ộ ề ủ ể m i s đ c gán nhãn theo màu c a đi m đó mà nó thu c v . Trong hình này, chú
ụ ằ ấ ằ ữ ể ậ ý vùng khoanh tròn màu vàng, ta nh n th y r ng đi m màu l c n m gi a hai vùng
ữ ệ ề ể ể ễ ế ấ ẫ ớ ỏ ớ l n v i nhi u d li u đ và lam, đi m này r t có th là nhi u d n đ n vi c d ệ ữ
17
ế ơ ề ẽ ế ệ ệ ả ả li u test n u r i vào vùng này s có nhi u kh năng cho k t qu sai l ch.
ượ ủ ể ậ Ư ể 2.1.5. u đi m, nh c đi m c a thu t toán
Ư ể u đi m:
D s d ng và cài đ t.
ễ ử ụ ặ
Vi c d đoán k t qu c a d li u m i d dàng.
ả ủ ữ ệ ệ ự ớ ễ ế
ộ ứ ạ ỏ Đ ph c t p tính toán nh .
Nh
ượ ể c đi m:
ễ ư ế ễ ả ỏ KNN nhi u d đ a ra k t qu không chính xác khi k nh .
C n th i gian l u training set, khi d li u training và test tăng lên nhi u s
ữ ệ ư ầ ờ ề ẽ
ề ấ ờ m t nhi u th i gian tính toán.
ả 2.2. Kho ng cách trong không gian vector
ữ ệ ể ề ả ấ ộ
ệ ố ủ ữ ệ ấ ộ ị ị Trong không gian m t chi u, vi c đo kho ng cách gi a hai đi m đã r t quen ề thu c: l y tr tuy t đ i c a hi u gi a hai giá tr đó. Trong không gian hai chi u,
ặ ẳ ườ ể ả ả ứ t c m t ph ng, chúng ta th ng dùng kho ng cách Euclid đ đo kho ng cách
ữ ể . gi a hai đi m
ữ ệ ữ ứ ệ ể ề ề ả Vi c đo kho ng cách gi a hai đi m d li u nhi u chi u, t c hai vector, là
ế ể ầ ấ ầ r t c n thi t trong Machine Learning. Chúng ta c n đánh giá xem đi m nào là
ấ ủ ể ể ầ ầ ộ ộ đi m g n nh t c a m t đi m khác; chúng ta cũng c n đánh giá xem đ chính xác
ệ ướ ượ ụ ữ ấ ủ c a vi c c l ề ng; và trong r t nhi u ví d khác n a.
ề ệ ạ ờ Và đó chính là lý do mà khái ni m norm ra đ i. Có nhi u lo i norm khác
18
ạ ẽ ấ ở ướ nhau mà các b n s th y d i đây:
ữ ể ả ị ườ ườ Đ xác đ nh kho ng cách gi a hai vector i ta th ụ ng áp d ng y và z, ng
ố ộ ố ượ ộ ể m t hàm s lên vector hi u ầ c dùng đ đo các vector c n ệ x = y−z. M t hàm s đ
ấ ặ ộ ệ có m t vài tính ch t đ c bi t.
ị 2.2.1. Đ nh nghĩa
ạ ộ ừ ề không gian ậ ố ự nn chi u sang t p s th c ộ M t hàm s ố f () ánh x m t đi m ể x t
ề ượ ọ ộ ề ế ệ ỏ m t chi u đ c g i là norm n u nó th a mãn ba đi u ki n sau đây:
ằ ấ F(x) >= 0. D u b ng x y ra ả x = 0.
α
∀α
€ R.
F(x1) +f(x2) >= f (x1 + x2), ∀x1, x2 € R
α F( x) = | |f(x),
ộ ố ườ 2.2.2. M t s norm th ng dùng
ả ử Gi s các vector x = [x1; x2…xn], y = [y1; y2…yn].
ậ ả ấ ộ ườ ượ ọ Nh n th y kho ng cách Euclid chính là m t norm, norm mày th ng đ c g i là
norm 2:
(1)
ấ ỳ ộ ố ớ ố ỏ ơ V i p là m t s không nh h n 1 b t k , hàm s sau đây:
(2)
ượ ứ ệ ỏ ượ ọ Đ c ch ng minh th a mãn ba ddieuf ki n trên, và đ c g i là norm p.
ậ ứ ể ở ầ ử ố ấ ằ Nh n th y r ng khi s các ph n t khác 0 p 0→ thì bi u th c bên trên tr thành
19
ượ ọ ả ẩ c g i là gi ả chu n (pseudonorm) 0. Nó không ph i c aủ x. Hàm số (2) khi p=0 đ
ủ ề ả ẩ ỏ ệ là norm vì nó không th a mãn đi u ki n 2 và 3 c a norm. Gi chu n này, th ườ ng
ượ ệ ề ọ đ c ký hi u là
ộ ||x||0, khá quan tr ng trong ML vì trong nhi u bài toán, chúng ta ầ ứ ố ượ ầ c n có ràng bu c “sparse”, t c s l ng thành ph n “active” c a ủ x là nh .ỏ
ộ ườ ượ Có m t vài giá tr c a ng đ c dùng: ị ủ p th
ư ở trên. Khi p = 2 chúng ta có norm2 nh
Khi p = 1 chúng ta có:
||x||1 = |x1| + |x2| + |x3| +…|xn| (3)
ệ ố ủ ừ ổ ị ườ ượ Là t ng các giá tr tuy t đ i c a t ng ph n t ng đ c dùng c a
ư ấ ỉ ủ ộ ầ ử ủ x. Norm 1 th ộ ướ ụ nh s p x c a norm 0 trong các bài toán có ràng bu c. D i đây là m t ví d so
Hình 2.2.2. Norm 1 và norm 2 trong không gian hai chi uề
sánh norm 1 và norm 2 trong không gian hai chi u:ề
ườ ữ Norm 2 (màu xanh) chính là đ ố ng chim bay n i gi a vector
20
ể ễ ữ ả ỏ ả ể Kho ng cách norm 1 gi a hai đi m này (màu đ ) có th di n gi x và vector y. ườ ng ư i nh là đ
ố ượ ạ ộ ố ờ đi t c t o hình bàn c , chúng ta ừ x đ n ế y trong m t thành ph mà thành ph đ
ờ ứ ể ể ọ ỉ ườ ch có th đi theo d c bàn c ch không th đi theo đ ẳ ng th ng.
ệ ố ủ ầ ử ớ ị Khi p > ∞, ta có norm p chính là tr tuy t đ i c a ph n t ấ ủ l n nh t c a
vector đó:
(4)
21
ƯƠ Ệ CH Ử NG 3: TH NGHI M
ộ ữ ệ 3.1. B d li u Iris flower dataset
ớ ệ i thi u 3.1.1. Gi
ậ ữ ệ ặ ậ ữ ệ ữ ệ ủ ậ
ế T p d li u hoa Iris ho c t p d li u Iris c a Fisher là t p d li u đa bi n ượ ậ ọ ườ ệ ớ ở ố i thi u b i nhà th ng kê và nhà sinh v t h c ng i Anh Ronald Fisher c gi đ
ệ ử ụ ề ề ấ ạ trong bài báo năm 1936 Vi c s d ng nhi u phép đo trong các v n đ phân lo i
ư ộ ụ ề ệ ế ượ ậ ọ nh m t ví d v phân tích phân bi t tuy n tính. Đôi khi nó đ c g i là t p d ữ
ữ ệ ể ị ủ ệ ậ ượ li u Iris c a Anderson vì Edgar Anderson đã thu th p d li u đ đ nh l ng s ự
ủ ủ ế ổ ố ượ bi n đ i hình thái c a hoa Iris c a ba loài liên quan. Hai trong s ba loài đ c thu
ậ ở ả ộ ồ ỏ ượ ọ th p Bán đ o Gaspé "t ấ ả ừ t c t cùng m t đ ng c , và đ ộ c ch n vào cùng m t
ượ ộ ườ ớ ộ ộ ngày và đ ở c đo cùng lúc b i cùng m t ng i v i cùng m t b máy".
ộ ữ ệ ẫ ừ ỗ ồ B d li u bao g m 50 m u t m i ba loài Iris (Iris setosa, Iris virginica và Iris
ể ặ ượ ừ ỗ ề ộ ủ ề ẫ ố Verscolor). B n đ c đi m đ c đo t m i m u: chi u dài và chi u r ng c a đài
ề ộ ề ự ằ hoa, chi u dài và chi u r ng ự ế ợ cánh hoa, tính b ng centimet. D a trên s k t h p
ể ộ ệ ế ủ ố c a b n tính năng này, Fisher đã phát tri n m t mô hình phân bi t tuy n tính đ ể
ọ ề
ả
Hình 3.1.1. Hình nh minh h a v Iris flower dataset
22
ệ ớ phân bi t các loài v i nhau.
ậ ữ ệ ử ụ 3.1.2. S d ng t p d li u
ự ệ ộ ữ ệ ủ ế ở D a trên mô hình phân bi t tuy n tính c a Fisher, b d li u này đã tr thành
ườ ử ệ ể ậ ạ ợ ố ỹ tr ề ng h p th nghi m đi n hình cho nhi u k thu t phân lo i th ng kê trong
ư ỗ ợ ọ h c máy nh máy vector h tr .
ệ ử ụ ữ ệ ụ ậ ổ ế Tuy nhiên, vi c s d ng t p d li u này trong phân tích c m không ph bi n,
ữ ệ ứ ụ ự ậ ộ ỉ ữ vì t p d li u ch ch a hai c m có s phân tách khá rõ ràng. M t trong nh ng
ứ ụ ạ ứ ả ụ c m ch a Iris setosa, trong khi c m còn l i ch a c Iris virginica và Iris Versolor
ờ ế ử ụ ể ề ề và không th tách r i n u không có thông tin v loài mà Fisher s d ng. Đi u này
ữ ệ ụ ố ể ả ộ ệ ữ ở làm cho d li u tr thành m t ví d t t đ gi ự i thích s khác bi t gi a các k ỹ
ậ ượ ữ ệ thu t đ c giám sát và không giám sát trong khai thác d li u: Mô hình phân bi ệ t
ủ ế ể ỉ ượ ế ố ượ ớ tuy n tính c a Fisher ch có th thu đ c khi bi t các loài đ i t ng: nhãn l p và
ấ ế ố ụ c m không nh t thi t gi ng nhau.
ề ể ế ả ờ ầ Tuy nhiên, c ba loài Iris đ u có th tách r i trong hình chi u trên thành ph n
ữ ệ ế ậ ượ ấ ớ ỉ ở ấ ầ chính phân nhánh phi tuy n. T p d li u đ ộ c x p x b i cây g n nh t v i m t
ố ượ ứ ể ố ạ ố s hình ph t cho s l ữ ệ ng nút, u n cong và kéo dài quá m c. Các đi m d li u
ượ ố ớ ơ ồ ủ ế ầ ấ đ ể ỗ c chi u vào nút g n nh t. Đ i v i m i nút, s đ hình tròn c a các đi m
ượ ượ ủ ệ ế ẩ ị ậ đ ế c chi u đ c chu n b . Di n tích c a chi c bánh t ỷ ệ l thu n v i s l ớ ố ượ ng
ượ ế ừ ơ ồ ướ ầ ớ ệ ố ằ ể đi m đ c chi u. Rõ ràng t s đ (bên d ẫ i) r ng ph n l n tuy t đ i các m u
ỉ ộ ề ầ ỏ ộ ủ c a các loài Iris khác nhau thu c v các nút khác nhau. Ch m t ph n nh Iris
ượ ộ ớ ỗ ợ virginica đ ơ ồ c tr n v i IrisVersolor (các nút màu xanh lam h n h p trong s đ ).
ể ượ Do đó, ba loài Iris (Iris setosa, Iris virginica và Iris Verscolor) có th đ c phân
ủ ụ ầ ằ ế tách b ng các th t c không giám sát trong phân tích thành ph n chính phi tuy n.
23
ể ệ ỉ ầ ọ ươ ứ Đ phân bi t chúng, ch c n ch n các nút t ng ng trên cây chính.
ơ ồ
ụ
ủ
ọ
Hình 3.1.2. S đ minh h a phân c m c a Iris flower datasets
ậ ữ ệ 3.1.3. T p d li u
ộ ữ ệ ộ ộ ứ ề ả ồ ộ B d li u ch a m t b 150 b n ghi bao g m các thu c tính – chi u dài và
ề ộ ề ộ ủ ủ ề chi u r ng c a đài hoa, chi u dài và chi u r ng c a cánh hoa.
ả B ng 1: Thông tin loài Setosa
ề Th tứ ự Chi u dài đài
1
5.1
3.5
1.4
0.2
2
4.9
3.0
1.4
0.2
3
4.7
3.2
1.3
0.2
4
4.6
3.1
1.5
0.2
5
5.0
3.6
1.4
0.3
6
5.4
3.9
1.7
0.4
24
hoa ề ộ Chi u r ng đài hoa ề Chi u dài cánh hoa ộ ề Chi u r ng cánh hoa
7
4.6
3.4
1.4
0.3
8
5.0
3.4
1.5
0.2
9
4.4
2.9
1.4
0.2
10
4.9
3.1
1.5
0.1
11
5.4
3.7
1.5
0.2
12
4.8
3.4
1.6
0.2
13
4.8
3.0
1.4
0.1
14
4.3
3.0
1.1
0.1
15
5.8
4.0
1.2
0.2
16
5.7
4.4
1.5
0.4
17
5.4
3.9
1.3
0.4
18
5.1
3.5
1.4
0.3
19
5.7
3.8
1.7
0.3
20
5.1
3.8
1.5
0.3
21
5.4
3.4
1.7
0.2
22
5.1
3.7
1.5
0.4
23
4.6
3.6
1.0
0.2
24
5.1
3.3
1.7
0.5
25
4.8
3.4
1.9
0.2
26
5.0
3.0
1.6
0.2
27
5.0
3.4
1.6
0.4
28
5.2
3.5
1.5
0.2
29
5.2
3.4
1.4
0.2
30
4.7
3.2
1.6
0.2
31
4.8
3.1
1.6
0.2
32
5.4
3.4
1.5
0.4
33
5.2
4.1
1.5
0.1
34
5.5
4.2
1.4
0.2
35
4.9
3.1
1.5
0.2
36
5.0
3.2
1.2
0.2
37
5.5
3.5
1.3
0.2
38
4.9
3.6
1.4
0.1
25
39
4.4
3.0
1.3
0.2
40
5.1
3.4
1.5
0.2
41
5.0
3.5
1.3
0.3
42
4.5
2.3
1.3
0.3
43
4.4
3.2
1.3
0.2
44
5.0
3.5
1.6
0.6
45
5.1
3.8
1.9
0.4
46
4.8
3.0
1.4
0.3
47
5.1
3.8
1.6
0.2
48
4.6
3.2
1.4
0.2
49
5.3
3.7
1.5
0.2
50
5.0
3.3
1.4
0.2
ả B ng 2: Thông tin loài Versicolor
ề Th tứ ự Chi u dài đài
1
7.0
3.2
4.7
1.4
2
6.4
3.2
4.5
1.5
3
6.9
3.1
4.9
1.5
4
5.5
2.3
4.0
1.3
5
6.5
2.8
4.6
1.5
6
5.7
2.8
4.5
1.3
7
6.3
3.3
4.7
1.6
8
4.9
2.4
3.3
1.0
9
6.6
2.9
4.6
1.3
10
5.2
2.7
3.9
1.4
11
5.0
2.0
3.5
1.0
12
5.9
3.0
4.2
1.5
13
6.0
2.2
4.0
1.0
14
6.1
2.9
4.7
1.4
15
5.6
2.9
3.6
1.3
26
hoa ề ộ Chi u r ng đài hoa ề Chi u dài cánh hoa ộ ề Chi u r ng cánh hoa
16
6.7
3.1
4.4
1.4
17
5.6
3.0
4.5
1.5
18
5.8
2.7
4.1
1.0
19
6.2
2.2
4.5
1.5
20
5.6
2.5
3.9
1.1
21
5.9
3.2
4.8
1.8
22
6.1
2.8
4.0
1.3
23
6.3
2.5
4.9
1.5
24
6.1
2.8
4.7
1.2
25
6.4
2.9
4.3
1.3
26
6.6
3.0
4.4
1.4
27
6.8
2.8
4.8
1.4
28
6.7
3.0
5.0
1.7
29
6.0
2.9
4.5
1.5
30
5.7
2.6
3.5
1.0
31
5.5
2.4
3.8
1.1
32
5.5
2.4
3.7
1.0
33
5.8
2.7
3.9
1.2
34
6.0
2.7
5.1
1.6
35
5.4
3.0
4.5
1.5
36
6.0
3.4
4.5
1.6
37
6.7
3.1
4.7
1.5
38
6.3
2.3
4.4
1.3
39
5.6
3.0
4.1
1.3
40
5.5
2.5
4.0
1.3
41
5.5
2.6
4.4
1.2
42
6.1
3.0
4.6
1.4
43
5.8
2.6
4.0
1.2
44
5.0
2.3
3.3
1.0
45
5.6
2.7
4.2
1.3
46
5.7
3.0
4.2
1.2
47
5.7
2.9
4.2
1.3
27
48
6.2
2.9
4.3
1.3
49
5.1
2.5
3.0
1.1
50
5.7
2.8
4.1
1.3
ả B ng 3: Thông tin loài Virginica
ề Th tứ ự dài
1
6.3
3.3
6.0
2.5
2
5.8
2.7
5.1
1.9
3
7.1
3.0
5.9
2.1
4
6.3
2.9
5.6
1.8
5
6.5
3.0
5.8
2.2
6
7.6
3.0
6.6
2.1
7
4.9
2.5
4.5
1.7
8
7.3
2.9
6.3
1.8
9
6.7
2.5
5.8
1.8
10
7.2
3.6
6.1
2.5
11
6.5
3.2
5.1
2.0
12
6.4
2.7
5.3
1.9
13
6.8
3.0
5.5
2.1
14
5.7
2.5
5.0
2.0
15
5.8
2.8
5.1
2.4
16
6.4
3.2
5.3
2.3
17
6.5
3.0
5.5
1.8
18
7.7
3.8
6.7
2.2
19
7.7
2.6
6.9
2.3
20
6.0
2.2
5.0
1.5
21
6.9
3.2
5.7
2.3
28
Chi u dài đài hoa ề ộ Chi u r ng đài hoa ề Chi u cánh hoa ộ ề Chi u r ng cánh hoa
22
5.6
2.8
4.9
2.0
23
7.7
2.8
6.7
2.0
24
6.3
2.7
4.9
1.8
25
6.7
3.3
5.7
2.1
26
7.2
3.2
6.0
1.8
27
6.2
2.8
4.8
1.8
28
6.1
3.0
4.9
1.8
29
6.4
2.8
5.6
2.1
30
7.2
3.0
5.8
1.6
31
7.4
2.8
6.1
1.9
32
7.9
3.8
6.4
2.0
33
6.4
2.8
5.6
2.2
34
6.3
2.8
5.1
1.5
35
6.1
2.6
5.6
1.4
36
7.7
3.0
6.1
2.3
37
6.3
3.4
5.6
2.4
38
6.4
3.1
5.5
1.8
39
6.0
3.0
4.8
1.8
40
6.9
3.1
5.4
2.1
41
6.7
3.1
5.6
2.4
42
6.9
3.1
5.1
2.3
43
5.8
2.7
5.1
1.9
44
6.8
3.2
5.9
2.3
45
6.7
3.3
5.7
2.5
46
6.7
3.0
5.2
2.3
47
6.3
2.5
5.0
1.9
48
6.5
3.0
5.2
2.0
49
6.2
3.4
5.4
2.3
50
5.9
3.0
5.1
1.8
29
3.2. Cài đ tặ
https://www.python.org/downloads/
ặ 3.2.1. Cài đ t python 3.6
ả ạ i đây: T i python t
Xu t hi n trang nh hình d
ư ệ ấ ướ ấ ọ ộ i: Nh p chu t vào dowload và ch n window.
ứ ủ ệ ặ ả ấ Lúc đó xu t hi n trang có ch a các phiên b n c a Python, vì cài đ t Python 3.6
30
ồ ả ề ụ ả ướ ả ọ nên ta tìm phiên b n 3.6 r i t i v . Ví d hình d i tôi ch n phiên b n 3.6.2.
ả ề ấ ắ ầ ặ Khi t i v hoàn t ế t ta b t đ u ti n hành cài đ t:
ệ ừ ả ề ẻ ự ạ ặ ấ ọ Nh p đúp vào t p v a t i v đ cài đ t. T i đây có hai l a ch n:
ặ ị ổ ệ ẵ Install now: M c đ nh cài python vào C, cài s n IDLE, pip và tài li u…
Customize installation: cho phép ch n cài đ t và tính năng c n thi
31
ặ ầ ọ ế t.
ử ộ ư ạ ặ ở ể ạ Khi đã cài đ t xong, m IDLE đ ch y th m t đo n code nh sau:
ư ậ ệ ệ ặ ạ ủ Ok. Nh v y đã hoàn thành xong vi c cài đ t python, vi c còn l i c a chúng ta là
ư ệ ầ ữ ặ ế ể ỗ ợ cài đ t nh ng th vi n c n thi t đ h tr cho bài toán.
Ở ầ ư ệ đây, bài toán chúng ta c n các th vi n sau: numpy, matplotlib, sklearn.
ử ụ ể ặ S d ng cmd đ cài đ t:
ủ ự ư ế ặ ả ẵ ạ ệ N u pip c a b n ch a có s n gói thì ta ph i cài đ t cho nó, ta th c hi n
ư nh sau:
Sau khi cài đ t thành công gói pip ta ti p t c cài đ t th vi n numpy:
32
ế ụ ư ệ ặ ặ
ặ ư ệ Cài đ t th vi n matplotlib:
Cu i cùng ta cài đ t th vi n sklearn:
33
ư ệ ặ ố
ư ệ ỗ ợ ư ậ ư ặ Nh v y là đã hoàn thành cài đ t các th vi n h tr cho python cũng nh bài
toán.
ề ư ộ ở ộ ữ ệ ư ệ ứ M t đi u l u ý đây, trong th vi n sklearn nó có ch a b d li u Iris flower
ầ ử ụ ộ ữ ệ ề ữ ả ầ dataset nên khi c n s d ng b d li u này ta không c n ph i dowload v n a.
ề ư ệ ể ộ Tìm hi u m t chút v th vi n Sklearn:
ư ệ ổ ế ấ ủ ế ẵ Sklearn là th vi n ph bi n nh t c a python. Nó vi ứ ậ t s n các thu t toán ph c
ữ ệ ồ ấ ỉ ầ ế ạ ờ ả ạ t p, b n ch c n nhét d li u vào và ch nó tính toán r i l y k t qu .
ụ ể ả ố ộ ư ệ Ví d mu n tìm hi u xem python đang dùng thu c phiên b n nào vào th vi n
34
ỉ ầ ư ể ả ộ sklearn thu c phiên b n nào thì ta ch c n ki m tra nh sau:
ậ ượ ế ả K t qu nh n đ c:
ộ ữ ệ ư ệ ẵ ườ ượ Ngoài ra th vi n sklearn có s n các b d li u th ng đ c dùng trong nghiên
ứ c u: iris, files, digits, boston, same_images…
35
ệ ử 3.2.2. Th nghi m
Hình 3.2.2. Mô hình bài toán
ữ ệ ẽ ầ Trong ph n này, chúng ta s tách 150 d li u trong Iris flower dataset ra
ẽ ự ậ ầ ọ thành hai ph n, g i là training set và test set. Thu t toán s d a vào thông tin ở
ỗ ữ ệ ể ự ươ ứ ạ ớ training set đ d đoán xem m i d li u trong test set t ng ng v i lo i hoa nào.
ượ ẽ ượ ẩ ậ ủ ế ạ ố ớ ữ ệ D li u đ c chu n đoán này s đ c đ i chi u v i lo i hoa th t c a m i d ỗ ữ
ả ủ ể ệ ệ li u trong test set đ đánh giá hi u qu c a KNN.
B c 1: Khai báo các th vi n c n thi
36
ư ệ ầ ướ ế t
B c 2: Load d li u và hi n th vài d li u m u
ữ ệ ữ ệ ướ ệ ẫ ị
37
ậ ượ ế ả K t qu nh n đ c:
B c 3: Tách training set và test set:
ướ
ả ử ữ ệ ể ể ố Gi s chúng ta mu n dùng 50 đi m d li u cho test set và 100 đi m còn l ạ i
ư ệ ẫ ố ộ cho training set. Th vi n sklearn có m t hàm s cho phép chúng ta ng u nhiên
ọ ự l a ch n:
38
ậ ượ ế ả K t qu nh n đ c:
ướ ự B c 4: KNN d đoán
ườ ữ ệ ứ ể ể ớ ớ ỗ ỉ Xét tr ữ ệ ng h p K=1, t c là v i m i đi m d li u test ta ch xét 1 đi m d li u
ả ể ữ ệ ể ự ể ấ ầ ấ training g n nh t và l y nhãn c đi m đó đ d đoán cho đi m d li u test.
ậ ượ ế ả K t qu nh n đ c:
ậ ủ ữ ệ ự ế ầ ấ ả ớ ố ỉ K t qu cho th y nhãn d đoán g n gi ng v i label th t c a d li u test, ch có 2
ể ố ượ ể ệ ả ị trong s 20 đi m đ ế c hi n th có k t qu sai l ch.
ướ B c 5: Đánh giá
ủ ể ậ ộ ể Đ đánh giá đ chính xác c a thu t toán KNN, chúng ta xem có bao nhiêu đi m
ượ ố ượ ự ấ ổ ữ ệ trong d li u test đ c d đoán đúng. L y s l ng đó chia cho t ng s l ố ượ ng
ậ ữ ệ ư ệ ẽ ấ ộ trong t p d li u test s ra đ chính xác. Th vi n sklearn cung c p cho ta hàm s ố
39
ể ự ệ ệ accuracy_score đ th c hi n công vi c này.
ậ ượ ế ả K t qu nh n đ c:
ấ ằ ể ế ế ầ ậ ấ ả ớ ỉ V i K=1 đã cho ra k t qu 96%. Nh n th y r ng n u ch xét 1 đi m g n nh t có
ể ẫ ử ể ế ễ ế ế ậ ả ớ ế th d n đ n k t qu sai n u đi m đó là nhi u. V y nên ta th xét v i K=9 thì k t
ả ẽ ư ế qu s nh th nào?
ậ ượ ế ả K t qu nh n đ c:
ế ả K t qu đã tăng lên 98%.
ư ậ ả ế ượ ớ ế ả ặ Nh v y chúng ta đã gi i quy t đ c bài toán đ t ra v i k t qu thu đ ượ c
ư ả ầ g n nh hoàn h o.
ấ ượ ể ầ ỹ Trong k thu t ỗ ậ majoring voting trên, m i trong 9 đi m g n nh t đ c xem
ự ế ề ư ế ị có vai trò và giá tr phi u nh nhau. Xét trên th c t đi u này là không đúng, vì rõ
ơ ẽ ữ ể ẽ ậ ả ầ ố ơ ọ ọ ràng nh ng đi m g n h n s ph i có tr ng s cao h n. V y nên ta s đánh tr ng
ư ề ể ệ ể ả ầ ỏ ố s khác nhau cho 9 đi m đang xét nh ng ph i th a mãn đi u ki n đi m g n test
40
ả ố ọ data thì ph i có tr ng s càng cao.
ị ặ ớ ươ ứ ể ớ V i giá tr m c đ nh ị weights=” uniform” t ậ ng ng v i các đi m lân c n
ị ư ể ầ có giá tr nh nhau, ta gán giá tr c a ớ ị ủ weights=” distance” lúc đó các đi m g n v i
ẽ ố ơ ọ test data s có tr ng s cao h n:
ế ả ọ ố K t qu sau khi đánh tr ng s :
ậ ượ ế ổ ả K t qu nh n đ c không thay đ i!
ƯƠ Ậ CH Ế NG 4: K T LU N
ự ệ ồ ố ế ứ ể ệ Trong quá trình th c hi n đ án t ố ắ t nghi p, em đã c g ng h t s c đ tìm
ư ể ả ỏ ọ ớ ạ ữ ỏ hi u và h c h i nh ng vì kh năng còn gi i h n không tránh kh i nh ng sai sót,
ả ữ ấ ấ nên có theerchuwa gi i quy t đ ế ượ ấ ả c t ề ặ t c nh ng v n đ , đ t ra. Em r t mong
ậ ượ ự ả ơ ủ ạ ầ ả nh n đ c s thông c m c a quý th y cô và các b n. Em xin chân thành c m n.
ả ạ ượ ữ ế Nh ng k t qu đ t đ c:
ự ể ế ề ơ ả ươ ậ ố ố S hi u bi t v thu t toán KNN c b n t ng đ i t t.
ớ Làm quen v i Iris flower dataset.
ừ ế ứ ụ ề ữ T nh ng gì đã làm đ ượ ừ c, t ể đó hi u bi ủ ủ t thêm v AI, ng d ng c a c a
ệ ệ ờ ố ạ ML vào đ i s ng công ngh hi n đ i.
41
ữ ậ Làm quen ngôn ng l p trình Python
ữ ạ ế Nh ng h n ch :
ệ ố ụ ề ậ ộ Thu t toán ph thu c nhi u vào h s K.
ả ư ự ế ể ấ ẫ ổ K t qu đ a ra có s thay đ i (vì các đi m xét l y ng u nhiên).
ự ự ể ế ề ư Ch a th s hi u h t v bài toán.
Ả Ệ TÀI LI U THAM KH O
[1] https://machinelearningcoban.com/2017/01/08/knn/
[2] https://en.wikipedia.org/wiki/Iris_flower_data_set
[3] https://machinelearningcoban.com/
[4] https://vi.wikipedia.org/wiki/Hoc_máy
ơ ả ữ ệ ọ ỹ ậ [5] Vũ H u Ti p, Machine Learning c b n, NXB Khoa H c Và K Thu t,
42
2018.
