Sử dụng cây quyết định phân lớp dữ liệu mất cân đối

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

Có thể bạn quan tâm!

Xem toàn bộ 81 trang tài liệu này.

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

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

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

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

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

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ố.

ý 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.

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