Luận văn Thạc sĩ Công nghệ thông tin: Sử dụng cây quyết định phân lớp dữ liệu mất cân đối

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

Thêm vào BST

Báo xấu

91
lượt xem 10
download

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

Luận văn "Sử dụng cây quyết định phân lớp dữ liệu mất cân đối" được thực hiện với mục tiêu chính như thách thức của bài toán phân lớp dữ liệu mất cân đối là vấn đề về đối tượng cần quan tâm nghiên cứu lại có rất ít mẫu - mẫu lớp thiểu số so với các lớp khác trong tập dữ liệu - mẫu lớp đa số.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Sử dụng cây quyết định phân lớp dữ liệu mất cân đối

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC THÀNH PHỐ HỒ CHÍ MINH LÊ THANH PHONG SỬ DỤNG CÂY QUYẾT ĐỊNH PHÂN LỚP DỮ LIỆU MẤT CÂN ĐỐI LUẬN VĂN THẠC SỸ NGÀNH CÔNG NGHỆ THÔNG TIN Mã số: 60 48 02 01 TP. HCM, THÁNG 10 NĂM 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC NGOẠI NGỮ TIN HỌC THÀNH PHỐ HỒ CHÍ MINH LÊ THANH PHONG SỬ DỤNG CÂY QUYẾT ĐỊNH PHÂN LỚP DỮ LIỆU MẤT CÂN ĐỐI LUẬN VĂN THẠC SỸ Ngành: CÔNG NGHỆ THÔNG TIN Mã số: 60 48 02 01 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. LÊ HOÀI BẮC TP. HCM, THÁNG 10 NĂM 2018
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC THÀNH PHỐ HỒ CHÍ MINH Người hướng dẫn khoa học: PGS. TS. Lê Hoài Bắc - Học viên đã bảo vệ thành công luận văn ngày 04 tháng 06 năm 2019, tại Hội đồng đánh giá luận văn thạc sĩ thành lập theo Quyết định số …. ngày …. /…./2019 của Hiệu trưởng Trường ĐH Ngoại ngữ -Tin học TP.HCM, với sự tham gia của: Chủ tịch Hội đồng: PGS.TS. Phạm Thế Bảo Phản biện 1: TS. Trần Minh Thái Phản biện 2: TS. Đặng Trường Sơn Ủy viên: PGS.TS Nguyễn Thanh Bình Thư ký: TS. Nguyễn Đức Cường - Có thể tìm hiểu Luận văn tại Thư viện của Trường ĐH Ngoại ngữ - Tin học TPHCM, hoặc trên cổng thông tin điện tử, website của đơn vị quản lý sau đại học của Trường.
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. TPHCM, ngày 25 tháng 10 năm 2018 Tác giả luận văn Lê Thanh Phong
LỜI CẢM ƠN Lời đầu tôi xin chân thành cảm ơn PGS. TS. Lê Hoài Bắc đã tận tình hướng dẫn cũng như cung cấp tài liệu thông tin khoa học cần thiết cho luận văn này. Xin chân thành cảm ơn Lãnh đạo trường Đại học Ngoại ngữ Tin học Thành Phố Hồ Chí Minh, Ban Sau Đại Học, Khoa Công Nghệ Thông Tin đã tạo điều kiện cho tôi hoàn thành tốt công việc nghiên cứu khoa học của mình. Cuối cùng, tôi xin chân thành cảm ơn đến gia đình, các anh chị và các bạn đồng nghiệp, đơn vị công tác đã hỗ trợ cho tôi rất nhiều trong suốt quá trình học tập, nghiên cứu và thực hiện đề tài luận văn thạc sĩ một cách hoàn chỉnh. Tôi xin chân thành cảm ơn! Tác giả Lê Thanh Phong
DANH MỤC VIẾT TẮT STT Từ viết tắt Ý nghĩa 1 AUC Area Under the ROC Curve 2 CLS Concept Learning System 3 CSC4.5 Cost-Sensitive C4.5 4 CSDL Cơ Sở Dữ Liệu 5 FN False Negative 6 FP False Positive 7 FPR False Positive Rate 8 ID3 Interactive Dichotomizer 3 9 ILA Inductive Learning Algorithm 10 KTDL Khai Thác Dữ Liệu 11 MDL Minimum Description Length 12 NB Naïve Bayes 13 ROC Receiver Operating Characteristic 14 SC4.5 Standard C4.5 15 SQL Structured Query Language 16 TN True Negative 17 TP True Positive 18 TPR True Positive Rate 19 UCI University of California Irvine (Machine Learning Repository) i
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 2-1: Quá trình khai thác dữ liệu ........................................................................................ 7 Hình 2-3: Quá trình phân lớp dữ liệu - Bước xây dựng mô hình phân lớp ............................... 9 Hình 2-4: Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình.............................. 10 Hình 2-5: Quá trình phân lớp dữ liệu – Phân lớp dữ liệu mới ................................................. 11 Hình 2-6: Mô hình ứng dụng luật ............................................................................................ 15 Hình 2-7: Phương pháp Holdout.............................................................................................. 28 Hình 2-8: K-Fold Coss–Validation .......................................................................................... 29 Hình 3-1: Đồ thị ROC biểu diển một bộ phân lớp rời rạc của xác suất B ............................... 30 Hình 3-2: AUC – diện tích dưới đường cong ROC của một bộ phân lớp A ........................... 31 Hình 3-3: Cây quyết định với thuật toán C4.5 bằng cách giảm nhiều impurity ...................... 40 Hình 3-4: Cây quyết định với thuật toán AUC4.5 bằng cách gia tăng giá trị AUC ................ 43 Hình 4-1: Đồ thị so sánh kết quả AUCmean của tập DTest ......................................................... 47 ii
DANH MỤC CÁC BẢNG BIỂU Bảng 3-1: Ma trận nhầm lẫn ..................................................................................................... 32 Bảng 3-2: Mô tả tập dữ liệu mất cân đối. ................................................................................. 39 Bảng 4-1: Tập dữ liệu với số phần tử lớp thiểu số.................................................................... 44 Bảng 4-2: Phương sai, độ lệch chuẩn trên toàn bộ các tập dữ liệu ........................................... 45 Bảng 4-3: Kết quả thực nghiệm trên tập DTest qua 10 lần kiểm tra. ....................................... 46 Bảng 4-4: Bảng kết quả 10 lần test trên tập dữ liệu Wine Quality – Red................................. 48 Bảng 4-5: Kết quả tập dữ liệu Wine Quality – Red .................................................................. 48 Bảng 4-6: Bảng kết quả 10 lần test trên tập dữ liệu Nursery .................................................... 49 Bảng 4-7: Kết quả tập dữ liệu Nursery ..................................................................................... 49 Bảng 4-8: Bảng kết quả 10 lần test trên tập dữ liệu Car Evaluation......................................... 50 Bảng 4-9: Kết quả tập dữ liệu Car Evaluation .......................................................................... 50 Bảng 4-10: Bảng kết quả 10 lần test trên tập dữ liệu Ecoli ...................................................... 50 Bảng 4-11: Kết quả tập dữ liệu Ecoli ....................................................................................... 51 Bảng 4-12: Bảng kết quả 10 lần test trên tập dữ liệu Mushroom ............................................. 51 Bảng 4-13: Kết quả tập dữ liệu Mushroom .............................................................................. 52 Bảng 4-14: Bảng kết quả 10 lần test trên tập dữ liệu Wine Quality – White ........................... 52 Bảng 4-15: Kết quả tập dữ liệu Wine Quality – White ............................................................ 53 Bảng 4-16: Bảng kết quả 10 lần test trên tập dữ liệu Contraceptive Method Choice............... 53 Bảng 4-17: Kết quả tập dữ liệu Contraceptive Method Choice ................................................ 54 Bảng 4-18: Bảng kết quả 10 lần test trên tập dữ liệu Tic-Tac-Toe Endgame .......................... 54 Bảng 4-19: Kết quả tập dữ liệu Tic-Tac-Toe Endgame ............................................................ 54 iii
MỤC LỤC DANH MỤC VIẾT TẮT .................................................................................................. i DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..........................................................................ii DANH MỤC CÁC BẢNG BIỂU .................................................................................. iii MỤC LỤC .................................................................................................................iv CHƯƠNG 1. TỔNG QUAN .......................................................................................... 1 1.1 Đặt vấn đề ....................................................................................................... 1 1.2 Cơ sở hình thành đề tài ................................................................................... 1 1.3 Các nghiên cứu liên quan ............................................................................... 2 1.4 Mục tiêu của luận văn ..................................................................................... 3 1.5 Đối tượng nghiên cứu ..................................................................................... 4 1.6 Các phương pháp nghiên cứu ......................................................................... 4 1.6.1 Phương pháp nghiên cứu tài liệu ....................................................... 4 1.6.2 Phương pháp thực nghiệm ................................................................. 4 1.6.3 Phương pháp thống kê, phân tích dữ liệu .......................................... 5 1.7 Nội dung và phạm vi của luận văn ................................................................. 5 1.8 Ý nghĩa của luận văn ...................................................................................... 5 1.8.1 Ý nghĩa khoa học ............................................................................... 5 1.8.2 Ý nghĩa thực tiễn ............................................................................... 5 1.9 Bố cục luận văn .............................................................................................. 6 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT ............................................................................... 7 2.1 Tổng quan về khai thác dữ liệu....................................................................... 7 iv
2.1.1 Khai thác dữ liệu là gì? ...................................................................... 7 2.1.2 Quá trình khai thác dữ liệu ................................................................ 7 2.1.3 Khai thác dữ liệu sử dụng phân lớp ................................................... 9 2.1.4 Khai thác dữ liệu sử dụng luật kết hợp ............................................ 14 2.1.5 Khai thác dữ liệu sử dụng cây quyết định ....................................... 15 CHƯƠNG 3. PHÂN LỚP DỮ LIỆU MẤT CÂN ĐỐI BẰNG CÂY QUYẾT ĐỊNH 30 3.1 Đường cong Receiver Operating Characteristic (ROC) ............................... 30 3.2 Diện tích dưới đường cong ROC .................................................................. 31 3.3 Độ đo đánh giá hiệu suất phân lớp ............................................................... 31 3.4 Thuật toán AUC4.5....................................................................................... 33 3.4.1 Ý tưởng chính thuật toán AUC4.5................................................... 33 3.4.2 Một số giải thuật chính .................................................................... 34 3.5 Ví dụ minh hoạ cho thuật toán AUC4.5 ....................................................... 39 3.5.1 Dữ liệu minh hoạ ............................................................................. 39 3.5.2 Minh hoạ bằng thuật toán C4.5 ....................................................... 40 3.5.3 Minh hoạ bằng thuật toán AUC4.5.................................................. 41 CHƯƠNG 4. THỰC NGHIỆM VÀ ĐÁNH GIÁ ........................................................ 44 4.1 Mô tả tập dữ liệu ........................................................................................... 44 4.2 Môi trường thực nghiệm ............................................................................... 44 4.3 Kiểm chứng mô hình bằng phương pháp Hold-out ...................................... 45 4.4 Kết quả thực nghiệm ..................................................................................... 45 4.4.1 Phương sai, độ lệch chuẩn ............................................................... 45 v
4.4.2 Kết quả tám tập dữ liệu sau khi kiểm tra tập DTest 10 lần. ............... 46 4.4.3 Phân tích trên từng tập dữ liệu......................................................... 48 4.5 Đánh giá kết quả thực nghiệm ...................................................................... 55 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................. 57 TÀI LIỆU THAM KHẢO .............................................................................................. 58 vi
TỔNG QUAN CHƯƠNG 1. TỔNG QUAN 1.1 Đặt vấn đề Trong những năm qua, nhiều mô hình phân lớp dữ liệu đã được các nhà khoa học trong nhiều lĩnh vực khác nhau đề xuất như mạng nơ ron, mô hình thông kê tuyến tính, cây quyết định, mô hình di truyền. Trong số những mô hình đó, cây quyết định [1] với những ưu điểm của mình được đánh giá là một công cụ mạnh, phổ biến và đặc biệt thích hợp cho khai thác dữ liệu (KTDL) nói chung và phân lớp dữ liệu nói riêng [2]. Có thể kể ra những ưu điểm của cây quyết định như: xây dựng tương đối nhanh; đơn giản, dễ hiểu. Cuối cùng, việc phân lớp dựa trên cây quyết định đạt được sự tương tự và đôi khi là chính xác hơn so với các phương pháp phân lớp khác [2][3]. 1.2 Cơ sở hình thành đề tài Dữ liệu thu được trong các ứng dụng thực tế thường là các tập dữ liệu mất cân đối (imbalanced datasets) [4]. Tập dữ liệu mất cân đối thường xuất hiện trong các lĩnh vực như: chẩn đoán y tế [5], phát hiện ung thư bằng xét nghiệm nhũ ảnh [6], phát hiện thư rác trong các giao dịch thư điện tử [7], phát hiện thâm nhập hệ thống [8]… Trong những vấn đề về phân lớp, đối tượng cần quan tâm nghiên cứu lại có rất ít mẫu - mẫu lớp thiểu số (minority class instances) so với các lớp khác trong tập dữ liệu - mẫu lớp đa số (majority class instances). Cụ thể, lớp bệnh nhân có rất ít mẫu so với các lớp khác trong ứng dụng y học, giao dịch tấn công có rất ít mẫu so với các lớp giao dịch khác của hệ thống mạng. Những ví dụ mà thực tế gặp phải vấn đề mất cân đối dữ liệu và việc chẩn đoán đúng nhãn (hay phân lớp chính xác, dự đoán chính xác) của mẫu thuộc lớp thiểu số là cần thiết và đóng vai trò quan trọng. Tuy nhiên, nếu áp dụng các kỹ thuật phân lớp truyền thống như hồi quy logistic, cây quyết định, máy hỗ trợ vector, đối với các bộ phân lớp được huấn luyện để mà tối ưu độ chính xác tổng thể (overall accuracy) và được áp dụng trên tập dữ liệu mất cân đối có xu hướng trả về kết quả dự đoán cao trên lớp đa số và dự đoán kém trên lớp thiểu số. Ví dụ: với một tập dữ liệu có 10.000 mẫu, trong đó lớp đa số có số mẫu là 9.900 mẫu, lớp thiểu số có số mẫu là 100 mẫu. Nếu dựa vào nguyên tắc số đông gán nhãn cho mẫu trong tập mất cân đối thì độ chính xác khi phân loại trên tập dữ liệu dễ dàng đạt tới xấp xỉ 99% trong khi độ chính 1
TỔNG QUAN xác của lớp nhỏ xấp xỉ 0%. Tuy nhiên, điều này không thể chứng minh được bộ phân lớp đã làm việc rất chính xác. Vì vậy, vấn đề đặt ra là cần có những phương pháp tiếp cận riêng cho những bài toán phân lớp có dữ liệu mất cân đối để dự đoán chính xác mẫu lớp thiểu số. 1.3 Các nghiên cứu liên quan Có nhiều nghiên cứu đã cố gắng đưa ra những giải thuật tốt hơn cho phân lớp dữ liệu mất cân đối. Để giải quyết bài toán phân lớp dữ liệu mất cân đối, có hai hướng tiếp cận chủ yếu:  Tiếp cận ở mức độ dữ liệu Những nỗ lực này nhằm mục đích thay đổi lại kích thước tập huấn để việc phân bố lớp có thể được cân đối. Nghĩa là điều chỉnh phân bố dữ liệu của các lớp sao cho giảm bớt hoặc không còn tính mất cân đối để đưa vào áp dụng các thuật toán phân lớp chuẩn. Có nhiều cách điều chỉnh dữ liệu khác nhau như: phương pháp Under-sampling [9] giảm phần tử ở lớp đa số để làm giảm tính mất cân đối dữ liệu. Cách đơn giản nhất đó là loại bỏ các phần tử ở lớp đa số một cách ngẫu nhiên. Dựa trên kỹ thuật under-sampling, nhóm tác giả trong bài báo [10] đưa ra các tiếp cận lấy mẫu dựa trên cụm. Cách tiếp cận đầu tiên là tập hợp tất cả các mẫu huấn luyện vào một số cụm. Nếu một cụm có mẫu lớp đa số nhiều hơn các mẫu lớp thiểu số, nó sẽ hoạt động giống như các mẫu lớp đa số. Mặt khác, nếu một cụm có mẫu lớp thiểu số nhiều hơn các mẫu lớp đa số, nó hoạt động giống như các mẫu lớp thiểu số. Trong khi đó, với thuật toán Random Border Undersampling [11], làm giảm phần tử ngẫu nhiên trên đường biên trong dữ liệu mất cân đối. Thuật toán được cải tiến dựa trên thuật toán Under-sampling [9]. Kỹ thuật under-sampling tuy tốn ít chi phí về thời gian cũng như bộ nhớ cho quá trình phân lớp nhưng lại dễ làm mất các thông tin quan trọng của lớp đa số. Một phương pháp khác là Over-sampling [12] điều chỉnh tăng kích thước mẫu, cụ thể tăng phần tử ở lớp thiểu số, bằng cách chọn ngẫu nhiên các phần tử lớp thiểu số sau đó sao chép giống hệt để làm tăng kích thước lớp thiểu số, làm cho dữ liệu cân bằng hơn. Tuy nhiên nhược điểm là tăng kích thước tập dữ liệu huấn luyện, thời gian huấn luyện tăng lên, dễ quá khớp. Để giải quyết vấn đề của phương pháp Over-sampling, phương pháp SMOTE [13] điều chỉnh dữ liệu bằng cách với mỗi phần tử lớp thiểu số thực hiện sinh thêm các phần tử nhân tạo giữa phần tử này với các láng giềng của nó. Nhóm tác giả trong bài báo [14] đã đề xuất phương pháp 2
TỔNG QUAN Borderline-SMOTE cải tiến từ SMOTE. Phương pháp Borderline-SMOTE chỉ thực hiện sinh thêm phần tử lớp thiểu số nằm ở được biên của tập dữ liệu. Theo Borderline-SMOTE, những phần tử lớp thiểu số nằm ở đường biên thì dễ phân sai lớp hơn những phần tử lớp thiểu số nằm ở xa đường biên.  Tiếp cận ở mức độ thuật toán Với cách tiếp cận ở mức độ dữ liệu, phương pháp lấy mẫu cố gắng cân bằng việc phân bố bằng cách xem xét tỷ lệ đại diện của các mẫu trong phân bố dữ liệu. Còn với cách tiếp cận ở mức độ thuật toán, các giải pháp bao gồm điều chỉnh chi phí của các lớp khác nhau để chống lại sự mất cân đối của lớp. Học với chi phí nhạy cảm (Cost-sensitive learning) [15] là một loại học trong khai thác dữ liệu có xem xét tính đến chi phí phân loại sai (misclassification cost). Bằng cách gán các chi phí khác đến các lớp thiểu số và đa số, các bộ phân lớp với học chi phí nhạy cảm nói chung gia tăng chính xác dự đoán cho lớp thiểu số. Có rất nhiều cách để thực hiện nghiên cứu học với chi phí nhạy cảm [4]: dùng chi phí nhạy cảm làm tiêu chí tách (splitting criteria) và phù hợp với phương pháp cắt tỉa (pruning methods) [16]. Một số bộ phân lớp thuộc loại quần thể (classifier ensembles) như AdaCost [17], AdaC1, AdaC2, và AdaC3 [18], The DataBoost-IM [19], Marcus A. Maloof (2003) [20] dùng chi phí của phân loại sai để cập nhật việc đào tạo phân bổ việc huấn luyện vào vòng tăng kế tiếp. Giảm bớt phần trên của chi phí phân loại sai của tập huấn luyện. Tuy nhiên, cả hai cách tiếp cận trên đều không có vấn đề, nhưng khi lấy mẫu lại vẫn còn những sự không chính xác liên quan đến việc xác định tỷ lệ lấy mẫu, và trong các phương pháp học nhạy cảm với chi phí, việc tính toán chi phí phân loại sai vẫn là vấn đề cần xem xét. 1.4 Mục tiêu của luận văn Thách thức của bài toán phân lớp dữ liệu mất cân đối là vấn đề về đối tượng cần quan tâm nghiên cứu lại có rất ít mẫu - mẫu lớp thiểu số so với các lớp khác trong tập dữ liệu - mẫu lớp đa số. Bài toán phân lớp dữ liệu mất cân đối dựa trên cây quyết định là phương pháp sử dụng học máy để phân lớp, việc nâng cao dự đoán chính xác mẫu lớp thiểu số là một vấn đề rất cần thiết và có 3
TỔNG QUAN ý nghĩa khoa học rất cao. Do đó, cần phải có tiêu chí tách và phương pháp cắt tỉa khi áp dụng trên cây quyết định là những vấn đề cần được nghiên cứu, cải tiến để dự đoán chính xác mẫu lớp thiểu số, góp phần nâng cao hiệu quả khai thác và phân lớp dữ liệu mất cân đối. Với những vấn đề nêu trên, người nghiên cứu nhận thấy rằng rất cần thiết về lý luận và thực tiễn để tập trung nghiên cứu và đề xuất phương pháp cải tiến nhằm góp phần giải quyết các vấn đề còn tồn đọng của bài toán sử dụng cây quyết định phân lớp cho dữ liệu mất cân đối, từ đó phát triển một số hướng nghiên cứu liên quan tiếp theo cho mảng phân lớp này. 1.5 Đối tượng nghiên cứu Thuật toán được đề cập dưới đây được đặt tên là AUC4.5, thay đổi và phát triển dựa trên thuật toán C4.5 [21] bằng cách sử dụng giá trị AUC (Area Under the ROC (Receiver Operating Characteristic) Curve) [22] thay cho Gain-entropy để phân lớp dữ liệu mất cân đối cho cả hai mục đích đó là: Mục tiêu học và độ đo đánh giá. 1.6 Các phương pháp nghiên cứu 1.6.1 Phương pháp nghiên cứu tài liệu - Nghiên cứu các tài liệu, bài báo liên quan là cơ sở lý luận của luận văn. - Nghiên cứu các cách tiếp cận, các kỹ thuật, các phương pháp, hiện trạng đã được công bố của các tác giả trong và ngoài nước có liên quan đến lĩnh vực sử dụng cây quyết định phân lớp dữ liệu mất cân đối nói riêng và lĩnh vực phân lớp trong khai thác dữ liệu nói chung. - Nghiên cứu các xu thế và hướng phát triển tương lai liên quan đến luận văn. - Nghiên cứu các tài liệu liên quan, phục vụ cho việc nghiên cứu của luận văn. 1.6.2 Phương pháp thực nghiệm Tiến hành hiện thực và thực nghiệm các phương pháp được đề xuất trong luận văn để xác định tính đúng đắn, khả thi và phát triển so với các phương pháp đã công bố của các tác giả trong và ngoài nước có liên quan đến luận văn. 4
TỔNG QUAN 1.6.3 Phương pháp thống kê, phân tích dữ liệu Thống kê, tổng hợp các số liệu trong quá trình thực nghiệm để từ đó phân tích, đánh giá và đưa ra những kết luận hoặc điều chỉnh nội dung nghiên cứu. 1.7 Nội dung và phạm vi của luận văn Nội dung và phạm vi nghiên cứu của luận văn - Tìm hiểu các kiến thức nền tảng về khai thác dữ liệu, phân lớp trong khai thác dữ liệu, cây quyết định, tập dữ liệu mất cân đối, thuật toán gốc của cây quyết đinh C4.5 và các cải tiến của AUC4.5. - Tiếp sau đó người nghiên cứu sẽ tiến hành hiện thực thuật toán cải tiến từ thuật toán C4.5, đó là thuật toán AUC4.5. So sánh kết qủa thực nghiệm từ thuật toán AUC4.5 với C4.5 1.8 Ý nghĩa của luận văn 1.8.1 Ý nghĩa khoa học Bài toán phân lớp dữ liệu mất cân đối dựa trên cây quyết định là phương pháp sử dụng học máy để phân lớp, việc nâng cao dự đoán chính xác mẫu lớp thiểu số là một vấn đề rất cần thiết và có ý nghĩa khoa học rất cao. Do đó, cần phải có tiêu chí tách và phương pháp cắt tỉa khi áp dụng trên cây quyết định là những vấn đề cần được nghiên cứu, cải tiến để dự đoán chính xác mẫu lớp thiểu số, góp phần nâng cao hiệu quả khai thác và phân lớp dữ liệu mất cân đối. 1.8.2 Ý nghĩa thực tiễn Mục đích cuối cùng của quá trình khai thác dữ liệu đó là khả năng ứng dụng các kết quả vào trong thực tế. Cây quyết định có một ưu thế rất lớn là luật sinh ra đơn giản dễ hiểu và kết quả được ứng dụng rất nhiều trong các hệ thống ra quyết định. Thế nhưng dùng cây quyết định để phân lớp dữ liệu mất cân đối thì kết quả không chính xác. Do vậy, cần nghiên cứu và thay đổi tiêu chí tách và phương pháp cắt tỉa để dự báo chính xác tập dữ liệu mất cân đối. Cho nên, bài toán sử dụng cây quyết định phân lớp tập dữ liệu mất cân đối cần được quan tâm và tiếp tục 5
TỔNG QUAN nghiên cứu hơn nữa để đóng góp về mặt lý luận cho lĩnh vực phân lớp nói riêng và lĩnh vực khai thác dữ liệu và khám phá tri thức nói chung. 1.9 Bố cục luận văn Luận văn bao gồm các phần sau: Chương 1: Tổng quan Giới thiệu về những vấn đề liên quan đến phân lớp dữ liệu trong khai thác dữ liệu, Cơ sở hình thành đề tài, Các nghiên cứu liên quan, Mục tiêu của luận văn, Đối tượng nghiên cứu, Các phương pháp nghiên cứu, Nội dung và phạm vi nghiên cứu, Ý nghĩa của luận văn và Bố cục luận văn. Chương 2: Cơ sở lý thuyết Giới thiệu cách tiếp cận và giải quyết vấn đề của luận văn. Trình bày cơ sở toán học và áp dụng lý thuyết vào bài toán. Chương 3: Thuật toán phân lớp dữ liệu mất cân đối bằng cây quyết định Trong chương này trình bày cách tiếp cận mới trong phân lớp dữ liệu mất cân đối bằng cây quyết định bằng cách thay đổi và cải tiến thuật toán C4.5. Chương 4: Thực nghiệm và đánh giá. Thực nghiệm chương trình với tập dữ liệu huấn luyện. Kiểm nghiệm đánh giá chương trình với tập dữ liệu kiểm tra. Chương 5: Kết luận và hướng phát triển Ý nghĩa thực tiễn, những hạn chế và hướng phát triển của luận văn. 6
CƠ SỞ LÝ THUYẾT CHƯƠNG 2. CƠ SỞ LÝ THUYẾT 2.1 Tổng quan về khai thác dữ liệu 2.1.1 Khai thác dữ liệu là gì? Khai thác dữ liệu là một khái niệm ra đời vào cuối những năm 1980. Nó là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu (CSDL) và có thể xem như là một bước trong quá trình khám phá tri thức. KTDL là giai đoạn quan trọng nhất trong tiến trình khai thác tri thức từ CSDL, các tri thức này hỗ trợ trong việc ra quyết định trong các lĩnh vực như: khoa học, giáo dục, kinh doanh, … Năm 1989 Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ CSDL trong đó KTDL là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu. KTDL là quá trình phát hiện các mô hình, các tổng kết khác nhau và các giá trị được lấy từ tập dữ liệu cho trước. Hay, KTDL là sự thăm dò và phân tích lượng dữ liệu lớn để khám phá từ dữ liệu ra các mẫu hợp lệ, mới lạ, có ích và có thể hiểu được. 2.1.2 Quá trình khai thác dữ liệu Hình 2-1: Quá trình khai thác dữ liệu 7
CƠ SỞ LÝ THUYẾT Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,…  Tập hợp dữ liệu Đây là giai đoạn đầu tiên trong quá trình KTDL. Giai đoạn này lấy dữ liệu trong một CSDL, một kho dữ liệu và dữ liệu từ các nguồn Internet.  Trích lọc dữ liệu Giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó.  Tiền xử lý và chuẩn bị dữ liệu Giai đoạn này rất quan trọng trong quá trình KTDL. Một số lỗi thường mắc phải trong khi thu thập dữ liệu như thiếu thông tin, không logic... 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. Giai đoạn này tiến hành xử lý những dạng dữ liệu nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Vì vậy, đây là một giai đoạn rất quan trọng vì dữ liệu này nếu không được làm sạch - tiền xử lý - chuẩn bị trước thì sẽ gây nên những kết quả sai lệch nghiêm trọng trong KTDL.  Chuyển đổi dữ liệu Giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó. Dữ liệu đã được chuyển đổi phù hợp với mục đích khai thác.  Khai thác dữ liệu Giai đoạn mang tính tư duy trong KTDL. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để xuất ra các mẫu từ dữ liệu. Thuật toán thường dùng là thuật toán phân loại dữ liệu, kết hợp dữ liệu hoặc các mô hình hóa dữ liệu tuần tự.  Đánh giá kết quả mẫu Giai đoạn cuối trong quá trình KTDL. Trong giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm KTDL. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị 8
CƠ SỞ LÝ THUYẾT sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để đưa ra các tri thức cần thiết và sử dụng được. 2.1.3 Khai thác dữ liệu sử dụng phân lớp 2.1.3.1 Phân lớp dữ liệu Phân lớp dữ liệu là một quá trình gồm hai bước  Bước thứ nhất – bước học. Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các khái niệm định trước. Đầu vào của quá trình này là một tập dữ liệu có cấu trúc được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu, có thể là các mẫu. Trong tập dữ liệu này, mỗi phần tử dữ liệu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính phân lớp. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng if-then, cây quyết định,... Quá trình này được mô tả như trong hình 2-2. Hình 2-2: Quá trình phân lớp dữ liệu - Bước xây dựng mô hình phân lớp 9