Xu Hướng 2/2023 # Cây Quyết Định Và Giải Thuật Id3 # Top 4 View | Bac.edu.vn

Xu Hướng 2/2023 # Cây Quyết Định Và Giải Thuật Id3 # Top 4 View

Bạn đang xem bài viết Cây Quyết Định Và Giải Thuật Id3 được cập nhật mới nhất trên website Bac.edu.vn. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất.

Giới thiệu về cây quyết định

Trong lý thuyết quyết định (chẳng hạn quản lí rủi ro), một cây quyết định (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.

Trong lĩnh vực máy học (Learning Machine), 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 máy học 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 đó. 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.

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 đó

Giới thiệu giải thuật ID3

Giải thuật ID3 (gọi tắt là ID3) Được phát triển đồng thời bởi Quinlan trong AI và Breiman, Friedman, Olsen và Stone trong thống kê. ID3 là một giải thuật học đơn giản nhưng tỏ ra thành công trong nhiều lĩnh vực. ID3 là một giải thuật hay vì cách biểu diễn tri thức học được của nó, tiếp cận của nó trong việc quản lý tính phức tạp, heuristic của nó dùng cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối với việc xử lý dữ liệu nhiễu.

ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết định (decision tree). Biểu diễn này cho phép chúng ta xác định phân loại của một đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó.

Như vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ một tập các ví dụ rèn luyện (training example) hay còn gọi là dữ liệu rèn luyện (training data).

Input: Một tập hợp các ví dụ. Mỗi ví dụ bao gồm các thuộc tính mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó.

Output: Cây quyết định có khả năng phân loại đúng đắn các ví dụ trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng cho cả các ví dụ chưa gặp trong tương lai.

Giải thuật ID3 xây dựng cây quyết định được trình bày như sau:

thuộc tính quyết định “tốt nhất” cho nút kế tiếp3. Với mỗi giá trị của A, tạo nhánh con mới của 4. Phân loại các mẫu huấn luyện cho các nút lá 2. Gán A là thuộc tính quyết định cho 5. Nếu các mẫu huấn luyện được phân loại hoàn toàn thì NGƯNG, Ngược lại, lặp với các nút lá mới.

Tri thức dạng luật

Tri thức được biểu diễn dưới dạng luật:

IF Điều kiện 1 ^ Điều kiện 2… THEN Kết luận

Dễ hiểu với con người, được sử dụng chủ yếu trong các hệ chuyên gia

Rút luật từ cây quyết định: đi từ nút gốc đến nút lá, lấy các phép thử làm tiền đề và phân loại của nút lá làm kết quả

Lưu ý: Một phiên bản khác của thuật toán ID3 sử dụng Informatic Gain thay cho entropy để chọn thuộc tính quyết định. Công thức tính Informatic Gain như sau:

Gain(A) = Entropy(S) – Entropy(A)

Trong đó: S là tập mẫu và A là một thuộc tính. Entropy(S): độ hỗn loạn của tập S.

Entropy(A): độ hỗn loạn trung bình của thuộc tính A (cách tính như trên)

Thuật Toán Cây Quyết Định C4.5

Thuật toán cây quyết định

Thuật toán cây quyết định cho ra kết quả là một tập luật của những dữ liệu huấn luyện có thuộc tính. Cây quyết định là một công cụ phổ biến trong khai phá và phân lớp dữ liệu Đặc điểm của cây quyết định: là một cây có cấu trúc, trong đó:

Root (Gốc): Là nút trên cùng của cây.

Node trong: nút trung gian trên một thuộc tính đơn (hình Oval).

Nhánh: Biểu diễn các kết quả của kiểm tra trên nút.

Node lá: Biểu diễn lớp hay sự phân phối lớp (hình vuông hoặc chữ nhật)

Phát triển cây quyết định: đi từ gốc, đến các nhánh, phát triển quy nạp theo hình thức chia để trị.

Bước 1. Chọn thuộc tính “tốt” nhất bằng một độ đo đã định trước

Bước 2. Phát triển cây bằng việc thêm các nhánh tương ứng với từng giá trị của thuộc tính đã chọn

Bước 3. Sắp xếp, phân chia tập dữ liệu đào tạo tới node conbước 4. Nếu các ví dụ được phân lớp rõ ràng thì dừng.

Ngược lại: lặp lại bước 1 tới bước 4 cho từng node con

Cắt tỉa cây: nhằm đơn giản hóa, khái quát hóa cây, tăng độ chính xác

Thuật toán Hunt sử dụng trong C4.5, CDP,… S={S1,S2,…,Sn} là tập dữ liệu đào tạo

C={C1,C2,…,Cm} là tập các lớp

Trường hợp 2: S thuộc về nhiều lớp trong C.

Chọn 1 test trên thuộc ơnh đơn có nhiều giá trị O={O1,..Ok} (k thường bằng 2).

Đánh giá thuật toán cây quyết định trong lĩnh vực khai phá dữ liệu

Thuận lợi:

Quá trình xây dựng cây quyết định không dùng kiến thức về lĩnh vực dữ liệu đang nghiên cứu hoặc thông số đầu vào nào.

Kết quả của quá trình huấn luyện (học) được biểu diễn dưới dạng cây nên dễ hiểu và gần gũi với con người.

Nhìn chung, các giải thuật cây quyết định cho kết quả có độ chính xác khá cao.

Khó khă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 dựa 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.

Khi dùng độ lợi thông tin (Information Gain) để xác định thuộc tính rẽ nhánh, các thuộc tính có nhiều giá trị thường được ưu tiên chọn.

Thuật toán C4.5

Là sự phát triển từ CLS và ID3.

ID3 (Quinlan, 1979)‐ 1 hệ thống đơn giản ban đầu chứa khoảng 600 dòng lệnh Pascal

Năm 1993, J. Ross Quinlan phát triển thành C4.5 với 9000 dòng lệnh C.

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 mỗi node trong quá trình phát triển cây quyết định. C4.5 còn chứa một kỹ thuật cho phép biểu diễn lại cây quyết định dưới dạng một danh sách sắp thứ tự các luật if-then (một dạng quy tắc phân lớp dễ hiểu). Kỹ thuật này cho phép làm giảm bớt kích thước tập luật và đơn giản hóa các luật mà độ chính xác so với nhánh tương ứng cây quyết định là tương đương.

Tư tưởng phát triển cây quyết định của C4.5 là phương pháp Hunt đã nghiên cứu ở trên. Chiến lược phát triển theo độ sâu (depth-first strategy) được áp dụng cho C4.5.

Mã giả của thuật toán C4.5:

Pseudocode:

· Kiểm tra case cơ bản

· Với mỗi thuộc tính A tìm thông tin nhờ việc tách thuộc tính A

· Chọn a_best là thuộc tính mà độ đo lựa chọn thuộc tính “tốt nhất”

· Dùng a_best làm thuộc tính cho node chia cắt cây.

· Đệ quy trên các danh sách phụ được tạo ra bởi việc phân chia theo a_best, và thêm các node này như là con của node

(1) ComputerClassFrequency(T); (2) if OneClass or FewCases return a leaf; Create a decision node N; (3) ForEach Attribute A ComputeGain(A); (4) N.test=AttributeWithBestGain; (5) if (N.test is continuous) find Threshold; (6) ForEach T’ in the splitting of T (7) If ( T’ is Empty ) Child of N is a leaf else (8) Child of N=FormTree(T’); (9) ComputeErrors of N; return N

C4.5 có những đăc điểm khác với các thuật toán khác, đó là: cơ chế chọn thuộc tính để kiểm tra tại mỗi node, cơ chế xử lý với những giá trị thiếu, việc tránh “quá vừa” dữ liệu, ước lượng độ chính xác và cơ chế cắt tỉa cây.

C4.5 dùng Gain-entropy làm độ đo lựa chọn thuộc tính “tốt nhất”.

Phần lớn các hệ thống đều cố gắng để tạo ra một cây càng nhỏ càng tốt, vì những cây nhỏ hơn thì dễ hiểu hơn và dễ đạt được độ chính xác dự đoán co hơn. 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.

Hai độ đo được sử dụng trong C4.5 là information gain và gain ratio. RF(Cj,S) biểu diễn tần xuất (Relative Frequency) các case trong S thuộc về lớp Cj.

Sau khi S được phân chia thành các tập con S1, S2,…, St bởi test B thì information gain được tính bằng:

Tuy nhiên có một vấn đề khi sử dụng G(S,B) ưu tiên test có số lượng lớn kết quả, ví dụ G(S,B) đạt cực đại với test mà từng Si chỉ chứa một case đơn. Tiêu chuẩn gain ratio giải quyết được vấn đề này bằng việc đưa vào thông tin tiềm năng (potential information) của bản thân mỗi phân hoạch.

Chuyển đổi sang luật: cắt tỉa cây

Dạng luật: if A and B and C… then class X. Không thỏa mãn điều kiện chuyển về lớp mặc định.

Xây dựng luật: 4 bước

Mỗi đường đi từ gốc đến lá là một luật mẫu. Đơn giản luật mẫu bằng cách bỏ dần điều kiện mà không ảnh hưởng tới độ chính xác của luật.

Các luật đã cắt tỉa được nhóm lại theo giá trị phân lớp tạo ra các tập Với mỗi tập con, xem xét để lựa chọn luật để tối ưu hóa độ chính xác dự đoán của lớp gắn với tập luật đó.

Sắp xếp các tập luật trên theo tần số lỗi. Lớp mặc định được tạo ra bằng cách xác định các case trong tập S không chứa trong các luật hiện tại và chọn lớp phổ biến nhất trong các case đó làm lớp mặc định.

Ước lượng đánh giá: các luật được ước lượng trên toàn tập S, loại bỏ luật làm giảm độ chính xác của sự phân lớp.

Hoàn thành: 1 tập các quy tắc đơn giản được lựa chọn cho mỗi lớp

Cây Quyết Định (Decision Tree) Là Gì? Ví Dụ Về Cây Quyết Định

Khái niệm

Cây quyết định trong tiếng Anh là Decision tree.

Cây quyết định là một phương tiện hỗ trợ cho việc ra quyết định trong điều kiện bất định. Nó chỉ ra nhiều đường lối hàng động khác nhau và hậu quả kinh tế của mỗi đường lối. Thông thường, mỗi đường lối hành động được gắn với một xác suất chủ quan về khả năng phát sinh các sự kiện trong tương lai.

Ví dụ về cây quyết định

Căn cứ vào Cây quyết định trên, người bán lẻ có hai phương án hành động là mở cửa hàng và không mở cửa hàng. Anh ta phải cân nhắc hai trạng thái tự nhiên, tức hai sự kiện có thể xảy ra: nền kinh tế phát triển mạnh hoặc suy thoái.

Người bán lẻ phải đánh giá khả năng xuất hiện mỗi sự kiện và trong tình huống này, anh ta dựa trên kinh nghiệm và hiểu biết để nhận định rằng khả năng xuất hiện mỗi sự kiện bằng 50%. Cuối cùng, người bán lẻ ước tính hậu quả tài chính là nếu mở cửa hàng sẽ có lãi 40.000 đồng khi kinh tế phát triển mạnh và lỗ 30.000 đồng nếu có suy thoái.

Để ra quyết định, người bán lẻ cần một tiêu chuẩn ra quyết định cho phép anh ta lựa chọn phương án hành động tốt nhất trong các phương án có thể có. Vì sự lựa chọn này gắn với yếu tố rủi ro, nên chúng ta cần biết thái độ của người bán lẻ đối với rủi ro.

Nếu người bán lẻ không chú ý đến rủi ro, chúng ta có thể tính toán tính xác định tương đương với hành vi “mở cửa hàng” bằng cách căn cứ vào hậu quả tài chính của mỗi kết cục và gia quyền nó theo xác suất xuất hiện của nó. Ví dụ:

Kết cục này chắc chắn lớn hơn 0 trong trường hợp không mở cửa hàng và nó biện minh cho việc tiếp tục thực hiện dự án này.

Song nếu người bán lẻ là người ghét rủi ro, tiêu chuẩn giá trị bằng tiền có thể không phải là tiêu chuẩn thích hợp, vì anh ta cần nhận được phần thưởng cho sự rủi ro để chấp nhận hành động. Việc tận dụng tiêu chuẩn cẩn thận hơn tiêu chuẩn tương đương với tính xác định sẽ làm giảm tiêu chuẩn tương đương với tính xác định của nhánh “mở cửa hàng” và điều này cũng dẫn đến quyết định tiếp tục mở cửa hàng.

Cây Quyết Định (Cart) Datai@Sg

1. Giới thiệu

Phân loại (classification) là một quá trình gồm hai bước, bước học tập và bước dự đoán, trong học máy. Trong bước học tập, mô hình được xây dựng dựa trên dữ liệu đào tạo (training data). Trong bước dự đoán, mô hình được sử dụng để dự đoán đáp ứng với dữ liệu đã cho. Cây quyết định (decision tree) là một trong những thuật toán phân loại phổ biến, dễ hiểu và dễ giải thích.

1.1 Cây quyết định là gì?

Cây quyết định là một trong những thuật toán học máy phổ biến và mạnh mẽ mà tôi đã học. Đây là một phương pháp học có giám sát, có thể được sử dụng cho cả nhiệm vụ phân loại (classification) và hồi quy (regression).

Mục tiêu là tạo ra một mô hình dự đoán giá trị của biến mục tiêu (target variable) bằng cách học các quy tắc quyết định đơn giản được suy ra từ các đặc trưng dữ liệu (data features).

Không giống như các thuật toán hộp đen (black box) như Mạng thần kinh (Neural Network), Cây quyết định tương đối dễ hiểu hơn vì nó chia sẻ logic ra quyết định một cách rõ ràng.

1.2 Tại sao sử dụng cây quyết định?

Mặc dù thực tế là nhiều nhà khoa học dữ liệu (data scientists) tin rằng đó là một phương pháp cũ và họ có thể nghi ngờ về tính chính xác của nó do vấn đề quá mức (overfitting). Tuy nhiên, các mô hình mạnh mẽ như Random forest (bagging method), gradient boosting (boosting method) và XGBoost (boosting method) đang được sử dụng phổ biến trong tất cả các loại vấn đề khoa học dữ liệu, chúng đều được xây dựng dựa trên thuật toán cây quyết định. Do đó, các khái niệm và thuật toán đằng sau Cây quyết định rất đáng để hiểu!

1.3 Các loại cây quyết định

Cây quyết định biến phân loại (Categorical Variable Decision Tree): Cây quyết định có biến mục tiêu phân loại thì nó được gọi là cây quyết định biến phân loại.

Ví dụ: dữ liệu ở đây của ta có dạng YES/NO

Cây quyết định biến liên tục (Continuous Variable Decision Tree): Cây quyết định có biến mục tiêu liên tục thì nó được gọi là cây quyết định biến liên tục

Ví dụ: dữ liệu ở đây của ta có dạng các giá trị liên tục như giá nhà

1.4 Các thuật toán cây quyết định

Có 4 loại thuật toán cây quyết định phổ biến:

ID3

CART

Chi-Square

Reduction in Variance

⟹Trong bài này, chúng ta sẽ chỉ tập trung vào cây phân loại và các giải thích về CART

2. Thuật toán CART

2.1 CART là gì?

CART hay Classification and regression tree (cây phân loại và hồi quy) là một thuật toán cây quyết định, được giới thiệu bởi Leo Breiman. Nó có thể giải quyết cả hai vấn đề phân loại và hồi quy.

Để trực quan hơn, ở đây ta lấy ví dụ về cây phân loại để dự đoán sô người có thể sống sót sau vụ chìm tàu Titanic

Nhìn một cách đơn giản, nó chính là một tập các IF-ELSE, là kết quả của quá trình đào tạo dữ liệu bằng cây quyết định.

2.2 Cách hoạt động của CART

CART thường sử dụng phương pháp Gini để tạo các điểm phân chia.

Gini impurity

Là phương pháp hướng đến đo lường tần suất một đối tượng dữ liệu ngẫu nhiên trong tập dữ liệu ban đầu được phân loại không chính xác, trên cơ sở đối tượng dữ liệu đã nằm trong một tập con được phân ra từ tập dữ liệu ban đầu, có dán nhãn thể hiện thuộc tính chung bất kỳ của các đối tượng còn lại trong tập con này, giá trị phân loại chính là nhãn của tập con.

Gini impurity chính là chỉ số đo lường mức độ đồng nhất hay nhiễu loạn của thông tin, hay sự khác biệt về các giá trị mà mỗi điểm dữ liệu trong một tập con, hoặc một nhánh của cây quyết định. Công thức Gini có thể dùng cho cả dữ liệu rời rạc và liên tục. Nếu điểm dữ liệu thuộc về một node và có chung thuộc tính bất kỳ thì node này thể hiện sự đồng nhất lúc này gini=0gini=0 và ngược lại gini sẽ lớn.

Công thức tổng quát của Gini:

Công thức trên để tính độ vẩn đục của một node, khi có nhiều cách phân nhánh mỗi cách có thể phân ra một số node nhất định. Cho nên, lúc này có thêm công thức thứ 2 để tìm ra các phân chia tối ưu nhất:

Trong đó:

 là số điểm dữ liệu có trong node của nhánh được phân

 là số điểm dữ liệu có trong node được dùng để phân nhánh

Hệ số 

 càng nhỏ thì cách phân nhánh đó càng tối ưu.

càng nhỏ thì cách phân nhánh đó càng tối ưu.

Bài toán

Dựa vào bộ dữ liệu trên, ta sẽ sử dụng Gini để xây dựng cây quyết định.

Gini của thuộc tính outlook = sunny:

Từ đó có được 

của thuộc tính outlook sẽ bằng:

của thuộc tính outlook sẽ bằng:

Lần lượt, sẽ được giá trị GiniGini của các thuộc tính còn lại:

Như vậy, thấy rằng thuộc tính outlook sẽ có giá trị 

 nhỏ nhất cho nên chọn làm root node. Sau khi chọn được root node, dữ liệu sẽ được rút gọn lại như sau:

nhỏ nhất cho nên chọn làm root node. Sau khi chọn được root node, dữ liệu sẽ được rút gọn lại như sau:

Tiếp tục phân chia theo các thuộc tính còn lại:

Như vậy thuộc tính tiếp theo được chọn là child node là humidity, tương tự các bước sau vẫn được làm như vậy.

Kết quả của 

 cho ví dụ trên sẽ cho ra một cây như sau:

2.3 Overfitting và Underfitting trong CART

Nhắc lại một chút, overfitting có nghĩa là chúng ta cố gắn fit các dữ liệu một cách cực kì chính xác trong tập train, tuy nhiên nó sẽ dự đoán sai khi đưa dữ liệu vào test. Underfitting thì ngược lại, ta train một đường phân loại khá đơn giản, nó sẽ không chính xác trong cả tập train và tập test.

Overfitting xảy ra khi độ sâu của cây là quá lớn

Underfitting xảy ra khi cây khá ngắn

cho ví dụ trên sẽ cho ra một cây như sau:

⟹Để hạn chế vấn đề underfitting và overfitting, ta có một kỹ thuật gọi là Tiêu chuẩn dừng (Stop criterion)

2.4 Tiêu chuẩn dừng

Nếu chúng ta tiếp tục phát triển cây cho đến khi mỗi nút lá tương ứng với tạp chất thấp nhất, thì dữ liệu thường được cung cấp quá mức (overfitting).

Nếu việc chia tách bị dừng quá sớm, lỗi về dữ liệu huấn luyện không đủ cao và hiệu suất sẽ bị ảnh hưởng do bias (underfitting).

Do đó, việc ngăn chặn overfitting và underfitting là mấu chốt trong khi mô hình hóa Cây quyết định và nó có thể được thực hiện theo 2 cách:

Đặt các ràng buộc về kích thước cây:

Cung cấp số lượng mẫu tối thiểu để phân chia nút.

Triển khai số lượng mẫu tối thiểu cho một nút lá (leaf node).

Cho phép độ sâu tối đa của cây (độ sâu dọc).

Số lượng terminal node tối đa.

Các tính năng tối đa để xem xét cho sự phân chia.

Tỉa cây (Tree pruning):

Tỉa cây là một kỹ thuật trong học máy giúp giảm kích thước của Cây quyết định bằng cách loại bỏ các phần của cây. Nó cũng làm giảm độ phức tạp của phân loại cuối cùng và do đó cải thiện độ chính xác dự đoán bằng cách giảm overfitting.

Tỉa cây có thể được thực hiện theo hai cách:

Pre-prunning:

Dừng phân tách nút hiện tại nếu nó không cải thiện entropy bằng ít nhất một số giá trị (ngưỡng) được đặt trước.

Dừng phân vùng nếu số lượng điểm dữ liệu ít hơn một số giá trị đặt trước (ngưỡng).

Giới hạn độ sâu của cây đối với một số giá trị được đặt trước (ngưỡng).

Post-prunning:

Điều này có thể được thực hiện bằng cách trước tiên cho phép cây phát triển hết tiềm năng và sau đó tỉa cây ở mỗi cấp sau khi tính toán độ chính xác chéo ở mỗi cấp.

3. Demo đơn giản

Tiếp theo, ta sữ dụng thư viện sklearn để dào tạo mô hình cây quyết định dựa trên dữ liệu hoa Iris.

from sklearn.tree import DecisionTreeClassifier from sklearn import datasets import numpy as np from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler iris = datasets.load_iris() #2: petal length #3: petal width X = iris.data[:, [2, 3]] y = iris.target

X_train, X_test, y_train, y_test = train_test_split( X, y, test_size=0.3, random_state=1, stratify=y)

Như đã đề cập, CART cũng có thể xử lý vấn đề hồi quy bằng cách sử dụng một tiêu chí phân tách khác: Lỗi bình phương trung bình (MSE) để xác định các điểm phân tách. Biến đầu ra của Cây hồi quy là số và các biến đầu vào cho phép kết hợp các biến liên tục và biến phân loại.

4. Kết luận

4.1 Ưu điểm của CART

Cây quyết định có thể thực hiện phân loại đa lớp.

Cung cấp hầu hết khả năng diễn giải mô hình bởi vì chúng đơn giản như là một loạt các điều kiện if-else.

Có thể xử lý cả dữ liệu số và dữ liệu phân loại.

Mối quan hệ phi tuyến (Nonlinear relationships) giữa các tính năng không ảnh hưởng đến hiệu suất của Cây quyết định.

4.2 Nhược điểm của CART

Nhược điểm lớn nhất của Cây quyết định là vấn đề Overfitting.

Một thay đổi nhỏ trong bộ dữ liệu có thể làm cho cấu trúc cây không ổn định có thể gây ra phương sai.

Cây quyết định có thể bị underfit nếu dữ liệu mất cân bằng. Do đó, nên cân bằng tập dữ liệu trước khi phù hợp với Cây quyết định.

4.3 Chuẩn bị dữ liệu cho CART

Việc phân chia các đặc trưng dạng số (splitting of numerical features) có thể được thực hiện bằng cách sắp xếp các đặc trưng theo thứ tự tăng dần và thử từng giá trị làm điểm ngưỡng, sau đó tính toán mức tăng thông tin cho từng giá trị làm ngưỡng. Cuối cùng, nếu giá trị đó thu được bằng với ngưỡng mang lại giá trị Gini Impurity tối thiểu thì hoan hô!!

Đặc trưng chia tỷ lệ (Feature scaling) (tiêu chuẩn hóa cột) không cần thiết để thực hiện trong các cây quyết định. Tuy nhiên, nó giúp với việc hiển thị / thao tác dữ liệu và có thể hữu ích nếu bạn có ý định so sánh hiệu suất với dữ liệu khác hoặc các phương pháp khác như SVM.

Để xử lý các đặc trưng dạng phân loại (categorical features) trong Cây quyết định, chúng ta không bao giờ phải thực hiện one hot encoding trên một biến phân loại vì hầu hết các thư viện có thể tự động xử lý các biến phân loại. Chúng ta vẫn có thể gán một số cho mỗi biến nếu muốn.

Lớp không cân bằng (Imbalanced class) có tác động bất lợi đến cấu trúc cây, do đó có thể tránh được bằng cách sử dụng upsampling hoặc bằng cách sử dụng downsampling tùy thuộc vào tập dữ liệu.

Hạn chế việc có quá nhiều đặc trưng (high dimensionality) vì nó có thể có tác động xấu đến cấu trúc của cây.

Các ngoại lệ (Outliers) cũng tác động đến cấu trúc của cây vì độ sâu của cây có thể làm tăng các ngoại lệ.

5. Tài liệu tham khảo

https://towardsdatascience.com/decision-trees-d07e0f420175

https://towardsdatascience.com/decision-tree…

https://www.vebuso.com/2020/01/decision-tree…

https://www.digitalvidya.com/blog/classification…

https://www.youtube.com/watch?v…

Cập nhật thông tin chi tiết về Cây Quyết Định Và Giải Thuật Id3 trên website Bac.edu.vn. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Chúc bạn một ngày tốt lành!