Xây dựng Cây quyết định (Decision Tree): Hiểu bản chất Entropy và Gini qua ví dụ Y khoa (Phần 1)

Trong thế giới của học máy, cây quyết định luôn là một trong những thuật toán được yêu thích nhất, đặc biệt là với những người mới bắt đầu.

Lý do rất đơn giản: Khác với các mô hình “hộp đen” phức tạp như Neural Networks – nơi bạn không biết thuật toán nghĩ gì, cây quyết định là một mô hình “hộp trắng”. Nó mô phỏng lại chính xác cách tư duy logic của con người. Để đưa ra một quyết định cuối cùng, mô hình sẽ liên tục đặt ra các câu hỏi dạng Có/Không từ trên xuống dưới, rẽ nhánh dần cho đến khi tìm được câu trả lời.

Tuy nhiên, có một bí mật toán học đằng sau thuật toán này mà nhiều người thường bỏ qua khi gọi thư viện: Làm sao máy tính biết nên đặt câu hỏi nào trước, câu hỏi nào sau để việc phân loại đạt hiệu quả cao nhất?

Đó chính là lúc chúng ta cần đến hai chỉ số đo lường: Entropy và Gini. Trong bài viết này, chúng ta sẽ cùng tự tay tính toán các chỉ số này để hiểu rõ bản chất của chúng, từ đó đưa ra lựa chọn phù hợp nhất khi lập trình.

Để các công thức toán học không trở nên khô khan, chúng ta sẽ áp dụng chúng vào một bài toán y khoa quen thuộc: dự đoán xem một người có bị cảm cúm hay không dựa trên các triệu chứng lâm sàng như sốt, ho, đau cơ. Dưới đây là dữ liệu giả lập của 20 người mà chúng ta sẽ dùng để xây dựng cây quyết định.

• Biến mục tiêu (Target/Label): Chẩn đoán (Cảm cúm / Không).
• Các đặc trưng đầu vào (Features):
  • Ho: Có / Không.
  • Đau nhức cơ: Có / Không.
  • Sốt: Không sốt / Sốt nhẹ / Sốt cao.

Nhìn lướt qua bảng dữ liệu trên. Bằng trực giác, ta có thể lờ mờ nhận ra một vài quy luật: hình như những người “sốt cao” thì đa phần đều mắc cúm, còn những người “không sốt” thì thường an toàn hơn. Nhưng với những ca “sốt nhẹ” thì hên xui.

Máy tính không có trực giác; nó cần những con số định lượng chính xác. Tiếp theo đây, chúng ta sẽ xem thuật toán cây quyết định biến những “trực giác” này thành các phép toán như thế nào để tìm ra nút gốc.

Trước tiên, chúng ta cần cắt lấy 80% của tập dữ liệu này (16 dòng) để tính toán, 20% còn lại (4 dòng) sẽ được dùng để kiểm chứng lại sau khi đã xây dựng xong cây quyết định. Để đơn giản, tôi sẽ lấy luôn 16 dòng đầu.

Để xây dựng cây, ta cần tìm ra một thuộc tính để làm điểm bắt đầu, gọi là nút gốc. Nếu là con người, bác sĩ có thể dựa vào kinh nghiệm lâm sàng để hỏi về tình trạng sốt trước, ho trước hoặc đau cơ trước. Nhưng máy tính thì không có kinh nghiệm; nó cần một tiêu chí toán học rõ ràng để đánh giá xem thuộc tính nào phù hợp nhất. Tiêu chí đó là độ thuần nhất (Purity) và độ vẩn đục (Impurity).

Hãy nhìn vào tập dữ liệu 16 bệnh nhân của chúng ta: có đúng 8 người mắc cúm và 8 người không mắc cúm. Trạng thái ban đầu này là sự pha trộn với tỷ lệ 50/50; ta nói tập dữ liệu này có độ vẩn đục rất cao, hay theo cách gọi của GS. Huỳnh Xuân Hiệp là rất “lộn xộn”.

Nhiệm vụ của cây quyết định là chọn ra một đặc trưng để làm nút gốc nhằm chia tách 16 người này thành các nhóm nhỏ hơn. Thuật toán sẽ đánh giá chất lượng của một phép cắt dựa trên một nguyên tắc cực kỳ đơn giản: Chia xong thì dữ liệu có “sạch” hơn (tức là làm giảm đi sự lẫn lộn) không?

Ở phần tiếp theo, tôi sẽ giới thiệu lý thuyết về Entropy và ứng dụng cụ thể vào bảng dữ liệu 16 bệnh nhân trên. Từ đó, tôi sẽ xây dựng một cây quyết định dựa trên số liệu đã tính được. Dựa vào đó, chúng ta sẽ kiểm chứng lại tính đúng đắn của cây quyết định thông qua dữ liệu của 4 bệnh nhân còn lại trong dữ liệu ban đầu.