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

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 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 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. 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 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 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. 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: 9 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. 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 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. 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. 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à 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. 14 1.3.3. Kiến trúc của 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 User Interface Pattern Evaluation Data mining Enggine Database or Data Warehouse Server Knowledge Base Database Data Warehouse Other Infor Repositories World Wide Web Data cleaning, integration and selection Hình 1. 3 Kiến trúc của mộ