Bài tập lớn môn Khai phá dữ liệu: Phân lớp dữ liệu số bằng giải thuật K-NN

ườ ạ ễ GVHD: Nguy n M nh C ng

ƯỜ

Ạ Ọ

Ệ

Ộ NG Đ I H C CÔNG NGHI P HÀ N I

Ệ

KHOA CÔNG NGH THÔNG TIN

Ậ Ớ

BÁO CÁO BÀI T P L N

ữ ệ

Môn Khai phá d li u

ả

ậ

ớ ữ ệ ố ằ Phân l p d li u s b ng gi

i thu t KNN

ướ

ườ

ẫ

ạ

Giáo viên h

ễ ng d n: Nguy n M nh C ng

Nhóm 5

ớ

ề

ậ

ầ

ỹ

L p K thu t ph n m m 1 – K7

Thành viên:

ễ

Nguy n Hà Anh Dũng

ễ

Nguy n Quang Long

ễ

ị

ả Nguy n Th Th o

Nhóm 5 1

ườ ạ ễ GVHD: Nguy n M nh C ng

ộ Hà N i, tháng 5 năm 2016

ờ

ầ

L i nói đ u

ờ ạ ệ ệ

ể ừ ủ

ổ ồ ữ ớ ố ộ đã có. Các ph

ướ ượ ng k

ươ ứ ệ ậ ậ ỹ

ư ữ ổ Trong th i bu i hi n đ i ngày nay, công ngh thông tin cũng nh nh ng ứ ơ ở ữ ệ ượ ượ ụ c ng thông tin và c s d li u đ ng d ng c a nó không ng ng phát tri n, l ế ườ ề ậ ộ thu th p và l u tr cũng tích lũy ngày m t nhi u lên. Con ng i cũng vì th mà ầ ữ ượ ự ế ị ấ ể ư c n có thông tin v i t c đ nhanh nh t đ đ a ra quy t đ nh d a trên l ng d ơ ở ữ ệ ệ ề ị ả li u kh ng l ng pháp qu n tr và khai thác c s d li u truy n ỹ ế ộ ố ự ế c th c t th ng ngày càng không đáp ng đ , vì th , m t khuynh h ượ ữ ệ ứ ớ c thu t m i là K thu t phát hi n tri th c và khai phá d li u nhanh chóng đ phát tri n.ể

ượ ứ ứ ề Khai phá d li u đã và đang đ

ướ ỹ Vi

ậ t Nam, k thu t này đang đ ộ ướ ữ ệ ứ

ứ ấ ườ ệ ọ

ệ ữ ệ ượ ế ả ố ệ ấ ộ ữ ệ ở ự các n v c khác nhau c trên th gi ư ầ nghiên c u và d n đ a vào ng d ng. Khai phá d li u là m t b ừ ứ trình ph t hi n tri th c. Hi n nay, m i ng ể ự đ th c hi n khai phá d li u m t cách nhanh nh t và có đ ụ c nghiên c u, ng d ng trong nhi u lĩnh ượ ế ớ Ở ệ c i. ụ c trong quy ậ ỹ i không ng ng tìm tòi các k thu t ấ t nh t. c k t qu t

ề ộ ỹ ề ậ ớ ể ậ ữ ệ ữ ệ ữ ệ ớ

ớ ữ ệ ố ằ ả ”. ể Trong bài t p l n này, chúng em tìm hi u và trình bày v m t k thu t trong khai ớ ề phá d li u đ phân l p d li u cũng nh t ng quan v khai phá d li u, v i đ tài “ Phân l p d li u s b ng gi ư ổ ậ i thu t KNN

ậ ớ Trong quá trình làm bài t p l n này, chúng em xin g i l

ầ ướ ễ ấ ậ Th y đã r t t n tình h ạ Nguy n M nh C ng.

ườ ầ ữ

ế ừ ầ ữ ử ờ ả ơ ế i c m n đ n ế ẫ ầ t cho ng d n chi ti th y giáo ậ ấ ấ ấ ữ chúng em, nh ng ki n th c th y cung c p r t h u ích. Chúng em r t mong nh n ượ đ c nh ng góp ý t ứ th y.

ả ơ Chúng em xin chân thành c m n!

Sinh viên nhóm 5.

Nhóm 5 2

ườ ạ ễ GVHD: Nguy n M nh C ng

ươ

ữ ệ

ổ

ề ng 1: T ng quan v Khai phá d li u

ơ ả

ệ

1.1. Khái ni m c b n

- Khai phá d li u là gì ?

ữ ệ

ữ ệ ộ ẫ Khai phá d li u là m t quá trình xác đ nh các m u ti m n có tính h p l ợ ệ ,

ớ ạ ể ể ượ ị ộ ề ẩ ố ữ ệ ấ ớ m i l , có ích và có th hi u đ c trong m t kh i d li u r t l n.

