intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Luận văn tốt nghiệp: Khai mỏ dữ liệu và khám phá tri thức - ĐH Tây Đô

Chia sẻ: Nguyễn Thị Minh | Ngày: | Loại File: PDF | Số trang:104

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

Luận văn tốt nghiệp - Khai mỏ dữ liệu và khám phá tri thức đ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ảng, chương trình khai phá dữ liệu, lập trình xử lý một 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,...Mời bạn đọc cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Luận văn tốt nghiệp: Khai mỏ dữ liệu và khám phá tri thức - ĐH Tây Đô

  1. 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 L p: ð i h c Tin h c 2 C n Thơ, 2011
  2. 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 L p: ð i h c 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 b o v t i: H i ñ 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:
  3. 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” 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 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 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 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à 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 ñ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 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 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 ơn!
  4. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C M CL 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:................................................................................................... 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 K T 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
  5. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C B NG KÝ HI U VÀ VI T T T T VI T STT TI NG ANH NGHĨA TI NG VI T T T 01 ANN Artifical neural network M ng 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 T p 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 d u m r ng Language 11 web website, web page Trang web SVTH: Quách Luyl ða Trang 5
  6. 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 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. 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
  7. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C 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 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 d a 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 g i ý, 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 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 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? - 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 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 h i ñ 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. 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 ñ 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.” SVTH: Quách Luyl ða Trang 7
  8. 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 r ng, 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 d a 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) m i 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 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 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 ñ nh th p và thu t M u 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ô: 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 (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
  9. 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 c 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 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 d n 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 h c 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á 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 SVTH: Quách Luyl ða Trang 9
  10. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C li u 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 c 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 u v quá trình khai phá d li u và khám phá tri th c t d li u. Qua vi c nghiên c u 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 ñó có ñư c nh ng ki n th c 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 quá trình nghiên c u và th c ti n ñ có th th y ñư c các v n ñ thách th c trong lĩnh v c khai phá d li u. S d ng cơ s lý thuy t ñã nghiên c u ñ 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 ñó 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 c. 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 ng minh cho các thu t toán và gi i thu t ñã nghiên c u. 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 ng cây quy t ñ nh và lu t k t h p b ng 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án. SVTH: Quách Luyl ða Trang 10
  11. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C 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 c 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 n th nh t v Khám phá tri th c và Khai phá d li u (Knowledge Discovery and Data mining, ñư c t ch c Motreal vào năm 1995, Usama Fayaad ñã ñưa ra khái ni m chính th c v Data mining. Nó ñư c s d ng ñ ch 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 c trư c ñây chưa bi t s ñư c suy lu n t kho d li u kh ng l , mà dư ng như không có b t c m t quy lu t ho c m i quan h rõ ràng nào. Khi thu t ng “Data mining” t t ñư c hình thành, nó ñã tr thành ki n th c dành cho vi c suy lu n. ði u này h t s c h u ích vì ñã bác b 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 ng m c ñ 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 m 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 ng ñư 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 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. 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 . Khai phá d li u không ch 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 c trong cơ s d li u (Hình II-1), ta có m t s khái ni m như sau: SVTH: Quách Luyl ða Trang 11
  12. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C - Input Data: d li u ñ 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 nhi u ngu n d li u khác nhau, làm s ch (clean) d li u b ng cách lo i b nhi u 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 ng 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 c quan tr ng, khá n ng nh c và tiêu t n nhi u th i gian cũng như công s c. - Postproccessing: H u x lý k t qu là quá trình lo i b 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 u 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 tr ra quy t ñ nh (Decision Support System). II.1.2. Nhi m 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 : ð quy 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 ng viên xin h c b ng? Ngư i/ t ch c 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 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 n này thư ng là gi i thích v m t b n ch t và thư ng yêu c u các k thu t h u x lý (postproccessing) nh m 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 ng 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: SVTH: Quách Luyl ða Trang 12
  13. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Hình II-2. B n nhi m v tr ng tâm c a khai phá d li u 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 n ñư 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 bi u di n b ng 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 ng cách làm hi u qu hay nói cách khác là ph i “lo i b 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: SVTH: Quách Luyl ða Trang 13
  14. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C 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 khi ra ñ i, khai phá d li u ñư c ng d ng r ng rãi, sau ñây là m t s 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 a 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 ñó ñưa ra các chi n lư c, phương pháp kinh doanh m i nh m m c ñích: - Khách hàng có l i và nh ng ñ c ñi m nào làm cho h như v y. SVTH: Quách Luyl ða Trang 14
  15. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C - 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. - Nh ng 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 n mua hàng,.. - Nh ng 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 c kh e: Lưu tr thông tin các b nh, các hi n tư ng, tri u ch ng,…t ñó, 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 y 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 y 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 a 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 n t ho c t p h p các ph n 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 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 c. 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 ng 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 ng ñ 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 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 m làm rõ tính ch t c a ñ i tư ng. Ví d : Xác ñ nh cân n ng b ng kg, chi u dài b ng 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: SVTH: Quách Luyl ða Trang 15
  16. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Ki u thu c tính STT Mô t Ví d (Attributed type) Giá tr c a thu c tính ki u Mã t nh, mã nominal là các tên g i hay ñ nh nhân viên, gi i ð nh danh danh khác nhau, ch cung c p tính,.. 1 (nominal) v a ñ thông tin ñ phân bi t gi ng nhau hay khác nhau (=, ≠ ). Giá tr thu c tính ki u ordinal Cao, cao hơn, Th t cung c p ñ y ñ thông tin ñ cao nh t,… 2 (ordinal) phân bi t (=, ≠ ) và so sánh theo th t (=). ð i v i thu c tính ki u interval, Ngày tháng ngoài phân bi t cung c p ñ y ñ năm Kho ng cách thông tin ñ phân bi t(=, ≠ ), so ð C ho c ñ F 3 (interval) sánh (=), s khác nhau (+,-) gi a các giá tr là h t s c quan tr ng. ð i v i thu c tính ki u ratio, s S lư ng, ñ T l khác nhau (+,-) và t l (*,/) dài, tu i,… 4 (ratio) gi a các giá tr là h t s c quan tr ng Trong ñó, thu c tính ki u ñ nh danh và th 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 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 ng 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 i ký t . Ví d : mã t nh, s ñi n tho i, gi i tính, s ch ng 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). SVTH: Quách Luyl ða Trang 16
  17. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C o D li u trên cơ s ñ th (graph-based data). o D li u có th 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 c 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 ng. H u h t các thu c tính c a các ñ i tư ng có giá tr 0 nhưng ch 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 n 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 c ñ khác nhau và tính ch t c a d li u cũng khác nhau tùy vào m c ñ phân gi i. M u trong d li u thư ng ph thu c nhi u vào m c ñ 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 u 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 i 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 ng (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). SVTH: Quách Luyl ða b) Ma tr n d li u Trang 17 a) D li u m u tin
  18. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C IDcustomers Items 1 Bread, coke, milk 2 Beer, Bread 3 Beer, Coke, Diaper, Milk 4 Beer, Bread, Diaper, Milk 5 Coke, Diaper, Milk Hình II-4. Các ñ i tư ng c a d li u d ng m u tin 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 n 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 n b ng các nút trên ñ th còn m i quan h gi a các ñ i tư ng thì ñư c bi u di n b ng 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. a) Các trang web ñư c liên k t v i nhau b) C u trúc ADN Hình II-5. Các ñ i tư ng d li u d a trên ñ th D li u có th 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 t . D li u có th 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 m u tin và t ng 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 ng th i ñi m như sau: SVTH: Quách Luyl ða Trang 18
  19. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C Hình II-6. B ng d li u giao d ch theo th i gian 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 i: (sequence data) là m t t p h p d li u mà nó là m t chu i các th c th ñơn l gi ng như 1 chu i các con s , ký t hay t 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 bi u di n như 1 chu i 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 i, m i m u tin là 1 time series. Nói cách khác, m i m u tin là m t chu i 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. Ch t 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õ ng d ng c th . Chính vì v y mà ch t lư ng d li u là m t v n ñ c n quan tâm khi khai thác chi th c t d li u. Vì v y, trư c khi s d ng, d li u ph i ñư c x lý ñ lo i b nhi u, cũng như lo i b 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. SVTH: Quách Luyl ða Trang 19
  20. luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U VÀ KHÁM PHÁ TRI TH C 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 n. Nguyên nhân c a nh ng v n ñ trên có th ñ n t : - L i c a con ngư i, có th nói ñ n l i 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. - L i 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 n quan tâm ñ n các v n ñ sau: a) L i ño lư ng và thu th p d li u: L i c a s ño lư ng có th ñ n t 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 i có th x y ra do nh ng nguyê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 huy t áp c a b nh nhân, tư th ño : n m 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 i l n ño huy t áp. - L i thu th p d li u x y ra do quá trình thu th p d li u và thư ng là b 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 n có các thông tin: lư ng b ch c u 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 suy th n,…n u thi u 1 trong các tri u ch ng 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 u và d li u b bóp méo: Nhi u ñư c hi u là thành ph n ng u nhiên c a l i ño lư ng d li u. L i 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 i 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 u 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 u chưa h p lý và làm m t quá nhi u thông tin,… SVTH: Quách Luyl ða Trang 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
6=>0