Decision Tree – Thuật toán cây quyết định là gì ?

Decision Tree – Thuật toán cây quyết định là gì ? Đây là một thuật thông thông dụng chỉ sau Láng giềng gần nhất KNN thôi, được ứng dụng rộng rãi trong phân tích dữ liệu thống kê, hay chạy mô hình định lượng … đặc biệt là trong các mô hình AI- trí tuệ nhân tạo.

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

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

Cây quyết định là một thuật toán học tập có giám sát không tham số, được sử dụng cho cả nhiệm vụ phân loại và hồi quy. Nó có cấu trúc dạng cây, phân cấp, bao gồm nút gốc ( root node) , các nhánh  , các nút bên trong ( internal node) và các nút lá (leaf nodes).

Cây quyết định bắt đầu bằng một nút gốc, không có bất kỳ nhánh nào đến. Các nhánh đi từ nút gốc sau đó đưa vào các nút bên trong, còn được gọi là nút quyết định. Dựa trên các đặc điểm sẵn có, cả hai loại nút đều tiến hành đánh giá để tạo thành các tập con đồng nhất, được ký hiệu bằng các nút lá, hoặc các nút đầu cuối. Các nút lá đại diện cho tất cả các kết quả có thể có trong tập dữ liệu.

Cơ chế hoạt động của Decision Tree

  • Cây quyết định sử dụng chiến lược phân chia và chinh phục bằng cách thực hiện một tìm kiếm tham lam để xác định các điểm phân tách tối ưu trong một cây. Quá trình tách này sau đó được lặp lại theo cách thức đệ quy từ trên xuống cho đến khi tất cả hoặc phần lớn các bản ghi đã được phân loại theo các nhãn lớp cụ thể.
  • Tất cả các điểm dữ liệu có được phân loại thành các tập đồng nhất hay không phần lớn phụ thuộc vào độ phức tạp của cây quyết định. Các cây nhỏ hơn có thể dễ dàng đạt được các nút lá thuần túy — tức là các điểm dữ liệu trong một lớp duy nhất. Tuy nhiên, khi một cây phát triển về kích thước, việc duy trì độ tinh khiết này ngày càng trở nên khó khăn và nó thường dẫn đến quá ít dữ liệu nằm trong một cây con nhất định.
  • Khi điều này xảy ra, nó được gọi là phân mảnh dữ liệu và nó thường có thể dẫn đến trang bị quá mức. Kết quả là, cây quyết định ưu tiên những cây nhỏ, điều này phù hợp với nguyên tắc của parsimony trong Occam’s Razor; nghĩa là, “các thực thể không nên được nhân lên quá mức cần thiết.” Nói cách khác, cây quyết định chỉ nên tăng thêm độ phức tạp khi cần thiết, vì lời giải thích đơn giản nhất thường là tốt nhất.
  • Để giảm bớt sự phức tạp và ngăn ngừa việc trang bị quá nhiều, việc cắt tỉa thường được sử dụng; đây là một quá trình, loại bỏ các nhánh phân chia trên các đối tượng địa lý có tầm quan trọng thấp. Sau đó, sự phù hợp của mô hình có thể được đánh giá thông qua quá trình xác nhận chéo.
  • Một cách khác mà cây quyết định có thể duy trì độ chính xác của chúng là bằng cách tạo thành một tập hợp thông qua một thuật toán rừng ngẫu nhiên ; trình phân loại này dự đoán kết quả chính xác hơn, đặc biệt khi các cây riêng lẻ không tương quan với nhau.

Đặc điểm của cây quyết định

  • Cây quyết định là một kỹ thuật học thuật có giám sát có thể được sử dụng cho cả bài toán phân loại và bài toán hồi quy, nhưng chủ yếu nó được ưu tiên hơn để giải các bài toán phân loại. Nó là một bộ phân loại có cấu trúc cây, trong đó các nút bên trong đại diện cho các tính năng của tập dữ liệu, các nhánh đại diện cho các quy tắc quyết định và mỗi nút lá đại diện cho kết quả.
  • Trong cây Quyết định, có hai nút, đó là Nút quyết định và Nút lá. Các nút quyết định được sử dụng để đưa ra bất kỳ quyết định nào và có nhiều nhánh, trong khi nút Lá là đầu ra của các quyết định đó và không chứa bất kỳ nhánh nào khác.
  • Các quyết định hoặc kiểm tra được thực hiện trên cơ sở các tính năng của tập dữ liệu đã cho.
  • Nó là một biểu diễn đồ họa để có được tất cả các giải pháp khả thi cho một vấn đề / quyết định dựa trên các điều kiện đã cho.
  • Nó được gọi là cây quyết định bởi vì, tương tự như cây, nó bắt đầu với nút gốc, nút này mở rộng trên các nhánh xa hơn và xây dựng một cấu trúc giống như cây.
  • Để xây dựng một cây, chúng tôi sử dụng thuật toán CART, viết tắt của thuật toán Cây phân loại và hồi quy.
    Cây quyết định chỉ cần đặt một câu hỏi và dựa trên câu trả lời (Có / Không), nó tiếp tục chia cây thành các cây con.

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