- Khai phá tri th c t

ứ ừ CSDL ( Knowledge Discovery in Database)

ứ ừ ồ Khai phá tri th c t CSDL g m 5 b ướ c

ự ọ B1: L a ch n CSDL

ề ử B2: Ti n x lý

ể ổ B3: Chuy n đ i

ữ ệ B4: Khai phá d li u

ễ ả B5: Di n gi i và đánh giá

 Khai phá d li u là 1 b

ữ ệ ướ ứ ừ c trong quá trình khai phá tri th c t CSDL

ữ ệ ứ ụ ủ - Các ng d ng c a khai phá d li u

Nhóm 5 3

ườ ạ ễ GVHD: Nguy n M nh C ng

ề ế ệ ứ ữ ệ ề

ố ạ ệ ậ

ộ ậ ứ

ứ ự ớ

ữ ệ ấ ầ ữ ệ ữ ệ ố ẫ ể ệ ậ ố

ệ ươ ữ ệ ụ ự

ế ệ ẽ ớ ứ ấ ặ

ữ ệ Phát hi n tri th c và khai phá d li u liên quan đ n nhi u ngành, nhi u lĩnh ơ ở ữ ệ ự v c: th ng kê, trí tu nhân t o, c s d li u, thu t toán, tính toán song song và ệ ặ ệ ố t c đ cao, thu th p tri th c cho các h chuyên gia, quan sát d li u... Đ c bi t ử ụ phát hi n tri th c và khai phá d li u r t g n gũi v i lĩnh v c th ng kê, s d ng các ph ng pháp th ng kê đ mô hình d li u và phát hi n các m u, lu t ... Ngân hàng d li u (Data Warehousing) và các công c phân tích tr c tuy n (OLAP On Line Analytical Processing) cũng liên quan r t ch t ch v i phát hi n tri th c và khai phá d li u.

ữ ệ ề ứ ự ế ụ Khai phá d li u có nhi u ng d ng trong th c t ụ ư , ví d nh :

ả ể ị ườ

ứ ủ

(cid:0) B o hi m, tài chính và th tr chính và d báo giá c a các lo i c phi u trong th tr ấ Danh m c v n và giá, lãi su t, d li u th tín d ng, phát hi n gian l n, ...

ng ch ng khoán: phân tích tình hình tài ị ườ ng ch ng khoán. ậ ệ ự ụ ố ạ ổ ữ ệ ứ ế ẻ ụ

(cid:0) Th ng kê, phân tích d li u và h tr ra quy t đ nh. ữ ệ

ỗ ợ ế ị ố

ị ề ế ệ ẩ

ọ ệ ố ệ ữ ả

(cid:0) Đi u tr y h c và chăm sóc y t ư ề ộ ố : m t s thông tin v chu n đoán b nh l u ệ ố ệ ệ trong các h th ng qu n lý b nh vi n. Phân tích m i liên h gi a các tri u ứ ị ệ ch ng b nh, chu n đoán và ph ng, ng pháp đi u tr (ch đ dinh d ố thu c, ...)

ế ộ ươ ưỡ ề ẩ

(cid:0) S n xu t và ch bi n: Quy trình, ph ế ế

ả ấ ươ ế ế ử ự ố ng pháp ch bi n và x lý s c .

(cid:0) Text mining và Web mining: Phân l p văn b n và các trang Web, tóm t ớ ả văn b n,...

ả ắ t

ọ ự ữ ệ

ữ ệ ố ề ệ

(cid:0) Lĩnh v c khoa h c: Quan sát thiên văn, d li u gene, d li u sinh v t h c, ậ ọ ệ tìm ki m, so sánh các h gene và thông tin di truy n, m i liên h gene và m t s b nh di truy n, ...

ế ộ ố ệ ề

ệ ố ễ ệ ạ ọ

(cid:0) M ng vi n thông: Phân tích các cu c g i đi n tho i và h th ng giám sát ộ ạ ỗ ự ố l

ấ ượ ụ ị i, s c , ch t l ng d ch v , ...

- Các b

ướ ủ ữ ệ c c a quá trình khai phá d li u

ứ ệ ườ ướ Quy trình phát hi n tri th c th ng tuân theo các b c sau:

Nhóm 5 4

ườ ạ ễ GVHD: Nguy n M nh C ng

ị

c th nh t: ừ ệ

ể ứ ấ Hình thành, xác đ nh và đ nh nghĩa bài toán. Là tìm hi u ị ả ị ụ đó hình thành bài toán, xác đ nh các nhi m v c n ph i ướ ế ị ượ

ụ ầ ứ ữ c các tri th c h u ích và ụ ợ ệ ữ ệ ứ ọ ớ

