ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ 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

- 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 .
- 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â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.
- Tránh “quá vừa” dữ liệu.
- C4.5 là một thuật toán hiệu quả cho những tập dữ liệu vừa và nhỏ.
- 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.
- 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ấu trúc dữ liệu sử dụng trong C4.5.
- 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ụ.
- Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng mong muốn đó.
- Khóa luận đã nghiên cứu tổng quan về công nghệ phân lớp dữ liệu nói chung và phân lớp dữ liệu dựa trên cây quyết định nói riêng.
- Từ đó có thể triển khai cài đặt và thử nghiệm các mô hình phân lớp dữ liệu trên thực tế.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 1- 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 cũng đã chạy thử nghiệm mô hình phân lớp C4.5 trên tập dữ liệu thực tế từ Tổng công ty bưu chính viễn thông.
- Qua đó tiếp thu được các kỹ thuật triển khai, áp dụng một mô hình phân lớp dữ liệu vào hoạt động thực tiễn.
- Khóa luận gồm có 3 chương chính: 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.
- Chương này cũng cung cấp một cái nhìn tổng quan về lĩnh vực 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 với nền tảng tư tưởng, tình hình nghiên cứu và phương hướng phát triển hiện nay.
- Chương 3 trình bày quá trình thực nghiệm với mô hình phân lớp C4.5 trên tập dữ liệu thực từ tổng công ty bưu chính viễn thông Việt Nam.
- Từ đó khóa luận đề xuất các cải tiến mô hình phân lớp C4.5 Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 2- 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 Chương 1.
- TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU DỰA TRÊN CÂY QUYẾT ĐỊNH 1.1.
- Tổng quan về phân lớp dữ liệu trong data mining 1.1.1.
- Phân lớp dữ liệu Ngày nay phân lớp dữ liệu (classification) là một trong những hướng nghiên cứu chính của khai phá dữ liệu.
- Quá trình phân lớp dữ liệu gồm hai bước [14.
- Đầu vào của quá trình này là một tập dữ liệu có cấu trúc được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 3- 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 đó.
- Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu (data tuple), có thể là các mẫu (sample), ví dụ (example), đối tượng (object), bản ghi (record) hay trường hợp (case).
- Quá vừa dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 4- 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 liệu đó.
- Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu đào tạo.
- b1) Classifier (model) Test data Age Car Type Risk 27 Sports High 34 Family Low Risk 66 Family High High 44 Sports High Low Low High 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 b2) Classifier (model) New data Age C a r T yp e R is k 27 S po rts 34 M iniv a n R is k 55 F a m ily H ig h 34 S po rts Low Low H ig h Hình 3 - Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp.
- Phân lớp cây quyết định (Decision tree classification) Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 5- 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 • Bộ phân lớp Bayesian (Bayesian classifier.
- Các vấn đề liên quan đến phân lớp dữ liệu 1.1.2.1.
- Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu quả và khả năng mở rộng được của mô hình phân lớp.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 7- 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ính đơn giản (simplicity) Tính đơn giản liên quan đến kích thước của cây quyết định hay độ cô đọng của các luật.
- Cả 2 kỹ thuật này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 8- 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 1.2.
- Cây quyết định ứng dụng trong phân lớp dữ liệu 1.2.1.
- Node lá: biểu diễn lớp hay sự phân phối lớp (hình tròn) Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 9- 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 Để 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.
- Quá vừa dữ liệu là một khó khăn đáng kể đối với học bằng cây quyết định và những phương pháp học khác.
- Có hai phương pháp tránh “quá vừa” dữ liệu trong cây quyết định.
- Dừng phát triển cây sớm hơn bình thường, trước khi đạt tới điểm phân lớp hoàn hảo tập dữ liệu đào tạo.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 10- 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 1.2.2.2.
- 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.
- Điều đó có nghĩa là nếu thuộc tính liên tục A trong tập dữ liệu đào tạo có d giá trị phân biệt thì cần thực hiện d-1 lần kiểm tra value(A.
- Đánh giá cây quyết định trong lĩnh vực khai phá dữ liệu 1.2.3.1.
- Thể hiện rõ ràng những thuộc tính tốt nhất 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.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 12- 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 1.2.3.2.
- Tư tưởng chung 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: Make Tree (Training Data T.
- 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 Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 14- 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 Các thuật toán phân lớp như C4.5 (Quinlan, 1993), CDP (Agrawal và các tác giả khác, 1993), SLIQ (Mehta và các tác giả khác, 1996) và SPRINT (Shafer và các tác giả khác, 1996) đều sử dụng phương pháp của Hunt làm tư tưởng chủ đạo.
- Tình hình nghiên cứu các thuật toán hiện nay 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à: 1.
- Có 3 loại tiêu chuẩn hay chỉ số để xác định thuộc tính tốt nhất phát triển tại mỗi node Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 15- 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 • Gini-index (Breiman và các đồng sự, 1984 [1.
- Do vậy các thuật toán ra đời trước yêu cầu toàn bộ tập dữ liệu đào tạo phải nằm thường trú trong bộ nhớ (memory- resident) trong quá trình phát triển cây quyết định.
- Hai thuật toán này đã sử dụng cơ chế lưu trữ dữ liệu thường trú trên đĩa (disk- resident) và cơ chế sắp xếp trước một lần (pre- sorting) tập dữ liệu đào tạo.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 16- 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 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ự 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.
- Tuy nhiên số lượng các case gắn với một node không nhất Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 18- 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 thiết phải tương ứng với số lượng công việc cần phải xử lý để phát triển cây con tại node đó.
- Chi phí di chuyển + Tải cân bằng Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 19- 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 Mô hình hoạt động của phương pháp lai được mô tả trong hình 9.
- Hình 9 - Sơ đồ xây dựng cây quyết định theo phương pháp lai Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 20- 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 Chương 2.
- Trong các thuật toán phân lớp dữ liệu dựa trên cây quyết định, C4.5 và SPRINT là hai thuật toán tiêu biểu cho hai phạm vi ứng dụng khác nhau.
- Thuật toán C4.5 Với những đặc điểm C4.5 là thuật toán phân lớp dữ liệu dựa trên cây quyết định hiệu quả và phổ biến trong những ứng dụng khai phá cơ sở dữ liệu có kích thước nhỏ.
- C4.5 sử dụng cơ chế lưu trữ dữ liệu thường trú trong bộ nhớ, chính đặc điểm này làm C4.5 chỉ thích hợp với những cơ sở dữ liệu nhỏ, và cơ chế sắp xếp lại dữ liệu tại Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 21- 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 mỗi node trong quá trình phát triển cây quyết định.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 22- 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 Do không thể đảm bảo được sự cực tiểu của cây quyết định, C4.5 dựa vào nghiên cứu tối ưu hóa, và sự lựa chọn cách phân chia mà có độ đo lựa chọn thuộc tính đạt giá trị cực đại.
- |S| là kích thước tập dữ liệu đào tạo.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 23- 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 Ví dụ mô tả cách tính information gain • Với thuộc tính rời rạc Bảng 1 - Bảng dữ liệu tập training với thuộc tính phân lớp là buys_computer Trong tập dữ liệu trên: s1 là tập những bản ghi có giá trị phân lớp là yes, s2 là tập những bản ghi có giá trị phân lớp là no.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 24- 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 • Với thuộc tính liên tục Xử lý thuộc tính liên tục đòi hỏi nhiều tài nguyên tính toán hơn thuộc tính rời rạc.
- Kỹ thuật Quick sort được sử dụng để sắp xếp các case trong tập dữ liệu đào tạo theo thứ tự tăng dần hoặc giảm dần các giá trị của thuộc tính liên tục V đang xét.
- Test để phân chia dữ liệu là test nhị phân dạng V θi.
- Thực thi test đó ta được hai tập dữ liệu con: V1 = {v1, v2.
- 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 Aa với các giá trị đầu ra là b1, b2.
- Tương ứng với G(S, B), P(S, B) cũng thay đổi, Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 25- 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 Hai thay đổi này làm giảm giá trị của test liên quan đến thuộc tính có tỉ lệ giá trị thiếu cao.
- Quá vừa dữ liệu là hiện tượng: nếu không có các case xung đột (là những case mà giá trị cho mọi thuộc tính là giống nhau nhưng giá trị của lớp lại khác nhau) thì cây quyết định sẽ phân lớp chính xác toàn bộ các case trong tập dữ liệu đào tạo.
- Có một số phương pháp tránh “quá vừa” dữ liệu trong cây quyết định.
- C4.5 sử dụng kỹ thuật thứ hai để tránh “quá vừa” dữ liệu.
- Khẳng định này sẽ được chứng minh qua kết quả thực nghiệm trên mô hình phân lớp C4.5 Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 26- 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 Giai đoạn chuyển dổi từ cây quyết định sang luật bao gồm 4 bước.
- C4.5 là một thuật toán hiệu quả cho những tập dữ liệu vừa và nhỏ C4.5 có cơ chế sinh cây quyết định hiệu quả và chặt chẽ bằng việc sử dụng độ đo lựa chọn thuộc tính tốt nhất là information-gain.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 27- 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 2.3.
- 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.
- Initial call: Partition(Training Data) Hình 11 - Mã giả thuật toán SPRINT Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 28- 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 2.3.1.
- 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.
- 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.
- Biểu đồ (Histogram) Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 30- 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 SPRINT sử dụng biểu đồ để lập bảng thống kê sự phân phối lớp của các bản ghi trong mỗi danh sách thuộc tính, từ đó dùng vào việc ước lượng điểm phân chia cho danh sách đó.
- 1- ∑pj2 Trong đó: S là tập dữ liệu đào tạo có n lớp.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 31- 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 Ưu điểm của loại chỉ số này là các tính toán trên nó chỉ dựa vào thông tin về sự phân phối các giá trị lớp trong từng phần phân chia mà không tính toán trên các giá trị của thuộc tính đang xem xét.
- Hình 14 - Ước lượng các điểm phân chia với thuộc tính liên tục Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 32- 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 Với thuộc tính rời rạc Với thuộc tính rời rạc, quá trình tìm điểm phân chia tốt nhất cũng được tính toán dựa trên biểu đồ của danh sách thuộc tính đó.
- Tập dữ liệu đào tạo có càng nhiều thuộc tính thì sự chênh lệch về thời gian thực thi giữa 2 quá trình trên càng lớn.
- 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 Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 53- 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 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.
- Trên thực tế đó, chúng tôi đề xuất tích hợp thêm vào C4.5 module trích chọn tập những luật “tốt Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 54- 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 nhất” có là những luật có độ chính xác chấp nhận được (mức độ chính xác có thể do người dùng tùy chọn) và có độ phổ biến cao (là những luật mà áp dụng được trên nhiều case trong tập dữ liệu thử nghiệm).
- Sinh luật sản xuất là một tính năng mới, đem lại nhiều lợi ích của C4.5 so với các thuật toán phân lớp dữ liệu khác.
- C4.5 bị hạn chế về số lượng thuộc tính trong tập dữ liệu đào tạo, và độ chính xác của các cây quyết định hay các luật sinh ra nói chung là chưa cao.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 55- 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 KẾT LUẬN 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.
- C4.5 và SPRINT có cách thức lưu trữ dữ liệu và xây dựng cây quyết định dựa trên những độ đo khác nhau.
- SPRINT là một thuật toán tối ưu cho những cơ sở dữ liệu cực lớn.
- Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 56- 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ÀI LIỆU THAM KHẢO [1] Anurag Srivastava, Eui- Hong Han, Vipin Kumar, Vieet Singh.
- In Proceeding of Fourteenth National Conference on Artificial Intelligence, Providence RI, 1997 Khóa luận tốt nghiệp – Nguyễn Thị Thùy Linh – K46CA - 57- 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 www.almaden.ibm.com/software/quest/Publications/papers/vldb96_sprint.pdf [13] Ron Kohavi, J