phần mở đầu, kết luận, mục lục, danh mục bảng, hình và tài liệu tham khảo, luận văn gồm 3 chƣơng nội dung chính, trong đó: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Chƣơng 1: Tổng quan về mô hình cây quyết định và thông tin không chắc chắn sẽ giới thiệu một số khái niệm và vấn đề chung nhất về những vấn đề này. Cụ thể Chƣơng I sẽ giới thiệu khái niệm về cây quyết định, phân loại cây quyết định, ƣu nhƣợc điểm của cây quyết định trong việc giải quyết bài toán về phân loại, ra quyết định và phƣơng pháp xây dựng cây quyết định. Chƣơng 1 cũng giới thiệu khái niệm, phân loại, cách biểu diễn và ứng dụng của thông tin không chắc chắn. Đó là những kiến thức cơ bản nhất, làm cơ sở để tìm khảo cứu và ứng dụng mô hình cây quyết định trong việc xử lý thông tin không chắc chắn nhằm hỗ trợ quá trình lập kế hoạch phát triển sản xuất kinh doanh doanh nghiệp ở các chƣơng tiếp sau.
Chƣơng 2: Công cụ hỗ trợ xây dựng mô hình cây quyết định và lập kế hoạch sản xuất kinh doanh doanh nghiệp sẽ trình bầy tóm lƣợc nội dung và quá trình ra quyết định với thông tin không chắc chắn; giới thiệu PrecisionTree 5.7, là công cụ đƣợc luận văn sử dụng để xây dựng cây quyết định nhằm xử lý thông tin không chắc chắn, hỗ trợ quá trình ra quyết định trong việc lập kế hoạch. Chƣơng này cũng trình bày khái niệm, lợi ích, quy trình, phân loại các hoạt động lập kế hoạch, các yếu tố chính tác động đến hoạt động lập kế hoạch và một số nội dung chủ yếu cần đƣợc ra quyết định trong quá trình lập kế hoạch sản xuất kinh doanh của doanh nghiệp. Nhƣ đã biết, công việc của các nhà lập kế hoạch trƣớc hết phải đánh giá đƣợc tính chất và mức độ không chắc chắn của môi trƣờng kinh doanh để xác định giải pháp phản ứng của doanh nghiệp, xây dựng và triển khai các kế hoạch thích hợp. Luận văn khảo cứu quá trình lập kế hoạch sản xuất kinh doanh doanh nghiệp và đề xuất ứng dụng mô hình cây quyết định trong quá trình đó.
Chƣơng 3: Ra quyết định với thông tin không chắc chắn trong lập kế hoạch sản xuất kinh doanh của doanh nghiệp sẽ trình bầy việc ứng dụng mô hình cây quyết định trong lập kế hoạch sản xuất kinh doanh dựa trên tập dữ liệu giả định và trên tập dữ liệu thực tế đƣợc thu thập từ Công ty cổ phần May Thăng Long. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 CHƢƠNG 1: TỔNG QUAN VỀ MÔ HÌNH CÂY QUYẾT ĐỊNH VÀ THÔNG TIN KHÔNG CHẮC CHẮN Chƣơng này giới thiệu tổng quan về mô hình cây quyết định và thông tin không chắc chắn. Luận văn trƣớc hết trình bày lý thuyết chung nhất về cây quyết định nhƣ giới thiệu cây quyết định, phân loại, xây dựng và ứng dụng của cây quyết định. Sau đó trình bày về thông tin không chắc chắn, gồm khái niệm cơ bản, các cách biểu diễn thông tin không chắc chắn với lý thuyết xác suất, định lý Bayes, lý thuyết về yếu tố chắc chắn Standford và tập mờ.1 Tổng quan về mô hình cây quyết định 1.1 Giới thiệu cây quyết định 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[3,12].
Mỗi một nút trong (internal nút) 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ự báo 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 là 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 đó. 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. 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[12]. Hình 1 dƣới đây thể hiện mô hình cây quyết định có cấu trúc dạng cây ở đó: - nút lá đƣợc gán nhãn tƣơng ứng với lớp của dữ liệu, - nút trong đƣợc tích hợp với điều kiện kiểm tra để rẽ nhánh. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 Hình 1: Cây quyết định cho tập dữ liệu weather Mô hình cây quyết định trong hình 1 đƣợc xây dựng từ việc học trên tập dữ liệu weather [3, 12] để dự báo chơi hay không chơi golf (yes hay no) dựa trên các thuộc tính outlook, temperature, humidity và windy. Mô hình rất dễ hiểu bởi vì ta có thể rút trích luật quyết định tƣơng ứng với nút lá có dạng IF-THEN đƣợc tạo ra từ việc thực hiện AND trên các điều kiện theo đƣờng dẫn từ nút gốc đến nút lá.
Các luật quyết định dễ hiểu với ngƣời sử dụng. Giải thuật học cây quyết định gồm 2 bƣớc lớn: xây dựng cây (Top-down), cắt nhánh (Bottom-up) để tránh học vẹt. Quá trình xây dựng cây đƣợc làm nhƣ sau: - Bắt đầu nút gốc, tất cả các dữ liệu học ở nút gốc, - Nếu dữ liệu tại 1 nút có cùng lớp thì nút đƣợc cho là nút lá, nhãn của nút lá là nhãn của các phần tử trong nút lá (hay luật bình chọn số đông nếu nút lá có chứa các phần tử có lớp khác nhau), - Nếu dữ liệu ở nút quá hỗn loạn (các phần tử có lớp rất khác nhau) thì nút đƣợc cho là nút trong, tiến hành phân hoạch dữ liệu một cách đệ quy bằng việc chọn 1 thuộc tính để thực hiện phân hoạch tốt nhất có thể. Quá trình xây dựng cây chủ yếu phụ thuộc vào việc chọn thuộc tính tốt nhất để phân hoạch dữ liệu.
Chọn thuộc tính phân hoạch tốt theo nghĩa, cho ra kết quả là cây nhỏ nhất. Việc lựa chọn này dựa vào các heuristics: chọn thuộc tính sinh ra các nút thuần khiết nhất. Giải thuật học cây quyết định tiêu biểu C4.5 của Quinlan [12] sử dụng entropy của Shannon để đánh giá sự hỗn loạn thông tin. Theo nhƣ hình 2, độ hỗn loạn đạt cực đại khi phân phối xác suất của lớp bằng nhau (bài toán 2 lớp, thì giá trị 0.
Nhƣng nếu tỉ lệ dữ liệu đã biết là lệch nhau, chẳng hạn ta có 10% là lớp dƣơng (pos) và 90% là lớp âm (neg), thì tại một nút khi phân hoạch, độ hỗn loạn nên đạt cực đại khi biết xác suất của lớp dƣơng là 0.1 chứ không phải là 0. Đây là yếu điểm của việc dùng hàm entropy khi xử lý dữ liệu không cân bằng về lớp, trong khi thực tế, dữ liệu thƣờng mất cân bằng. Vì lý do đó những LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Hình 2: Hàm entropy của Shannon năm gần đây ngƣời ta tập trung nghiên cứu đề xuất thay thế hàm phân hoạch cây quyết định entropy bằng bằng hàm khoảng cách Kolmogorov-Smirnov để xử lý tốt hơn cho dữ liệu không cân bằng [10-11]. Có thể nói cây quyết định đƣợ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.
Cây quyết định giúp biến một biểu diễn dữ liệu phức tạp thành một cấu trúc đơn giản hơn rất nhiều. Các cây quyết định thƣờng đƣợc sử dụng trong hoạt động nghiên cứu và ứng dụng nhƣ trong phân tích quyết định, giúp xác định một chiến lƣợc có khả năng đạt đƣợc một mục tiêu hay không,. Mô hình cây quyết định hỗ trợ quá trình ra quyết định là mô hình cây quyết định ở đó có phƣơng tiện để tính toán xác suất có điều kiện và/hoặc mô tả việc thực hiện ra quyết định [14]. Ví dụ, một tổ chức tín dụng xác định đối tƣợng khách hàng cho vay nhƣ sau: Nếu khách hàng có dƣ nợ tại tổ chức lớn hơn hoặc bằng một giá trị nào đó (n) theo quy định thì không cho vay, trong trƣờng hợp ngƣợc lại, nếu khách hàng có thu có khả năng trả nợ thì mới cho vay.
Cây quyết định có thể đƣợc tạo ra nhƣ sau: Hình 3: Cây quyết định hỗ trợ ra quyết định LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 Trong cây này: - Gốc: là nút trên cùng của cây, từ đó sinh ra các nhánh. - Nút trong: biểu diễn một kiểm tra trên một thuộc tính đơn (hình tròn). - Nhánh: biểu diễn các kết quả của kiểm tra trên nút trong (cạnh). - Nút lá: biểu diễn lớp hay sự phân phối lớp (hình tam giác).
Để ra quyết định với mẫu dữ liệu thu đƣợc, 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à biểu diễn dự báo giá trị để có quyết định cuối cùng cho dữ liệu mẫu.2 Các kiểu cây quyết định Theo tiêu chí phân loại dựa vào giá trị thuộc tính của cây, cây quyết định đƣợc chia thành 2 loại chính: 1.1 Cây hồi quy: ƣớc lƣợng các hàm giá có giá trị là số thực thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. Giá trị thuộc tính liên tục A cần đƣợc rời rạc hóa trong cây quyết định. Với các cách tiếp cận thông thƣờng: ta coi thuộc tính chỉ có một cách rời rạc trong khoảng [ - ∞,t] , [t,+∞].
Cần lựa chọn ngƣỡng t: để với mỗi trƣờng hợp của t tính toán độ tăng thông tin của A do sự rời rạc của t. Chọn t với độ tăng thông tin lớn nhất (t có thể biến đổi với các trƣờng hợp của A trên cây). Các giá trị của t đƣợc xem xét: giá trị của A trong một số trƣờng hợp của dữ liệu [3,8]. Nói cách khác 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.