ẽ ươ ng pháp khai phá d li u thích h p v i m c đích ng ấ ủ ữ ệ ướ B ự ứ lĩnh v c ng d ng t hoàn thành. B c này s quy t đ nh cho vi c rút ra đ cho phép ch n các ph ả ụ d ng và b n ch t c a d li u.

ướ ề ử ử

ằ ữ ệ ễ ứ c th hai: ề ử

ậ ữ ệ ạ ọ ữ ệ ử ế ầ

ướ ộ t, b

ề

ấ ng chi m nhi u th i gian nh t trong toàn b qui trình phát ấ ồ ữ ệ ẽ ồ ầ ủ ể ấ ầ nhi u ngu n khác nhau, không đ ng nh t, ướ c này, d li u s nh t quán, đ y đ ,

ờ ạ ọ ậ B Thu th p và ti n x lý d li u. Là thu th p và x lý thô, còn ữ ệ ệ ạ ỏ ượ ọ c g i là ti n x lý d li u nh m lo i b nhi u (làm s ch d li u), x lý vi c đ ữ ệ ế ế ữ ệ ổ ữ ệ thi u d li u (làm giàu d li u), bi n đ i d li u và rút g n d li u n u c n ườ ế ề ờ ế c này th thi ữ ệ ượ ấ ừ ứ ệ c l y t hi n tri th c. Do d li u đ ẫ … có th gây ra các nh m l n. Sau b ượ c rút g n và r i r c hoá. đ

ướ ữ ệ B ứ c th ba: Khai phá d li u, rút ra các tri th c. Là khai phá d li u, hay

ữ ệ ặ

ư ạ

ấ ủ ạ ụ ữ ệ ươ

ư ồ

ự ấ ồ

ữ ệ ấ ủ ữ ệ ữ ệ ệ ị ệ ự c mà ta l a

ỳ ữ ệ ươ ọ ợ ứ ẫ ữ ệ ẩ ướ i các d li u. Giai nói cách khác là trích ra các m u ho c/và các mô hình n d ệ ứ ồ ọ ụ đo n này r t quan tr ng, bao g m các công đo n nh : ch c năng, nhi m v và ườ m c đích c a khai phá d li u, dùng ph ng, ng pháp khai phá nào? Thông th ả các bài toán khai phá d li u bao g m: các bài toán mang tính mô t đ a ra tính ả ệ ch t chung nh t c a d li u, các bài toán d báo bao g m c vi c phát hi n các ượ ễ ự suy di n d a trên d li u hi n có. Tu theo bài toán xác đ nh đ ch n các ph ng pháp khai phá d li u cho phù h p.

ứ ứ ứ ư S d ng các tri th c phát hi n đ c. Là hi u tri th c đã tìm

ỏ ả

ệ ộ ố ầ ử ụ t là làm sáng t ả ế các mô t ượ ể ượ ấ ướ B c th t : ặ ượ đ c, đ c bi ặ ạ l p l i m t s l n, k t qu thu đ ệ ượ ự và d đoán. Các b c có th đ ể ướ c l y trung bình trên t ể ặ c trên có th l p đi ấ ả t c các

Nhóm 5 5

ườ ạ ễ GVHD: Nguy n M nh C ng

ứ ế ệ c đ a vào

ể ượ ư ự ả ủ ự ệ ế ự ụ ể ả ầ l n th c hi n. Các k t qu c a quá trình phát hi n tri th c có th đ ứ ng d ng trong các lĩnh v c khác nhau do các k t qu có th là các d đoán.

ộ ố ỹ

ữ ệ

ậ 1.2. M t s k thu t Khai phá d li u

a. K thu t khai phá lu t k t h p

ậ ế ợ ậ ỹ

ậ ế ợ ố

ụ ố ượ ố ượ ệ ữ Trong khai phá d li u, m c đích c a lu t k t h p là tìm ra các m i quan h gi a các đ i t ủ ớ ữ ệ ng l n d li u. ữ ệ ng trong kh i l

ể ậ ế ợ ề ấ ậ ấ

ậ ư ổ ế ậ ị

ổ ế ữ ệ ượ ử ụ ậ ế ợ ể ệ ạ ị

ẳ ữ ệ ậ ế ợ ị Đ khai phá lu t k t h p có r t nhi u thu t toán, nh ng dùng ph bi n nh t là ậ thu t toán Apriori. Đây là thu t toán khai phá t p ph bi n trong d li u giao d ch ị ể c s d ng đ xác đ phát hi n các lu t k t h p d ng kh ng đ nh nh phân và đ ị đ nh, tìm ra các lu t k t h p trong d li u giao d ch.

ậ ậ Ngoài ra, còn có các thu t toán FPgrowth, thu t toán Partition,…

ớ ỹ ậ b. K thu t phân l p

