Luận văn Khai mỏ dữ liệu và khám phá tri thức

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). Dựa trên dữliệu vềkhai phá dữliệu và khám phá tri thức từ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ằng 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ừhình ảnh (Image mining), web (web mining), Các phương pháp khai phá dữliệu khác

pdf104 trang | Chia sẻ: oanh_nt | Lượt xem: 2129 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Luận văn Khai mỏ dữ liệu và khám phá tri thức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TR ƯNG ðI H C TÂY ðÔ KHOA K THU T CÔNG NGH LU N V ĂN T T NGHI P ð I H C 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 Lp: ð i h c Tin h c 2 Cn 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 H C 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 Lp: ð i h c Tin h c 2 Cán b ph n bi n Hc hàm, h c v , h và tên cán b ph n bi n Lu n v ăn ñưc b o 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 h c 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 h c Tây ðô. • Website: LI 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” Khuy t 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 bc 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 s ng 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 c a 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 thy 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à chuyê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 ñiu 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 b n 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 chuy 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 bn, các cô chú nhân viên tr ưng ñã giúp ñ và quan tâm tôi trong su t thi gian theo h c ti tr ưng. Tôi xin chân thành cám ơn! Xin chân thành cám ơn! luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C MC L C LI CÁM ƠN BNG 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:................................................................................................... 24 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. Chuy 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 n nh t: (K Nearest neighbour-KNN) ................................... 44 II.4.5. Gi i thu t di truy 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 I DUNG NGHIÊN C U................................................................... 67 III.1. NGHIÊN C U V PH N 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 NG:................................................................... 83 III.2.1. Khai phá d li u b ng lu t k t h p:.......................................................... 83 III.2.2. Khai phá d li u b ng cây quy t ñ nh: ..................................................... 93 KT LU N VÀ KI N NGH PH L C Ph l c I: ðo kho ng cách gi a 2 ñ i t ưng Ph l c II: Thu t gi i Heuristic Ph l c III: H ưng d n s d ng ch ươ ng trình khai phá lu t k t h p Ph l c 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 O SVTH: Quách Luyl ða Trang 4 luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C BNG KÝ HI U VÀ VI T T T T VI T STT TI NG ANH NGH ĨA TI NG VI T TT 01 ANN Artifical neural network Mng th n kinh nhân t o 02 AND, DNA Acid DeoxyriboNucleic Ph n t nucleotic a xít 03 GA Genetic Algorithm Gi i thu t di truy n Giao di n ñ h a ng ưi 04 GUI Graphical user interface dùng 05 Item Item Món hàng, m c,.. 06 Itemset Itemset Tp các m c, các hàng,… 07 KNN K Nearest neighbour K-lân c n g n nh t Knowledge Discovery in 08 KDD Khám phá tri th c t d li u Databases 09 RAM Ram memory B nh ram Extensible Markup 10 XML Ngôn ng ñánh du m r ng Language 11 web website, web page Trang web SVTH: Quách Luyl ða Trang 5 luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C 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 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 cu. 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). Da trên d li u v khai phá d li u và khám phá tri th c t d li u v ăn bn (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 ng 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 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 and quickly, besides increasing the data quantity. Scientists have been studying 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 knowledge from data. In this study, we focus on understanding the data mining 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 aspect of data-mining from image (Image mining), web (web mining), ... The data-mining methods other. SVTH: Quách Luyl ða Trang 6 luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Ch ươ ng I : TNG 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 ca 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 n 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 c a n n kinh t m i – n n kinh t s ( hay có th g i là n n kinh t tri th c, n n kinh t da trên tri th c). 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 n 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 u ñã ñư a m t s k thu t nh m gi i quy 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 ñã ng 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 gi ý, có l b n s ngh ĩ: nó ñã ñc ñưc nh ng suy ngh ĩ c a mình! Mà ña ph n các g i ý ñ y g n nh ư là các thông tin mà b n c n tìm ki m. Vì sao Google bi t mình c n 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 bn 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 n 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? - Mt 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 bn các l a ch n v nh ng quy n sách mà 90% là b n c n mua. V y t i sao nó hi u b n nhi u nh ư th ? Và câu h i cu i cùng, vi c x lý thông tin c a nó ra sao? T t c nh ng câu hi ñ y là m t ng d ng c th c a khai phá d li u và khám phá tri th c. V y khai phá d li u là gì? I.2. LCH 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 ln d li u ñ tìm ra nh ng quy lu t ho c các m i quan h ch ưa bi t ñ u tiên v i mc ñí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.” SVTH: Quách Luyl ða Trang 7 luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Qua quá trình phát tri n, ñ nh ngh ĩa v khai phá d li u ngày càng ñưc m rng, và d n d n 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 da trên các c ơ s d li u l n nh m tìm ki m các m u hay các quy lu t (pattern) mi và h u d ng mà ch ưa t ng ñưc bi t tr ưc ñó. Ví d : “Nh ng sinh viên h c gi i 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 i 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 c 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 . Khai phá d li u không ch 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 dng 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 n hoàn ch nh c a l ĩnh v c khám phá tri th c (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á. Th ng kê tóm t t Xác Xác Thu Gi i ñnh th p và ñnh thu t Mu nhi m d ti n x khai v li u lý d phá liên li u D li u tr c ti p Hình I-2. Quá trình khai phá d li u Các khó kh ăn trong vi c khai thác tri th c t d li u: a) Tính qui mô: Vi 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 hp d li u ñuc l ưu tr ngày càng l n (gigabytes, 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 u ñ c bi t nh m qu n lý các v n ñ trong nghiên c u t ăng theo c p SVTH: Quách Luyl ða Trang 8 luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C s nhân. Tính qui mô (scalability) yêu c u ph ươ ng pháp cài ñt c a c u trúc d li u m i nh m 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 cn 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 ng 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 n d li u theo th i gian hay còn ñưc g i là d li u tu n 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 a 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 n, s l ưng các thu c tính có th t ăng dn 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 n nh t và ph c 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 a 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 hc ngày càng t ăng thì c n 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 n nh t (heterogeneous attributes). Bên c nh ñó, cũng ph i áp d ng ñưc cho các d li u ph c 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 n 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 n 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 n ñư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 i 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 ñ c n 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 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 n r t nhi u công s c ñ ki m tra các gi thuy t. Các công vi c phân tích d li u hi n t i ñòi h i ph i ñ t và ki m tra hàng nghìn gi ñ nh m t cách tu n 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á