Tài liệu Luận văn thạc sĩ hướng xây dựng cây quyết định với chi phí hiệu quả

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA TRƯƠNG TIẾN QUỐC TRƯƠNG TIẾN QUỐC * KHOA HỌC MÁY TÍNH HƯỚNG XÂY DỰNG CÂY QUYẾT ĐỊNH VỚI CHI PHÍ HIỆU QUẢ LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH * KHÓA K32 Đà Nẵng - Năm 2018 ĐẠI HỌC ĐÀ NẴNG TRƢỜNG ĐẠI HỌC BÁCH KHOA --------------------------------------- TRƢƠNG TIẾN QUỐC HƢỚNG XÂY DỰNG CÂY QUYẾT ĐỊNH VỚI CHI PHÍ HIỆU QUẢ Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số: 60.48.01 LUẬN VĂN THẠC SĨ NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. Nguyễn Văn Hiệu Đà Nẵng – Năm 2018 i LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả Trƣơng Tiến Quốc ii MỤC LỤC Trang phụ bìa Lời cam đoan Mục lục Tóm tắt luận văn Danh mục các từ viết tắt Danh mục các bảng Danh mục các hình i ii iv v vi vii MỞ ĐẦU CHƢƠNG 1 - GIỚI THIỆU TỔNG QUAN 1.1. Cây quyết định: ............................................................................................... 4 1.1.1. Giới thiệu chung: ..................................................................................... 4 1.1.2. Các kiểu cây quyết định:.......................................................................... 5 1.1.3. Ƣu và nhƣợc điểm của cây quyết định: ................................................... 5 1.1.4. Phƣơng pháp tổng quát xây dựng cây quyết định: .................................. 6 1.1.5. Phƣơng pháp đánh giá độ chính xác của cây quyết định:........................ 7 1.1.6. Cách biểu diễn cây quyết định: ................................................................ 8 1.1.7. Các vấn đề khó khăn: ............................................................................... 9 1.2. Các thuật toán liên quan cây quyết định: ...................................................... 10 1.2.1. Thuật toán ID3: ...................................................................................... 10 1.2.2. Thuật toán C4.5: .................................................................................... 13 1.2.3. Thuật toán tìm kiếm Heurictis: .............................................................. 16 1.2.4. Lập trình ràng buộc:............................................................................... 20 CHƢƠNG 2 - XÂY DỰNG CÂY QUYẾT ĐỊNH VỚI CHI PHÍ HIỆU QUẢ 2.1. Giới thiệu về D4: ........................................................................................... 25 2.2. Dữ liệu nhập và dữ liệu xuất: ........................................................................ 26 2.3. Mô hình xây dựng: ........................................................................................ 27 2.4. Tổng kết chƣơng 2: ....................................................................................... 29 CHƢƠNG 3 - ĐÁNH GIÁ KẾT QUẢ THỬ NGHIỆM 3.1. Giới thiệu: ..................................................................................................... 31 3.2. Dữ liệu:.......................................................................................................... 31 3.3. Cây quyết định có yếu tố chi phí: ................................................................. 32 3.4. Lợi ích của nhị phân:..................................................................................... 33 3.5. Ảnh hƣởng của các thuộc tính nhị phân đối với sự đa dạng dữ liệu:............ 37 iii 3.6. Tổng kết chƣơng 3: ....................................................................................... 43 KẾT LUẬN 1. Kết luận: ........................................................................................................... 44 2. Hƣớng nghiên cứu trong tƣơng lai: .................................................................. 44 DANH MỤC TÀI LIỆU THAM KHẢO QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (bản sao) 46 iv HƢỚNG TIẾP CẬN XÂY DỰNG CÂY QUYẾT ĐỊNH VỚI CHI PHÍ HIỆU QUẢ Học viên: TRƢƠNG TIẾN QUỐC Chuyên ngành: Khoa Học Máy Tính Mã số: 60.48.01 Khóa:32 Trƣờng Đại học Bách khoa – ĐHĐN Tóm tắt - Cây quyết định là một kỹ thuật máy học phổ biến có nhiều ứng dụng trong thực tế. Cây quyết định có thể đƣợc mở rộng để bao gồm chi phí liên quan đến mỗi lần kiểm thử, cho phép ƣu tiên về không gian đặc trƣng. Bài toán giảm thiểu chi phí dự kiến của một cây quyết định đƣợc gọi là bài toán NP- đầy đủ. Kết quả là, hầu hết các phƣơng pháp tiếp cận để tạo cây quyết định đều dựa vào một heuristic. Luận văn này nhằm mở rộng các phƣơng pháp đƣợc sử dụng trong các nghiên cứu trƣớc đây để tìm kiếm các cây quyết định với một chi phí dự kiến nhỏ hơn so với cách sử dụng một heuristic đơn giản. Ngƣợc lại với các nghiên cứu trƣớc đây về các cây quyết định nhỏ hơn sử dụng các phƣơng pháp tiếp cận chính xác, nhiều nghiên cứu cho rằng các phƣơng pháp tiếp cận chính xác nói chung không tìm ra các cây quyết định thấp hơn các cách tiếp cận heuristic. Luận văn chỉ ra sự thành công của các nghiên cứu trƣớc đây về vấn đề giảm thiểu kích thƣớc cây quyết định phụ thuộc một phần vào việc chuyển đổi dữ liệu sang dạng nhị phân. Chuyển đổi này sử dụng các giá trị của thuộc tính nhƣ là các phép thử nhị phân thay vì các thuộc tính khi xây dựng cây quyết định. Phƣơng pháp chuyển đổi dữ liệu sang dạng nhị phân đƣợc kiểm tra chi tiết và thông qua nhiều phép đo dữ liệu Từ khóa: cây quyết định; giảm thiểu chi phí dự kiến; phƣơng pháp tiếp cận chính xác; tìm kiếm cây quyết định nhỏ nhất; tiếp cận heuristic; chuyển dữ liệu sang dạng nhị phân AN APPROACH TO BUILDING DECISION TREES WITH COST EFFICIENCY Abstract - Decision trees have been a popular machine learning technique for some time. Decision trees are simple to construct, easy to understand on viewing, and have many desirable properties such as resistance to errors and noise in real world data. Decision trees can be extended to include costs associated with each test, allowing a preference over the feature space. The problem of minimizing the expected-cost of a decision tree is known to be NP-complete. As a result, most approaches to decision tree induction rely on a heuristic. This thesis extends the methods used in past research to look for decision trees with a smaller expected-cost than those found using a simple heuristic. In contrast to the past research which found smaller decision trees using exact approaches, I find that exact approaches in general do not find lower expected-cost decision trees than heuristic approaches. It is the work of this thesis to show that the success of past research on the simpler problem of minimizing decision tree size is partially dependent on the conversion of the data to binary form. This conversion uses the values of the attributes as binary tests instead of the attributes themselves when constructing the decision tree. The effect of converting data to binary form is examined in detail and across multiple measures of data to show the extent of this effect. Key words - decision tree; minimizing the expected-cost; exact approaches; search for the smallest decision tree; heuristic approaches; converting data to binary form v DANH MỤC CÁC TỪ VIẾT TẮT ACL Agent Communication Language AMS Agent Management System AP Agent Platform API Application Programming Interface CF Communication Failitator vi DANH MỤC CÁC BẢNG Số hiệu bảng 1.1 2.1 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 Tên bảng Đƣa ra bài toán tìm ra cây quyết định nhỏ nhất Tập các mẫu đƣợc đánh nhãn Các bộ dữ liệu từ UCI Machine Learning Repository đƣợc sử dụng để kiểm tra thuật toán D4. Bộ dữ liệu chi phí từ UCI Machine Learning Respository đƣợc sử dụng để kiểm tra thuật toán D4 Chi phí dự kiến của cây quyết định đƣợc tăng lên trên các bộ dữ liệu từ UCI Machine Learning Repository. So sánh giữa J48 của Weka, thuật toán D4 và lập trình ràng buộc (CP) của Bessiere trên dữ liệu phân loại. So sánh giữa J48 của Weka, thuật toán D4, phƣơng pháp lập trình ràng buộc (CP) của Bessiere trên dữ liệu phân loại. So sánh giữa J48 của WEKA và phƣơng pháp lập trình ràng buộc (CP) trên dữ liệu phân loại So sánh kích thƣớc cây quyết định giữa các đặc điểm dạng nhị phân và không phải dạng nhị phân trên một loại dữ liệu So sánh kích thƣớc cây quyết định giữa các đặc điểm dạng nhị phân và không phải dạng nhị phân trên một loại dữ liệu So sánh độ chính xác của các cây quyết định có đặc điểm dạng nhị phân và không phải dạng nhị phân trên một loại dữ liệu. Các dạng tập dữ liệu có kích thƣớc tƣơng tự đƣợc tìm thấy khi so sánh kích thƣớc cây quyết định. Trang 22 24 32 32 33 34 34 36 39 40 41 42 vii DANH MỤC CÁC HÌNH Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Ƣớc lƣợng độ chính xác của mô hình phân lớp với phƣơng pháp holdout 8 1.2 Ví dụ về cây quyết định 9 1.3 Đồ thị cho giải thuật tìm kiếm tốt nhất đầu tiên 17 1.4 Trạng thái bắt đầu và kết thúc trong trò đố 8 ô 18 1.5 Mô hình CP [5] 21 2.1 Hình minh họa của thuật toán D4. 24 3.1 3.2 3.3 Biều đồ cột cho thấy kích thƣớc trung bình của cây quyết định đƣợc tạo ra bởi mỗi thuật toán trên mỗi tập dữ liệu Biểu đồ cột cho thấy tính chính xác trung bình của cây quyết định trên dữ liệu kiểm thử đƣợc tạo ra bởi từng thuật toán trên mỗi tập dữ liệu. Ảnh hƣởng của việc chuyển đổi các thuộc tính sang dạng nhị phân. 35 36 38 1 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI: Trong quá trình hoạt động, con ngƣời tạo ra nhiều dữ liệu nghiệp vụ. Các tập dữ liệu đƣợc tích lũy có kích thƣớc ngày càng lớn, và có thể chứa nhiều thông tin ẩn dạng những quy luật chƣa đƣợc khám phá. Chính vì vậy, một nhu cầu đặt ra là cần tìm cách trích rút từ tập dữ liệu đó các luật về phân lớp dữ liệu hay dự đoán những xu hƣớng dữ liệu tƣơng lai. Những quy tắc nghiệp vụ thông minh đƣợc tạo ra sẽ phục vụ đắc lực cho các hoạt động thực tiễn, cũng nhƣ phục vụ đắc lực cho quá trình nghiên cứu khoa học. Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng mong muốn đó. Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trƣớc những khao khát tri thức của con ngƣời. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà nghiên cứu trong nhiều lĩnh vực khác nhau nhƣ học máy hệ chuyên gia, thống kê... Công nghệ này cũng ứng dụng trong nhiều lĩnh vực thực tế nhƣ: thƣơng mại, nhà băng, maketing, nghiên cứu thị trƣờng, bảo hiểm, y tế, giáo dục... Nhiều kỹ thuật phân lớp đã đƣợc đề xuất nhƣ: Phân lớp cây quyết định phân lớp Bayesian, phân lớp sử dụng kỷ thuật láng giềng, mạng nơron nhân tạo, sử dụng kỹ thuật phân tích thống kê,… Trong các kỹ thuậ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 cho khai phá dữ liệu[5][7]. Trong các mô hình phân lớp, thuật toán phân lớp là nhân tố chủ đạo. Do vậy cần xây dựng những thuật toán có độ chính xác cao, thực thi nhanh, có khả năng mở rộng để có thực thi với tập dữ liệu ngày càng lớn. Tuy nhiên, đối với tập dữ liệu có nhiều thuộc tính thì cấu trúc cây quyết định sẽ lớn (lớn về chiều sâu, và lớn cả chiều ngang), vì vậy vấn đề làm giảm độ lớn là cấp thiết. Việc xếp hạng các thuộc tính để thực hiện phân nhánh phụ thuộc vào lần phân nhánh trƣớc đó. Chính vì những khó khăn trên, các nhà nghiên cứu không ngừng cải tiến các thuật toán xây dựng cây quyết định nhỏ nhất với độ chính xác cao nhất. Nhƣng kèm theo đó cũng có một số khó khăn khi phải cân bằng giữa tính chính xác và chi phí xây dựng cây quyết định. Vì vậy, luận văn “Hướng tiếp cận xây dựng cây quyết định với chi phí hiệu quả” là hƣớng tiếp cận để giải quyết các vấn đề đã đƣợc nêu ra. 2. MỤC TIÊU NGHIÊN CỨU: - Nghiên cứu cây quyết định, cách xây dựng cây quyết định. - Nghiên cứu các phƣơng pháp xây dựng cây quyết định - Nghiên cứu các công trình tối ƣu hóa cây quyết định 2 - Nghiên cứu phƣơng pháp cải tiến, hƣớng tiếp cận mới trong xây dựng cây quyết định với chi phí hiệu quả. - Kiểm tra và đánh giá phƣơng pháp cải tiến, cũng nhƣ hƣớng tiếp cận mới. 3. ĐỐI TƢỢNG VÀ PHẠM VI NGHIÊN CỨU: 3.1. Đối tƣợng nghiên cứu: - Nghiên cứu các phƣơng pháp tối ƣu cây quyết định. - Cơ sở lý thuyết, công trình nghiên cứu trƣớc trong việc nỗ lực giảm chi phí cây quyết định với độ chính xác cao. 3.2. Phạm vi nghiên cứu: - Lập trình ràng buộc trong việc tìm kiếm cây quyết định. - Chuyển đổi dữ liệu sang dạng nhị phân trong xây dựng cây quyết định. - Phƣơng pháp quay lui trong việc đánh giá và xây dựng cây quyết định. - Nghiên cứu hƣớng tiếp cận mới nhằm tối ƣu hóa chi phí xây dựng cây quyết định. 4. PHƢƠNG PHÁP NGHIÊN CỨU: 4.1. Phƣơng pháp nghiên cứu lý thuyết: Tìm hiểu, tra cứu, phân tích và tổng hợp từ sách, báo, bài viết, tạp chí khoa học, các trang web, các bài luận văn thạc sĩ trong và ngoài nƣớc. 4.2. Phƣơng pháp thực nghiệm: - Đề xuất thuật toán mới tối ƣu chi phí xây dựng cây quyết định dựa trên công trình nghiên cứu đã có. - Cài đặt thực nghiệm, thu thập số liệu, so sánh và đánh giá kết quả đạt đƣợc. 5. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN: 5.1. Ý nghĩa khoa học: - Hiểu đƣợc đặc điểm, cấu trúc, quá trình thực hiện việc tìm kiếm cây quyết định tối ƣu dựa trên lập trình ràng buộc và các kỹ thuật khác. - Hiểu đƣợc lợi ích, hạn chế trong việc tìm kiếm cây quyết định nhỏ nhất. - Áp dụng thuật toán đề xuất dựa trên bộ dữ liệu UCI để đánh giá tính hiệu quả của thuật toán. 5.2. Ý nghĩa thực tiễn: - Đề xuất đƣợc giải pháp mới trong việc tìm kiếm cây quyết định nhỏ nhất với chi phí tối ƣu. 3 - Đánh giá hiệu quả, tính thực tiễn và khả năng áp dụng trong tƣơng lai. 6. CẤU TRÚC LUẬN VĂN: Ngoài phần mở đầu và kết luận, luận văn tổ chức nội dung thành ba chƣơng : - - Chƣơng 1: Giới thiệu tổng quan. Giới thiệu về cây quyết định, chỉ ra ƣu điểm và nhƣợc điểm của cây quyết định để từ đó đề xuất mô hình mới Chƣơng 2: Xây dựng cây quyết định với chi phí hiệu quả. Trình bày cách thức xây dựng cây quyết định, dữ liệu nhập và dữ liệu xuất, mô hình xây dựng cây quyết định với chi phí hiệu quả Chƣơng 3: Đánh giá kết quả thử nghiệm. Kiểm tra tính hiệu quả của việc xây dựng cây quyết định với chi phí hiệu quả sử dụng thuật toán D4 4 Chƣơng 1 - GIỚI THIỆU TỔNG QUAN 1.1. CÂY QUYẾT ĐỊNH: Trong lý thuyết quyết định, một cây quyết định (tiếng Anh: decision tree) là một đồ thị của các quyết định và các hậu quả có thể của nó (bao gồm rủi ro và hao phí tài nguyên). Cây quyết định đƣợc sử dụng để xây dựng một kế hoạch nhằm đạt đƣợc mục tiêu mong muốn. Các cây quyết định đƣợc dùng để hỗ trợ quá trình ra quyết định. Cây quyết định là một dạng đặc biệt của cấu trúc cây. 1.1.1. Giới thiệu chung: Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tƣợng tới các kết luận về giá trị mục tiêu của sự vật/hiện tƣợng. Mỗi một nút trong (internal node) tƣơng ứng với một biến; đƣờng nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trƣớc các giá trị của các biến đƣợc biểu diễn bởi đƣờng đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định đƣợc gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. Học bằng cây quyết định cũng là một phƣơng pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó[1]. Một cây quyết định có thể đƣợc học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính[1]. Quá trình này đƣợc lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành khi không thể tiếp tục thực hiện việc chia tách đƣợc nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên (random forest) sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại. Cây quyết định cũng là một phƣơng tiện có tính mô tả dành cho việc tính toán các xác suất có điều kiện. Cây quyết định có thể đƣợc mô tả nhƣ là sự kết hợp của các kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trƣớc. Dữ liệu đƣợc cho dƣới dạng các bản ghi có dạng: (x, y) = (x1, x2, x3..., xk, y) Biến phụ thuộc (dependant variable) y là biến mà chúng ta cần tìm hiểu, phân loại hay tổng quát hóa. x1, x2, x3 ... là các biến sẽ giúp ta thực hiện công việc đó 5 1.1.2. Các kiểu cây quyết định: Cây quyết định còn có hai tên khác: - Cây hồi quy (Regression tree) ƣớc lƣợng các hàm có giá trị là số thực thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. (ví dụ: ƣớc tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện) - Cây phân lớp (Classification tree): là kiểu cây có biến phụ thuộc là một biến phân loại nhƣ: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua). 1.1.3. Ƣu và nhƣợc điểm của cây quyết định: 1.1.3.1. Ưu điểm: - Khả năng sinh ra các quy tắc hiểu được: Cây quyết định có khả năng sinh ra các luật IF-THEN hoặc có thể chuyển đổi đƣợc sang SQL. Đây là ƣu điểm nổi bật của kỹ thuật này. Thậm chí với những tập dữ liệu lớn khiến cho hình dáng cây quyết định lớn và phức tạp, việc đi theo bất cứ đƣờng đi nào trên cây là dễ dàng thực hiện đƣợc. Do vậy, sự giải thích cho bất cứ một sự phân lớp hay dự đoán đều mang tính tƣơng đối minh bạch. - Khả năng thực thi trong nh ng l nh vực hư ng quy tắc: những quy tắc quy nạp nói chung và cây quyết định nói riêng là lựa chọn hoàn hảo cho những lĩnh vực hƣớng quy tắc. Rất nhiều lĩnh vực từ di truyền tới các quá trình công nghiệp thực sự chứa các quy tắc ẩn, không rõ ràng (underlying rules), khá phức tạp và tối nghĩa bởi những dữ liệu lỗi (noisy). dàng t nh toán trong khi phân l p mặc dù cây quyết định có thể chứa nhiều định dạng, nhƣng trong thực tế, các thuật toán sử dụng để tạo ra cây quyết định thƣờng tạo ra những cây với số phân nhánh thấp và các điều kiện đơn giản tại từng nút. Những điều kiện điển hình là: so sánh số, xem xét phần tử của một tập hợp và các phép nối đơn giản. Khi thực thi trên máy tính, những điều kiện này chuyển thành các toán hàm logic và số nguyên là những toán hạng thực thi nhanh và không tốn chi phí. Đây là một ƣu điểm quan trọng bởi trong môi trƣờng thƣơng mại, các mô hình dự đoán thƣờng đƣợc sử dụng để phân lớp hàng triệu thậm trí hàng tỉ bản ghi. - Khả năng xử lý v i cả thuộc t nh liên tục và rời rạc: cây quyết định xử lý tốt nhƣ nhau với cả các thuộc tính liên tục và thuộc tính rời rạc, tuy rằng với các thuộc tính liên tục cần nhiều tài nguyên tính toán hơn. - 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 phân chia tốt nhất tập dữ liệu đào tạo, bắt đầu từ nút gốc của cây. 6 - Có khả năng thực hiện tốt trên tập d liệu l n trong thời gian ngắn: một lƣợng lớn dữ liệu có thể đƣợc phân tích bằng máy tính cá nhân trong thời gian ngắn đủ để ngƣời sử dụng đƣa ra quyết định dựa trên sự phân tích đó. Chính nhờ những điểm mạnh này mà trong nhiều năm qua, cây quyết định đƣợc bình chọn là giải thuật đƣợc sử dụng nhiều nhất và thành công nhất. Cây quyết định đƣợc ứng dụng thành công trong hầu hết các lĩnh vực về phân tích dữ liệu, phân loại văn bản, phân loại gen,… 1.1.3.2. Nhược điểm: Bên cạnh những ƣu điểm nổi bật trên, cây quyết định cũng có những điểm yếu nhƣ sau: xảy ra l i khi có nhi u l p: một số cây quyết định chỉ thao tác với lớp giá trị nhị phân dạng yes/no hay accept/reject. Dễ xảy ra lỗi khi tập dữ liệu huấn luyện không đủ lớn. - Chi ph học cao: do phải đi qua nhiều nút để đến nút lá cuối cùng. Tại từng nút, cần tính toán mật độ (hay tiêu chuẩn phân chia) trên từng thuộc tính, với thuộc tính liên tục phải thêm thao tác sắp xếp lại tập dữ liệu theo thứ tự giá trị của từng thuộc tính đó. Sau đó mới có thể chọn đƣợc một thuộc tính phát triển và tƣơng ứng là một phân chia tốt nhất. 1.1.4. Phƣơng pháp tổng quát xây dựng cây quyết định: Hiện nay, có một số lƣợng lớn các thuật toán khác nhau để xây dựng cây quyết định. Nhìn chung, việc xây dựng cây quyết đƣợc thực hiện bởi 3 giai đoạn cơ bản: - Xây dựng cây: Thực hiện chia một cách đệ quy tập mẫu dữ liệu huấn luyện cho đến khi các mẫu ở mỗi nút lá thuộc cùng một lớp. - Cắt tỉa cây: Là việc làm dùng để tối ƣu hoá cây. Cắt tỉa cây chính là việc trộn một cây con vào trong một nút lá. - Đánh giá cây Dùng để đánh giá độ chính xác của cây kết quả. Tiêu chí đánh giá là tổng số mẫu đƣợc phân lớp chính xác trên tổng số mẫu đƣa vào. Quá trình xây dựng một cây quyết định cụ thể bắt đầu bằng một nút rỗng bao gồm toàn bộ các đối tƣợng huấn luyện và làm nhƣ sau: 1. Nếu tại nút hiện thời, tất cả các đối tƣợng huấn luyện đều thuộc vào một lớp nào đó thì cho nút này thành nút lá có tên là nhãn lớp chung của các đối tƣợng. 2. Trƣờng hợp ngƣợc lại, sử dụng một độ đo, chọn thuộc tính điều kiện phân chia tốt nhất tập mẫu huấn luyện có tại nút. 7 3. Tạo một lƣợng nút con của nút hiện thời bằng số các giá trị khác nhau của thuộc tính đƣợc chọn. Gán cho mỗi nhánh từ nút cha đến nút con một giá trị của thuộc tính rồi phân chia các các đối tƣợng huấn luyện vào các nút con tƣơng ứng. 4. Nút con đƣợc gọi là thuần nhất, trở thành lá, nếu tất cả các đối tƣợng mẫu tại đó đều thuộc vào cùng một lớp. Lặp lại các bƣớc 1-3 đối với mỗi nút chƣa thuần nhất. Trong các thuật toán cơ sở xây dựng cây quyết định chỉ chấp nhận các thuộc tính tham gia vào quá trình phân lớp có giá trị rời rạc, bao gồm cả thuộc tính đƣợc dùng để dự đoán trong quá trình học cũng nhƣ các thuộc tính đƣợc sử dụng để kiểm tra tại mỗi nút của cây. Do đó trong trƣờng hợp các thuộc tính có giá trị liên tục có thể dễ dàng loại bỏ bằng cách phân mảnh tập giá trị liên tục của thuộc tính thành một tập rời các khoảng. Việc xây dựng cây quyết định đƣợc tiến hành một cách đệ qui, lần lƣợt từ nút gốc xuống tới các nút lá. Tại mỗi nút hiện hành đang xét, nếu kiểm tra thấy thoả điều kiện dừng: thuật toán sẽ tạo nút lá. Nút này đƣợc gán một giá trị của nhãn lớp tùy điều kiện dừng đƣợc thoả mãn. Ngƣợc lại, thuật toán tiến hành chọn điểm chia tốt nhất theo một tiêu chí cho trƣớc, phân chia dữ liệu hiện hành theo điều kiện chia này. Sau bƣớc phân chia trên, thuật toán sẽ lặp qua tất cả các tập con (đã đƣợc chia) và tiến hành gọi đệ qui nhƣ bƣớc đầu tiên với dữ liệu chính là các tập con này. Trong bƣớc 3, tiêu chuẩn sử dụng lựa chọn thuộc tính đƣợc hiểu là một số đo độ phù hợp, một số đo đánh giá độ thuần nhất, hay một quy tắc phân chia tập mẫu huấn luyện. 1.1.5. Phƣơng pháp đánh giá độ chính xác của cây quyết định: Ƣớc lƣợng độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán đƣợc độ chính xác của các kết quả phân lớp những dữ liệu tƣơng lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau. Luận văn này đề cập đến 2 phƣơng pháp đánh giá phổ biến là holdout và k-fold cross-validation. 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 Trong phƣơng pháp holdout, dữ liệu đƣa ra đƣợc phân chia ngẫu nhiên thành 2 phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thƣờng 2/3 dữ liệu cấp cho tập dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm tra [2]. 8 Hình 1.1 - Ƣớc lƣợng độ chính xác của mô hình phân lớp với phƣơng pháp holdout Trong phƣơng pháp k-fold cross validation tập dữ liệu ban đầu đƣợc chia ngẫu nhiên thành k tập con (fold) có kích thƣớc xấp xỉ nhau S1, S2, …, Sk. Quá trình học và kiểm tra đƣợc thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Có nghĩa là, đầu tiên việc dạy đƣợc thực hiện trên các tập S2, S3 …, Sk, sau đó test trên tập S1; tiếp tục quá trình dạy đƣợc thực hiện trên tập S1, S3, S4,…, Sk, sau đó test trên tập S2; và cứ thế tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia cho tổng số mẫu của tập dữ liệu ban đầu 1.1.6. Cách biểu diễn cây quyết định: 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 notron, mô hình thống kê tuyến tính /bậc 2, cây quyết định, mô hình di truyền. Trong số những mô hình đó, cây quyết định 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 data mining nói chung và phân lớp dữ liệu nói riêng [3]. 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. Hơn nữa các cây có thể dễ dàng đƣợc chuyển đổi sang các câu lệnh SQL để có thể đƣợc sử dụng để truy nhập cơ sở dữ liệu một cách hiệu quả. 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à chính xác hơn so với các phƣơng pháp phân lớp khác [4]. Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây, nhƣ mô tả trong hình vẽ sau: 9 Hình 1.2- Ví dụ về cây quyết định Trong cây quyết định: • Gốc: là node trên cùng của cây • Node trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình chữ nhật) • Nhánh: biểu diễn các kết quả của kiểm tra trên node trong (mũi tên) • Node lá: biểu diễn lớp hay sự phân phối lớp (hình tròn) Để 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. Mỗi mẫu tƣơng ứng có một đƣờng đi từ gốc đến lá và lá biểu diễn dự đoán giá trị phân lớp mẫu đó. 1.1.7. Các vấn đề khó khăn: Các vấn đề đặc thù trong khi học hay phân lớp dữ liệu bằng cây quyết định gồm: xác định độ sâu để phát triển cây quyết định, xử lý với những thuộc tính liên tục, chọn phép đo lựa chọn thuộc tính thích hợp, sử dụng tập dữ liệu đào tạo với những giá trị thuộc tính bị thiếu, sử dụng các thuộc tính với những chi phí khác nhau, và cải thiện hiệu năng tính toán. Sau đây luận văn sẽ đề cập đến những vấn đề chính đã đƣợc giải quyết trong các thuật toán phân lớp dựa trên cây quyết định. 1.1.7.1. Tránh “quá vừa” dữ liệu: Thế nào là “quá vừa” dữ liệu? Có thể hiểu đây là hiện tƣợng cây quyết định chứa một số đặc trƣng riêng của tập dữ liệu đào tạo, nếu lấy chính tập dữ liệu đào tạo để test lại mô hình phân lớp thì độ chính xác sẽ rất cao, trong khi đối với những dữ liệu tƣơng lai khác nếu sử dụng cây đó lại không đạt đƣợc độ chính xác nhƣ vậy. 10 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 biệt khi số lƣợng mẫu trong tập dữ liệu đào tạo quá ít, hay có nhiễu trong dữ liệu. 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. Với phƣơng pháp này, một thách thức đặt ra là phải ƣớc lƣợng chính xác thời điểm dừng phát triển cây. • Cho phép cây có thể “quá vừa” dữ liệu, sau đó sẽ cắt, tỉa cây. Mặc dù phƣơng pháp thứ nhất có vẻ trực tiếp hơn, nhƣng với phƣơng pháp thứ hai thì cây quyết định đƣợc sinh ra đƣợc thực nghiệm chứng minh là thành công hơn trong thực tế. Hơn nữa việc cắt tỉa cây quyết định còn giúp tổng quát hóa, và cải thiện độ chính xác của mô hình phân lớp. Dù thực hiện phƣơng pháp nào thì vấn đề mấu chốt ở đây là tiêu chuẩn nào đƣợc sử dụng để xác định kích thƣớc hợp lý của cây cuối cùng. 1.1.7.2. Thao tác với thuộc tính liên tục: Việc thao tác với thuộc tính liên tục trên cây quyết định hoàn toàn không đơn giản nhƣ với thuộc tính rời rạc. Thuộc tính rời rạc có tập giá trị (domain) xác định từ trƣớc và là tập hợp các giá trị rời rạc. Việc phân chia dữ liệu dựa vào phép kiểm tra giá trị của thuộc tính rời rạc đƣợc chọn tại một mẫu cụ thể có thuộc tập giá trị của thuộc tính đó hay không: value(A) ∈ X với X ⊂ domain (A). Đây là phép kiểm tra logic đơn giản, không tốn nhiều tài nguyên tính toán. Trong khi đó, với thuộc tính liên tục (thuộc tính dạng số) thì tập giá trị là không xác định trƣớc. Chính vì vậy, trong quá trình phát triển cây, cần sử dụng kiểm tra dạng nhị phân: value(A) ≤ θ. 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 huấn luyện. Điều đó có nghĩa là nếu thuộc tính liên tục A trong tập dữ liệu huân luyện có d giá trị phân biệt thì cần thực hiện d-1 lần kiểm tra value(A) ≤ θi với i = 1..d-1 để tìm ra ngƣỡng θbest tốt nhất tƣơng ứng với thuộc tính đó. Việc xác định giá trị của θ và tiêu chuẩn tìm θ tốt nhất tùy vào chiến lƣợc của từng thuật toán. 1.2. CÁC THUẬT TOÁN LIÊN QUAN CÂY QUYẾT ĐỊNH: 1.2.1. Thuật toán ID3: Thuật toán ID3 đƣợc phát biểu bởi Quinlan (trƣờng đại học Syney, Australia) và đƣợc công bố vào cuối thập niên 70 của thế kỷ 20. Sau đó, thuật toán ID3 đƣợc giới thiệu và trình bày trong mục máy học năm 1986. ID3 đƣợc xem nhƣ là một cải tiến 11 của CLS với khả năng lựa chọn thuộc tính tốt nhất để tiếp tục triển khai cây tại mỗi bƣớc. ID3 xây dựng cây quyết định từ trên- xuống (top -down)[5]. 1.2.1.1. Entropy: Entropy dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của một tập S đƣợc tính theo công thức (1) Entropy(S)= - P+ log 2 ( P )  P- log 2 ( P ) (2.1) Trong trƣờng hợp các mẫu dữ liệu có hai thuộc tính phân lớp "yes" (+), "no" (-). Ký hiệu p+ là để chỉ tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "yes", và p- là tỷ lệ các mẫu có giá trị của thuộc tính quyết định là "no" trong tập S. Trƣờng hợp tổng quát, đối với tập con S có n phân lớp thì ta có công thức sau: n Entropy(S)=  (- Pi log 2 ( Pi )) (2.2) i=1 Trong đó Pi là tỷ lệ các mẫu thuộc lớp i trên tập hợp S các mẫu kiểm tra. Các trƣờng hợp đặc biệt - Nếu tất cả các mẫu thành viên trong tập S đều thuộc cùng một lớp thì Entropy(S) =0 - Nếu trong tập S có số mẫu phân bổ đều nhau vào các lớp thì Entropy(S) =1 - Các trƣờng hợp còn lại 0< Entropy(S)<1 1.2.1.2. Information Gain: Information Gain (viết tắt là Gain) là đại lƣợng dùng để đo tính hiệu quả của một thuộc tính đƣợc lựa chọn cho việc phân lớp. Đại lƣợng này đƣợc tính thông qua hai giá trị Information và Entropy. - Cho tập dữ liệu S gồm có n thuộc tính Ai(i=1,2…n) giá trị Information của thuộc tính Ai ký hiệu là Information(Ai) đƣợc xác định bởi công thức . n Information(Ai ) = - log 2 ( pi )  Entropy(S) (2.3) i=1 - Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S,A) và đƣợc tính theo công thức sau: Gain( S , A)  Information(A) - Entropy(A)= Entropy(S)-  vvalue(A) Sv Entropy(Sv ) S (2.4) Trong đó :  S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tƣơng ứng là các giá trị của thuộc tính A.