ậ ậ ồ ớ ỹ Trong k thu t phân l p g m có các thu t toán:

- Phân l p b ng cây quy t đ nh (gi

ế ị ậ ả

ớ ữ ệ ự ế ế ị ể

ớ ằ ệ ậ ữ ệ ế ị ớ i thu t ID3, J48): phân l p d li u d a trên vi c l p nên cây quy t đ nh, nhìn vào cây quy t đ nh có th ra quy t ộ ị đ nh d li u thu c phân l p nào.

- Phân l p d a trên xác su t (Naïve Bayesian): d a trên vi c gi

ớ ự ự ệ ấ ả ị đ nh các

ệ ử ụ ộ ậ ạ ộ ớ ị thu c tính đ c l p m nh v i nhau qua vi c s d ng đ nh lý Bayes.

- Phân l p d a trên kho ng cách (gi

ớ ự ả ư

ữ ệ ẽ ượ ề ề i thu t K – láng gi ng): làm nh láng ớ ữ ệ ố ượ ậ ớ ủ ầ ng g n v i d li u c phân vào l p c a k đ i t

ả gi ng làm, d li u s đ đó nh t.ấ

ệ ằ ộ

ớ ữ ệ ớ ấ ể ề ề ố ơ ẳ ớ ữ ệ ự - Phân l p b ng SVM: phân l p d li u d a trên vi c tìm ra m t siêu ph ng t nh t” đ tách các l p d li u trên không gian nhi u chi u h n. “t

ụ ỹ ậ c. K thu t phân c m

ố ụ

ữ ệ ơ ầ ử ng d li u vào các nhóm/ c m sao ồ ụ khác c m, g m h n các ph n t

ố ượ ộ ố ươ ố ượ ố gi ng nhau ơ ả ụ Phân c m d li u cho các đ i t có m t s ph ữ ệ là cách phân b các đ i t ộ ụ ng trong m t c m thì ư ụ ng pháp phân c m c b n nh :

ụ ả ủ ng pháp Kmean: tìm ra tâm c a các c m mà kho ng cách

ằ ế ữ ệ ắ ươ ụ + Phân c m b ng ph ố ượ ủ c a tâm đó đ n các đ i t ng, d li u khác là ng n.

ụ ồ ị + Phân c m trên đ th

Nhóm 5 6

ườ ạ ễ GVHD: Nguy n M nh C ng

ữ ệ ấ ậ ỹ ỹ ậ ơ

ề ữ ệ ữ ể ượ ả ơ ư Ngoài ra, khai phá d li u có r t nhi u k thu t, nh ng đây là nh ng k thu t c ả b n và đ n gi n trong khai phá d li u mà chúng em đ c tìm hi u.

Nhóm 5 7

ườ ạ ễ GVHD: Nguy n M nh C ng

ươ

ả

ề

ậ

ấ

ầ

ng 2: Gi

i thu t K láng gi ng g n nh t (KNN)

ổ

ề

2.1. T ng quan v KNN

ữ ộ Bài toán phân lo i d li u là m t trong nh ng bài toán th

ườ ậ ượ ặ ư ả ậ ậ i thu t đ

ế ố ề ộ ế ầ ng g p trong ộ ố ể c đ a ra đ ề ả i quy t bài toán phân l p. M t trong s đó là thu t toán láng gi ng g n k

ạ ữ ệ ấ cu c s ng và kĩ thu t, có r t nhi u cách ti p c n và gi ậ ớ gi NN(kNearest Neighbors).

ầ ậ ề ụ ấ

ạ ớ ự ẫ ớ

ẫ ằ ọ

