Chương trình mô phỏng thuật toán id3 cây quyết định

TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

ĐỀ TÀI MÔN HỌC

THUẬT TOÁN NÂNG CAO

ĐỀTÀI:

CÂY QUYẾT ĐỊNH VÀ THUẬT TOÁNCÂY QUYẾT ĐỊNH VÀ THUẬT TOÁN XÂY DỰNG CÂY QUYẾT ĐỊNHXÂY DỰNG CÂY QUYẾT ĐỊNH

Giáo viên hướng dẫn : TS. NGUYỄN QUANG TẤNNhóm thực hiện : HUỲNH PHƯỚC THÁIHUỲNH CÔNG KHANHLớp :CH10CNT2

THÀNH PHỐ HỒ CHÍ MINHTháng 11 năm 2010

Thuật toán nâng cao – Cây quyết định và các thuật toán

Lời cảm ơn

Báo cáo đề tài này được hoàn thành, trước hết chúng em xin chânthành cảm ơn thầy, TS. Nguyễn Quang Tấn, đã giúp đỡ nhóm chúng em rất nhiều về việc chuẩn bị các kiến thức tổng quan về môn học Thuật toán nâng cao, đặc biệt là những kiến thức cơ bản về Cây quyết định và các thuật toántrên cây quyết định; đồng thời chúng em cũng gửi lời cám ơn đến các bạncùng khóa học, vì đã cùng trao đổi, chia sẻ thông tin và các kiến thức liênquan để nghiên cứu và hoàn thành tốt tiểu luận môn học của mình. Đối với chúng em đây là một đề tài mới, do hạn chế về trình độ hiểubiết của bản thân, cũng như các tài liệu tham khảo và thời gian có hạn, chonên dù cố gắng làm việc, nghiên cứu tích cực nhưng báo cáo của chúng emcũng không thể tránh được những sai sót và còn có những vấn đề chưa đượchoàn thiện. Kính mong được sự góp ý và chỉ dẫn tận tình của thầy, cùng các bạn để đề tài của chúng em được hoàn thiện hơn.Thành phố Hồ Chí Minh, ngày 09 tháng 11 năm 2010 Nhóm học viên thực hiện

Huỳnh Phước Thái Huỳnh Công Khanh

1

Thuật toán nâng cao – Cây quyết định và các thuật toán

MỤC LỤC

CÂY QUYẾT ĐỊNH. Giáo viên hướng dẫn: TS. Nguyễn Nhật Quang Sinh viên thực hiện : Vũ Thành Trung Nguyễn Hồng Phúc Lưu Văn Đảng Nguyễn Văn Hưng Lớp : TTM K52. Nội dung. Mô hình làm việc Thuật toán ID3 Cơ sở dữ liệu và DataSet Mô phỏng chương trình

Download Presentation

CÂY QUYẾT ĐỊNH

An Image/Link below is provided (as is) to download presentationDownload Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author. Content is provided to you AS IS for your information and personal use only. Download presentation by click this link. While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server. During download, if you can't get a presentation, the file might be deleted by the publisher.

Presentation Transcript

• CÂY QUYẾT ĐỊNH Giáo viên hướng dẫn: TS. Nguyễn Nhật Quang Sinh viên thực hiện : Vũ Thành Trung Nguyễn Hồng Phúc Lưu Văn Đảng Nguyễn Văn Hưng Lớp : TTM K52
• Nội dung • Mô hình làm việc • Thuật toán ID3 • Cơ sở dữ liệu và DataSet • Mô phỏng chương trình • Những khó khăn và đề xuất cải tiến
• Quan hệ khách hàng • So sánh thông tin khách hàng – thông tin khóa học/lớp học • Chọn ra các đối tượng khách hàng phù hợp • Gửi thư tư vấn, hỗ trợ thông tin khách hàng => Đây là công việc rất vất vả
• Mô hình làm việc của chương trình
• Thuật toán ID3 • Entropy: định mức giá trị cho những nguồn thông tin không chắc chắn • Info – Gain: độ lợi thông tin Gain (X,T) = H(T) – H(X,T)
• Ưu điểm của ID3 • Sử dụng thuật tìm kiếm leo đồi (hill - climbing) dựa trên giá trị Gain để tìm kiếm các thuộc tính trong toàn bộ Cây quyết định • Đầu ra (Output) chỉ là một giả thuyết đơn (1 kết quả duy nhất) • Không bao giờ gặp hiện tượng quay lui – tính hội tụ cao • ...
• DataSet • Với Dataset trên, ta có các thuộc tính và miền giá trị : • - CourseName : {MCSA, CCNP, MCDBA, SCJP…} • - CourseCertificated : {CCNP, MCSA, MCDBA} • …tương tự với các thuộc tính khác • Ta sẽ dựa vào ý tưởng của thuật toán ID3, tính toán các giá trị Entropy H(T), các giá trị H(X,T) và tính giá trị Gain. Từ đó, với giá trị Gain nào lớn nhất thì đó là thuộc tính có độ lợi thông tin lớn nhất thì sẽ được chọn làm nút để xây dựng cây quyết định. Thao tác trên được lặp đi lặp lại đến khi kết thúc (hết thuộc tính để duyệt hoặc tìm ra được lá tối ưu)
• Cơ sở dữ liệu
• Mô phỏng chương trình • Main Form và tập dữ liệu Dataset :
• Mô phỏng chương trình Form khi ấn vào nút tạo cây :
• Mô phỏng chương trình Form khi ấn vào nút demo
• Điểm yếu của ID3 • Chỉ thích hợp với mô hình có lượng dữ liệu ít, rời rạc • Không thích ứng được với những tập dữ liệu tạp (dễ phát sinh lỗi) • Không hiệu quả khi xuất hiện những dữ liệu không mong muốn • Cây quyết định khi dựng ra vẫn còn có thể lớn, rườm rà, chưa được tối ưu ở mức tối đa có thể
• Cải tiến thuật toán – C4.5 - Có khả năng phòng tránh hiện tượng Overfiting : là hiện tượng lượng dữ liệu không cần thiết - Thích hợp được với các dữ liệu liên tục • Giải quyết bài toán với trường hợp mà các thuộc tính có dữ liệu trống • Cắt tỉa cây: Pre-pruning, Post-pruning • Có thể chuyển đổi từ Cây quyết định thành các Luật
• Những khó khăn gặp phải • Khó khăn trong việc tìm tài liệu cho thuật toán C4.5 • Khó khăn trong việc tìm hiểu về tính chất của khách hàng, thông tin khóa học/lớp học trong thực tiễn ở các trung tâm đào tạo. • Khó khăn trong việc nhập dữ liệu để kiểm nghiệm vì bài toán đòi hỏi một lượng dữ liệu tương đối lớn, nếu ít dữ liệu quá thì mức độ đánh giá thuật toán sẽ không khách quan.

Kết luận • Hiệu năng và chi phí cho công việc là bài toán khó • Những ứng dụng của khoa học kĩ thuật đã giúp ích rất nhiều cho con người