luận văn: NGHIÊN CỨU VÀ ÁP DỤNG MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU VỚI CƠ SỞ DỮ LIỆU NGÀNH THUẾ VIỆT NAM

Chia sẻ: Nguyễn Thị Bích Ngọc | Ngày: | Loại File: PDF | Số trang:112

Thêm vào BST

Báo xấu

120
lượt xem 44
download

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

Thời đại phát triển mạnh của internet, intranet, data warehouse, cùng với sự phát triển nhanh về công nghệ lưu trữ đã tạo điều kiện cho các doanh nghiệp, các tổ chức thu nhập và sở hữu được khối lượng thông tin khổng lồ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: luận văn: NGHIÊN CỨU VÀ ÁP DỤNG MỘT SỐ KỸ THUẬT KHAI PHÁ DỮ LIỆU VỚI CƠ SỞ DỮ LIỆU NGÀNH THUẾ VIỆT NAM

B GIÁO D C VÀ ðÀO T O TRƯ NG ð I H C BÁCH KHOA HÀ N I NGUY N THU TRÀ ---------------------------------------------- LU N VĂN TH C S KHOA H C NGÀNH: CÔNG NGH THÔNG TIN CÔNG NGH THÔNG TIN NGHIÊN C U VÀ ÁP D NG M T S K THU T KHAI PHÁ D LI U V I CƠ S D LI U NGÀNH THU VI T NAM 2004-2006 NGUY N THU TRÀ Hà N i Hà N i 2006 2006
2 M CL C DANH M C CÁC KÝ HI U VÀ CÁC CH VI T T T........................4 DANH M C CÁC B NG ..........................................................................5 DANH M C CÁC HÌNH V .....................................................................6 M ð U .....................................................................................................8 CHƯƠNG 1. KHAI PHÁ D LI U .....................................................12 1.1. T ng quan khai phá d li u..................................................... 12 1.1.1 D li u .............................................................................. 14 1.1.2 Ti n x lý d li u .............................................................. 16 1.1.3 Mô hình khai phá d li u .................................................. 18 1.2. Các ch c năng cơ b n khai phá d li u .................................. 19 1.2.1 Phân l p (Classification) .................................................. 19 1.2.2 H i qui .............................................................................. 31 1.2.3 Phân nhóm........................................................................ 34 1.2.4 Khai phá lu t k t h p........................................................ 38 CHƯƠNG 2. M T S THU T TOÁN KHAI PHÁ D LI U ..........46 2.1. Thu t toán khai phá lu t k t h p............................................. 46 2.1.1 Thu t toán Apriori ............................................................ 46 2.1.2 Thu t toán AprioriTid ....................................................... 49 2.1.3 Thu t toán AprioriHybrid ................................................. 51 2.2. C i ti n hi u qu thu t toán Apriori........................................ 54 2.2.2 Phương pháp FP-tree ....................................................... 56 2.2.3 Thu t toán PHP ................................................................ 59 2.2.4 Thu t toán PCY................................................................. 63 2.2.5 Thu t toán PCY nhi u ch ng............................................. 65 2.3. Thu t toán phân l p b ng h c cây quy t ñ nh ........................ 67 2.3.1 Các ñ nh nghĩa.................................................................. 68 2.3.2 Thu t toán ID3.................................................................. 69 2.3.3 Các m r ng c a C4.5 ...................................................... 70 CHƯƠNG 3. ÁP D NG KHAI PHÁ TRÊN CSDL NGÀNH THU ..72 3.1. CSDL ngành Thu .................................................................. 72 3.2. L a ch n công c khai phá ..................................................... 73 3.2.1 L a ch n công c .............................................................. 73 3.2.2 Oracle Data Mining (ODM) ............................................. 76 3.2.3 DBMS_DATA_MINING.................................................... 78 3.3. M c tiêu khai thác thông tin c a ngành Thu ......................... 79
3 3.4. Th nghi m khai phá lu t k t h p .......................................... 81 3.5. Phân l p b ng h c cây quy t ñ nh .......................................... 91 3.5.1 Phân l p ðTNT d a vào so sánh t su t các năm ............. 93 3.5.2 Phân l p ðTNT theo s li u c a m t năm......................... 96 CHƯƠNG 4. K T LU N .................................................................... 102 HƯ NG NGHIÊN C U TI P THEO.................................................. 103 TÀI LI U THAM KH O ...................................................................... 104 PH L C ................................................................................................ 106
4 DANH M C CÁC KÝ HI U VÀ CÁC CH VI T T T Ký hi u, ch vi t t t Ý nghĩa Association Rules Các lu t k t h p Candidate itemset M t itemset trong t p Ck ñư c s d ng ñ sinh ra các large itemset Ck T p các candidate k-itemset giai ño n th k Confidence ð ch c ch n c a lu t k t h p = support(X∪Y)/support(X) ph n ánh kh năng giao d ch h tr X thì cũng h tr Y CSDL Cơ s d li u DM Data mining – Khai phá d li u DW Data warehouse – Kho d li u ðTNT ð i tư ng n p thu , ch t i các cá nhân ho c t ch c n p thu Frequent/large itemset M t itemset có ñ h tr (support) >= ngư ng ñ h tr t i thi u ID Identifier Item M t ph n t c a itemset Itemset T p c a các item k-itemset M t itemset có ñ dài k Lk T p các Large itemset giai ño n th k ODM Oracle Data Mining – 1 công c khai phá d li u TID Unique Transaction Identifier Transaction Giao d ch
5 DANH M C CÁC B NG B ng 1.1: CSDL ñơn gi n g m các ví d hu n luy n .................................... 25 B ng 1.2 Mô hình CSDL giao d ch ñơn gi n ................................................. 39 B ng 2.1 Cơ s d li u giao d ch T ............................................................... 56 B ng 2.2 B ng các s n ph m khai phá d li u ............................................... 74
6 DANH M C CÁC HÌNH V Hình 1.1 Quá trình khám phá tri th c ............................................................. 14 Hình 1.2 Khuôn d ng ñơn b n ghi và ña b n ghi ........................................... 16 Hình 1.3: Cây quy t ñ nh ñơn gi n v i các tests trên các thu c tính X và Y. 22 Hình 1.4: S phân l p m t m u m i d a trên mô hình cây quy t ñ nh ......... 23 Hình 1.5 Cây quy t ñ nh cu i cùng cho CSDL T ñã nêu trong b ng 1.1 ....... 29 Hình 1.6 Cây quy t ñ nh d ng gi code cho CSDL T (b ng 1.1)............... 29 Hình 1.7 H i qui tuy n tính ............................................................................ 32 Hình 1.8 G p nhóm theo phương pháp k-means (ði m ñánh d u + là tâm) 36 Hình 1.9 Phân ho ch vun ñ ng ho c tách d n ............................................... 37 Hình 1.10 Bư c l p ñ u tiên c a thu t toán Apriori cho CSDL DB .............. 41 Hình 1.11 L n l p th 2 c a thu t toán Apriori cho CSDL DB ..................... 42 Hình 1.12 L n l p th 3 c a thu t toán Apriori cho CSDL DB ..................... 42 Hình 2.1 Thu t toán Apriori............................................................................ 46 Hình 2.2 Thu t toán AprioriTid ...................................................................... 50 Hình 2.3 Ví d ................................................................................................ 51 Hình 2.4: Th i gian th c hi n cho m i l n duy t c a Apriori và AprioriTid 52 Hình 2.5: M t ví d c a cây phân c p khái ni m cho khai phá các frequent itemsets nhi u m c.......................................................................................... 55 Hình 2.6: FP-tree cho CSDL T trong b ng 2.1 ............................................... 57 Hình 2.7 Thu t toán PHP ................................................................................ 62 Hình 2.8 B nh v i 2 l n duy t c a thu t toán PCY .................................. 63 Hình 2.9 S d ng b nh cho các b ng băm nhi u ch ng............................. 66 Hình 3.1 Công s c c n cho m i giai ño n khai phá d li u .......................... 82 Hình 3.2 Các bư c khai phá lu t k t h p trên CSDL ngành Thu ................ 83 Hình 3.3 Nhánh cây phân c p ngành ngh .................................................... 85 Hình 3.4 Các lu t khai phá t ODM (ñ dài lu t = 2) ................................... 87
7 Hình 3.5 Các lu t khai phá t ODM (ñ dài lu t = 3) ................................... 89 Hình 3.6 Cây quy t ñ nh dùng ODM – Bài toán phân tích t su t................ 95 Hình 3.7 Cây quy t ñ nh dùng See5 – Bài toán phân tích t su t ................. 96 Hình 3.8 Cây quy t ñ nh dùng ODM – Bài toán xét s li u m t năm........... 99 Hình 3.9 Cây quy t ñ nh dùng See5 – Bài toán phân tích trong năm.......... 100
8 M ð U Th i ñ i phát tri n m nh c a Internet, Intranet, Data warehouse, cùng v i s phát tri n nhanh v công ngh lưu tr ñã t o ñi u ki n cho các doanh nghi p, các t ch c thu th p và s h u ñư c kh i lư ng thông tin kh ng l . Hàng tri u CSDL ñã ñư c dùng trong qu n tr kinh doanh, qu n lý chính ph , qu n lý d li u khoa h c và nhi u ng d ng khác. V i kh năng h tr m nh c a các H qu n tr CSDL, các CSDL này càng l n lên nhanh chóng. Câu “S l n m nh c a các CSDL d n ñ n s c n thi t ph i có các k thu t và các công c m i ñ th c hi n chuy n ñ i t ñ ng d li u m t cách thông minh thành thông tin và tri th c h u ích” [10] ñã tr thành ñ t v n ñ c a nhi u bài vi t v khai phá thông tin và tri th c t các CSDL l n. Công tác trong ngành Thu , nơi Công ngh thông tin ñư c áp d ng vào qu n lý Thu t nh ng năm 1986, CSDL thông tin liên quan ñ n các lĩnh v c qu n lý Thu là m t CSDL l n và ch c ch n ti m n nhi u thông tin quý báu. V i mong mu n bư c ñ u áp d ng k thu t khai phá d li u trên CSDL ngành Thu , lu n văn ñã t p trung nghiên c u v các k thu t khai phá d li u và ti n hành khai phá th nghi m trên CSDL ngành Thu . Kh năng m r ng tri th c có ích n trong d li u ñ ñưa ra nh ng hành ñ ng c n thi t d a trên tri th c ñó ñang tr nên ngày càng quan tr ng trong th gi i c nh tranh hi n nay. Toàn b quá trình dùng các phương pháp lu n d a trên tính toán, bao g m các k thu t m i ñ phát hi n ra tri th c t d li u ñư c g i là khai phá d li u (data mining). [9] Khai phá d li u là s tìm ki m thông tin m i, có giá tr và không t m thư ng trong m t kh i lư ng d li u l n. Nó là s ph i h p n l c c a con ngư i và máy tính. Các k t qu t t nh t nh n ñư c b ng vi c cân b ng gi a
9 tri th c c a các chuyên gia con ngư i trong vi c mô t các v n ñ và m c ñích v i kh năng tìm ki m c a máy tính. Hai m c ñích chính c a khai phá d li u là ñ d ñoán (prediction) và mô t (description). D ñoán bao g m vi c dùng m t vài bi n ho c trư ng trong t p d li u ñ d ñoán các giá tr tương lai ho c chưa bi t c a các bi n c n quan tâm. Còn mô t t p trung vào vi c tìm ra các m u mô t d li u mà con ngư i có th hi u ñư c/ biên d ch ñư c. Có th ñưa các ho t ñ ng khai phá d li u vào m t trong hai lo i sau:  Khai phá d li u d báo, t o ra mô hình c a h th ng ñư c mô t b i t p d li u cho trư c, ho c  Khai phá d li u mô t , v i vi c t o ra thông tin m i, không t m thư ng d a trên t p d li u có s n. M t s ch c năng khai phá d li u chính như:  Mô t khái ni m: Mô t ñ c ñi m và phân bi t. Tìm ra các ñ c ñi m khái quát hoá, t ng k t, các ñ c ñi m khác nhau trong d li u.  K t h p: xem xét v tương quan và quan h nhân qu .  Phân l p và d báo (Classification and Prediction): Xác ñ nh mô hình mô t các l p riêng bi t và dùng cho d ñoán tương lai.  Phân tích nhóm (Cluster analysis): Chưa bi t nhãn l p, th c hi n nhóm d li u thành các l p m i d a trên nguyên t c c c ñ i hoá s tương t trong cùng l p và c c ti u hoá s khác tương t gi a các l p khác nhau.  Phân tích nhi u (Outlier analysis): H u ích trong vi c phát hi n l i, phân tích các s ki n hi m.  Phân tích xu hư ng và s phát tri n Khai phá d li u là m t trong nh ng lĩnh v c phát tri n nhanh nh t trong công nghi p máy tính. T ch là m t mi n quan tâm nh trong khoa h c
10 máy tính và th ng kê, nó ñã nhanh chóng m r ng thành m t lĩnh v c/ngành c a riêng nó. M t trong nh ng l n m nh nh t c a khai phá d li u là s nh hư ng trong ph m vi r ng c a các phương pháp lu n và các k thu t ñư c ng d ng ñ i v i m t lo t các bài toán, các lĩnh v c. Trong kinh doanh, khai phá d li u có th ñư c dùng ñ khám phá ra nh ng xu hư ng mua s m m i, k ho ch cho các chi n lư c ñ u tư, và phát hi n nh ng s tiêu dùng không chính ñáng t h th ng k toán. Nó có th giúp c i ti n các chi n d ch marketing ñ mang l i nhi u h tr và quan tâm hơn t i khách hàng. Các k thu t khai phá d li u có th ñư c áp d ng ñ i v i các bài toán thi t k l i quy trình kinh doanh, trong ñó m c ñích là ñ hi u ñư c các tương tác và quan h trong thông l kinh doanh và các t ch c kinh doanh. Nhi u ñơn v thi hành lu t, các ñơn v ñi u tra ñ c bi t, có nhi m v tìm ra các hành ñ ng không trung th c và phát hi n ra các xu hư ng ph m t i, cũng ñã s d ng khai phá d li u m t cách thành công. Các k thu t khai phá d li u cũng có th ñư c dùng trong các t ch c tình báo nơi lưu gi nhi u ngu n d li u l n liên quan ñ n các ho t ñ ng, các v n ñ v an ninh qu c gia. V i m c ñích nghiên c u m t s phương pháp khai phá d li u và th nghi m khai phá trên CSDL ngành Thu , lu n văn ñư c trình bày v i các ph n sau: Chương 1 – Khai phá d li u: Tìm hi u các ch c năng khai phá d li u. Chương 2 – M t s thu t toán khai phá d li u. Nghiên c u trên hai ki u khai phá: Khai phá lu t k t h p - m t k thu t thông d ng trong h c không giám sát. Phân l p b ng h c cây quy t ñ nh - k thu t h c có giám sát. Chương 3 – Áp d ng khai phá trên CSDL ngành Thu : Th nghi m khai phá lu t k t h p và phân l p trên CSDL ngành Thu
11 Chương 4 – K t lu n và nh ng k t qu ñ t ñư c Cu i cùng là m t s hư ng nghiên c u ti p theo. Em xin chân thành c m ơn PGS. TS Nguy n Ng c Bình ñã hư ng d n và cho em nh ng ý ki n quý báu, chân thành c m ơn các th y cô giáo c a trư ng ð i h c Bách khoa Hà N i ñã trang b ki n th c giúp em hoàn thành lu n văn này.
12 CHƯƠNG 1. KHAI PHÁ D LI U 1.1. T ng quan khai phá d li u Khai phá d li u có ngu n g c t các phương pháp riêng bi t, 2 d ng quan tr ng nh t là th ng kê và h c máy. Th ng kê có ngu n g c t toán h c và do ñó nh n m nh ñ n ñ chính xác toán h c, mong mu n thi t l p cái mà có th nh n ra trên n n toán h c trư c khi ki m th nó trong th c t . Ngư c l i, h c máy có ngu n g c r t nhi u trong th c ti n tính toán. ði u này d n ñ n s hư ng th c ti n, s n sàng ki m th ñ bi t nó th c hi n t t th nào mà không c n ch m t ch ng minh chính th c. [9] Có th có ñ nh nghĩa v Khai phá d li u như sau: Khai phá d li u là quá trình phát hi n các mô hình, các t ng k t khác nhau và các giá tr ñư c l y t t p d li u cho trư c. [9] Hay, Khai phá d li u là s thăm dò và phân tích lư ng d li u l n ñ khám phá t d li u ra các m u h p l , m i l , có ích và có th hi u ñư c [14]. H p l là các m u ñ m b o tính t ng quát, m i l là m u chưa ñư c bi t trư c ñó, có ích là có th d a vào m u ñó ñưa ra các hành ñ ng phù h p, hi u ñư c là có th biên d ch và hi u th u ñáo các m u. Các k năng phân tích c a con ngư i là không ñ y ñ do: Kích thư c và chi u c a d li u; t c ñ tăng trư ng c a d li u là r t l n. Thêm vào ñó là nh ng ñáp ng m nh m c a k thu t v kh năng: thu th p d li u, lưu tr , năng l c tính toán, ph n m m, s thành th o v chuyên môn. Ngoài ra còn có môi trư ng c nh tranh v d ch v , ch không ch c nh tranh v giá (ñ i v i Ngân hàng, công ty ñi n tho i, khách s n, công ty cho thuê …) v i câu “Bí quy t c a s thành công là bi t nh ng gì mà không ai khác bi t” (Aristotle Onassis [14]). T t c nh ng ñi u ñó chính là nh ng nguyên nhân thúc ñ y Khai phá d li u phát tri n.
13 Quá trình khám phá tri th c: Trư c tiên, phân bi t gi a các thu t ng “mô hình (model)” và “m u (pattern)” dùng trong khai phá d li u. Mô hình là m t c u trúc “quy mô l n”, có th là t ng k t các quan h qua nhi u trư ng h p (case) (ñôi khi là t t c các trư ng h p), trong khi m u là m t c u trúc c c b , tho mãn b i m t s ít trư ng h p ho c trong m t mi n nh c a không gian d li u. Trong khai phá d li u, m t m u ñơn gi n là m t mô hình c c b . Quá trình khám phá tri th c ti n hành theo các bư c sau: 1. Xác ñ nh bài toán nghi p v : Trư c tiên ph i tìm hi u lĩnh v c c a ng d ng nghi p v ; Tìm hi u các tri th c liên quan và các m c ñích c a ng d ng. 2. Khai phá d li u - L a ch n d li u: Xác ñ nh các t p d li u ñích và các trư ng liên quan - Làm s ch d li u: Xoá b nhi u, ti n x lý. Ph n vi c này có th chi m t i 60% công s c. - Gi m b t d li u và chuy n ñ i d li u: Tìm ra nh ng ñ c trưng h u d ng, gi m b t các chi u ho c các bi n, bi u di n l i các ñ i lư ng b t bi n - L a ch n ch c năng khai phá d li u: T ng k t, phân l p, H i qui, k t h p, phân nhóm. - L a ch n thu t toán khai phá. - Th c hi n khai phá d li u (Data Mining): Tìm ki m các m u quan tâm - ðánh giá các m u và bi u di n tri th c
14 Hình 1.1 Quá trình khám phá tri th c 3. Áp d ng khám phá tri th c 4. ðánh giá và ño ñ c 5. Tri n khai và tích h p vào các qui trình nghi p v 1.1.1 D li u Do có nhi u ki u d li u, các CSDL s d ng trong các ng d ng cũng khác nhau, nên ngư i dùng luôn mong ñ i m t h th ng khai phá d li u có th ñi u khi n ñư c t t c các lo i d li u. Th c t CSDL có s n thư ng là CSDL quan h và h th ng khai phá d li u cũng th c hi n hi u qu vi c khai phá tri th c trên d li u quan h . V i nh ng CSDL c a ng d ng ch a các ki u d li u ph c t p, như d li u hypertext và multimedia, d li u t m và không gian (spatial), d li u k th a (legacy)… thư ng ph i có các h th ng khai phá d li u riêng bi t xây d ng ñ khai phá cho các ki u d li u c th .
15 D li u ñư c khai phá có th là d li u có c u trúc, ho c không có c u trúc. M i b n ghi d li u ñư c coi như m t trư ng h p ho c m t ví d (case/example). Phân bi t hai ki u thu c tính: phân lo i (categorical) và s (numerical). Các thu c tính ki u phân lo i là nh ng thu c tính có các giá tr thu c vào m t s lư ng nh các phân lo i ho c các l p riêng r và gi a chúng không có th t n nào. N u ch có 2 giá tr , ví d là yes và no, ho c male và female, thu c tính ñư c coi là binary. N u có hơn 2 giá tr , ví d , nh , v a, l n, r t l n, thu c tính ñư c coi là ña l p (multiclass). Các thu c tính s là nh ng thu c tính l y các giá tr liên t c, ví d , thu nh p hàng năm, ho c tu i. Thu nh p hàng năm ho c tu i có th v lý thuy t là b t kỳ m t giá tr nào t 0 t i vô h n, m c dù m i giá tr thư ng xu t hi n phù h p v i th c t . Các thu c tính s có th ñư c bi n ñ i thành categorical: Ví d , thu nh p hàng năm có th ñư c chia thành các lo i: th p, trung bình, cao. D li u không có c u trúc có th áp d ng các thu t toán khai phá d li u thư ng là d li u ki u Text. Khuôn d ng b ng c a d li u có th thu c hai lo i:  D li u d ng ñơn b n ghi (còn g i là ki u không giao d ch), ñây là các b ng d li u quan h thông thư ng.  D li u d ng ña b n ghi (còn g i là ki u giao d ch), ñư c dùng cho d li u v i nhi u thu c tính. d ng ñơn b n ghi (ki u không giao d ch), m i b n ghi ñư c lưu tr như 1 dòng trong b ng. D li u ñơn b n ghi không ñòi h i cung c p khoá ñ xác ñ nh duy nh t m i b n ghi. Nhưng, khoá là c n cho các trư ng h p k t h p (associate) ñ có k t qu cho h c có giám sát.
16 Trong d ng ña b n ghi (ki u giao d ch), m i trư ng h p (case) ñư c lưu trong nhi u b n ghi trong m t b ng v i các c t: dãy s ñ nh danh, tên thu c tính, giá tr . Hình 1.2 Khuôn d ng ñơn b n ghi và ña b n ghi 1.1.2 Ti n x lý d li u D li u ñư c ch n l c s ph i qua bư c ti n x lý trư c khi ti n hành khai phá phát hi n tri th c. Bư c thu th p và ti n x lý d li u là bư c r t ph c t p. ð m t gi i thu t DM th c hi n trên toàn b CSDL s r t c ng k nh, kém hi u qu . Trong quá trình khai phá d li u, nhi u khi ph i th c hi n liên k t/tích h p d li u t r t nhi u ngu n khác nhau. Các h th ng s n có ñư c thi t k v i nh ng m c ñích và ñ i tư ng ph c v khác nhau, khi t p h p d li u t nh ng h th ng này ñ ph c v khai phá d li u, hi n tư ng dư th a là r t ph bi n, ngoài ra còn có th x y ra xung ñ t gây m y d li u, d li u không ñ ng nh t, không chính xác. Rõ ràng yêu c u ch n l c và làm s ch d li u là r t c n thi t. N u ñ u vào c a quá trình khai phá là d li u trong DW thì s r t thu n ti n, vì d li u này ñã ñư c làm s ch, nh t quán và có tính ch t hư ng ch ñ .
17 Tuy nhiên nhi u khi v n ph i có thêm m t s bư c ti n x lý ñ ñưa d li u v ñúng d ng c n thi t. Ngoài m t s x lý thông thư ng như: bi n ñ i, t p h p d li u t nhi u ngu n v m t kho chung, x lý ñ ñ m b o nh t quán d li u (kh các trư ng h p l p, th ng nh t cách ký hi u, chuy n ñ i v khuôn d ng th ng nh t (ñơn v ti n t , ngày tháng..)). M t s x lý ñ c bi t c n chú ý trong bư c ti n x lý d li u: X lý v i d li u thi u (missing data): Thư ng thì khi khai phá d li u không ñòi h i NSD ph i x lý các giá tr thi u b ng cách th c ñ c bi t nào. Khi khai phá, thu t toán khai phá s b qua các giá tr thi u. Tuy nhiên trong m t vài trư ng h p c n chú ý ñ ñ m b o thu t toán phân bi t ñư c gi a giá tr có nghĩa (“0”) v i giá tr tr ng. (tham kh o trong [11]). Các giá tr gây nhi u (Outliers): M t outlier là m t giá tr xa bên ngoài c a mi n thông thư ng trong t p h p d li u, là giá tr chênh l ch v i chu n v ý nghĩa. S có m t c a outliers có th có nh hư ng ñáng k trong các mô hình khai phá d li u. Outliers nh hư ng ñ n khai phá d li u trong bư c ti n x lý d li u ho c là khi nó ñư c th c hi n b i NSD ho c t ñ ng trong khi xây d ng mô hình. Binning: M t vài thu t toán khai phá d li u có th có l i nh vi c binning v i c hai lo i d li u number và categorical. Các thu t toán Naive Bayes, Adaptive Bayes Network, Clustering, Attribute Importance, và Association Rules có th có l i t vi c binning. Binning nghĩa là nhóm các giá tr liên quan v i nhau, như v y gi m s lư ng các giá tr riêng bi t c a m t thu c tính. Có ít hơn các giá tr riêng bi t d n ñ n mô hình g n nh và xây d ng ñư c nhanh hơn, nhưng nó cũng có th
18 d n ñ n vi c m t ñi ñ chính xác [11] (Các phương pháp tính toán ranh gi i bin [11]). 1.1.3 Mô hình khai phá d li u Mô hình khai phá d li u là m t mô t v m t khía c nh c th c a m t t p d li u. Nó t o ra các giá tr ñ u ra cho t p các giá tr ñ u vào. Ví d : Mô hình H i qui tuy n tính, mô hình phân l p, mô hình phân nhóm. M t mô hình khai phá d li u có th ñư c mô t 2 m c:  M c ch c năng (Function level): Mô t mô hình b ng nh ng thu t ng v d ñ nh s d ng. Ví d : Phân l p, phân nhóm.  M c bi u di n (representation level): Bi u di n c th m t mô hình. Ví d : Mô hình log-linear, cây phân l p, phương pháp láng gi ng g n nh t. Các mô hình khai phá d li u d a trên 2 ki u h c: có giám sát và không giám sát (ñôi khi ñư c nói ñ n như là h c tr c ti p và không tr c ti p – directed and undirected learning) [11]. Các hàm h c có giám sát (Supervised learning functions) ñư c s d ng ñ d ñoán giá tr . Các hàm h c không giám sát ñư c dùng ñ tìm ra c u trúc bên trong, các quan h ho c tính gi ng nhau trong n i dung d li u nhưng không có l p hay nhãn nào ñư c gán ưu tiên. Ví d c a các thu t toán h c không giám sát g m phân nhóm k-mean (k-mean clustering) và các lu t k t h p Apriori. M t ví d c a thu t toán h c có giám sát bao g m Naive Bayes cho phân l p (classification). Tương ng có 2 lo i mô hình khai phá d li u:  Các mô hình d báo (h c có giám sát):
19 • Phân l p: nhóm các items thành các l p riêng bi t và d ñoán m t item s thu c vào l p nào. • H i qui (Regression): x p x hàm và d báo các giá tr liên t c • ð quan tr ng c a thu c tính: xác ñ nh các thu c tính là quan tr ng nh t trong các k t qu d báo  Các mô hình mô t (h c không giám sát): • Phân nhóm (Clustering): Tìm các nhóm t nhiên trong d li u • Các mô hình k t h p (Association models): Phân tích “gi hàng” • Trích ch n ñ c trưng (Feature extraction): T o các thu c tính (ñ c trưng) m i như là k t h p c a các thu c tính ban ñ u 1.2. Các ch c năng cơ b n khai phá d li u 1.2.1 Phân l p (Classification) Trong bài toán phân l p, ta có d li u l ch s (các ví d ñư c gán nhãn - thu c l p nào) và các d li u m i chưa ñư c gán nhãn. M i ví d ñư c gán nhãn bao g m nhi u thu c tính d báo và m t thu c tính ñích (bi n ph thu c). Giá tr c a thu c tính ñích chính là nhãn c a l p. Các ví d không ñư c gán nhãn ch bao g m các thu c tính d báo. M c ñích c a vi c phân l p là xây d ng mô hình d a vào d li u l ch s ñ d báo chính xác nhãn (l p) c a các ví d không gán nhãn. [11] Nhi m v phân l p b t ñ u v i vi c xây d ng d li u (d li u hu n luy n) có các giá tr ñích (nhãn l p) ñã bi t. Các thu t toán phân l p khác nhau dùng các k thu t khác nhau cho vi c tìm các quan h gi a các giá tr c a thu c tính d báo và các giá tr c a thu c tính ñích trong d li u hu n luy n. Nh ng quan h này ñư c t ng k t trong mô hình, sau ñó ñư c dùng
20 cho các trư ng h p m i v i các giá tr ñích chưa bi t ñ d ñoán các giá tr ñích. Mô hình phân l p có th ñư c dùng trên b d li u ki m th /d li u ñánh giá v i m c ñích so sánh các giá tr d báo v i các câu tr l i ñã bi t. K thu t này ñư c g i là ki m tra mô hình, nó ño ñ chính xác d báo c a mô hình. Áp d ng mô hình phân l p ñ i v i d li u m i ñư c g i là s d ng mô hình, và d li u ñư c g i là d li u s d ng hay d li u trung tâm (apply data or scoring data). Vi c s d ng d li u thư ng ñư c g i là ‘scoring the data’. S phân l p ñư c dùng trong phân ño n khách hàng, phân tích tín d ng, và nhi u ng d ng khác. Ví d , công ty th tín d ng mu n d báo nh ng khách hàng nào s không tr ñúng h n trên các chi tr c a h . M i khách hàng tương ng v i m t trư ng h p; d li u cho m i trư ng h p có th bao g m m t s thu c tính mô t thói quen tiêu dùng c a khách hàng, thu nh p, các thu c tính nhân kh u h c,… ðây là nh ng thu c tính d báo. Thu c tính ñích ch ra có hay không ngư i khách hàng ñã v n /không tr ñúng h n; như v y, có hai l p có kh năng, tương ng v i v n ho c không. D li u hu n luy n s ñư c dùng ñ xây d ng mô hình dùng cho d báo các trư ng h p m i sau này (d báo khách hàng m i có kh năng chi tr n không). Chi phí (Costs): Trong bài toán phân l p, có th c n xác ñ nh chi phí bao hàm trong vi c t o ra m t quy t ñ nh sai l m. Vi c này là quan tr ng và c n thi t khi có chênh l ch chi phí l n gi a các phân l p sai (misclassification). Ví d , bài toán d báo có hay không m t ngư i s tr l i v i thư qu ng cáo. ðích có 2 phân lo i: YES (khách hàng tr l i) và NO (khách hàng không tr l i). Gi s tr l i tích c c ñ i v i qu ng cáo sinh ra $500 và nó tr giá $5 ñ g i thư. N u