EnglishQuay trở lại với chủ đề về Decision trees, thì ở 2 bài viết trước BigDataUni đã giới thiệu đến các bạn khái quát thế nào là thuật toán cây quyết định, bao gồm các thành phần, và một số công thức tính toán để lựa chọn các biến phân nhánh hay cách phân nhánh tối ưu, mục đích dự báo, phân loại, phân nhóm các đối tượng dữ liệu vào các nhóm, các lớp của biến mục tiêu sao cho chính xác nhất.
Chúng ta đã cùng nhau tìm hiểu về CART với ví dụ ứng dụng trong lĩnh vực ngân hàng để dự báo khả năng khách hàng đem lại rủi ro tín dụng, tiếp theo phần 3, BigDataUni cung cấp thêm cho các bạn một loại thuật toán cây quyết định mới, đó chính là C4.5 sử dụng công thức Entropy để xây dựng mô hình. Các bạn có thể xem lại các bài viết của chúng tôi trong link dưới đây để xem thêm về phương pháp Classification (phân lớp) trong Data mining, và thuật toán cây quyết định bắt đầu với CART.
Nguyên nhân nữa là, khác với bài viết vừa rồi, phần 3 chúng tôi sẽ không đề cập hay giải thích lại những gì đã trình bày trước đây mà đi thẳng vào phần mới, do đó nếu các bạn chưa biết gì sẽ khó có thể hiểu được nội dung trong bài viết này.
(Link các bài viết trước)
Thuật toán KNN và ví dụ đơn giản trong ngành ngân hàng
Thuật toán cây quyết định (P.1): Classification & regression tree (CART)
Thuật toán cây quyết định (P.2) Classification & regression tree (Gini index)
Như vậy chúng ta đã làm quen với thuật toán Decision tree đầu tiên là CART, phân 2 nhánh mỗi lần, sử dụng công thức Goodness of split và công thức Gini Index áp dụng cho các biến định tính (categorical variables) để tiến hành phân nhánh và xây dựng mô hình cây quyết định hoàn chỉnh.
Tuy nhiên trong một số trường hợp, đặc biệt khi bộ dữ liệu phức tạp với nhiều biến khác nhau (ở đây giả định chưa nói đến việc áp dụng phương pháp Feature selection để chọn lựa các biến đầu vào liên quan đến biến mục tiêu), mỗi biến chứa nhiều thuộc tính, hay giá trị, đồng thời đều có thể làm cơ sở để phân loại đối tượng dữ liệu, thì nếu áp dụng CART và mỗi lần chỉ phân được 2 nhánh, mô hình của chúng ta có thể sẽ rất phức tạp và không hiệu quả. Để đánh giá chúng ta phải xét đến độ sâu của cây quyết định (depth of decision tree) – là khoảng cách từ Root node (ngọn cây) đến leaf node cuối cùng, kích thước của cây quyết định (size of decision tree) – tổng số node trong cây. Độ sâu và kích thước sẽ phụ thuộc vào bộ dữ liệu chúng ta nghiên cứu.
Nếu bộ dữ liệu đơn giản, không có quá nhiều biến, và giá trị hay thuộc tính dữ liệu mỗi biến không quá đa dạng ví dụ biến thu nhập chỉ có 3 giá trị “Cao”, “Trung bình”, “Thấp”, biến hôn nhân chỉ có 2 giá trị “Độc thân”, “Đã kết hôn và từng kết hôn”, nhưng cây quyết định sau khi được hình thành lại có độ sâu lớn, và quá nhiều node như vậy sẽ không được tối ưu. Có 2 nguyên nhân, thứ nhất quá trình tính toán và lựa chọn cách phân nhánh không hợp lý, thứ hai là vấn đề từ bộ dữ liệu mà chúng ta chưa thể xác định được. Một khía cạnh khác cần quan tâm nữa chính là độ chính xác, khả năng đưa ra kết quả phân loại đúng của mô hình cây quyết định. Nếu mô hình quá đơn giản, độ sâu cây quyết định nhỏ, số phân nhánh, số node ít, thì khả năng mô hình bị Underfitting, không xét hết mọi tình huống có thể phân loại đối tượng dữ liệu, các bạn còn có thể gọi vui là mô hình “hời hợt”, chưa được training tới nơi.
Ngược lại nếu mô hình cây quyết định quá phức tạp, và xét đến mọi khả năng phân loại đối tượng dữ liệu ứng với từng biến đầu vào, thì mô hình có thể bị Overfitting, quá khớp với dữ liệu training khiến cho việc áp dụng dữ liệu test sẽ không còn hiệu quả. Underfitting hay Overfitting là các vấn đề không còn xa lạ đối với những nhà phân tích trong lĩnh vực Data mining, và Machine learning. Chúng có thể xảy ra đối với tất cả các mô hình dữ liệu ứng với mỗi loại thuật toán khác nhau không chỉ riêng Decision Trees.
Và dĩ nhiên chúng ta luôn có giải pháp để hạn chế, cụ thể trong thuật toán cây quyết định, chúng ta có phương pháp phổ biến nhất là Pruning tree, “ngắt cành” hiểu nôm na là giảm chiều sâu của cây quyết định, khắc phục Overfitting mà đảm bảo mô hình không bị Underfitting.
Về phương pháp Pruning và vấn đề Overfitting hay Underfitting, chúng tôi sẽ trình bày cụ thể và rõ ràng hơn trong các bài viết sắp tới.
Trở lại với bài viết lần này, chúng ta sẽ tiếp cận thêm một thuật toán cây quyết định mới chính là C4.5, cho phép phân nhánh nhiều hơn 2 nhánh, và sử dụng công thức Entropy để tính mức độ tương đồng, “thuần nhất” – purity, của các đối tượng dữ liệu trong một node.
Đầu tiên chúng ta tìm hiểu một chút về thuật toán C4.5, là thuật toán mở rộng của thuật toán ID3 (Iterative Dichotomiser 3) của nhà nghiên cứu khoa học máy tính Ross Quinlan, ra đời vào năm 1986. ID3 cũng sử dụng công thức Entropy và Information Gain để xây dựng mô hình cây quyết định có thể phân nhiều hơn 2 nhánh, tuy nhiên ID3 chỉ hỗ trợ áp dụng cho dữ liệu/ biến định tính nên còn nhiều hạn chế không đem lại hiệu quả khi triển khai phân tích dữ liệu định lượng cụ thể là Regression tree. Do đó mặc dù ID3 là thuật toán cây quyết định ra đời từ rất lâu nhưng không còn được sử dụng phổ biến cũng chính vì lí do trên.
C4.5 được xem là phiên bản nâng cấp của ID3 với khả năng xử lý được cả dữ liệu đinh lượng dạng liên tục (continuous data) và cả dữ liệu định tính, và là thuật toán Decision tree tiêu biểu. C4.5 sử dụng thêm công thức Gain ratio để khắc phục các khuyết điểm của Information Gain của ID3 trong việc lựa chọn cách phân nhánh tối ưu. Về công thức Entropy, Information Gain và Gain ratio chúng tôi sẽ giới thiệu ngay sau đây.
Cũng giống như CART, C4.5 cũng xem xét đến từng biến đầu vào, từng node trên cây quyết định, tìm ra các phân nhánh tối ưu cho đến khi không thể phân nhánh được nữa để phân loại chính xác cho đối tượng dữ liệu. Tuy nhiên C4.5 và CART có một số điểm khác biệt sau:
- Khác với CART, thuật toán C4.5 không bị giới bởi số nhánh có thể phân trong mỗi lần. Trong khi CART chỉ phân được 2 nhánh mỗi lần, còn C4.5 thì có thể xây dựng cây quyết định với nhiều nhánh ở mỗi tầng.
- Đối với dữ liệu định tính, CART có trường hợp một nhánh gồm 2 thuộc tính dữ liệu và nhánh còn lại thể hiện 1 thuộc tính dữ liệu. Ví dụ ở các bài viết trước chúng ta có thể phân nhánh cho biến thu nhập như nhánh trái “Thu nhập = Cao”, nhánh phải là “Thu nhập = {trung bình, thấp}”, các đối tượng dữ liệu sẽ được phân chia tương tự vào các node của 2 nhánh này dựa trên loại thu nhập nào. Còn C4.5 do không bị giới hạn
- CART sử dụng Gini index và Goodness of split để tiến hành lựa chọn cách thức phân nhánh, còn C4.5 thì sử dụng công thức Entropy với Information Gain, và Gain Ratio.
Tiếp theo chúng ta sẽ đi vào tìm hiểu công thức Entropy, cơ sở xây dựng thuật toán C4.5.
Entropy là phương pháp lựa chọn cách phân nhánh tối ưu dựa trên cơ sở tối đa hóa lượng thông tin nhận vào “Information maximization” tức giảm thiểu tối đa độ hỗn độn và nhiễu loạn trong từng node “Entropy reduction”. Các node phân nhánh được lựa chọn theo phương pháp này phải thể hiện tối đa thông tin cần thiết để cây quyết định có thể phân loại chính xác đối tượng dữ liệu vào các tập con có chứa nhãn, là giá trị/ thuộc tính của biến đầu vào. Tương tự như Gini index nếu tất cả các đối tượng trong một node, một tập con đều mang giá trị là nhãn của phân nhánh, hay chính tập con đó thì Entropy có giá trị bằng 0, ngược lại nếu các đối tượng chứa nhiều giá trị khác nhau thì Entropy sẽ cao nhất và bằng 1. Entropy là thuật ngữ liên kết với Information gain trong học thuyết về thông tin (Information theory) và tương đồng với học thuyết “Kullback-Leibler divergence” trong Machine Learning.
Về diễn giải ý nghĩa công thức, cũng như công thức được hình thành như thế nào, tại sao lại sử dụng hàm logarit để tính toán, và mối liên hệ của nó đến các thuật ngữ khác, chúng tôi sẽ không trình bày cụ thể trong bài viết này. Các bạn có thể tham khảo thêm ở một số tài liệu khác.
Bên trên là công thức tổng quát của Entropy. Với p(j/t) là xác suất xuất hiện đối tượng dữ liệu mang thuộc tính j của biến mục tiêu trong node t. Khi p(j/t) càng lớn thì log2 của p(j/t) sẽ mang giá trị âm và tiến gần đến 0, nhân với giá trị âm p(j/t) ở đầu công thức luôn bé hơn 1, sẽ được giá trị dương tiến gần đến 0. Như vậy cũng giống Gini index, giá trị Entropy càng nhỏ thì tức node hay tập con chứa nhiều đối tượng dữ liệu có cùng thuộc tính j bất kỳ (p(j/t) sẽ lớn).
Chúng ta cùng so sánh với công thức Gini index, trong trường hợp tính độ thuần khiết của node chỉ bao gồm các đối tượng dữ liệu có 1 trong 2 thuộc tính A và B, tức xét biến phân nhánh của node này là biến thay phiên (Binary variable). Nhắc lại công thức Gini index:
Nhìn trên biểu đồ các bạn có thể thấy tại vị trí p = 0.5, (p là xác suất mà một đối tượng dữ liệu trong tập con hay node đang xét mang 1 thuộc tính A, B bất kỳ), tức lúc này p(A/t) = p (B/t) = 0.5. Áp dụng vào 2 công thức chúng ta có được, Entropy = 1, và Gini index = 0.5 đều mang giá trị cao nhất, nghĩa là trong trường hợp một node với biến Binary, nếu số lượng đối tượng được chia đều theo thuộc tính A, B bất kỳ, thì node này có mức độ không thuần túy “impurity” hay mức độ hỗn độn thông tin “Entropy” là cao nhất.
Trên hình các bạn có thể thấy giới hạn giá trị mà Entropy có thể nhận được đó chính là từ 0 đến 1, còn Gini index nhận giá trị từ 0 đến 0.5, nên xét về khả năng so sánh mức độ đồng nhất, hay thuần khiết của các node được lựa chọn phân nhánh thì Entropy có lẽ thể hiện rõ hơn sự khác biệt giữa các node so với Gini index, vì thế Entropy được dùng chủ yếu cho C4.5 trong trường hợp phân nhiều nhánh. Tuy chung “concept” nhưng trong thực tế Gini index thường được ưa chuộng do việc tính toán đơn giản hơn, khi sử dụng công thức bình phương, còn Entropy sử dụng hàm logarit, có thể dẫn đến chi phí tính toán cao hơn khi bộ dữ liệu cần phân tích là rất lớn và đa dạng về các biến đầu vào.
Tiếp tục chúng ta đến với Information Gain. Nếu dịch trực tiếp ra nghĩa tiếng Việt thì là “lượng thông tin có được”, các bạn có thể hiểu đơn giản đây là công thức để xác định xem trong số các cách thức phân nhánh thì cách nào đem lại nhiều “thông tin nhất”, “rõ ràng nhất”, đầy đủ cơ sở nhất để chúng ta phân loại đối tượng dữ liệu theo các giá trị, các nhóm, các phân lớp có sẵn của biến mục tiêu.
Tuy nhiên nhiều chuyên gia cho rằng Information Gain vẫn còn nhiều hạn chế nhất định ví dụ trong trường hợp biến cần xét có quá nhiều giá trị khác biệt (distinct values) giả sử như biến thông tin về số tài khoản ngân hàng với Information Gain cao được chọn vào làm node phân nhánh. Nhưng làm sao chúng ta có thể phân nhánh theo số tài khoản ngân hàng của từng khách hàng? Nếu thực hiện luôn (mỗi nhánh là 1 số tài khoản) thì mô hình có thể bị “overfitting” tức khớp hoàn toàn với dữ liệu training, vậy khi các khách hàng mới với các số tài khoản ngân hàng khác nhau đưa vào mô hình thì mô hình không thể phân loại được do các số tài khoản ngân hàng này không giống với các số tài khoản lúc huấn luyện mô hình. Information Gain có khuynh hướng thiên vị hay còn gọi “bias” cho các biến chứa nhiều giá trị dữ liệu khác nhau. Gain ratio do đó được ra đời như một bảng nâng cấp của Information Gain và hạn chế được các khuyết điểm của nó khi xét cả số lượng và quy mô của các nhánh trong khi tính toán:
Với SplitInfo có công thức như sau:
Splitinfo chính là “thông tin có được” về số lượng đối tượng dữ liệu trong mỗi nhánh. Diễn giải cho các bạn dễ hiểu hơn, ví dụ chúng ta có 15 khách hàng với ID khác nhau tức có thể có 15 nhánh mỗi nhánh có 1 đối tượng dữ liệu, và mỗi khách hàng có thể mang lại rủi ro tín dụng hoặc không mang lại rủi ro tín dụng (giả sử đã được phân loại theo biến mục tiêu), nên Entropy trung bình của node ID này có thể là:
Entropy (ID) = -1*log2(1) + …. + -1*log2(1) = 0, lúc này Information Gain sẽ lớn nhất, với Entropy (target variable) là mặc định.
Đây là trường hợp không xảy ra trong thực tế nhưng là giả định xấu nhất có thể phải đối mặt: mỗi một nhánh chứa 1 đối tượng dữ liệu. Do đó nếu trong thực tế khi số nhánh nhiều, nghĩa là có nhiều thuộc tính hay giá trị dữ liệu trong một node, thì Information Gain của node này có thể cao hơn các node khác. Ví dụ giả sử chúng ta có biến về trình độ học vấn của khách hàng như: “Chưa tốt nghiệp THPT”, “Tốt nghiệp THPT”, “Đại học”, “Trên Đại học”, “Cao đẳng”, “Trung cấp”, và biến về tình trạng hôn nhân “Đã có gia đình”, “Độc thân”, “Từng ly hôn”, thì khả năng Information Gain sẽ có khả năng nghiên về biến trình độ học vấn, và chúng ta sẽ phải dùng biến này để phân nhánh.
Về cách thức thực hiện thuật toán này như thế nào, BigDataUni sẽ lấy lại ví dụ trong bài viết đầu tiên về CART, đơn giản hơn so với ví dụ trong bài viết thứ 2 xét đến nhiều biến hơn nếu trình bày sẽ khá phức tạp, và khiến bài viết cồng kềnh và dài, do C4.5 sử dụng đến 4 công thức để xây dựng mô hình.
Các bạn có thể xem lại bài viết CART theo link dưới đầy để nắm thông tin về ví dụ chúng tôi trình bày:
Thuật toán cây quyết định (P.1): Classification & regression tree (CART)
Ví dụ sau đây được tham khảo từ giáo trình “Discovering Knowledge in Data: An introduction to Data mining” của Daniel T.Larose (phần 2). Giả sử chúng ta có một tập dữ liệu training cho model C4.5 như sau:
Đầu tiên tìm ra các cách phân nhánh thứ nhất cho C4.5 mà chúng ta có thể lựa chọn theo các biến đầu vào ngoại trừ biến mục tiêu. Do thuật toán C4.5 không bị giới hạn bởi 2 nhánh nên việc xác định các cách thức phân nhánh khá đơn giản so với thuật toán CART.
Đầu tiên chúng ta tính Entropy của biến mục tiêu, chúng ta có 3 khách hàng có rủi ro tín dụng, và 5 khách hàng không có rủi ro tín dụng, đây là Entropy, mức độ hỗn độn thông tin mà chúng ta xác định được trước khi phân nhánh. Các bạn nên xem lại các công thức chúng tôi trình bày phía trên song song với việc theo dõi ví dụ dưới đây.
Entropy(rủi ro tín dụng) = – 5/8*log2(5/8) – 3/8*log2(3/8) = 0.9544
Tiếp theo chúng ta xét từng cách phân nhánh để chọn là node phân nhánh đầu tiên
Cách 1, khoản tiết kiệm chúng ta có 3 giá trị thấp, trung bình, cao, với khoản tiết kiệm thấp thì có 1 khách hàng không có rủi ro tín dụng, 2 khách hàng còn lại có rủi ro tín dụng, các bạn thống kê tương tự cho khoản tiết kiệm trung bình và cao để tiến hành tính Entropy.
Entropy(khoản tiết kiệm = cao) = – 1∕2*log2(1∕2) – 1∕2*log2(1∕2) = 1
Entropy(khoản tiết kiệm = trung bình) = -3∕3*log2(3∕3) – 0∕3*log2(0∕3) = 0 do 3 khách hàng có khoản tiết kiệm trung bình đều không có rủi ro tín dụng, do đó nhánh này sẽ dẫn đến pure node
Entropy(khoản tiết kiệm = thấp) = -1∕3*log2(1∕3) – 2∕3*log2(2∕3) = 0.9183
Chúng ta ghép vào để tính chung entropy cho khoản tiết kiệm theo công thức
WeightedEntropy, tính theo tỷ lệ số đối tượng dữ liệu trong mỗi nhánh, ví dụ khoản tiết kiệm cao có 2 quan sát, thì entropy có trọng số là 2/8 với 8 là tổng số quan sát.
Entropy(khoản tiết kiệm) = (2∕8)*(1) + (3∕8)*(0) + (3∕8)*(0.9183) = 0.5944
Chúng ta tính Information Gain, lượng thông tin chúng ta sẽ có được làm cơ sở để phân loại khách hàng theo mức độ rủi ro tín dụng nếu chọn biến khoản tiết kiệm để phân nhánh. Lấy Entropy của biến mục tiêu trừ đi Entropy của khoản tiết kiệm.
Information Gain(khoản tiết kiệm) = Entropy(rủi ro tín dụng) – Entropy(khoản tiết kiệm) = 0.9544 – 0.5944 = 0.36
Lưu ý đơn vị của Entropy hay Information gain chính là “bit” trong Computer science. Tiếp tục chúng ta tính Gain ratio của biến khoản tiết kiệm, trước tiên là SplitInfo
SplitInfo (khoản tiết kiệm) = -(2/8)*log2(2/8) – (3/8)*log2(3/8) – (3/8)*log2(3/8) = 1.56 với số khách hàng có khoản tiết kiệm thấp là 2, trung bình là 3, và cao là 3.
GainRatio (khoản tiết kiệm) = Information Gain (khoản tiết kiệm)/ SplitInfo (khoản tiết kiệm) = 0.23.
Các bạn tính tương tự như trên cho các cách phân nhánh còn lại thì sẽ được kết quả như bảng dưới đây và dựa theo kết quả GainRatio để so sánh và chọn lựa node nào sẽ là node đầu tiên phân nhánh.
Như vậy với information gain và gain ratio đều cao nhất thì cách phân thứ 2 với biến tài sản hiện có sẽ được làm root node.
Tiếp tục tại nhánh tài sản = trung bình thì chúng ta chưa thể phân loại được mà phải xét tiếp, nhưng lúc này chúng ta chỉ còn 4 quan sát, tức 4 khách hàng cần phân loại mà thôi. Như vậy sau khi sử dụng cách thứ 2 để phân nhánh thì lúc này chúng ta còn 4 cách phân nhánh.
Số khách hàng còn phải xét:
Các bạn có thể thấy trong khoản tiết kiệm chúng ta có 1 khách hàng có khoản tiết kiệm cao, và 100% có rủi ro tín dụng, tương tự như thấp và trung bình đều 100%. Vậy khi tính Entropy cho 3 nhóm này và tính Weighted Entropy cho khoản tiết kiệm thì chắc chắn giá trị sẽ bằng 0, lúc này Information Gain sẽ là cao nhất, tương tự như Gain ratio, nên chúng ta sẽ lấy khoản tiết kiệm làm node phân nhánh tiết theo mà không cần xét đến thu nhập. Như vậy chúng ta sẽ có một cây quyết định C4.5 hoàn chỉnh như sau:
Như vậy đến đây là kết thúc bài viết về thuật toán C4.5 sử dụng công thức Entropy, Information Gain, và Gain Ratio. Ở bài viết sắp tới chúng tôi sẽ trình bày về các vấn đề tiếp theo trong thuật toán cây quyết định bao gồm các phương pháp hạn chế khả năng overfitting của mô hình, các ưu điểm, khuyết điểm của thuật toán cây quyết định, và nguyên tắc quyết định (decision rule) khi diễn giải mô hình. Mong các bạn tiếp tục theo dõi và ửng hộ BigDataUni.
Về chúng tôi, công ty BigDataUni với chuyên môn và kinh nghiệm trong lĩnh vực khai thác dữ liệu sẵn sàng hỗ trợ các công ty đối tác trong việc xây dựng và quản lý hệ thống dữ liệu một cách hợp lý, tối ưu nhất để hỗ trợ cho việc phân tích, khai thác dữ liệu và đưa ra các giải pháp. Các dịch vụ của chúng tôi bao gồm “Tư vấn và xây dựng hệ thống dữ liệu”, “Khai thác dữ liệu dựa trên các mô hình thuật toán”, “Xây dựng các chiến lược phát triển thị trường, chiến lược cạnh tranh”.