Có nhiều thuật toán khác nhau trong Học máy, vì vậy việc chọn thuật toán tốt nhất cho tập dữ liệu và vấn đề đã cho là điểm chính cần nhớ trong khi tạo mô hình học máy. Dưới đây là hai lý do để sử dụng cây Quyết định:

  • Cây Quyết định thường bắt chước khả năng tư duy của con người trong khi đưa ra quyết định, vì vậy nó rất dễ hiểu.
  • Có thể dễ dàng hiểu được logic đằng sau cây quyết định vì nó cho thấy một cấu trúc giống như cây.
Thuật toán cây quyết định Decision Tree
Thuật toán cây quyết định Decision Tree

Các thuật ngữ cây quyết định

Nút gốc (Root node) 

Nút gốc là nơi bắt đầu cây quyết định. Nó đại diện cho toàn bộ tập dữ liệu, được chia thành hai hoặc nhiều tập đồng nhất.

Nút lá (Leaf node)

Các nút lá là nút đầu ra cuối cùng và cây không thể được phân tách thêm sau khi nhận được nút lá.

Tách ( Splitting)

Tách là quá trình phân chia nút quyết định / nút gốc thành các nút con theo các điều kiện cho trước.

Cành / Cây phụ ( Branch/Sub Tree)

Cây được hình thành bằng cách tách cây.

Tỉa cành ( Pruning) 

Tỉa cành là quá trình loại bỏ những cành không mong muốn khỏi cây.

Nút cha / nút con ( Parent/Child node)

Nút gốc của cây được gọi là nút cha, và các nút khác được gọi là nút con.

Thuật toán Cây quyết định hoạt động như thế nào?

Trong cây quyết định, để dự đoán lớp của tập dữ liệu đã cho, thuật toán bắt đầu từ nút gốc của cây. Thuật toán này so sánh các giá trị của thuộc tính gốc với thuộc tính bản ghi (tập dữ liệu thực) và dựa trên sự so sánh, đi theo nhánh và nhảy đến nút tiếp theo.

Đối với nút tiếp theo, thuật toán lại so sánh giá trị thuộc tính với các nút con khác và di chuyển xa hơn. Nó tiếp tục quá trình cho đến khi nó đạt đến nút lá của cây. Quy trình hoàn chỉnh có thể được hiểu rõ hơn bằng cách sử dụng thuật toán dưới đây:

  • Bước 1: Bắt đầu cây với nút gốc (Đặt tên: S), nút này chứa tập dữ liệu hoàn chỉnh.
  • Bước 2: Tìm thuộc tính tốt nhất trong tập dữ liệu bằng cách sử dụng Phép đo lựa chọn thuộc tính (ASM).
  • Bước 3: Chia S thành các tập con chứa các giá trị có thể có cho các thuộc tính tốt nhất.
  • Bước 4: Tạo nút cây quyết định chứa thuộc tính tốt nhất.
  • Bước 5: Tạo một cách đệ quy cây quyết định mới bằng cách sử dụng các tập con của tập dữ liệu đã tạo ở bước -3. Tiếp tục quá trình này cho đến khi đạt đến một giai đoạn mà bạn không thể phân loại thêm các nút và được gọi là nút cuối cùng là nút lá.

Các biện pháp lựa chọn thuộc tính

Trong khi thực hiện cây Quyết định, vấn đề chính nảy sinh là làm thế nào để chọn thuộc tính tốt nhất cho nút gốc và cho các nút con. Vì vậy, để giải quyết những vấn đề như vậy có một kỹ thuật được gọi là thước đo lựa chọn thuộc tính hoặc ASM. Bằng phép đo này, chúng ta có thể dễ dàng chọn thuộc tính tốt nhất cho các nút của cây. Có hai kỹ thuật phổ biến cho ASM, đó là:

  • Thông tin thu được
  • Chỉ số Gini

1. Tăng thông tin:

  • Mức tăng thông tin là phép đo những thay đổi trong entropy sau khi phân đoạn tập dữ liệu dựa trên một thuộc tính.
  • Nó tính toán lượng thông tin mà một đối tượng cung cấp cho chúng ta về một lớp.
  • Theo giá trị thu được thông tin, chúng tôi chia nút và xây dựng cây quyết định.
  • Thuật toán cây quyết định luôn cố gắng tối đa hóa giá trị của mức thu được thông tin và một nút / thuộc tính có mức tăng thông tin cao nhất sẽ được tách ra trước.

2. Chỉ số Gini:

  • Chỉ số Gini là thước đo tạp chất hoặc độ tinh khiết được sử dụng trong khi tạo cây quyết định trong thuật toán CART (Cây phân loại và hồi quy).
  • Thuộc tính có chỉ số Gini thấp nên được ưu tiên hơn so với chỉ số Gini cao.
  • Nó chỉ tạo ra các phân tách nhị phân và thuật toán CART sử dụng chỉ số Gini để tạo phân tách nhị phân.

