Báo cáo thực tập tốt nghiệp: Khai phá dữ liệu bằng cây quyết định và ứng dụng

Chia sẻ: Saucaca | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

1.056
lượt xem 165
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Báo cáo thực tập tốt nghiệp: Khai phá dữ liệu bằng cây quyết định và ứng dụng có cấu trúc gồm 3 chương với nội dung trình bày về công nghệ khai phá trí thức; các phương pháp khai phá dữ liệu bằng cây quyết định; cài đặt chương trình khai phá dữ liệu sử dụng cây quyết định. Tài liệu hữu ích với những bạn chuyên ngành Công nghệ thông tin và những bạn quan tâm tới lĩnh vực này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo thực tập tốt nghiệp: 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
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
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
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
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
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
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
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
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
-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
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
Đâ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
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
- 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
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