Thạc Sĩ Nghiên cứu các thuật toán phân lớp dữ liệu dựa trên cây quyết định

TÓM TẮT NỘI DUNG

Phân lớp dữ liệu là một trong những hướng nghiên cứu chính của khai phá dữ
liệu. Công nghệ này đã, đang và sẽ có nhiều ứng dụng trong các lĩnh vực thương mại,
ngân hàng, y tế, giáo dục Trong các mô hình phân lớp đã được đề xuất, cây quyết
định được coi là công cụ mạnh, phổ biến và đặc biệt thích hợp với các ứng dụng khai
phá dữ liệu. Thuật toán phân lớp là nhân tố trung tâm trong một mô hình phân lớp.
Khóa luận đã nghiên cứu vấn đề phân lớp dữ liệu dựa trên cây quyết định. Từ
đó tập trung vào phân tích, đánh giá, so sánh hai thuật toán tiêu biểu cho hai phạm vi
ứng dụng khác nhau là C4.5 và SPRINT. Với các chiến lược riêng về lựa chọn thuộc
tính phát triển, cách thức lưu trữ phân chia dữ liệu, và một số đặc điểm khác, C4.5 là
thuật toán phổ biến nhất khi phân lớp tập dữ liệu vừa và nhỏ, SPRINT là thuật toán
tiêu biểu áp dụng cho những tập dữ liệu có kích thước cực lớn. Khóa luận đã chạy thử
nghiệm mô hình phân lớp C4.5 với tập dữ liệu thực và thu được một số kết quả phân
lớp có ý nghĩa thực tiễn cao, đồng thời đánh giá được hiệu năng của mô hình phân lớp
C4.5. Trên cơ sở nghiên cứu lý thuyết và quá trình thực nghiệm, khóa luận đã đề xuất
một số cải tiến mô hình phân lớp C4.5 và tiến tới cài đặt SPRINT.

MỤC LỤC
TÓM TẮT NỘI DUNG i
LỜI CẢM ƠN . ii
MỤC LỤC . . iii
DANH MỤC BIỂU ĐỒ HÌNH VẼ .v
DANH MỤC THUẬT NGỮ vii
ĐẶT VẤN ĐỀ . 1
Chương 1. TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT
ĐỊNH . 3
1.1. Tổng quan về phân lớp dữ liệu trong data mining 3
1.1.1. Phân lớp dữ liệu 3
1.1.2. Các vấn đề liên quan đến phân lớp dữ liệu .6
1.1.3. Các phương pháp đánh giá độ chính xác của mô hình phân lớp 8
1.2. Cây quyết định ứng dụng trong phân lớp dữ liệu .9
1.2.1. Định nghĩa 9
1.2.2. Các vấn đề trong khai phá dữ liệu sử dụng cây quyết định 10
1.2.3. Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu .11
1.2.4. Xây dựng cây quyết định . .13
1.3. Thuật toán Xây dựng cây quyết định . 14
1.3.1. Tư tưởng chung 14
1.3.2. Tình hình nghiên cứu các thuật toán hiện nay . .15
1.3.3. Song song hóa thuật toán phân lớp dựa trên cây quyết định tuần tự 17
Chương 2. C4.5 VÀ SPRINT 21
2.1. Giới thiệu chung .21
2.2. Thuật toán C4.5 .21
2.2.1. C4.5 dùng Gain-entropy làm độ đo lựa chọn thuộc tính “tốt nhất” 22
2.2.2. C4.5 có cơ chế riêng trong xử lý những giá trị thiếu . .25
2.2.3. Tránh “quá vừa” dữ liệu .26
2.2.4. Chuyển đổi từ cây quyết định sang luật .26
2.2.5. C4.5 là một thuật toán hiệu quả cho những tập dữ liệu vừa và nhỏ .27
2.3. Thuật toán SPRINT 28
2.3.1. Cấu trúc dữ liệu trong SPRINT 29
2.3.2. SPRINT sử dụng Gini-index làm độ đo tìm điểm phân chia tập dữ liệu “tốt nhất”
31
2.3.3. Thực thi sự phân chia .34
2.3.4. SPRINT là thuật toán hiệu quả với những tập dữ liệu quá lớn so với các thuật toán
khác . 35
- iv-
2.4. So sánh C4.5 và SPRINT 37
Chương 3. CÁC KẾT QUẢ THỰC NGHIỆM .38
3.1. Môi trường thực nghiệm .38
3.2. Cấu trúc mô hình phân lớp C4.5 release8: . .38
3.2.1. Mô hình phân lớp C4.5 có 4 chương trình chính: 38
3.2.2. Cấu trúc dữ liệu sử dụng trong C4.5 39
3.3. Kết quả thực nghiệm .4 0
3.3.1. `7Một số kết quả phân lớp tiêu biểu: . .40
3.3.2. Các biểu đồ hiệu năng 47
3.4. Một số đề xuất cải tiến mô hình phân lớp C4.5 54
KẾT LUẬN 56
TÀI LIỆU THAM KHẢO .57