Mở rộng thuật toán Decision Tree

Thuật toán của Hunt, được phát triển vào những năm 1960 để mô hình hóa việc học tập của con người trong Tâm lý học, tạo thành nền tảng của nhiều thuật toán cây quyết định phổ biến, chẳng hạn như sau:

– ID3: Ross Quinlan được ghi nhận trong quá trình phát triển ID3, viết tắt của “Lặp lại Dichotomiser 3.” Thuật toán này tận dụng entropy và thu thập thông tin làm số liệu để đánh giá sự phân chia ứng viên. Bạn có thể tìm thấy một số nghiên cứu của Quinlan về thuật toán này từ năm 1986.

– C4.5: Thuật toán này được coi là sự lặp lại sau này của ID3, thuật toán này cũng được phát triển bởi Quinlan. Nó có thể sử dụng tỷ lệ thu được hoặc thu được thông tin để đánh giá các điểm phân tách trong cây quyết định.

– CART: Thuật ngữ, CART, là từ viết tắt của “cây phân loại và hồi quy” và được giới thiệu bởi Leo Breiman. Thuật toán này thường sử dụng tạp chất Gini để xác định thuộc tính lý tưởng để phân tách. Tạp chất Gini đo tần suất một thuộc tính được chọn ngẫu nhiên bị phân loại sai. Khi đánh giá bằng cách sử dụng tạp chất Gini, giá trị thấp hơn là lý tưởng hơn.

Đánh giá DT

Trong khi cây quyết định có thể được sử dụng trong nhiều trường hợp sử dụng khác nhau, các thuật toán khác thường hoạt động tốt hơn các thuật toán cây quyết định. Điều đó nói rằng, cây quyết định đặc biệt hữu ích cho các nhiệm vụ khai thác dữ liệu và khám phá kiến ​​thức. Hãy cùng khám phá những lợi ích và thách thức chính của việc sử dụng cây quyết định dưới đây:

Thuận lợi

  1. Dễ hiểu: Logic Boolean và các biểu diễn trực quan của cây quyết định giúp chúng dễ hiểu và dễ hiểu hơn. Bản chất phân cấp của cây quyết định cũng giúp bạn dễ dàng thấy thuộc tính nào là quan trọng nhất, điều này không phải lúc nào cũng rõ ràng với các thuật toán khác, như mạng nơ-ron .
  2.  Ít hoặc không cần chuẩn bị dữ liệu: Cây quyết định có một số đặc điểm, làm cho nó linh hoạt hơn các bộ phân loại khác. Nó có thể xử lý các kiểu dữ liệu khác nhau — tức là các giá trị rời rạc hoặc liên tục và các giá trị liên tục có thể được chuyển đổi thành các giá trị phân loại thông qua việc sử dụng các ngưỡng. Ngoài ra, nó cũng có thể xử lý các giá trị bị thiếu giá trị, điều này có thể gây ra vấn đề cho các bộ phân loại khác, như Naïve Bayes.
  3. Linh hoạt hơn: Cây quyết định có thể được tận dụng cho cả nhiệm vụ phân loại và hồi quy, làm cho nó linh hoạt hơn so với một số thuật toán khác. Nó cũng không nhạy cảm với các mối quan hệ cơ bản giữa các thuộc tính; điều này có nghĩa là nếu hai biến có tương quan cao, thuật toán sẽ chỉ chọn một trong các đặc điểm để tách.

Nhược điểm

  1. Dễ bị overfitting: Cây quyết định phức tạp có xu hướng quá mức và không tổng quát hóa tốt cho dữ liệu mới. Kịch bản này có thể tránh được thông qua quá trình cắt tỉa trước hoặc sau cắt tỉa. Việc cắt tỉa trước sẽ tạm dừng sự phát triển của cây khi không có đủ dữ liệu trong khi sau khi cắt tỉa sẽ loại bỏ các cây phụ có dữ liệu không đầy đủ sau khi xây dựng cây.
  2. Các công cụ ước tính phương sai cao: Các biến thể nhỏ trong dữ liệu có thể tạo ra một cây quyết định rất khác. Tính tổng hợp, hoặc tính trung bình của các ước tính, có thể là một phương pháp giảm phương sai của cây quyết định. Tuy nhiên, cách tiếp cận này bị hạn chế vì nó có thể dẫn đến các yếu tố dự báo có tương quan cao.
  3. Tốn kém hơn: Do cây quyết định có cách tiếp cận tìm kiếm tham lam trong quá trình xây dựng, chúng có thể tốn kém hơn để đào tạo so với các thuật toán khác.
  4. Không được hỗ trợ đầy đủ trong scikit-learning: Scikit-learning là một thư viện máy học phổ biến dựa trên Python. Mặc dù thư viện này có mô-đun Cây quyết định, việc triển khai hiện tại không hỗ trợ các biến phân loại.

Bài viết mới

Có thể bạn thích bài viết này:

Trả lời

Email của bạn sẽ không được hiển thị công khai.