ậ ế ắ t là KNN) là thu t toán có m c đích Thu t toán K láng gi ng g n nh t ( vi t t ẫ ộ ộ phân lo i l p cho m t m u m i ( Query Point) d a trên các thu c tính và các m u ộ ệ ọ ượ ẵ s n có ( Training Data) , các m u này đ c n m tr ng m t h g i là không gian m u.ẫ

ớ ự ề ng đ

ượ ị ự ệ ậ

ướ c xác đ nh tr ể ữ ả ớ

ự ề ẫ ẩ ị

ớ ầ ướ ẫ ả ớ ủ ố ộ ố ượ c phân l p d a vào K láng gi ng c a nó. K là s nguyên M t đ i t ườ ườ ượ ươ i ta th c khi th c hi n thu t toán. Ng ng đ ng dùng d ẫ ớ ố ượ ả ng v i m u m i, sau kho ng cách Euclidean đ tính kho ng cách gi a các đ i t ộ ố ớ đó chu n đoán m u m i thu c phân l p nào d a vào s k láng gi ng xác đ nh ấ ẫ tr ớ c có kho ng cách g n m u m i nh t so v i các m u khác.

ả

ậ

2.2. Mô t

thu t toán KNN

ẫ ượ ề ỗ ộ ố

c mô t ộ ề ệ ạ ả ằ b ng n – chi u thu c tính s . M i m u đ i di n ấ ả ề t c các

Các m u đ ể ộ ẫ ượ ư ữ ề ộ ẫ cho m t đi m trong m t chi u không gian n – chi u. Theo cách này t m u đ c l u tr trong m t mô hình không gian n – chi u.

ướ ệ ủ ự ậ ượ ả ư Các b c th c hi n c a Thu t toán KNN đ c mô t nh sau:

(cid:0) Xác đ nh giá tr tham s K ( s láng gi ng g n nh t).

ề ầ ấ ố ố ị ị

(cid:0) ố ượ ầ

ố ượ ớ ẵ ẫ ả t c các đ i t ớ ữ ng c n phân l p (Query Point) v i ng trong các m u có s n (Trainning Data)

ả ườ ử ụ ả Tính kho ng cách gi a đ i t ấ t ( Th ng s d ng kho ng cách Euclidean).

(cid:0) ứ ự ầ ề ị tăng d n và xác đ nh K láng gi ng

ế ấ ớ ả ắ S p x p kho ng cách theo th t ầ g n nh t v i Query Point.

(cid:0) ấ ấ ả ớ ủ ấ ầ ị L y t ề t c các l p c a K láng gi ng g n nh t đã xác đ nh.

(cid:0) D a vào ph n l n l p c a láng gi ng g n nh t đ xác đ nh l p cho

ầ ớ ớ ủ ấ ể ự ề ầ ớ ị

Query Ponit.

ọ ề Minh h a v KNN:

Nhóm 5 8

ườ ạ ễ GVHD: Nguy n M nh C ng

ả ằ ấ c mô t

ị i đây, Trainning Data đ ớ ượ ướ c xác đ nh l p cho nó (Query Point) là hình m t c

ủ ệ ự ớ

ề ự ng l p c a Query Point d a vào vi c l a ch n s ế ệ ố ấ b ng d u (+) và d u (), ặ ườ ỏ i đ . ố ọ ẽ ượ c t li u Query Point s đ

ấ ớ ớ ớ Trong hình d ố ượ ượ ầ ng c n đ đ i t ướ ượ ụ ủ ệ Nhi m v c a ta là c l ầ láng gi ng g n nh t v i nó. Nói cách khác ta mu n bi phân vào l p (+) hay l p ().

 Ta th y r ng:

ấ ằ

ấ

ề ộ ớ ề ớ ượ ế c x p vào l p d u (–) vì ơ ng thu c l p (–) nhi u h n

ầ ố ượ ế ả Có 5 Nearest Neightbor: K t qu là (–) :Query Point đ ố ượ ấ ớ trong 5 láng gi ng g n nh t v i nó thì có 3 đ i t ỉ ớ l p (+) ch có 2 đ i t ng.)

ư

ượ

ủ

ể

ậ

2.3. Đánh giá u, nh

c đi m c a thu t toán

Ư ể u đi m:

ư ưở ớ ệ ố ả ơ + T t ỏ ợ ng đ n gi n, thích h p v i h th ng nh .

ễ ể ễ ặ + D hi u, d cài đ t

- Nh

ượ ể c đi m

ả ạ ữ ệ ợ i thu t KNN thích h p cho vi c phân lo i d li u ch gi

ậ ả ữ ệ

ừ ữ ệ ạ ộ ả ả ị ệ ậ ứ ả + Gi i thu t này ị ể không có kh năng phân tích d li u đ tìm ra các thông tin có giá tr . Trong quá ầ d li u c n xác đ nh trình KNN ho t đ ng, nó ph i tính toán "kho ng cách" t

Nhóm 5 9

ườ ạ ễ GVHD: Nguy n M nh C ng

ậ ấ

ấ ệ t c các d li u trong t p hu n luy n (training set) ==> N u t p hu n ạ ủ ớ ế ậ ẽ ấ ữ ệ ẽ ươ ề ờ ạ ế ấ ả lo i đ n t ệ luy n quá l n, đi u đó s làm cho th i gian ch y c a ch ng trình s r t lâu.

ọ ụ 2.4. Ví d minh h a

ờ ẽ ủ ả Bây gi ta s đi vào chi ti t cách th c ho t đ ng c a gi

ạ ộ ệ

ứ ấ ộ ớ ườ c thu c l p nào. Ng

ậ ư

ệ ầ ậ ọ

ữ ệ ế ẽ ư ẽ ố ớ

