ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGHIÊN CỨU CÁC THUẬT TOÁN PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT ĐỊNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông

Description
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGHIÊN CỨU CÁC THUẬT TOÁN PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT ĐỊNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin

Please download to get full document.

View again

of 67
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Psychiatry

Publish on:

Views: 2 | Pages: 67

Extension: PDF | Download: 0

Share
Tags
Transcript
    ĐẠ I H Ọ C QU Ố C GIA HÀ N Ộ I TR  ƯỜ  NG ĐẠ I H Ọ C CÔNG NGH Ệ   Nguy ễ n Th ị  Thùy Linh NGHIÊN C Ứ  U CÁC THU Ậ T TOÁN PHÂN L Ớ  P D Ữ   LI Ệ U D Ự  A TRÊN CÂY QUY Ế T ĐỊ NH KHÓA LU Ậ N T Ố T NGHI Ệ P ĐẠ I H Ọ C H Ệ  CHÍNH QUY HÀ N Ộ I - 2005  Ngành: Công ngh ệ  thông tin    ĐẠ I H Ọ C QU Ố C GIA HÀ N Ộ I TR  ƯỜ  NG ĐẠ I H Ọ C CÔNG NGH Ệ   Nguy ễ n Th ị  Thùy Linh NGHIÊN C Ứ  U CÁC THU Ậ T TOÁN PHÂN L Ớ  P D Ữ   LI Ệ U D Ự  A TRÊN CÂY QUY Ế T ĐỊ NH KHÓA LU Ậ N T Ố T NGHI Ệ P ĐẠ I H Ọ C H Ệ  CHÍNH QUY HÀ N Ộ I - 2005 Ngành: Công ngh ệ  thông tin Cán b ộ  h ướ  ng d ẫ n: TS. Nguy ễ n H ả i Châu    - i - TÓM T Ắ T N Ộ I DUNG Phân l ớ   p d ữ  li ệ u là m ộ t trong nh ữ ng h ướ  ng nghiên c ứ u chính c ủ a khai phá d ữ  li ệ u. Công ngh ệ  này đ ã, đ ang và s ẽ  có nhi ề u ứ ng d ụ ng trong các l  ĩ  nh v ự c th ươ  ng m ạ i, ngân hàng, y t ế , giáo d ụ c…Trong các mô hình phân l ớ   p đ ã đượ  c đề  xu ấ t, cây quy ế t đị nh đượ  c coi là công c ụ  m ạ nh, ph ổ  bi ế n và đặ c bi ệ t thích h ợ   p v ớ  i các ứ ng d ụ ng khai  phá d ữ  li ệ u. Thu ậ t toán phân l ớ   p là nhân t ố  trung tâm trong m ộ t mô hình phân l ớ   p. Khóa lu ậ n đ ã nghiên c ứ u v ấ n đề  phân l ớ   p d ữ  li ệ u d ự a trên cây quy ế t đị nh. T ừ   đ ó t ậ  p trung vào phân tích, đ ánh giá, so sánh hai thu ậ t toán tiêu bi ể u cho hai ph ạ m vi ứ ng d ụ ng khác nhau là C4.5 và SPRINT. V ớ  i các chi ế n l ượ  c riêng v ề  l ự a ch ọ n thu ộ c tính phát tri ể n, cách th ứ c l ư u tr  ữ  phân chia d ữ  li ệ u, và m ộ t s ố   đặ c đ i ể m khác, C4.5 là thu ậ t toán ph ổ  bi ế n nh ấ t khi phân l ớ   p t ậ  p d ữ  li ệ u v ừ a và nh ỏ , SPRINT là thu ậ t toán tiêu bi ể u áp d ụ ng cho nh ữ ng t ậ  p d ữ  li ệ u có kích th ướ  c c ự c l ớ  n. Khóa lu ậ n đ ã ch ạ y th ử  nghi ệ m mô hình phân l ớ   p C4.5 v ớ  i t ậ  p d ữ  li ệ u th ự c và thu đượ  c m ộ t s ố  k  ế t qu ả  phân l ớ   p có ý ngh  ĩ  a th ự c ti ễ n cao, đồ ng th ờ  i đ ánh giá đượ  c hi ệ u n ă ng c ủ a mô hình phân l ớ   p C4.5. Trên c ơ   s ở   nghiên c ứ u lý thuy ế t và quá trình th ự c nghi ệ m, khóa lu ậ n đ ã đề  xu ấ t m ộ t s ố  c ả i ti ế n mô hình phân l ớ   p C4.5 và ti ế n t ớ  i cài đặ t SPRINT.    - ii - L Ờ I C Ả M Ơ N Trong su ố t th ờ  i gian h ọ c t ậ  p, hoàn thành khóa lu ậ n em đ ã may m ắ n đượ  c các th ầ y cô ch ỉ  b ả o, dìu d ắ t và đượ  c gia đ ình, b ạ n bè quan tâm, độ ng viên. Em xin đượ  c bày t ỏ  lòng bi ế t ơ  n chân thành t ớ  i các th ầ y cô tr  ườ  ng Đạ i h ọ c Công Ngh ệ   đ ã truy ề n đạ t cho em ngu ồ n ki ế n th ứ c vô cùng quý báu c ũ ng nh ư  cách h ọ c t ậ  p và nghiên c ứ u khoa h ọ c. Cho phép em đượ  c g ử i l ờ  i c ả m ơ  n sâu s ắ c nh ấ t t ớ  i TS. Nguy ễ n H ả i Châu, ng ườ  i th ầ y đ ã r  ấ t nhi ệ t tình ch ỉ  b ả o và h ướ  ng d ẫ n em trong su ố t quá trình th ự c hi ệ n khóa lu ậ n. V ớ  i t ấ t c ả  t ấ m lòng mình, em xin bày t ỏ  lòng bi ế t ơ  n sâu s ắ c đế n TS. Hà Quang Th ụ y đ ã t ạ o đ i ề u ki ệ n thu ậ n l ợ  i và cho em nh ữ ng đị nh h ướ  ng nghiên c ứ u. Em xin l ờ  i c ả m ơ  n t ớ  i Nghiên c ứ u sinh Đ oàn S ơ  n (JAIST) đ ã cung c ấ  p tài li ệ u và cho em nh ữ ng l ờ  i khuyên quý báu. Em c ũ ng xin g ử i l ờ  i c ả m ơ  n t ớ  i các th ầ y cô trong B ộ  môn Các h ệ  th ố ng thông tin, Khoa Công ngh ệ  thông tin đ ã giúp em có đượ  c môi th ự c nghi ệ m thu ậ n l ợ  i. Em c ũ ng xin g ử i t ớ  i các b ạ n trong nhóm Seminar “Khai phá d ữ  li ệ u và Tính toán song song” l ờ  i c ả m ơ  n chân thành vì nh ữ ng đ óng góp và nh ữ ng ki ế n th ứ c quý báu em đ ã ti ế  p thu đượ  c trong su ố t th ờ  i gian tham gia nghiên c ứ u khoa h ọ c. Cu ố i cùng, em xin c ả m ơ  n gia đ ình, b ạ n bè và t ậ  p th ể  l ớ   p K46CA, nh ữ ng ng ườ  i đ ã luôn ở   bên khích l ệ  và độ ng viên em r  ấ t nhi ề u. Hà N ộ i, tháng 6 n ă m 2005 Sinh viên  Nguy ễ n Th ị  Thùy Linh    - iii - M Ụ C L Ụ C TÓM T Ắ T N Ộ I DUNG..................................................................................................i   L Ờ  I C Ả M Ơ  N...............................................................................................................ii   M Ụ C L Ụ C....................................................................................................................iii   DANH M Ụ C BI Ể U ĐỒ  HÌNH V Ẽ ...............................................................................v   DANH M Ụ C THU Ậ T NG Ữ  ......................................................................................vii   ĐẶ T V Ấ N ĐỀ .................................................................................................................1   Ch ươ  ng 1. T Ổ NG QUAN V Ề  PHÂN L Ớ  P D Ữ   LI Ệ U D Ự  A TRÊN CÂY QUY Ế T ĐỊ NH...............................................................................................................................3   1.1. T ổ ng quan v ề  phân l ớ   p d ữ  li ệ u trong data mining................................................3  1.1.1. Phân l ớ   p d ữ  li ệ u........................................................................................................3 1.1.2. Các v ấ n đề  liên quan đế n phân l ớ   p d ữ  li ệ u...............................................................6 1.1.3. Các ph ươ  ng pháp đ ánh giá độ  chính xác c ủ a mô hình phân l ớ   p..............................8 1.2. Cây quy ế t đị nh ứ ng d ụ ng trong phân l ớ   p d ữ  li ệ u.................................................9  1.2.1. Đị nh ngh  ĩ  a................................................................................................................9 1.2.2. Các v ấ n đề  trong khai phá d ữ  li ệ u s ử  d ụ ng cây quy ế t đị nh....................................10 1.2.3. Đ ánh giá cây quy ế t đị nh trong l  ĩ  nh v ự c khai phá d ữ  li ệ u.......................................11 1.2.4. Xây d ự ng cây quy ế t đị nh........................................................................................13 1.3. Thu ậ t toán xây d ự ng cây quy ế t đị nh...................................................................14  1.3.1. T ư  t ưở  ng chung......................................................................................................14 1.3.2. Tình hình nghiên c ứ u các thu ậ t toán hi ệ n nay........................................................15 1.3.3. Song song hóa thu ậ t toán phân l ớ   p d ự a trên cây quy ế t đị nh tu ầ n t ự ......................17 Ch ươ  ng 2. C4.5 VÀ SPRINT......................................................................................21   2.1. Gi ớ  i thi ệ u chung.................................................................................................21   2.2. Thu ậ t toán C4.5...................................................................................................21  2.2.1. C4.5 dùng Gain-entropy làm độ   đ o l ự a ch ọ n thu ộ c tính “t ố t nh ấ t”........................22 2.2.2. C4.5 có c ơ   ch ế  riêng trong x ử  lý nh ữ ng giá tr  ị  thi ế u..............................................25 2.2.3. Tránh “quá v ừ a” d ữ  li ệ u.........................................................................................26 2.2.4. Chuy ể n đổ i t ừ  cây quy ế t đị nh sang lu ậ t.................................................................26 2.2.5. C4.5 là m ộ t thu ậ t toán hi ệ u qu ả  cho nh ữ ng t ậ  p d ữ  li ệ u v ừ a và nh ỏ .......................27 2.3. Thu ậ t toán SPRINT............................................................................................28  2.3.1. C ấ u trúc d ữ  li ệ u trong SPRINT..............................................................................29 2.3.2. SPRINT s ử  d ụ ng Gini-index làm độ   đ o tìm đ i ể m phân chia t ậ  p d ữ  li ệ u “t ố t nh ấ t”..........................................................................................................................................31 2.3.3. Th ự c thi s ự  phân chia.............................................................................................34 2.3.4. SPRINT là thu ậ t toán hi ệ u qu ả  v ớ  i nh ữ ng t ậ  p d ữ  li ệ u quá l ớ  n so v ớ  i các thu ậ t toán   khác...................................................................................................................................35
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks