TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN ************* PHAN THỊ NGỌC TRINH THUẬT TOÁN ID3 VÀ CHƢƠNG TRÌNH MÔ PHỎNG CHUẨN ĐOÁN BỆNH CÚM H1N1 KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Khoa học máy tính HÀ NỘI, 2015 TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN ************* PHAN THỊ NGỌC TRINH THUẬT TOÁN ID3 VÀ CHƢƠNG TRÌNH MÔ PHỎNG CHUẨN ĐOÁN BỆNH CÚM H1N1 KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Khoa học máy tính Ngƣời hƣớng dẫn khoa học PGS. TS. Bùi Thế Hồng HÀ NỘI, 2015 LỜI CẢM ƠN Trong suốt trình học tập thực đề tài khóa luận, em nhận đƣợc giúp đỡ, tạo điều kiện tập thể lãnh đạo, thầy, cô giáo Trƣờng Đại học Sƣ phạm Hà Nội nói chung thầy, cô giáo Khoa Công nghệ thông tin nói riêng. Em xin bày tỏ lòng cảm ơn chân thành giúp đỡ đó. Em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Bùi Thế Hồng, ngƣời thầy trực tiếp hƣớng dẫn bảo cho em hoàn thành khóa luận này. Em xin gửi lời cảm ơn đến gia đình, bạn học chia sẻ, động viên khích lệ em chuyên môn nhƣ mặt sống để em hoàn thành tốt khóa luận. Do thời gian kinh nghiệm nghiên cứu khoa học chƣa nhiều nên khóa luận nhiều thiếu xót, mong nhận đƣợc đóng góp thầy, cô giáo bạn để khóa luận đƣợc hoàn thiện hơn. Hà Nội, ngày 10 tháng 05 năm 2015 Sinh viên Phan Thị Ngọc Trinh LỜI CAM ĐOAN Tên em là: Phan Thị Ngọc Trinh Sinh viên lớp: K37A - Tin học, khoa Công nghệ Thông tin, trƣờng Đại học Sƣ phạm Hà Nội 2. Em xin cam đoan: 1. Đề tài: “Thuật toán ID3 chƣơng trình mô chuẩn đoán bệnh cúm H1N1” nghiên cứu riêng em dƣới hƣớng dẫn PGS. TS. Bùi Thế Hồng. 2. Kết nghiên cứu em không trùng với kết tác giả khác. 3. Các kết nêu khóa luận nghiên cứu thực tiễn đảm bảo tính xác trung thực. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 10 tháng 05 năm 2015 Sinh viên thực (Ký ghi rõ họ tên) Phan Thị Ngọc Trinh MỤC LỤC MỞ ĐẦU CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 1.1. Quá trình phát tri thức 1.2. Khai phá liệu . 1.2.1. Tính cấp bách việc khai phá liệu . 1.2.2. Mục tiêu khai phá liệu . 1.2.3. Quá trình khai phá liệu . 1.2.4. Các dạng liệu khai phá 1.3. Ứng dụng khai phá liệu 1.3.1. Phân tích liệu tài (Financial Data Analysis) 1.3.2. Công nghiệp bán lẻ (Retail Industry) 10 1.3.3. Công nghiệp viễn thông (Telecommunication Industry) . 10 1.3.4. Phân tích liệu sinh học (Biological Data Analysis) . 11 1.3.5. Phát xâm nhập bất hợp pháp (Intrusion Detection) 11 1.4. Hàm Entropy 11 1.5. Hàm Gain . 12 1.6. Một số phƣơng pháp khai phá liệu . 13 1.6.1. Cây định luật . 13 1.6.2. Phương pháp suy diễn quy nạp . 13 1.6.3. Luật kết hợp . 14 1.6.4. Phân nhóm phân đoạn 14 1.6.5. Mạng neural . 14 1.6.6. Giải thuật di truyền 15 CHƢƠNG 2: KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT ĐỊNH . 16 2.1. Giới thiệu . 16 2.1.1. Kỹ thuật khai phá sử dụng định . 16 2.1.2. Ưu điểm 16 2.1.3. Cấu trúc định . 17 2.1.4. Điều kiện dừng định 18 2.2. Thuật toán 18 2.2.1. Thuật toán CLS 18 2.2.2. Thuật toán ID3 . 24 2.2.3. Thuật toán C4.5 34 2.3. Rút gọn định 42 2.4. Rút gọn luật từ định . 44 CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH MÔ PHỎNG 46 3.1. Phát biểu toán . 46 3.2. Giải toán . 47 3.2.1. Áp dụng thuật toán . 47 3.2.2. Hàm xây dựng định 47 3.2.3. Tính giá trị Gain cho thuộc tính 48 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN . 62 TÀI LIỆU THAM KHẢO 64 MỞ ĐẦU 1. Lý chọn đề tài Ngày nay, phát triển mạnh mẽ Công nghệ thông tin làm cho khả thu thập lƣu trữ thông tin hệ thống thông tin tăng nhanh, lƣợng liệu mà lƣu trữ trở nên nhiều, gây khó khăn cho việc lấy đƣợc thông tin hữu ích. Do vậy, cần có kỹ thuật công cụ để tự động chuyển đổi lƣợng liệu khổng lồ thành tri thức hữu ích. Với hàng loạt công trình nghiên cứu, giải pháp đƣợc thử nghiệm ứng dụng thành công vào đời sống chứng minh khai phá liệu lĩnh vực nghiên cứu có tảng lý thuyết vững chắc. Đã có nhiều nghiên cứu khai phá liệu nhà khoa học khai phá liệu lĩnh lực đƣợc nhiều ngƣời quan tâm. Một phƣơng pháp khai phá liệu có hiệu quả, đƣợc ứng dụng nhiều phƣơng pháp định. Vì khả ứng dụng thiết thực vào đời sống xã hội phƣơng pháp cao nên em chọn đề tài “Thuật toán ID3 chƣơng trình mô chuẩn đoán bệnh cúm H1N1” để làm đề tài khóa luận tốt nghiệp. 2. Mục đích nghiên cứu - Hiểu đƣợc tổng quan khai phá liệu phát tri thức. - Nghiên cứu vấn đề thuật toán xây dựng định ID3, cài đặt đánh giá thuật toán đó. Áp dụng mô hình định ID3 để chuẩn đoán bệnh cúm H1N1. 3. Đối tƣợng phạm vi nghiên cứu Nghiên cứu Khai phá liệu, thuật toán khai phá liệu xây dựng chƣơng trình minh họa thuật toán ID3 để chuẩn đoán bệnh cúm H1N1. 4. Nhiệm vụ nghiên cứu - Tìm hiểu khai phá liệu thuật toán phân lớp liệu. - Xây dựng chƣơng trình chuẩn đoán bệnh cúm H1N1 thuật toán ID3. Cài đặt thử nghiệm đánh giá kết quả. 5. Giả thuyết khoa học Tìm hiểu nghiên cứu số thuật toán phân lớp liệu giúp định dễ dàng việc lựa chọn có định đắn. Chƣơng trình đƣợc xây dựng dựa thuật toán ID3 ích lĩnh vực y tế mô chuẩn đoán bệnh cúm H1N1 mà áp dụng hiệu dạng liệu tƣơng tự thuộc nhiều lĩnh vực khác. 6. Phƣơng pháp nghiên cứu a. Phương pháp nghiên cứu lý luận Nghiên cứu qua việc đọc sách, báo, tài liệu web thông tin liên quan nhằm xây dựng sở lý thuyết biện pháp cần thiết để giải vấn đề cần thiết đề tài. b. Phương pháp chuyên gia Tham khảo ý kiến chuyên gia để thiết kế chƣơng trình phù hợp với yêu cầu thực tiễn. Nội dung xử lý nhanh đáp ứng nhu cầu ngày cao ngƣời sử dụng. Phân tích tổng hợp tài liệu khai phá liệu sử dụng thuật toán Cây định có thuật toán ID3, phân loại liệu, mô hình dự báo. c. Phương pháp thực nghiệm Thông qua quan sát thực tế, yêu cầu sở, lý luận đƣợc nghiên cứu kết đạt đƣợc qua phƣơng pháp trên. 7. Cấu trúc khóa luận Ngoài phần mở đầu, kết luận hƣớng phát triển, tài liệu tham khảo, khóa luận gồm chƣơng sau: - Chƣơng 1: Cơ sở lý thuyết - Chƣơng 2: Khai phá liệu sử dụng định - Chƣơng 3: Xây dựng chƣơng trình mô CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 1.1. Quá trình phát tri thức Khám phá tri thức lĩnh vực nghiên cứu mở thời kỳ việc tìm thông tin hữu ích. Nhiệm vụ lĩnh vực khám phá tri thức sở liệu. Khám phá liệu sở liệu hệ thống phân tích tự động mà trình tƣơng tác thƣờng xuyên ngƣời với sở liệu đƣợc trợ giúp nhiều phƣơng pháp công cụ tin học. Trong thời đại ngày nay, kinh tế xã hội phát triển liền với bùng nổ công nghệ thông tin cạnh tranh nhiều lĩnh vực ngày cao. Yếu tố định thành công lĩnh vực gắn liền với việc nắm bắt, thống kê khai thác thông tin hiệu quả. Dữ liệu ngày lớn nên việc tìm thông tin tiềm ẩn chúng ngày khó khăn phát tri thức trình quan trọng. Hình thành Định nghĩa toán Thu thập Tiền xử lý liệu Khai phá liệu Rút gọn tri thức Phân tích kiểm định kết Sử dụng tri thức phát đƣợc Hình 1.1. Quá trình phát tri thức Quá trình phát tri thức bao gồm bƣớc sau: Bƣớc 1: Hình thành định nghĩa toán Đây bƣớc tìm hiểu lĩnh vực ứng dụng hình thành toán, định cần rút dạng tri thức nhƣ nào, đồng thời lựa chọn phƣơng pháp khai phá liệu thích hợp với mục đích ứng dụng chất liệu. Bƣớc 2: Thu thập tiền xử lý liệu Thu thập tiền xử lý liệu thu thập xử lý thô đƣợc gọi tiền xử lý liệu nhằm loại bỏ nhiễu, xử lý việc thiếu liệu, biến đổi liệu rút gọn liệu cần thiết. Bƣớc thƣờng chiếm nhiều thời gian trình phát tri thức. Bƣớc 3: Khai phá liệu rút tri thức Đây bƣớc khai phá liệu hay nói cách khác trích đƣợc mẫu mô hình ẩn dƣới liệu. Đây bƣớc quan trọng tiến trình phát tri thức. Bƣớc 4: Phân tích kiểm định kết Bƣớc thứ hiểu tri thức tìm đƣợc, đặc biệt làm sáng tỏ mô tả dự đoán. Trong bƣớc này, kết tìm đƣợc biến đổi sang dạng phù hợp với lĩnh vực ứng dụng dễ hiểu cho ngƣời dùng. Bƣớc 5: Sử dụng tri thức phát đƣợc Các tri thức khám phá đƣợc đƣợc củng cố, kết hợp lại thành hệ thống, đồng thời giải xung đột tiềm tri thức đó. Các mô hình rút đƣợc đƣa vào hệ thống thông tin thực tế dƣới dạng môđun hỗ trợ việc đƣa định. Các giai đoạn trình phát tri thức có mối quan hệ chặt chẽ với bối cảnh chung hệ thống. Các kỹ thuật sử dụng giai đoạn trƣớc ảnh hƣởng tới hiệu giải thuật đƣợc sử dụng giai đoạn tiếp theo. Các bƣớc trình phát tri thức đƣợc lặp lặp lại số lần, kết thu đƣợc đƣợc lấy trung bình tất lần thực hiện. ứ đ , - ( (, ứ đ ) -) Bảng 3.2. Bảng giá trị Gain cho thuộc tính Đ u Thuộc tính đầu Số lƣợng [Yes;No] Entropy(Yes, No) ( Đ Nhức đầu ,5 Bình thƣờng ,4 0.99 ) ( ) ( * - Với thuộc tính ) ứ đ ( ứ đ ) }. Khi đó: [2 ] có mẫu giá trị “Yes” mẫu giá trị “No” có mẫu “Yes” mẫu “No” [3 ] có mẫu “Yes” mẫu “No” , - ( ) ,4 - (, -) Vậy bảng thu đƣợc là: Bảng 3.3. Bảng giá trị Gain thuộc tính M i Thuộc tính mũi Số lƣợng [Yes: No] Entropy(Yes, No) ( ( ) Hắt [2 ] 0.918 Xổ mũi nặng ,4 0.920 Xổ mũi nhẹ [3 ] 0.971 ) ( ( ) ( ) 49 ) * ọ - Xét thuộc tính ươ + óđ Tƣơng tự nhƣ cách tính trình bày bảng thu đƣợc có dạng sau: Bảng 3.4. Bảng giá trị Gain thuộc tính C họng Ho thƣờng [2 ] 0.971 Thuộc tính Cổ họng Số lƣợng [Yes: No] Entropy(Yes, No) ( Ho đờm ,5 Ho khan [2 ] ) ( ) ( ( ( ) óđ ) )= - Xét thuộc tính: * ể ứ â ỉ ịđ đ + Bảng 3.5. Bảng giá trị Gain thuộc tính Cơ thể Thuộc tính Cơ thể Số lƣợng [Yes: No] Entropy(Yes, No) ( ể) ( ) Vậy Chỉ bị đau vùng đầu ,5 0.87 Nhức mỏi toàn thân ,4 0.985 ( ứ ( â ) ( ỉ ịđ đ ) ( Đ ) ) ( ọ ) ( ọ )có giá trị lớn nhất. Vậy thuộc tính cổ họng thuộc ( tính để khai triển cây. Cây có dạng sau: 50 ể) Cổ họng , - Ho đờm Ho thƣờng ? Ho khan ? ? , , - , - - Hình 3.1. Khai triển định theo thuộc tính C họng - Xét nhánh Cổ họng = Ho đờm. Các mẫu thuộc lớp “Yes” suy nút với nhãn nút “Yes”. Cây thu đƣợc có dạng sau: Cổ họng , Ho đờm Ho thƣờng ? , - Ho khan ? Yes , - , - - Hình 3.2.Khai triển định theo thuộc tính C họng = Ho đ m Xét nhánh bên trái cây, Cổ họng = Ho thƣờng, mẫu nhánh không thuộc lớp nên phải tính giá trị Gain thuộc tính ứng viên lại. Khi đó: ( (, ) -) Tính Gain cho thuộc tính ứng viên lại để chọn thuộc tính mở rộng tiếp theo. Tính Entropy cho thuộc tính {Đầu, Mũi, Cơ thể}. 51 Tập liệu ứng với Cổ họng = Ho thƣờng nhƣ sau: Bảng 3.6. Bảng tập liệu ứng với C họng = Ho thư ng Đầu Nhức đầu Bình thƣờng Bình thƣờng Bình thƣờng Nhức đầu Mũi Hắt Xổ mũi nặng Xổ mũi nhẹ Xổ mũi nặng Xổ mũi nặng * - Với thuộc tính Đ Cơ thể Nhức mỏi toàn thân Nhức mỏi toàn thân Nhức mỏi toàn thân Nhức mỏi toàn thân Chỉ bị đau vùng đầu ứ đ Result Yes No No No Yes +: ứ đ Bảng 3.7. Thuộc tính Đ u ứng với C họng = Ho đ m Thuộc tính đầu Số lƣợng [Yes;No] Entropy(Yes, No) ( ,Đ ( Nhức đầu [2 ] ) ( ) Bình thƣờng [ ] ) ứ đ ( ứ đ ) Vậy bảng thu đƣợc nhƣ sau: Bảng 3.8. Thuộc tính M i ứng với C họng = Ho đ m Thuộc tính mũi Số lƣợng [Yes: No] Entropy(Yes, No) ( ( Hắt [1 ] Xổ mũi nặng [1 ] 0.918 Xổ mũi nhẹ [ ] ) ( ) ( ) ( ) )= - Xét thuộc tính ể * ứ â ỉ ịđ 52 đ +. Bảng 3.9. Thuộc tính Cơ thể ứng với C họng = Ho đ m Thuộc tính Cơ thể Số lƣợng [Yes: No] Entropy(Yes, No) Nhức mỏi toàn thân [1 ] 0.811 ( Chỉ bị đau vùng đầu [1 ] ) ( ( Vậy ( ) ) ( ) )= ( ,Đ ( ) 0.971 ) ( 0.421 ể) = 0.321 Thuộc tính “Đầu” có Gain lớn nhất. Vậy thuộc tính “Đầu” thuộc tính đƣợc dùng để triển khai cây. Với nhánh: Đ ứ đ , mẫu thuộc lớp "Yes" => Đây nút nhãn nút " Yes ". Đ ứ đ , mẫu thuộc lớp "No" => Đây nút nhãn nút "No". Cây có dạng: 53 Cổ họng , Ho đờm Ho thƣờng Đầu Ho khan ? Yes , , - - , Bình thƣờng Nhức đầu No Yes , - - , - Hình 3.3. Khai triển định theo thuộc tính “Đ u” Xét nhánh bên trái cây, Cổ họng = Ho khan, mẫu nhánh không thuộc lớp nên phải tính giá trị Gain thuộc tính ứng viên lại. Khi đƣợc tính nhƣ sau: , - ( ) (, -) Tính Gian cho thuộc tính ứng viên lại để chọn thuộc tính mở rộng tiếp theo. Tính Entropy cho thuộc tĩnh * Tập liệu ứng với ọ ể+. có bảng sau: Bảng 3.10. Bảng tập liệu ứng với C họng = Ho khan Mũi Hắt Xổ mũi nặng Xổ mũi nhẹ Xổ mũi nhẹ Cở thể Chỉ bị đau vùng đầu Chỉ bị đau vùng đầu Nhức mỏi toàn thân Chỉ bị đau vùng đầu 54 Result No Yes Yes No - * - Xét thuộc tính + Khi đóbảng thu đƣợc là: Bảng 3.11. Thuộc tính M i với C họng = Ho khan Thuộc tính mũi Số lƣợng [Yes: No] Entropy(Yes, No) ( ( Hắt [ ] Xổ mũi nặng [1 ] Xổ mũi nhẹ [1 ] ) ) ( ( ) ( ) )= - Xét thuộc tính ể * ứ â ỉ ịđ +. đ Bảng 3.12. Thuộc tính Cơ thể với C họng = Ho khan Thuộc tính Cơ thể Số lƣợng [Yes: No] Entropy(Yes, No) ( ể) ( ) ( Vậy: Chỉ bị đau vùng đầu [1 ] 0.918 Nhức mỏi toàn thân [1 ] ( ( ỉ ịđ ) ( đ ứ â ) ) 0.50 ể) = 0.31 Thuộc tính Mũi có Gain (Độ thông tin) lớn nhất. Vậy thuộc tính Mũi thuộc tính dùng để mở rộng cây. Cây thu đƣợc có dạng sau: 55 Cổ họng , Ho đờm Ho thƣờng Đầu Ho khan Mũi Yes , , - - , Bình thƣờng Nhức đầu Xổ mũi nặng No Yes , - - Xổ mũi nhẹ - , Nhức đầu ? Yes , - , - No - , Hình 3.4. Khai triển định theo thuộc tính “M i” - Xét nhánh Các mẫu nhánh không thuộc lớp nên chọn thuộc tính ứng viên “Cơ thể” lại để triển khai cây. - Xét thuộc tính: ể ể * ứ ứ â ỉ ịđ đ +. â có mẫu thuộc lớp Yes suy nút với nhãn nút Yes. ể ỉ ịđ đ có mẫu thuộc lớp No suy nút có nhãn nút No. Kết chƣơng trình cho nhƣ sau: 56 - Cổ họng , Ho đờm Ho thƣờng Đầu , Nhức đầu Ho khan Mũi Yes , - - , Bình thƣờng Xổ mũi nặng No Yes , - - , , Xổ mũi nhẹ Nhức đầu Cơ thể Yes - - - - , , Nhức mỏi toàn thân No Chỉ bị đau vùng đầu Yes , - Yes - , Hình 3.5. Cây định sử dụng thuật toán ID3 Từ định trên, luật đƣợc đƣa nhƣ sau: IF (Cổ họng = Ho đờm) THEN Bị cúm H1N1 ELSE IF (Cổ họng = Ho thƣờng) and (Đầu = Nhức đầu) THEN Bị cúm H1N1 ELSE IF (Cổ họng = Ho thƣờng) and (Đầu = Bình thƣờng) THEN Không bị cúm H1N1 ELSE IF (Cổ họng = Ho Khan) and (Mũi = Hắt hơi) THEN Không bị cúm H1N1 ELSE IF (Cổ họng = Ho Khan) and (Mũi = Xổ mũi nặng ) THEN Bị cúm H1N1 57 - ELSE IF (Cổ họng =Ho Khan) and (Mũi =Xổ mũi nhẹ ) and (Cơ thể =Chỉ bị đau vùng đầu) THEN Không bị cúm H1N1 ELSE Bị cúm H1N1. 3.3. Thiết kế chƣơng trình Sau số Form giao diện chƣơng trình. Hình 3.1. Form giao diện load chương trình Hình 3.2. Form giao diện 58 Hình 3.3. Form giao diện giới thiệu hướng dẫn Hình 3.4.Form giao diện trước chạy chương trình 59 Hình 3.5. Form giao diệnload liệu Hình 3.6.Form giao diện sau load liệu 60 Hình 3.7.Form giao diện xây dựng định 61 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN Kết luận Khóa luận nghiên cứu Khai phá liệu, sử dụng định, thuật toán ID3 mô chƣơng trình chuẩn đoán cúm H1N1. Cụ thể khóa luận chứng minh đƣợc cần thiết việc khai phá liệu nhƣ tính khoa học tính ứng dụng cao công cụ phân loại liệu. Từ áp dụng kỹ xử lý liệu vào việc mô chuẩn đoán bệnh cúm H1N1 thuật toán ID3 dựa sở liệu thu thập trƣớc đó. Khóa luận làm rõ đƣợc vấn đề sau: + Tìm hiểu điều khai phá liệu. + Trình bày thuật toán phân lớp liệu. + Xây dựng chƣơng trình mô ứng dụng thuật toán ID3 việc chuẩn đoán cúm H1N1. Hạn chế + Cơ sở liệu đƣợc sử dụng khóa luận dừng lại mức đại diện thực tế lại đa dạng. + Khóa luận sâu tìm hiểu thuật toán cụ thể mà chƣa minh họa thuật toán lại. Hƣớng phát triển Con ngƣời quan tâm tìm hiểu thuật toán ứng dụng chúng vào nhiều lĩnh vực thực tế có chung mong muốn áp dụng thành tựu khoa học vào sống. Vì việc phát triển ứng dụng giữ vai trò quan trọng. - Về lý thuyết: Tiếp tục nghiên cứu phát triển thuật toán định. Mỗi thuật toán phƣơng pháp khai phá liệu có ƣu điểm khuyết điểm riêng nên việc nghiên cứu giải pháp kết hợp phƣơng pháp khai phá liệu nhằm đạt đƣợc kết tốt giữ vai trò quan trọng. 62 - Về phát triển ứng dụng: Kết nghiên cứu khóa luận sử dụng để cài đặt ứng dụng giải toán thực tiễn. Do điều kiện hạn hẹp thời gian, tài liệu tham khảo nên khóa luận chƣa đề cập tới sở liệu khác bƣớc đầu lĩnh vực nghiên cứu không tránh khỏi sai xót. Vì mong nhận đƣợc quan tâm góp ý quý thầy, cô giáo bạn để khóa luận đƣợc hoàn thiện nữa. 63 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt , -. Nguyễn Thanh Thủy, Khai phá liệu - Kỹ thuật ứng dụng. , - GS.TS Đỗ Phúc, Bài giảng khai phá liệu, Đại học Quốc gia TP Hồ Chí Minh. Tài liệu tiếng Anh [5]. Han J. and Kamber (2000), Data mining Concepts and Techniques, MorganKanufmann. [6]. Murthy, S.K (1998), “Automatic construction of decision trees from data: Amulti – disciplication survey”. Data mining and Knowledge. [7]. John Darlington, Moustafa M. Ghanem, Yike Guo, Hing Wing To. Performance Model for Co-odinating Parallel Data Classification [8]. John Shafer, Rakesh Agrawal, Manish Mehta. SPRINT- A Scalable Paralllel Classifier for Data mining. In Predeeings of the 22nd International Conference on Very Large Database, India, 1996. [9]. J. R. Quinlan. Improve Used of Continuous Attribute in C4.5. In Joural of Artficial Intelligence Research (1996) 77-90. [10]. Manish Mehta, Rakesh Agrawal, Jorma Rissanen. SLIQ: A Fast Scalable Classifier for Data mining.IBM Amaden Research Center, 1996. [11]. Mohammed J. Zaki, Ching-Tien Ho, Rekesh Agrawal. Parallel Classification for Data Mining on Shared-Memory Multiprocessors.IVM Almaden Research Center, San Jose, CA 95120. [12]. Rajeev Rastogi, Kyuseok Shim (Bell Laboratories). PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning, 1998. 64 [...]... nhỏ nhất và độ chính xác của việc phân lớp là tốt nhất Vấn đề này sẽ đƣợc giải quyết trong thuật toán ID3 2.2.2 Thuật toán ID3 Thuật toán ID3 biểu diễn các khái niệm ở dạng cây quyết định Biểu diễn này cho phép xác định phân loại của đối tƣợng bằng cách kiểm tra giá trị của nó trên một số thuộc tính nào đó Nhiệm vụ của thuật toán ID3 là học cây quyết định từ một tập dữ liệu rèn luyện Đầu vào: Một tập... 1.6.6 Giải thuật di truyền Là quá trình mô phỏng tiến hóa trong tự nhiên Ý tƣởng chính của giải thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hóa trong sinh học Giải thuật di truyền là một giải thuật tối ƣu hóa, nó đƣợc sử dụng rất rộng rãi trong việc tối ƣu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng neural Sự liên hệ của nó với các giải thuật khai phá... trong khai phá dữ liệu Ở trong giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu Thuật toán thƣờng dùng để trích mẫu dữ liệu là thuật toán phân loại dữ liệu, kết hợp dữ liệu, thuật toán mô hình hoá dữ liệu tuần tự… - Giai đoạn 6: Đánh giá kết quả mẫu (Evaluation of result ) Đây là giai đoạn cuối cùng trong quá trình khai phá dữ liệu, ở giai đoạn này các mẫu dữ... nền tảng toán học vững vàng, khả năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ƣơng của con ngƣời Kết quả mà mạng neural học đƣợc có khả năng tạo ra các mô hình dự báo, dự đoán với độ chính xác và độ tin cậy cao Nó có khả năng phát hiện ra các xu hƣớng phức tạp mà kỹ thuật thông thƣờng khác khó có thể phát hiện ra đƣợc Tuy nhiên phƣơng pháp mạng neural rất phức tạp và quá trình tiến... chọn không thích hợp, cây quyết định thu đƣợc có thể rất phức tạp Để làm đƣợc việc này thuật toán ID3 có sử dụng tới hai hàm Entropy và Entropy Gains (hay còn gọi là Information Gain viết tắt là Gain) Chọn thuộc tính cho bước tiếp theo trong thuật toán ID3 Để chọn đƣợc thuộc tính cho bƣớc tiếp theo trong thuật toán ID3, cần tính giá trị Gain của các thuộc tính Thuộc tính nào có giá trị Gain lớn nhất... cơ sở dữ liệu và Q là mệnh đề dự đoán Cây quyết định là phƣơng pháp dùng trong các bài toán phân loại dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính Cây quyết định và luật có ƣu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu đối với ngƣời sử dụng Tuy nhiên giới hạn của nó là miêu tả cây và luật chỉ có thể biểu diễn đƣợc một số dạng chức năng và vì vậy giới... 2.1.1 Kỹ thuật khai phá sử dụng cây quyết định Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân lớp và dự báo Các đối tƣợng dữ liệu đƣợc phân thành các lớp Các giá trị của đối tƣợng dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo Tri thức đƣợc rút ra trong kỹ thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản, trực quan, dễ hiểu đối với ngƣời sử dụng Cây quyết định là một mô tả... 2: Rút gọn cây: Phát hiện và bỏ đi các nhánh chứa các điểm dị thƣờng và nhiễu trong dữ liệu 17 2.1.4 Điều kiện dừng của cây quyết định - Tất cả các mẫu rơi vào cùng một nút thuộc về cùng một lớp (nút lá) - Không còn thuộc tính nào có thể dùng để phân chia mẫu - Không còn lại mẫu nào tại nút 2.2 Thuật toán 2.2.1 Thuật toán CLS Xây dựng cây quyết định lần đầu tiên đƣợc Hoveland và Hunt giới thiệu trong... chóng và mạnh mẽ của phần cứng thì vấn đề này cũng đƣợc khắc phục 1.6.4 Phân nhóm và phân đoạn Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó Mối quan hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm Một số kỹ thuật. .. tính cho bƣớc tiếp theo trong thuật toán ID3: 12 ( ) tƣơng Để chọn đƣợc thuộc tính cho bƣớc tiếp theo trong thuật toán ID3, cần phải tính giá trị Gain của các thuộc tính Thuộc tính nào có giá trị Gain lớn nhất đƣợc xem là thuộc tính tốt nhất để lựa chọn cho việc triển khai cây 1.6 Một số phƣơng pháp khai phá dữ liệu 1.6.1 Cây quyết định và luật Cây quyết định là phƣơng pháp mô tả tri thức dạng đơn giản . và phát hiện tri thức. - Nghiên cứu các vấn đề cơ bản của thuật toán xây dựng cây quyết định ID3, cài đặt và đánh giá thuật toán đó. Áp dụng mô hình cây quyết định ID3 để chuẩn đoán bệnh cúm. Vì khả năng ứng dụng thiết thực vào đời sống xã hội của phƣơng pháp này rất cao nên em đã chọn đề tài Thuật toán ID3 và chƣơng trình mô phỏng chuẩn đoán bệnh cúm H1N1” để làm đề tài khóa luận. 3. Đối tƣợng và phạm vi nghiên cứu Nghiên cứu về Khai phá dữ liệu, các thuật toán khai phá dữ liệu cơ bản và xây dựng chƣơng trình minh họa thuật toán ID3 để chuẩn đoán bệnh cúm H1N1.