ậ ữ ệ ầ ộ ị ậ ế i thu t kNN. ấ ả ả ẩ ị ộ ậ ầ t c các Đ u tiên, chúng ta ph i chu n b m t t p hu n luy n(training set) mà t ẽ ư ữ ệ ề ế ướ ượ i dùng s đ a vào c đ d li u trong t p đó đ u bi t tr ớ ấ ữ ệ ẽ ộ ớ ế ượ ộ ữ ệ t c thu c l p nào. KNN s so sánh d li u đó v i t t đ m t d li u ch a bi ữ ả ữ ệ ấ ố ấ k d li u g n gi ng nh t. Trong k d c d li u trong t p hu n luy n và ch n ra ớ ệ ế li u đó, kNN s xem xét xem l p nào là l p chi m đa s > và s đ a ra k t ạ ậ ằ lu n r ng t p d li u c n xác đ nh thu c lo i đó.

ụ ượ ủ ả ố Ví d đ c tham kh o trong cu n “Machine learning in action” c a Petter

Harington.

ạ ộ ộ ộ

ẽ ả ể ạ ằ ạ ị

c xác đ nh b ng cách đ m s l Ở ệ ố ượ ặ

ẽ ượ ng n hôn trong phim. ậ ứ ệ ộ Ta s đi phân lo i xem m t b phim thu c th lo i phim hành đ ng hay ế ố ượ ng ấ ộ ậ đây, chúng ta đã m t t p hu n ụ ng cú đá, n hôn trong ế ố ượ t s l

ả ạ phim tình c m. Vi c phân lo i phim s đ ụ cú đá ho c s l luy n(training set), t p đó ch a m t s phim đã bi ượ phim đó, và lo i phim đ ộ ố c cho trong b ng sau:

ố ượ S l S l Lo i phim

ố ượ ng cú đá 3 2 ụ ng n hôn 104 100 ạ Tình c mả Tình c mả

Tên phim California Man He isn't really into dudes Beautiful Woman Kevin Longblade Robo Slayer 3000 Amped II Anh 1 101 99 98 18 81 10 5 2 90 Tình c mả Hành đ ngộ Hành đ ngộ Hành đ ngộ ???

ế ượ ố ượ ụ ủ ụ ệ c s l ng n hôn trong phim. Nhi m v c a ta ở

ng cú đá, s l ộ Ta đã bi t đ ị đây là xác đ nh xem phim ố ượ ể ạ ? thu c th lo i nào?

ầ ớ ự ố Đ u tiên chúng ta s xác đ nh xem s gi ng nhau c a phim “Anh” v i các

ẽ ể ị ượ ề ủ c đi u đó, ta s s d ng ẽ ử ụ Euclidean distance. ư ế phim khác nh th nào. Đ làm đ

ữ ể ả

ụ Euclidean distance là vi c chúng ta tìm kho ng cách gi a hai đi m trong ể P1(x1,y1) và P2(x2,y2) thì Euclidean distance sẽ

ứ ệ không gian, ví d cho 2 đi m ượ c tính theo công th c: đ

Nhóm 5 10

ườ ạ ễ GVHD: Nguy n M nh C ng

d =

ụ ợ

ở ể ỗ ườ ọ ộ ớ ố ượ

ễ ụ ọ ộ ể ọ ộ ể c bi u di n b i m t đi m trong t a đ Oxy v i s l ề ng n hôn là t a đ y. Đi u đó có nghĩa là phim “

ở ẽ ng h p này, chúng ta s coi ng cú đá California He isn't really into dudes” sẽ

ễ ể c bi u di n b i đi m (2, 100), ..

Đ áp d ng trong euclidean distance vào trong tr ẽ ượ m i phim s đ ộ ố ượ là t a đ x và s l ể ể ẽ ượ Man” s đ c bi u di n b i đi m (3, 104); phim “ ở ễ ể ượ đ G iọ d là euclidean distance thì: (cid:0)

(cid:0)

(cid:0) “California Man”: d = =20.5 “He isn't really into dudes”: d= = 18.7 “Beautiful Woman”: d = =19.2 “Kevin Longblade”: d = = 115.3 “Robo Slayer 3000”: d = = 117.4 “Amped II”: d = = 118.9

ượ ả Sau khi tính toán ta đ c b ng:

Tên phim Euclidean distance

California Man 20.5 He isn’t really into dudes 18.7 19.2 Beautiful Woman 115.3 Kevin Longblade 117.4 Robo Slayer 3000 118.9 Amped II

ừ t l p t

ấ ệ ắ

ừ

ầ ề ấ

ẽ ấ ạ

ế ư ị ầ ầ

ế ề ạ ả ể ạ ượ Anh” thu cộ th lo i

