- 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. - 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ỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT ĐỊNH...3. - Tổng quan về phân lớp dữ liệu trong data mining...3. - Phân lớp dữ liệu...3. - Các vấn đề liên quan đến phân lớp dữ liệu...6. - Cây quyết định ứng dụng trong phân lớp dữ liệu ...9. - Các vấn đề trong khai phá dữ liệu sử dụng cây quyết định...10. - Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu...11. - Tránh “quá vừa” dữ liệu ...26. - 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. - Cấu trúc dữ liệu trong SPRINT ...29. - 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. - Cấu trúc dữ liệu sử dụng trong C4.5 ...39. - Hình 1 - Quá trình phân lớp dữ liệu - (a) Bước xây dựng mô hình phân lớp ...4. - Hình 2 - Quá trình phân lớp dữ liệu - (b1)Ước lượng độ chính xác của mô hình...5. - Hình 3 - Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ...5. - Hình 6 - Mã giả của thuật toán phân lớp dữ liệu dựa trên cây quyết định ...14. - Hình 19 - File chứa dữ liệu cần phân lớp ...40. - Hình 20 - Dạng cây quyết định tạo ra từ tập dữ liệu thử nghiệm...41. - Hình 25 - Ước lượng tập luật trên tập dữ liệu đào tạo ...46. - Bảng 1 - Bảng dữ liệu tập training với thuộc tính phân lớp là buys_computer ...24 Bảng 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích. - thước tập dữ liệu đào tạo 2 thuộc tính...49 Bảng 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích. - thước tập dữ liệu đào tạo 7 thuộc tính...50 Bảng 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích. - 1 training data dữ liệu đào tạo. - 2 test data dữ liệu kiểm tra. - 3 Pruning decision tree Cắt, tỉa cây quyết định 4 Over fitting data Quá vừa dữ liệu. - 5 Noise Dữ liệu lỗi. - 7 Data tuple Phần tử dữ liệu. - Chương 1 đi từ tổng quan công nghệ phân lớp dữ liệu tới kỹ thuật phân lớp dữ liệu dựa trên cây quyết định. - TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT ĐỊNH. - Tổng quan về phân lớp dữ liệu trong data mining. - Phân lớp dữ liệu. - Quá trình phân lớp dữ liệu gồm hai bước [14]:. - Hình 1 - Quá trình phân lớp dữ liệu - (a) Bước xây dựng mô hình phân lớp. - Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu mới. - Hình 2 - Quá trình phân lớp dữ liệu - (b1)Ước lượng độ chính xác của mô hình. - Hình 3 - Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới. - Các vấn đề liên quan đến phân lớp dữ liệu. - Chuẩn bị dữ liệu cho việc phân lớp. - Làm sạch dữ liệu. - Phân tích sự cần thiết của dữ liệu. - Chuyển đổi dữ liệu. - Cây quyết định ứng dụng trong phân lớp dữ liệu. - Để phân lớp mẫu dữ liệu chưa biết, giá trị các thuộc tính của mẫu được đưa vào kiểm tra trên cây quyết định. - Các vấn đề trong khai phá dữ liệu sử dụng cây quyết định. - Tránh “quá vừa” dữ liệu. - Có hai phương pháp tránh “quá vừa” dữ liệu trong cây quyết định:. - Với θ là hằng số ngưỡng (threshold) được lần lượt xác định dựa trên từng giá trị riêng biệt hay từng cặp giá trị liền nhau (theo thứ tự đã sắp xếp) của thuộc tính liên tục đang xem xét trong tập dữ liệu đào tạo. - Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu. - Các thuật toán xây dựng cây quyết định đưa ra thuộc tính mà phân chia tốt nhất tập dữ liệu đào tạo bắt đầu từ node gốc của cây. - Phần lớn các thuật toán phân lớp dữ liệu dựa trên cây quyết định có mã giả như sau:. - Các thuật toán phân lớp dữ liệu dựa trên cây quyết định đều có tư tưởng chủ đạo là phương pháp Hunt đã trình bày ở trên. - Luôn có 2 câu hỏi lớn cần phải được trả lời trong các thuật toán phân lớp dữ liệu dựa trên cây quyết định là:. - Song song hóa xu hướng nghiên cứu hiện nay của các thuật toán phân lớp dữ liệu dựa trên cây quyết định. - |S| là kích thước tập dữ liệu đào tạo.. - Bảng 1 - Bảng dữ liệu tập training với thuộc tính phân lớp là buys_computer. - Thực thi test đó ta được hai tập dữ liệu con: V 1 = {v 1 , v 2. - Trong quá trình xây dựng cây từ tập dữ liệu đào tạo S, B là test dựa trên thuộc tính A a với các giá trị đầu ra là b 1 , b 2. - Có một số phương pháp tránh “quá vừa” dữ liệu trong cây quyết định:. - Hàng Tetabyte (100 M bản ghi * 2000 trường * 5 bytes) dữ liệu cần được khai phá. - Cả 2 thuật toán sử dụng những cấu trúc dữ liệu giúp cho việc xây dựng cây quyết định dễ dàng hơn. - Cấu trúc dữ liệu trong SPRINT. - SLIQ phân chia dữ liệu thành hai loại cấu trúc:[14][9]. - Hình 12 - Cấu trúc dữ liệu trong SLIQ. - Danh sách lớp (Class List) chứa các giá trị của thuộc tính phân lớp tương ứng với từng bản ghi trong cơ sở dữ liệu. - SPRINT tạo danh sách thuộc tính cho từng thuộc tính trong tập dữ liệu. - Các danh sách thuộc tính ban đầu tạo ra từ tập dữ liệu đào tạo được gắn với gốc của cây quyết định. - 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”. - Trong đó: S là tập dữ liệu đào tạo có n lớp. - Cơ chế lưu trữ dữ liệu. - Cơ chế sắp xếp dữ liệu. - Sắp xếp lại tập dữ liệu tương ứng với mỗi node. - Chương trình ứng dụng cây quyết định vào phân lớp những dữ liệu mới (consult). - Chương trình ứng dụng bộ luật sản xuất vào phân lớp những dữ liệu mới (consultr). - Filestem.names: định nghĩa bộ dữ liệu. - Các dòng tiếp theo là danh sách các thuộc tính cùng với tập giá trị của nó trong tập dữ liệu. - Filestem.data: chứa dữ liệu training. - Hình 19 - File chứa dữ liệu cần phân lớp. - Filestem.test: chứa dữ liệu test. - -f: xác định bộ dữ liệu cần phân lớp. - Hình 20 - Dạng cây quyết định tạo ra từ tập dữ liệu thử nghiệm. - Hình 21 - Ước lượng trên cây quyết định vừa tạo ra trên tập dữ liệu training và tập dữ liệu test. - Hình 25 - Ước lượng tập luật trên tập dữ liệu đào tạo. - Số các bản ghi trong tập dữ liệu đào tạo (N). - t div (i) là chi phí phân chia tập dữ liệu theo thuộc tính đã chọn. - Thử nghiệm với tập dữ liệu 2 thuộc tính. - Bảng 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo 2 thuộc tính. - Kích thước Thời gian tập dữ liệu xây dựng (giây). - Biểu đồ 2 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo 2 thuộc tính. - Thử nghiệm với tập dữ liệu 7 thuộc tính. - Bảng 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo 7 thuộc tính. - Biểu đồ 3 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo 7 thuộc tính. - Thử nghiệm với tập dữ liệu 18 thuộc tính. - Bảng 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo18 thuộc tính. - Biểu đồ 4 - Thời gian xây dựng cây quyết định và tập luật sản xuất phụ thuộc vào kích thước tập dữ liệu đào tạo18 thuộc tính. - Do vậy C4.5 bị hạn chế về số lượng thuộc tính trong tập dữ liệu đào tạo [2]. - Do vậy tập dữ liệu có nhiều. - thuộc tính liên tục ảnh hưởng đáng kể đến thời gian sinh cây quyết định so với tập dữ liệu có nhiều thuộc tính rời rạc.. - Trong khuôn khổ khóa luận tốt nghiệp này, chúng tôi đã nghiên cứu, phân tích, đánh giá các thuật toán phân lớp dữ liệu dựa trên cây quyết định