Đề tài Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining)

Nội dung text: Đề tài Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining)

1. LỜI CẢM ƠN Trước tiên em xin được gửi lời cảm ơn chân thành tới các thầy cô giáo trong khoa Công nghệ thông tin - Trường đại học sư phạm Hà Nội đã tần tình giúp đỡ và giảng dạy cho chúng em trong những năm học vừa qua. Đặc biệt, em xin gửi lời cảm ơn chân thành nhất tới cô giáo - T.S Hồ Cẩm Hà cùng các thầy cô giáo trong tổ bộ môn Hệ thống thông tin đã tận tình hướng dẫn, giúp đỡ em hoàn thành đề tài nghiên cứu khoa học này. Trong thời gian vừa qua mặc dù em đã cố gắng rất nhiều để hoàn thành tốt đề tài nghiên cứu khoa học của mình. Song chắc chắn kết quả nghiên cứu sẽ không tránh khỏi những thiếu sót, vì vậy em kính mong nhận được sự chỉ bảo và góp ý của quý thầy cô và các bạn. Em xin chân thành cám ơn! Ký tên Hạnh Nguyễn Thị Hạnh
2. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học MỤC LỤC LỜI MỞ ĐẦU 3 Chương 1: Tổng quan về khai phá dữ liệu 4 1.1. Khám phá tri thức và khai phá dữ liệu là gì? 4 1.2. Quá trình phát hiện tri thức 4 1.2.1. Hình thành và định nghĩa bài toán 5 1.2.2. Thu thập và tiền xử lý dữ liệu 5 1.2.3. Khai phá dữ liệu và rút ra các tri thức 6 1.2.4. Phân tích và kiểm định kết quả 6 1.2.5. Sử dụng các tri thức phát hiện được 6 1.3. Quá trình khai phá dữ liệu 7 1.3.1. Gom dữ liệu (gatherin) 7 1.3.2. Trích lọc dữ liệu (selection) 7 1.3.3. Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing). 8 1.3.4. Chuyển đổi dữ liệu (transformation) 81.3.5. Phát hiện và trích mẫu dữ liệu ( pattern extraction and discovery) 8 1.3.6. Đánh giá kết quả mẫu (evaluation of result ) 8 1.4. Chức năng của khai phá dữ liệu 9 1.5. Các kỹ thuật khai phá dữ liệu 9 1.5.1. Phân lớp dữ liệu: 9 1.5.2. Phân cụm dữ liệu: 9 1.5.3. Khai phá luật kết hợp: 10 1.5.4. Hồi quy: 10 1.5.5. Giải thuật di truyền: 10 1.5.6. Mạng nơron: 10 1.5.7. Cây quyết định. 11 1.6. Các dạng dữ liệu có thể khai phá được 11 1.7. Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá dữ liệu 11 1.7.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu 11 1.7.2. Ứng dụng của khai phá dữ liệu 11 1.8. Các thách thức và hướng phát triển của phát hiện tri thức và khai phá dữ liệu. 12 Chương 2: Khai phá dữ liệu bằng cây quyết định 13 2.1. Cây quyết định 13 2.1.1. Định nghĩa cây quyết định 13 2.1.2. Ưu điểm của cây quyết định 14 2.1.3. Vấn đề xây dựng cây quyết định 14 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 1
3. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 2.1.4. Rút ra các luật từ cây quyết định. 15 2.2. Các thuật toán khai phá dữ liệu bằng cây quyết định 15 2.2.1. Thuật toán CLS 15 2.2.2. Thuật toán ID3 16 2.2.3. Thuật toán C4.5 18 2.2.4. Thuật toán SLIQ[5] 22 2.2.5. Cắt tỉa cây quyết định 25 2.2.6. Đánh giá và kết luận về các thuật toán xây dựng cây quyết định 27 Chương 3: Xây dựng chương trình dêmo 29 3.1. Mô tả bài toán 29 3.2. Thu thập và tiền xử lý dữ liệu 29 3.3. Chương trình 30 Chương 4. KẾT LUẬN 30 4.1 Đánh Giá 30 4.1.1 Lý thuyết 30 4.1.2 Ứng dụng 30 4.2 Hướng Phát Triển 30 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 2
4. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học LỜI 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: Tìm hiể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 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 3
5. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Chương 1: Tổng quan về khai phá dữ liệu 1.1. Khám phá tri thức và khai phá dữ liệu là gì? 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 [4]. 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 [4]. 1.2. Quá trình phát hiện tri thức Quá trình khám phá tri thức được tiến hành qua 5 bước sau [5]: Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 4
6. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Hình 1.1. Quá trình khám phá tri thức 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à tiền 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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 5
7. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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 phá dữ liệu và rút ra các 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à kiểm định kết quả 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 các 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á tri Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 6
8. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học thứ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. 1.3. Quá trình khai phá dữ liệu Khai phá dữ liệu là hoạt động trọng tâm của quá trình khám phá tri thức . Thuật ngữ khai phá dữ liệu còn được một số nhà khoa học gọi là phát hiện tri thức trong cơ sở dữ liệu ( knowledge discovery in database _KDD) ( theo Fayyad Smyth and Piatestky- Shapiro 1989). Quá trình này gồm có 6 bước [1]: Hình 1.2. Quá trình khai phá dữ liệu Quá trình khai phá dữ liệu bắt đầu với kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Nội dung của quá trình như sau: 1.3.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. 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 đó. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 7
9. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 1.3.3. Làm sạch và tiền xử lý dữ liệu (cleansing preprocessing). 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à 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.4. Chuyển đổi dữ liệu (transformation) 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.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.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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 8
10. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 1.4. Chức năng của khai phá dữ liệu Khai phá dữ liệu có hai chức năng cơ bản đó là: chức năng dự đoán và chức năng mô tả. 1.5. 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.5.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ữ 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.5.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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 9
11. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 1.5.3. Khai phá luật kết hợp: Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm được. Phương pháp khai phá luật kết hợp gồm có hai bước: - Bước 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến được xác định thông qua tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu. - Bước 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu. 1.5.4. 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.5.5. 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. 1.5.6. Mạng nơron: Đâ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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 10
12. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 1.5.7. 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.6. Các dạng dữ liệu có thể khai phá được - CSDL quan hệ - CSDL đa chiều - CSDL giao dịch - CSDL quan hệ - đối tượng - CSDL không gian và thời gian - CSDL đa phương tiện. 1.7. Các lĩnh vực liên quan đến khai phá dữ liệu và ứng dụng của khai phá dữ liệu 1.7.1. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu được ứng dụng trong nhiều ngành và lĩnh vực khác nhau như: tài chính ngân hàng, thương mại, y tế, giáo dục, thống kê, máy học, trí tuệ nhân tạo, csdl, thuật toán toán học, tính toán song song với tốc độ cao, thu thập cơ sở tri thức cho hệ chuyên gia, 1.7.2. Ứng dụng của khai phá dữ liệu Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu, từ ảnh viễn thám, cảnh báo hỏng hóc trong các hệ thống sản xuất; Được ứng dụng cho việc quy hoạch và phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; Áp dụng cho các vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh Một số ứng dụng cụ thể như sau : Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 11
13. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học - Khai phá dữ liệu được sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định. - Trong sinh học: nó dùng để tìm kiếm , so sánh các hệ gen và thông tin di chuyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di chuyền - Trong y học: khai phá dữ liệu giúp tìm ra mối liên hệ giữa các triệu chứng, chuẩn đoán bệnh. - Tài chính và thị trường chứng khoán: Khai phá dữ liệu để phân tích tình hình tài chính, phân tích đầu tư, phân tích cổ phiếu - Khai thác dữ liệu web. - Trong thông tin kỹ thuật: khai phá dữ liệu dùng để phân tích các sai hỏng, điều khiển và lập lịch trình - Trong thông tin thương mại: dùng để phân tích dữ liệu người dùng, phân tích dữ liệu marketing, phân tích đầu tư, phát hiện các gian lận. 1.8. Các thách thức và hướng phát triển của phát hiện tri thức và khai phá dữ liệu. Sự phát triển của phát hiện tri thức và khai phá dữ liệu gặp phải một số thách thức sau: - CSDL lớn (số lượng bản ghi, số bảng) - Số chiều lớn - Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp nữa. - Dữ liệu bị thiếu hoặc bị nhiễu. - Quan hệ giữa các trường phức tạp - Vấn đề giao tiếp với người sử dụng và kết hợp với các tri thức đã có. - Tích hợp với các hệ thống khác. - Hướng phát triển của khám phá tri thức và khai phá dữ liệu là vượt qua được tất cả những thách thức trên. Chú trọng vào việc mở rộng ứng dụng để đáp ứng cho mọi lĩnh vực trong đời sống xã hội, và tăng tính hữu ích của việc khai phá dữ liệu trong những lĩnh vực đã có khai phá dữ liệu. Tạo ra các phương pháp khai phá dữ liệu linh động, uyển chuyển để xử lý số lượng dữ liệu lớn một cách hiệu quả. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 12
14. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Tạo ra tương tác người sử dụng tốt, giúp người sử dụng tham gia điều khiển quá trình khai phá dữ liệu, định hướng hệ thống khai phá dữ liệu trong việc phát hiện các mẫu đáng quan tâm. Tích hợp khai phá dữ liệu vào trong các hệ cơ sở dữ liệu. Ứng dụng khai phá dữ liệu để khai phá dữ liệu web trực tuyến. Một vấn đề quan trọng trong việc phát triển khám phá tri thức và khai phá dữ liệu đó là vấn đề an toàn và bảo mật thông tin trong khai phá dữ liệu. Chương 2: Khai phá dữ liệu bằng cây quyết định 2.1. Cây quyết định 2.1.1. Định nghĩa cây quyết định 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. [3] Ví dụ: Cây quyết định phân lớp mức lương Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 13
15. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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. Ư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 có một số ưu điểm sau - Cây quyết định tương đối dể hiểu. - Đòi hỏi mức tiền xử lý dữ liệu đơn giản. - Có thể xử lý với cả các dữ liệu rời rạc và liên tục. - Cây quyết định là một mô hình hộp trắng. - Kết quả dự đoán bằng cây quyết định có thể thẩm định lại bằng cách kiểm tra thống kê. 2.1.3. Vấn đề 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á. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 14
16. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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.4. Rút ra các 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 khai phá dữ liệu bằ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 [6]: 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ì: + 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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 15
17. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học + 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) [5] . Entropy [5]: 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 (1) +- 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à 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: Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 16
18. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học n Entropy(S)=  (- Pi2 log (Pi )) (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 Information Gain (viết tắt là Gain)[5]: 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 . n Information(Ai2 ) = - log (pi ) Entropy(S) (2.3) i=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: Sv Gain( S , A ) Information(A) - Entropy(A)= Entropy(S)- Entropy(Sv ) (2.4) 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. Hàm xây dựng cây quyết định trong thuật toán ID3 [2] Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 17
19. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Function induce_tree(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 các ví dụ trong tập_ví_dụ có giá trị V V tại thuộc tính P; Gọi induce_tree(phân_vùng , tập_thuộc_tính), gắn kết quả V vào nhánh V end end end 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 - 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 với việc cho phép xử lý trên tập dữ liệu có các thuộc tính số (numeric atributes) và và làm việc được với tập dữ liệu bị thiếu và bị nhiễu. Nó thực hiện phân lớp tập mẫu dữ liệu theo chiến lược ưu tiên theo chiều sâu (Depth - First). 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 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 18
20. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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: Gain(,) X T GainRation(,) X T (2.5) SplitInfo(X,T) Với: |Tii | |T | Splitinfo(X,T) = - log2 (2.6) i Value(X) |TT | | | 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. Đố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 Thuật toán xây dựng cây quyết định C4.5 Mô tả thuật toán dưới dạng giả mã như sau [5]: Function xay_dung_cay(T) { 1. ; 2. If Then Else ; 3. For Do ; 4. ; 5. If Then ; 6. For Do ( T` được tách ra theo quy tắc: - Nếu N.test là thuộc tính liên tục tách theo ngưỡng ở bước 5 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 19
21. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học - Nếu N.test là thuộc tính phân loại rời rạc tách theo các giá trị của thuộc tính này. ) 7. { If } Then ; Else 8. ; } 9. ; ; } Một số công thức được sử dụng n Ti Infoxi (T)=- *Info(T ) (2.7) i=1 T Gain( X ) Info(T)-InfoX ( T ) (2.8) (2.8) được sử dụng 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ị Gain 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 (2.8) 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 sau: freq(,) C T P j S n Ti Ti SplitInfo (X) =-  log2 (2.9) i=1 T T Gain() X GainRatio() X (2.10) SplitInfo(X) Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 20
22. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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(Cj ,T) freq ( Cj , T ) Info(T) = -  *log2 (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: ||TU Gain( X ) (Info(T)-Info ( T )) (2.13) ||T x 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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 21
23. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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. Qua tìm hiểu trên ta thấy thuật toán C4.5 là cải tiến của thuật toán ID3 2.2.4. Thuật toán SLIQ[5] Thuật toán SLIQ (Supervised Learning In Quest) được gọi là thuật toán phân lớp leo thang nhanh. Thuật toán này có thể áp dụng cho cả hai kiểu thuộc liên tục và thuộc tính rời rạc. Thuật toán này có sử dụng kỹ thuật tiền xử lý phân loại(Pre sorting) trước khi xây dựng cây, do đó giải quyết được vấn đề bộ nhớ cho thuật toán ID3. Thuật toán SLIQ có sử dụng giải thuật cắt tỉa cây hữu hiệu. Thuật toán SLIQ có thể phân lớp rất hiệu quả đối với các tập dữ liệu lớn và không phụ thuộc vào số lượng lớp, số lượng thuộc tính và số lượng mẫu trong tập dữ liệu. Xây dựng cây quyết định theo thuật toán này chia ra làm 2 giai đoạn: 1. Giai đoạn tạo cây  Vào: tập dữ liệu học T  Ra: cây được phân loại trên tập T Hàm MakeTree(TrainningData T) {partition (T) ;} Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 22
24. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 2. Giai đoạn phân chia tập dữ liệu S Thủ tục phân loại tập S có giả mã như sau: Function partition (Data S) { If Then Else{ ; ; ; ; } } Chỉ số chia tách (Spliting index): Vấn đề đặt ra trong thủ tục Partition(S) trên là làm thế nào để đánh giá thuộc tính tốt nhất cho việc lựa chọn thuộc tính để chia tách. Để đánh giá thuộc tính tốt nhất đó, thuật toán SLIQ đưa vào một đại lượng, gọi là chỉ số hàm gini, chỉ số gini được định nghĩa như sau:  Nếu tập dữ liệu T gồm n lớp thì giá trị gini của tập T ký hiệu gini(T) được xác định bởi công thức: 2 gini( T ) 1  p j (2.14) Trong đó pj là tần suất xuất hiện của lớp j trong tập mẫu T.  Nếu tập T được tách ra làm 2 tập con T1 và T2 thì chỉ số gini của tập T khi được chia tách ký hiệu là gini(T)split được xác định bởi công thức sau: TT gini()()() T 12 gini T gini T (2.15) split TT12 Sau khi tính toán chỉ số gini cho các nút, thuộc tính nào có chỉ số gini nhỏ nhất sẽ được chọn để thực hiện tiếp việc triển khai cây. Kỹ thuật tiền xử lý phân loại(Pre_sorting Technique) Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 23
25. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Kỹ thuật này tạo ra một lược đồ, lược đồ này được tạo ra bằng cách sắp xếp dữ liệu tạo ra tại mỗi nút. Ứng với mỗi thuộc tính có một danh sách riêng tạo ra bởi tập giá trị của thuộc tính và định danh các mẫu dữ liệu. Mỗi danh sách riêng gọi là danh sách lớp (class list). Các danh sách riêng sẽ tạo ra tương ứng nhãn của cây gắn với các mẫu học. Thuật toán SLIQ yêu cầu tại một thời điểm có một danh sách lớp và chỉ một danh sách thuộc tính được lưu trữ trong bộ nhớ của máy tính, các danh sách còn lại lưu trên đĩa. Đánh giá sự phân chia: Thuật toán đánh giá phân chia: EvaluateSplits() { For do { ; For do ; ; If Then for do } } Cập nhật danh sách lớp: Thuật toán cập nhật danh sách lớp: UpdateLabels() { for do { ; For do Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 24
26. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học { ; ; ; ; } } } 2.2.5. 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 (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. [3][5][9] 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 đó [5]. b) Hậu cắt tỉa (Postpruning): Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 25
27. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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ó. [5][7] [9] 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) 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[5][8][9] : Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 26
28. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học - 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.6. Đánh giá và kết luận về các thuật toán xây dựng cây quyết định 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 Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 27
29. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học 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ị p hâ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ớ. - Thuật toán SLIQ phân lớp rất có hiệu quả đối với các tập dữ liệu lớn, nó làm việc không phù thuộc vào số lượng các lớp, các thuộc tính và số lượng bản ghi trong tập dữ liệu. SLIQ đã cải thiện được vấn đề về bộ nhớ vì có 3 pha tiền xử lý phân loại, tại một thời điểm chỉ có 1 danh sách lớp thường trú trong bộ nhớ. SLIQ có kỹ thuật cắt tỉa cây mô tả độ dài tối thiểu MDL, rất hữu hiệu . Nó là thuật toán phân lớp nhanh, chính xác, chi phí thấp. Tuy nhiên việc cài đặt phức tạp, áp dụng cho các cơ sở dữ liệu lớn. 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á 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. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 28
30. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Chương 3: Xây dựng chương trình dêmo 3.1. Mô tả bài toán Phương pháp khai phá dữ liệu trong những năm gần đây được ứng dụng trong nhiều lĩnh vực như: thương mại, giáo dục, y tế, bưu chính viễn thông Tuy nhiên, ở Việt Nam phương pháp này còn chưa được áp dụng nhiều, nhất là trong lĩnh vực giáo dục, đào tạo. Vì vậy trong nội dung nghiên cứu khoa học của mình, em đã tiến hành xây dựng chương trình ứng dụng khai phá dữ liệu trong giáo dục đào tạo. Cụ thể là ứng dụng khai phá dữ liệu Trường đại học sư phạm Hà Nội. Bài toán như sau: "Sử dụng các thông tin: Khu vực sống, thành phần gia đình, học lực 4 năm đại học, điểm thi đầu vào của sinh viên để dự đoán xếp loại tốt nghiệp đại học của sinh viên." 3.2. Thu thập và tiền xử lý dữ liệu Dữ liệu mà em thu thập được lấy kho dữ liệu của Trường đại học sư phạm Hà Nội. Sau khi đã có được toàn bộ các dữ liệu, em tiến hành trích lọc ra những thông tin cần thiết cho bài toán ứng dụng của em. Dữ liệu thu thập được ở dạng file access như sau: Tiền xử lý dữ liệu: do một số lý do nào đó, trong bảng dữ liệu về sinh viên, có một số ô không có giá trị. Vì vậy, em tiến hành bước tiền xử lý dữ liệu: dùng giá trị dữ liệu thông dụng nhất cho các thuộc tính mà có giá trị bị thiếu để điền vào các ô dữ liệu bị để trống đó. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 29
31. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học Sau đó, do em dự tính dùng tool dtree (dtree làm việc với dữ liệu dạng file text ) để xây dựng cây quyết định, vì vậy em tiến hành xử lý , export dữ liệu từ access ra file text. 3.3. Chương trình - Đầu vào: dữ liệu phẳng (dạng file text) chứa các thông tin được sử dụng trong mô tả bài toán. - Đầu ra: đầu ra của cây là file text chứa các luật dự đoán xếp loại tốt nghiệp của sinh viên dựa vào các thông tin đầu vào. . Chương 4. KẾT LUẬN 4.1 Đánh Giá Qua quá trình nghiên cứu và tìm hiểu về các vấn đề liên quan tới data mining và cơ bản hoàn thành đề tài và đạt được một số kết quả như sau: 4.1.1 Lý thuyết - Tìm được nhiều tài liệu hay và bổ ích liên quan tới data mining - Nắm được một số kỹ thuật cơ bản để khai phá dữ liệu, các chức năng và ứng dụng của khai phá dữ liệu. - Nắm được kỹ thuật khai phá dữ liệu bằng cây quyết định, các thuật toán xây dựng cây quyết định. 4.1.2 Ứng dụng - Xây dựng chương trình demo cho ứng dụng khai phá dữ liệu bằng cây quyết định. Sử dụng cây quyết định để dự đoán xếp loại tốt nghiệp đại học của sinh viên. 4.2 Hướng Phát Triển - Nghiên cứu thêm một số thuật toán mới về khai phá dữ liệu bằng cây quyết đinh, tìm hiểu kỹ hơn về các kỹ thuật khai phá dữ liệu khác. - Xây dựng được những chương trình ứng dụng phức tạp và có tính thực tế hơn bằng cây quyết định. Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 30
32. Trường đại học sư phạm Hà Nội Sinh viên nghiên cứu khoa học TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] PGS.TS. Đỗ Phúc, Bài giảng khai thác dữ liệu, Đại học Quốc gia TP. Hồ Chí Minh, 2007 [2] Võ Huỳnh Tâm - Trần Ngân Bình, "Giáo trình trí tuệ nhân tạo", Chương 9 Học máy, Nhà xuất bản: Đại học Cần Thơ. [3] Wikipedia - Bách khoa toàn thư mở - Cây quyết định. tree Tài liệu tiếng Anh [4] Introduction to Knowledge Discovery and Data Mining, Institute of Information Technology [5] Jaiwei Han and Micheline Kamber, Data Mining: Concepts and Techniques (2001), ISBN 1-55860-489-8. [6] Knowledge Discovery in Databases. G.piatetsky - Shapiro and W.J. Frawley. AAAI/MIT Press, 1991. [7] Knowledge Discovery Nuggets: [8] Slide Learning from Data: Decision trees, Amos Storkey, School of Informatics university of Edinburgh, Semester 1, 2004 [9] Thomas, Data mining: Definittions and decision tree examples, State university of New York Sinh viên: Nguyễn Thị Hạnh – Lớp: C-K54-CNTT 31