Tài liệu 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 HƢỚNG TIẾP CẬN 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 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Đà Nẵng – Năm 2018 Công trình đƣợc hoàn thành tại TRƢỜNG ĐẠI HỌC BÁCH KHOA Ngƣời hƣớng dẫn khoa học: TS. NGUYỄN VĂN HIỆU Phản biện 1: TS. NGUYỄN THIỆN NGHĨA Phản biện 2: TS. ĐẶNG HOÀI PHƢƠNG Luận văn sẽ đƣợc bảo vệ trƣớc Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Khoa học máy tính họp tại Trƣờng Đại học Bách khoa vào ngày 03 tháng 02 năm 2018 Có thể tìm hiểu luận văn tại:  Trung tâm Học liệu, Đại học Đà Nẵng tại Trƣờng Đại học Bách khoa  Thƣ viện Khoa Công nghệ thông tin, Trƣờng Đại học Bách khoa - ĐHĐN 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. Nhiều kỹ thuật phân lớp đã đƣợc đề xuất nhƣ: Phân lớp cây quyết định (Decision tree classification), phân lớp Bayesian (Bayesian classifier), phân lớp Khàng xóm gần nhất (K-nearest neighbor classifier), mạng nơron, 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 data mining [5][7]. Tuy nhiên, đối với các tập dữ liệu có nhiều thuộc tính thì cây quyết định sẽ lớn ( về chiều sâu cả chiều ngang), vì vậy làm giảm độ dễ hiểu. Việc xếp hạng các thuộc tính để phân nhánh phụ thuộc vào lần phân nhánh trƣớc đó và bỏ qua sự phụ thuộc lẫn nhau giữa các thuộc tính. Chính vì những khó khăn đó, các nhà nghiên cứu không ngừng cho ra đời, 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 này đề cập đến “Hướng tiếp cận xây dựng cây quyết định với chi phí hiệu quả”. 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 2 - Nghiên cứu các công trình tối ƣu hóa cây quyết định - 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, mô phỏng - Đề 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. 3 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. - Đá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 Luận văn gồm nội dung nhƣ sau - Chƣơng 1: Giới thiệu chung về cây quyết định, các kiểu cây quyết định, ƣu điểm của cây quyết định và các thuật toán xây dựng cây quyết định. - Chƣơng 2: Xây dựng cây quyết định với chi phí hiệu quả - Chƣơng 3: Đánh giá kết quả kiểm thử - Kết luận: Kết luận những việc đã làm đƣợc và hƣớng nghiên cứu trong thời gian tới 4 Chƣơng 1. GIỚI THIỆU TỔNG QUAN 1.1. CÂY QUYẾT ĐỊNH 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. 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]. 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. 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ây phân loại (Classification tree) 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. - Khả năng thực thi trong những lĩnh vực hƣớng quy tắc. - Dễ dàng tính toán trong khi phân lớp. - Khả năng xử lý với cả thuộc tính liên tục và rời rạc. 5 - Thể hiện rõ ràng những thuộc tính tốt nhất. - 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. 1.1.3.2. Nhược điểm -C . í ọ o. 1.1.4. Phƣơng pháp tổng quát xây dựng cây quyết định 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ự g â . - Cắt tỉ - Đá â . gá â . 1.1.5. Các phƣơng pháp đánh giá độ chính xác của cây quyết định Phƣơng pháp holdout, Phƣơng pháp k-fold cross validation 1.1.6. Cách biểu diễn cây quyết định Cây quyết định là biểu đồ phát triển có cấu trúc dạng cây. Hình 1.2- Ví dụ về cây quyết định 6 1.1.7. Các vấn đề khó khăn 1.1.7.1. Tránh “quá vừa” dữ liệu 1.1.7.2. Thao tác với thuộc tính liên tục 1.2. CÁC THUẬT TOÁN LIÊN QUAN CÂY QUYẾT ĐỊNH 1.2.1. Thuật toán ID3 ID3 đƣợc xem nhƣ là một cải tiến 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 1.2.1.2. Information Gain 1.2.1.3. Hàm xây dựng cây quyết định trong thuật toán ID3 1.2.1.4. Đánh giá Thuật toán ID3 đƣợc xem là một cải tiến của thuật toán CLS. Tuy nhiên thuật toán ID3 không có khả năng xử lý đối với những dữ liệu có chứa thuộc tính số - thuộc tính liên tục (numeric attribute) và khó khăn trong việc xử lý các dữ liệu thiếu (missing data) và dữ liệu nhiễu (noisy data). 1.2.2. Thuật toán C4.5 Thuật toán C4.5 là một thuật toán đƣợc cải tiến từ thuật toán ID3 với việc cho phép xử lý trên tập dữ liệu có các thuộc tính số (numeric atributes) và và làm việc đƣợc với tập dữ liệu bị thiếu và bị nhiễu. 1.2.2.1. Thuật toán xây dựng cây quyết định C4.5 1.2.2.2. Một số cải tiến của thuật toán C4.5 a. Làm việc với thuộc tính đa trị b. Làm việc với dữ liệu bị thiếu . 7 1.2.3. Thuật toán tìm kiếm Heurictis 1.2.3.1. Tìm kiếm leo núi (Hill climbing – Pearl 1984) Cách đơn giản nhất để thực hiện tìm kiếm heuristic là tìm kiếm “leo núi”. Chiến lƣợc leo núi phát triển trạng thái con tốt nhất sẽ đƣợc chọn cho bƣớc tiếp theo, không lƣu giữ lại bất kỳ thông tin nào về các nút anh em lẫn cha mẹ của nó. Quá trình tìm kiếm sẽ dừng lại khi tiếp cận trạng thái tốt hơn so với mọi trạng thái con của nó.. Hạn chế chủ yếu của chiến lƣợc leo núi là có xu hƣớng rơi vào “một cực đại cục bộ”. 1.2.3.2. Tìm kiếm tốt nhất đầu tiên (Best – first – search) Tìm kiếm tốt nhất dùng các danh sách để lƣu giữ trạng thái: danh sách open chứa các nút đƣợc triển khai trong quá trình tìm kiếm và danh sách closed chứa các nút đã xét. Một bƣớc mới đƣợc bổ sung vào thuật toán là sắp xếp các trạng thái trong danh sách open phù hợp với giá trị heuristic ƣớc lƣợng “độ tốt” của chúng so với đích 1.2.3.3. Cài đặt hàm đánh giá heuristic (heuristic evaluation function) Một heuristic dùng hàm đánh giá f(n) nhƣ trên kết hợp với thuật toán tìm kiếm tốt nhất đầu tiên best-first-search, đƣợc gọi là t ật toá A (algorithm A) 1.2.3.4. Tính khả chấp, tính đơn nhất và khả năng cung cấp thông tin của heuristic a. Tính khả chấp Một heuristic dùng để tìm ra con đƣờng dẫn đến đích ngắn nhất bất cứ khi nào nó có tồn tại đƣợc gọi là heuristic khả chấp (admissible). 8 b. Tính đơn nhất Khi có một trạng thái đƣợc phát hiện nhờ sử dụng tìm kiếm heuristic, liệu có bảo đảm rằng về sau sẽ không tìm đƣợc một trạng thái nhƣ vậy với khoảng cách ngắn hơn tính từ trạng thái xuất phát c. Khả năng cung cấp thông tin: Chúng ta có thể đặt câu hỏi liệu có một heuristic nào “tốt hơn” những cái khác hay không? Heuristic này tốt hơn heuristic kia theo ý nghĩa nào ? Đây là khả năng cung cấp thông tin (informedness) của một heuristic. 1.2.4. Lập trình ràng buộc Là ngôn ngữ lập trình ràng buộc, công nghệ điển hình giải quyết hiệu quả vấn đề mô hình hóa và tối ƣu hóa tổ hợp, đặc biệt là trong lĩnh vực quy hoạch và lập lịch. Lập trình ràng buộc (CP) là một cách tiếp cận mới về giải quyết vấn đề thỏa mãn các ràng buộc và các vấn đề tối ƣu hóa đang đƣợc sử dụng trong nhiều ứng dụng thƣơng mại. 1.2.4.1. Mô Hình Lập Trình Ràng Buộc Hình 1.5. Mô hình CP [5] 1.2.4.2. Phương pháp tiếp cận Lập Trình Ràng Buộc Bessiere, Hebrard, và O'Sullivan [8] sử dụng lập trình ràng buộc để cố gắng giải quyết bài toán cây quyết định nhỏ nhất. 9 Để giải quyết bài toán cây quyết định nhỏ nhất, Bessiere và các cộng sự đề xuất sử dụng một mô hình lập trình ràng buộc. Họ thiết lập một giới hạn trên (ban đầu đƣợc tìm thấy bằng cách sử dụng độ lợi thông tin) trên kích thƣớc của cây quyết định và tìm ra cây nhị phân có số nút ít hơn hoặc bằng giới hạn. Để giải quyết bài toán này, họ tiếp cận bằng cách sử dụng độ lợi thông tin đƣợc nhìn thấy trong thuật toán C4.5 để xây dựng cây từ trên xuống dƣới. Phƣơng pháp tìm kiếm này, cùng với chiến lƣợc khởi động lại, làm cho nó xuất hiện nhƣ thể các cây quyết định nhỏ hơn đáng kể đƣợc tìm thấy. Trong Chƣơng 3, luận văn sẽ đánh giá kích thƣớc của cây quyết định gần tiếp cận đến cây quyết định đƣợc tìm thấy bởi thuật toán C4.5 và chỉ sau khi đã đạt đƣợc một số lợi ích; trình bày chi tiết hơn về hiệu quả của việc chuyển đổi dữ liệu để chứa các thuộc tính nhị phân có trong bài toán, cũng nhƣ trình bày một số kết quả của Bessiere và các cộng sự, và nó có thể chỉ đạt đƣợc bằng cách truyền dữ liệu nhị phân tới thuật toán C4.5. Chƣơng 2 - XÂY DỰNG CÂY QUYẾT ĐỊNH VỚI CHI PHÍ HIỆU QUẢ Trong chƣơng này tôi sẽ đề xuất thuật toán mới, tạm gọi là D4, là một thuật toán học máy có giám sát. Dữ liệu INPUT là một tập các mẫu đƣợc đánh nhãn (ví dụ dữ liệu trong bảng 2.1). Dữ liệu INPUT cho thuật toán sẽ là một tập hợp các bệnh nhân đã đƣợc chẩn đoán dựa trên các xét nghiệm đƣợc tiến hành. Dữ liệu OUTPUT thuật toán D4 là một cây quyết định mô tả một nhóm bệnh nhân có cùng chẩn đoán có cùng kết quả thử nghiệm. Cây quyết định đƣợc sử dụng để chẩn đoán bệnh nhân trong tƣơng lai, dựa vào những kết quả xét nghiệm để tìm ra những bệnh nhân tƣơng tự và phân loại. 10 2.1. GIỚI THIỆU D4 Trong một số mẫu đơn giản, thuật toán D4 là quá trình xử lý quy nạp cây quyết định theo chiều rộng của thuật toán ID3 với việc thêm phƣơng pháp quay lui (backtracking). Thuật toán D4 xuất phát từ công trình của Bessiere và các cộng sự [5] nhằm tối ƣu hóa kích thƣớc của một cây quyết định bằng cách sử dụng lập trình ràng buộc. Thuật toán D4 đƣợc đề xuất nhằm cải thiện mô hình của họ. D4 loại bỏ tổng phí của thƣ viện ràng buộc bằng cách suy ra cấu trúc của cây quyết định trong khi vẫn giữ đƣợc hiệu quả của phƣơng pháp quay lui. 2.2. DỮ LIỆU NHẬP VÀ DỮ LIỆU XUẤT D4 đƣợc thử nghiệm với bộ dữ liệu huấn luyện trong ARFF. Một khi cây quyết định cuối cùng đƣợc xác định, D4 lƣu trữ cây đó nhƣ là một chƣơng trình C++ có thể biên dịch đƣợc. Chƣơng trình C++ lấy tệp CSV và trả về độ chính xác của cây quyết định trên tất cả mẫu thử nghiệm. 2.3. MÔ HÌNH XÂY DỰNG D4 đƣợc chia thành ba phần: Thuật toán D4; Thuật toán GenerateLayer; Thuật toán CostHeuristic. Thuật toán chính D4 tạo các cây mới sau khi tìm kiếm lỗi, thuật toán GenerateLayer xây dựng một cây quyết định duy nhất bằng cách tìm kiếm quay lui theo chiều rộng và thuật toán CostHeuristic cung cấp trọng số cho mỗi thuộc tính. Thuật toán D4 Gọi E là tập hợp các mẫu huấn luyện Gọi A là tập hợp các thộc tính Gọi C là tập hợp các chi phí liên quan đến Gọi N là danh sách mở của các nút trong 11 Gọi UB là giới hạn trên đối với kích thƣớc của cây Gọi UBC là giới hạn trên đối với chi phí của cây function D4 (E, A, C) đƣợc phân loại với Y then if return cây nút đơn với phân loại Y end if for all thuộc tính ai A do end for Sắp xếp các thuộc tính trong A bằng giá trị heuristic hi while X hiện tại < Z tối đa do Tạo nút mới, n, có chứa E và A Thêm n vào danh sách mở N if then kích thƣớc của cây T chi phí dự kiến của cây T end if end while return T end function Thuật toán GenerateLayer Gọi N là danh sách mở của các nút trong Gọi UB là giới hạn trên đối với kích thƣớc của cây Gọi UBC là giới hạn trên đối với chi phí của cây function GenerateLayer(T, N, UB, UBC) while X’ hiện tại < Z’ tối đa do for all n N do 12 Gán thuộc tính a A trong n ngẫu nhiên for all vi Vf do hoặc if hoặc tất cả đều có phân loại tƣơng tự then Thêm nút lá tới N’ và đặt là con của n trong T else for all các thuộc tính ai trong A’ do end for Sắp xếp ai theo giá trị heuristic hi Tạo nút mới, n, có chứa và A’ Thêm n tới danh sách mở N’ và đặt là con của n trong T end if end for end for if Chi phí của T>UBC hoặc Chi phí của T=UBC và kích thƣớc của T>UB then Cập nhật X’, X else if then return T else if return T end if end while return NIL end function then 13 Thuật toán CostHeuristic Gọi E là tập con của các mẫu huấn luyện Gọi A là một thuộc tính Gọi c là chi phí liên quan đến a A function CostHeuristic (a, c, E) return ( ) end function 2.4. TÓM TẮT D4 là một sự mở rộng trực tiếp của thuật toán ID3 và phƣơng pháp quay lui, cho phép sử dụng sự tìm kiếm bất kỳ heuristic, phƣơng pháp lựa chọn thuộc tính, tiêu chuẩn dừng, và các giới hạn trên để thực hiện phƣơng pháp quay lui. Nó cũng rất hữu ích trong việc tìm ra cây quyết định ngoài những cái đƣợc tạo ra bằng cách sử dụng những thuật toán heuristic đơn giản và cho phép các thuộc tính có các chi phí liên quan. Chƣơng 3 - ĐÁNH GIÁ KẾT QUẢ KIỂM THỬ Kiểm thử đầu tiên so sánh cây quyết định đƣợc tạo ra bởi thuật toán D4 và phiên bản đƣợc chỉnh sửa của thuật toán C4.5. Kiểm thử thứ hai xem xét lại kết quả của Bessiere và các cộng sự [8]. Kiểm thử cuối cùng xem xét xu hƣớng trên dữ liệu có các giới hạn kích thƣớc khác nhau. 3.1. DỮ LIỆU Dữ liệu đƣợc sử dụng trong luận văn này lấy từ UCI Machine Learning Repository. 14 3.2. CÂY QUYẾT ĐỊNH CÓ YẾU TỐ CHI PHÍ Phần này bao gồm các kết quả đƣợc tiến hành để tìm xem liệu rằng một cuộc tìm kiếm quay lui trong không gian giải pháp cây quyết định có thể tạo ra các cây quyết định có chi phí thấp hơn dự kiến không. Thực nghiệm so sánh thuật toán C4.5 (với không cắt tỉa: c4.5-m 1 -u -g -f ) đƣợc viết bằng C, với D4 (đƣợc lựa chọn ngẫu nhiên từ ba thuộc tính đầu tiên đã đƣợc giảm thiểu bằng phƣơng pháp tìm kiếm heuristic) đƣợc viết bằng C++ với cùng một thời gian chạy là 30 phút. Sau đó, cây tốt nhất đƣợc D4 tìm thấy tính tới thời điểm đó đƣợc trả về và sử dụng ở mức trung bình. Bảng 3.3: 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. C4.5 Bộ dữ liệu Cleveland Chi Kích phí thƣớc D4 Độ chính xác Chi Kích phí thƣớc Độ chính xác 76,2 390,3 48,5% 76,2 390,3 48,5% Diabetes 8,4 805,0 65,0% 8,4 805 65,0% Hepatitis 4,7 65,4 74,2% 3,5 66,2 77,5% 93,4 333,6 72,5% 93,3 344,2 71,8% 24,5 342,2 60,0% 24,4 345,0 60,6% 157,4 252,6 25,4% 157,4 252,6 25,4% 31,3 3667,0 31,2 3712,2 92,0% 115,7 458,2 30,5% 115,7 458,2 30,5% Heart Hungarian Heart Liver Switzerland Heart Thyroid VA Heart 91,9% 15 3.3. LỢI ÍCH CỦA NHỊ PHÂN 100 90 80 70 60 50 40 30 20 10 0 J48 D4 J48(B) CP J48(P) J48(BP) Hình 3.1: 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. 120 100 80 60 40 20 0 J48 D4 J48(B) CP J48(P) J48(BP) Hình 3.2. 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. 16 Bảng 3.6: 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. Tập dữ liệu Car Income Chess Average % Dữ WEKA liệu CP CP Không Nhị First Best nhị phân phân 5 30,1 24,8 18,5 29,3 23,0 10 46,7 40,2 30,1 46,7 33,8 20 71,0 59,8 47,7 72,8 55,2 30 87,7 74,2 60,1 91,1 64,2 50 114,5 93,3 75,6 117,0 81,5 70 139,2 105,5 86,3 136,1 88,6 90 161,7 115,2 92,0 156,6 92,6 1 185,9 85,1 76,2 150,5 97,9 1,5 265,2 123,6 112,9 208,8 150,3 5 791,0 390,7 364,8 639,1 379,3 1 126,8 81,5 66,6 127,6 93,2 1,5 172,4 119,6 98,9 176,6 139,2 5 434,5 317,2 274,7 449,8 294,8 10 735,3 525,5 458,8 717,7 601,8 240,1 154,0 133,1 222,8 156,8 3.4. ẢNH HƢỞNG CỦA CÁC THUỘC TÍNH NHỊ PHÂN ĐỐI VỚI SỰ ĐA DẠNG CỦA DỮ LIỆU 17 Hình 3.3: Ảnh hƣởng của việc chuyển đổi các thuộc tính sang dạng nhị phân. Bảng 3.7: So sánh kích thƣớc cây quyết định giữa các thuộc tính dạng nhị phân và không phải dạng nhị phân trên một loại dữ liệu D4 không cắt tỉa D4 tối thiểu WEKA có cắt tỉa Không Dạng Không Dạng Không Dạng phải nhị phải nhị phải nhị dạng phân dạng phân dạng phân nhị nhị nhị phân phân phân 4f4v10 13 9 5 9 1 7 4f4v100 117 95 53 95 13 17 4f4v1000 341 457 337 457 33 73 4f4v10000 341 509 341 509 105 117 4f2-5v10 10 9 10 9 1 5 4f2-5v100 83 95 73 95 10 13 4f2-5v1000 184 221 184 221 35 59 4f2-5v10000 194 237 194 237 61 91 4f8v10 25 11 1 11 1 1 4f8v100 217 93 33 93 1 33 4f8v1000 1793 931 305 931 25 163 4f8v10000 4681 6205 2737 6205 209 1049 4f2-10v10 19 7 9 7 1 5 4f2-10v100 181 105 131 105 1 11 4f2-10v1000 681 767 629 767 65 119 1019 1237 1019 1237 225 325 4f210v10000 18 Cột đầu tiên bên trái mô tả về các dữ liệu đang đƣợc sử dụng. Mã 4f 4v 10e nghĩa là dữ liệu này có 4 thuộc tính, 4 giá trị cho mỗi thuộc tính và 10 mẫu, còn 2-5v cho thấy phạm vi các giá trị. Bảng đƣợc chia thành ba mục: D4 không kèm theo số mẫu tối thiểu cần thiết cho một lá và không cắt tỉa, D4 kèm theo số mẫu tối thiểu cần thiết cho một lá và không cắt tỉa, và các cài đặt cắt tỉa mặc định của WEKA J48. Trong mỗi mục này có hai cột thể hiện dữ liệu bình thƣờng và dữ liệu đƣợc chuyển sang các thuộc tính nhị phân bằng cách sử dụng phƣơng pháp mà Bessiere [8] đã áp dụng. Ba cột này nhằm cho thấy cây quyết định nhị phân thƣờng nhỏ hơn các cây quyết định không nhị phân tƣơng ứng. Khi đòi hỏi một số lƣợng tối thiểu các mẫu trong một lá, các cây quyết định nhị phân không còn nhỏ hơn nữa, vì các cây không nhị phân không có lá nào trống. Điều này sẽ loại bỏ các lá trống và thu nhỏ kích thƣớc của cây quyết định đƣợc xây dựng trên dữ liệu có thuộc tính không ở dạng nhị phân. Trong thực nghiệm này chỉ có thuộc tính tốt nhất đƣợc kiểm tra nhƣ thuật toán heuristic đã xác định, D4 không thực hiện tìm kiếm hoặc quay lui. Bảng 3.8: So sánh kích thƣớc cây quyết định giữa các thuộc tính dạng nhị phân và không phải dạng nhị phân trên một loại dữ liệu. Tiếp tục bảng 3.7 với 10 thuộc tính thay vì 4 thuộc tính. 10f4v10 10f4v100 D4 không cắt tỉa D4 tối thiểu WEKA có cắt tỉa Không Dạng Không Dạng Không Dạng phải nhị phải nhị phải nhị dạng phân dạng phân dạng phân nhị nhị nhị phân phân phân 9 5 5 5 5 3 101 63 69 63 21 41