Đ I H C QU C GIA HÀ N I TR NG Đ I H C CÔNG NGH Nguy n Th Thùy Linh 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 T T NGHI P Đ I H C H CHÍNH QUY Ngành: Công ngh thông tin HÀ N I - 2005 Đ I H C QU C GIA HÀ N I TR NG Đ I H C CÔNG NGH Nguy n Th Thùy Linh 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 T T NGHI P Đ I H C H CHÍNH QUY Ngành: Công ngh thông tin Cán b h ng d n: TS. Nguy n H i Châu HÀ N I - 2005 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. 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.
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. - i- L IC M N Trong suốt thời gian học tập, hoàn thành khóa luận em đã may mắn đ ợc các thầy cô chỉ bảo, dìu dắt và đ ợc gia đình, bạn bè quan tâm, động viên. Em xin đ ợc bày tỏ lòng biết ơn chân thành tới các thầy cô tr ờng Đại học Công Nghệ đã truyền đạt cho em nguồn kiến thức vô cùng quý báu cũng nh cách học tập và nghiên cứu khoa học. Cho phép em đ ợc gửi lời cảm ơn sâu sắc nhất tới TS.
Nguyễn Hải Châu, ng ời thầy đã rất nhiệt tình chỉ bảo và h ớng dẫn em trong suốt quá trình thực hiện khóa luận. Với tất cả tấm lòng mình, em xin bày tỏ lòng biết ơn sâu sắc đến TS. Hà Quang Thụy đã tạo điều kiện thuận lợi và cho em những định h ớng nghiên cứu. Em xin lời cảm ơn tới Nghiên cứu sinh Đoàn Sơn (JAIST) đã cung cấp tài liệu và cho em những lời khuyên quý báu.
Em cũng xin gửi lời cảm ơn tới các thầy cô trong Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin đã giúp em có đ ợc môi thực nghiệm thuận lợi. Em cũng xin gửi tới các bạn trong nhóm Seminar “Khai phá dữ liệu và Tính toán song song” lời cảm ơn chân thành vì những đóng góp và những kiến thức quý báu em đã tiếp thu đ ợc trong suốt thời gian tham gia nghiên cứu khoa học. Cuối cùng, em xin cảm ơn gia đình, bạn bè và tập thể lớp K46CA, những ng ời đã luôn ở bên khích lệ và động viên em rất nhiều. Hà Nội, tháng 6 năm 2005 Sinh viên Nguyễn Thị Thùy Linh - ii- M CL C TÓM T T N I DUNG.
iii DANH M C BI U Đ HÌNH VẼ.v DANH M C THU T NG. 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.
Các vấn đề liên quan đến phân lớp dữ liệu. Các ph ơng pháp đánh giá độ chính xác của mô hình phân lớp. Cây quyết định ứng dụng trong phân lớp dữ liệu. Các vấn đề trong khai phá dữ liệu sử dụng cây quyết định.
Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu. Xây dựng cây quyết định. Thuật toán xây dựng cây quyết định. Tình hình nghiên cứu các thuật toán hiện nay.
Song song hóa thuật toán phân lớp dựa trên cây quyết định tuần tự. Giới thiệu chung .5 dùng Gain-entropy làm độ đo lựa chọn thuộc tính “tốt nhất”.5 có cơ chế riêng trong xử lý những giá trị thiếu. Tránh “quá vừa” dữ liệu. Chuyển đổi từ cây quyết định sang luật .5 là một thuật toán hiệu quả cho những tập dữ liệu vừa và nhỏ.
Thuật toán SPRINT. Cấu trúc dữ liệu trong SPRINT. 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”. Thực thi sự phân chia.
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. CÁC K T QU TH C NGHI M. Môi tr ờng thực nghiệm. Cấu trúc mô hình phân lớp C4.
Mô hình phân lớp C4.5 có 4 ch ơng trình chính:. Cấu trúc dữ liệu sử dụng trong C4. Kết quả thực nghiệm. `7Một số kết quả phân lớp tiêu biểu:.
Các biểu đồ hiệu năng. Một số đề xuất cải tiến mô hình phân lớp C4.56 TÀI LI U THAM KH O.57 - iv- DANH M C BI U Đ HÌNH VẼ 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 4 - ớc l ợng độ chính xác của mô hình phân lớp với ph ơng pháp holdout .8 Hình 5- Ví dụ về cây quyết định .9 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 7 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp đồng bộ.18 Hình 8 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp phân hoạch .19 Hình 9 - Sơ đồ xây dựng cây quyết định theo ph ơng pháp lai.20 Hình 10 - Mã giả thuật toán C4.22 Hình 11 - Mã giả thuật toán SPRINT.28 Hình 12 - Cấu trúc dữ liệu trong SLIQ.29 Hình 13 - Cấu trúc danh sách thuộc tính trong SPRINT – Danh sách thuộc tính liên tục đ ợc sắp xếp theo thứ tự ngay đ ợc tạo ra .30 Hình 14 - ớc l ợng các điểm phân chia với thuộc tính liên tục .32 Hình 15 - ớc l ợng điểm phân chia với thuộc tính rời rạc .33 Hình 16 - Phân chia danh sách thuộc tính của một node .34 Hình 17 - Cấu trúc của bảng băm phân chia dữ liệu trong SPRINT (theo ví dụ các hình tr ớc) .35 Hình 18 - File định nghĩa cấu trúc dữ liệu sử dụng trong thực nghiệm .39 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 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 .42 Hình 22 - Một số luật rút ra từ bộ dữ liệu 19 thuộc tính, phân lớp loại thiết lập chế độ giao diện của ng ời sử dụng (WEB_SETTING_ID).43 Hình 23 - Một số luật rút ra từ bộ dữ liệu 8 thuộc tính, phân lớp theo số hiệu nhà sản xuất điện thoại (PRODUCTER_ID) .44 Hình 24 - Một số luật sinh ra từ tập dữ liệu 8 thuộc tính, phân lớp theo dịch vụ điệnthoại mà khách hàng sử dụng (MOBILE_SERVICE_ID).45 Hình 25 - ớc l ợng tập luật trên tập dữ liệu đào tạo .46 - v- 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 th ớc tập dữ liệu đào tạo18 thuộc tính.51 Bảng 5 - Thời gian sinh cây quyết định phụ thuộc vào số l ợng thuộc tính .52 Bảng 6 - Thời gian xây dựng cây quyết định với thuộc tính rời rạc và thuộc tính liên tục .53 Bảng 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp.54 Biểu đồ 1- So sánh thời gian thực thi của mô hình phân lớp SPRINT và SLIQ theo kích th ớc tập dữ liệu đào tạo.36 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.49 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.50 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.51 Biểu đồ 5 - Sự phụ thuộc thời gian sinh cây quyết định vào số l ợng thuộc tính.52 Biểu đồ 6 - So sánh thời gian xây dựng cây quyết định từ tập thuộc tính liên tục và từ tập thuộc tính rời rạc .53 Biểu đồ 7 - Thời gian sinh cây quyết định phụ thuộc vào số giá trị phân lớp.54 - vi- DANH M C THU T NG STT Ti ng Anh Ti ng Vi t 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 6 Missing value Giá trị thiếu 7 Data tuple Phần tử dữ liệu Case (đ ợc hiểu nh một data 8 Case tuple, chứa một bộ giá trị của các thuộc tính trong tập dữ liệu) - vii- 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 V N Đ Trong quá trình hoạt động, con ng ời tạo ra nhiều dữ liệu nghiệp vụ.