Luận văn: Khai mỏ dữ liệu và khám phá tri thức
337 1
Tải về máy để xem đầy đủ hơn, bản xem trước là bản PDF
Tags: #luận án#luận văn#đồ án#tiểu luận
Mô tả chi tiết
1. Mở đầu
Sự bùng nổ thông tin ngày càng lan rộng và nhanh chóng, bên cạnh dữ liệu ngày càng gia tăng về số lượng. Các nhà khoa học ñã nghiên cứu về khả năng sử dụng những dữ liệu ấy ñể phục vụ nhu cầu kinh doanh, học tập và nghiên cứu. Việc khai thác dữ liệu dựa trên những dữ liệu ñã tồn tại ñược gọi là khai phá dữ liệu (Data mining). Quá trình khai phá dữ liệu là bước ngoặc quan trọng cho quá trình khám phá tri thức từ dữ liệu (Knowledge Discovery in Databases).
2. Nội dung
2.1 Tổng quan
Ðặt vấn đề
Lịch sử giải quyết vấn đề
Phạm vi của đề tài
Phương pháp nghiên cứu
2.2 Cơ sở lý thuyết
Khái niệm về khai phá dữ liệu
Các khái niệm cơ bản
Thu thập và tiền xử lý dữ liệu
Một số kỹ thuật khai phá dữ liệu
2.3 Nội dung nghiên cứu
Nghiên cứu về phần mềm khai phá dữ liệu
Chương trình ứng dụng
3. Kết luận
Luận văn tập trung nghiên cứu các quá trình khai phá dữ liệu từ dữ liệu thô ban đầu đến dữ liệu đã qua xử lý và phục vụ cho quá trình khám phá tri thức. Qua việc nghiên cứu các phương pháp và các giải thuật khai phá dữ liệu, luận văn cho thấy được sự hữu ích của dữ liệu phục vụ cho quá trình kinh doanh, nghiên cứu và học tập
4. Tài liệu tham khảo
Dương Văn Hiếu. Khai khoáng dữ liệu. Khoa Công nghệ thông tin – đại học Cần Thơ.
Nguyễn Hoàng Tú Oanh. Bài giảng Khai phá dữ liệu và ứng dụng. đại học Khoa học Tự nhiên – ðại học Quốc gia Thành phố Hồ Chí Minh
Nguyễn Nhật Quang. Bài giảng Khai phá dữ liệu. Viện Công nghệ thông tin và truyền thông - ðại học Bách khoa Hà Nội. Năm học 2010-2011
Nội dung
LU N V ĂN T T NGHI P ð I HC KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Sinh viên th c hi n: Cán b h ư ng d n: H và tên: Quách Luyl ða Ths. D ương V ăn Hi u MSSV: 0751010009 L p: ð i hc Tin h c 2 C n Th ơ, 2011 TRƯ NG ðI H C TÂY ðÔ KHOA K THU T CÔNG NGH LU N V ĂN T T NGHI P ð I HC KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Sinh viên th c hi n Cán b h ư ng d n H và tên: Quách Luyl ða Ths. D ương V ăn Hi u MSSV: 0751010009 L p: ð i hc Tin h c 2 Cán b ph n bi n H c hàm, h c v , h và tên cán b ph n bi n Lu n v ăn ñư c bo v t i: Hi ñ ng ch m lu n v ăn t t nghi p B môn …….. …………………… .. ..…..Khoa K Thu t Công Ngh , Tr ư ng ði hc Tây ðô vào ngày .... tháng ..... n ăm …. Mã s ñ tài: Có th tìm hi u lu n v ăn t i: • Th ư vi n: Tr ư ng ði hc Tây ðô. • Website: TR ƯNG ðI H C TÂY ðÔ KHOA K THU T CÔNG NGH L I CÁM ƠN “ð i kh p th gian không ai t t b ng M Gánh n ng cu c ñ i không ai kh b ng Cha N ư c bi n mênh mông không ñong ñy tình M Mây tr i l ng l ng không ph kín công Cha” Khuyt danh Vi t Nam ð i kh p th gian không ai t t nh ư m , ch ăm lo cu c s ng cho con không ai b ng cha, gánh n ng y cha m không nói ra, nh ưng tôi có th c m nh n và bi t ñư c qua mái tóc b c c a m , nh ng gi t m hôi và làn da rám n ng c a cha. T t c nh ng vi c làm c a cha m ch ñ cho gia ñình ñưc sng vui v và h nh phúc, cho anh em tôi ñưc ăn h c nên ng ư i. Gánh n ng y càng gia t ăng và n ng n h ơn trên vai cha và trong m t m khi con b ư c vào ng ư ng c a ñ i h c. V i bao lo l ng t cái ăn, cái m c, vi c h c hành càng làm t ă ng gánh n ng cho cha m . Gánh n ng y không th th y ñư c trong ti ng c ưi ca cha, trong ánh m t và ti ng nói c a m . Tôi xin g i l i cám ơn và k t qu h c t p trong nh ng n ăm tháng h c xa nhà ñ làm món quà dâng t ng lên cha m c a tôi! Tôi xin chân thành cám ơn quý th y cô trong ban giám hi u, các th y cô trong khoa và các th y cô tr !c ti p gi ng d y chúng tôi, và ñã cung c p cho chúng tôi ñưc nh ng ki n th "c, nh ng k # n ăng c n thi t trong cu c s ng và chu yên môn. T ñ ó có th v n d $ng vào trong h c t p và quá trình nghiên c "u. ð c bi t, tôi xin chân thành cám ơn th y D ương V ăn Hi u, m c dù có nhi u khó kh ăn v m t ñ% a lý và công vi c, nh ưng th y ñã t o m i ñ i u ki n ñ hư ng d &n chúng tôi hoàn thành khóa lu n này. Tôi xin chân thành cám ơn! Kho ng th i gian theo h c t i tr ưng, v i nh ng l l &m khi v a b ư c vào môi tr ư ng m i, v i nhi u b n m i. Chính nh ng ng ưi bn cùng ñng hành v i tôi trên b ư c ñư ng ñi h c, v i nh ng lý t ư'ng và tính cách khác nhau. Chính nh ng câu chu y n bu n – vui – gi n – ghét và chính nh ng s ! giúp ñ trong h c t p và công tác, các b n ñã giúp tôi thêm tr ư'ng thành h ơn, trao d i ñư c nhi u ki n th "c h ơn t các b n. Tôi xin chân thành cám ơn! Và l i c m ơn sau cùng, xin chân thành cám ơn các anh ch %, và c ũng là nh ng ng ưi b n, các cô chú nhân viên tr ưng ñã giúp ñ và quan tâm tôi trong su t th i gian theo h c t i tr ưng. Tôi xin chân thành cám ơn! Xin chân thành cám ơ[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 4 MC L C L I CÁM ƠN B NG KÝ HI U VÀ VI T T T Ch ương I : T NG QUAN ............................................ ................................................ 7 I.1. ðT V N ð ................................................... ................................................. 7 I.2. L CH S GI I QUY T V N ð ................................................... ................... 7 I.3. PH M VI C A ð TÀI ............................................... ................................... 10 I.4. PH ƯƠNG PHÁP NGHIÊN C U .................................................. ................... 10 Ch ương II : C Ơ S LÝ THUY T .................................................. ............................ 11 II.1. KHÁI NI M V KHAI PHÁ D LI U.................................................. ........ 11 II.1.1. Khái ni m: ................................................. ............................................... 11 II.1.2. Nhi m v c a khai thác d li u: ................................................. ............... 12 II.1.3. ng d ng c a khai phá d li u: ................................................. ................ 14 II.2. CÁC KHÁI NI M C Ơ B N .................................................. ......................... 15 II.2.1. D li u và ki u d li u: ................................................. ............................ 15 II.2.2. Ch t l ư ng c a d li u: ................................................. ............................ 19 II.3. Thu th p và ti n x lý d li u: ................................................. ........................ 23 II.3.1. T !ng h p d li u:................................................. ..................................... 23 II.3.2. L y m "u: ................................................. .................................................. 2 4 II.3.3. Gi #m b $t thu %c tính: ............................................ ..................................... 25 II.3.4. L &a ch 'n t p thu %c tính con: ........................................ ............................. 26 II.3.5. T (o ra thu %c tính m $i: ................................................. .............................. 27 II.3.6. R )i r (c hóa và nh * phân hóa: ......................................... ............................ 29 II.3.7. Chu y n ñ! i thu %c tính: ............................................ .................................. 30 II.4. M %t s , k - thu t khai phá d li u: ................................................. .................... 30 II.4.1. Phân c m d li u (Cluster analysis): .............................. ........................... 30 II.4.2. H .i quy (Regression): ................................ ............................................... 33 II.4.3. Cây quy /t ñ* nh (Decision tree): ................................ ................................. 37 II.4.4. K – lân c n g 0n nh t: (K Nearest neighbour-KNN) ....................... ............ 44 II.4.5. Gi #i thu t di tru y n: ................................................. ................................. 46 II.4.6. M (ng neuron nhân t (o (Neural networks):............................... .................. 50 II.4.7. Lu t k /t h p (Association rule): .............................. .................................. 57 Ch ương III : N 1I DUNG NGHIÊN C U.................................................. ................. 67 III.1. NGHIÊN C U V PH 2N M M KHAI PHÁ D LI U ............................... 67 III.1.1. Gi $i thi u Tanagra: ......................................... ......................................... 67 III.1.2. Tìm hi u v Tanagra: .......................................... ..................................... 68 III.1.3. ng d ng Tanagra: ........................................ .......................................... 81 III.2. CH ƯƠNG TRÌNH NG D 3NG:................................................ ................... 83 III.2.1. Khai phá d li u b 4ng lu t k /t h p:................................................. ......... 83 III.2.2. Khai phá d li u b 4ng cây quy /t ñ* nh: ................................................ ..... 93 KT LU 5N VÀ KI N NGH PH 3 L 3C Ph lc I: ðo kho #ng cách gi a 2 ñ,i tư ng Ph lc II: Thu t gi #i Heuristic Ph lc III: H ư$ng d "n s d ng ch ương trình khai phá lu t k /t h p Ph lc IV: H ư$ng d "n s d ng ch ương trình khai phá cây quy /t ñ* nh TÀI LI U THAM KH [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 5 B NG KÝ HI U VÀ VI T T T STT T 6 VI T T T TING ANH NGH ĨA TI NG VI T 01 ANN Artifical neural network M (ng th 0n kinh nhân t (o 02 AND, DNA Acid DeoxyriboNucleic Ph 0n t nucleotic a xít 03 GA Genetic Algorithm Gi #i thu t di truy n 04 GUI Graphical user interface Giao din ñ. h'a ng ư)i dùng 05 Item Item Món hàng, m c,.. 06 Itemset Itemset T p các m c, các hàng,… 07 KNN K Nearest neighbour K-lân c n g 0n nh t 08 KDD Knowledge Discovery in Databases Khám phá tri th8c t 9 d li u 09 RAM Ram memory B % nh $ ram 10 XML Extensible Markup Language Ngôn ng ñ ánh d u m : r %ng 11 web website, web page Trang [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 6 TÓM T T S & bùng n ! thông tin ngày càng lan r %ng và nhanh chóng, bên c (nh d li u ngày càng gia t ăng v s , l ư ng. Các nhà khoa h 'c ñã nghiên c 8u v kh # n ăng s d ng nh ng d li u y ñ ph c v nhu c 0u kinh doanh, h 'c t p và nghiên c 8 u. Vi c khai thác d li u d &a trên nh ng d li u ñã t .n t (i ñư c g'i là khai phá d li u (Data mining). Quá trình khai phá d li u là b ư$c ngo <c quan tr 'ng cho quá trình khám phá tri th 8c t 9 d li u (Knowledge Discovery in Databases). D &a trên d li u v khai phá d li u và khám phá tri th 8c t 9 d li u v ăn b #n (text mining), lu n v ăn ñi sâu vào vi c tìm hi u v quá trình khai phá d li u bao g .m: ti n x lý d li u, các ph ương pháp khai phá d li u làm n n t #n, ch ươ ng trình khai phá d li u, l p trình x lý 1 s , thu t toán c ơ b #n c a ph ương pháp khai phá d li u b 4ng lu t k /t h p và cây quy /t ñ* nh,.. Tuy nhiên, ñ tài ch ưa ñi khai thác ñư c h/t các khía c (nh c a khai phá d li u t 9 hình #nh (Image mining), web (web mining),…Các ph ương pháp khai phá d li u khác. ABSTRACT The explosion of information becomes more widely an d quickly, besides increasing the data quantity. Scientists have been stud ying the possibility of using that data to serve the needs of business, learning and research activities. Mining based on historical data is called data mining. The data mining process is an very important landmark for the process of discovering k nowledge from data. In this stud y, we focus on understanding the data m ining process including data preprocessing, common data mining techniques, data-mining programs. And, implementing the basic methods of data mining such as association rule and decision tree, … However, the topic is not going to exploit every as pect of data-mining from image (Image mining), web (web mining), ... The dat a-mining methods [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 7 Chương I : T NG QUAN I.1. ð T V N ð Ngày nay, công ngh thông tin ñã tr : thành m %t trong nh ng ñ%ng l &c quan tr 'ng c a s & phát tri n. V $i kh # n ăng s , hóa m 'i thông tin (s ,, ñ. th *, v ăn b #n, hình #nh, âm thanh, ti /ng nói,…), máy tính ñã tr : thành m %t công c thông minh, nó ñư c s d ng ñ x lý thông tin v $i nhi u d (ng thông tin thu %c nhi u l ĩnh v &c khác nhau trong ñ)i s,ng nh ư: kinh doanh, y h 'c,… Bên c (nh ñó, cùng v $i s & phát tri n c a công ngh l ưu tr d li u ph c v trong công vi c l ưu tr các thông tin liên quan ñ/n nhi u m <t c a cu %c s ,ng: kinh doanh, buôn bán, … ñã góp ph 0n c #i thi n cu %c s ,ng và làm gi #m b $t ñi vi c l ưu tr thông tin d &a trên v ăn b #n. ð ó chính là ti n ñ cho s & ra ñ)i ca n n kinh t / m $i – n n kinh t / s , ( hay có th g 'i là n n kinh t / tri th 8c, n n kinh t / d &a trên tri th 8c). N n kinh t / ñ y ñ ã và ñang làm cho s & phát tri n thông tin l ưu tr ngày càng nhi u, và kh # n ăng linh ho (t c a các ph 0n m m ph #i ñ# m ñươ ng nhi u công vi c trong vi c l &a ch 'n thông tin. Và trong nh ng n ăm 1980, m %t s , nhà nghiên c 8u ñã ñư a m %t s , k - thu t nh 4m gi #i qu y /t các v n ñ trên, và ñư c g'i là k - thu t khai phá d li u (data mining). Các k - thu t khai phá d li u ñã ñư c các công ty kinh doanh các s #n ph >m liên quan ñ/n thông tin ñã 8ng d ng nh ư: - Duy t web, tìm ki /m các thông tin trên Google, Google luôn ñưa ra các g i ý, có l ? b (n s ? ngh ĩ: nó ñã ñ' c ñư c nh ng su y ngh ĩ c a mình! Mà ña ph 0n các g i ý ñ y g 0n nh ư là các thông tin mà b (n c 0n tìm ki /m. Vì sao Google bi /t mình c 0n tìm thông tin ñ y? - Facebook, nh @c ñ/ n Facebook b (n s ? ngh ĩ ñ/ n m %t c %ng ñ.ng v $i s , l ư ng thông tin cá nhân ñư c lưu tr v $i s , l ư ng l $n, ph #i nói là r t l $n. Khi b (n mu ,n k /t b (n trên c %ng ñ.ng y, Facebook luôn ñưa ra nh ng g i ý v nh ng ng ư)i b(n cho b (n k /t b (n. Và nh ng ng ư)i b(n y g 0n nh ư b (n ñã quen bi /t ngoài cu %c s ,ng ñ)i th ư)ng. B (n ngh ĩ t (i sao nó có th làm nh ư v y? - M%t ví d khác, ñó là vi c tìm và mua 1 quy n sách trên c a hàng sách tr &c tuy /n kh !ng l . Amazon. Khi l &a ch 'n m %t quy n sách, nó luôn ñưa ra cho b (n các l &a ch 'n v nh ng quy /n sách mà 90% là b (n c 0n mua. V y t (i sao nó hi u b (n nhi u nh ư th /? Và câu h Ai cu ,i cùng, vi c x lý thông tin c a nó ra sao? T t c # nh ng câu h A i ñ y là m %t 8ng d ng c th c a khai phá d li u và khám phá tri th 8c. V y khai phá d li u là gì? I.2. L CH S GI I QUY T V N ð “ Data mining là quá trình th ăm dò, l &a ch 'n và mô hình hóa kh ,i l ư ng l $ n d li u ñ tìm ra nh ng quy lu t ho <c các m ,i quan h ch ưa bi /t ñ0 u tiên v $i m c ñích là ñ có ñư c k/t qu # rõ ràng và h u ích cho các ch s : h u c a c ơ s : d li u.”[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 8 Qua quá trình phát tri n, ñ*nh ngh ĩa v khai phá d li u ngày càng ñư c m: r % ng, và d 0n d 0n hoàn thi n: - Khai phá d li u là quá trình khám phá thông tin h u d ng trong các kho d li u kh !ng l . m %t cách t & ñ% ng. Các k - thu t khai phá d li u ñư c tri n khai d & a trên các c ơ s : d li u l $n nh 4m tìm ki /m các m "u hay các quy lu t (pattern) m $i và h u d ng mà ch ưa t 9ng ñư c bi/t tr ư$c ñó. Ví d : “Nh ng sinh viên h 'c gi Ai các môn Toán r )i r (c, L p trình, C u trúc d li u và C ơ s : d li u thì s ? h 'c gi Ai môn khai phá d li u” - Khai phá d li u là quá trình tìm ki /m các m "u m $i, nh ng thông tin, tri th 8c có ích, ti m >n và mang tính d & ñ oán trong kh ,i l ư ng d li u l $n. Các k - thu t khai phá d li u c ũng cung c p các kh # n ăng phán ñoán (d & ñ oán) k /t qu # c a các quan sát trong hi n t (i và quá kh 8. Khai phá d li u không ch C khám phá các thông tin h u d ng trong các c ơ s : d li u (databases) hay kho d li u (data respostories) mà còn liên quan ñ/n các l ĩnh v &c truy xu t thông tin (information retrieval). Ví d: S d ng h qu #n tr * c ơ s : d li u ñ tìm ki /m các m "u tin ho <c s d ng các công c tìm ki /m trên Internet ñ tìm ki /m các trang web ho <c thông tin ñư c lưu tr : các trang web c th nào ñó. Data mining là 1 ph 0n hoàn ch Cnh c a l ĩnh v &c khám phá tri th 8c (Knowledge Discovery). Nó là toàn b % quá trình chuy n d li u thô sang thông tin h u d ng. Quá trình này g .m nhi u b ư$c ti n x lý d li u ñ/ n h u x lý k /t qu # c a quá trình khai phá. Các khó kh ăn trong vi c khai thác tri th 8c t 9 d li u: a) Tính qui mô: V $i s & phát tri n trong vi c t (o ra d li u c ũng nh ư thu th p d li u, các t p h p d li u ñu c l ưu tr ngày càng l $n (gigab ytes, terabytes,petabytes) và ngày càng tr : nên thông d ng. Các thu t toán khai phá d li u ph #i có kh # n ăng phân tích ñư c các t p d li u ñó. Nhi u k - thu t khai phá d li u tri n khai các chi /n l ư c nghiên c 8u ñ< c bi t nh 4m qu #n lý các v n ñ trong nghiên c 8u t ăng theo c p Xác ñ* nh nhi m v Xác ñ* nh d li u liên Thu th p và ti n x lý d liu Th ,ng kê tóm t @t D li u tr& c ti /p Gi #i thu t khai phá M "u Hình I-2. Quá trình khai phá d li [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 9 s, nhân. Tính qui mô (scalability) yêu c 0u ph ương pháp cài ñ<t c a c u trúc d li u m $i nh 4m truy xu t ñư c các m >u tin m %t cách hi u qu #. Ví d : Các thu t toán “x lý d li u ngoài b % nh $ (RAM)” (out-of-core) r t c 0 n thi /t khi x lý các t p d li u l $n h ơn dung l ư ng c a b % nh $. Tính qui mô có th ñư c c#i ti /n b 4ng cách s d ng các d li u m "u (samples), s d ng các gi #i thu t song song và phân tán. b) Tính ña thu %c tính: X lý các t p d li u có hàng tr ăm hay hàng nghìn thu %c tính ngày càng tr : nên ph ! bi /n. Trong l ĩnh v &c tin h 'c cho sinh h 'c, d li u v gen có th bao g .m hàng ngàn thu %c tính. Các t p d li u v $i các thành ph 0n d li u theo th )i gian hay còn ñư c g'i là d li u tu 0n t & (temporal/ spatial components) c ũng có xu h ư$ ng có r t nhi u thu %c tính. Ví d : T p d li u ch 8a các thông tin v ñ* a ch t : nhi u khu v &c khác nhau ñư c thu th p l <p ñi l <p l (i nhi u l 0n, s , l ư ng các thu %c tính có th t ăng d 0n theo th )i gian. Các k - thu t phân tích d li u truy n th ,ng ñư c thi /t k / cho d li u có ít thu %c tính không th áp d ng cho tr ư)ng h p d li u có nhi u thu %c tính. c) D li u không thu 0n nh t và ph 8c t (p: Các ph ương pháp phân tích d li u truy n th ,ng áp d ng cho các t p h p d li u ch 8a các thu %c tính có cùng ki u d li u (có th là liên t c hay r )i r (c). Khi vi c s d ng khai phá d li u trong kinh doanh, trong khoa h 'c và trong y h ' c ngày càng t ăng thì c 0n có các k - thu t phân tích d li u có th áp d ng ñư c cho các thu %c tính không thu 0n nh t (heterogeneous attributes). Bên c (nh ñó, c ũ ng ph #i áp d ng ñư c cho các d li u ph 8c t (p. Ví d : Các ki u d li u truy n th ,ng bao g .m: t p h p các trang web l ưu v ăn b #n và liên k /t bán c u trúc, các d li u v DNA trong không gian 3 chi u, d li u v th )i ti /t (nhi t ñ% , áp su t, ñ% > m) t (i nhi u vùng trên th / gi $i. Các k - thu t ñư c phát tri n cho khai phá d li u c 0n ph #i quan tâm ñ/n m ,i quan h trong d li u nh ư: m ,i quan h v nhi t ñ% theo th )i gian, s & liên thông gi a các ñ. th *, quan h gi a các thành ph 0n trong d li u bán c u trúc và XML. d) S: h u và phân b , d li u: Có khi d li u c 0n ñư c phân tích ñư c lưu tr : nhi u n ơi khác nhau và ñư c s: h u b :i nhi u c ơ quan khác nhau. Các khó kh ăn này ñòi h Ai ph #i phát tri n các k - thu t khai phá d li u theo d (ng phân tán. V n ñ c0n quan tâm là “làm sao h (n ch / l ưu l ư ng truy n t #i d li u khi th &c hi n các thu t toán phân tán?”, “làm sao h p nh t d li u t 9 các ngu .n g ,c khác nhau m %t cách hi u qu # nh t?”, “làm sao ñ#m b #o tính an toàn và b #o m t?”,… e) Vi c phân tích d li u không theo cách truy n th ,ng: Cách ti /p c n d li u theo ph ương pháp th ,ng kê truy n th ,ng d &a trên cách ñ<t gi # thuy /t và ki m tra gi # thuy /t c 0n r t nhi u công s 8c ñ ki m tra các gi # thu y /t. Các công vi c phân tích d li u hi n t (i ñòi h Ai ph #i ñ< t và ki m tra hàng nghìn gi # ñ* nh m %t cách tu 0n t &. Quá trình phát tri n các k - thu t khai phá d li u ñã ñư c thúc ñ>y b :i s & mong ñ i m %t quá trình ñ<t và ki m tra gi # ñ* nh m %t cách hoàn toàn t & ñ% ng. H ơn n a, d li u ñư c phân tích trong khai phá d [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 10 liu là d li u ng "u nhiên nên các ph ương pháp phân tích truy n th ,ng không th áp d ng cho các t p d li u ph 8c t (p và mang tính ng "u nhiên. I.3. PH M VI C A ð TÀI ð tài ñi sâu nghiên c 8u v quá trình khai phá d li u và khám phá tri th 8c t 9 d li u. Qua vi c nghiên c 8u có th tìm hi u thêm v các k - thu t c ơ b #n trong vi c ti n x lý d li u, các k - thu t khai phá d li u c ơ b #n và t 9 ñ ó có ñư c nh ng ki /n th 8c trong vi c tìm hi u m %t công c khai phá d li u, xây d &ng demo khai phá d li u d &a trên m %t s , thu t toán c a cây quy /t ñ* nh và lu t k /t h p. T 9 quá trình nghiên c 8u và th &c ti Dn ñ có th th y ñư c các v n ñ thách th 8c trong l ĩnh v &c khai phá d li u. S d ng c ơ s : lý thuy /t ñã nghiên c 8u ñ cài ñ<t chu ơng trình sinh lu t k /t h p và cây quy /t ñ* nh là 2 k - thu t c ơ b #n c a quá trình khai phá d li u. I.4. PH ƯƠ NG PHÁP NGHIÊN C U D &a trên vi c tìm hi u các t ư li u trong l ĩnh v &c khai phá d li u, t 9 ñ ó rút ra ñư c nh ng k /t qu # c a quá trình ti n x lý d li u, m %t s , k - thu t khai phá d li u c ơ b #n cùng v $i các thu t toán c a nó. ð có ñư c nh ng hi u bi /t v quá trình khai phá d li u và khám phá tri th 8c. D &a trên quá trình tìm hi u v khai phá d li u, ti /p c n m %t công c khai phá d li u, ñ ch 8ng minh cho các thu t toán và gi #i thu t ñ ã nghiên c 8u. T !ng h p các d li u ñã tìm hi u, minh h 'a m %t thu t toán c ơ b #n trong vi c khai phá d li u b 4ng cây qu y /t ñ* nh và lu t k /t h p b 4ng demo c th . Demo s d ng ngôn ng l p trình Microsoft Visual Basic 2008 ñ xây d &ng các thu t toá[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 11 Chương II : C Ơ S LÝ THUY T II.1. KHÁI NI M V KHAI PHÁ D LI U II.1.1. Khái ni m: Khai phá d li u (Data mining) là m %t m %t b ư$ c trong quá trình khám phá tri th 8c trong c ơ s : d li u (Knowledge Discovery in Databases – KDD). Hình II-1. Quá trình khám phá tri th c trong c ơ s d li u T (i h %i ngh * qu ,c t / l 0n th 8 nh t v Khám phá tri th 8c và Khai phá d li u (Knowledge Discovery and Data mining, ñư c t! ch 8c : Motreal vào n ăm 1995, Usama Fayaad ñã ñư a ra khái ni m chính th 8c v Data mining. Nó ñư c s d ng ñ ch C m %t t p h p các k - thu t phân tích ñư c chia làm nhi u giai ño (n khác nhau, v $i m c tiêu ki /n th 8c tr ư$c ñây ch ưa bi /t s ? ñư c su y lu n t 9 kho d li u kh !ng l ., mà d ư)ng nh ư không có b t c 8 m %t quy lu t ho <c m ,i quan h rõ ràng nào. Khi thu t ng “Data mining” t 9 t 9 ñư c hình thành, nó ñã tr : thành ki /n th 8c dành cho vi c suy lu n. ði u này h /t s 8c h u ích vì ñã bác b A nh ng khía c ( nh – m c ñích cu ,i cùng c a khai khoáng d li u còn m ơ h . tr ư$ c ñó. M c tiêu c a khai khoáng d li u là thu ñư c k/t qu # có th ñ o b 4ng m 8c ñ% phù h p c a d li u cho các ch s : h u c ơ s : d li u–kinh doanh ñư c thu n l i. Khai phá d li u (Data mining) là m %t quá trình khám phá thông tin h u d ng trong kho d li u kh !ng l . m %t cách t & ñ% ng. Các k - thu t khai phá d li u ñư c tri n khai trên các c ơ s : d li u l $n nh 4m tìm ki /m các m "u hay các qui lu t (pattern) m $i và h u d ng mà ch ưa t 9ng ñư c bi/t tr ư$c ñó. Ví d : Ng ư)i ta th ư) ng mua ñư)ng khi mua ñ u xanh, nh ng sinh viên h 'c gi Ai các môn Toán r ) i r (c, l p trình, c u trúc d li u và c ơ s : d li u thì s ? h 'c gi Ai môn khai phá d li u. Các k - thu t khai phá d li u c ũng cung c p kh # n ăng phán ñoán (d & ñ oán) k /t qu # c a các quan sát trong t ương lai d &a vào d li u hi n t (i và quá kh 8. Khai phá d li u không ch C là khám phá các thông tin h u d ng trong các c ơ s : d li u (databases) hay kho d li u (data repositories) mà còn bao g .m các công vi c liên quan ñ/n l ĩnh v &c truy xu t thông tin (information retrieval). Theo s ơ ñ. Quá trình khám phá tri th 8c trong c ơ s : d li u (Hình II-1), ta có m %t s , khái ni m nh ư sau:[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 12 - Input Data: d li u ñ0 u vào, nó có th ñư c lưu tr v $i d ư$i nhi u ñ*nh d (ng khác nhau (file text, file b #ng tính, các b #n quan h ) và ñư c lưu tr trong kho d li u t p trung ho <c phân tán nhi u n ơi khác nhau. - Data Preprocessing: Quá trình ti n x lý d li u bao g .m phân rã (puse) d li u t 9 nhi u ngu .n d li u khác nhau, làm s (ch (clean) d li u b 4ng cách lo (i b A nhi Du và d li u trùng nhau, l &a ch 'n các m "u tin (record) và các ñ<c tính (feature) có liên quan ñ/n quá trình khai thác (mine) d li u. Trong th &c t /, d li u có th ñư c thu nh p và l ưu tr b 4ng nhi u cách khác nhau nên quá trình ti n x lý d li u là m %t quá trình h /t s 8c quan tr 'ng, khá n <ng nh 'c và tiêu t ,n nhi u th )i gian c ũng nh ư công s 8c. - Postproccessing: H u x lý k /t qu # là quá trình lo (i b A các k /t qu # không phù h p hay l &a ch 'n các k /t qu # phù h p v $i các công vi c và nhu c 0u th &c t /. Các k /t qu # sau b ư$c h u x lý s ? ñư c s d ng cho các h th ,ng h E tr ra quy /t ñ* nh (Decision Support System). II.1.2. Nhim v c a khai thác d li u: Khai phá d li u có 2 nhi m v l $n là d & ñ oán và mô t #: II.1.2.1. Nhi m v d & ñ oán: M c ñích c a nhi m v d & ñ oán là d & ñ oán giá tr * c a m %t thu %c tính c th d & a trên giá tr * c a các thu %c tính khác. Thu %c tính ñư c d& ñ oán ñư c g'i là thu %c tính m c tiêu (target attributed) hay thu %c tính ph thu %c (dependent variables/ attributed), thu %c tính dùng ñ t(o d & ñ oán g 'i là thu %c tính mô t # hay thu %c tính ñ%c l p (explanatory/ Indepent variables). Ví d : ð qu y /t ñ* nh vi c c p h 'c b !ng cho sinh viên ñ(i h 'c và sau ñ(i h ' c, ng ư)i ta có th d &a vào r t nhi u y /u t , c ũng nh ư tiêu chí khác nhau. M %t trong nh ng tiêu chí ñó là kh # n ăng thành công trong h 'c t p c a ng ư)i s? ñư c c p h 'c b !ng. Làm th / nào ñ ư$ c lư ng ñư c kh # n ăng h 'c t p c a các 8ng viên xin h 'c b !ng? Ng ư)i/ t! ch 8c c p h 'c b !ng có th s d ng các thông tin v sinh viên nh ư: gi $i tính, ñ% tu !i, hoàn c #nh gia ñình, tình tr (ng hôn nhân, ngh nghi p. II.1.2.2. Nhi m v mô t #: M c ñích c a nhi m v mô t # là l y ra t 9 các m "u (pattern) mang tính mô t # nh ư: s & t ươ ng quan (correlation), xu h ư$ng (trend), nhóm (cluster), ñư)ng di chuy n (trajectory) và ngo (i l . Các m "u này nói lên m ,i quan h gi a d li u. Nhi m v c a ph 0n này th ư)ng là gi #i thích v m <t b #n ch t và th ư)ng yêu c 0u các k - thu t h u x lý (postproccessing) nh 4m xác nh n (validate) và gi #i thích (explain) các k /t qu #. II.1.2.3. Nhi m v tr 'ng tâm c a khai phá d li u: Nhi m v tr 'ng tâm c a khai báo d li u là: mô hình hóa cho vi c d & báo, phân tích và nhóm các ñ,i tư ng d li u thành t 9ng nhóm d &a trên nh ng thu %c tính c a chúng, phân tích và ñưa ra các lu t k /t h p d &a trên các d li u hi n t (i, phân tích và phát hi n các tr ư)ng h p ngo (i l . B ,n nhi m v y có th ñư c mô t # ng @n g 'n nh ư sau:[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 13 a) Mô hình hóa cho vi c d & báo: Nhi m v chính là xây d &ng mô hình cho thu %c tính c 0n ñư c d& ñ oán giá tr * (target variable) nh ư là m %t hàm c a các bi /n ñ% c l p (independent variable) ñư c dùng ñ ñ oán giá tr * cho target variable. Có hai ki u mô hình d & báo (predictive modeling), ñó là: phân l $p d li u (classification analysis) và h .i quy (regression). S & phân l $p d li u ñư c s d ng cho các thu %c tính target có giá tr * r )i r (c. S & h .i quy ñư c s d ng cho các thu %c tính target có giá tr * liên t c. Ví d 1: D & ñ oán m %t ng ư)i dùng Internet s ? mua hàng tr &c tuy /n hay không thì ph #i s d ng ph ương pháp phân l $p vì giá tr * c a thu %c tính target r )i r ( c (“mua” và “không”). Ví d 2: D & ñ oán giá c ! phi /u trong t ương lai thì ph #i s d ng ph ương pháp regession vì giá tr * c a c ! phi /u là giá tr * liên t c. M c ñích c a c # phân l $p và h .i quy là tìm ra mô hình ñ d& ñ oán giá tr * c a m %t thu %c tính d &a trên các thu %c tính khác sao cho t ,i thi u quá sai khác gi a các d & ñ oán và giá tr * th &c t /. b) Phân tích k /t h p: Phân tích k /t h p dùng ñ khám phá các m "u (pattern) mà các m "u này mô t # m %t cách m (nh m ? các m ,i quan h gi a các ñ<c ñi m c a d li u. Các m "u qui lu t ñư c khám phá thông th ư)ng ñư c biu di Dn b 4ng lu t k /t h p. B :i vì kích th ư$c c a không gian tìm ki /m t ăng lên theo c p s , nhân nên m c ñích chính c a ph ương pháp phân tích k /t h p là k /t xu t các m "u có ý ngh ĩa b 4ng cách làm hi u qu # hay nói cách khác là ph #i “lo (i b A các lu t có giá tr * s d ng ít”. Ví d: Xét các giao d *ch t (i m %t c a hàng nh ư b #ng bên d ư$i: Hình II-2. B n nhi m v tr ng tâm c a khai phá d li [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 14 Hình II-3. M t s giao d ch t i c a hàng Phân tích l $p d li u có th ñư c dùng ñ phân tích và tìm các m <t hàng ñư c mua cùng v $i nhau ñ “b , trí các m <t hàng sao cho khách hàng mua hàng thu n ti n nh t”. c) Phân tích nhóm: Ph ương pháp phân tích nhóm dùng ñ tìm các nhóm (groups) c a các giá tr * quan sát ñư c (observations) có liên quan ñ/n nhau. Các giá tr * quan sát cùng m %t nhóm ch @c ch @n s ? gi ,ng nhau nhi u h ơn so v $i các giá tr * : các nhóm khác nhau. Ví d: phân nhóm khách hàng ñ tìm ra các khách hàng có cùng s : thích mua s @m. d) Phát hi n ngo (i l : Phát hi n các ngo (i l là tìm các quan sát mà chúng khác r t nhi u so v $i các giá tr * khác. Các giá tr * khác bi t so v $i các giá tr * khác ñư c g'i là ngo (i l (anomaly, outlier). Ví d: ng d ng ph ương pháp phát hi n ngo (i l ñ tìm các giao d *ch “b t th ư) ng” trong l ĩnh v &c ngân hàng nh ư: r a ti n, gian l n khác trong giao d *ch. II.1.3. ng d ng c a khai phá d li u: T 9 khi ra ñ)i, khai phá d li u ñư c 8ng d ng r %ng rãi, sau ñây là m %t s , 8 ng d ng c th : a) Thiên v ăn h 'c: Xác ñ*nh v * trí và h ư$ng di chuy n c a các chòm sao, các hành tinh trong h m <t tr )i d &a trên nh ng d li u v h ư$ ng di chuy n, l *ch s phát tri n c a nó,… b) Phát hi n gian l n: D &a trên nh ng doanh thu, tài kho #n ph #i thu, thu th p nh ng d li u hi u qu # biên c a biên ch / gian l n, ki m toán t & ñ% ng ho <c các k - thu t ñ phát hi n gian l n, s d ng d li u phân tích k /t qu # ñ ki m soát biên ch / phòng ng 9a gian l n,… c) Qu #n lý quan h bán hàng: L ưu tr thông tin khách hàng, phân lo (i khách hàng, các thông tin mua hàng,…t 9 ñ ó ñư a ra các chi /n l ư c, ph ương pháp kinh doanh m $i nh 4m m c ñích: - Khách hàng có l i và nh ng ñ<c ñi m nào làm cho h ' nh ư v [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 15 - Thay ñ!i trong hành vi mua c a khách hàng – ho <c là m %t c ơ h %i hay ñe d ' a ñ, i v$i kinh doanh. - Nhng kho #ng tr ,ng trong danh m c s #n ph >m – cho bi /t qua vi c bán, s , lư ng bán s #n ph >m t ăng, và l <p l (i các l 0n mua hàng,.. - Nhng m <t hàng nào b , trí thu n l i và ti n d ng cho khách hàng,.. d) Ch ăm sóc s 8c kh Ae: L ưu tr thông tin các b nh, các hi n t ư ng, tri u ch 8ng,…t 9 ñ ó, d &a trên nh ng thông tin y ñ phát hi n các b nh và h ư$ng ñi u tr * c th ñ, i v$i các b nh ñã ñư c phát hi n. e) Nông nghi p: Tìm ki /m các thông tin v r 0y nâu, h ư$ng di chuy n, l *ch s phát tri n,… ñ ñư a ra các bi n pháp phòng và tránh r 0y nâu phá ho (i mùa màng. f) Giáo d c: D &a trên nh ng thông tin v t p quán, n ơi c ư trú, ñi u ki n c a xã h %i, tính cách,… ñ ñư a ra nh ng ñ*nh h ư$ng trong vi c l &a ch 'n ngh nghi p cho h 'c sinh v 9a t ,t nghi p ph ! thông ñ có h ư$ng l &a ch 'n ngh nghi p h p lý,… II.2. CÁC KHÁI NI M C Ơ B N II.2.1. D li u và ki u d li u: D li u là ph 0n t ho <c t p h p các ph 0n t mà ta g 'i là tín hi u. Nó ñư c bi u hi n d ư$i các d (ng nh ư hình #nh, âm thanh, màu s @c, mùi v *,…T 9 nh ng tín hi u ñó, chúng ta có s & hi u bi /t v m %t s & v t, hi n t ư ng hay quá trình nào ñó trong th / gi $i khách quan thông qua quá trình nh n th 8c. M %t t p h p d li u có th ñư c xem nh ư m %t t p h p các ñ,i tư ng d li u. Các ñ,i tư ng d li u có th là m "u tin (record), ñi m (point), véc t ơ (vector), m "u (pattern), s & ki n (event), tr ư)ng h p (case), d li u m "u (sample), các th &c th (entity) và các k /t qu # quan sát (observation). ð,i tư ng d li u ñư c mô t # b 4ng các thu %c tính (attribute) mà các thu %c tính này nói lên tính ch t / ñ< c ñi m c ơ b #n c a ñ, i tư ng d li u. Trong ng c #nh khai phá d li u, thu %c tính ñư c g'i v $i nh ng tên khác nhau nh ư: Bi /n (variable), ñ<c tr ưng (characteristis), tr ư)ng d li u (field), tính n ăng (feature), kích th ư$c (dimension). II.2.1.1. Thu %c tính và phép ño: a) ð nh ngh ĩa thu c tính: Thu %c tính là tính ch t c a m %t ñ, i tư ng mà giá tr * c a nó có th khác nhau tùy vào t 9ng ñ,i tư ng c th . Ví d : màu m @t, cân n <ng, chi u cao là thu %c tính c a con ng ư)i, tù y vào t 9 ng ng ư)i s? có giá tr * khác nhau. b) Phép tính ñ ñ o: Phép tính ñ% ñ o là m %t quy t @c (rule) hay m %t hàm (function) dùng ñ k/t h p m %t giá tr * ho <c m %t ký hi u v $i m %t thu %c tính c a ñ, i tư ng, nh 4m làm rõ tính ch t c a ñ, i tư ng. Ví d : Xác ñ*nh cân n <ng b 4ng kg, chi u dài b 4ng mét, gi $i tính là nam hay n , s , gh / trong phòng h 'c là ñ hay thi /u,… c) Ki u c a thu c tính:[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 16 STT Kiu thu %c tính (Attributed type) Mô t# Ví d 1 ð*nh danh (nominal) Giá tr* c a thu %c tính ki u nominal là các tên g 'i hay ñ*nh danh khác nhau, ch C cung c p v 9 a ñ thông tin ñ phân bi t gi ,ng nhau hay khác nhau (=,≠). Mã tCnh, mã nhân viên, gi $i tính,.. 2 Th8 t& (ordinal) Giá tr* thu %c tính ki u ordinal cung c p ñ0y ñ thông tin ñ phân bi t (=,≠) và so sánh theo th 8 t& (<, <=,>,>=). Cao, cao hơn, cao nh t,… 3 Kho#ng cách (interval) ð,i v$i thu %c tính ki u interval, ngoài phân bi t cung c p ñ0 y ñ thông tin ñ phân bi t(=,≠), so sánh (<, <=,>,>=), s & khác nhau (+,-) gi a các giá tr * là h /t s 8c quan tr 'ng. Ngày tháng năm ð% C ho <c ñ% F 4 TF l (ratio) ð,i v$i thu %c tính ki u ratio, s & khác nhau (+,-) và t C l (*,/) gi a các giá tr * là h /t s 8c quan tr 'ng S, l ư ng, ñ% dài, tu !i,… Trong ñó, thu %c tính ki u ñ*nh danh và th 8 t & ñư c coi nh ư thu %c tính dùng ñ phân bi t/ phân lo (i hay thu %c tính ñ*nh danh. Thu %c tính ki u kho #ng cách và t C l ñư c xem nh ư là thu %c tính ñ*nh l ư ng hay thu %c tính ki u s ,. d) Mô t thu c tính b ng t p h p các giá tr : B 4ng cách d &a vào s , l ư ng và giá tr * mà thu %c tính có th có, chúng ta có th chia làm 3 lo (i thu %c tính: - Thu %c tính nh * phân: có 2 giá tr *. Th ư)ng ñư c s d ng v $i thu %c tính ki u nh * phân, ki u yes/no. Ví d : 0 và 1. - Thu %c tính r )i r (c là thu %c tính có m %t t p h p h u h (n các giá tr *, có nhi u h ơn 2 giá tr *. Th ư)ng ñư c s d ng v $i thu %c tính ki u s , nguyên, ki u ký t & , ki u chu Ei ký t &. Ví d : mã t Cnh, s , ñ i n tho (i, gi $i tính, s , ch 8ng minh nhân dân,… - Thu %c tính liên t c: là thu %c tính có m %t t p vô h (n các giá tr * liên t c hay có giá tr * là các s , th &c, có vô h (n các giá tr *. Thu %c tính liên t c th ư)ng ñư c s d ng là thu %c tính ki u s , th &c hay s , có d u ch m ñ%ng. II.2.1.2. Ki u c a t p d li u: Có r t nhi u ki u d li u ñư c s d ng trong l ĩnh v &c khai phá d li u khi có càng nhi u các t p d li u ñư c s d ng ñ phân tích. Ki u d li u có th ñư c chia ra làm 3 nhóm l $n: o D li u m "u tin (record data)[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 17 o D li u trên c ơ s : ñ. th* (graph-based data). o D li u có th 8 t& (ordered data). a) Tính ch t t !ng quát c a các t p d li u: Có 3 tính ch t quan tr 'ng #nh h ư: ng ñ/n vi c l &a ch 'n và s d ng các k - thu t khai phá d li u là: - S, chi u (dimensionality): S , chi u c a 1 t p h p d li u là s , l ư ng các thu %c tính mà các ñ,i tư ng trong t p d li u ñó s : h u. M %t trong nh ng thách th 8c c a l ĩnh v &c khai phá là d li u có nhi u thu %c tính. - S& th ưa th $t (sparsity): ð,i v$i m %t s , t p h p nh ư các thu %c tính không ñ, i x 8ng. H 0u h /t các thu %c tính c a các ñ,i tư ng có giá tr * 0 nh ưng ch C m %t s , tr ư) ng h p không có giá tr * 0. Trong th &c t /, ñây là m %t thu n l i vì ch C c 0n l ưu tr và thao tác trên các giá tr * khác 0. Cách làm này s ? làm gi #m th )i gian tính toán c ũng nh ư b % nh $ lưu tr . - ð% phân gi #i (resolution): Trong khai phá d li u, ñ% phân gi #i d li u th ư) ng : nhi u m 8c ñ% khác nhau và tính ch t c a d li u c ũng khác nhau tùy vào m 8c ñ% phân gi #i. M "u trong d li u th ư)ng ph thu %c nhi u vào m 8c ñ% phân gi #i. Ví d : ð% phân gi #i quá m *n thì m "u s ? b * m ), ñ% phân gi #i quá thô thì m "u s ? m t. b) Chi ti /t v các ki u d li u trong khai phá d li u: D li u d (ng m "u tin: H 0u h /t các tr ư)ng h p d li u c a khai phá d li u là d (ng m "u tin (record data). M Ei m "u tin là m %t ñ, i tư ng d li u bao g .m m %t t p h p các thu %c tính. Các m "u tin có th ñư c lưu trong các t p tin ph Gng (flat files) ho <c l ưu trong các b #ng d li u (table) trong c ơ s : d li u quan h . D li u d (ng m "u tin có th là các b #ng ghi trong c ơ s : , giao d *ch (transaction), ma tr n d li u (data matrix) và ma tr n thu t ng trong v ăn b #n (document – term matrix). b) M a tr n d li u a) D li u m "u [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 18 D li u d &a trên ñ. th *: ð. th* ñư c coi nh ư là 1 công c r t m (nh và r t thu n l i cho vi c bi u di Dn d li u vì nó có th mô t # ñư c m,i quan h gi a các thành phân d li u. Các ñ,i tư ng d li u bi u di Dn b 4ng các nút trên ñ. th * còn m ,i quan h gi a các ñ,i tư ng thì ñư c biu di Dn b 4ng các ñư)ng liên k /t gi a các nút. M ,i quan h gi a các ñ,i tư ng th ư)ng nói lên thông tin quan tr 'ng v d li u. D li u có th 8 t& : Trong m %t s , tr ư) ng h p, các thu %c tính c a d li u m "u tin có các m ,i quan h v m <t th )i gian c ũng nh ư không gian. D li u nh ư v y ñư c g'i là d li u có th 8 t&. D li u có th 8 t& bao g .m: - D li u ñư c s@p x /p liên t c theo th )i gian: ðây là m %t d (ng m : r %ng c a d li u d (ng m "u tin. Không ch C m "u tin và t 9ng thu %c tính c a m "u tin c ũng có s & k /t h p v $i th )i gian (th )i ñi m). Ví d : D li u v giao d *ch c a khách hàng t (i t 9ng th )i ñi m nh ư sau: IDcustomers Items 1 Bread, coke, milk 2 Beer, Bread 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Coke, Diaper, Milk a) Các trang web ñư c liên k /t v $i nhau b) C u trúc ADN Hình II-4. Các ñi tư ng c a d li u d ng m u tin Hình II-5. Các ñi tư ng d li u d a trên ñ [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 19 Hình II-7. B ng d li u giao d ch theo th i gian (ti p theo) - D li u d (ng chu Ei: (sequence data) là m %t t p h p d li u mà nó là m %t chu Ei các th &c th ñơ n l H gi ,ng nh ư 1 chu Ei các con s ,, ký t & hay t 9 khóa. R t gi ,ng v $i ki u d li u theo th )i gian nh ưng không liên quan ñ/n th )i gian (th )i ñ i m). Ví d v thông tin di chuy n c a loài ñ%ng hay th &c v t ñư c biu di Dn nh ư 1 chu Ei nucleotide ñư c g'i là lag gene. Hình II-8. Chu i d li u - Time series data: Là m %t d (ng ñ<c bi t c a d li u d (ng chu Ei, m Ei m "u tin là 1 time series. Nói cách khác, m Ei m "u tin là m %t chu Ei các giá tr * ñ o ñư c t ( i các th )i ñi m. - Spatial data: M %t s , ñ, i tư ng có thu %c tính liên quan ñ/n không gian hay v * trí. Ví d : D li u v th )i ti /t t (i các v * trí khác nhau trên trái ñ t. II.2.2. Cht l ư ng c a d li u: Khai phá d li u th ư)ng s d ng ñư c thu nh p cho nh ng m c ñích khác ho <c cho vi c s d ng trong t ương lai ho <c không rõ 8ng d ng c th . Chính vì v y mà ch t l ư ng d li u là m %t v n ñ c0n quan tâm khi khai thác chi th 8c t 9 d li u. Vì v y, tr ư$c khi s d ng, d li u ph #i ñư c x lý ñ lo (i b A nhi Du, c ũng nh ư lo (i b A d li u trùng nhau và d li u vô ích không th ph c v cho công vi c khai phá d li u hi n t (i. V n ñ ñư c trình bày ti /p theo là v n ñ liên quan ñ/n ch t l ư ng d li u. Hình II-6. Bng d li u giao d ch theo th i [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 20 II.2.2.1. ð% ñ o ch t l ư ng và v n ñ thu th p d li u: Trong cu %c s ,ng không có gì là hoàn h #o, d li u ñư c thu nh p c ũng ñ x lý c ũng g <p nhi u v n ñ khác nhau và không ñ#m b #o ñư c ch t l ư ng c a d li u ph c v cho quá trình khai phá d li u. Các v n ñ có th là: - Giá tr * c a m %t ho <c nhi u thu %c tính c a m %t ho <c ñ, i tư ng có th b * thi /u. - D li u b * trùng l @p nhi u l 0n. Nguyên nhân c a nh ng v n ñ trên có th ñ/ n t 9: - LEi c a con ng ư)i, có th nói ñ/n l Ei c a ng ư)i thu th p d li u hay tác ñ% ng tr &c ti /p ñ/ n d li u. - S& gi $i h (n c a các thi /t b * ñ o, có th do ñơn v * ñ o và kho #ng cách quá chênh l ch. - LEi trong quá trình thu th p d li u. Vì th /, v n ñ liên quan ñ/n ch t l ư ng c a d li u, chúng ta c 0n quan tâm ñ/ n các v n ñ sau: a) LEi ño l ư) ng và thu th p d li u: L Ei c a s & ñ o l ư)ng có th ñ/ n t 9 các thi /t b * hay chính s & tác ñ%ng tr &c ti /p c a con ng ư)i. Nó ñư c sinh ra do quá trình ño l ư) ng. Các l Ei có th x #y ra do nh ng ngu yên nhân sau: - Giá tr * ñư c lưu khác v $i giá tr * th &c. Ví d : N ăng l ư ng ion hóa nguyên t hirô là 13,6 eV, do quá trình ghi chép và l ưu tr trong thi /t b * có th là 13,9eV; 14eV; 13eV;… - Do ph ương pháp ño không phù h p ho <c thi /t b * ñ o hay ñi u ki n ño không phù h p. Ví d : Trong vi c ño hu y /t áp c a b nh nhân, t ư th / ñ o : n 4m ho <c ng .i, s d ng thi /t b * ñ o cánh tay ño : c ! tay ho <c ng ư c l(i, u ,ng cà phê tr ư$ c khi ño,… c ũng #nh h ư:ng ñ/n ch t l ư ng c a m Ei l 0n ño hu y /t áp. - LEi thu th p d li u x #y ra do quá trình thu th p d li u và th ư)ng là b A qua m %t s , ñ, i tư ng d li u hay thu %c tính, thu th p d li u không ñúng. Ví d : Xác ñ*nh b nh s ,t rét c 0n có các thông tin: l ư ng b (ch c 0u trong máu, thay ñ!i d *ch não t y, gi #m canxi trong máu, h ( natri máu, b nh nhân su y th n,…n /u thi /u 1 trong các tri u ch 8ng và các xét nghi m trên thì không th có k /t lu n c th v b nh. b) Nhi Du và d li u b * bóp méo: Nhi Du ñư c hiu là thành ph 0n ng "u nhiên c a l Ei ño l ư)ng d li u. L Ei này có th làm cho d li u b * bi /n d (ng, b * ñư a vào các ñ,i tư ng gi # m (o. L Ei th ư) ng g <p ñ, i v $i các ñ,i tư ng là âm thanh, s , l ư ng d li u quá l $n không th gom nhóm ñư c,…V n ñ nhi Du và d li u b * bóp méo có th do nh ng nguyên nhân: ti /ng .n xung quanh, ph ương pháp hay gi #i thu t x lý nhi Du ch ưa h p lý và làm m t quá nhi u thông tin,…[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 21 Hình II-9. Nhi u trong Time series data c) Tính chính xác, ñ% lch, s & ñ úng ñ@n c a d li u: Trong quá trình th ,ng kê và thí nghi m, ch t l ư ng c a quá trình ño l ư) ng và d li u c a k /t qu # ñư c ño b 4ng tính chính xác (precision) và ñ% lch (bias). - Tính chính xác: Là g 0n k c a k /t qu # ñ o ñư c l<p l (i nhi u l 0n. - ð% lch: Là s & khác nhau v m <t h th ,ng c a nh ng k /t qu # ñ o khi ño cùng m %t ñ( i lư ng. Tính chính xác th ư)ng ñư c ño b 4ng ñ% lch tiêu chu >n (standard deviation) c a m %t t p các giá tr *. ð% lch ñư c ño b 4ng s & khác nhau gi a giá tr * trung bình c a t p h p các giá tr * v $i giá tr * ñ ã bi /t c a l ư ng ñư c ño. Ví d : ð% ñ o c a v t th X sau 5 l 0n ño, có k /t qu # nh ư sau: 1.015;0.99;1.013;1.001;0.986. Giá tr * trung bình là X=1.001, ñ% lch tiêu chu >n b 4ng 0.013096. - S& ñ úng ñ@n: S & g 0n ñúng c a các s , li u ño ñư c v$i giá tr * th &c c a l ư ng ñư c ño. S & ñ úng ñ@n (accuracy) th ư)ng ñư c s d ng ñ mô t # m 8c ñ% ñ o sai. S & ñ úng ñ@n ph thu %c vào tính chính xác và ñ% lch c a phép ño (k /t qu # ñ o). d) Ngo (i l : Là nh ng ñ,i tư ng d li u có nh ng ñ<c ñi m khác xa so v $i h 0u h /t d li u trong cùng 1 nhóm hay ngo (i l là nh ng tr ư)ng h p các ñ,i tư ng d li u có giá tr * c a m %t s , thu %c tính khác xa giá tr * c a cùng thu %c tính c a các ñ,i t ư ng còn l (i trong nhóm. Ví d : Trong cùng 1 loài hoa Iris có ñ% dài ñài hoa, ñ% r % ng ñài hoa, ñ% dài cu ,n hoa, ñ% r%ng cu ,n hoa l 0n lu t có giá tr * trung bình l 0n Hình II-10. D li u g c và d li u b nhi [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 22 lư t là: 5.1, 3.5, 1.4, 0.2; nh ưng xu t hi n m %t bông hoa iris có các s , ñ o t ương 8 ng là: 7.0,3.2,4.7,1.4 và xu t hi n màu khác,… T 9 ñ y có th rút ra k /t lu n r 4ng, ngo (i l # nh h ư:ng r t l $n ñ/ n quá trình phân tích d li u trong khai phá d li u. Ngo (i l c 0n ñư c phát hi n và lo (i b A trong quá trình ti n x lý d li u. e) Giá tr * b * thi /u: Giá tr * b * thi /u do quá trình thu nh p d li u không ñ#m b #o thu th p ñ0 y ñ giá tr * c a t t c # các thu %c tính c a các ñ,i tư ng d li u. L Ei ñó có th do 1 s , nguyên nhân sau: - Do ng ư)i dùng không cung c p d li u không cung c p ñ0 y ñ thông tin. - Do ng ư)i thu th p d li u làm m t thông tin. - Trong 1 s , tr ư) ng h p ñ< c bi t nào ñó mà d li u b * m t ñi m %t ph 0n. Vì v y, d li u b * thi /u ñóng m %t vai trò r t quan tr 'ng trong quá trình phân tích. Vi c x lý d li u có nhi u cách khác nhau, nh ưng m Ei cách ñ u có ưu ñ i m, khuy /t ñi m và phù h p v $i nh ng tình hu ,ng c th khác nhau. Do ñó, c 0 n c >n th n trong vi c l &a ch 'n cách x lý nh 4m tránh #nh h ư:ng ñ/n k /t qu # c a các b ư$c ti /p theo và ñ% chính xác c ũng nh ư hi u qu # c a c # h th ,ng. Sau ñ ây là m %t vài cách x lý cho các tr ư)ng h p c th : Lo (i b A ñ, i tư ng d li u hay thu %c tính: là cách x lý ñơn gi #n và hi u qu # trong tr ư)ng h p d li u b * thi /u giá tr *. T ương 8ng v $i các tr ư)ng h p s ? có bi n pháp x lý sau: - N/u ñ, i tư ng d li u nào thi /u thu %c tính thì lo (i ra kh Ai t p d li u dùng ñ phân tích. - N/u có quá nhi u ñ, i tư ng cùng thi /u giá tr * do m %t thu %c tính nào ñó thì lo (i b A thu %c tính ñó ra kh Ai t p thu %c tính c a ñ, i tư ng d li u. Ư$ c lư ng giá tr * b * thi /u: Trong m %t s , tr ư) ng h p, các giá tr * thi /u có th ñư c ư$ c lư ng t 9 các giá tr * khác ñã có tr ư$c ñó. Không quan tâm ñ/n giá tr * b * thi /u trong su ,t quá trình phân tích: Nhi u h ư$ ng ti /p c n c a khai phá d li u có th b A qua các giá tr * b * thi /u trong lúc phân tích. f) Giá tr * không nh t quán: Ví d : 2 m "u tin có giá tr * “t Cnh thành” gi ,ng nhau nh ưng giá tr * “mã b ưu c c” khác nhau. Có nhi u nguyên nhân d "n ñ/ n d li u không nh t quán. Có th do c ơ s : d li u thi /t k / không t ,t, do ng ư)i cung c p d li u cung c p sai thông tin, do ng ư) i thu nh p nh p d li u sai,…D li u không nh t quán có th ñư c phát hi n và ch Cnh s a k *p th )i. g) D li u b * trùng l @p: D li u trong quá trình thu nh p có th ch 8a nhi u ñ, i tư ng d li u b * trùng l @p. D li u trùng l @p có th do quá trình nh p li u và thu th p d li u không l <p l (i nhi u l 0n. D li u b * trùng l @p c 0n ñư c phát hi n và lo (i b A trong quá trình ti n x lý d li [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 23 II.2.2.2. Các v n ñ liên quan ñ/n 8ng d ng: Ch t l ư ng c a d li u có th ñư c quan sát và ñánh giá : nhi u g ,c ñ% 8 ng d ng khác nhau. Tùy vào 8ng d ng c th mà ch t l ư ng d li u s ? phù h p v $i 8 ng d ng ñó. M %t s , tr ư) ng h p ñòi h Ai d li u ph #i th t t ,t (ch t l ư ng cao) trong khi m %t s , tr ư) ng h p ch p nh n d li u có ch 8a m %t ít sai sót. M %t s , v n ñ c0n quan tâm ñ/n 8ng d ng là: a) Tính phù h p theo th )i gian: Trong m %t s , tr ư) ng h p, d li u ch C có giá tr * s d ng trong m %t kho #ng th )i gian nh t ñ* nh k t 9 khi d li u ñư c thu th p. D li u ñư c thu th p quá lâu có th s ? không còn h u d ng, không còn ph #n ánh ñúng b #n ch t c a s & v t. Ví d : ð i m sàng ñ(i h 'c n ăm 2010 không th áp d ng cho ñi m sàng ñ(i h ' c n ăm 2010. b) Tính liên quan: D li u ph #i ch 8a thông tin h u ích và c 0n thi /t cho 8ng d ng. Ví d : ð xây d &ng mô hình t ư v n vi c ch 'n ngành ngh cho thí sinh thi tuy n sinh ñ(i h 'c. Thông tin v m 8c s ,ng, s : thích, ñi u ki n và hoàn c #nh gia ñ ình c a thí sinh không th t s & c 0n thi /t. Trong khi, thông tin v h 'c l &c, h (nh ki m, s 8c kh Ae,…l (i r t quan tr 'ng. c) Tri th 8c v d li u: M %t cách lý t ư:ng, các t p d li u có ñư c t9 các tài li u mô t # các khía c ( nh khác nhau c a d li u. Ch t l ư ng c a tài li u này s ? giúp ích r t nhi u cho quá trình phân tích d li u. Ki /n th 8c v d li u còn th hi n : vi c nh n bi /t các ñ< c ñi m quan tr 'ng c a d li u nh ư: tính chính xác c a d li u, các ki u thu %c tính, t C l ñ o và ngu .n g ,c c a d li u. II.3. Thu th p và ti n x lý d li u: ð d li u có th 8 ng d ng vào quá trình khai phá d li u, d li u c 0n ñư c thu th p và x lý. Công vi c c a giai ño(n này là l &a ch 'n ñ, i tư ng d li u và thu %c tính cho quá trình phân tích ho <c t (o ra các thu %c tính m $i ho <c thay ñ!i thu %c tính. M c ñích cu ,i cùng c a quá trình này là c #i thi n quá trình phân tích trong khai phá d li u : khía c (nh th )i gian, ti n c a và ch t l ư ng. II.3.1. T ng h p d li u: Là vi c gom 2 hay nhi u ñ, i tư ng d li u l (i v $i nhau, nh 4m m c ñích t (o thành m %t ñ, i tư ng. Ví d : m %t siêu th * có nhi u phòng ban, m Ei phòng ban có quy n truy c p ñ/ n h th ,ng : m %t lãnh v &c riêng c a h th ,ng. M Ei nhân viên : siêu th * s ? làm vi c cho các v ăn phòng c a siêu th *. B 4ng vi c thi /t l p quy n tru y c p cho các phòng c a siêu th * s ? ti /t ki m th )i gian và không gian b % nh $ h ơn vi c thi /t l p quy n riêng cho các nhân viên. T !ng h p d li u s ? ph #i d &a trên các ngu yên t @t sau: - ð, i v$i thu %c tính ki u s ,: l y t !ng ho <c trung bình. - ð, i v$i các thu %c tính không ph #i ki u s ,: có th b A qua ho <c t !ng h p nh ư là môt t p h p các giá tr *. Ư u ñi m c a vi c k /t h p d li u:[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 24 (1) T p h p d li u sau khi k /t h p nh A h ơn ñáng k so v $i t p d li u ban ñ0 u. Dung l ư ng b % nh $ l ưu tr ít h ơn, th )i gian x lý ng @n h ơn, s d ng các thu t toán vét c (n. (2) Có th coi vi c k /t h p d li u nh ư là vi c thay ñ!i giá tr * và thang chia giá tr *. Cung c p góc nhìn d li u : m 8c cao. (3) D li u sau khi k /t h p !n ñ*nh h ơn d li u ñơ n l ? tr ư$ c khi k /t h p. H (n ch / c a vi c k /t h p d li u: Kh # n ăng m t các thông tin hay chi ti /t quan tr 'ng. II.3.2. Ly m u: Th ư)ng ñư c s d ng trong vi c l &a ch 'n t p thu %c tính con dùng ñ phân tích và c ũng là m %t cách làm r t h u d ng trong khai phá d li u. M c ñích chính c a vi c l y m "u là “làm gi #m th )i gian và tài nguyên cho quá trình phân tích d li u”. Nguyên t @t l y m "u hi u qu #: - L y m "u ph #i ñ( i di n cho t p h p d li u. - M"u d li u ph #i có ñ0y ñ các thu %c tính nh ư t p d li u g ,c. - Ph ương pháp l y m "u ph #i ñ# m b #o tính ñ(i di n c a m "u d li u. - K- thu t l y m "u và s , l ư ng m "u ph #i phù h p. Cách ti /p c n khi l y m "u: (1) L y m "u ng "u nhiên (random samling): ðây là cách l y m "u ñơ n gi #n nh t. ð, i v$i cách này, xác su t ñ ch 'n các ph 0n t trong t p h p là nh ư nhau. Có 2 cách bi /n th c a l y m "u ng "u nhiên là: - L y m "u không có s & thay th /: M Ei ph 0n t ch C có th ñư c ch 'n m %t l 0 n du y nh t. Khi m %t ph 0n t ñư c ch 'n thì nó s ? b * lo (i ra kh Ai t p h p và vi c l & a ch 'n m "u ti /p theo s ? áp d ng trên các t p h p các ph 0n t ch ưa ñư c ch 'n. - L y m "u có s & l <p l (i: M %t ph 0n t có th ñư c ch 'n nhi u h ơn m %t l 0n. Khi ch 'n m %t ph 0n t ñ u c ch 'n thì nó s ? không b * lo (i ra kh Ai t p h p và nó s ? có kh # n ăng ñư c ch 'n : l0n ch 'n ti /p theo. (2) ð h(n ch / các hi u 8ng ph ( ñi m y /u) c a ph ương pháp l y m "u, d li u ban ñ0u nên ñư c chia làm nhi u l $p. Vi c ch 'n l y m "u s ? áp d ng cho t 9 ng l $p d li u nên m "u l y v s ? ñ( i di n cho c # t p h p d li u ban ñ0u. L y m "u theo l ũy ti /n (progressive sampling): Trong th &c t /, r t khó xác ñ* nh s , l ư ng m "u c a t 9ng t p d li u. L y m "u theo cách l ũy ti /n là cách l y m "u nh ư sau: - B@t ñ0 u v $i 1 l ư ng m "u nh A. - Tăng d 0n l ư ng m "u cho ñ/n khi nào ñ(t ñư c kích th ư$c phù h p ( ñ l $ n). - D9ng t ăng khi nào ñ% chính xác c a mô hình ñ(t ñ/ n m 8c !n ñ* nh. M t thông tin trong l y m "u: V n ñ l&a ch 'n kích th ư$c c a t p h p m "u r t quan tr 'ng vì nó #nh h ư: ng ñ/n ñ% chính xác c a mô hình sau khi phân tích. Kích th ư$c c a m "u càng l $ n thì k /t qu # phân tích càng g 0n v $i k /t qu # phân tích c a t p d li u g ,c nh ưng ý ngh ĩa c a vi c l y m "u s ? không còn n a. Kích th ư$c c a m "u càng nh [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 25 thì s? d "n ñ/ n m t thông tin và thu ñư c k/t qu # phân tích khác xa so v $i k /t qu # phân tích c a t p d li u g ,c. II.3.3. Gi m b t thu !c tính: Gi #m b $t thu %c tính chính là ñ ch C các k - thu t làm gi #m s , chi u (thu %c tính) c a d li u b 4ng cách t (o ra thu %c tính m $i là t p h p c a các thu %c tính c ũ. Vi c gi #m b $t thu %c tính mang l (i r t nhi u l i ích cho quá trình phân tích d li u. II.3.3.1. Thu n l i: - Các thu t toán trong khai phá d li u s ? làm vi c t ,t h ơn khi áp d ng trên t p d li u có ích thu %c tính. B :i vì, gi #m b $t thu %c tính s ? b A ñ i các thu %c tính kém quan tr 'ng và có th gi #m ñư c nhi Du trong d li u. - Làm cho quá trình bi u di Dn (visualize) d li u d D h ơn. - Gi#m th )i gian và tài nguyên cho vi c phân tích. II.3.3.2. Khó kh ăn: Thu t ng “the curse of dimensionality” dùng ñ ch C hi n t ư ng mà nhi u ki u phân tích d li u tr : nên khó kh ăn h ơn khi s , thu %c tính c a d li u t ăng lên. M %t cách ñ<t bi t, khi t ăng s , l ư ng thu %c tính thì d li u càng tr : nên th ưa th $t trong không gian mà nó chi /m gi . Tùy vào m 8c #nh h ư:ng, nó s ? tác ñ%ng tr &c ti /p ñ/ n các thu t toán c a khai phá d li u. - ð, i v$i quá trình phân l $p d li u (classification) là r t khó kh ăn, vì không ñ ñ, i tư ng d li u cho vi c t (o ra mô hình ñáng tin c y. - ð, i v$i vi c gom nhóm d li u (clustering), m t ñ% và kho #ng cách gi a các ñ,i tư ng tr : nên vô ngh ĩa. Tóm l (i, thu t toán phân l $p d li u và gom nhóm d li u g <p r @c r ,i khi d li u có quá nhi u thu %c tính. a) nh ban ñ0u b) nh m t thông tin c) nh m t thông tin do nhi Du mu ,i tiêu do nhi Du Gause Hình II-11. M t thông tin khi l y m [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 26 II.3.3.3. Các k - thu t ñ( i s, tuy /n tính cho vi c gi #m thu %c tính: Nh 4m làm gi #m b $t các thu %c tính b 4ng cách s d ng k - thu t ñ( i s, tuy /n tính ñ chi /u d li u t 9 không gian nhi u chi u sang không gian có s , chi u ít h ơn. Các k - thu t th ư)ng ñư c s d ng là: Principal Compoment Analysis (PCA): Là k - thu t dùng cho các thu %c tính liên t c. Ngu yên t @t c a cách phân tích này là tìm thu %c tính m $i có tính ch t: - Là t ! h p tuy /n tính c a các thu %c tính g ,c. - Tr&c giao vuông góc v $i nhau. - Gi ñư c lư ng l $n nh t c a s & thay ñ!i d li u. Sigualr Value Descomposition (SVD): Là m %t k - thu t liên quan v $i PCA và th ư)ng ñu c dùng ñ gi #m s , thu %c tính. II.3.4. L" a ch #n t p thu !c tính con: M %t cách khác ñ gi #m b $t s , thu %c tính là s d ng t p thu %c tính con. Cách làm này có th lo (i b A ñư c các thu %c tính d ư th 9a (không s d ng) và các thu %c tính không có ý ngh ĩa hay không có liên quan (không s d ng). Ví d : S d ng thu %c tính ñơn giá mua thì không c 0n s d ng thu %c tính thu / giá tr * gia t ăng, thu %c tính mã s , sinh viên không liên quan ñ/n quá trình d & ñ oán kh # n ăng h 'c t p c a sinh viên. T 9 ñ ó, ñ l&a ch 'n t p thu %c tính con t ,t nh t ñòi h Ai ph #i có m %t cách ti /p c n m %t cách h th ,ng. II.3.4.1. Ti /p c n trong vi c l &a ch 'n thu %c tính con: - Theo d (ng nhúng (embedded aproaches): Vi c l &a ch 'n thu %c tính x #y ra m %t cách t & nhiên nh ư là m %t thành ph 0n c a thu t toán khai phá d li u. Trong su ,t quá trình x lý, thu t toán khai phá d li u s ? quy /t ñ* n thu %c tính nào ñư c dùng, thu %c tính nào s ? b * b A qua. - Ti/p c n theo d (ng l 'c (filter approaches): Thu %c tính s ? ñư c l&a ch 'n tr ư$ c khi ñư c dùng cho quá trình khai phá d li u. Cách l &a ch 'n ñ% c l p v $i các thu t toán khai phá d li u. - Ti/p c n theo d (ng bao l 'c (wrapper approaches): S d ng các thu t toán khai phá d li u nh ư m %t h %p ñen ñ tìm t p thu %c tính con t ,t nh t. II.3.4.2. Qui trình l &a ch 'n thu %c tính con: g .m 4 ph 0n: - M%t giá tr * ñ o l ư) ng cho vi c ñánh giá m %t t p thu %c tính con. Vi c ñánh giá t p con hi n t (i v $i các t p con khác, ñòi h Ai ph #i có m %t ñ% ñ o dùng ñ ñ ánh giá nh 4m xác ñ*nh m 8c ñ% t,t c a các thu %c tính ñ,i v $i m %t công vi c c th trong khai phá d li u. - M%t chi /n l ư t tìm ki /m có kh # n ăng ñi u khi n ñư c vic sinh ra t p thu %c tính con. V m <t ý t ư:ng, vi c l &a ch 'n thu %c tính con là vét h /t t t c # các t p h p có th có. Có th s d ng nhi u chi /n l ư t tìm ki /m khác nhau nh ưng ph #i chú ý ñ/n ñ% ph 8c t (p c a thu t toán và các ràng bu %c khác. - ði u ki n d 9ng là r t c 0n thi /t vì s , l ư ng các t p con là r t l $n và vi c ki m tra t t c # các t p con là không th &c t /. ð i u ki n d 9ng liên quan ñ/n: s , l [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 27 l< p, so sánh k /t qu # ñ ánh giá v $i giá tr * “c 0m canh” (threshold), s , l ư ng các thu %c tính con,… - Kim ñ*nh và xác nh n k /t qu # khi các t p h p con ñư c ch 'n. Ph ương pháp ñơn gi #n là áp d ng thu t toán khai phá d li u trên toàn t p d li u g ,c và trên các t p thu %c tính con. N /u k /t qu # ch (y trên t p h p con các thu %c tính mà t , t h ơn hay ít nh t là g 0n b 4ng v $i ch (y trên t t c # các thu %c tính thì s ? d 9ng vi c tìm thu %c tính con. M %t cách khác dùng ñ xác ñ*nh k /t qu # là s d ng nhi u gi #i thu t l &a ch 'n thu %c tính khác nhau ñ sinh ra các t p thu %c tính con khác nhau. Sau ñó so sánh k /t qu # c a t 9ng gi #i thu t l &a ch 'n. II.3.4.3. Gán tr 'ng l ư ng cho thu %c tính: Là m %t cách làm ñ lo (i b A các thu %c tính kém quan tr 'ng và gi l (i các thu %c tính quan tr 'ng h ơn. Thu %c tính càng quan tr 'ng thì gán tr 'ng s , càng l $n. II.3.5. T$o ra thu !c tính m i: Thu %c tính m $i th ư)ng ñư c t(o d &a trên thu %c tính có s In. M %t t p h p các thu %c tính m $i có th ch 8a nhi u thông tin quan tr 'ng h ơn t p thu %c tính g ,c. Có 3 ph ương pháp dùng ñ t(o ra thu %c tính m $i là: II.3.5.1. Trích l 'c thu %c tính: Là vi c t (o ra t p thu %c tính m $i d &a trên m %t t p thu %c tính ban ñ0u. Ví d : Cho tr ư$c t p h p các c ch C trong ngôn ng c ch C (sign language).Trích l 'c các thu %c tính dùng ñ phân lo (i và nh n d (ng c ch C. Thu %c tính này có th là: ñư)ng di chuy n c a tay, ñ% dài t 9 tâm c a kí hi u ñ/ n các ñ i m biên, g ,c d *ch chu y n c a các frame hình. Các thu %c tính Chi /n l ư c tìm ki /m T p thu %c tính con ð ánh giá t p thu %c tính con ð i u ki n d9 ng L &a ch 'n thu%c tính Th t c xác nh n Yes No Hình II-12. Ki n trúc c a vi c ch n t p thu c tí[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 28 II.3.5.2. Chuy n ñ! i không gian: g ,c ñ% khác nhau, vi c hi u d li u có th phát hi n ra nhi u thông tin quan tr 'ng t 9 d li u c ũng nh ư các thu %c tính quan tr 'ng trong quá trình phân tích d li u. Ví d : D li u time series có th ch 8a các chu trình. N /u d li u không b * nhi Du thì vi c tìm ra các chu trình r t d D dàng, ng ư c l(i r t khó kh ăn. ð, i v$i d li u theo th )i gian, thì bi /n ñ! i Fourier, Wavelet là m %t cách làm hi u qu # trong vi c chuy n không gian d li u. II.3.5.3. Xây d &ng thu %c tính: Trong m %t s , tr ư) ng h p, t p thu %c tính hi n t (i c a d li u ch 8a nhi u thông tin quan tr 'ng không th áp d ng cho các k - thu t khai phá d li u. Trong tình hu ,ng này, c 0n ph #i xây d &ng t p thu %c tính m $i d &a trên t p thu %c tính có s I n ñ phù h p v $i các k - thu t khai phá d li u mà mình mu ,n áp d ng. a) ðư)ng ñi “g ,c” b) ðư)ng ñi ñã ñư c “làm m*n” Hình II-13. Ví d v ñư ng di chuy n c a m t ký hi u trong ngôn ng khi m thính c a ng ưi Vi t Nam Hình II-14. Áp d ng bi n ñ i Fouries ñ xác ñnh t n s quan tr ng c a time series [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 29 II.3.6. R%i r $c hóa và nh & phân hóa: II.3.6.1. Nh * phân hóa: M %t s , k - thu t ñơ n gi #n ñ nh * phân hóa các thu %c tính phân lo (i là: - N/u thu %c tính phân lo (i có t ,i ñ a m giá tr * thì gán m Ei giá tr * b :i m %t s , nguyên t 9 0 ñ/n m-1. - N/u thu %c tính phân lo (i có giá tr * là ki u s , có th 8 t& thì s @p x /p th 8 t& các giá tr *. - Chuy n các giá tr * s , nguyên sang s , nh * phân. S , ch s , dùng ñ bi u di Dn m giá tr * là []mn2log= . Ví d : Xét m %t bi /n ki u phân lo (i có 5 giá tr * {kém, y /u, trung bình, khá, gi Ai}. Các giá tr * này chuy n sang s , nh * phân 3 bit nh ư sau: B ng II-1 Giá tr * phân lo (i Giá tr * s , ngu yên x1 x2 x3 Kém 0 0 0 0 Y /u 1 0 0 1 Trung bình 2 0 1 0 Khá 3 0 1 1 Gi Ai 4 1 0 0 Tuy nhiên, vi c chuy n ñ! i nh ư v y không th hi n ñư c m,i quan h gi a các giá tr * c a thu %c tính ñư c chu y n ñ! i. Ví d : gi Ai h ơn khá, khá h ơn trung bình, trung bình h ơn y /u, y /u h ơn kém. M %t cách khác ñ nh * phân hóa là ñ!i s, nguyên sang s , nh * phân không ñ, i x 8ng. Trong ví d trên, có 5 giá tr * phân lo (i, c 0n 5 bits ñ bi u di Dn nh * phân không ñ,i x 8ng nh ư sau: B ng II-2 Giá tr* phân lo (i Giá tr * s , nguyên x1 x2 x3 x4 x5 Kém 0 1 0 0 0 0 Y /u 1 0 1 0 0 0 Trung bình 2 0 0 1 0 0 Khá 3 0 0 0 1 0 Gi Ai 4 0 0 0 0 1 Trong m %t s , tr ư) ng h p, có th áp d ng bi n pháp: n /u m %t thu %c tính có 2 giá tr * thì ch C c 0n s d ng 1 bits. Ví d : x1=0 là n, x2=1 là nam. II.3.6.2. R )i r (c hóa thu %c tính liên t c: Th ư)ng ñư c s d ng khi áp d ng k - thu t phân tích phân lo (i d li u (classification) và k /t h p (assiociation). M %t cách t !ng quát, cách r )i r (c hóa t ,t nh t ph thu %c vào thu t toán khai phá d li u s ? áp d ng ñ phân tích c ũng nh ư các thu %c tính s ? ñư c r)i r (c hó[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 30 a) R )i r (c hóa các giá tr * liên t c: ð! i m %t thu %c tính t 9 liên t c sang r )i r (c liên quan ñ/n 2 v n ñ : i. S, l ư ng giá tr * c a thu %c tính r )i r (c. ii. Cách chu y n t 9 giá tr * liên t c sang giá tr * r )i r (c. Vi c ñ0 u tiên khi th &c hi n r )i r (c hóa các giá tr * liên t c là s @p x /p các giá tr * c a thu %c tính liên t c, chia các giá tr * này ra làm n {(x0,x1];(x1,x2];…(xn-1,xn)} ñ o (n b 4ng các s d ng n-1 ñi m chia. Công vi c th &c hi n k / ti /p là ánh x ( m Ei ñ o (n vào m %t giá tr * r )i r (c. Cách th &c hi n trong r )i r (c hóa có th là : giám sát và không giám sát. Tùy vào ñi u ki n th &c t / c a k - thu t khai phá d li u thì s ? áp d ng. b) Tr ư) ng h p thu %c tính phân lo (i có nhi u giá tr *: C 0n ph #i k /t h p nhi u ph ương pháp r )i r (c hóa phù h p v $i k - thu t khai phá d li u s ? ñư c s d ng. II.3.7. Chuyn ñ i thu !c tính: Chuy n ñ! i thu %c tính là vi c chu y n ñ! i ñư c áp d ng cho t t c # các giá tr * c a m %t thu %c tính. Có 2 ki u chu y n ñ! i quan tr 'ng là: II.3.7.1. S d ng hàm ñơn gi #n: Trong tr ư)ng h p này, m %t s , hàm tính toán ñơn gi #n ñư c s d ng ñ chuy n ñ! i giá tr * c a thu %c tính. Các hàm này có th s d ng ñ chuy n ñ! i giá tr * x c a thu %c tính là: x k, log x, e x, 1/x, |x|, sin x, x . L ưu ý: Khi bi /n ñ! i d li u c 0n l ưu ý ñ/n các kh # n ăng có th thay ñ!i b #n ch t c a d li u. Ví d : Hàm f(x)=1/x có th gi #m ñ% l$n c a f(x) v $i x>1 nh ưng l ( i làm t ăng giá tr * c a f(x) ñ,i v$i x<1. II.3.7.2. Chu >n hóa: M c ñích là làm cho c # t p d li u có m %t thu %c tính nào ñó. Có nhi u cách ñ chu >n hóa d li u ñư c áp d ng tùy vào tr ư)ng h p c th . II.4. M !t s ( k ) thu t khai phá d li u: II.4.1. Phân c m d li u (Cluster analysis): II.4.1.1. Gi $i thi u: Phân tích c m là 1 k - thu t th ư)ng ñư c s d ng trong l ĩnh v &c khám phá tri th 8c. K - thu t này, th ư)ng ñư c s d ng trong vi c gom nhóm các d li u t ươ ng t & nhau ho <c các mô hình có m t ñ% xác ñ*nh l (i v $i nhau nh 4m t (o nên 1 d li u m $i d &a trên nhóm d li u ñã cho và có th ñư c rút g 'n h ơn so v $i d li u ban ñ0u. Phân tích c m g @n li n v $i vi c h 'c không giám sát, khi ñó d li u và nhãn là không có s In. Ví d : Khi gi $i thi u 1 s #n ph >m trong siêu th *, ng ư)i qu #n lý hay nhà kinh doanh s ? xác ñ*nh 1 nhóm ho <c c m khách hàng ñã t .n t (i trong l *ch s thanh toán c a h th ,ng, ñ,i v $i vi c gom nhóm khách hàng có th là theo tu !i, thu nh p ho <c m 8c s ,ng ñ ñư a ra ñư c chi /n l ư c kinh doanh và h ư$ng t $i khách hàng. Phân tích c m d li u th ư)ng ñư c s d ng cho ph ương pháp khai thác d li u mô t #. Cho m %t ma tr n g .m n dòng d li u và p c %t, m c tiêu c a phân tí[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 31 c m là gom các d li u và các nhóm thành n %i b % ñ. ng nh t (n %i b % g @n k /t) và không ñ.ng nh t t 9 nhóm này sang nhóm khác (tách bên ngoài). Bên c (nh ñó, Phân tích c m c ũng là 1 k - thu t quan tr 'ng ñư c 8ng d ng trong khai khoáng d li u ña ph ương ti n. M c ñích là ñ phân tích c m n %i dung ña ph ương ti n v $i nhau ñ l p ra các ch C m c hi u qu #, và ñư c lưu tr vào trong c ơ s : d li u (database) ña ph ương ti n. Ví d : Các b 8c #nh t ương t & nhau có th ñư c Phân tích c m v $i nhau ñ l p thành 1 ch C m c hi u qu #; khi ñó, khi th &c hi n tru y v n thì k /t qu # tr # v s d ng 1 hình #nh truy v n ho <c hình #nh mô t #, sau ñó là các hình #nh t ương t & ñ u c thu h .i. M c tiêu chính c a ph ương pháp phân c m d li u là nhóm các ñ,i tư ng t ươ ng t & nhau trong t p d li u vào các c m sao cho các ñ,i tư ng thu %c cùng m %t l $p là t ương ñ.ng còn các ñ,i tư ng thu %c các c m khác nhau s ? không t ươ ng ñ.ng. II.4.1.2. Các ph ương pháp phân c m : a) Ph ương pháp phân c p: (Hierachical methods) Phân c p c m th ư)ng ñư c biu di Dn d ư$i d(ng cây c a các c m. Trong ñó: - Các lá c a cây bi u di Dn t 9ng ñ,i tư ng. - Các nút trong bi u di Dn các c m. Có 2 ph ương pháp t (o cây phân c p: Ph ương pháp phân c p t 9 trên xu ,ng: B @t ñ0 u t 9 c m l $n nh t ch 8a t t c # các ñ,i tư ng. Chia c m phân bi t nh t thành các c m nh A h ơn và ti /p di Dn cho ñ/n khi có n c m tho # mãn ñi u ki n d 9 ng. Hình II-12. Bi u di n c a ph ương pháp phân c m t ! trên xu ng Ph ương pháp phân c p t 9 d ư$ i lên: Các b ư$c th &c hi n: - Bư$ c 1: T (o n nhóm, m Ei nhóm g .m m %t ñ, i tư ng và l p ma tr n kho #ng cách c p n. b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 32 - Bư$ c 2:Tìm 2 nhóm u,v có kho #ng cách nh A nh t (duv) - Bư$ c 3: G %p nhóm u v $i nhóm v. Ký hi u nhóm m $i là (uv). L p ma tr n kho #ng cách m $i b 4ng cách: + Lo (i các hàng và c %t t ươ ng 8ng v $i các nhóm u,v + Thêm m %t hàng và m %t c %t ñ lưu kho #ng cách c a nhóm uv v $i các nhóm còn l (i - Bư$ c 4: L <p l (i các b ư$c 2 và b ư$c 3 cho ñ/n khi ch 'n ñư c k nhóm thích h p nh t cho bài toán ho <c ch C có m %t nhóm du y nh t. b) Ph ương pháp phân c m b % ph n: (Partitional clustering methods) Mô t # các ph ương pháp: Cho m %t c ơ s : d li u D ch 8a n ñ,i tư ng, t (o phân ho (ch thành t p có k c m sao cho: - MEi c m ch 8a ít nh t m %t ñ, i tư ng - MEi ñ, i tư ng thu %c v m %t c m duy nh t - Cho tr * k, tìm phân ho (ch có k c m sao cho t ,i ư u hoá tiêu chu >n phân ho (ch ñư c ch 'n. Các ph ương pháp (1) Ph ương pháp gom c m k-means: Input: S, các c m k c 0n gom và c ơ s : d li u ch 8a n ñ,i tư ng. Output: k cm ñã ñư c gom. Thu t gi i: g .m 4 b ư$c - Bư$ c1: Phân ho (ch ñ,i tư ng thành k t p con (c m) ng "u nhiên. - Bư$ c 2: Tính các tâm (trung bình c a các ñ,i tư ng trong c m) cho t 9ng c m trong phân ho (ch hi n hành. - Bư$ c 3: Gán m Ei ñ, i tư ng cho c m tâm g 0n nh t - Bư$ c 4: N /u c m không có s & thay ñ!i thì d 9ng, ng ư c l (i quay l (i b ư$ c 2 (2) Ph ương pháp gom c m k-medoid: Input: S, các c m k c 0n gom và c ơ s : d li u ch 8a n ñ,i tư ng. Output: k cm ñã ñư c gom. Thu t toán: - Bư$ c 1: Ch 'n k ñ,i tư ng ng "u nhiên làm tâm c a nhóm. - Bư$ c 2: Gán t 9ng ñ,i tư ng còn l (i vào c m có tâm g 0n nh t. - Bư$ c 3: Ch 'n ng "u nhiên 1 ñ,i tư ng không là ñ,i tư ng tâm, và thay m %t trong các tâm ñó b 4ng nó n /u nó làm thay ñ!i ñ, i tư ng trong c m (gán ñ,i t ư ng cho c m có tâm g 0n nh t). - Bư$ c 4: N /u gán tâm m $i thì quay l (i b ư$ c 2, ng ư c l(i thì d 9ng. (3) D &a trên mô hình c m : (Model-based clustering) Các ph ương pháp này nh 4m m c ñích ñ phù h p gi a d li u nh t ñ* nh và m %t s , mô hình toán h 'c t ,i ưu hóa. ñ ây, d li u th ư)ng gi # ñ* nh ñư c t(o ra t 9 phân ph ,i xác su t c, th ư)ng là phân ph ,i Gaussian ho <c Normal, xung [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 33 c m trung tâm. ði u này có th g 'i là 1 ph 0n c a thu t toán Phân tích c m c-means. T,i ưu hóa k ỳ v 'ng (Exceptation Maximization – EM) là 1 thu t toán ph ! bi /n l <p l (i (interation) thu %c v danh m c c a phân nhóm, th ư)ng là d &a trên mô hình. Nó khác v $i thu t toán c-means : ch E: t (i m Ei ñi m trên mô hình thu %c v m %t nhóm theo 1 tr 'ng s , (Xác su t c a các thành viên). Nói cách khác, không có ranh gi $i nghiêm ng <c gi a các c m. ði u ñó ñ. ng ngh ĩa v $i vi c các thông s , ñư c tính toán d &a trên bi n pháp là tìm tr 'ng s ,. Nó cung c p 1 mô hình th ,ng kê c a các d li u và có kh # n ăng x lý s & không ch @c ch @n liên quan. Thu t toán này có th ñư c ñ< c tr ưng nh ư sau: Kh :i t (o c c m trung tâm. Quá trình th &c hi n g .m 2 b ư$c và có th chu y n ñ! i qua l (i v $i nhau: • Bư c k ỳ v ng: (Exceptation step) Ch C ñ* nh cho d li u t (i ñi m Xi ñ/ n c m Uk v$i xác su t là: ()()( )i kikikkiXp UXpUpXUpUXP |)|()( ==∈ (CT-II-1) V $i ))(,()|(ikkkiXEmNUXp = theo phân ph ,i Normal theo kho #ng cách m k v$i k ỳ v 'ng Ek. • Bư c khai thác t i ñ a: Ư$ c tính các thông s , c a mô hình: ∑∑=∈∈=Ni j ji kiikUXP UXPXNm1)( )(1 (CT-II-2) Trong th &c t /, bài toán s ? h %i t nhanh h ơn, nh ưng không th ñ( t t,i ưu. H %i t ñư c ñ# m b #o ñ, i v $i các hình th 8c nh t ñ* nh c a ch 8c n ăng t ,i ưu hóa. S & ph 8c t (p tính toán là O(c*N*n*t), v $i n là các tính n ăng ñ0u vào. II.4.2. H*i quy (Regression): II.4.2.1. Gi $i thi u: Thu t ng h .i quy ñư c s d ng ñ0u tiên n ăm 1908, b :i Pearson. M c ñích c a h .i quy là: - V n ñ giao d *ch v $i các 8$c tính c a m %t giá tr * s #n xu t d &a trên giá tr * ñ0 u vào. - H.i quy là m %t k - thu t khai thác d li u ñư c s d ng ñ phù h p v $i m %t ph ương trình c a t p d li u. Ngoài ra, m c ñích c a h .i quy là tìm hi u thêm v m ,i quan h gi các bi /n ñ% c l p (independent) ho <c bi /n d & ñ oán (predictor) và m %t bi /n ph thu %c (dependent) hay tiêu chu >n (criterion). Mô hình h .i quy d &a trên vi c xây d &ng các ñ. th * d &a trên ñư)ng th Gng ñ gi #i qu y /t các bài toán có m 8c ñ% khó khác nhau. Chính vì v y, h .i quy còn ñư c bi/t ñ/ n là t t c # nh ng thu t toán liên quan ñ/n d li u s ,. Hình th 8c ñơ n gi #n nh t c a h .i quy là h .i quy tuy /n tính, trong ñó s d ng ph ương trình ñ(i s,: ii kkiii exbxbxbay +++++= ...2211 v$i i=1,2,...,n (CT-II-3)[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 34 Ho<c t ươ ng ñươ ng: Y=XB+E (CT-II-4) Trong ñó: - n là t t c # các quan sát xem xét. - Y là véc t ơ c %t v $i n dòng ch 8a giá tr * c a các bi /n ph #n 8ng. - X là ma tr n v $i n dòng và k+1 c %t, cho m Ei c %t ch 8a giá tr * c a bi /n gi #i thích cho n quan sát. - B là véc t ơ v $i k+1 dòng có ch 8a t t c # các tr 'ng s , c a mô hình ñư c ư$ c tính trên c ơ s : d li u: các ng ăn ch <n và h s , d ,c t ươ ng 8ng k so v $i m Ei bi /n gi #i thích. - E là véc t ơ c %t c a n chi u dài có ch 8a các t 9 ng lE i (the error terms). Có nhi u lo (i h .i quy khác nhau ñư c s d ng trong l ĩnh v &c th ,ng kê và th ư) ng ñư c s d ng trong l ĩnh v &c d & ñ oán, nh ưng ý t ư:ng c ơ b #n c a h .i quy là mô hình ñư c t(o ra mà b #n ñ. giá tr * t 9 d & ñ oán có giá tr * x #y ra l Ei là th p nh t trong vi c ñư a ra m %t d & ñ oán. Ví d : m %t nhà nông h 'c có th quan tâm t $i vi c nghiên c 8u s & ph thu %c c a s #n l ư ng lúa vào nhi t ñ% , lư ng m ưa, n @ng, phân bón,... II.4.2.2. Các lo (i h .i quy Có 2 lo (i: 1) H .i quy tuy /n tính: a) Hi quy tuy n tính hai chi u: H .i qu y tu y /n tính 2 chi u là m %t ph 0n c ơ b #n trong h .i qu y tu y /n tính. Nó ñ i sâu vào vi c ñánh giá 1 bi /n ph thu %c hay ph #n 8ng, ñư c gây ra và gi #i thích b : i 1 bi /n khác, ñó là bi /n ñ% c l p hay là bi /n gi #i thích. Quá trình xây d &ng và xác ñ*nh bi /n gi #i thích có th ñư c xem nh ư quá trình d & ñ oán. Trong quá trình nghiên c 8u, chúng ta s ? s d ng bi /n Y ñ ch C bi /n ph thu %c (ph #n 8ng) và X cho bi /n ñ% c l p (gi #i thích). Trong m %t s , mô hình th ,ng kê ñơn gi #n có th mô t # Y nh ư là m %t hàm c a X là h .i quy tuy /n tính. Các mô hình h .i quy tuy /n tính xác ñ*nh m ,i quan h tuy /n tính là m ,i quan h nhi Du gi a bi /n Y và X, và ñ,i v $i các c <p (xi,yi) ñư c quan sát và ñư c g'i là hàm h .i quy: iii ebxay ++= (i=1,2,…,n) (CT-II-5) Trong ñó: - a là giá tr * ch <n (intercep) c a hàm h .i qu y. - b là h s , h .i quy (hay ñ% d,c c a hàm h .i quy). - ie là l Ei ng "u nhiên t ương 8ng v $i v * trí th 8 i c a hàm h .i [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 35 b) Hi quy tuy n tính ña chi u: Vi c gi #i quy /t mô hình h .i quy tuy /n tính d &a trên m ,i quan h 2 chi u còn g <p nhi u khó kh ăn, do ch C s dung 1 bi /n ñ% c l p (gi #i thích) . Chính vì th /, mô hình h .i quy tuy /n tính nhi u chi u ñư c 8ng d ng ñ gi #i quy /t v n ñ ñ ó. Gi # s t t c # các bi /n có trong ma tr n d li u, tr 9 các bi /n ñư c g'i là bi /n ph #n 8ng. Cho k là s , bi /n gi #i thích. H .i quy tu y /n tính nhi u chi u ñư c xác ñ* nh b :i m ,i quan h sau: iikkiiiexbxbxbay +++++= ...2211 v$i i=1,2,...,n (CT-II-6) Hình II-17. Chu "n ñoán c a mô hình h i quy Ho <c t ươ ng ñươ ng: Y=XB+E (CT-II-7) Hình II-16. Bi u di n ñư ng h i [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 36 Trong ñó: - n là t t c # các quan sát xem xét. - Y là véc t ơ c %t v $i n dòng ch 8a giá tr * c a các bi /n ph #n 8 ng. - X là ma tr n v $i n dòng và k+1 c %t, cho m Ei c %t ch 8a giá tr * c a bi /n gi #i thích cho n quan sát. - B là véc t ơ v $i k+1 hàng có ch 8a t t c # các tr 'ng s , c a mô hình ñư c ư$ c tính trên c ơ s : d li u: các ng ăn ch <n và h s , d ,c t ươ ng 8ng k so v $i m Ei bi /n gi #i thích. - E là véc t ơ c %t c a n chi u dài có ch 8a các t 9 ng l Ei (the error terms). Trong tr ư)ng h p mô hình h .i quy 2 chi u ñư c ñ( i di n b 4ng 1 dòng, bây gi ) (CT-II-6) t ương 8ng v $i k+1 – chi u m <t ph Gng, ñư c g'i là m <t ph Gng h .i quy. M <t ph Gng này ñư c ñ* nh ngh ĩa là 1 ph ương trình: ikkiiixbxbxbay ++++= ...2211 (CT-II-8) ð xác ñ*nh m <t ph Gng ñư c trang b * c 0n thi /t ñ ư$ c tính véc t ơ c a các tham s , (a, b1, b2,…,bk) trên cơ s : d li u có s In. 2) H .i quy lo gic: H .i quy tuy /n tính ñư c coi là 1 mô hình d & báo cho 1 bi /n ñáp 8ng v s , l ư ng, còn h .i quy lo gic ñư c xem xét m %t mô hình d & báo cho m %t bi /n ph #n 8 ng ñ*nh tính. M %t v n ñ ñ áp 8ng ch t l ư ng th ư)ng có th ñư c chia thành bài toán nh * phân. Các khóa xây d &ng (bulding lock) c a h 0u h /t các mô hình ph #n 8 ng ñ*nh tính là mô hình h .i quy logic, ñây là m %t trong nh ng d & ñ oán quan tr 'ng nh t c a ph ương pháp khai thác. M %t mô hình ñư c hi u là h .i quy logic c 0n có các giá tr * trang b * ñư c hi u là các xác su t mà s & ki n x #y ra trong các qu 0n th khác nhau. )1( ==ii YPπ v $i i=1,2,…,n (CT-II-9) Chính xác h ơn, 1 mô hình h .i quy tuy /n tính c 0n xác ñ*nh m %t ch 8c n ăng thích h p c a các xác su t l @p ñ< t ca s & ki n là 1 hàm tuy /n tính c a giá tr * quan sát c a các bi /n gi #i thích có s In. ñ ây là m %t ví d : ikkiitixbxbxba ++++= − ...1log2211ππ (CT-II-10) V / trái xác ñ*nh ch 8c n ăng lo gic c a xác su t ñư c trang b *, t 8c là: −=iiiπππ1log)log( (CT-II-11) M %t khi iπñư c tính toán, trên c : s : c a d li u, 1 giá tr * ñư c gán cho m Ei giá tr * nh * phân iyˆ có th thu ñư c, ñư a vào 1 giá tr * ng ưKng c a iπ v$i giá tr * c n trên là iyˆ=1 và c n d ư$i là iyˆ=0. Không gi ,ng nh ư h .i quy tuy /n tính, các giá tr * ph #n 8ng ñư c quan sát không th b * phân h y c %ng tính là t !ng giá tr * trang b * và 1 gi $i h (n l Ei. Vi c l &a ch 'n ch 8c n ăng logit ñ mô t # các ch 8c n ăng liên k /t iπ ñ/ n s & k /t h p tuy /n tính c a các bi /n gi #i thích, ñư c thúc ñ>y b :i m %t th &c t / mà v [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 37 s& l &a ch 'n này có xu h ư$ng v 0 và d 0n d 0n v 1. Và các gi $i h (n này c ũng không ñ#m b #o r 4ng iπ là m %t xác su t h p l . M %t bi /n ph #n 8ng nh * phân không thích h p ñ s d ng mô hình h .i quy tuy /n tính ñ gi #i quy /t, b :i vì 1 hàm tu y /n tính là không gi $i h (n. Do ñó, mô hình có th d & ñ oán giá tr * c a bi /n ph #n 8ng bên ngoài kho #ng [0,1], ñi u ñó là vô ngh ĩa. Nh ưng d &a trên các ki u liên k /t ñ tìm ra k /t qu # là có th . II.4.2.3. Nh n xét: a) Nh n xét chung: Phân tích h .i quy th ư)ng ñư c s d ng ñ gi #i quy /t các v n ñ sau: - Ư$ c lư ng giá tr * trung bình c a bi /n ph thu %c v $i giá tr * ñ ã cho c a bi /n ñ% c l p. - Kim ñ*nh gi # thi /t v b #n ch t c a s & ph thu %c. - D& ñ oán giá tr * trung bình c a bi /n ph thu %c khi bi /t giá tr * c a các bi /n ñ% c l p. - K/t h p các v n ñ trên. b) Ư u ñi m: - Trong tr ư)ng h p h .i quy tuy /n tính, nó xây d &ng m %t mô hình trong ñó có m ,i quan h gi a các bi /n ñ% c l p và ph thu %c ñư c lên ñ/n nhi m v c a nó và cho k /t qu # t ,i ư u. Còn ñ,i v$i h .i qu y logic, xây d &ng m %t mô hình d &a trên xác su t mà s & ki n x #y ra trong qu >n th . - C# h .i quy tuy /n tính và h .i quy logic ñ u d &a trên d li u có s In ñ xây d &ng. - Là m %t công c m (nh trong vi c khai thác d li u phân l $p. - H.i quy ñư c gi$i h (n trong vi c d & ñ oán các giá tr * s ,. c) Khuy /t ñi m: - H.i quy không ñư c 8ng d ng trong vi c gi #i qu y /t các v n ñ khai thác d li u v $i m c ñích phân tích k /t h p. - Trong vi c x lý v $i s , l ư ng d li u l $n, vi c l &a ch 'n h .i qu y cho vi c khai thác d li u s ? g <p r t nhi u l Ei và nhi Du trong quá trình khai thác. II.4.3. Cây quy +t ñ& nh (Decision tree): II.4.3.1. Gi $i thi u: Cây quy /t ñ* nh ñư c s d ng trong l ĩnh v &c khai phá d li u và h 'c máy. Cây quy /t ñ* nh th ư)ng ñư c s d ng nh ư là m %t mô hình d & báo v m %t ñ, i t ư ng m c tiêu, ñ có ñư c k/t lu n v giá tr * c a m c tiêu ñó. Cây quy /t ñ* nh còn ñư c g'i là cây phân lo (i hay cây h .i qu y. C u trúc c a m %t cây quy /t ñ* nh: trên cây quy /t ñ* nh có 3 lo (i nút - Nút g ,c: Không có c (nh vào, không có ho <c có nhi u c (nh ra. - Nút gi a: Có chính xác m %t c (nh vào, có hai hay nhi u c (nh ra. - Nút lá: có chính xác m %t c (nh vào, không có c (nh ra. Nút lá còn là ñ(i di n cho phân lo (i, ngành ñ(i di n ho <c liên t 9 c a tính n ăng, t 9 ñ ó d "n ñ/ n nh ng phân lo ([email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 38 Trong phân tích quy /t ñ* nh, m %t cây quy /t ñ* nh có th ñư c s d ng ñ ñ( i di n rõ ràng và tr &c quan quy /t ñ* nh và ra qu y /t ñ* nh. Trong khai phá d li u, cây quy /t ñ* nh mô t # m %t d li u nh ưng không quy /t ñ* nh, các k /t qu # c a cây phân lo (i d li u có th là ñ0u vào cho vi c h E tr ra quy /t ñ* nh. Hình II-18. Ví d v cây quy t ñ nh II.4.3.2. Gi $i h (n c a cây quy /t ñ* nh: - V n ñ h'c trong cây quy /t ñ* nh t ,i ưu ñư c bi/t ñ/ n là NP-complete theo các khía c (nh t ,i ưu và ngay c # ñ, i v $i các khái ni m ñơn gi #n. Do ñó, thu t toán h 'c c a cây quy /t ñ* nh th &c t / là d &a trên thu t toán Heuristic ( Ph l c II ) c ơ b #n, nh ư các thu t toán ham ăn (Greedy) n ơi mà quy /t ñ* nh t ,i ưu ñư c th&c hi n t (i ñ* a ph ương c a m Ei nút. Thu t toán này không th ñ# m b #o cây quy /t ñ* nh v 9a tìm ñư c là t ,i ưu. - Vic h 'c c a cây quy /t ñ* nh có th t (o ra cây ph 8c t (p, n /u d li u ñ0 u vào không khái quát các d li u t ,t. ði u này còn ñư c g'i là Over-fitting, c ơ ch / nh ư v y có th ñư c s d ng ñ c@t t Ca cây, tránh g <p ph #i v n ñ này. - Có nh ng khái ni m r t khó ñ h'c, vì th / cây quy /t ñ* nh không th bi u di Dn chúng m %t cách d D dàng, nh ư XOR, t ương ñươ ng ho <c các v n ñ ñ a x lý. Tr ư) ng h p này, cây quy /t ñ* nh tr : thành m %t ng ăn c #n l $n. II.4.3.3. Ph ương pháp xây d &ng cây quy /t ñ* nh: • Vi c t (o cây quy /t ñ* nh bao g .m 2 giai ño (n : T (o cây và t Ca cây . - ð t(o cây : th )i ñi m b @t ñ0 u t t c # nh ng ví d hu n luy n là : g ,c sau ñó phân chia ví d hu n luy n theo cách ñ qui d &a trên thu %c tính ñư c ch 'n . - Vic t Ca cây là xác ñ*nh và xóa nh ng nhánh mà có ph 0n t h En lo (n ho <c nh ng ph 0n t n 4m ngoài (nh ng ph 0n t không th phân vào m %t l $p nào ñ ó) . • Có r t nhi u bi /n ñ! i khác nhau v thu t toán xây d &ng cây quy /t ñ* nh, m <c dù v y chúng v "n tuân theo nh ng b ư$c cơ b #n sau : - Cây ñư c thi /t l p t 9 trên xu ,ng d ư$i và theo cách th 8c chia ñ tr*. - th )i ñi m b @t ñ0 u, các m "u hu n luy n n 4m : g ,c c a câ[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 39 D li u g ,c Phép phân tách kém Phép phân tách kém Phép phân táct ,t Hình II-19. Bi u di n c a các phép phân tách - Thu %c tính ñư c phân lo (i (R )i r (c hóa các thu %c tính d (ng phi s , ) - Ch 'n m %t thu %c tính ñ phân chia thành các nhánh. Thu %c tính ñư c ch 'n d &a trên ñ% ñ o th ,ng kê ho <c ñ% ñ o heuristic. - Ti/p t c l <p l (i vi c xây d &ng cây quy /t ñ* nh cho các nhánh. • ði u ki n ñ d9ng vi c phân chia: - T t c # các m "u r ơi vào m %t nút thu %c v cùng m %t l $p (nút lá) - Không còn thu %c tính nào có th dùng ñ phân chia m "u n a - Không còn l (i m "u nào t (i nút. II.4.3.4. Xây d &ng cây quy /t ñ* nh: 1) Ch n thu c tính phân tách: Lúc kh :i ñ0 u, ta có trong tay m %t t p luy n ch 8a t p các b #n ghi ñư c phân lo (i tr ư$c – t 8c là giá tr * c a bi /n ñích ñư c xác ñ*nh trong t t c # các tr ư)ng h p. Cây quy /t ñ* nh ñư c xây d &ng b 4ng cách phân tách các b #n ghi t (i m Ei nút d &a trên m %t thu %c tính ñ0u vào. Rõ ràng nhi m v ñ0 u tiên là ph #i ch 'n ra xem thu %c tính nào ñưa ra ñư c s& phân tách t ,t nh t t (i nút ñó. ð% ñ o ñư c s d ng ñ ñ ánh giá kh # n ăng phân tách là ñ% tinh khi /t. Chúng ta s ? có nh ng ph ương pháp xác ñ*nh ñ tính toán ñ% tinh khi /t m %t cách chi ti /t, tuy nhiên chúng ñ u c , g @ng ñ(t ñư c hiu qu # nh ư nhau. M %t s & phân tách t ,t nh t là s & phân tách làm t ăng ñ% tinh khi /t c a t p b #n ghi v $i s , lư ng l $n nh t. M %t s & phân tách t ,t c ũng ph #i t (o ra các nút có kích c K t ươ ng t & nhau, hay chí ít c ũ ng không t (o ra các nút có quá ít b #n ghi. Thu t toán xây d &ng cây quy /t ñ* nh h /t s 8c th u ñáo. Chúng b @t ñ0 u b 4ng vi c ch 'n m Ei bi /n ñ0 u vào ch ưa ñư c ch 'n và ño m 8c ñ% tăng ñ% tinh khi /t trong các k /t qu # 8 ng v $i m Ei bi /n. Sau ñó m %t phép tách t ,t nh t s ? ñư c s d ng trong phép tách kh :i ñ0 u, ñ t(o hai hay nhi u nút con. N /u không phé[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 40 phân tách nào có kh # n ăng (có th do có quá ít b #n ghi) ho <c do không có phép phân tách nào làm t ăng ñ% tinh khi /t thì thu t toán k /t thúc và nút ñó tr : thành nút lá. Phép phân tách trên các bi n ñ u vào ki u s : ñ, i v $i s & phân tách nh * phân trên m %t bi /n ñ0 u vào, m Ei giá tr * mà bi /n ñó ch 8a ñ u có th tr : thành giá tr * d & tuy n. Phép phân tách nh * phân d &a trên bi /n ñ0 u vào ki u s , có d (ng X < N. ð c#i thi n hi u n ăng, m %t s , thu t toán không ki m tra h /t toàn b % các giá tr * c a bi /n mà ch C ki m tra trên t p m "u giá tr * c a bi /n ñó. Phép phân tách trên các bi n ñ u vào ñnh tính : thu t toán ñơn gi #n nh t trong vi c phân tách trên m %t bi /n ñ*nh tính là 8ng v $i m Ei giá tr * c a bi /n ñó, ta t ( o m %t nhánh t ương 8ng v $i m %t l $p ñư c phân lo (i. Ph ương pháp này ñư c s d ng th &c s & trong m %t s , ph 0n m m nh ưng mang l (i hi u qu # th p. M %t ph ương pháp ph ! bi /n h ơn ñó là nhóm các l $p mà d & ñ oán cùng k /t qu # v $i nhau. C th , n /u hai l $p c a bi /n ñ0 u vào có phân ph ,i ñ, i v $i bi /n ñích ch C khác nhau trong m %t gi $i h (n cho phép thì hai l $p này có th h p nh t v $i nhau. Phép phân tách v i s có m t c a các giá tr b thi u: m %t trong nh ng ñ i m hay nh t c a cây qu y /t ñ* nh là nó có kh # n ăng x lý các giá tr * b * thi /u b 4ng cách coi giá tr * r Eng ( NULL ) là m %t nhánh c a nó. Ph ương pháp này ñư c ưa thích h ơn so v $i vi c v 8t các b #n ghi có giá tr * thi /u ho <c c , g @ng g @n giá tr * nào ñ ó cho nó b :i vì nhi u khi các giá tr * r Eng c ũng có ý ngh ĩa riêng c a nó. M <c dù phép phân tách giá tr * r Eng nh ư là m %t l $p riêng r ? khá có ý ngh ĩa nh ưng ng ư)i ta th ư) ng ñ xu t m %t gi #i pháp khác. Trong khai phá d liêu, m Ei nút ch 8a vài lu t phân tách có th th &c hi n t (i nút ñó, m Ei phép phân tách ñó d &a vào các bi /n ñ0 u vào khác nhau. Khi giá tr * r Eng xu t hiên trong bi /n ñ0 u vào c a phép phân tách t ,t nh t, ta s d ng phép phân tách thay th / trên bi /n ñ0 u vào có phép phân tách t ,t th 8 hai. 2) Cách ki m tra ñ ch n phép phân tách t t nh t: Hi n nay, có nhi u cách ñ ñ ánh giá cách chia là t ,t hay không t ,t. Các ñ% ñ o dùng ñ ñ ánh giá và l &a ch 'n cách chia ñư c ñ* nh ngh ĩa trên g ,c ñ% s& phân ph ,i v l $ p c a các m "u tin tr ư$c và sau khi b * chia. G 'i pi=p(i|t) là t C l các m "u tin thu %c vào l $p I c a nút t. Trong cách chia ñôi, gi # s có hai l $p class=0 và class=1 thì p 1=1-p0 (V$i p0, p1 là xác su t c a class=0 và class =1) . ð% ñ o ñư c phát tri n cho vi c l &a ch 'n cách chia t ,t nh t d &a trên m 8c ñ% không thu 0n nh t (impurity) c a các nút con. ð% không thu 0n nh t càng nh A thì phân ph ,i l $p càng l ch. ð% không thu 0n nh t có th ñư c ño b 4ng entropy, gini, classification error. Entropy, gini, classification error t (i nút t ñư c ñ* nh ngh ĩa nh ư sau: ∑ −=−= 10 2)|(log)|(ci tiptipEntropy (CT-II-12) ∑ −=−= 10 2)]|([1)( ci tiptGini (CT-II-13) )]|(max[1)(_ tipterrortionClassifica−= (CT-II-14) Trong ñó, c là t !ng s , l $p, các l $p ñư c ñánh s , t9 0 ñ/n [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 41 3) Thu t toán s ăn m i: Thu t toán s ăn m .i hay còn g 'i là thu t toán c a nh ng ng ư)i th s ăn (Hunt’s algorithm). Trong thu t toán này, cây quy /t ñ* nh ñư c phát tri n d &a trên ph ươ ng pháp ñ quy b 4ng cách chia t p d li u h 'c ra thành các t p con m %t cách liên t c. G 'i Dt là t p d li u h 'c t (i nút t và y={y1, y2,…,yc) là t p giá tr * c a thu %c tính l $p. Thu t toán s ăn m .i ñư c ñ* nh ngh ĩa m %t cách ñ quy nh ư sau: - Bư$ c 1: N /u t t c # các m >u tin trong t p Dt thu%c v m %t l $p yt thì t là nút lá ñư c gán nhãn là yt. - Bư$ c 2: N /u t p h p Dt ch8a các m "u tin thu %c nhi u h ơn m %t l $p thì m %t ñi u ki n ki m tra thu %c tính ñư c l&a ch 'n là chia t p Dt ra thành các t p con nh A h ơn. ng v $i m %t ñư) ng ra c a ñi u ki n ki m tra thu %c tính là m %t nút con d &a trên t p h p con c a Dt. - Bư$ c 3: L <p l (i các b ư$c 1, 2 cho ñ/n khi t p Dt chC thu %c m %t l $p. 4) Thu t toán ID3: ID3 xây d &ng cây quy /t ñ* nh theo cách t 9 trên xu ,ng. L ưu ý r 4ng ñ,i v $i b t k ỳ thu %c tính nào, chúng ta c ũng có th phân vùng t p h p các ví d rèn luy n thành nh ng t p con tách r )i, mà : ñ ó m 'i ví d trong m %t phân vùng (partition) có m %t giá tr * chung cho thu %c tính ñó. ID3 ch 'n m %t thu %c tính ñ ki m tra t (i nút hi n t (i c a cây và dùng tr @c nghi m này ñ phân vùng t p h p các ví d ; thu t toán khi ñó xây d &ng theo cách ñ qu y m %t cây con cho t 9ng phân vùng. Vi c này ti /p t c cho ñ/n khi m 'i thành viên c a phân vùng ñ u n 4m trong cùng m %t l $p; l $p ñó tr : thành nút lá c a cây. Vì th 8 t & c a các tr @c nghi m là r t quan tr 'ng ñ,i v $i vi c xây d &ng m %t cây quy /t ñ* nh ñơn gi #n, ID3 ph thu %c r t nhi u vào tiêu chu >n ch 'n l &a tr @c nghi m ñ làm g ,c c a cây. 1 Function induce_tree (t p_ví_d , t p_thu %c_tính) 2 begin 3 if m'i ví d trong t p_ví_d ñ u n 4m trong cùng m %t l $p then 4 return m%t nút lá ñư c gán nhãn b :i l $p ñó 5 else if t p_thu %c_tính là r Eng then 6 return nút lá ñư c gán nhãn b :i tuy n c a t t c # các l $p trong t p_ví_d 7 else 8 begin 9 ch 'n m %t thu %c tính P, l y nó làm g ,c cho cây hi n t (i; 10 xóa P ra kh Ai t p_thu %c_tính; 11 v $i m Ei giá tr * V c a P 12 begin 13 t (o m %t nhánh c a cây gán nhãn V; 14 ð<t vào phân_vùngV các ví d trong t p_ví_d có giá tr * V t (i thu %c tính P; 15 G 'i induce_tree (phân_vùngV, t p_thu %c_tính), g @n k /t qu # vào nhánh V 16 end 17 end 18 [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 42 5) Thu t toán C4.5: - D li u vào: T p d li u D, t p danh sách thu %c tính, t p nhãn l $p - D li u ra: Mô hình cây qu y /t ñ* nh - Thu t toán: T(ocây(T p d li u E, t p danh sách thu %c tính F, t p nhãn l $ p) 1 N /u ñi u_ki n_d 9ng(E,F) = ñúng 2 nútlá = CreateNode() 3 nútlá.nhãnl $p=Phânl $p(E) 4 return nútlá 5 Ng ư c l(i 6 Nútg ,c = CreateNode () 7 Nútg,c. ñi uki nki mtra = tìm_ ñi m_chia_t ,t_nh t(E, F) 8 ð<t F = F \ {Nút ch 'n phân chia} 9 ð<t V = {v| v tho # ñ i u ki n là ph 0n phân chia xu t phát t 9 Nútg ,c} 10 L <p qua t 9ng t p phân chia v ∈V 11 ð<t Ev = {e | Nútg ,c. ñi uki nki mtra(e) = v và e ∈ E} 12 Nútcon = T (ocây(Ev, F, t p nhãn l $p) 13 D 9ng l <p 14 End if 15 Tr # v nútg ,c. 6) Thu t toán lu t quy n p ILA (Inductive learning algorithm) a) Ý t ư:ng: - Xác ñ*nh các lu t IF-THEN tr &c ti /p t 9 t p hu n lu y n (phát tri n lu t theo h ư$ng t 9 t!ng quát ñ/n c th ) - Chia t p d li u hu n luy n thành các b #ng con theo t 9ng giá tr * c a l $p. - Th &c hi n vi c so sánh các giá tr * c a thu %c tính trong t 9ng b #ng con và tính s , l 0n xu t hi n. b) Các b ư$c xây d &ng: - Bư$ c 1: Chia b #ng con có ch 8a m m "u thành n b #ng con ( 8ng v $i n giá tr * c a thu %c tính l $p). - Bư$ c 2: Kh :i t (o s , thu %c tính k /t h p j=1 - Bư$ c 3: Xét t 9ng b #ng con, t (o danh sách các thu %c tính k /t h p (ph 0n t danh sách có j thu %c tính) - Bư$ c 4: V $i m Ei ph 0n t trong danh sách trên, ñ/m s , l 0n xu t hi n các giá tr * c a thu %c tính : các dòng ch ưa ñánh d u c a b #ng con ñang xét, nh ưng giá tr * không ñư c xu t hi n : các b #ng con khác. Ch 'n ph 0n t k /t h p ñ0 u tiên có s , l 0n xu t hi n c a giá tr * thu %c tính nhi u nh t và ñ<t tên là max-combination. - Bư$ c 5: N /u max-combination=0 thì j=j+1 và quay l (i b ư$ c 3. - Bư$ c 6: Trong b #ng con ñang xét, ñánh d u các dòng có xu t hi n giá tr * c a [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 43 - Bư$ c 7: T (o lu t IF AND (Thu %c tính = giá tr *) (thu %c max-combination) THEN giá tr * c a thu %c tính l $p t ươ ng 8ng v $i b #ng con ñang xét. - Bư$ c 8: N/u t t c # các dòng ñ u ñánh d u o N/u còn b #ng con thì chu y n qua b #ng con ti /p theo và l p l (i t 9 b ư$ c 2. o Ng ư c l(i: Ch m d 8t thu t toán. Ng ư c l(i (còn dòng ch ưa ñánh d u) thì quay l (i b ư$ c 4. II.4.3.5. Ưu ñi m c a cây quy /t ñ* nh: - Cây quy /t ñ* nh d D hi u. Ng ư)i ta có th hi u mô hình cây quy /t ñ* nh sau khi ñư c gi#i thích ng @n. - Vic chu >n b * d li u cho m %t cây qu y /t ñ* nh là c ơ b #n ho <c không c 0n thi /t. Các k - thu t khác th ư)ng ñòi h Ai chu >n hóa d li u, c 0n t (o các bi /n ph (dummy variable) và lo (i b A các giá tr * r Eng. - Cây quy /t ñ* nh có th x lý c # d li u có giá tr * b 4ng s , và d li u có giá tr * là tên th lo (i. Các k - thu t khác th ư)ng chuyên ñ phân tích các b % d li u ch C g .m m %t lo (i bi /n. Ch Gng h (n, các lu t quan h ch C có th dùng cho các bi /n tên, trong khi m (ng n ơ-ron ch C có th dùng cho các bi /n có giá tr * b 4ng s ,. - Cây quy /t ñ* nh là m %t mô hình h %p tr @ng. M (ng n ơ-ron là m %t ví d v mô hình h %p ñen, do l )i gi #i thích cho k /t qu # quá ph 8c t (p ñ có th hi u ñư c. - Có th th >m ñ*nh m %t mô hình b 4ng các ki m tra th ,ng kê. ði u này làm cho ta có th tin t ư:ng vào mô hình. - Cây qu y /t ñ* nh có th x lý t ,t m %t l ư ng d li u l $n trong th )i gian ng @n. Có th dùng máy tính cá nhân ñ phân tích các l ư ng d li u l $n trong m %t th )i gian ñ ng @n ñ cho phép các nhà chi /n l ư c ñư a ra qu y /t ñ* nh d &a trên phân tích c a cây quy /t ñ* nh. II.4.3.6. Tính ch t: - Không c 0n có các gi # ñ* nh phân ph ,i c a các l $p tr ư$c khi xây d &ng cây. - Tìm cây t ,i ưu là v n ñ ph 8c t (p vì t ,n nhi u th )i gian và tài nguyên cho vi c tính toán và so sánh. Cách ti /p c n là d &a trên các k - thu t Heuristics. - Các gi #i thu t xây d &ng cây quy /t ñ* nh ph #i có ñ% ph 8c t (p ch p nh n ñư c. - ð, i v$i nh ng cây t ương ñ,i nh A, r t d D d *ch sang câu l nh IF-THEN-ELSE. - Cây quy /t ñ* nh cung c p các mô t # t p lu t m %t cách ph 8c t (p. - Gi#i thu t xây d &ng cây quy /t ñ* nh ch *u #nh h ư:ng c a nhi Du. - S& thi /u ho <c d ư th 9a d li u không #nh h ư:ng nhi u l @m ñ/n k /t qu #. - N/u t p training g .m nhi u m "u tin thì cây k /t qu # có th r t ph 8c t (p và c 0 n ñư c “tCa b $t nhánh” cho cây. - M%t nhánh hay cây con có th l <p l (i nhi u l 0n : nhi u m 8c khác [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 44 II.4.4. K – lân c n g ,n nh t: (K Nearest neighbour-KNN) II.4.4.1. Gi $i thi u: Thu t toán K- lân c n g 0n nh t là thu t toán khai khoáng dùng ñ phân lo (i d li u. KNN là m %t thu t toán h 'c có giám sát mà k /t qu # c a truy v n hi n m $i ñư c phân lo (i d &a trên ña s , các lo (i KNN. M c ñích KNN ñư c s d ng là ñ phân lo (i các ñ,i tư ng m $i d &a trên các thu %c tính và các m "u ñào t (o. Vi c phân lo (i không s d ng b t k ỳ mô hình ñ ñ i u ch Cnh, mà ch C d &a vào b % nh $. V $i m %t ñi m truy v n, chúng ta tìm k ñ,i tư ng ho <c ( ñi m ñào t (o) g 0n nh t ñ th &c hi n truy v n. Vi c phân lo (i ñư c s d ng ña s , trong vi c phân lo (i K ñ,i t ư ng. B t k ỳ m ,i quan h có th ñư c chia m %t cách ng "u nhiên. KNN s d ng trong các thu t toán phân lo (i lân c n là giá tr * d & ñ oán c a các ví d tru y v n m $i. Ví d : Chúng ta có d li u t 9 b #ng câu h Ai kh #o sát ( ñ l y ý ki /n ng ư)i dân) và m c tiêu th nghi m hai thu %c tính (acid durability and strength) ñ phân lo (i xem m %t mô gi y là t ,t hay không. B ng II-3 X1 = Acid Durability (seconds) X2 = Strength (kg/square meter) Classification 7 7 Bad 7 4 Bad 3 4 Good 1 4 Good II.4.4.2. Tìm hi u v K-lân c n g 0n nh t: Thu t toán KNN r t ñơ n gi #n. Nó ho (t ñ% ng d &a trên kho #ng cách t ,i thi u t 9 các m "u truy v n ñ/ n các m "u ñào t (o ñ xác ñ*nh K- lân c n g 0n nh t. Sau khi chúng ta ñã t p h p ñư c ñư c nh ng lân c n g 0n nh t, chúng ta s ? s d ng ñ d& ñ oán các m "u truy v n. Các d li u ñu c dùng cho thu t toán KNN bao g .m: m %t s , thu %c tính ña bi /n Xi s? ñư c s d ng ñ phân lo (i Y. Các d li u c a KNN là các d li u b t k ỳ, có th là th 8 t &, ñ* nh danh(nominal), ñ/n các giá tr * ñ* nh l ư ng nh ưng th )i ñ i m ñ chúng ta x lý v $i các ñ*nh l ư ng Xi và nh* phân ( ñ*nh danh) Y. ñ ây, chúng ta s ? ñ, i phó v $i lo (i qu y mô ño l ư) ng. Hình II-20. B ng d li u dùng cho quá trình h [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 45 Gi# s chúng ta có b #ng d li u sau: V $i các t p d li u mà chúng ta s d ng cho quá trình h 'c (training data) và dòng cu ,i cùng là vùng d li u mà ta c 0 n d & ñ oán (preditcion). ð. th* c a v n ñ này ñư c th hi n nh ư Hình II-21: Hình II-21. ð th bi u di n Gi # s chúng ta c 0n xác ñ*nh K=8, có ngh ĩa là chúng ta s ? s d ng 8 lân c n g 0n nh t nh ư m %t tham s , c a thu t toán này. Sau ñó, chúng ta tính toán kho #ng cách gi a các m "u truy v n và ñào t (o. B :i vì chúng ta s d ng y /u t , ñ* nh l ư ng Xi nên chúng ta có th s d ng kho #ng cách Euclide ñ gi #i quy /t bài toán này. Gi# d , truy v n có t 'a ñ% ( qqxx21 ,) và s& ph ,i h p c a m "u ñào t (o là ( ttxx21 ,), thì bình ph ương kho #ng cách Euclide 2222112)()(qtqtSqxxxxd −+−= . N/u X có ch 8a d li u phân lo (i, ho <c ñ* nh danh thì có th áp d ng t ương t &. B ư$ c ti /p theo ñ tìm K-lân c n g 0n nh t. M %t m "u ñào t (o ñư c g'i là lân c n g 0n nh t n /u kho #ng cách c a m "u ñào t (o này cho ác tr ư)ng h p tru y v n nh A h ơn ho <c b 4ng v $i kho #ng cách nh A nh t th 8 K. Nói cách khác, chúng ta s ? s @ p x /p các kho #ng cách c a t t c # các m "u ñào t (o cho các tr ư)ng h p tru y v n và xác ñ*nh kho #ng cách t ,i thi u th 8 K. Hình II-22. Bi u di n c a m u ñào t [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 46 N/u kho #ng cách c a m "u ñào t (o là d ư$i m 8c t ,i thi u th 8 K, thì chúng ta t p h p ñư c Y th lo (i c a m "u hu n lu y n này. Các b ư$c th &c hi n v cách tính toán K lân c n g 0n nh t, áp d ng thu t toán KNN cho các d li u ñ*nh l ư ng : (1) Xác ñ*nh tham s , K-s , lân c n g 0n nh t. (2) Tính kho #ng cách gi a t t c # các m "u tru y v n và ñào t (o (3) Phân lo (i theo kho #ng cách và xác ñ*nh nh ng lân c n g 0n nh t d &a vào kho #ng cách t ,i thi u th 8 k. (4) T p h p các giá tr * c a Y c a nh ng ng ư)i lân c n g 0n nh t. (5) S d ng trung bình c a các lân c n g 0n nh t là giá tr * d & ñ oán c a các m "u truy v n. II.4.4.3. Nh n xét: - Thu t toán KNN có tác d ng ñ lo (i b A nhi Du trong d li u hu n luy n ( ð< c bi t là s d ng hình vuông ngh *ch ñ#o c a kho #ng cách tr 'ng s , nh ư là “kho #ng cách). - Thu t toán KNN s ? hi u qu # h ơn n /u d li u ñào t (o là l $n. II.4.5. Gi i thu t di truy n: II.4.5.1. Gi $i thi u: Gi #i thu t di truy n (Genetic Algorithm – GA) là m %t ph ương pháp tìm ki /m c &c tr * t !ng th , k - thu t t ,i ưu t !ng th có t 0m quan tr 'ng r t l $n ñ, i v $i nhi u v n ñ khác nhau trong khoa h 'c và k - thu t. Trong khai phá d li u, gi #i thu t di truy n th ư)ng ñư c s d ng trên n n c a các k - thu t khác nh ư m (ng neuron hay phân l $p theo k lân c n g 0n nh t. M <c dù v y, gi #i thu t di truy n là m %t k - thu t r t c 0n thi /t vì h 0u h /t các k - thu t khai phá d li u tóm l (i ñ u là v n ñ t,i ư u hóa. - ð, i v$i m (ng neuron, ñó là v n ñ tìm ki /m các tr 'ng s , cho c u trúc m (ng t ,i ư u. - ð, i v$i k lân c n g 0n nh t, ñó là v n ñ tìm các tr 'ng s , quan tr 'ng t ,i ư u ñ áp d ng cho m Ei y /u t , d & ñ oán. - ð, i v$i cây quy /t ñ* nh, ñó là bài toán tìm ki /m các y /u t , d & ñ oán t ,t nh t và các giá tr * ñ phân tách trong vi c t ,i ư u hóa cây. Gi #i thu t di tru y n ñư c ñánh giá b 4ng hàm thích nghi ñ xác ñ*nh các mô hình d & ñ oán t ,i ưu cho vi c khai thác d li u. II.4.5.2. C ơ b #n v gi #i thu t di tru y n: Ý t ư:ng c a gi #i thu t di tru y n là mô ph Ang theo c ơ ch / c a quá trình ch 'n l 'c và di tru y n trong t & nhiên. T 9 t p các l )i gi #i ban ñ0u, thông qua nhi u b ư$ c ti /n hóa ñ hình thành các t p m $i v $i nh ng l )i gi #i t ,t h ơn, cu ,i cùng s ? tìm ñư c l)i gi #i t ,i ư u nh t. GA s d ng các thu t ng l y t 9 di tru y n h 'c: - M%t t p h p các l )i gi #i ñư c g'i là m %t l $p hay qu 0n th (population). - MEi l )i gi #i ñư c bi u di Dn b :i m %t nhi Dm s @c th hay các th (chromosome)[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 47 - Nhi Dm s @c th ñư c t(o thành t 9 các gien. M %t quá trình ti /n hóa ñư c th&c hi n trên m %t qu 0n th t ươ ng ñươ ng v $i s & tìm ki /m trên không gian các l )i gi #i có th c a bài toán. Quá trình tìm ki /m này luôn ñòi h Ai s & cân b 4ng gi a hai m c tiêu: Khai thác l )i gi #i t ,t nh t và xem xét toàn b % không gian tìm ki /m. GA th &c hi n tìm ki /m theo chi u h ư$ng b 4ng cách duy trì t p h p các l )i gi #i có th và khu y /n khích s & hình thành và trao ñ!i thông tin gi a các h ư$ng. T p l )i gi #i ph #i trãi qua nhi u b ư$c ti /n hóa, t (i m Ei th / h , m %t t p m $i các cá th ñư c t(o ra, và có ch 8a các ph 0n c a nh ng cá th thích nghi nh t trong th / h c ũ. ð. ng th )i, gi #i thu t di truy n c ũng khai thác m %t cách có hi u qu # thông tin tr ư$c ñó ñ su y xét trên ñi n hình tìm ki /m m $i, v $i mong mu ,n có ñư c s& c #i thi n qua t 9ng th / h . Nh ư v y, các ñ<c tr ưng ñư c ñánh giá t ,t s ? có c ơ h %i phát tri n và các tính ch t x u (không thích nghi v $i môi tr ư)ng) s ? có xu h ư$ng bi /n m t. Gi #i thu t di truy n t !ng quát ñư c mô t # nh ư sau: 1 PROCEDURE GeneticAlgorithm; 2 BEGIN 3 T:=0; 4 Kh :i t (o l $p P(t); 5 ðánh giá l $p P(t); 6 While not (ð i u_ki n_k /t_thúc) do 7 Begin 8 t:=t+1; 9 Ch 'n l 'c P(t) t 9 P(t-1); 10 K /t h p các cá th c a P(t); 11 ðánh giá l $p P(t); 12 End; 13 END ; Trong ñó: - T p h p các l )i gi #i ban ñ0u ñư c kh :i t (o ng "u nhiên. - Trong vòng l <p th 8 t, GA xác ñ*nh t p các nhi Dm s @c th },...,,{)(21 tnttxxxtP = b4ng cách ch 'n l &a các nhi Dm s @c th thích nghi h ơn là t 9 P(t-1). M Ei nhi Dm s @c th tixñư c ñánh giá ñ xác ñ*nh ñ% thích nghi c a nó và m %t s , thành viên c a P(t) l (i ñư c tái s #n xu t nh ) các toán t Lai ghép và ð%t bi /n. Khi áp d ng GA ñ gi #i quy /t các bài toán c th , ph #i làm rõ các v n ñ sau: (1) Ch 'n cách bi u di Dn di tru y n nào ñ,i v $i nh ng l )i gi #i có th c a bài toán? (2) T (o t p l )i gi #i ban ñ0u nh ư th / nào? (3) Xác ñ*nh hàm ñánh giá ñ ñ ánh giá m 8c ñ% t thích nghi c a các cá th . (4) Xác ñ*nh các toán t di tru y n ñ s#n sinh ra con cháu. (5) Xác ñ*nh giá tr * c a các tham s , mà GA s d ng nh ư kích th ư$c các t p l )i gi #i, xác su t áp d ng các toán t di truy n,…[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 48 II.4.5.3. Các toán t di truy n: Các cá th trong gi #i thu t di truy n là các chu Ei bit ñư c t(o b :i vi c c @t dán các chu Ei bit con. M Ei chu Ei bit ñ(i di n cho m %t t p các thông s , trong không gian tìm ki /m, nên ñư c g'i là l )i gi #i tìm n ăng c a bài toán t ,i ưu. T 9 m %t chu Ei bit ta gi #i mã ñ tính l (i t p các thông s ,, sau ñó tính ñư c giá tr * c a hàm m c tiêu. T 9 ñ ó, giá tr * hàm m c tiêu ñư c bi/n ñ! i thành giá tr * ñ o phù h p c a t 9ng chu Ei. Qu 0n th ban ñ0u ñư c kh :i t (o ng "u nhiên, sau ñó ti /n hóa t 9 th / h này sang th / h khác b 4ng các toán t di truy n (t !ng s , chu Ei trong m Ei qu 0n th là không thay ñ!i). Có 3 toán t di tru y n ñơ n gi #n là: - Tái t (o. - Lai ghép. - ð% t bi /n. a) ð ánh giá ñ% thích nghi c a cá th và phép tái t (o M Ei bài toán trong th &c t / có các ñi u ki n ràng bu %c khác nhau ñ,i v $i l )i gi #i. Quá trình tìm ki /m l )i gi #i chính là quá trình ti /n hóa mà : m Ei b ư$c, c 0n ph #i l &a ch 'n các cá th thích nghi h ơn ñ tái s #n xu t : th / h sau b 4ng phép tái t ( o. ð ñ ánh giá các l )i gi #i, ng ư)i ta xây d &ng hàm thích nghi Fitness(). Tái t ( o là quá trình sao chép các chu Ei (các cá th ) t 9 th / h tr ư$ c sang th / h sau theo giá tr * c a hàm thích nghi (còn g 'i là hàm m c tiêu hay hàm s 8c kh Ae). Toán t này mô ph Ang theo h 'c thuy /t c a Darwin, ch C có các cá th kh Ae m $i có c ơ h %i s ,ng sót và ñóng góp con cháu vào các th / h sau. Hàm thích nghi ñư c xây d &ng nh ư sau: - Xét l )i gi #i P có n cá th , v $i m Ei cá th hi thu%c P, tính ñ% thích nghi Fitness(h i). - Xác su t ch 'n cá th hi ñ tái s #n xu t ñư c xác ñ*nh b :i công th 8c: ∑==nj jiihFitness hFitnessh1 )( )()Pr( (CT-II-15) - T(i m Ei b ư$ c ti /n hóa, các cá th ñư c ch 'n tái t (o là các cá th có xác su t Pr() cao, ñi u này cho phép t (o ra th h sau có ñ% thích nghi t ,t h ơn th / h tr ư$ c. Fitness() còn ñư c dùng ñ xác ñ*nh ñi m d 9ng c a quá trình tìm ki /m l )i gi #i khi ñã ñ( t ñư c ñ% thích nghi ch p nh n ñư c. b) Lai ghép (Crossover) Các cá th trong qu 0n th sau khi ñã tái t (o s ? ñư c ch 'n lai ghép v $i nhau. Toán t lai ghép ñư c coi là toán t di truy n quan tr 'ng nh t, nó k /t h p các ñ<c tr ưng c a các cá th b , m M ñ t(o ra hai cá th con b 4ng cách tráo ñ!i các ño (n gien t ương 8ng trên hai cá th cha m M. Phép lai ghép ch 'n nh "u nhiên hai chu Ei b t kì trong qu 0n th sau khi ñã th &c hi n táo t (o, ñ.ng th )i sinh ra m %t s , ng "u nhiên, n /u nh A h ơn xác su t [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 49 ghép pc thì th&c hi n lai ghép, ng ư c l(i ch C th &c hi n sao chép ñơn gi #n hai chu Ei vào qu 0n th m $i. Phép lai ghép hai chu Ei th &c hi n tráo ñ!i hai ño (n mã cho nhau, r .i ñư a hai chu Ei k /t qu # vào m %t qu 0n th m $i. c) ð% t bi /n (Mutation) Tái t (o và lai ghép ch C t (o ra các chu Ei m $i ch 8 không ñem l (i cho qu 0n th m %t thông tin m $i. Phép ñ%t bi /n ng ăn ng 9a kh # n ăng GA ch C tìm ki /m trên m %t vùng c c b % và k /t qu # ch C là c &c tr * ñ* a ph ương. Toán t ñ% t bi /n s ? thay ñ!i ng "u nhiên m %t bit thông tin c a m %t chu Ei v $i xác su t ñ% t bi /n pm. Xác su t ñ% t bi /n th hi n m 8c ñ% th ư)ng xuyên ñư c th&c hi n c a toán t ñ% t bi /n ph #i ñ nh A vì th &c t / toán t ñ% t bi /n là toán t tìm ki /m ng "u nhiên. V $i ph ương pháp mã hóa chu Ei bit, m %t bit thông tin A n /u b * ñ% t bi /n ñư c bi/n ñ! i b4ng công th 8c ñơ n gi #n: A=1-A. Ba toán t tái t (o, lai ghép và ñ%t bi /n ñư c ti/n hành l <p ñi l <p l (i cho ñ/n khi các chu Ei con chi /m toàn b % qu 0n th m $i. Qu 0n th m $i bao g .m các cá th ch a ba lo (i: Lai ghép nh ưng không ñ%t bi /n, b * ñ% t bi /n sau khi lai ghép và không lai ghép c ũng không ñ%t bi /n mà ch C ñơ n thu 0n là sao chép l (i. Nh ư v y, trong m %t gi #i thu t di tru y n ñơ n gi #n, chúng ta c 0n xác ñ*nh các thông s , sau: - S, các cá th trong qu 0n th n. - Xác su t lai ghép pc. - Xác su t ñ% t bi /n pm. - ð% g,i c a qu 0n th G. Ba thông s , ñ0 u r t d D hi u và ñã ñư c nh @c ñ/ n. Còn ñ% g,i G ñư c tác gi # De Jong ñưa vào n ăm 1975, ý ngh ĩa c a nó là cho phép qu 0n th m $i ch 8a m %t ph 0n c a qu 0n th c ũ: V $i G=1, t t c # các cá th m $i ñ u ñư c sinh ra b :i các toán t c a gi #i thu t di tru y n, v $i 0<G<1, s ? có G*n cá th ñư c ñư a ra tr &c ti /p t 9 qu 0n th c ũ sang qu 0n th m $i. II.4.5.4. Nh n xét: GA là m %t gi #i thu t l <p nh 4m gi #i quy /t các bài toán tìm ki /m, nó khác v $i các th t c t ,i ưu thông th ư)ng : nh ng ñi m c ơ b #n sau: - Gi#i thu t di truy n làm vi c v $i b % mã c a t p thông s , ch 8 không làm vi c tr &c ti /p v $i giá tr * c a các thông s ,. - Gi#i thu t di tru y n tìm ki /m song song trên m %t qu 0n th ch 8 không tìm ki /m t 9 m %t ñi m, m <t khác, nh ) áp d ng các toán t di truy n, nó s ? trao ñ!i thông tin gi a các ñi m, nh ư v y s ? gi #m b $t kh # n ăng k /t thúc t (i m %t ñi m c &c ti u c c b % mà không tìm th y c &c ti u toàn c c. - Gi#i thu t di truy n ch C s d ng thông tin c a hàm m c tiêu ñ ñ ánh giá quá trình tìm ki /m ch 8 không ñòi h Ai các thông tin b ! tr khác. - Các lu t chuy n ñ! i c a gi #i thu t di tru y n mang tính xác su t ch 8 không mang tính ti n ñ* [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 50 II.4.6. M$ng neuron nhân t $o (Neural networks): II.4.6.1. Gi $i thi u: M (ng neuron nhân t (o là m %t mô ph Ang x lý thông tin, ñư c nghiên c 8u ra t 9 h th ,ng th 0n kinh c a sinh v t, gi ,ng nh ư b % não ñ x lý thông tin. Nó bao g . m s , lư ng l $n các m ,i g @n k /t c p cao ñ x lý các y /u t , làm vi c trong m ,i liên h gi #i quy /t v n ñ rõ ràng. ANNs gi ,ng nh ư con ng ư)i, ñư c h'c b :i kinh nghi m, l ưu nh ng kinh nghi m hi u bi /t và s d ng trong nh ng tình hu ,ng phù h p. ð0u tiên ANN ñư c gi $i thi u n ăm 1943 b :i nhà th 0n kinh h 'c Warren McCulloch và nhà logic h 'c Walter Pits. Nh ưng v $i nh ng k - thu t trong th )i gian này ch ưa cho phép h ' nghiên c 8u ñư c nhi u. Nh ng n ăm g 0n ñây mô ph Ang ANN xu t hi n và phát tri n. II.4.6.2. C u trúc m (ng neuron: M Ei neuron (nút) là m %t ñơ n v * x lý thông tin c a m (ng neural, là y /u t , c ơ b #n ñ c u t (o nên m (ng neuron. Trong ñó: - xi: các tín hiu input - wkp: tr'ng s , c a t 9ng input - f(.): hàm ho (t ñ% ng - yk: k/t xu t c a Neural - b: thông s , # nh h ư:ng ñ/n ng ưKng ra c a output II.4.6.3. Mô hình và quá trình x lý trong m (ng neuron: a) Hàm truy n trong m (ng neuron: C u trúc c a m (ng neuron ch y /u ñư c ñ< c tr ưng b :i lo (i c a các neuron và m ,i liên h x lý thông tin gi a chúng. V c u trúc c a neuron, ch y /u ng ư)i ta quan tâm t $i cách t !ng h p các tín hi u ñ0 u vào, giá tr * ng ưKng t (i m Ei neuron và các hàm tru y n. Hàm tru y n xác ñ*nh m 8c ñ% liên k /t bên trong các neuron. Hàm truy n có nhi m v t(o m 8c kích thích c a neuron, t 9 ñ ó s ? làm h ưng ph n ho <c 8c ch / các neuron khác trong m (ng. Trong lý thuy /t m (ng neuron, phép t !ng h p tín hi u ñ0 u vào c a neuron I có m tín hi u ñ0 u vào xj thư) ng ñư c ký hi u: ),...,,(;211 i miii jmj ji jiwwwwxwnet ==∑= (CT-II-16) wk1 wk2 wk3 ∑ F(.) Output yk b Hình II-23. Cu trúc c a m t m ng [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 51 Tín hi u ra t (i neuron i th ư)ng ký hi u là outi ho<c fi, ñư c tính theo công th 8c sau v $i f là hàm truy n: ))(()( tnetftoutii = (CT-II-17) Có nhi u hàm truy n khác nhau ñư c s d ng trong t 9ng tr ư)ng h p c th , các hàm truy n nói chung nên th Aa mãn các tính ch t sau: - B* ch <n: xMxf∀≤,|)(| - ðơ n ñi u t ăng: 2121),()( xxxfxf >∀> - Kh # vi liên t c: f(x) có ñ(o hàm f’(x) và f’(x) là hàm liên t c. Trong th &c t /, khi xét các neuron, chúng ch C có th có hai tr (ng thái là b * kích ho (t ho <c không b * kích ho (t. Ngh ĩa là tín hi u ra c a m %t neuron c 0n ph #i ñ# m b #o sao cho có th nh n bi /t ñư c neuron ñó có b * kích ho (t hay không. Vì lý do ñó, hàm truy n ph #i th Aa mãn ñi u ki n tín hi u ra cu ,i cùng c a neuron ph #i liên t c và n 4m trong m %t gi $i h (n xác ñ*nh (có th là gi a 0 và 1). Sau ñây là m %t s , hàm truy n th ư)ng ñư c s d ng: Hàm ranh gi $i c 8ng (Hard-limiter): <≥=)(,0 )(,1)(θθxif xifxf Hàm ranh gi $i b t ñ, i x8ng: <− ≥=)(,1 )(,1)(θθxif xifxf Hàm Gauss: 2)(xexf −= Hàm Sigmoidal hay hàm logicstic (còn g 'i là hàm ch S): xexf−+=11)( b) C u trúc m (ng neuron: Trong mô hình m (ng neuron nhân t (o, các neuron ñư c n,i v $i nhau b :i các liên k /t neuron, m Ei liên k /t có m %t tr 'ng s , ñ< c tr ưng cho ñ<c tính kích ho (t hay 8c ch / gi a các neuron. ð.ng th )i, các neuron ñư c nhóm l (i v $i nhau theo c u trúc phân l $p, bao g .m: - L$p vào (input layer): Các nút trong l $p vào g 'i là nút vào, chúng mã hóa m "u ñư c ñư a vào m (ng x lý. Các neuron vào không x lý thông tin, ch C Hình II-3. Hàm [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 52 phân tán thông tin cho các nút khác (trên bi u ñ. chúng ñư c v? khác các nút >n và các nút ra ñ phân bi t gi a các nút có x lý và không x lý thông tin). - L$p >n (hidden layer): Các neuron : l $p >n g 'i là các nút >n vì chúng không th quan sát tr &c ti /p. Chúng t (o thành các mô hình toán h 'c phi tu y /n cho m (ng. - L$p ra (output layer): Các neuron trong l $p này g 'i là các nút ra, chúng có nhi m v ñư a thông tin ra thích nghi v $i m "u mà ng ư)i s d ng c 0n. M %t m (ng ñư c g'i là k /t n ,i ñ0 y ñ n/u t t c # các nút c a m %t l $p ñư c n , i v $i t t c # các nút li n k nó. Có nhi u lo (i k /t n ,i khác nhau: - K/t n ,i liên l $p là k /t n ,i gi a các nút trong các l $p khác nhau. - K/t n ,i trong l $p là k /t n ,i gi a các nút trong cùng m %t l $p. - T& k /t n ,i là k /t n ,i t 9 m %t nút t $i chính nó. - K/t n ,i siêu l $p là kêt n ,i gi a các l $p khác nhau (không k nhau). M %t k /t n ,i b c cao là m %t k /t n ,i v $i nhi u nút ñ0u vào. S , các nút ñ0u vào xác ñ*nh b c k /t n ,i và b c k /t n ,i c a m (ng là b c k /t n ,i b c cao nh t. c) Phân lo (i m (ng neuron: Phân lo (i theo ki u liên k /t neuron: - M(ng neuron truy n th Gng (feed-forward Neural netword): Trong m (ng, các liên k /t neuron ch C ñ i theo m %t h ư$ng t 9 l$ p vào ñ/n l $p ra, không t (o thành chu trình v $i các ñCnh là các neuron, các cung là các liên k /t gi a chúng. - M(ng h .i qu y: cho phép các liên k /t neuron t (o thành chu trình, có thông tin ñư c x lý theo hai chi u. Vì các thông tin ra c a các neuron ñư c truy n l (i cho các neuron ñã góp ph 0n kích ho (t chúng nên m (ng h .i quy còn có kh # n ăng l ưu gi tr (ng thái trong c a nó d ư$i d(ng các ng ưKng kích ho (t ngoài các tr 'ng s , liên k /t neuron. Hình II-25. M ng neuron truy n th %ng nhi u l &[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 53 - M(ng k /t n ,i ñ, i x 8ng và không ñ,i x 8ng: M (ng k /t n ,i ñ, i x 8ng là m (n th Aa mãn ñi u ki n: n /u có m %t ñư) ng n ,i t 9 nút i ñ/n nút j thì c ũng có m %t ñư) ng n ,i t 9 nút j ñ/n nút I và tr 'ng s , t ươ ng 8ng v $i hai ñư)ng n ,i này là b 4ng nhau:w ij=wji. Và m(ng không th Aa mãn ñi u ki n ñ, i x 8ng là m (ng k /t n ,i không ñ,i x8ng. Phân lo (i theo s , l $p: - M(ng ch C g .m m %t l $p vào và m %t l $p ra g 'i là m (ng ñơn l $p hay m (ng m %t l $p. - M(ng có t 9 m %t l $p >n tr : lên ñư c g'i là m (ng ña l $p hay m (ng nhi u l $ p. L$p vào L $p >n L $p ra neuron neuron neuron neuron input output Hình II-26. M ng neuron h i quy Hình II-27. M ng neuron ñơn l&p Hình II-28. M ng neuron ña l &p Hidden layer Output 1 Output 2 Output 3 Output [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 54 II.4.6.4. H 'c và lan truy n trong m (ng: 1) H c và t ng quát hóa M (ng neuron th &c hi n hai ch 8c n ăng quan tr 'ng là h 'c và t !ng quát hóa. H 'c là quá trình hi u ch Cnh các tham s , và các tr 'ng s , liên k /t trong m (ng ñ t,i thi u hóa sai s , v $i véc t ơ ñ0 u vào cho tr ư$c. Quá trình h 'c d 9ng khi th Aa mãn m %t tiêu chu >n d 9ng nào ñó, ch Gng h (n khi các tr 'ng s , c a m (ng t (o ra l Ei ñ nh A gi a ñ0 u ra mong ñ i và k /t qu # ñ0 u ra tính ñư c t9 m (ng. Bài toán h 'c có th ñư c mô t # nh ư: Cho t p m "u (Xi,Yi) v$i Xi và Yi là hai véc t ơ trong không gian m %t chi u ho <c nhi u chi u, c 0n xác ñ*nh b % tr 'ng s , W0 trên không gian tham s , computer(Xi, W0)=Yi. Quá trình h 'c ñư c th&c hi n theo hai b ư$c: Xác ñ*nh hàm giá tr * trên các tham s , và t ,i thi u hóa tham s , trong không gian c a các tham s ,. Xét v m <t c u trúc, h 'c ñư c chia làm hai lo (i là: h 'c tham s , và h 'c c u trúc. - H'c tham s ,: Là quá trình xác ñ*nh m %t t p h p tham s , W0 là các tr'ng s , t ,t nh t v $i m %t c u trúc m (ng c , ñ* nh. ð làm ñư c ñi u này, c 0n xây d &ng m %t hàm giá tr * d &a trên t p d li u Tmin và t p tr 'ng s , W. Hàm giá tr * có th là m %t hàm kh # vi b t k ỳ có tính ch t ñ( t ñ/ n c &c ti u khi các ñ0u ra Oi ñ úng b 4ng ñ0 u ra lý t ư:ng Yi ca t p m "u. Có th xây d &ng hàm giá tr * d ư$ i d (ng Ln- neuron nh ư sau: ∑∞≤≤−= pwithOypEpii1,)(1 (CT-II-18) V $i b % tham s , này, có th áp d ng m %t gi #i thu t tìm ki /m nào ñó trên không gian R m c a t p tr 'ng s ,. N /u thu ñư c k/t qu # t ,t v $i m %t c &c ti u toàn c c, ta s ? có m %t tham s , t ,t nh t cho m (ng. - H'c c u trúc: V $i h 'c tham s ,, ta gi # ñ* nh r 4ng m (ng có m %t c u trúc c , ñ* nh. Vi c h 'c c u trúc c a m (ng truy n th Gng g @n v $i yêu c 0u tìm ra s , l $p c a m (ng L và s , neuron trên m Ei l $p nj. Tu y nhiên, v$i các m (ng h .i quy còn ph #i xác ñ*nh thêm các tham s , ng ưKng θ ca các neuron trong m (ng. M %t cách t !ng quát là ph #i xác ñ*nh các tham s , P=(L,n1,…,nk, kθθ,...,1 ). Các k - thu t h 'c c a m (ng neuron ch C ra cách ch Cnh s a các tr 'ng s , liên k /t m (ng khi m %t m "u h 'c ñư c ñư a vào m (ng. Sau ñây, là các trình bày c th v các k - thu t h 'c: a) H 'c có giám sát: V $i các ph ương pháp h 'c có giám sát (supervised learning), khi ñ y, m (ng ñư c cung c p m %t t p mâu h 'c {(Xs,Ys)} theo nghĩa Xs là tín hiu vào, thì k /t qu # ra ñúng c a h ph #i là Ys. m Ei l 0n h 'c, véc t ơ tín hi u vào Xs ñư c ñư a vào m (ng, sau ñó so sánh s & sai khác gi a các k /t qu # ñ úng Ys v$i k /t qu # tính toán m (ng out. Sai s , này s ? ñư c dùng ñ hi u ch Cnh l (i các tr 'ng s , liên k /t trong m (ng. Quá trình c 8 ti /p t c cho ñ/n khi th Aa mãn m %t tiêu chu >n nào ñó. Có hai cách s d ng t p m "u h 'c: ho <c dùng các m "u l 0n l ư t, h /t m "u này ñ/n m "u khác; ho <c s d ng ñ.ng th )i t t c # các m "[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 55 b) H 'c t ăng c ư)ng: Ta th y trong k - thu t h 'c có giám sát, các véc t ơ ñ0 u ra ñư c bi/t m %t cách chính xác, nh ưng trong m %t s , tr ư) ng h p có ít thông tin, ch Gng h (n ch C có th nói là m (nh sinh Output quá l $n ho <c ch C ñ úng kho #ng 40%. Khi ñó, ch C có tín hi u ñánh giá là “True” ho <c False quay l (i m (ng, các th t c h 'c ñó g 'i là th t c h 'c t ăng c ư)ng. c) H 'c không có giám sát: Trong ph ương pháp h 'c không giám sát (unsepervised learning), ñ0u ra mong mu ,n c a m (ng không ñư c cho tr ư$c và m (ng ñư c trang b * kh # n ăng t & t ! ch 8c. M (ng không s d ng m ,i quan h l $p c a các m "u h 'c mà dùng thông tin k /t h p v $i nhóm các n ơ-ron ñ thay ñ!i các tham s , h 'c c c b % sao cho h p nh t. H th ,ng h 'c không giám sát ñư c chia các m "u vào các nhóm ho <c các l $ p quy /t ñ* n b 4ng cách ch 'n các neuron “chi /n th @ng” và thay ñ!i các tr 'ng s , t ươ ng 8ng c a chúng. Thông th ư)ng, vi c h 'c không giám sát dùng nhi u tham s , k - thu t h ơn h 'c có giám sát. X s ð0 u vào ANN w ð0u ra th &c t / Tính sai s , ð0 u ra mong mu ,n Ys Sai s , Xs ð0 u vào ANN w ð0u ra th &c t / Tính sai s , Tín hi u t ăng c ư)ng Tín hiu ñ ánh giá Xs ð0 u vào ANN w ð0 u ra th &c t / Hình II-4. S ơ ñ h c có giám sát Hình II-30. S ơ ñ hc t ăng c ưng Hình II-31. S ơ ñ hc không giám sá[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 56 Như v y, gi #i thu t h 'c là gi #i thu t xu t phát t 9 m %t t p m "u, qua quá trình hu n luy n ñ tìm ra b % tr 'ng s , liên k /t gi a các neuron, có th mô t # t !ng quát nh ư sau: - ð0 u vào: M %t t p m "u g .m n ph 0n t . - ð0 u ra: C u trúc m (ng và b % tr 'ng s , các liên k /t neuron. - Gi#i thu t: 1. Kh :i t (o tr 'ng s , c a m (ng, ñ<t i=1; 2. ðưa m "u I vào l $p vào c a m (ng; 3. S d ng thu t toán lan tru y n, nh n ñư c giá tr * các nút ra. N /u giá tr * ñ0 u ra c a m (ng ñ(t yêu c 0u th Aa mãn tiêu chu >n d 9ng thì k /t thúc. 4. S a ñ! i tr 'ng s , b 4ng lu t h 'c c a m (ng; 5. N /u i=n thì ñ<t l(i i=1, n /u không thì t ăng i len 1:i=i+1 Quay l (i b ư$ c 2. Có nhi u tiêu chu >n d 9ng quá trình h 'c, ví d : - Chu >n l Ei E nh A h ơn m %t ng ưKng cho tr ư$c: E<θ. - Các tr 'ng s , c a m (ng thay ñ!i nhi u sau khi hi u ch Cnh; θ<− oldijnewij ww. - Vic l <p l (i bão hòa, t 8c là s , l 0n v ư t quá m %t ng ưKng N cho tr ư$c. 2) Lan truy n trong m ng M (ng neuron lan tru y n thông tin t 9 l$p vào ñ/n l $p ra. Khi vi c lan truy n k /t thúc, thông tin t (i l $p ra chính là k /t qu # c a quá trình lan truy n. Gi #i thu t lan truy n ñư c mô t # nh ư sau: - ð0 u vào: M %t t p tín hi u vào. - ð0 u ra: K /t qu # t ươ ng 8ng v $i t p tín hi u vào - Gi#i thu t: 1. ðư a tín hi u vào l $p vào c a m (ng. 2. Tính m 8c tích c &c c a các nút trong m (ng. 3. V $i m (n tru y n th Gng: N /u m 8c tích c &c c a nút ra ñã bi /t thì k /t thúc. V $i m (ng ph #n h .i: N /u m 8c tích c &c c a nút ra b 4ng ho <c x p x C b 4ng h 4ng s , thì k /t thúc. N /u không thì quay l (i b ư$ c 2. II.4.6.5. Nh n xét: M (ng neuron là m %t công c h u hi u trong các mô hình tính toán thông minh v $i m %t s , ñ< c ñi m chính sau: - Cho phép xây d &ng m %t mô hình tính toán có kh # n ăng h 'c d li u cao: Ch C c 0n ñư a vào cho m (ng m %t t p d li u trong quá trình h 'c là m (ng có th phát hi n nh ng ràng bu %c d li u và áp d ng nh ng ràng bu %c này trong quá trình s d ng mà không c 0n có thêm các tri th 8c v mi n 8ng d ng. Kh # n 4ng này cho phép xây d &ng mô hình d li u khá d D dà[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 57 - X lý các quá trình phi tuy /n: M (ng có kh # n ăng x p x C nh ng ánh x ( phi tuy /n tùy ý nên có th gi #i ñư c nh ng bài toán phi tuy /n ph 8c t (p. Nó có th th &c hi n nhi u phép l 'c n 4m ngoài kh # n ăng c a nh ng b % l %c tuy /n tính thông th ư) ng. ð<c tr ưng này r t quan tr 'ng, ví d : trong x p x C m (ng, mi Dn nhi Du (ch p nh n nhi Du) và có kh # n ăng phân l $p. - Kh # n ăng c a các quá trình x lý song song và phân tán: Có th ñư a vào m (ng m %t l ư ng l $n các neuron liên k /t v $i nhau theo nh ng l ư c ñ. v$i ki /n trúc khác nhau. M (ng có c u trúc song song l $n, có kh # n ăng t ăng t ,c ñ% tính toán và hy v 'ng s ? ñ áp 8ng ñư c yêu c 0u c a nh ng h th ,ng c 0n ñ% chính xác cao h ơn nh ng h th ,ng truy n th ,ng. - M(ng neuron có kh # n ăng h 'c l Ei cao: C , g @ng b @t ch ư$c kh # n ăng x lý l Ei c a b % não, ñ bA qua các l Ei y và ti /p t c làm vi c, ñi u ch Cnh khi nh n tín hi u vào có m %t ph 0n thông tin b * sai l ch ho <c thi /u. - Kh # n ăng thích nghi và s & t! ch 8c: v ñ< c tr ưng này, ng ư)i ta ñ c p t $i kh # n ăng thích nghi và ñi u ch Cnh b n v ng d &a vào các thu t toán thích nghi và các quy t @c t & t! ch 8c. - Hơn n a, m <c dù có r t nhi u k - thu t và gi #i thu t ñư c s d ng trong khai phá d li u, m %t s , k - thu t còn ñư c k/t h p ñ s d ng có hi u qu #, song m (ng neuron v 0n có nh ng ưu ñi m ñáng chú ý nh ư: T & ñ% ng tìm ki /m t t c # các m ,i quan h có th gi a các nhân t , chính. Mô hình hóa t & ñ% ng các bài toán ph 8c t (p mà không c 0n bi /t tr ư$c m 8c ñ% ph 8c t (p. Có kh # n ăng chi /t xu t ra nh ng thông tin nhanh h ơn r t nhi u so v $i nhi u công c khác. II.4.7. Lut k +t h p (Association rule): II.4.7.1. Các ñ*nh ngh ĩa: 1) Bi u di n nh phân: Bi u di Dn nh * phân là m %t s & bi u di Dn các giá tr * c a giao d *ch b 4ng m %t b #ng nh * phân. T !ng s , c %t c a b #ng này b 4ng t !ng s , m <t hàng +1, c %t ñ0 u tiên là mã giao d *ch, các c %t còn l (i t ươ ng 8ng v $i m <t hàng. M Ei dòng t ương 8ng v $i m %t giao d *ch. N /u giao dich I ch 8a các m <t hàng (x,y,z) thì giá tr * c a các ô (i,x), (i,y) và (i,z) là s , 1, các ô còn l (i có giá tr * là s , 0. 2) Itemset và support count: G 'i I={i1, i2,…,id} là t p h p t t c # các m <t hàng (items). Và g 'i T={t1, t 2 ,…,tN} là t p h p các giao d *ch. M Ei giao d *ch t (i th )i gian ti ch8a m %t t p con c a t p I. Trong phân tích k /t h p, m %t t p h p ch 8a 0 ho <c n items ñư c g'i là itemset. N /u m %t itemset ch 8a k items thì ñư c g'i là k-itemset. M %t tính ch t quan tr 'ng c a itemset là support count. Support count c a m %t itemset ñư c ñ* nh ngh ĩa là t !ng s , giao d *ch ch 8a itemset ñó. Support count c a m %t itemset X ñư c tính b 4ng công th 8c sau: {}TttXtXiii∈⊆= ,|)(σ (CT-II-19) Trong ñó, |.| ký hi u cho s , ph 0n t c a t p h [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 58 3) Lu t k t h p: M Ei lu t k /t h p là m %t bi u th 8c suy di Dn có d (ng X->Y, v $i X và Y là hai itemset r )i nhau. S 8c m (nh c a lu t k /t h p ñư c ño b 4ng support và confidence. Support xác ñ*nh t C l mà m %t lu t th Aa cho m %t t p d li u cho tr ư$c. Confidence xác ñ*nh t p các item xu t hi n th ư)ng xuyên (frequently items) trong bi u th 8c Y xu t hi n trong các giao d *ch ch 8a bi u th 8c X. Công th 8c support và congidence ñư c tính nh ư sau: Support: NYXYXs )()(∪=→σ (CT-II-20) Confidence: )( )()(XYXYXcσσ∪=→ (CT-II-21) Trong ñó, N là t !ng s , giao d *ch Tính ch t quan tr 'ng c a support là : ch E m %t lu t k /t h p có giá tr * support th p ngh ĩa là có r t ít khi x #y ra tình hu ,ng theo s & suy di Dn c a lu t ñó hay nói cách khác các lu t k /t h p có support th p s ? không h u ích trong khi s d ng, c 0n ñư c lo(i b A. Confidence dùng ñ ñ o d % tin c y c a lu t k /t h p. N /u m %t lu t có ñ% tin c y cao thì có nhi u giao d *ch th Aa lu t hay nói cách khác m %t lu t k /t h p có confidence càng cao thì càng có giá tr * s d ng. II.4.7.2. Phát hi n lu t k /t h p: Cho tr ư$c t p giao d *ch T có N giao d *ch. Yêu c 0u tìm t t c # các lu t th Aa ñ i u ki n support>=minisup và confidence>=miniconf. Trong ñó minisup và miniconf là giá tr * support và confidence nh A nh t ñư c cho tr ư$c. Có 2 ph ương pháp ti /p c n vi c phát hi n lu t k /t h p: - M%t ph ương pháp ti /p c n ñ tìm các lu t k /t h p có tên g 'i “a brute-force approach” là tính giá tr * support và confidence cho t t c # các lu t k /t h p có th có và xóa ñi nh ng lu t có support<minisup ho <c confidence<miniconf. Ph ương pháp này t ,n nhi u th )i gian và tài nguyên vì ph #i li t kê t t c # các lu t có d items (d=1,2,3,…). T !ng s , lu t có th k /t xu t ñư c t9 m %t t p h p có d items là R ñư c tính nh ư sau: R=3d-2 d+1 (CT-II-22) - M%t cách ti /p c n khác ñư c s d ng r t nhi u trong các thu t toán phân tích là chia v n ñ gi #i quy /t : trên ra thành 2 v n ñ con nh ư sau: (1) Tìm các itemset có t 0n su t xu t hi n cao (frequent itemsets): M c ñích c a ph 0n này là tìm t t c # các itemset có support l $n h ơn ho <c b 4ng minisup. (2) Sinh lu t: M c ñích c a ph 0n này là sinh t t c # các lu t có confidence cao t 9 các frequent [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 59 II.4.7.3. Sinh các frequent itemset b 4ng nguyên lý “bi /t tr ư$c”: Vi c tìm các frequent itemsets b 4ng nguyên lý bi /t tr ư$c ñư c ti/n hành qua t 9ng b ư$c. B ư$c th 8 i (i>=2) s ? ñư c s d ng k /t qu # c a các b ư$c tr ư$c ñó (b ư$ c i-1) ñ lo (i b A nh ng infrequent itemsets. B ư c kh i t o (i=1): - Lit kê các t p h p g .m 1 item ñư c g'i là 1-itemsets. - Tính support count cho t 9ng 1-itemset. - Lo (i b A các 1-itemsets không th Aa minisup. - K/t qu # cu ,i cùng c a b ư$c này là các 1-itemsets th Aa ñi u ki n minisup. B ư c i=2: - Xu t phát t 9 k /t qu # c a b ư$c th 8 i-1 - Lit kê các t p 2-itemsets d &a trên các t p 1-itemsets là k /t qu # c a b ư$ c 1. - Tính support count cho t t c # các 2-itemsets. - Lo (i b A các 2-itemsets không th Aa ñi u ki n minisup. - K/t qu # cu ,i cùng c a b ư$c này là các 2-itemsets th Aa ñi u ki n minisup. B ư c th i>=3: - L p l (i gi ,ng nh ư b ư$ c 2 cho ñ/n khi nào không tìm ñư c k/t qu # là các k-itemsets (v $i k là t !ng s , items) ho <c không tìm ñư c itemset nào th Aa ñi u ki n minisup. II.4.7.4. Sinh các itemsets 8ng viên và c @t nhánh: G 'i X={i1, i2,…,ik} là m%t candidates m $i g .m k ph 0n t c 0n xét. Thu t toán này c 0n ki m tra t t c # các t p con g .m k-1 ph 0n t c a X-{ij} v$i j=1,2,…,k. N /u t .n t (i m %t t p h p con c a nó không th Aa ñi u ki n minisup thì t p X s ? b * lo (i b A ngay l <p t 8c. Có r t nhi u cách sinh ra các candidate itemset. M %t thu t toán hi u qu # ph #i ñ# m b #o các yêu c 0u sau: (1) Không sinh ra các itemsets không c 0n thi /t. M %t itemsets ñư c g'i là không c 0n thi /t ñư c sinh ra n /u t .n t (i ít nh t 1 t p con c a nó không th Aa ñi u ki n minisup. (2) Ph #i ñ# m b #o sinh ra t t c # các itemsets c 0n thi /t. (3) ð# m b #o không l <p l (i các itemsets. M %t s , ph ương pháp ñư c xây d &ng ñ#m b #o các yêu c 0u trên: Phương pháp “brute-force”: - Sinh t t c # các candidates có k ph 0n t . - Lo (i b A các candidates không c 0n thi /t. Phương pháp “Fk-1xF1”: - Sinh t t c # các candidates có k ph 0n t t9 k /t qu # c a b ư$c th 8 k-1 và k /t qu # c a b ư$c [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 60 - Lo (i b A các candidates không th Aa minisup. Phương pháp “Fk-1xFk-1”: - S d ng k /t qu # c a b ư$c l<p th 8 k-1. - Tr%n t 9ng c <p itemsets có k-2 ph 0n t ñ0 u gi ,ng nhau. - Lo (i b A các candidates không th Aa minisup. II.4.7.5. ð/m support: ð/ m support count là quá trình xác ñ*nh t 0n su t xu t hi n c a m Ei candidate itemset. M %t cách làm ñơn gi #n là so sánh t 9ng candidate itemset v $i t 9 ng giao d *ch trong t p h p các giao d *nh ban ñ0u. Cách làm này ñòi h Ai t ,n nhi u th )i gian cho vi c so sánh. M %t ph ương pháp ñư c dùng ñ ñ/ m các support c a các candidate itemsets h u hi u là s d ng cây b ăm. Trong gi #i thu t bi /t tr ư$c, các candidate itemset ñư c chia thành nhi u nhóm khác nhau và ñư c lưu tr trong m %t cây có tên là cây b ăm (Hash tree). Trong su ,t quá trình ñ/m support, các itemsets ñư c ch 8a trong m Ei giao d *ch ñư c lưu vào trong các ô phù h p. V $i cách làm này, ch C c 0n so sánh các candidate itemsets n 4m cùng m %t ô. Ví d : Xét m %t giao d *ch ch 8a 5 item ñư c ñánh s , là 1,2,3,5 và 6. Hình II-32. Minh h a cách li t kê các 3-itemsets t ! giao d ch {1,2,3,5,6} II.4.7.6. Sinh t p lu t k /t h p: Sau khi có ñư c t p h p các item th Aa ñi u ki n minisup (frequent itemset), chúng ta s ? ñ i xây d &ng t p h p này thành các lu t c th . M Ei t p h p frequent itemset có th sinh t ,i ña 2 k- 2 lu t k /t h p. M %t lu t k /t h p ñư c sinh ra b 4ng cách phân t p frequent itemset Y ra thành 2 t p con r )i nhau (X và Y-X) sau cho X->(Y-X) th Aa ñi u ki n [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 61 a) C @t nhánh d &a vào ñ% tin c y: ð* nh lý: N /u m %t lu t k /t h p có d (ng X->Y-X không th Aa ñi u ki n miniconf thì t t c # các lu t k /t h p có d (ng X’->Y-X’ v $i X là t p con c a X ñ u không th Aa minisup. b) Sinh lu t k /t h p trong thu t toán bi /t tr ư$c: ð0 u tiên, t t c # các lu t có ñ% tin c y cao ph #i là lu t ch C có m %t item : v / bên ph #i (rule consequence). Các lu t này ph #i ñư c sinh ra tr ư$c sau ñó ñư c s d ng ñ sinh ra các lu t 8ng viên (candidate rules) ti /p theo. M %t lu t m $i ñư c sinh ra b 4ng các lu t ban ñ0u : 2 v /. V / trái thì l y ph 0n gi ,ng nhau (phép giao), còn v / ph #i thì l y c # 2 (phép h p). II.4.7.7. Các lo (i bài toán: Bài toán 1 : Tìm t t c # các t p m c mà có ñ% hE tr l $n h ơn ñ% hE tr t ,i thi u do ng ư)i dùng xác ñ*nh. Các t p m c tho # mãn ñ% hE tr t ,i thi u ñư c g'i là các t p m c ph ! bi /n. Bài toán 2 : Dùng các t p m c ph ! bi /n ñ sinh ra các lu t mong mu ,n. Ý t ư: ng chung là n /u g 'i ABCD và AB là các t p m c ph ! bi /n, thì chúng ta có th xác ñ*nh lu t n /u AB => CD gi l (i v $i t F l ñ% tin c y: )sup( )sup(ABABCDconf = (CT-II-23) N /u confidence ≥ miniconf thì lu t ñư c gi l(i (lu t này s ? tho # mãn ñ% hE tr t, i thi u vì ABCD là ph ! bi /n). II.4.7.8. Các tính ch t liên quan ñ,i v$i t p m c ph ! bi /n Tính ch t 1 (ð% hE tr c a t p con): V $i A và B là t p các m c, n /u A ⊆ B thì sup(A) ≥ sup(B) . ð i u này là rõ ràng vì t t c # các giao tác c a D h E tr B thì c ũng h E tr A. Tính ch t 2: M %t t p ch 8a m %t t p không ph ! bi /n thì c ũng là t p không ph ! bi /n. N /u mt m c trong B không có ñ h" tr t i thi u trên D ngh ĩa là sup(B)< minisup thì m %t t p con A c a B s ? không ph #i là m %t t p ph ! bi /n vì sup(B) ≤ sup(A) < minisup (theo tính ch t 1). Tính ch t 3: Các t p con c a t p ph ! bi /n c ũng là t p ph ! bi /n. N /u m c B là m c ph ! bi /n trên D, ngh ĩa là sup(B) ≥ minisup thì m 'i t p con A c a B là t p ph ! bi /n trên D vì sup(A) ≥ sup(B) > minisup. II.4.7.9. Các tính ch t liên quan ñ,i v$i lu t k /t h p: Tính ch t 1:( Không h p các lu t k /t h p) N /u có X →Z và Y →Z trong D thì không nh t thi /t X ∪Y→ Z là ñúng. Xét tr ư)ng h p X ∩Z = ∅ và các tác v trong D h E tr Z n /u và ch C n /u chúng h E tr m Ei X ho <c Y, khi ñó lu t X ∪Y→ Z có ñ% hE tr 0%. T ươ ng t & : X →Y ∧ X →Z ⇒ X→Y∪ Z Tính ch t 2:(Không tách lu t) N /u X ∪Y→ Z thì X →Z và Y →Z ch ưa ch @c x #y [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 62 Tính ch t 3: (Các lu t k /t h p không có tính b @c c 0u) N /u X →Y và Y →Z, chúng ta không th suy ra X →Z. Tính ch t 4: N /u A →(L - A) không tho # mãn ñ% tin c y c &c ti u thì lu t B →(L -B) c ũ ng không tho # mãn, v $i các t p m c L,A,B và B ⊆ A ⊂ L. II.4.7.10. Các thu t toán xây d &ng lu t k /t h p: a) Thu t toán Apriori: Gi $i thi u bài toán: Bài toán ñư c phát bi u: Tìm t có ñ% hE tr s th Aa mãn s ≥ s0 và ñ% tin c y c ≥ c0 (s0, c0 là hai ngư#ng do ng ư$i dùng xác ñnh và s0=minisupp, c0 =miniconf) . Ký hi u: Lk t p các t p k - m c ph ! bi /n, Ck t p các t p k-m c 8ng c (c # hai t p có: t p m c và ñ% hE tr ). Bài toán ñ<t ra là: 1) Tìm t t c # các t p m c ph ! bi /n v $i minisup nào ñó. 2) S d ng các t p m c ph ! bi /n ñ sinh ra các lu t k /t h p v $i ñ% tin c y miniconf nào ñó. Quá trình th &c hi n (duy t): (1) Th &c hi n nhi u l 0n duy t l <p ñi l <p l (i, trong ñó t p (k-1) - m c ñư c s d ng cho vi c tìm t p k-m c. L 0n th 8 nh t tìm t t c # các ñ% hE tr c a các m c, xác ñ*nh m c ph ! bi /n (m c tho # mãn ñ% hE tr c &c ti u-minisup). Gi # s tìm ñư c L1-mc ph ! bi /n. (2) Các l 0n duy t còn l (i: B @t ñ0 u k /t qu # tìm ñư c bư$c tr ư$c nó, s d ng các t p m c m "u (L1) sinh ra các t p m c ph ! bi /n ti m n ăng ( 8ng c )(gi # s L2), tìm ñ% hE tr th &c s &. M Ei l 0n duy t ta ph #i xác ñ*nh t p m c m "u cho l 0n duy t ti /p theo. (3) Th &c hi n l <p ñ tìm L3, ..., Lk cho ñ/n khi không tìm th y t p m c ph ! bi /n nào n a. Chú ý: ng d ng Lk-1 ñ tìm Lk bao g.m hai b ư$c chính: (1) B ư$ c k /t n ,i: tìm Lk là t p k-m c t ương 8ng ñư c sinh ra b :i vi c k /t n , i Lk-1 v$i chính nó cho k /t qu # là Ck. Gi# s L1, L2 thu%c Lk-1. Ký hiu Lij là m c th 8 j trong Li. ði u ki n là các t p m c hay các m c trong giao dch có th t . (2) B ư$ c k /t n ,i nh ư sau: Các thành ph 0n Lk-1 k/t n ,i (n /u có chung k-2-m c ñ0 u tiên) t 8c là:(L1[1]=L2[1]) ∩ (L1[2]=L2[2]) ∩ ... ∩ (L1[k-2]=L2[k-2]) ∩ (L 1[k-1]=L2[k-1]). (3) B ư$ c tCa: Ck là t p ch 8a Lk (có th là t p ph ! bi /n ho <c không) nh ưng t t c # t p k-m c ph ! bi /n ñư c ch 8a trong Ck. Bư$c này, duy t l 0n hai CSDL ñ tính ñ% hE tr cho m Ei 8 ng c trong Ck s? nh n ñư c [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 63 Thut toán Apriori Các kí hi u: L k: T p các k-m c ph ! bi /n (large k-itemset) (t 8c t p các itemset có sup t ,i thi u và có l &c l ư ng b 4ng k). M Ei ph 0n t c a t p này có 2 tr ư)ng: itemset và support-count. C k: T p các candidate k-itemset (t p các t p k-m c 8ng c viên). M Ei ph 0n t trong t p này c ũng có 2 tr ư)ng itemset và support-count. N i dung thu t toán Apriori ñư c trình bày nh ư sau: 1 Input: T p các giao d *ch D, ng ưKng support t ,i thi u minisup 2 Output: L- t p m c ph ! bi /n trong D 3 Method: 4 L1={large 1-itemset (t p 1- m c ph ! bi /n)} //tìm t t c # các t p m c ph ! bi /n: nh n ñư c L1 5 for (k=2; Lk-1 ≠ ∅ ; k++) do 6 begin 7 Ck=apriori-gen(Lk-1); //sinh ra t p 8ng c viên t 9 Lk-1 8 for (mEi m %t giao d *ch T∈D) do 9 begin 10 CT = subset(Ck, T); //l y t p con c a T là 8ng c viên trong Ck 11 for (mEi m %t 8 ng c viên c∈ CT) do 12 c.count++; //t ăng b % ñ/ m t 0n xu t 1 ñơn v * 13 end; 14 Lk = {c ∈ Ck| c.count ≥ minisup} 15 end; 16 return ∪kLk +) Trong thu t toán này, giai ño(n ñ0 u ñơ n gi #n ch C là vi c ñ/ m support cho các m c(item). ð xác ñ*nh t p 1-m c ph ! bi /n (L1), ngư)i ta ch C gi l (i các m c (item) mà sup c a nó l $n h ơn ho <c b 4ng minisup. +) Trong các giai ño (n th 8 k sau ñó (k>1), m Ei giai ño(n g .m có 2 pha. Tr ư$ c h /t các large(k-1)-itemset (t p k-1- m c ph ! bi /n) trong t p Lk-1ñư c s d ng ñ sinh ra các candidate itemset (t p 8ng c viên) Ck, b4ng cách th &c hi n hàm Apriori_gen. +) Ti/p theo CSDL D s ? ñư c quét ñ tính support cho m Ei 8ng viên trong C k. ð vic ñ/ m ñư c nhanh, c 0n ph #i có m %t gi #i pháp hi u qu # ñ xác ñ*nh các 8 ng viên trong Ck là có m<t trong m %t giao d *ch T cho tr ư$c. V n ñ sinh t p candidate (t p 8ng c ) c a Apriori – Hàm Apriori_gen: 1 Input: t p m c ph ! bi /n Lk-1 có kích thư$c k-1 2 Output: t p 8ng c viên Ck 3 Method: 4 function apriori-gen(Lk-1: t p m c ph ! bi /n có kích th ư$c k-1) 5 Begin 6 For (mEi L1 ∈ Lk-1) [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 64 7 For (mEi L2 ∈ Lk-1) do 8 If ((L1[1]=L2[1]) ∩ (L1[2]=L2[2]) ∩ ... ∩ (L1[k-2]=L2[k-2]) ∩ (L1[k-1]=L2[k-1])) then 9 c = L1 ⊕ L2; // k/t n ,i L1 v$i L2 sinh ra 8ng c viên c 10 If has_infrequent_subset(c, Lk-1) then //có t p con kh ! ph ! bi /n c a c trong Lk-1 11 remove (c) // b ư$c tCa (xoá 8ng c viên c) 12 else Ck = Ck ∪ {c}; k /t t p c vào Ck 13 end ; 14 Return Ck; 15 End ; Hàm Apriori_gen v $i ñ, i s, là Lk-1(t p các large(k-1)-itemset) s ? cho l (i k /t qu # là m %t superset, t p c a t t c # các large k – itemset. S ơ ñ. sau là thu t toán cho hàm này. V$i n %i dung trên, ta th y hàm này có 2 b ư$c: - B ư$c n ,i (join step) - B ư$c c @t t Ca (prune step) Hàm Subset (trong b ư$c tCa) Các t p 8ng c viên Ck ñư c lưu tr trong m %t cây b ăm: +) Nút lá c a cây b ăm ch 8a danh sách m %t t p m c và ñ/m +) Các nút trong ch 8a : trong b #ng b ăm -> Hàm subset: tìm t t c # các 8ng c viên ñư c ch 8a trong giao tác. Hàm ki m tra t p con k-1 m c c a 8ng c viên k-m c không là t p ph ! bi /n: 1 function has_infrequent_subset(c: 8ng c viên k-m c; Lk-1 t p ph ! bi /n k-1 m c) 2 Begin //s d ng t p m c ph ! bi /n tr ư$c 3 For (mEi t p con k-1 m c s c a c) do 4 If s ∈ Lk-1 then return TRUE; 5 End; b) M %t s , bi /n th c a thu t toán Apriori: (1) Gi #i thu t AprioriTID là ph 0n m : r %ng theo h ư$ng ti /p c n c ơ b #n c a gi #i thu t Apriori. Thay vì d &a vào c ơ s : d li u thô gi #i thu t AprioriTID bi u di Dn bên trong m Ei thao tác b :i các 8ng viên hi n hành. 1 L 1= {Large 1-itemset}; 2 C’1 = Database D; 3 for (k=2; Lk-1 ≠ ∅ ; k++) do 4 Begin 5 Ck = apriori_gen (Lk-1); 6 C’k = ∅ ;[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 65 7 for t t c # t ∈ C’k-1 do 8 begin // xác ñ*nh t p 8ng viên trong Ck ch8a trong giao d *ch v $i ñ* nh //danh t. Tid (Tran saction Code) 9 Ct = {c ∈ Ck | (c-c[k]) ∈ t.Set_of_ItemSets ^ (c-c[k-1] ∈ t.Set_of_ItemSets } 10 for nhng 8ng viên c ∈ Ct do c.count ++; 11 if (Ct≠∅) then C’k+= < t.Tid, Ct > 12 end 13 Lk = {c ∈ Ck | c.count ≥ minsup }; 14 End 15 return = ∪kLk; Thu t toán này c ũng s d ng hàm apriori_gen ñ sinh ra các t p 8ng c viên cho m Ei giai ño(n. Nh ưng thu t toán này không dùng CSDL D ñ ñ/ m các support v $i các giai ño(n k > 1 mà s d ng t p C’k. MEi ph 0n t c a C’k có d(ng <Tid, {X k}>, trong ñó m Ei Xk là m%t t p ph ! bi /n k_itemset ti m n ăng trong giao d *ch Tid. Khi k = 1, C’k tươ ng 8ng v $i D, trong ñó m Ei item i ñư c coi là m %t itemset {i}. V $i k>1, C’k ñư c sinh ra b :i C’k+= < t.Tid, Ct >. Ph0n t c a C’k t ươ ng 8ng v $i giao d *ch t là <t.Tid, {c ∈ | c ch 8a trong t}>. N /u m %t giao d *ch không ch 8a b t k ỳ t p 8ngviên k_itemset nào thì C’k s? không có m %t ñi m vào nào cho giao d *ch này. Do ñó, s , l ư ng ñi m vào trong C’k có th nh A h ơn s , giao d *ch trong CSDL, ñ<c bi t v $i k l $n. H ơn n a, v $i các giá tr * k khá l $n, m Ei ñ i m vào có th nh A h ơn giao d *ch t ương 8ng vì m %t s , 8 ng viên ñã ñư c ch 8a trong giao d *ch. Tuy nhiên, v $i các giá tr * k nh A, m Ei ñi m vào có th l $n h ơn giao d *ch t ương 8ng vì m %t ñi m vào trong C’k bao g.m t t c # các 8ng viên k_itemset ñư c ch 8a trong giao d *ch. (2) Gi #i thu t AprioriHybrid k /t h p c # hai h ư$ng ti /p c n trên. Ngoài ra còn có m %t s , các gi #i thu t t &a Apriori(TID), chúng ñư c ñ* nh h ư$ng ñ cài tr &c ti /p trong SQL. (3) Gi #i thu t DIC là m %t bi /n th khác n a c a gi #i thu t Apriori. Gi #i thu t DIC làm gi #m ñi kho #ng phân bi t nghiêm ng <t gi a vi c ñ/ m và vi c phát sinh các 8ng viên. B t k ỳ 8 ng viên nào t $i ñư c ng ưKng minsupp, thì gi #i thu t DIC b @t ñ0 u phát sinh thêm các 8ng viên d &a vào nó. ð th&c hi n ñi u này gi #i thu t DIC dùng m %t prefix-tree (cây ti n t ,). Ng ư c v $i hashtree, m Ei nút (nút lá ho <c nút trong) c a prefix-tree ñư c gán m %t 8ng viên xác ñ*nh trong t p ph ! bi /n. Cách s d ng c ũng ng ư c v $i hashtree, b t c 8 khi nào t $i ñư c m%t nút ta có th kh Gng ñ*nh r 4ng t p item ñã k /t h p v $i nút này trong giao tác ñó. H ơn n a, vi c xác ñ*nh ñ% hE tr và phát sinh 8ng viên kh $p nhau s ? làm gi #m ñi s , l 0 n du y t c ơ s : d li u. II.4.7.11. ng d ng: - ðư c s d ng trong vi c gi #i quy /t các v n ñ tư v n s @p x /p danh m c các hàng hóa mà khách hàng th ư)ng xuyên l &a ch 'n và liên quan v $i nhau d &a trên các t p d li u ban ñ[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 66 - Các website s d ng lu t k /t h p nh ư m %t l &a ch 'n theo nhu c 0u c a khách hàng, ph c v nhanh chóng trong vi c l &a ch 'n thông tin và hi n th * thông tin theo nhu c 0u khách hàng. - M%t s , khó kh ăn trong vi c xây d &ng lu t k /t h p ch y /u là n 4m : khâu thu th p d li u, ñ d li u chính xác thì c 0n m %t l ư ng d li u l $n ñ phân tích và ñư c c p nh t th ư)ng xu yê[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 67 Chương III : N - I DUNG NGHIÊN C U III.1. NGHIÊN C U V PH .N M M KHAI PHÁ D LI U Trong th &c t /, có r t nhi u ch ương trình ñư c s d ng nh 4m ph c v cho công vi c khai phá d li u nh ư: Mathlab, Excel, minitab, SQL Server,… là các công c khai phá d li u có b #n quy n. Bên c (nh ñó, c ũng không th không nh @c ñ/ n các công c ñư c phát tri n mi Dn phí nh ư: weka, Rapid miner, Tanagra,… góp ph 0n ph c v nhu c 0u tìm hi u v khai phá d li u. Trong quá trình nghiên c 8 u, chúng ta s ? ñ i sâu vào nghiên c 8u v ph 0n m m Tanagra. III.1.1. Gi i thi u Tanagra: Tanagra là m %t ph 0n m m khai phá d li u mi Dn phí, ph c v cho công vi c h ' c t p và nghiên c 8u. Nó là công c ph c v cho công vi c khai phá d li u t 9 phân tích d li u th ăm dò (exploratory), h 'c th ,ng kê (statistical learning), máy h ' c (machine learning) và vùng c ơ s : d li u (databases area). D & án v Tanagra là s & k / th 9a c a Sipina mà vi c th &c hi n các thu t toán h ' c có giám sát, ñ<c bi t là xây d &ng các t ương tác và hình #nh c a cây quy /t ñ* nh. Tanagra m (nh h ơn, nó ch 8a m %t s , ph ương pháp h 'c có giám sát, nh ư: phân nhóm, phân tích giai th 9a, th ,ng kê tham s , và phi tham s ,, association rules, l &a ch 'n tính n ăng (feature selection) và các thu t toán xây d &ng (construction algorithms). Tác gi # c a Tanagra và Sipina là Ricco Rakomalala – Phó giáo sư Khoa h ' c máy tính c a tr ư)ng ð(i h'c Lyon 2, Pháp. Ông là thành viên c a ERIC (Equipe de recherche en Ingénierie des Connaissance s – Nhóm nghiên c8u k F thu t ki /n trúc) do ñ(i h 'c Lyon t ! ch 8c nh 4m nghiên c 8u v máy tính và các 8 ng d ng c a nó. Tanagra là m %t d & án mã ngu .n m :, nh ư m 'i nhà nghiên c 8u có th truy c p vào mã ngu .n, và thêm vào các thu t toán riêng c a mình, nh ưng ph #i ñ. ng ý và tuân th gi y phép phân ph ,i ph 0n m m. M c ñích chính c a d & án Tanagra là ñ cho các nhà nghiên c 8u và sinh viên d D s d ng ph 0n m m khai phá d li u, phù h p v $i các ch C tiêu hi n t (i c a phát tri n ph 0n m m trong mi n này ( ñ<c bi t trong vi c thi /t k / GUI và cách s d ng nó), và cho vi c phân tích thi /t th &c và t !ng h p d li u. M c ñích th 8 hai c a Tanagra là ñ ñ xu t v $i các nhà nghiên c 8u m %t ki /n trúc cho phép h ' d D dàng thêm các ph ương pháp khai thác d li u c a riêng h ' , ñ so sánh k /t qu # c a h '. Nhi u tác ñ%ng c a Tanagra nh ư là n n t #n th nghi m nh 4m ñ cho h ' ñ i ñ/ n nh ng thi /t y /u c a công vi c c a h ', và ñ h' có th ñ, i phó v $i các ph 0n khó kh ăn trong vi c qu #n lý d li u. M c ñích th 8 ba và cu ,i cùng, trong vi c m $i làm quen v $i h ư$ng phát tri n, bao g .m trong vi c khuy /ch tán m %t ph ương pháp có th ñ xây d &ng các lo (i ph 0n m m. H ' c 0n t n d ng l i th / c a truy c p mi Dn phí mã ngu .n, ñ tìm các s @p x /p c a ph 0n m m này ñư c xây d &ng, các v n ñ c0n tránh, các b ư$c chính c a d & án, có các công c và th ư vi n mã ñ s d ng. B 4ng cách này, Tanagra có th ñư c coi nh ư là m %t công c nghi p v s ư ph (m cho vi c h 'c t p k - thu t l p trì[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 68 Tanagra không bao g .m t t c # s 8c m (nh c a các ph 0n m m th ương m (i trong l ĩnh v &c này nh ư: m %t t p h p nhi u ngu .n d li u, truy c p tr &c ti /p c ơ s : d li u và kho d li u (datawarehouses), làm s (ch d li u, t ương tác s d ng,... Tanagra có kh # n ăng t ương tác v $i Microsoft Office và Open Office. III.1.2. Tìm hiu v Tanagra: III.1.2.1. M : m %t 8 ng d ng và t #i t p tin: Có 2 các ñ m : ch ương trình và t #i t p tin: (1) Cách 1: M : tr &c ti /p t 9 ch ương trình th &c thi: 1- Kh :i ñ% ng ch ương trình Tanagra. 2- Trên menu chính, ch 'n File/new ñ m : m %t 8 ng d ng m $i. Hình III-1. M ng d ng m &i 3- Nh p tiêu ñ cho bi u ñ. Hình III-2. C a s nh p tiêu ñ [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 69 Trong ñó: - Diagram title: Tên c a s ơ ñ. . - Data mining diagram file name: Tên t p tin s ơ ñ. khai khoáng d li u, ñ ây là tên t p tin có liên quan ñ/n t p d li u c 0n khai khoáng. Nó s ? giúp ti /t ki m th )i gian th &c hi n. ñ ây ta ch 'n t p s ơ ñ. là m <c ñ* nh c a ch ương trình (“Default.tdm”). Ch 'n tên t p tin và click vào nút . - Dataset: ðư)ng d "n t p d li u c 0n khai phá. T (i ñây, Tanagra h E tr cho vi c phân tích d li u c a các ñ*nh d (ng nh ư: D li u ki u Text(*.txt). D li u c a weka(*.arff). D li u c a Excel (*.xls). Click vào nút ñ m : t p ñư) ng d "n: Hình III-3. C a s m t p tin Và sau ñó ch 'n Open. M %t s ơ ñ. m $i ñư c t(o ra d &a vào t p tin “adult.txt”. B (n có th xem mô t # n %i dung trong khung bên ph #i. Hình III-4. C a s hi n th t p tin N %i dung mô t # cho t p d li u “adult.txt”[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 70 M%t s , thông tin mô t # v n %i dung: a) Datasource processing: X lý d li u ngu .n. N ơi cho bi /t các thông tin v ngu .n d li u ñư c s lý nh ư: Th )i gian tính toán (Computation time), b % nh $ ñư c c p phát (allocated memory). b) Dataset description: T p d li u mô t #. Mô t # v t p d li u ngu .n, bao g . m các thông tin nh ư: • Attribute: Thu %c tính c a d li u. Ví d : Age, workclass,… • Category: Ph (m trù hay ki u c a d li u thu %c tính. Ví d : Continue, discrete,… • Infomations:Thông tin v thu %c tính c a d li u hay ñ/m s , m "u tin có cùng thu %c tính. Ví d : thu %c tính workclass có ki u là continue và có 8 giá tr * t ươ ng 8ng (Values). c) Default tilte: Tên t p d li u, khung này bao g .m các quá trình phân tích s ? ñư c th&c hi n t (i ñ ây. (2) Cách 2: M : gián ti /p thông qua Excel: 1- M : t p d li u Excel c 0n khai phá. Hình III-5. C a s làm vi c c a [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 71 2- Trên thanh menu chính, click ch 'n Tanagra\Excute tanagra: Hình III-6. Cách chuy n sang Tanagra trên Excel 3- Ch 'n các c %t d li u ph c v cho quá trình h 'c: Hình III-7. Ch n d li u trên Excel ph c v vho quá trình h [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 72 4- Sau khi ch 'n xong, click Ok, thì ch ương trình Tanagra ñư c m:: Hình III-8. C a s chuy n ñ i Excel sang Tanagra Các thông tin ñư c mô t # nh ư cách 1. III.1.2.2. Xác ñ*nh giá tr * Input và Target: - ð0 u vào (Input): Là nh ng thu %c tính ñ0u vào ph c v cho vi c xác ñ*nh m c tiêu, thu %c tính ñ0u vào có th là liên t c, r )i r (c,… - Mc tiêu (Target): ðư c xác ñ*nh d &a trên nh ng thu %c tính ñ0u vào. Ví d : T p d li u v ñ% ng v t: Input Target Hình III-9. T p d li u v ñ ng v t có x ương s [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 73 III.1.2.3. Các thao tác trên Components: Trong thanh Components ch 8a ñ& ng nh ng thành ph 0n ph c v cho quá trình khai phá d li u nh ư: (1) Data visualization: D li u ñư c nhìn : khia c (nh tr &c quan, v $i các ki u bi u di Dn d li u c a khai phá d li u. V $i các ki u trình bày d li u khác nhau nh ư: Correlation scatterplot: Bi u ñ. d(ng t ương quan phân tán. Export dataset: Xu t d li u sang ñ*nh d (ng ph c v cho vi c báo cáo Scatterplot: Bi u ñ. d(ng phân tán. Scatterplot with label: Bi u ñ. d(ng phân tán v $i các nhãn ñính kèm. View dataset: Khung nhìn d li u View multiple scatterplot: Khung nhìn bi u ñ. ñ a phân tán ñư c gom nhóm. (2) Statistics: Công c ph c v cho vi c th ,ng kê t p d li u c 0n phân tích, v $i các công c nh ư: ANOVA Randomized: phân tích ph ương sai cho thi /t k / kh ,i ng "u nhiên. Ph ương pháp này so sánh m %t s , m "u có liên quan Bartlett’s test: Ki m tra Bartlett’s cho tính ñ.ng nh t c a ph ương sai - k m "u phân ph ,i th ư)ng. So sánh ph ương sai c a m %t ph thu %c c a cá nhân thu %c các nhóm khác nhau. Box’s M test: Ki m tra h %p M là quá trình ki m tra t ĩnh, các ki m tra gi # ñ* nh ph ương sai có ñi u ki n thay ñ!i. Ví d : Các gi # thuy /t là các ma tr n hi p ph ươ ng sai là nh ư nhau trong các nhóm ñư c xác ñ*nh b :i giá tr * c a bi /n ñ% c l p riêng bi t. Brown-Forsythe’s test: Ki m tra Brown-Forsythe’s cho tính thu 0n nh t c a ph ương sai – K m "u ñ% c l p. So sánh ph ương sai c a m %t bi /n ph thu %c riêng l H ñ/ n các nhóm khác. Fisher’s test: Ki m tra Fisher cho tính thu 0n nh t c a ph ương sai-2 phân ph ,i m "u th ư)ng. So sánh ph ương sai c a m %t bi /n ph thu %c riêng l H ñ/ n 2 nhóm khác. Group characterization: so sánh s , li u th ,ng kê ñ mô t # ñ< c ñ i m nhóm ñư c xác ñ*nh b :i thu %c tính r )i r (c. M c ñích c a ph 0n này là ñ hi n th * n /u có s & khác bi t gi a các nhóm theo ch C s , th ,ng kê khác nhau nh ư: trung bình, t F l , vv Group exploration: nhóm th ăm dò tr &c quan, nó là m %t s & t !ng quát c a các nhóm ñ<c tính. M c ñích là ñ tính toán th ,ng kê mô t # v m %t nhóm con c a t p d li u, các phân nhóm ñư c xác ñ*nh b :i thu %c tính giá tr * ñ i u ki n b 4ng cách s d ng các thu %c tính r )i r (c. Hottelling’s T2: so sánh ña bi /n c a hai ph ương ti n v $i gi # ñ* nh ph ươ ng sai có ñi u ki n không ñ!i. Các gi # thuy /t là các vector c a các ph ương ti n c a các thu %c tính ph thu %cnhi u là m %t trong cùng m %t thành hai nhóm ñư c xác ñ*nh b :i giá tr * c a bi /n ñ% c l p riêng bi [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 74 Hottelling’s T2 Heteroscedastic: so sánh ña bi /n c a hai ph ương ti n v $i gi # ñ* nh ph ương sai th &c s & ph thu %c vào m %t bi /n ng "u nhiên khác. Các gi # thuy /t là các vector c a các ph ương ti n c a các thu %c tính ph thu %c nhi u là m %t trong cùng m %t thành hai nhóm ñư c xác ñ*nh b :i giá tr * c a bi /n ñ% c l p riêng bi t. Linear correlation: tính toán và ki m tra t 0m quan tr 'ng c a các m ,i t ươ ng quan tuy /n tính t 9 c <p c a các thu %c tính liên t c: m c tiêu ñ0u vào, ho <c l &a ch 'n ñ0 u vào chéo. More Univariate: th ,ng kê mô t # chi ti /t v các thu %c tính ñ0u vào liên t c. One-way ANOVA: m %t cách phân tích ph ương sai: tính toán trung bình c a các thu %c tính liên t c m c tiêu theo nhóm ñư c xác ñ*nh b :i thu %c tính ñ0u vào . One-way MANOVA: m %t cách phân tích ña bi /n c a ph ương sai: tính toán các nhóm khác bi t trên m %t s , bi /n liên t c ph thu %c ñ. ng th )i. Partial Correlation: tính toán và ki m tra t 0m quan tr 'ng c a s & t ươ ng quan m %t ph 0n t 9 c <p m c tiêu- ñ0u vào liên t c ki m soát các thu %c tính giá tr * c a bi /n minh h 'a. Semi-partial Correlation: tính toán và ki m tra t 0m quan tr 'ng c a s & t ươ ng quan m %t n a ph 0n t 9 c <p m c tiêu- ñ0u vào liên t c ki m soát các thu %c tính giá tr * c a bi /n minh h 'a. T-Test: cho 2 m "u test cho gi # ñ* nh b 4ng ph ương ti n – Gi # ñ* nh b 4ng v $ i ph ương sai. So sánh các trung bình c a m %t bi /n ph thu %c c a cá nhân tr &c thu %c nhóm khác nhau. T-Test Unequal Variance: cho 2 m "u test cho gi # ñ* nh b 4ng ph ương ti n – Gi # ñ* nh không b 4ng v $i ph ương sai. So sánh các trung bình c a m %t bi /n ph thu %c c a cá nhân tr &c thu %c nhóm khác nhau. (3) Clustering: CT: Cây phân c m. Cây phân c m ñơn nguyên t @c. Nó r t gi ,ng v $i cây h . i quy nh ưng có th x lý nhi u h ơn m %t l $p thu %c tính liên t c. CTP: Cây phân c m v $i vi c x lý c @t t Ca ñ xác ñ*nh kích th ư$c bên ph #i c a cây. Thành ph 0n này t ương t & nh ư cây phân c m. M %t ph ương pháp c @t t Ca ñư c cài ñ<t (m %t ph 0n trong nh ng ví d ñư c l&a ch 'n) ñư c th &c hi n ñ l y ñư c kích th ư$c phù h p c a cây. EM-Clustering: Phân c m v $i k ỳ v 'ng tuy t ñ, i c a thu t toán phân c m. H En h p c a ph ương pháp Gaussian và các ñ0u vào là các bi /n liên t c. EM-Selection: L &a ch 'n s , “t ,t nh t” trong c m v $i EM-Clustering. Có th ñư c g@n vào lo (i ch C có thành ph 0n. HAC: C m phân c p. Thành ph 0n này s d ng chi /n l ư c tiêu chu >n c m chi /n l ư c phân c p. Lá c a cây phân c p t ươ ng 8ng v $i d li u ñư c ñư a vào xây d &ng (h 'c). K-Means: Phân c m v $i thu t toán K-Means (Forgy or mcqueen). Thu %c tính ñư c ñ0 u vào là thu %c tính liên t [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 75 Kohonen-SOM: Phân c m v $i b #n ñ. t! ch 8c Kohonen. Thu %c tính ñ0u vào là thu %c tính liên t c. LVQ: Phân c m giám sát v $i l ư ng t c a vec t ơ h 'c Kohonen (LVQ1). Thu %c tính m c tiêu riêng bi t và ñ0u vào là thu %c tính liên t c. Neighborhood Graph: Giám sát c m v $i ñ. th * vùng lân c n. Nó là m %t ph ươ ng pháp th &c nghi m ñang ñư c phát tri n. VARCLUS: Phân c m bi /n b 4ng cách s d ng varclus - Ti /p c n t 9 trên xu ,ng. D &a trên các bi /n ti m >n. Liên t c ñ0 u vào thu %c tính VARHCA: Phân c m bi /n b 4ng cách s d ng HCA – Phân tích c m phân c p - Ph ương pháp ti /p c n theo ph ương pháp phân tích c m trên bi /n ti m > n,thu %c tính ñ0u vào là liên t c. Varkmeans: Phân c m bi /n b 4ng cách s d ng ph ương pháp K-Means ti /p c n v bi /n ti m >n. Thu %c tính ñ0u vào là liên t c. (4) Spv learning: Binary logistic regresion: H .i quy logic nh * phân, m c tiêu ph #i ñư c thu %c tính nh * phân riêng bi t, ñ0 u vào là giá tr * liên t c. C4.5: M %t thu t toán c a cây qu y /t ñ* nh. C-PLS: PLS cho phân lo (i ( M c tiêu nh * phân, ñ0u vào liên t c ho <c nh * phân). CS-CRT: Thu t toán cây phân lo (i phân bi t giá tr *. Phiên b #n c a x lý CART sai phân lo (i trong ma tr n giá tr *. CS-MC4: chi phí thu t toán cây quy /t ñ* nh nh (y c #m. Phiên b #n này s d ng d & toán xác su t làm m *n (m %t s & t !ng quát c a d & Laplace). Nó s ?gi #m thi u s & m t mát b 4ng cách s d ng ma tr n phân lo (i sai chi phí cho các d & báo t ,t nh t trong lá. ID3: M %t thu t toán c a cây quy /t ñ* nh. L y ñ( o hàm thu t toán ID3 c a Quinlan (1979), m %t s , thông s , ñư c thêm vào, nh p vào b t k ỳ các thu %c tính. K-NN: Thu t toán K-lân c n g 0n nh t. Linear discriminant analysis: Giám sát phân tích bi t th 8c tuy /n tính, t t c # ñ0 u vào là liên t c, ki m tra c %ng tuy /n. Multilayer perceptron: MLP m (ng l ư$i th 0n kinh, thu %c tính ñ0u vào liên t c. Multinominal Logistic Regression: H .i quy lo-gic ña ñ* nh danh. Naïve bayes: Thu t toán Naïve bayes. Naïve bayes continuons: Giám sát phân lo (i Naïve Bayes cho d & ñ oán liên t c. Theo gi # ñ* nh Gaussian. Theo gi # thi /t ph ương sai có ñi u ki n không ñ! i (homoscedasticity), chúng ta có th có ñư c m%t mô hình tuy /n tính ( ñ úng) ho <c m %t mô hình b c hai (sai). Prototype-NN: Ngu yên m "u – lân c n g 0n nh t, thu %c tính ñ0u vào liên t c, h (t nhân có th ñư c ñ* nh ngh ĩa b :i phân c [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 76 Radial basis function: M (ng th 0n kinh RBF, thu %c tính ñ0u vào liên t c, ph ươ ng pháp h 'c off-line c a các h (t nhân, v $i gi #i thu t phân c m ñư c áp d ng cho các m "u. (5) Feature construction: Menu ch 8a các tính n ăng ph c v cho vi c xây d &ng các dataset phù h p v $ i các ph ương pháp khai thác d li u s ? ñư c 8ng d ng, ñư c s d ng nh ư tính n ăng ti n x lý d li u, v $i các công c nh ư: Fomula: Tính toán thu %c tính m $i t 9 bi u th 8c ñ( i s,. Trong menu tham s , cho phép b (n xác ñ*nh s & bi u hi n c a m %t toán h 'c m $i. Th &c hi n và xem các menu c a bi u th 8c m $i. Các l Ei có th ñư c c#nh báo và báo cáo. Residual Scores: tính toán các ñi m h .i qu y còn l (i c a m Ei thu %c tính m c tiêu vào các thu %c tính ñ0u vào. Các thu %c tính m $i có th ñư c s d ng trong các phân tích ti /p theo nh ư tính toán c a các m ,i t ươ ng quan m %t ph 0n. Rnd Proj: tính toán m %t thu %c tính m $i t 9 các s #n ph >m c a hai thu %c tính ch 'n ng "u nhiên. Thành ph 0n này là th nghi m nên không s d ng Standardize: tiêu chu >n hóa thu %c tính liên t c. Bình th ư)ng ho <c tiêu chu >n hóa các thu %c tính liên t c s d ng bình th ư)ng bi u th 8c toán h 'c, ví d nh ư: new_value= (giá tr * trung bình) / ñ% lch chu >n. Trend: T (o ra m %t xu h ư$ng (1,2,3, .., n) trong m %t c %t m $i (thu %c tính liên t c). (6) Spv learning assessment: Bootstrap: Áp d ng ph ương pháp h 'c có giám sát ñ ñ ánh giá v $i giá tr * c a Error rate là 0,632 và 0,632+ giá tr * ng ưKng (bootstrap). Thành ph 0n này tính toán ma tr n t !ng th r @c r ,i (overall confusion matrix) và ñưa ra m %t ư$ c lư ng t F l l Ei. Cross-validation: Áp d ng ph ương pháp h 'c có giám sát ñ v$i vi c ñ ánh giá nhi u giá tr * xác th &c chéo. Thành ph 0n này ñư c th&c hi n m %t s & l <p l ( i c a m %t xác nh n tiêu chu >n chéo và tính trung bình t !ng th c a d & báo t F l l E i. Hosmer Lemeshow Test: Ph ương pháp ki m tra Hosmer Lemeshow cho h . i quy lo-gic nh * phân (binary logistic regression). Leave-One-Out: Áp d ng ph ương pháp h 'c có giám sát v $i m %t giá tr * b * lo (i b A. Thành ph 0n này th &c hi n ñánh giá t F l l Ei (error rate) ngoài s & cho phép cho các thu t toán h 'c có giám sát. Logistic Regression Residuals: Tính toán các s , d ư và các gi #i pháp #nh h ư: ng cho h .i quy tuy /n tính nh * phân. Test: ðánh giá thu t toán h 'c có giám sát (s) trên m %t t p ki m tra xác ñ* nh tr ư$c. D li u ph #i ñư c phân chia vào cài ñ<t ñào t (o (training) và th nghi m (testing) b 4ng cách s d ng m %t thành ph 0n l &a ch 'n m "u. T F l ki m tra l E i s ? ñư c tính vào các m "u không ñư c ch 'n. Train-test: Áp d ng ph ương pháp h 'c có giám sát ñ ñ ánh giá vi c phân c p d li u vào cài ñ<t h 'c và cài ñ<t ki m tra. Thành ph 0n này th &c hi n s & l <p l ( i c a quá trình ñào t (o-ki m tra ñ dánh giá t C l l E i d & bá[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 77 (7) Feature selection: ð ây là menu l &a ch 'n các tính n ăng tr ư$c khi th &c hi n giai ño (n h 'c, nh 4m m c ñích c #i thi n hi u su t phân lo (i d li u. Các tính n ăng th ư)ng ñư c l&a ch 'n là:Backward-logit, CFS filtering, Define status, FCBF filtering ( ñây là d (ng th ư)ng dùng ph ! bi /n cho vi c phân lo (i d li u), Feature ranking, Fisher filtering, Relieff, Remove constant, Runs filtering , Stepdisc. (8) Regression: Backward Elimination Reg: D & ñoán giá tr * c a m %t m c tiêu (n %i sinh) t 9 nh ng thu %c tính ñ0u vào (ngo (i sinh), t t c # các bi /n là liên t c. Nó th &c hi n m %t h .i quy ña tu y /n tính và t & ñ% ng tìm t p h p con "t ,t nh t" c a các thu %c tính ngo (i sinh s d ng các chi /n l ư c lo (i b A lùi. Các b ư$c ca quá trình l &a ch 'n s ? ñư c mô t #. K /t qu # h .i qu y t ,t nh t ñư c cung c p. C-RT Regression tree: Cây h .i quy d & ñoán. D & ñoán giá tr * c a m %t thu %c tính m c tiêu liên t c v $i m %t cây h .i quy, ñ0u vào (s) có th là liên t c ho <c r )i r (c. Các thu t toán ñư c s d ng là các Breiman và al. K /t qu # chi ti /t v trình t & c @t t Ca có th ñư c mô t #. Cây t ,t nh t trên vi c cài ñ<t c @t t Ca và cây ch 'n l &a ñư c tô sáng. Dfbetas: ðo l ư)ng dfbetas #nh h ư:ng c a m Ei quan sát trên t 9ng cá nhân c a các h s , h .i qu y. ði m ñ<c bi t c a dfbetas là s , l ư ng các sai s , chu >n mà các h s , thay ñ!i khi quan sát này ñư c lo(i b A ñ h.i quy. S , l ư ng ñi m phát hi n ñư c t!ng k /t trong m %t b #ng t 9 k /t qu # chi ti /t có s I n. Chúng ta có th sao chép các giá tr * trong m %t b #ng tính. Espilon SVR: D & ñoán giá tr * c a m %t thu %c tính m c tiêu t 9 nh ng thu %c tính ñ0u vào, t t c # ñ u liên t c, nó th &c hi n m %t h E tr c a véc t ơ h .i quy. Thành ph 0n này s d ng th ư vi n LIBSVM. Forward Entry Regression: D & ñoán giá tr * c a m %t thu %c tính m c tiêu (n %i sinh) t 9 nh ng thu %c tính ñ0u vào (ngo (i sinh), t t c # ñ u liên t c. Nó th &c hi n h .i quy tuy /n tính ña bi /n và t & ñ% ng tìm các t p h p con "t ,t nh t" c a các thu %c tính ngo (i sinh s d ng l &a ch 'n chi /n l ư c l&a ch 'n tr ư$c. Các b ư$c ca quá trình l &a ch 'n ñư c mô t #. K /t qu # h .i quy t ,t nh t ñư c cung c p. Multiple linear regression: D & ñoán giá tr * c a m %t thu %c tính m c tiêu t 9 nh ng thu %c tính ñ0u vào, t t c # ñ u liên t c, nó th &c hi n m %t h .i quy tu y /n tính nhi u theo ngu yên t @c OLS (Ordinary least square). NuSVR: D & ñ oán giá tr * c a m %t thu %c tính m c tiêu t 9 nh ng thu %c tính ñ0u vào, t t c # ñ u liên t c, nó th &c hi n m %t h E tr c a véc t ơ h .i quy. Thành ph 0n này s d ng th ư vi n LIBSVM. Outliner Detection: Phát hi n s & chênh l ch và / ho <c các ñi m có #nh h ư: ng cho h .i qu y tuy /n tính ña bi /n. S , ñ i m phát hi n ñư c t!ng k /t trong m %t b #ng. K /t qu # chi ti /t có s In. Chúng ta có th sao chép các giá tr * trong m %t b #ng tính Regression Assessment: So sánh giá tr * quan sát [thu %c tính m c tiêu] v $i giá tr * d & ñoán [thu %c tính ñ0u vào (s)] t 9 phân tích h .i qu y. Thành ph 0n này cho phép ñ làm n !i b t các mô hình t ,t nh t t 9 các mô hình khá[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 78 Regression tree: D & ñoán giá tr * c a m %t m c tiêu liên t c do v $i m %t cây h .i quy, ñ0u vào (s) có th là liên t c ho <c r )i r (c. Các thu t toán ñư c s d ng là phiên b #n ñơ n bi /n c a cây phân c m. Ph ương pháp h 'c t p bao g . m m %t quá trình c @t t Ca. K /t qu # chi ti /t v trình t & c @t t Ca có th ñư c mô t # . Cây t ,t nh t là cây ñư c cài ñ<t c@t t Ca và cây ñư c ch 'n s ? ñư c nh n m (nh. (9) Association: Menu ch 8a các thu t toán và mô hình ñ thi /t l p theo ph ương pháp khai phá d li u b 4ng lu t k /t h p. A priori: Thành ph 0n này tính toán lu t k /t h p b 4ng cách s d ng m %t thu t toán c ơ b #n ñư c ñ xu t b :i các mô t # c a Agrawal "tiên nghi m". A propri PT: Thu t toán A priori c a Christian Borgelt ñư c th&c hi n b 4ng cách s d ng cây ti n t ,. Thành ph 0n này chu >n b * m %t t p tin t (m th )i và g ' i ñ/ n ch ương trình c a Borgelt. ð0u ra ñư c x lý và xu t ra trong Tanagra. Ch ương trình Borgelt là m %t trong nh ng ch ương trình tính toán nhanh chóng ñ ñư a ra m %t t p lu t k /t h p, nh ưng h u qu # có th ch 8a m %t ch C m c. A propri MR: Thành ph 0n này tính toán lu t k /t h p theo nghiên c 8u MR (2004). ðây là m %t phiên b #n th nghi m trong vi c xây d &ng lu t k /t h p. Assoc Outlier: Thành ph 0n này s d ng các nguyên t @c liên k /t khai phá lu t k /t h p ñ phát hi n các ngo (i l ( ðây là phiên b #n th nghi m). Spv Assoc Rule: Giám sát lu t k /t h p v $i b % sinh ( ví d : cho nhóm ñ<c tính ña bi /n). Thành ph 0n này tính toán t t c # các qu y t @c hàng ñ0u cho thu %c tính m c tiêu riêng bi t b 4ng cách s d ng thu t toán A Priori. Spv Assoc Tree: Giám sát lu t k /t h p v $i b % sinh (ví d cho nhóm ñ<c tính ña bi /n. Thành ph 0n này tính toán t t c # các quy t @c hàng ñ0u cho thu %c tính m c tiêu riêng bi t b 4ng cách s d ng thu t toán A Priori. Thành ph 0n này là hi u qu # h ơn so v $i thành ph 0n " Spv Assoc Rule ". III.1.2.4. Phân tích các nhóm s d ng th ,ng kê mô t # Trong khuôn kh ! c a quá trình h 'c có giám sát, tính toán các th ,ng kê mô t # c a các mô t # theo các thành viên nhóm th ư)ng là các thông tin. ðây là nh ng mô t # ñơ n bi /n c a các quá trình. Chúng ta chèn các thành ph 0n DIFINE STATUS vào bi u ñ. . Chúng ta cài ñ< t DISEASE nh ư là m c tiêu (Target), các bi /n khác là ñ0u vào (Input)[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 79 Hình III-10. Quá trình cài ñ(t bi n ñ u vào và k t qu Sau ñó, chúng ta thêm thành ph 0n GROUP CHARACTERIZATION ( trong tab Statistics) vào bi u ñ. . Hình III-11. Th c hi n ch c n ăng Group [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 80 Chúng ta s ? có k /t qu # nh ư bên d ư$i: Hình III-12. Hi n th d li u trong menu ñ ng view III.1.2.5. Sao chép k /t qu # vào Excel: Vào Tanagra, chúng ta click vào menu COMPONENT / C OPY RESULTS. Chúng ta có th dán vào m %t b #ng tính m $i (Ctrl+V). Các giá tr * ñư c xác nh p vào các ô c a Excel. C u trúc c a b #ng s ? ñư c lưu gi l(i. T t nhiên, t 9 Excel, chúng ta có th k /t h p b t k ỳ lo (i thông tin nào vào các tài li u khác. Hình III-13. Quá trình sao chép k t qu vào [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 81 T (o các m "u h 'c và ki m tra: Chúng ta chèn các thành th 0n Sampling (trong tab INSTANCE SELECTION) vào bi u ñ. . Chúng ta click chu %t vào menu ng c # nh PARAMETERS. Chúng ta ch 'n s , m "u ñào t (o t (i m c absolute size ( : ñ ây, ta ch 'n s , m "u là 108). Hình III-14. Quá trình t o m u h c Chúng ta xác nh n các thi /t l p b 4ng cách nh n vào nút OK. Sau ñó, chúng ta click vào menu ng c #nh View ñ th &c hi n l y m "u. III.1.3. ng d ng Tanagra: B ư$ c ñào t (o (Training test): Chúng ta s ? s d ng d li u hu n luy n là phân lo (i hoa Iris (“Iris.txt”),v $i các quá trình th &c hi n nh ư sau: - T (o m "u h 'c, : ñ ây ta s ? l y s , l ư ng m "u ñào t (o là m <c ñ*nh proportion size. 15. Ch n s l ư ng m u ñào t [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 82 - D&a trên t p d li u Sampling 1 v 9a t (o. Chúng ta chèn C4.5 (trong tab Spv learning) vào bi u ñ. . Sau ñó, chúng ta click vào menu ng c #nh View ñ xem k /t qu #. III-16. K t qu c a quá trình h c. Bư$ c ki m tra: - T C l l Ei (Error rate) là 0.0400, t 8c là 0.4%. T C l này kh # quan ñ,i v $i mô hình cây quy /t ñ* nh. III-17. Xác ñnh t ) l l [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 83 III.2. CHƯƠ NG TRÌNH NG D /NG: III.2.1. Khai phá d li u b 0ng lu t k +t h p: III.2.1.1. Tìm hi u v lý thuy /t: Bài toán c ơ s : Cho t p d li u giao d *ch D nh ư sau: TID Items 100 M1,M2,M5 200 M2,M4 300 M2,M3 400 M1,M2,M4 500 M1,M3 600 M2,M3 700 M1,M3 800 M1,M2,M3,M5 900 M1,M2,M3 M c tiêu: - Lit kê các t p ph ! bi /n. - Tìm t t c # các lu t th Aa mãn ñi u ki n minisup=22% và miniconf=50%. Gi i quy t bài toán b ng cách th công: Hình III-18. Chuy n CSDL D sang nh phân Hình III-19. C ơ s d li u D Minisup=22%=2/[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 84 Các t p ph ! bi /n ñư c sinh ra và th Aa ñi u ki n minisup = 22% là: Hình III-20. 1-itemset Hình III-21. 2-Itemsets Hình III-22. 3-Itemsets Các t p lu t ñư c sinh ra và th Aa ñi u ki n minisup=22% và miniconf=70% là: - M1^M5->M2 - M2^M5->M1 - M5->M1^M2 - M5->M1 - M5->M2 - M4-M2 III.2.1.2. Ch ương trình 8ng d ng và ki m tra: D li u vào: - T p d li u text ph c v cho quá trình h 'c, v $i ñ* nh d (ng g .m 2 c % t, m Ei c %t cách nhau b 4ng tab, m Ei dòng cách nhau b 4ng phím enter. - ChC s , minisup và miniconf ph c v cho vi c ki m tra D li u ra: Các lu t ñư c sinh ra d &a trên t p d li u text. Gi i thu t: S% d ng thu t toán Apriori - Ti n x lý d li u b 4ng cách bi u di Dn các giá tr * c a d li u b 4ng b #ng nh * phân ( Th t c 1 ). - Sinh các 8ng viên b 4ng cách s d ng cây b ăm ( Gii thu t 1 ). - ð/m các 8ng viên xu t hi n trong giao d *ch ( Th t c 2 ). - Kim tra các 8ng viên th Aa ñi u ki n minisup ( Th t c 3 ). - Sinh các lu t d &a trên các 8ng c viên th Aa ñi u ki n miniconf ( Th t c 4 ). - Kim tra t .n t (i c a 8ng viên trong t p 8ng viên ( Gii thu t 2 ). - Sinh ra v / ph #i c a lu t d &a trên v / trái c a lu t ( Gi i thu t 3 )[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 85 Lưu ñ x lý c a ch ương trình: III-23. Lưu ñ x lý c a ch ương trình. Th t c 1: Ch c n ăng: - Chuy n d li u sang b #ng d li u nh * phân, lo (i b A d li u nhi Du và ph c v cho quá trình x lý. D li u vào: - T p d li u hu n luy n sau khi ñã qua x lý. D li u ra: - D li u sau khi chuy n sang nh * phân. Sinh các 8ng viên (Gi #i thu t 1) Begin End T p hu n luy n Bi u di Dn nh * phân (Th tc 1) k=1 k<s , item ð/ m s , 8 ng viên trong giao d *ch (Th tc 2) Ki m tra ñi u ki n 8ng viên th Aa minisup (Th tc 3) Sinh các lu t th Aa ñi u ki n [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 86 Gii thu t: - Khai báo itemset(chi u dài th hi n các giao d *ch ( length ), chi u ngang là các items( length_buff)). - L<p i=0 ñ/n length_buff Gán itemset(0,i)= itemset - L<p i=0 ñ/n lenghth L y các item trong các giao d *ch L <p j=0 ñ/n s , item trong giao d *ch L <p k=0 ñ/n length_buff If item =itemset(0,k) Itemset(i+1,k)=1 Gi i thu t 1: Ch c n ăng: - Sinh các k itemset 8ng viên t 9 các item trong t p d li u. D li u vào: - ChC s , k. - Các item trong giao d *ch. D li u ra: - Các t p k itemset. Gi i thu t: - If k=1 then L<p i=0 ñ/n s , item k_itemset = item - Else i=0 L<p khi (i+k-1)< s , item m=i t ăng i L <p j=1 ñ/n k L y s , item ñ/n k-1 L <p l=m ñ/n s , item K /t h p các item v 9a l y v $i các item còn l (i ñ sinh ra t p 8ng viê[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 87 III-24. L ưu d cú pháp gi i thu t 1. Th t c 2: Ch c n ăng: - ð/m các 8ng viên xu t hi n trong các giao d *ch. D li u vào: - T p 8ng viên k-itemset. - B#ng giao d *ch bi u di Dn nh * phân (itemset(,)). D li u ra: - T p 8ng viên th Aa ñi u ki n minisup. Gi i thu t: - Khai báo f_k có ki u d li u g .m itemset và count. - L<p i=0 ñ/n chi u dài c a t p k-itemset. F_k(i).itemset = k-itemt(i) - L<p i=0 ñ/n chi u dài c a m #ng f_k End S i=0 i+k-1<s, item m=i, i=I+1, j=1 j<k L y s , item t 9 m ñ/n k-1 j=j+1, m=m+1 l=m l<s , item K/t h p các item v 9a l y v $i các item còn l (i. l=l+1 ð S ð ð S k=1 i=0 i<s , item K_itemset = item i+=1 Begin ð S S ð[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 88 Khai báo m #ng tmp ñ lưu tr các itemset c a f_k Khai bao tmpc ñ lư u t 9ng giá tr * c a m #ng tmp Khai báo m #ng vi_tri ñ lưu gi v * trí c a t 9ng item trong b #ng nh * phân L <p j =0 ñ/n chi u dài c a m #ng tmp tmpc=tmp(j) L <p k=0 ñ/n chi u r %ng c a itemset(,) If tmpc=itemset(0,k) then vi_tri(j)=k If chi u dài c a m #ng vi_tri là 1 L <p k=1 ñ/n chi u dài c a m #ng itemset If (k, vi_tri(0))=1 then f_k(i).count+1 Else L <p j=0 ñ/n chi u dài c a itemset(,) If itemset(j,vi_tri(0))=1 then Khai báo bi /n true_false= True ñ d9ng l < p L <p k=1 ñ/n chi u dài m #ng v * trí và bi /n true_false ñúng If itemset(j,vi_tri(k))=1 Else true_false=False và d 9ng vòng l <p If true_false=True then f_k(i).count+1 Th t c 3: Ch c n ăng: - Kim tra và lo (i b A các 8ng viên không th Aa ñi u ki n minisup D li u vào: - T p các 8ng viên f_k. - ði u ki n minisup D li u ra: - Các 8ng viên th Aa ñi u ki n minisupp. Gi i thu t: - Khai báo bi /n f_k_count ñ ñ/ m s , 8 ng viên th Aa ñi u ki n minisup . - Khai báo so_tap_dataset là s, l ư ng các giao d *ch. - Khai báo bi /n minisup ñ lư u tr giá tr * ki m tra - L<p i=0 ñ/n chi u dài m #ng f_k If f_k.count/so_tap_dataset>minisup và các f_k ph #i ch 8a 2 item Then f_k_count+1 - Khai báo m #ng luat có chi u dài là f_k_count g .m 2 bi /n item và count. - Khai báo [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 89 - L<p i=0 ñ/n chi u dài c a f_k If f_k.count/so_tap_dataset>minisup và các f_k ph #i ch 8a 2 item Then luat(j).item=f_k(i).item, luat(j).count=f_k(i).cou nt, t ă ng i, t ăng j. Th t c 4: Ch c n ăng: - Sinh các lu t 8ng viên d &a trên các t p 8ng viên th #o ñi u ki n. D li u vào: - Các t p 8ng viên th Aa ñi u ki n minisupp (luat()) - ði u ki n miniconf. D li u ra: - Các lu t th Aa ñi u ki n miniconf. Gi i thu t: - Khai báo m #ng luat_sinh() là m%t m #ng ki u chu Ei. - Khai báo bi /n itemset_l là bi/n ki u chu Ei ñ lưu t p 8ng viên ñư c xét. - Khai báo bi /n miniconf ñ lư u ñi u ki n lo (i b A. - L<p i=0 ñ/n chi u dài c a m #ng lu t itemset_l =luat(i).item L <p j=0 ñ/n s , itemset có trong itemset_l Sinh các 8ng viên d &a vào gi #i thu t 1 L ưu các lu t ñư c sinh ra vào m #ng luat_sinh. L <p k=0 ñ/n chi u dài m #ng lu t sinh If f_k(i).count/ ktra(luat_sinh(k),f_k))>= miniconf luat(k)-> hieu_tap(itemset_l, luat(k) Gi i thu t 2: Ktra() Ch c n ăng: - Kim tra t .n t (i c a 8ng viên trong t p 8ng viên . D li u vào: - ng viên và t p 8ng viên. D li u ra: - Giá tr * c a 8ng viên . Gi i thu t: - L<p i= 0 ñ/n chi u dài m #ng 8ng viên. If 8 ng viên t .n t (i then tra v giá tr * t .n t (i c a 8ng viên. Else t ăng [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 90 Gii thu t 3: hieu_tap() Ch c n ăng: - Sinh ra v / ph #i c a lu t d &a trên v / trái c a lu t. D li u vào: - Chu Ei 8 ng viên và v / trái c a lu t. D li u ra: - V/ ph #i c a lu t. Gi i thu t: - Khai bao tap1 lư u các item c a 8ng viên. - Khai báo tap2 lư u các item c a v / trái lu t. - L<p i=0 ñ/n chi u dài m #ng tap1 L <p j=0 ñ/n chi u dài m #ng tap 2 If tap1(i)=tap2(j) then tap1(i)=rong. - L y các giá tr * tap1() khác r Eng s ? ñư c v/ ph #i c a lu t. III-25. L ưu d cú pháp gi i thu t 3. ð S S Begin End Tap1= T p item c a 1 8ng viên Tap2= T p item c a v / trái lu t i=0 i<chi u dài tap1 j<chi u dài tap2 j=0 tap1(i)=tap2(j) Tap1(i)=r Eng ð ð [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 91 III.2.1.3. Demo minh h 'a: Màn hình chính c a ch ương trình nh ư sau: III-26. Màn hình chính c a demo khai phá d li u b *ng lu t k t h p. Ch ương trình khai phá d li u b ng lu t k t h p có các thành ph n sau ñ ây: - Textbox Link dataset: Ch 8a ñư) ng d "n c a t p d li u. - Textbox Dataset: Hi n th * n %i dung t p d li u. - Textbox Change dataset to binary: Hi n th * bi u di Dn c a t p giao d *ch : d (ng nh * phân. - Textbox Minisup: Nh p vào ñi u ki n minisup ñ lo (i các item không th Aa ñi u ki n. - Textbox Miniconf: Nh p vào ñi u ki n ñ lo (i b A các lu t không th Aa ñ i u ki n. - Textbox Result: Hi n th * k /t qu # sau khi khai phá g .m các t p 8ng viên và các lu t th Aa ñi u ki n minisup và miniconf. - Button Open: M : t p d li u và hi n th * ñư) ng d "n và n %i dung t p d li u vào textbox Link dataset và Dataset. - Button Start: B @t ñ0 u quá trình khai phá và hi n th * vào textbox Result. - Button Save to file: L ưu k /t qu # c a quá trình khai phá d li u c a t p giao d *ch : d (ng file TXT. M t p d li u hu n luy n: T p d li u hu n luy n là t p có c u trúc ñư c lưu tr trong t p TXT, ch 8a các giao d *ch (Itemset). C u trúc g .m: - 2 tr ư)ng d li u th hi n mã giao dich và giao d *ch, cách nhau b 4ng phím Tab. - Các dòng cách nhau b 4ng phím Enter. - MEi dòng có các item, cách nhau b 4ng d u “,”[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 92 Ví d: T p d li u giao dich Vi_du_0 nh ư sau: Hình III-27. T p d li u Vi_du_0 Màn hình k /t qu # sau khi nh p t p d li u Vi du 0, k /t qu # nh ư sau: Hình III-28. Màn hình k t qu vi c hu n l uy n t p d li u [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 93 III.2.2. Khai phá d li u b 0ng cây quy +t ñ& nh: III.2.2.1. Tìm hi u v lý thuy /t: Bài toán c ơ s : Cho t p d li u nh ư sau: Hình III-29. T p d li u ví d Mc tiêu: Xây d &ng các lu t IF-THEN d &a trên thu t toán ILA ( ðã tìm hi u : m c II.4.3.4) Gii quy t bài toán b ng lý thuy t: - Bư$ c 1: Chia b #ng ch 8a m m "u thành n b #ng con Hình III-30. T p d li u sau khi chi a làm 2 b ng con Xét b ng con 1: - Bư$ c 2: Cho j = 1. - Bư$ c 3: Danh sách các thu %c tính k /t h p là {|Size|, |Color|, |Shape|}. - Bư$ c 4: Ch 'n max-combination = “Xanh lá cây”. - Bư$ c 5: Vì max-combination ≠ rEng, nên không làm gì. - Bư$ c 6: ðánh d u dòng 3,4. - Bư$ c 7: R1: IF Color= “Xanh lá cây” THEN Decision= “Ye s” - Bư$ c 8: Vì B #ng con 1 còn có thu %c tính ch ưa ñánh d u, nên quay l (i b ư$ c [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 94 Hình III-31. B ng con 1 sau khi ñánh d u dòng 3,4. - Bư$ c 4: Ch 'n max-combination = “V 9a” - Bư$ c 5: Vì max-combination ≠ rEng, nên không làm gì. - Bư$ c 6: ðánh d u dòng 1. - Bư$ c 7: R2: IF Size = “V 9a” THEN Decision = “Yes”. - Bư$ c 8: Vì B #ng con 1 còn có thu %c tính ch ưa ñánh d u, nên quay l (i b ư$ c 4. Hình III-32. B ng con 1 sau khi ñánh d u dòng 1,3,4. - Bư$ c 4: Ch 'n max-combination = “C 0u”. - Bư$ c 5: Vì max-combination ≠ rEng, nên không làm gì. - Bư$ c 6: ðánh d u dòng 2. - Bư$ c 7: R3: IF Shape = “C 0u” THEN Decision = “Yes”. - Bư$ c 8: Vì B #ng con 1 ñã ñư c ñánh d u t t c # nên chuy n sang B #ng con 2. Xét b ng con 2: Hình III-33. Xét b ng con 2. - Bư$ c 2: j=1 - Bư$ c 3: Danh sách các thu %c tính k /t h p là {|size|, |color|, |shape|}. - Bư$ c 4: Ch 'n max-combination = “Nón” - Bư$ c 5: Vì max-combination ≠ rEng, nên không làm gì. - Bư$ c 6: ðánh d u dòng 1,2. - Bư$ c 7: R4: IF Shape = “Nón” THEN Decision = “No”[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 95 - Bư$ c 8: Vì còn dòng ch ưa ñánh d u nên quay l (i b ư$ c 4. Hình III-34. B ng con 2 sau khi ñánh d u dòng 1,2. - Bư$ c 4: max-combination = {} - Bư$ c 5: Vì max-combination = r Eng, nên j=2 và quay l (i b ư$c 3. - Bư$ c 3: Danh sách các thu %c tính k /t h p là {|Size, Color|,|Size, Shape|, |Color, Shape|} - Bư$ c 4: Ch 'n max-combination = “L $n” và “ ñA”. - Bư$ c 5: Vì max-combination ≠ rEng, nên không làm gì. - Bư$ c 6: ðánh d u dòng 3. - Bư$ c 7: R5: IF Size = “L $n” AND Color = “ ñA” THEN decision = “No”. - Bư$ c 8: Vì các b #ng ñ u ñã ñư c xét nên k /t thúc thu t toán. T p lu t ñư c sinh ra là: R1: IF Color= “Xanh lá cây” THEN Decision= “Yes” R2: IF Size = “V 9a” THEN Decision = “Yes” R3: IF Shape = “C 0u” THEN Decision = “Yes” R4: IF Shape = “Nón” THEN Decision = “No” R5: IF Size = “L $n” AND Color = “ ñA” THEN Decision = “No” III.2.2.2. Demo minh h 'a: Màn hình chính c a ch ương trình: Hình III-35. Màn hình chính c a ch ương trình khai phá d li u b *ng cây quy t ñ [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 96 Ch ương trình khai phá d li u b ng cây quy t ñ nh có các thành ph n sau ñây: - Textbox Training dataset: ðư)ng d "n t p d li u hu n luy n và hi n th * n % i dung c a t p d li u hu n lu y n : datagridview bên d ư$i. - Textbox Attribute: Hi n th * k /t qu # c a quá trình khai phá d li u. - Textbox Testing dataset: ðư)ng d "n c a t p d li u ki m tra ñ% chính xác c a t p lu t và hi n th * n %i dung c a t p ki m tra : datagridview bên d ư$i. - Button Open: M : t p d li u hu n luy n và t p d li u ki m tra. M tp d li u: T p d li u hu n luy n là t p có c u trúc ñư c lưu tr trong t p TXT, ch 8a các giao d *ch (Itemset). C u trúc g .m: - 2 tr ư)ng d li u th hi n mã giao dich và giao d *ch, cách nhau b 4ng phím Tab. - Các dòng cách nhau b 4ng phím Enter. Ví d : T p d li u Vi_du_1 nh ư sau: Hình III-36. T p d li u Vi_du_1 Màn hình k t qu ñ i v i t p d li u Vi_du_1 và t p d li u ki m tra Vi_du_1test nh ư sau: Hình III-36. Màn hình k t qu ñ i v&i t p d li u Vi_du_1 và T p d li u ki m tra [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 97 KT LU 1N VÀ KI N NGH I. KT LU 1N : Lu n v ăn t p trung nghiên c 8u các quá trình khai phá d li u t 9 d li u thô ban ñ0u ñ/ n d li u ñã qua x lý và ph c v cho quá trình khám phá tri th 8c. Qua vi c nghiên c 8u các ph ương pháp và các gi #i thu t khai phá d li u, lu n v ăn cho th y ñư c s& h u ích c a d li u ph c v cho quá trình kinh doanh, nghiên c 8u và h 'c t p. M t s k t qu ñ t ñư c: - T!ng k /t nh ng v n ñ nghiên c 8u v khai phá d li u và khám phá tri th 8c t 9 d li u. - Tìm hi u v các k - thu t khai phá d li u, làm n n t #n cho quá trình khám phá tri th 8c t 9 d li u. - Tìm hi u v ch ương trình khai phá d li u ph c v cho quá trình nghiên c 8 u và h 'c t p. - ðã làm sáng rõ s & c 0n thi /t c a vi c khai phá d li u và 8ng d ng tri th 8c trong l ĩnh v &c kinh doanh, nghiên c 8u và h 'c t p. - Áp d ng nh ng v n ñ nghiên c 8u v k - thu t khai phá d li u b 4ng lu t k /t h p và cây qu y /t ñ* nh vào khai phá d li u c ơ b #n. M t s h ư ng phát tri n: - Tìm hi u thêm v các ph ương pháp khai phá d li u khác. - M: r %ng nghiên c 8u khai phá d li u t 9 hình #nh và web. - Tìm hi u thêm v ngôn ng l p trình ñ có th c #i ti /n, rút ng @n các gi #i thu t và th t c, c ũng nh ư xây d &ng thêm các thu t toán khai phá d li u ñ có th ph c v cho công vi c nghiên c 8u. II. KI N NGH : Trong quá trình nghiên c 8u tôi ñã h 'c h Ai ñư c r t nhi u v m %t ki /n th 8c m $i và hi u ñư c t0m quan tr 'ng c a d li u sau khi s d ng. Ngoài m c ñích l ư u tr còn có th ph c v t,t cho công vi c ñ* nh h ư$ng kinh doanh, nghiên c 8u và h 'c t p. ðó là “ngu .n tài ngu yên” h u ích ph c v cho ñ)i s,ng con ng ư)i. Qua quá trình nghiên c 8u, tôi ñã hi u và bi /t ñư c s& h u ích c a d li u qua các m %t s , khai phá d li u. Bên c (nh ñó, vì th )i gian nghiên c 8u còn h (n h Mp nên ch C nghiên c 8u ñư c các k - thu t khai phá d li u c ơ b #n trên d li u là các t p tin v ăn b #n, ch ưa ñi sâu vào nghiên c 8u khai phá d li u trên d li u là hình #nh, âm thanh, web,…. ð.ng th )i, do môn h 'c còn m $i nên ch ưa n @m b @t ñư c h/t n %i dung c a môn h 'c. Chính vì v y, r t mong nhà tr ư)ng và ban ch nhi m khoa xem xét vi c ñư a môn h 'c này vào gi #ng d (y, ñ các khóa sinh viên sau s ? ti /p thu ñư c m%t môn h 'c m $i và h u ích cho cu %c s ,ng. Riêng tôi, s ? c , g @ng phát tri n hoàn ch Cnh v c ơ s : lý thuy /t v khai phá d li u, tìm hi u thêm v ngôn ng l p trình ñ có th ñư a ra ñư c các gi #i pháp và gi #i thu t m $i ph c v cho nhu c 0u h 'c t p và công vi c sau khi ra tr ư)[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 98 PH L C Ph l c I: ð o kho #ng cách gi a 2 ñ,i tư ng d li u: 1) Kho #ng cách Euclid (Euclid distance) gi a 2 ñi m x, y trong không gian n chi u: ∑= −=ki kkyxyxd12)(),( Trong ñó: - n là s , chi u. - kkyx , là giá tr * thu %c tính th 8 k c a ñ, i tư ng x và y. 2) Kho #ng cách Haming (Haming distance) gi a hai ñ,i tư ng là s , bit khác nhau gi a hai ñ,i tư ng ch C có giá tr * nh * phân. 3) Kho #ng cách l $n nh t (Supremun distance) là kho #ng cách l $n nh t gi a 2 thu %c tính b t kì c a 2 ñ,i tư ng. 4) Kho #ng cách Minkowski (Minkowski distance) gi a 2 ñ,i t ư ng ñư c ñ* nh ngh ĩa nh ư sau: rrnk kk yxyxd /11),( −=∑= trong ñó r là tham s , - Khi r = 1: Kho #ng cách Minkowski tr : thành kho #ng cách Hamming. - Khi r = 2: Kho #ng cách Minkowski tr : thành kho #ng cách Euclid. - Khi r = ∞: Kho #ng cách Minkowski tr : thành kho #ng cách l $n nh t. Ph l c II: Thu t gi #i Heuristic Thu t gi #i Heuristic là m %t s & m : r %ng khái ni m thu t toán. Nó th hi n cách gi #i bài toán v $i các ñ<c tính sau: - Th ư)ng tìm ñư c l)i gi #i t ,t (nh ưng không ch @c là l )i gi #i t ,t nh t). - Gi#i bài toán theo thu t gi #i Heuristic th ư)ng th hi n khá d D dàng và nhanh chóng ñưa ra k /t lu n h ơn so v $i gi #i thu t t ,i ư u, vì v y chi phí th p h ơn. - Thu t toán Heuristic th ư)ng th hi n khá t & nhiên, g 0n g ũi v $i cách suy ngh ĩ và hành ñ%ng c a con ng ư)i. Có nhi u ph ương pháp ñ xây d &ng m %t gi #i thu t Heuristic, trong ñó ng ư)i ta th ư)ng d &a trên các nguyên lý c ơ b #n sau: - Nguyên lý vét c (n thông minh: Trong m %t bài toán tìm ki /m nào ñó, khi không gian tìm ki /m l $n, ng ư)i ta th ư)ng tìm cách gi $i h (n l (i không gian tìm ki /m ho <c th &c hi n m %t k /t qu # dò tìm ñ<c bi t d &a vào ñ<c thù c a bài toán ñ nhanh chóng tìm ra m c tiêu. - Nguyên lý tham ăn (Greedy): L y tiêu chu >n t ,i ưu ( trên ph (m vi toàn c c) c a bài toán ñ làm tiêu chu >n ch 'n l &a hành ñ%ng cho ph (m vi c c b % c a t 9 ng b ư$c (hay t 9ng giai ño(n) trong quá trình tìm ki /m l )i gi #i. - Nguyên lý th 8 t& : Th &c hi n hành ñ%ng d &a trên m %t c u trúc th 8 t& h p lý c a không gian kh #o sát nh 4m nhanh chóng ñ(t ñư c m%t l )i gi #i t ,[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 99 - Hàm Heuristic: Trong vi c xây d &ng các gi #i thu t Heuristic, ng ư)i ta th ư) ng dùng các hàm Heuristic. ðó là các hàm ñánh giá thô, giá tr * c a hàm ph thu %c vào tr (ng thái hi n t (i c a bài toán t (i m Ei b ư$ c gi #i. Nh ) giá tr * này ng ư)i ta có th ch 'n ñư c cách hành ñ%ng t ương ñ,i h p lý cho t 9ng b ư$c c a gi #i thu t. Ph l c III: H ư$ng d "n s d ng ch ương trình khai phá lu t k /t h p. ð ch (y ch ương trình khai phá d li u b 4ng lu t k /t h p, b (n c 0n ch (y kích ho (t file “Luat_ket_hop.exe”. B (n c 0n chu >n b * m %t t p d li u th Aa yêu c 0u sau: - M%t t p d li u g .m 2 c %t, m Ei c %t cách nhau b 4ng phím Tab. - T p d li u g .m nhi u dòng (record), m Ei dòng cách nhau b 4ng phím Enter. - MEi dòng có các item, cách nhau b 4ng d u “,”. Ch (y m %t 8ng d ng: - Màn hình chính sau khi kích ho (t file ch ương trình: Hình 1: Màn hình chính c a ch ương trình khai phá d li u Lu t k t h p - Click ch 'n nút nh n Open ñ m : t p d li u, ch 'n t p d li u “Vi du 0”: Hình 2. C a s m 1 t p d li [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 100 - Sau khi m : t p d li u, màn hình sau xu t hi n: Hình 3. Màn hình ñi n các ch + s mi nisup và miniconf ñ sinh lu t. - Sau khi ñã nh p các ch C s , minisup và miniconf, click vào nút Start ñ b @t ñ0 u khai phá và k /t qu # c a vi c khai phá t p d li u Vi du 0 nh ư sau: Hình 4. K t qu c a ch ương trình. - Sau khi k /t qu # xu t hi n t (i textbox Result, nút nh n Save to file hi n lên ñ b(n có th l ưu t p lu t v 9a khai phá thành m %t file text d li u ñ s d ng sau này. Hình 5. C a s l ưu k t qu [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 101 Ph l c IV: H ư$ ng d "n s d ng ch ương trình khai phá b 4ng cây quy /t ñ* nh. ð ch (y ch ương trình khai phá d li u b 4ng cây qu y /t ñ* nh, b (n c 0n ch (y kích ho (t file “Cay_quyet_dinh.exe”. B (n c 0n chu >n b * m %t t p d li u th Aa yêu c 0u sau: - M%t t p d li u g .m nhi u c %t, m Ei c %t cách nhau b 4ng phím Tab. - T p d li u g .m nhi u dòng (record), m Ei dòng cách nhau b 4ng phím Enter. Cách ch (y m %t 8 ng d ng: - Màn hình chính c a ch ương trình: Hình 6. Màn hình chính c a ch ương trình khai phá d li u b ăng cây quyêt ñnh. - T9 màn hình chính, ch 'n t p d li u hu n luy n b 4ng cách nh n nút Open c a textbox Training dataset, : ñ ây ta ch 'n t p d li u “Thoi_tiet.txt”: Hình 7. C a s ch n t p d li u ñ hu n luy [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 102 - K/t qu # sau khi ch 'n t p d li u và sinh các lu t d &a trên t p d li u ñó, t p lu t này ñư c s d ng su ,t trong quá trình ki m tra: Hình 8.C a s sau khi ch n t p d li u hu n luy n và các lu t ñư c sinh ra. - Sau khi ch 'n t p d li u hu n lu y n, ñ ki m tra lu t ta ch 'n t p d li u ki m tra b 4ng cách nh n nút Open c a textbox Testing dataset, : ñ ây ta ch 'n t p d li u “Thoi_tiet_test.txt”:[email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 103 - Sau khi ch 'n t p d li u ki m tra tính ñúng ñ@ng d &a trên lu t ñư c sinh ra, k /t qu # ñư c hin th * nh ư sau: Hình 10. Màn hì nh k t qu ñ i v&i vi c ki m tra t p lu t. - Sau khi ch 'n t p d li u ki m tra, nút nh n Save to file xu t hi n ñư c dùng ñ lưu k /t qu # thành t p tin d li u TXT ñ thu n ti n cho vi c s d ng: Hình 11. C a s l ưu t p lu t và k t qu ki m tra. Lư u ý: Chương trình khai phá d li u b 4ng lu t k /t h p mu ,n sinh ra t p lu t d &a trên t p d li u khác c 0n t @t ch ương trình và làm l (i t 9 ñ0 [email protected] NGHIÊN CU KHAI M D LI U VÀ KHÁM PHÁ TRI TH C SVTH: Quách Luyl ða Trang 104 TÀI LI ,U THAM KH -O Tài li u ti ng Vi t [1]. D ương V ăn Hi /u. Khai khoáng d li u . Khoa Công ngh thông tin – ð(i h ' c C 0n Th ơ. [2]. Nguy Dn Hoàng Tú Oanh. Bài ging Khai phá d li u và ng d ng . ð( i h'c Khoa h 'c T & nhiên – ð(i h'c Qu ,c gia Thành ph , H . Chí Minh. [3]. Ngu y Dn Nh t Quang. Bài ging Khai phá d li u . Vi n Công ngh thông tin và truy n thông - ð(i h'c Bách khoa Hà N %i. N ăm h 'c 2010-2011. Tài li u ti ng Anh [1]. Alex Berson & Stephen Smith, and Kurt Thearlin g. Building Data Mining Applications for CRM [2]. John F.Elder IV & Dean w.Abbott . A Comparison of Leading Data mining tools . New York. 1998. [3]. Michael J.A.Berry & Gordon S.Linoff. Data mining techniques for marketing, sales, and customer relationship . Indiannapolis, Indiana. 2004. [4]. Paolo Giudici. Applied data mining statistical methods for business and industry . University of Pavia, Italia. 2003. [6]. Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data mining. Pearson International . 2006. Chapter 4,6. [7]. Tanagra – Data Mining Tutorials . http://data-mining-tutorials.blogspot.com. [8]. Xianjun Ni. Reasearch of Data mining Based on Neural Networks . World Academy of Science, Engineering and technology 39. 2008. www.waset.org/journals/waset/v39/v39-72. [9]. Decision Tree & Data mining . www.decisiontrees.net . [10]. John wiley&Sons. Data mining multimedia, soft computing, and bioinformatics . New Jersey- Canada. 2003 [11]. Tanagra help . [12]. Weka help . [13]. Câu l c b visual basic . http://www.caulacbovb.com/
- Xem thêm -
Tài liệu liên quan
Bình luận
Người bán
Tải nhiều
Tài liệu chọn lọc