ế ớ ớ ừ ư ả phim ch a bi Chúng ta đã có kho ng cách euclidean t i t ng phim trong ế ấ ằ ờ ầ ề ẽ ậ chúng ta s tìm ra k láng gi ng g n nh t b ng cách s p x p t p hu n luy n, gi ả ử ỏ ế ớ ứ ự các phim theo th t s k = 3 thì 3 láng nh đ n l n. Gi euclidean distance t California Man”, “He isn't really into dudes” và gi ng g n nh t, đó là các phim “ ế ậ “Beautiful Woman”. Thu t toán kNN s l y lo i phim nào chi m u th trong ớ ấ ể c xác đ nh l p. Vì 3 các láng gi ng g n nh t đ làm lo i phim cho phim c n đ ể ạ phim tình phim trên đ u là th lo i Tình c m ==> Phim “ c mả .

Nhóm 5 11

ườ ạ ễ GVHD: Nguy n M nh C ng

Nhóm 5 12

ườ ạ ễ GVHD: Nguy n M nh C ng

ệ

ả

ậ

i thu t KNN trên Weka

Ch ổ

ề

ự ươ ng 3: Th c hi n gi 3.1. T ng quan v Weka

ọ cượ Đ i h c Waikato

ế ắ ủ t t ề h c máy ọ đ ề ầ ộ Weka (vi ầ ộ b ph n m m b ngằ Java. Weka là ph n m m t ộ t c a Waikato Environment for Knowledge Analysis) là m t , New Zealand phát tri nể ấ ự phát hành theo Gi y phép công c ng GNU ạ do .

ữ ệ ẩ Theo KDNuggets (2005): Weka là s n ph m khai thác d li u đ ượ ử c s

ề ấ ấ ả ả ệ ụ d ng nhi u nh t và hi u qu nh t năm 2005.

ổ ậ ủ ữ Nh ng tính năng n i b t c a Weka:

(cid:0) ỗ ợ ữ ệ ề ậ ọ H tr nhi u thu t toán máy h c và khai thác d li u.

(cid:0) ượ ổ ứ ạ ồ Đ c t ở ch c theo d ng mã ngu n m .

(cid:0) ộ ậ ớ ườ ử ụ ả Đ c l p v i môi tr ng ( do s d ng máy o java JVM).

(cid:0) ế ệ ễ ạ ự ư ệ D s d ng, ki n trúc d ng th vi n d dàng trong vi c xây d ng

ễ ử ụ ụ ự ứ ệ các ng d ng th c nghi m.

ứ ủ Các ch c năng c a Weka:

Nhóm 5 13

ườ ạ ễ GVHD: Nguy n M nh C ng

ể ệ ứ ủ ẻ ủ Các ch c năng chính c a Weka Explorer th hi n trong các th (tab) c a

màn hình chính, bao g m:ồ

(cid:0) ữ ệ ộ ậ ẻ ở

ề ỉ Preprocess: Cho phép m , đi u ch nh, l u m t t p tin d li u, th này ề ử ư ữ ệ ứ ụ ậ ch a các thu tt toán áp d ng trong ti n x lý d li u.

(cid:0) ạ ữ ệ ặ ồ ấ Classify: Cung c p các mô hình phân lo i d li u ho c h i quy.

(cid:0) ụ ấ Cluster: Cung c p các mô hình gom c m.

(cid:0) ậ ế ợ ổ ế ậ Associate: Khai thác t p ph bi n và lu t k t h p.

(cid:0) ự ậ ấ ọ ợ ữ ộ SelectAttribites: L a ch n các thu c tính thích h p nh t trong 1 t p d

li u.ệ

(cid:0) ể ệ ữ ệ ướ ạ ể ồ i d ng bi u đ . Visualize: Th hi n d li u d

ữ ệ Khai phá d li u:

ử ụ * S d ng th ẻ Preprocess

ở ộ ậ ữ ệ (1) Open file…: M m t t p tin d li u.

ử ữ ệ ế ầ ể ằ ỉ ị ế t. (2) Edit…: Hi n th và ch nh s a d li u b ng tay n u c n thi

ệ ạ ư ậ ỗ ợ ộ ố ị m t s đ nh

ữ ệ ị ầ ạ (3) Save…: L u d li u hi n t i ra t p tin. Weka Explorer h tr ạ d ng trong đó có 2 đ nh d ng chính c n quan tâm là *.arff và *.csv

ụ ề ử ượ ọ ậ ộ ọ c g i là các b l c( thu t toán) (4) Filter: Các tác v ti n x lý đ

Nhóm 5 14

ườ ạ ễ GVHD: Nguy n M nh C ng

ề ộ ượ ọ c ch n: (5) Selected attribute: Thông tin v thu c tính đang đ

ủ ể ộ ạ Numeric: D ng s , ố Nominal:

ạ ữ ệ o Type: Ki u d li u c a thu c tính ( ố ờ ạ D ng r i r c/phi s ).

o Missing: S m u thi u giá tr trên thu c tính đang xét.

ố ẫ ế ộ ị

ị ệ t. ố o Distinct: S giá tr phân bi

