Đề tài Báo cáo: Khai phá dữ liệu bằng cây quyết định và ứng dụng

Nội dung text: Đề tài Báo cáo: Khai phá dữ liệu bằng cây quyết định và ứng dụng

1. TRƢỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN  BÁO CÁO THỰC TẬP TỐT NGHIỆP ĐỀ TÀI: KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG Giảng viên hƣớng dẫn: Ths. Trần Hùng Cƣờng Sinh viên thực hiện: Nguyễn Bá Nguyện Lớp: Khoa học máy tính 3 Khóa: 4 Hà Nội, Tháng 3 năm 2013
2. LỜI MỞ ĐẦU Trong thời đại ngày nay, yếu tố quyết định thành công trong mọi lĩnh vực luôn gắn liền với việc nắm bắt, thống kê và khai thác thông tin hiệu quả. Dữ liệu ngày càng lớn nên việc tìm ra những thông tin tiềm ẩn trong chúng càng khó khăn hơn. Khai phá tri thức là một lĩnh vực nghiên cứu mới, mở ra một thời kỳ trong việc tìm ra thông tin hữu ích. Nhiệm vụ cơ bản của lĩnh vực này là khai phá tri thức trong cơ sở dữ liệu, khai phá dữ liệu trong cơ sở dữ liệu không phải là một hệ thống phân tích tự động mà là một quá trình tƣơng tác thƣờng xuyên giữa con ngƣời với cơ sở dữ liệu đƣợc sự trợ giúp của nhiều phƣơng pháp và công cụ tin học. Em xin bày tỏ sự biết ơn sâu sắc của mình tới Ths Trần Hùng Cƣờng ngƣời đã trực tiếp hƣớng dẫn, chỉ bảo tận tình, cung cấp tài liệu và phƣơng pháp nghiên cứu khoa học để em hoàn thành bản luận văn này. Em xin gửi lời cảm ơn tới các thầy cô giáo đã dạy dỗ trong quá trình em theo học tại Trƣờng. Trong suốt quá trình nghiên cứu, mặc dù đã hết sức cố gắng nhƣng chắc chắn bài luận không tránh khỏi những thiếu sót, rất mong quý thầy cô góp ý để luận văn đƣợc hoàn chỉnh hơn. Em xin chân thành cảm ơn! Ký tên Nguyện Nguyễn Bá Nguyện
3. TÓM TẮT NỘI DUNG Nội dung luận văn em xin trình bày bao gồm ba chƣơng: Chƣơng một: giới thiệu chung về công nghệ khai phá trí thức, các khái niệm cơ bản, ý nghĩa và tầm quan trọng của việc khai phá tri thức. Chƣơng hai: trình bày các phƣơng pháp khai phá dữ liệu bằng cây quyết định, khái niệm cơ bản về cây quyết định, các thuật toán xây dựng cây quyết định: CLS, ID3, C4.5, rút gọn các luật quyết định và đánh giá các thuật toán xây dựng cây quyết định. Chƣơng ba: cài đặt chƣơng trình hỗ trợ ra quyết đinh bằng cây quyết đinh dựa trên thuật toán C4.5.
4. MỤC LỤC LỜI MỞ ĐẦU 2 TÓM TẮT NỘI DUNG 3 MỤC LỤC 4 DANH SÁCH HÌNH VẼ 6 PHẦN MỞ ĐẦU 7 CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC 8 1.1 Phát hiện tri thức và khai phá dữ liệu 8 1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu 8 1.2.1. Hình thành và định nghĩa bài toán. 9 1.2.2. Thu thập và xử lý dữ liệu. 9 1.2.3. Khai thác dữ liệu và rút ra tri thức 10 1.2.4. Phân tích và đánh giá tri thức 10 1.2.5. Sử dụng tri thức phát hiện được 10 1.3. Khai phá dữ liệu 11 1.3.1. Các quan niệm về khai phá dữ liệu. 11 1.3.2. Quá trình khái phá dữ liệu. 12 1.3.3. Kiến trúc của hệ thống khai phá dữ liệu. 14 1.4. Các kỹ thuật khai phá dữ liệu 15 1.4.1. Phân lớp dữ liệu 15 1.4.2. Phân cụm dữ liệu 16 1.4.3. Cây quyết định 16 1.4.4. Luật kết hợp 16 1.4.5. Hồi quy 16 1.4.6. Mạng Nơron 16 1.4.7. Giải thuật di truyền 17
5. CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH 18 2.1 Cây quyết định 18 2.1.1 Giới thiệu 18 2.1.2 Các kiểu cây quyết định 18 2.1.3 Ưu điểm của cây quyết định 19 2.1.4 Phân lớp dữ liệu bằng cây quyết định 19 2.1.5 Xây dựng cây quyết định. 21 2.1.6 Rút ra luật từ cây quyết định 22 2.2 Các thuật toán xây dựng cây quyết định 22 2.2.1 Thuật toán CLS 22 2.2.2 Thuật toán ID3 23 2.2.3 Thuật toán C4.5 25 2.2.4 Cắt tỉa cây quyết định 31 2.2.5 Đánh giá và kết luận về các thuật toán xây dựng cây quyết định 33 CHƢƠNG 3: CẶT ĐẶT CHƢƠNG TRÌNH KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT ĐỊNH 36 3.1 Bài toán thực tế 36 3.2 Cài đặt thuật toán 36 3.3 Hình ảnh demo 40 KẾT LUẬN 44 TÀI LIỆU THAM KHẢO 45
6. DANH SÁCH HÌNH VẼ Hình 1. 1 Quá trình khai phá dữ liệu từ cơ sở dữ liệu 9 Hình 1. 2 Quá trình khai phá dữ liệu 12 Hình 1. 3 Kiến trúc của một hệ thống khai phá dữ liệu 14 Hình 2. 1: Cây quyết định phân lớp mức lương 18 Hình 2. 2 Xây dựng mô hình 20 Hình 2. 3 Sử dụng mô hình 21 Hình 3. 1 Giao diện khi mở chương trình 40 Hình 3. 2 Load dữ liệu và tạo cây quyết định 41 Hình 3. 3 Tiến hành cắt tỉa cây 42 Hình 3. 4 Hình ảnh của cây quyết định 42 Hình 3. 5 Rút ra luật từ cây quyết định 43 Hình 3. 6 Phân tích dữ liệu mới 43
7. PHẦN MỞ ĐẦU Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng dụng của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, thì lƣợng dữ liệu đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều lên. Ngƣời ta lƣu trữ những dữ liệu này vì cho rằng nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên theo thống kê thì chỉ có một lƣợng nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn đƣợc phân tích, số còn lại họ không biết sẽ phải làm gì và có thể làm gì với những dữ liệu này, nhƣng họ vẫn tiếp tục thu thập và lƣu trữ vì hy vọng những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một cách nhanh chóng để đƣa ra những quyết định kịp thời vào một lúc nào đó. Chính vì vậy, các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng đƣợc thực tế đã làm phát triển một khuynh hƣớng kỹ thuật mới đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang đƣợc nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau trên thế giới, tại Việt Nam kỹ thuật này còn tƣơng đối mới mẻ tuy nhiên cũng đang đƣợc nghiên cứu và bắt đầu đƣa vào một số ứng dụng thực tế. Vì vậy, hiện nay ở nƣớc ta vấn đề phát hiện tri thức và khai phá dữ liệu đang thu hút đƣợc sự quan tâm của nhiều ngƣời và nhiều công ty phát triển ứng dụng công nghệ thông tin. Trong phạm vi đề tài nghiên cứu khoa học này của em, em sẽ trình bày những nội dung sau: Chƣơng 1: Giới thiệu những kiến thức tổng quan về khám phá tri thức và khai phá dữ liệu. Chƣơng 2: Nghiên cứu kỹ thuật khai phá dữ liệu bằng cây quyết định. Chƣơng 3: Xây dựng ứng dụng demo cho kỹ thuật khai phá dữ liệu bằng cây quyết định. 7
8. CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ KHAI PHÁ TRI THỨC 1.1 Phát hiện tri thức và khai phá dữ liệu Phát hiện tri thức (Knowledge Discovery ) trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu đƣợc. Còn khai thác dữ liệu (data mining) là một ngữ tƣơng đối mới, nó ra đời vào khoảng những năm cuối của của thập kỷ 1980. Có rất nhiều định nghĩa khác nhau về khai phá dữ liệu. Giáo sƣ Tom Mitchell đã đƣa ra định nghĩa của khai phá dữ liệu nhƣ sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tƣơng lai.”. Với một cách tiếp cận ứng dụng hơn, tiến sĩ Fayyad đã phát biểu: ”Khai phá dữ liệu thƣờng đƣợc xem là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất những thông tin ẩn, trƣớc đây chƣa biết và có khả năng hữu ích, dƣới dạng các quy luật, ràng buộc, qui tắc trong cơ sở dữ liệu.”. Còn các nhà thống kê thì xem " khai phá dữ liệu nhƣ là một quá trình phân tích đƣợc thiết kế thăm dò một lƣợng cực lớn các dữ liệu nhằm phát hiện ra các mẫu thích hợp và/ hoặc các mối quan hệ mang tính hệ thống giữa các biến và sau đó sẽ hợp thức hoá các kết quả tìm đƣợc bằng cách áp dụng các mẫu đã phát hiện đƣợc cho tập con mới của dữ liệu". Nói tóm lại: khai phá dữ liệu là một bƣớc trong quy trình phát hiện tri thức gồm có các thụât toán khai thác dữ liệu chuyên dùng dƣới một số quy định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô hình trong dữ liệu. 1.2 Quá trình phát hiện tri thức từ cơ sở dữ liệu Quá trình phát hiện tri thức có thể chia thành các bƣớc nhƣ sau: 8
9. Hình thành và định nghĩa bài toán Thu thập và tiền xử lý dữ liệu KHAI PHÁ DỮ LIỆU (Triết xuất tri thức) Phân tích và đánh giá tri thức Sử dụng tri thức phát hiện đƣợc Hình 1. 1 Quá trình khai phá dữ liệu từ cơ sở dữ liệu 1.2.1. Hình thành và định nghĩa bài toán. Đây là bƣớc tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bƣớc này sẽ quyết định cho việc rút ra những tri thức hữu ích, đồng thời lựa chọn các phƣơng pháp khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ liệu. 1.2.2. Thu thập và xử lý dữ liệu. Trong bƣớc này dữ liệu đƣợc thu thập ở dạng thô (nguồn dữ liệu thu thập có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai đoạn này dữ liệu cũng đƣợc tiền xử lý để biến đổi và cải thiện chất lƣợng dữ liệu cho phù hợp với phƣơng pháp khai phá dữ liệu đƣợc chọn lựa trong bƣớc trên. Bƣớc này thƣờng chiếm nhiều thời gian nhất trong quá trình khám phá tri thức. Các giải thuật tiền xử lý dữ liệu bao gồm : 1. Xử lý dữ liệu bị mất/ thiếu: Các dạng dữ liệu bị thiếu sẽ đƣợc thay thế bởi các giá trị thích hợp 2. Khử sự trùng lắp: các đối tƣợng dữ liệu trùng lắp sẽ bị loại bỏ đi. Kỹ thuật này không đƣợc sử dụng cho các tác vụ có quan tâm đến phân bố dữ liệu. 9
10. 3. Giảm nhiễu: nhiễu và các đối tƣợng tách rời khỏi phân bố chung sẽ bị loại đi khỏi dữ liệu. 4. Chuẩn hoá: miền giá trị của dữ liệu sẽ đƣợc chuẩn hoá. 5. Rời rạc hoá: các dạng dữ liệu số sẽ đƣợc biến đổi ra các giá trị rời rạc. 6. Rút trích và xây dựng đặc trƣng mới từ các thuộc tính đã có. 7. Giảm chiều: các thuộc tính chứa ít thông tin sẽ đƣợc loại bỏ bớt. 1.2.3. Khai thác dữ liệu và rút ra tri thức Đây là bƣớc quan trọng nhất trong tiến trình khám phá tri thức. Kết quả của bƣớc này là trích ra đƣợc các mẫu và/hoặc các mô hình ẩn dƣới các dữ liệu. Một mô hình có thể là một biểu diễn cấu trúc tổng thể một thành phần của hệ thống hay cả hệ thống trong cơ sở dữ liệu, hay miêu tả cách dữ liệu đƣợc nảy sinh. Còn một mẫu là một cấu trúc cục bộ có liên quan đến vài biến và vài trƣờng hợp trong cơ sở dữ liệu. 1.2.4. Phân tích và đánh giá tri thức Bƣớc thứ tƣ là hiểu các tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán.Trong bƣớc này, kết quả tìm đƣợc sẽ đƣợc biến đổi sang dạng phù hợp với lĩnh vực ứng dụng và dễ hiểu hơn cho ngƣời dùng. 1.2.5. Sử dụng tri thức phát hiện được Trong bƣớc này, các tri thức khám phá đƣợc sẽ đƣợc củng cố, kết hợp lại thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức đó. Các mô hình rút ra đƣợc đƣa vào những hệ thống thông tin thực tế dƣới dạng các môdun hỗ trợ việc đƣa ra quyết định. Các giai đoạn của quá trình khám phá tri thức có mối quan hệ chặt chẽ với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật đƣợc sử dụng trong giai đoạn trƣớc có thể ảnh hƣởng đến hiệu quả của các giải thuật đƣợc sử dụng trong các giai đoạn tiếp theo. Các bƣớc của quá trình khám phá trithức có thể đƣợc lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực hiện. 10
11. 1.3. Khai phá dữ liệu 1.3.1. Các quan niệm về khai phá dữ liệu. Khai phá dữ liệu là tập hợp các thuật toán nhằm chiết xuất những thông tin có ích từ kho dữ liệu khổng lồ. Khai phá dữ liệu đƣợc định nghĩa nhƣ một quá trình phát hiện mẫu trong dữ liệu, quá trình này có thể là tự động hay bán tự động, song phần nhiều là bán tự động. Các mẫu đƣợc phát hiện thƣờng hữu ích theo định nghĩa:các mẫu mang lại cho ngƣời sử dụng một lợi thế nào đó, thƣờng là lợi ích về kinh tế. Khai phá dữ liệu giống nhƣ quá trình tìm ra và mô tả mẫu dữ liệu. Dữ liệu nhƣ là một tập hợp các vật hay sự kiện, còn đầu ra của quá trình khai phá dữ liệu thƣờng nhƣ là những dự báo của các vật hay các sự kiện mới. Khai phá dữ liệu đƣợc áp dụng trong các cơ sở dữ liệu quan hệ, giao dịch, cơ sở dữ liệu không gian, cũng nhƣ các kho dữ liệu phi cấu trúc, mà điển hình là World Wide Web. Khám phá tri thức là quá trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính chất: Đúng đắn, mới, khả ích và có thể hiểu đƣợc. Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức bao gồm các thuật toán khai phá dữ liệu chuyên dùng dƣới một số quy định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu và các mô hình trong dữ liệu. Nhƣ vậy, mục đích của khám phá tri thức và khai phá dữ liệu là tìm ra các mẫu hoặc mô hình đang tồn tại trong các cơ sở dữ liệu nhƣng vẫn còn bị khuất bởi số lƣợng dữ liệu khổng lồ. Nhiệm vụ của khai phá dữ liệu. 11
12. 1.3.2. Quá trình khái phá dữ liệu. Hình 1. 2 Quá trình khai phá dữ liệu 1.3.2.1. Gom dữ liệu (gatherin) Tập hợp dữ liệu là bƣớc đầu tiên trong khai phá dữ liệu. Bƣớc này lấy dữ liệu từ trong một cơ sở dữ liệu, một kho dữ liệu, thậm chí dữ liệu từ những nguồn cung ứng web. 1.3.2.2. Trích lọc dữ liệu (selection) Ở giai đoạn này dữ liệu đƣợc lựa chọn và phân chia theo một số tiêu chuẩn nào đó. 1.3.2.3. Làm sạch và tiền xử lý dữ liệu (cleansing prepocessing) Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thƣờng mắc phải trong khi gom dữ liệu là dữ liệu không đầy đủ hoặc không thống nhất, thiếu chặt chẽ. Vì vậy dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ Sinh viên có tuổi=200. Giai đoạn thứ ba này nhằm xử lý các dữ liệu nhƣ trên(dữ liệu vô nghĩa, dữ liệu không có khả năng kết nối). Những dữ liệu dạng này thƣờng đƣợc xem là thông tin dƣ thừa, không có giá trị. Bởi vậy đây là 12
13. một quá trình rất quan trọng. Nếu dữ liệu không đƣợc làm sạch- tiền xử lý - chuẩn bị trƣớc thì sẽ gây nên những kết quả sai lệch nghiêm trọng về sau. 1.3.2.4. Chuyển đổi dữ liệu (tranformation) Trong giai đoạn này, dữ liệu có thể đƣợc tổ chức và sử dụng lại. Mục đích của việc chuyển đổi dữ liệu là làm cho dữ liệu phù hợp hơn với mục đích khai phá dữ liệu. 1.3.2.5. Phát hiện và trích mẫu dữ liệu (pattern extraction and discovery) Đây là bƣớc tƣ duy 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ự. 1.3.2.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ữ liệu đƣợc chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải mẫu dữ liệu nào cũng hữu ích, đôi khi nó còn bị sai lệch. Vì vậy cần phải đƣa ra những tiêu chuẩn đánh giá độ ƣu tiên cho các mẫu dữ liệu để rút ra đƣợc những tri thức cần thiêt. 13
14. 1.3.3. Kiến trúc của hệ thống khai phá dữ liệu. User Interface Pattern Evaluation Knowledge Base Data mining Enggine Database or Data Warehouse Server Data cleaning, integration and selection Database Data World Wide Other Infor Warehouse Web Repositories Hình 1. 3 Kiến trúc của một hệ thống khai phá dữ liệu Database, data warehouse, World Wide Web, và information repositories - Thành phần này là các nguồn dữ liệu/thông tin sẽ đƣợc khai phá. - Trong những tình huống cụ thể, thành phần này là nguồn nhập (input) của các kỹ thuật tích hợp và làm sạch dữ liệu. Database hay data warehouse server - Thành phần chịu trách nhiệm chuẩn bị dữ liệu thích hợp cho các yêu cầu khai phá dữ liệu. Knowledge base - Thành phần chứa tri thức miền, đƣợc dùng để hƣớng dẫn quá trình tìm kiếm, đánh giá các mẫu kết quả đƣợc tìm thấy. - Tri thức miền có thể là các phân cấp khái niệm, niềm tin của ngƣời sử dụng, các ràng buộc hay các ngƣỡng giá trị, siêu dữ liệu, Data mining engine 14
15. - Thành phần chứa các khối chức năng thực hiện các tác vụ khai phá dữ liệu. User interface - Thành phần hỗ trợ sự tƣơng tác giữa ngƣời sử dụng và hệ thống khai phá dữ liệu. . Ngƣời sử dụng có thể chỉ định câu truy vấn hay tác vụ khai phá dữ liệu. . Ngƣời sử dụng có thể đƣợc cung cấp thông tin hỗ trợ việc tìm kiếm, thực hiện khai phá dữ liệu sâu hơn thông qua các kết quả khai phá trung gian. . Ngƣời sử dụng cũng có thể xem các lƣợc đồ cơ sở dữ liệu/kho dữ liệu, các cấu trúc dữ liệu; đánh giá các mẫu khai phá đƣợc; trực quan hóa các mẫu này ở các dạng khác nhau. 1.4. Các kỹ thuật khai phá dữ liệu Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau nhằm thực hiện hai chức năng mô tả và dự đoán. - Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp (Summarisation), trực quan hoá (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation analyst), . - Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đƣa ra các dự đoán dựa vào các suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây quyết định (Decision tree), thống kê (statictics), mạng nơron (neural network), luật kết hợp, . Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để khai phá dữ liệu hiện nay là : 1.4.1. Phân lớp dữ liệu Mục tiêu của phân lớp dữ liệu đó là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ 15
16. liệu( mỗi mẫu 1 lớp). Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp nhận đƣợc. 1.4.2. Phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cum, sao cho các đối tƣợng thuộc cùng một lớp là tƣơng đồng. 1.4.3. 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. 1.4.4. Luật kết hợp Chẳng hạn nhƣ có luật: âm nhac, thể thao => thiếu nhi, nghĩa là những ngƣời mua sách âm nhạc và thể thao thì cũng mua sách thiếu nhi. Lúc đó ta sẽ quan tâm đến số lƣợng trƣờng hợp khách hàng thỏa mãn luật này trong cơ sở dữ liệu hay độ hỗ trợ (Support) cho luật này. Độ hỗ trợ cho luật chính là phần trăm số bản ghi có cả sách âm nhạc, thể thao và thiếu nhi hay tất cả những ngƣời thích cả ba loại sách nói trên. Tuy nhiên, giá trị độ hỗ trợ là không đủ, có thể có trƣờng hợp ta có một nhóm tƣơng đối những ngƣời đọc cả ba loại trên nhƣng lại có một nhóm với lực lƣợng lớn hơn những ngƣời thích sách thể thao, âm nhạc mà không thích sách thiếu nhi. Trong trƣờng hợp này tính kết hợp rất yếu mặc dù độ hỗ trợ tƣơng đối cao, nhƣ vậy chúng ta cần thêm một độ đo thứ hai đó là độ tin cậy (confidence). Độ tin cậy chính là phần trăm các bản ghi có sách thiếu nhi trong số các bản ghi có sách âm nhạc và thể thao. 1.4.5. Hồi quy Phƣơng pháp hồi quy tƣơng tự nhƣ là phân lớp dữ liệu. Nhƣng khác ở chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc. 1.4.6. Mạng Nơron 16
17. Đây là một trong những kỹ thuật khai phá dữ liệu đƣợc ứng dụng phổ biến hiện nay. Kỹ thuật này phát triển dựa trên một 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 nơron 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á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 nơ ron rất phức tạp và quá trình tiến hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều dữ liệu, nhiều lần kiểm tra thử nghiệm. 1.4.7. Giải thuật di truyền Là quá trình mô phỏng theo tiến hoá của 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 hoá trong sinh học. Việc xây dựng các thuật toán di truyền mô phỏng sinh học nhằm tìm ra các giải pháp tốt nhất bao gồm các bƣớc sau: 1. Tạo ra cơ chế mã di truyền dƣới dạng các xâu của một bảng mã ký tự hạn chế. 2. Thiết lập môi trƣờng nhân tạo trên máy tính có các giải pháp có thể tham gia “đấu tranh sinh tồn” với nhau để xác định độ đo thành công hay thất bại, hay còn gọi là “hàm thích nghi”. 3. Phát triển các “phép lai ghép” để các giải pháp kết hợp với nhau. Khi đó các xâu mã di truyền của giải pháp cha và mẹ bị cắt đi và xếp lại, trong quá trình sinh sản nhƣ vậy các kiểu đột biến có thể đƣợc áp dụng. 4. Cung cấp một quần thể các giải pháp ban đầu tƣơng đối đa dạng và để máy tính thực hiện “cuộc chơi tiến hóa” bằng cách loại bỏ các giải pháp từ mỗi cá thể và thay thế chúng bằng các con cháu hoặc các đột biến của các giải pháp tốt. Thuật toán sẽ kết thúc khi một họ các giải pháp thành công đƣợc sinh ra. 17
18. CHƢƠNG 2: CÁC PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH 2.1 Cây quyết định 2.1.1 Giới thiệu Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tƣợng tới các kết luận về giá trị mục tiêu của sự vật/hiện tƣợng. Mỗi nút trong (internal node) tƣơng ứng với một biến; đƣờng nối giữa nó với nút con của nó thể hiện giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trƣớc các giá trị dự đoán của các biến đƣợc biểu diễn bởi đƣờng đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định đƣợc gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. Ví dụ: Cây quyết định phân lớp mức lƣơng Age? ≤ 35 > 35 salary salary ≤ 40 >40 ≤50 >50 bad good bad good Hình 2. 1: Cây quyết định phân lớp mức lương 2.1.2 Các kiểu cây quyết định Cây quyết định còn có hai loại: - Cây hồi quy (Regression tree): ƣớc lƣợng các hàm giá có giá trị là số thực thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. (Ví dụ: ƣớc tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện.) 18
19. - Cây phân loại (Classification tree): nếu y là một biến phân loại nhƣ: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua). 2.1.3 Ưu điểm của cây quyết định So với các phƣơng pháp khai phá dữ liệu khác, cây quyết định là phƣơng pháp có một số ƣu điểm: - Cây quyết định dễ hiểu. Ngƣời ta có thể hiểu mô hình cây quyết định sau khi đƣợc giải thích ngắn. - Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thƣờng đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị rỗng. - Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thƣờng chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số. - Cây quyết định là một mô hình hộp trắng. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu đƣợc. Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho ta có thể tin tƣởng vào mô hình. 2.1.4 Phân lớp dữ liệu bằng cây quyết định Phân lớp dựa trên cây quyết định rất thích hợp cho việc khai phá dữ liệu vì cây quyết định có cấu trúc đơn giản, dễ hiểu và có thể đƣợc xây dựng khá nhanh, từ cây quyết định có thể dễ dàng rút ra các luật. Quy nạp cây quyết định là một quá trình học tập của cây quyết định từ các nhãn lớp của bộ dữ liệu huấn luyện (training tuple). Một cây quyết định là một biểu đồ dòng dữ liệu nhƣ cấu trúc cây, mỗi nút trong (không phải lá) tƣợng trƣng cho một thuộc tính kiểm tra, mỗi nhánh đại diện cho kết quả của việc kiểm tra, và mỗi nút lá (hay nút giới hạn) giữ một lớp nhãn. Nút đầu tiên trên cây là nút gốc. 19
20. Quá trình phân lớp dữ liệu thông qua 2 bƣớc cơ bản nhƣ sau: Bƣớc 1: Xây dựng mô hình từ tập huấn luyện Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc. Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn lớp. Tập các bộ/mẫu dữ liệu huấn luyện - tập huấn luyện - đƣợc dùng để xây dựng mô hình. Mô hình đƣợc biểu diễn bởi các luật phân lớp, các cây quyết định hoặc các công thức toán học. Hình 2. 2 Xây dựng mô hình Bƣớc 2: Sử dụng mô hình, kiểm tra tính đúng đắn của mô hình và dùng nó để phân lớp dữ liệu mới. Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp. Đánh giá độ chính xác của mô hình: 20
21. Lớp biết trƣớc của một mẫu/bộ dữ liệu đem kiểm tra đƣợc so sánh với kết quả thu đƣợc từ mô hình. Tỉ lệ chính xác bằng phần trăm các mẫu/bộ dữ liệu đƣợc phân lớp đúng bởi mô hình trong số các lần kiểm tra. Hình 2. 3 Sử dụng mô hình Việc tạo cây quyết định bao gồm 2 giai đoạn: Tạo cây và tỉa cây. Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện là ở gốc sau đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính đƣợc chọn. Việc tỉa cây là xác định và xóa những nhánh mà có phần tử hỗn tạp hoặc những phần tử không thể phân vào một lớp nào đó 2.1.5 Xây dựng cây quyết định. Có nhiều thuật toán khác nhau để xây dựng cây quyết định nhƣ: CLS, ID3, C4.5, SLIQ, SPRINT, EC4.5, C5.0 Nhƣng nói chung quá trình xây dựng cây quyết định đều đƣợc chia ra làm 3 giai đoạn cơ bản: a. Xây dựng cây: Thực hiện chia một cách đệ quy tập mẫu dữ liệu huấn luyện cho đến khi các mẫu ở mỗi nút lá thuộc cùng một lớp b. Cắt tỉa cây: Là việc làm dùng để tối ƣu hoá cây. Cắt tỉa cây chính là việc trộn một cây con vào trong một nút lá. 21
22. c. Đánh giá cây: Dùng để đánh giá độ chính xác của cây kết quả. Tiêu chí đánh giá là tổng số mẫu đƣợc phân lớp chính xác trên tổng số mẫu đƣa vào. 2.1.6 Rút ra luật từ cây quyết định Có thể chuyển đổi qua lại giữa mô hình cây quyết định và mô hình dạng luật (IF THEN ). Hai mô hình này là tƣơng đƣơng nhau. Ví dụ từ cây 2.1 ta có thể rút ra đƣợc các luật sau. IF (Age 40) THEN class = good IF (Age>35) AND (salary 35) AND(salary>50) THEN class = good 2.2 Các thuật toán xây dựng cây quyết định 2.2.1 Thuật toán CLS Thuật toán này đƣợc Hovland và Hint giới thiệu trong Concept learning System (CLS) vào những năm 50 của thế kỷ 20. Sau đó gọi tắt là thuật toán CLS. Thuật toán CLS đƣợc thiết kế theo chiến lƣợc chia để trị từ trên xuống. Nó gồm các bƣớc sau: 1. Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn luyện. 2. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị "yes" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "yes" và dừng lại. T lúc này là nút lá. 3. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang giá trị "no" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "no" và dừng lại. T lúc này là nút lá. 4. Trƣờng hợp ngƣợc lại các mẫu của tập huấn luyện thuộc cả hai lớp "yes" và "no" thì: 22
23. + Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ liệu, X có các giá trị v1,v2, vn. + Chia tập mẫu trong T thành các tập con T1, T2, .,Tn. chia theo giá trị của X. + Tạo n nút con Ti (i=1,2 n) với nút cha là nút T. + Tạo các nhánh nối từ nút T đến các nút Ti (i=1,2 n) là các thuộc tính của X. 5. Thực hiện lặp cho các nút con Ti(i =1,2 n) và quay lại bƣớc 2. Ta nhận thấy trong bƣớc 4 của thuật toán, thuộc tính đƣợc chọn để triển khai cây là tuỳ ý. Do vậy cùng với một tập mẫu dữ liệu huấn luyện nếu áp dụng thuật toán CLS với thứ tự chọn thuộc tính triển khai cây khác nhau, sẽ cho ra các cây có hình dạng khác nhau. Việc lựa chọn thuộc tính sẽ ảnh hƣởng tới độ rộng, độ sâu, độ phức tạp của cây. Vì vậy một câu hỏi đặt ra là thứ tự thuộc tính nào đƣợc chọn để triển khai cây sẽ là tốt nhất. Vấn đề này sẽ đƣợc giải quyết trong thuật toán ID3 dƣới đây. 2.2.2 Thuật toán ID3 Thuật toán ID3 đƣợc phát biểu bởi Quinlan (trƣờng đại học Syney, Australia) và đƣợc công bố vào cuối thập niên 70 của thế kỷ 20. Sau đó, thuật toán ID3 đƣợc giới thiệu và trình bày trong mục Induction on decision trees, machine learning năm 1986. ID3 đƣợc xem nhƣ là một cải tiến của CLS với khả năng lựa chọn thuộc tính tốt nhất để tiếp tục triển khai cây tại mỗi bƣớc. ID3 xây dựng cây quyết định từ trên- xuống (top -down). Nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ huấn luyện (training example) hay còn gọi là dữ liệu huấn luyện (training data). Hay nói khác hơn, giải thuật có: Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tƣợng nào đó, và một giá trị phân loại của nó. 23
24. Đầu ra: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu huấn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chƣa gặp trong tƣơng lai. ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên xuống. Lƣu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng có thể phân vùng tập hợp các ví dụ rèn luyện thành những tập con tách rời, mà ở đó mọi ví dụ trong một phân vùng (partition) có một giá trị chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút hiện tại của cây và dùng trắc nghiệm này để phân vùng tập hợp các ví dụ; thuật toán khi đó xây dựng theo cách đệ quy một cây con cho từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của phân vùng đều nằm trong cùng một lớp; lớp đó trở thành nút lá của cây. Các thuộc tính phân loại: Entropy: dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của một tập S đƣợc tính theo công thức +- Entropy(S)= - P log22 (PP ) P log ( ) (2.1) Trong trƣờng hợp các mẫu dữ liệu có hai thuộc tính phân lớp "yes" (+), "no" (-). Ký hiệu p+ là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "yes", và kí hiệu p- là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no" trong tập S. Trƣờng hợp tổng quát, đối với tập con S có n phân lớp thì ta có công thức sau: n Entropy(S)= (- P log (P ))  i2i (2.2) i=1 Trong đó Pi là tỷ lệ các mẫu thuộc lớp i trên tập hợp S các mẫu kiểm tra. Các trƣờng hợp đặc biệt: - Nếu tất cả các mẫu thành viên trong tập S đều thuộc cùng một lớp thì Entropy(S) =0 - Nếu trong tập S có số mẫu phân bổ đều nhau vào các lớp thì Entropy(S) =1 - Các trƣờng hợp còn lại 0< Entropy(S)<1 24
25. Information Gain (viết tắt là Gain): Gain là đại lƣợng dùng để đo tính hiệu quả của một thuộc tính đƣợc lựa chọn cho việc phân lớp. Đại lƣợng này đƣợc tính thông qua hai giá trị Information và Entropy. Cho tập dữ liệu S gồm có n thuộc tính Ai(i=1,2 n) giá trị Information của thuộc tính Ai ký hiệu là Information(Ai) đƣợc xác định bởi công thức . 푛 (2.3) Information( 푖) = − 푙표 2(푃푖) = 푛푡 표 (푆) 푖=1 Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S,A) và đƣợc tính theo công thức sau: (2.4) S V Gain(S, A) Entropy(S)  Entropy(SV ) V Value(A) S Trong đó : . S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tƣơng ứng là các giá trị của thuộc tính A. . Sv bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v. . |Sv| là số phần tử của tập Sv. . |S| là số phần tử của tập S. Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi bƣớc triển khai cây, thuộc tính đƣợc chọn để triển khai là thuộc tính có giá trị Gain lớn nhất. Với việc tính toán giá trị Gain để lựa chọn thuộc tính tối ƣu cho việc triển khai cây, thuật toán ID3 đƣợc xem là một cải tiến của thuật toán CLS. Tuy nhiên thuật toán ID3 không có khả năng xử lý đối với những dữ liệu có chứa thuộc tính số - thuộc tính liên tục (numeric attribute) và khó khăn trong việc xử lý các dữ liệu thiếu (missing data)và dữ liệu nhiễu (noisy data). Vấn đề này sẽ đƣợc giải quyết trong thuật toán C4.5 sau đây. 2.2.3 Thuật toán C4.5 25
26. Thuật toán C4.5 đƣợc phát triển và công bố bởi Quinlan vào năm 1996. Thuật toán C4.5 là một thuật toán đƣợc cải tiến từ thuật toán ID3. Giải thuật C4.5 là một giải thuật học đơn giản nhƣng tỏ ra thành công trong nhiều lĩnh vực. C4.5 là một thuật toán hay vì cách biểu diễn tri thức học đƣợc của nó, tiếp cận của nó trong việc quản lý tính phức tạp, kinh nghiệm của nó dùng cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu. Thuật toán C4.5 biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree). Biểu diễn này cho phép chúng ta xác định phân loại của một đối tƣợng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. Các thuộc tính: a. Entropy: Tập S là tập dữ liệu huấn luyện, trong đó thuộc tính phân loại có hai giá trị, giả sử là âm (-) và dƣơng (+). Trong đó: p+ là phần các ví dụ dƣơng trong tập S. p_ là phần các ví dụ âm trong tập S. Khi đó, entropy đo độ hỗn loạn của tập S theo công thức sau: Entropy(S) = -p log p - p log p + 2 + - 2 - (2.5) Một cách tổng quát hơn, nếu các ví dụ của tập S thuộc nhiều hơn hai loại, giả ử là có c giá trị phân loại thì công thức entropy tổng quát là: c (2.6) Entropy(S)  pilog 2pi i 1 Ví dụ: Xét bài toán “có chơi tennis” ứng với thời tiết hay không? Thuật toán C4.5 sẽ học cây quyết định từ tập dữ liệu huấn luyện sau: Quang Nhiệt Chơi Ngày cảnh độ Độ ẩm Gió tennis 26
27. D1 Nắng Nóng Cao Nhẹ Không D2 Nắng Nóng Cao Mạnh Không D3 Âm u Nóng Cao Nhẹ Có D4 Mƣa Ấm áp Cao Nhẹ Có D5 Mƣa Mát TB Nhẹ Có D6 Mƣa Mát TB Mạnh Không D7 Âm u Mát TB Mạnh Có D8 Nắng Ấm áp Cao Nhẹ Không D9 Nắng Mát TB Nhẹ Có D10 Mƣa Ấm áp TB Nhẹ Có D11 Nắng Ấm áp TB Mạnh Có D12 Âm u Ấm áp Cao Mạnh Có D13 Âm u Nóng TB Nhẹ Có D14 Mƣa Ấm áp Cao Mạnh Không Từ 14 mẫu của bảng dữ liệu “Chơi tennis”, ta nhận thấy trong tập thuộc tính đích S có 9 mẫu thuộc lớp dƣơng và 5 mẫu thuộc lớp âm (ký hiệu là [9+, 5-] ). Do đó: Entropy(S) = - (9/14)log2(9/14) - (5/14)log2(5/14) = 0,940 b. Gain: Entropy là một số đo đo độ pha trộn của một tập ví dụ, bây giờ chúng ta sẽ định nghĩa một phép đo hiệu suất phân loại các ví dụ của một thuộc tính. Phép đo này gọi là lƣợng thông tin thu đƣợc (hay độ lợi thông tin), nó đơn giản là lƣợng giảm entropy mong đợi gây ra bởi việc phân chia các ví dụ theo thuộc tính này. Một cách chính xác hơn, Gain(S, A) của thuộc tính A, trên tập S, đƣợc định nghĩa nhƣ sau: SV Gain(S, A) Entropy(S)  Entropy(SV ) V Value(A) S Giá trị Value (A) là tập các giá trị có thể cho thuộc tính A, và Sv là tập con của S mà A nhận giá trị v. Ví dụ: Trở lại với bảng dữ liệu “Chơi tennis”, áp dụng công thức trên ta có: 27
28. Gain(S, Quang cảnh) = Entropy(S) - (5/14)Entropy(Snắng) – (4/14)Entropy(S âm u) – (5/4)Entropy(Smƣa) = 0,246 Một cách tƣơng tự: Gain(S, Độ ẩm) = 0,151 Gain(S, Nhiệt độ) = 0,029 Gain(S, Gió) = 0,048 Ta thấy, Gain(S, Quang cảnh) lớn nhất nên thuộc tính Quang cảnh đƣợc chọn làm nút phân tách cây. Sau khi lập đƣợc cấp đầu tiên của cây quyết định ta lại xét nhánh Nắng Tiếp tục lấy Entropy và Gain cho nhánh Nắng ta đƣợc hiệu suất nhƣ sau: Gain(S Nắng, Độ ẩm) = 0,970 Gain(S Nắng, Nhiệt độ) = 0,570 Gain(S Nắng, Gió) = 0,019 Nhƣ vậy thuộc tính độ ẩm có hiệu suất phân loại cao nhất trong nhánh Nắng nên ta chọn thuộc tính Độ ẩm làm nút kế tiếp . c. SplitInfo và Gain Ratio Khái niệm độ lợi thông tin Gain có xu hƣớng ƣu tiên các thuộc tính có số lƣợng lớn các giá trị. Nếu thuộc tính D có giá trị riêng biệt cho mỗi bảng ghi (thuộc tính Ngày ở bảng dữ liệu trên), thì Entropy(S, D) = 0, nhƣ vậy Gain(S, D) sẽ đạt giá trị cực đại. Rõ ràng, một phân vùng nhƣ vậy thì việc phân loại là vô ích. Thuật toán xét tất cả các phép thử có thể để phân chia tập dữ liệu đã cho và chọn ra một phép thử có giá trị GainRatio tốt nhất. GainRatio là một đại lƣợng để đánh giá độ hiệu quả của thuộc tính dùng để thực hiện phép tách trong thuật toán để phát triển cây quyết định. GainRatio đƣợc tính dựa trên kết quả tính toán đại lƣợng Information Gain theo công thức sau: 28
29. Với: n Ti Ti SplitInfo (X) =-  log2 (2.7) i=1 T T Gain() X GainRatio() X SplitInfo(X) (2.8) Trong đó: Value(X) là tập các giá trị của thuộc tính X Ti là tập con của tập T ứng với thuộc tính X = giá trị là vi. Ví dụ: Tính Gain Ratio cho các thuộc tính ở bảng dữ liệu 1.7 SplitInformation(S, Quang cảnh) = - (5/14)log2(5/14)-(4/14)log2(4/14) -(5/14)log2(5/14) = 1,57 Gain(S, Quang cảnh) = 0,246 GainRatio(S, Quang cảnh) = 0,246/1,57 = 0,157 Tƣơng tự, ta cũng tính đƣợc: GainRatio(S, Nhiệt độ) = 0,0187 GainRatio(S, Độ ẩm) = 0,151 GainRatio(S, Gió) = 0,049 Ta nhận thấy, GainRatio(S, Quang cảnh) có giá trị lớn nhất nên thuộc tính Quang cảnh đƣợc chọn làm nút phân tách cây. Đối với các thuộc tính liên tục, chúng ta tiến hành phép thử nhị phân cho mọi giá trị của thuộc tính đó. Để thu thập đƣợc giá trị Entropy gain của tất cả các phép thử nhị phân một cách hữu hiệu ta tiến hành xắp xếp các dữ liệu theo giá trị của thuộc tính liên tục đó bằng thuật toán Quicksort, (2.8) đƣợc sử dụng 29
30. làm tiêu chuẩn để lựa chọn thuộc tính khi phân lớp. Thuộc tính đƣợc chọn là thuộc tính có giá trị GainRatio tính theo (2.8) đạt giá trị lớn nhất. Một số cài tiến của thuật toán C4.5: 1. Làm việc với thuộc tính đa trị Tiêu chuẩn Gain có một khuyết điểm là không chấp nhận các thuộc tính đa trị. Vì vậy thuật toán C4.5 đã đƣa ra các đại lƣợng GainRatio và SplitInfo (SplitInformation), chúng đƣợc xác định theo các công thức (2.7), (2.8) Giá trị SplitInfo là đại lƣợng đánh giá thông tin tiềm năng thu thập đƣợc khi phân chia tập T thành n tập hợp con. GainRatio là tiêu chuẩn để đánh giá việc lựa chọn thuộc tính phân loại. 2. Làm việc với dữ liệu bị thiếu Thuật toán vừa xây dựng dựa vào giả thuyết tất cả các mẫu dữ liệu có đủ các thuộc tính. Nhƣng trong thực tế, xẩy ra hiện tƣợng dữ liệu bị thiếu, tức là ở một số mẫu dữ liệu có những thuộc tính không đƣợc xác định,hoặc mâu thuẫn, hoặc không bình thƣờng. Ta xem xét kỹ hơn với trƣờng hợp dữ liệu bị thiếu. Đơn giản nhất là không đƣa các mẫu với các giá trị bị thiếu vào, nếu làm nhƣ vậy thì có thể dẫn đến tình trạng thiếu các mẫu học. Giả sử T là một tập hợp gồm các mẫu cần đƣợc phân loại, X là phép kiểm tra theo thuộc tính L, U là số lƣợng các giá trị bị thiếu của thuộc tính L. Khi đó ta có k freq(C ,T) freq ( C , T ) Info(T) = - j *log j  2 (2.11) j=1 |T|-U |TU | n |T| Infox2 (T) = -  *log (Ti ) (2.12) j=1 |T|-U Trong trƣờng hợp này, khi tính tần số freq (Ci , T) ta chỉ tính riêng các mẫu với giá trị trên thuộc tính L đã xác định. Khi đó tiêu chuẩn (2.8) đƣợc viết lại bằng công thức (2.13) nhƣ sau: 30
31. ||TU Gain( X ) (Info(T)-Info ( T )) ||T x (2.13) Tƣơng tự thay đổi tiêu chuẩn (2.13). Nếu phép kiểm tra có N giá trị đầu vào thì tiêu chuẩn (2.13) đƣợc tính nhƣ trong trƣờng hợp chia N tập hợp ban đầu thành (N+1) tập hợp con. Giả sử phép thử X có các giá trị O1,O2, .On đƣợc lựa chọn theo tiểu chuẩn (2.13), ta cần xử lý nhƣ thế nào với các dữ liệu bị thiếu. Giả sử mẫu từ tập hợp T với đầu ra là Oi có liên quan đến tập hợp Ti thì khả năng mẫu đó thuộc tập hợp Ti là 1. Giả sử mỗi mẫu trong Ti có một chỉ số xác định xác suất thuộc tập hợp Ti. Nếu mẫu có giá trị thuộc tính L thì có trọng số bằng 1. Nếu trong trƣờng hợp ngƣợc lại, thì mẫu này liên quan đến tập con T1,T2, Tn với xác xuất tƣơng ứng là : TTT 12, , , n |TUTUTU | | | | | Ta có thể dễ dàng thấy đƣợc rằng tổng các xác xuất này bằng 1. n T i 1  i 1 TU Tóm lại giải pháp này đƣợc phát biểu nhƣ sau: xác suất xuất hiện của các giá trị bị thiếu tỷ lệ thuận với xác suất xuất hiện của các giá trị không thiếu. 2.2.4 Cắt tỉa cây quyết định Qua tìm hiểu các thuật toán xây dựng cây quyết định ở trên, ta thấy việc xây dựng cây bằng cách phát triển nhánh cây đầy đủ theo chiều sâu để phân lớp hoàn toàn các mẫu huấn luyện; nhƣ thuật toán CLS và thuật toán ID3 đôi khi gặp khó khăn trong các trƣờng hợp dữ liệu bị nhiễu (Noisy Data) hoặc dữ liệu bị thiếu 31
32. (Missing Data) không đủ để đại diện cho một quy luật; tức là tạo ra các nút có số mẫu rất nhỏ. Trong trƣờng hợp này, nếu thuật toán vẫn cứ phát triển cây thì ta sẽ dẫn đến một tình huống mà ta gọi là tình trạng "Over fitting" trong cây quyết định. Vẫn đề Over fitting là một khó khăn trong việc nghiên cứu và ứng dụng cây quyết định. Để giải quyết tình trạng này ngƣời ta sử dụng phƣơng pháp cắt tỉa cây quyết định. Có hai phƣơng pháp cắt tỉa cây quyết định. a) Tiền cắt tỉa (Prepruning): Chiến thuật tiến cắt tỉa nghĩa là sẽ dừng sớm việc phát triển cây trƣớc khi nó vƣơn đến điểm mà việc phân lớp các mẫu huấn luyện đƣợc hoàn thành. Nghĩa là trong quá trình xây dựng cây, một nút có thể sẽ không đƣợc tách thêm bƣớc nữa nếu nhƣ kết quả của phép tách đó rơi vào một ngƣỡng gần nhƣ chắc chắn. Nút đó trở thành nút lá và đƣợc gán nhãn là nhãn của lớp phổ biến nhất của tập các mẫu tại nút đó. b) Hậu cắt tỉa (Postpruning): Chiến thuật này ngƣợc với chiến thuật tiền cắt tỉa. Nó cho phép phát triển cây đầy đủ sau đó mới cắt tỉa. Nghĩa là xây dựng cây sau đó mới thực hiện cắt bỏ các nhánh không hợp lý. Trong quá trình xây dựng cây theo chiến thuật hậu cắt tỉa thì cho phép tình trạng Over fitting xẩy ra. Nếu một nút mà các cây con của nó bị cắt thì nó sẽ trở thành nút lá và nhãn của lá đƣợc gán là nhãn của lớp phổ biến nhất của các con trƣớc đó của nó. Trong thực tế, phƣơng pháp hậu cắt tỉa là một phƣơng pháp khá thành công cho việc tìm ra các giả thuyết chính xác cao. Chiến thuật hậu cắt tỉa đƣợc tiến hành thông qua việc tính toán lỗi nhƣ sau: Giả sử ta gọi: E(S) là lỗi tĩnh (Static error hay expected error) của một nút S; BackUpError(S) là lỗi từ các nút con của S (Back Up Error); Error(S) là lỗi của nút S. Các giá trị này đƣợc tính nhƣ sau: Error(S) = Min(E(S), BackUpError(S)) E(S) = (N - n + 1) / (N + 2) 32
33. Trong đó: N là tổng số mẫu ở nút S n là số mẫu của lớp phổ biến nhất trong S. Trong trƣờng hợp tổng quát, nếu thuộc tính lớp có K giá trị (K lớp) thì: E(S) = (N-n+K-1) / (N+K) BackUpError(S) = Pi Error(Si ) i Trong đó: Si là nút con của S Pi là tỷ lệ số mẫu trong Si trên số mẫu trong S Nhƣ vậy các nút lá sẽ có lỗi Error(Si) = E(Si) do nút lá không có nút con dẫn đến không có lỗi BackUpError. Nếu BackUpError(S) >= E(S) thì chiến thuật hậu cắt tỉa cây quyết định sẽ cắt tại nút S (tức là cắt bỏ các cây con của S). Tóm lại, việc cắt tỉa cây nhằm: tối ƣu hoá cây kết quả. Tối ƣu về kích cỡ cây và về độ chính xác của việc phân lớp bằng cách cắt bỏ các nhánh không phù hợp (over fitted branches). Để thực hiện việc cắt tỉa cây thì có các kỹ thuật cơ bản sau đây: - Sử dụng tập hợp tách rời của mẫu học để đánh giá tính hữu dụng của việc hậu cắt tỉa những nút trong cây. Sử dụng kỹ thuật cắt tỉa cây này có thuật toán CART, gọi tắt là chi phí phức tạp (Cost - Complexity prunning). - Áp dụng phƣơng pháp thống kê để đánh giá và cắt bỏ các nhánh có độ tin cậy kém hoặc mở rộng tiếp các nhánh có độ chính xác cao. Kỹ thuật cắt tỉa này đƣợc gọi là cắt tỉa bi quan và thƣờng đƣợc sử dụng để cắt tỉa các cây đƣợc xây dựng theo thuật toán ID3 và C4.5. - Kỹ thuật mô tả độ dài tối thiểu - MDL (Minimum Description Length) (với kỹ thuật này không cần kiểm tra các mẫu). Kỹ thuật này không cần thiết phải kiểm tra các mẫu và nó thƣờng đƣợc sử dụng trong các thuật toán SLIQ, SPRINT. 2.2.5 Đánh giá và kết luận về các thuật toán xây dựng cây quyết định 33
34. Các thuật toán xây dựng cây quyết định vừa đƣợc trình bày ở trên đều có những điểm mạnh và điểm yếu riêng của nó. - Đầu tiên ta xét đến thuật toán CLS đây là một trong những thuật toán ra đời sớm nhất. Nó chỉ áp dụng cho các CSDL có các thuộc tính nhỏ, giá trị các thuộc tính dạng phân loại hay rời rạc. Còn đối với các CSDL lớn và có chứa các thuộc tính mà giá trị của nó là liên tục thì CLS làm việc không hiệu quả.Thuật toán có thể cho các kết quả khác nhau với cùng một tập dữ liệu đầu vào. Bởi vì, thuật toán này chƣa có tiêu chí để lựa chọn thuộc tính trong quá trình xây dựng cây. Nhƣng đây là thuật toán đơn giản, dễ cài đặt, phù hợp trong việc hình thành ý tƣởng và giải quyết những nhiệm vụ đơn giản. - Thuật toán ID3: trong thuật toán ID3, Quinlan đã khắc phục đƣợc hạn chế của thuật toán CLS (ID3 đƣợc xem là phiên bản cải tiến của CLS). Thuật toán này làm việc rất có hiệu quả, nó cho kết quả tối ƣu hơn thuật toán CLS . Khi áp dụng thuật toán ID3 cho cùng một tập dữ liệu đầu vào và thử nhiều lần thì cho cùng một kết quả. Bởi vì, thuộc tính ứng viên đƣợc lựa chọn ở mỗi bƣớc trong quá trình xây dựng cây đƣợc lựa chọn trƣớc. Tuy nhiên thuật toán này cũng chƣa giải quyết đƣợc về vấn đề thuộc tính số, liên tục, số lƣợng các thuộc tính còn bị hạn chế và giải quyết hạn chế với vấn đề dữ liệu bị thiếu hoặc bị nhiễu. - Thuật toán C4.5: Để tiếp tục khắc phục những nhƣợc điểm của thuật toán ID3, Quinlan đã đƣa ra thuật toán C4.5(C4.5 là sự cải tiến cho thuật toán ID3 và cọi là phiên bản sau của ID3). Trong thuật toán này đã giải quyết đƣợc vấn đề làm việc với thuộc tính số(liên tục), thuộc tính có nhiều giá trị, và vấn đề dữ liệu bị thiếu hoặc bị nhiễu. Trong C4.5 thực hiện việc phân ngƣỡng với thuộc tính số bằng phép tách nhị phân đƣa vào đại lƣợng GainRatio thay thế cho đại lƣợng Gain của ID3. Để giải quyết đƣợc vấn đề thuộc tính có nhiều giá trị. Ngoài ra C4.5 còn có bƣớc cắt tỉa nhánh không phù hợp. Tuy nhiên yếu điểm của thuật toán này là làm việc không hiệu quả với những CSDL lơn vì chƣa giải quyết đƣợc vấn đề bộ nhớ. Mặc dù đã có nhiều cải tiến, nhiều thuật toán xây dựng cây quyết định ra đời, nhƣng nói chung vấn còn nhiều vấn đề khó khăn phức tạp và nhiều thách thức trong KPDL bằng cây quyết định. Nhƣ vấn đề dữ liệu bị thiếu giá 34
35. trị đối với các thuộc tính trong CSDL. Vấn đề các CSDL rất lớn về số lƣợng các thuộc tính và về số lƣợng các bản ghi, vấn đề về bộ nhớ Những vấn đề này luôn làm đau đầu những nhà khoa học. Trên thực tế các thuật toán xây dựng cây quyết định vấn đang đƣợc cải tiến, nghiên cứu và phát triển. 35
36. CHƢƠNG 3: CẶT ĐẶT CHƢƠNG TRÌNH KHAI PHÁ DỮ LIỆU SỬ DỤNG CÂY QUYẾT ĐỊNH 3.1 Bài toán thực tế Trong cuộc sống hằng ngày, mỗi ngƣời trong chúng ta đều phải ra không biết bao nhiêu quyết định liên quan đến các sinh hoạt cá nhân từ ăn gì, uống gì, làm gì, khi nào, ở đâu, là các quyết định rất bình thƣờng, quyết định đó có thể đƣợc suy tính kỹ càng, cũng có thể chỉ là quyết định theo cảm xúc tức thời. Tuy nhiên, đối với những nhà quản lý hay những ngƣời làm các công việc liên quan đến: phân loại thƣ điện tử, dự báo thời tiết, đầu tƣ chứng khoán, đầu tƣ tài chính, một quyết định đƣa ra rất quan trọng, vì vậy quyết định đƣợc lựa chọn phải là quyết định có độ tin cây lớn nhất và an toàn nhất. Từ thực tiễn trên, đề xuất xây dựng một chƣơng trình hỗ trợ ra quyết định, giúp ngƣời dùng có đƣợc quyết định đáng tin cậy, an toàn và nhanh chóng. 3.2 Cài đặt thuật toán Thuật toán xây dựng cây quyết định đƣợc áp dụng: Thuật toán C4.5 Thuật toán C4.5 là học cây quyết định từ một tập các ví dụ huấn luyện (training example) hay còn gọi là dữ liệu huấn luyện (training data). Đầu vào: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tƣợng nào đó, và một giá trị phân loại của nó. Đầu ra: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu huấn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chƣa gặp trong tƣơng lai. Thuật toán C4.5 đƣợc thực hiện qua các bƣớc chính sau: 36
37. 3.2.1 Tính độ hỗn loạn: Entropy Đầu vào: số giá trị dƣơng và số giá trị âm của cả bảng hoặc tập thuộc tính con Đầu ra: giá trị Entropy của bảng hoặc thuộc tính tƣơng ứng //Tính độ hỗn loạn Entropy private double entropy(int tot, int xau) { int tong = tot + xau; double tyleTot = (double)tot / tong; double tyleXau = (double)xau / tong; if (tyleTot != 0) tyleTot = -(tyleTot) * System.Math.Log(tyleTot, 2); if (tyleXau != 0) tyleXau = -(tyleXau) * System.Math.Log(tyleXau, 2); double _entropy = tyleTot + tyleXau; return _entropy; } 3.2.2 Tính: GainRatio Đầu vào: Giá trị Entropy toàn bảng, thuộc tính cần xét, danh sách giá trị, danh kết quả tƣơng ứng của thuộc tính Đầu ra: giá trị GainRatio của thuộc tính đó private double _tinhGainRatio(double enTropy, string attr, List listValue, List attrList, List > data, List resultList) { double splitInfo = 0.0; double Gain; double sum = 0.0; List tem = this.laygiatricot_khonglap(attr, attrList, data); for (int i = 0; i < tem.Count(); i++) { int positives = 0, negatives = 0; this.tinhsogtritotxau(attr, attrList, data, tem[i], resultList, out positives, out negatives); double entropy = this.entropy(positives, negatives); sum += -((double)(positives + negatives) / listValue.Count()) * entropy; //Tính splitInfo splitInfo += ((double)(positives + negatives) / listValue.Count()) * System.Math.Log(((double)(positives + negatives) / listValue.Count()), 2); } Gain = enTropy + sum; 37
38. return Gain / splitInfo;//tra ve gia tri Gain ratio } 3.2.3 Xây dựng cây Function C45_builder(tập_ví_dụ, tập_thuộc_tính) begin if mọi ví dụ trong tập_ví_dụ đều nằm trong cùng một lớp then return một nút lá đƣợc gán nhãn bởi lớp đó else if tập_thuộc_tính là rỗng then return nút lá đƣợc gán nhãn bởi tuyển của tất cả các lớp trong tập_ví_dụ else begin Chọn một thuộc tính P, lấy nó làm gốc cho cây hiện tại; Xóa P ra khỏi tập_thuộc_tính; Với mỗi giá trị V của P begin Tạo một nhánh của cây gán nhãn V; Đặt vào phân_vùng V các ví dụ trong tập_ví_dụ có giá trị V tại thuộc tính P; Gọi C45_builder (phân_vùng V, tập_thuộc_tính), gắn kết quả vào nhánh V end end end private void xaydungcay(ref Node nodegoc, string val, ref List > dulieu, ref List listcot, ref List listketluan) { //thay đổi giá trị value của node string backupVal = val; if (val != "") val = "(" + val + ") "; int pos = sokqtot(listketluan); //nếu đồng nhất thì gán nhãn if (pos == listketluan.Count || pos == 0) { Node temNode; if (pos == 0) { temNode = new Node(val + "==> [Kết luận = " + _negative + "]", nodegoc.level + 1); temNode.value = 0; } else { 38
39. temNode = new Node(val + "==> [Kết luận = " + _positive + "]", nodegoc.level + 1); temNode.value = 1; } temNode.edge_value = backupVal; temNode.isLeaves = true; nodegoc.addChild(temNode); return; }//chưa đồng nhất thì tiếp tục phân lớp else { //tính entropy của thuộc tính hiện tại double entropyx = this.entropy(pos, listketluan.Count - pos); //tính độ đo gain ratio gán vào mảng temp double[] temp = new double[listcot.Count]; if (temp.Length == 0) return; for (int i = 0; i listValue = dulieucot(listcot[i], listcot, dulieu); temp[i] = -(this._tinhGainRatio(entropyx, listcot[i], listValue, listcot, dulieu, listketluan)); } //tìm thuộc tính có gain ratio max để phân lớp double max = temp[0]; int maxIdx = 0; for (int i = 0; i max) { max = temp[i]; maxIdx = i; } } //tìm được rồi thì thêm vào con của nodegoc Node temNode = new Node(val + listcot[maxIdx], nodegoc.level + 1); temNode.edge_value = backupVal; temNode.attr = listcot[maxIdx]; temNode.value = temp[maxIdx]; nodegoc.addChild(temNode); //danh sách các lớp được phân theo thuộc tính này, dựa vào giá trị khác nhau để phân lớp List valueList = laygiatricot_khonglap(listcot[maxIdx], listcot, dulieu); foreach (string temval in valueList) { //tạo data mới ứng với yêu cầu mới //tạo result mới ứng với yêu cầu mới List > newData = new List >(); List newResultList = new List (); List newAttrList = new List (); //lọc dữ liệu từ trong data theo giá trị value newData = _getAllValueRows(temval, dulieu, maxIdx); 39
40. newResultList = _getResultList(temval, dulieu[maxIdx], listketluan); foreach (string attrListItem in listcot) { if (attrListItem != listcot[maxIdx]) { newAttrList.Add(attrListItem); } } //đệ quy gọi lại hàm với nhánh dữ liệu con của thuộc tính this.xaydungcay(ref temNode, temval, ref newData, ref newAttrList, ref newResultList); } } } 3.3 Hình ảnh demo Hình 3. 1 Giao diện khi mở chương trình 40
41. Hình 3. 2 Load dữ liệu và tạo cây quyết định 41
42. Hình 3. 3 Tiến hành cắt tỉa cây Hình 3. 4 Hình ảnh của cây quyết định 42
43. Hình 3. 5 Rút ra luật từ cây quyết định Hình 3. 6 Phân tích dữ liệu mới 43
44. KẾT LUẬN Những nghiên cứu về khai phá dữ liệu và ứng dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú đƣợc lƣu trữ trong các hệ thống thông tin. Khai phá dữ liệu cũng đƣợc áp dụng nhiều trong việc tƣ vấn, dự báo , giáo dục. Trong khuôn khổ khóa luận tốt nghiệp này, em đã nghiên cứu, phân tích, đánh giá các thuật toán phân lớp dữ liệu dựa trên cây quyết định. Tiêu biểu là các thuật toán CLS, ID3 và C4.5. Các thuật toán này có cách thức lƣu trữ dữ liệu và xây dựng cây quyết định dựa trên những độ đo khác nhau. Do đó các thuật toán này có phạm vi ứng dụng vào các cơ sở dữ liệu có kích thƣớc khác nhau. C4.5 là thuật toán xử lý đầy đủ các vấn đề của quá trình phân lớp dữ liệu: lựa chọn thuộc tính tốt nhất, lƣu trữ phân chia dữ liệu, xử lý giá trị thiếu, tránh quá vừa, cắt tỉa cây, Với những lý do đó C4.5 đã trở thành thuật toán phổ biến nhất trong những ứng dụng vừa và nhỏ. Quá trình triển khai, cài đặt thử nghiệm cùng với các đánh giá hiệu năng mô hình phân lớp C4.5 đã đƣợc tiến hành. Và đã thu đƣợc nhiều kết quả có ý nghĩa thực tiến, cũng nhƣ các kết quả gợi mở những hƣớng nghiên cứu tiếp theo. 44
45. TÀI LIỆU THAM KHẢO [1]. Anurag Srivastava, Eui- Hong Han, Vipin Kumar, Vieet Singh. Parallel Formulations of Decision-Tree Classification Algorithm. Kluwer Academic Publisher, 1999. [2]. Anurag Srivastava, Vineet Singh, Eui- Hong (Sam) Han, Vipin Kumar. An Efficient, Scalable, Parallel Classifier for Data mining. [3]. Ron Kohavi, J. Ross Quinlan. Decision Tree Discovery, 1999. [4]. Vanden Berghen Frank (2003), C4.5 – Classification Tree, Universit Libre de bruxelles. [5]. Vũ Tiến Thành – Lƣu Công Tố - Thuật toán cây quyết định C4.5. [6]. Huỳnh Trâm Võ - Học liệu mở Việt Nam - Tiếp cận ký hiệu: Giải thuật quy nạp cây quyết định ID3. [7]. Lê Văn Dực (2006), Hệ hỗ trợ ra quyết định, NXB Đại học Quốc gia TP Hồ Chí Minh. [8]. Khoa khoa học & Kỹ thuật máy tính - Slide & bài giảng Data mining – Trƣờng Đại học quốc gia TP Hồ Chí Minh. [9]. á_dữ_liệu tháng 3/2013. [10]. Cây quyết định - ây_quyết_định tháng 3/2013. [11]. tháng 3/2013. 45