o Unique: S m u không có giá tr trùng v i m u khác.

ố ẫ ẫ ớ ị

o B ng th ng kê:

ố ả

 D ng phi s :

ạ ể ệ ấ ủ ầ ỗ ị ị ố Th hi n các giá tr và t n su t c a m i giá tr

ộ ố ạ ượ ể ệ ỏ ị ấ ư ng th ng kê nh giá tr nh nh t,

ẩ ị ố Th hi n m t s đ i l ố ạ  D ng s : ộ ệ ấ ớ l n nh t, giá tr trung bình và đ l ch chu n.

Nhóm 5 15

ườ ạ ễ GVHD: Nguy n M nh C ng

ự

ệ

ậ

3.2. Th c hi n thu t toán KNN trong Weka

ậ ệ ể ự ẵ

ộ ữ ệ ở ệ

ướ ọ ữ ệ ượ ư C:\Program Files\Weka36\data.

ọ ượ ộ ữ ệ ị ư ọ Đ th c hi n thu t toán KNN trên Weka, chúng em ch n b d li u Iris s n có ể ự ậ ể trong Weka đ trình bày. Tr c tiên, đ th c hi n thu t toán, ta m Weka, ch n Explorer, ch n ọ Open file, d li u đ c l u: ể Sau khi ch n đ c b d li u, màn hình hi n th nh sau:

ể ự ệ ọ Đ th c hi n KNN trên Weka, ta ch n tag Classify r i ồ Choose IBk:

Nhóm 5 16

ườ ạ ễ GVHD: Nguy n M nh C ng

ể ọ ố ứ ậ ả ị

ộ ử ổ ệ ư ậ Chúng ta có th ch n s K và xác đ nh công th c tính kho ng cách cho thu t tán ằ b ng cách click đúp vào ô thu t toán m t c a s hi n ra nh sau:

ự ủ ứ ệ ể

ứ ế ị Ngoài ra, chúng ta còn th c hi n ch c năng KnowledgeFlow c a Weka hi n th ki n th c:

Nhóm 5 17

ườ ạ ễ GVHD: Nguy n M nh C ng

ộ ố ế

ả ạ ượ

ệ

ả

ớ ộ ữ ệ

ậ

i thu t KNN trên Weka v i b d li u Iris,

ụ ả ư

ự Sau khi th c hi n áp d ng gi ượ ế c k t qu nh sau: ta thu đ

3.3. M t s k t qu đ t đ

Nhóm 5 18

ườ ạ ễ GVHD: Nguy n M nh C ng

ế ả ớ K t qu v i k=1

Nhóm 5 19

ườ ạ ễ GVHD: Nguy n M nh C ng

ế ả ớ K t qu v i k=2

ế ả ớ K t qu v i k=5

Nhóm 5 20

ườ ạ ễ GVHD: Nguy n M nh C ng

ế

ậ

K t lu n

ả ạ ượ ế ế ế ạ *K t qu đ t đ c và h n ch n u có

ế ả K t qu :

ể ượ ổ ư ộ ố ỹ ữ ệ ề ậ c t ng quan v khai phá d li u cũng nh m t s k thu t khai phá

+ Hi u đ ơ ả c b n.

ể ứ ộ ữ ệ ụ ề ậ

+ Có th ng d ng thu t toán K láng gi ng vào các b d li u khác nhau sau này.

ạ ế ấ ả ứ ắ ế ặ c

ự ế ự ế ơ m c lý thuy t ho c th c hành s ộ ể ể ề nhi u đ hi u sau r ng

ượ ở ứ c th c hành trên th c t ậ ữ ệ ư ậ H n ch : T t c các ki n th c n m đ ự ư ượ qua trên máy tính riêng, ch a đ ỹ ề v thu t toán cũng nh các k thu t khai phá d li u.

ướ ứ *H ng nghiên c u

ể ậ ấ

ơ ộ ậ ề ự ả ậ ệ ứ

ộ ữ ệ ớ ế

ư ể ậ ậ ỹ

ậ ữ ệ ứ ể ụ ụ ụ ự ụ ư ế ệ

Trong quá trình tìm hi u và th c hành, chúng em nh n th y thu t toán Kláng ễ ử ụ ậ ụ gi ng là m t thu t toán đ n gi n, d s d ng. Tuy nhiên, vi c ng d ng thu t ẽ ế ụ ạ toán này trên các b d li u l n còn khá h n ch . Vì v y, chúng em s ti p t c ề tìm hi u các k thu t cũng nh thu t toán khai phá d li u đ có thêm nhi u ự ứ ki n th c ph c v công vi c cũng nh áp d ng vào các ng d ng t xây d ng sau này.

Nhóm 5 21

ườ ạ ễ GVHD: Nguy n M nh C ng