توصيفگر ها :
طبقه‌بندي , درخت تصميم , يادگيري ماشين , الگوريتم‌هاي دقيق و غيردقيق , مسئله ارضاپذيري دودويي (SAT) , شاخه و كران (BB) , شاخه و هزينه (BP) , برنامه‌ريزي قيد (CP) , برنامه‌ريزي منطقي
چكيده فارسي :
درخت‌هاي تصميم به دليل قابليت تفسير و عملكردشان، يك مدل طبقه‌بندي محبوب در يادگيري ماشين هستند. به‌طور سنتي، درخت‌هاي تصميم با استفاده از الگوريتم‌هاي حريصانه و ابتكاري ساخته مي‌شوند اما اين الگوريتم‌ها تضميني در مورد كيفيت درخت‌هاي توليدشده ارائه نمي‌دهند. در مقابل، در پژوهش‌هاي اخير از رويكردهاي بهينه‌سازي دقيق براي ساخت درخت‌هاي تصميم بهينه استفاده شده‌است. يك درخت تصميم ايده‌آل، درخت تصميمي با كم‌ترين عمق و بيش‌ترين دقت ممكن است. با وجود سادگي اين ساختار، ساخت درخت تصميم بهينه يك مسئله NP- سخت مي‌باشد. الگوريتم‌هاي سنتي ساخت درخت تصميم، اعم از C4.5، ID3 و CART، حريصانه هستند و تضميني درمورد كيفيت و دقت درخت تصميم ارائه نمي‌دهند. بنابراين استفاده از رويكردهاي دقيق براي ساخت درخت تصميم با دقت بيش‌تر، از اهميت ويژه‌اي برخوردارند. در اين پژوهش، به پياده‌سازي و تحليل و بررسي چند رويكرد دقيق موجود براي ساخت درخت تصميم بهينه، مانند رويكرد مبتني بر مسئله ارضاپذيري دودويي، شاخه و كران و شاخه و هزينه مي‌پردازيم. همچنين يك رويكرد دقيق را براي ساخت درخت تصميم بهينه با بهره‌گيري از برنامه‌ريزي منطقي معرفي مي‌كنيم. در همه رويكردهاي دقيق موجود و رويكرد پيشنهادي، استراتژي بر اين است كه عمق ثابتي براي درخت تصميم در نظر گرفته مي‌شود. همچنين درخت تصميم حاصل، يك درخت دودويي بوده و هدف، تنظيم ويژگي‌ها و آستانه‌هاي گره‌ها و برچسب‌هاي برگ‌ها به نحوي است كه بيش‌ترين دقت بر روي مجموعه داده آموزشي به دست آيد. رويكردهاي دقيق و غيردقيقي كه براي ساخت درخت تصميم مطرح شده‌اند، بعضاً مناسب نوع خاصي از داده يا طبقه‌بندي‌ها هستند. طبق نتايج به دست آمده، رويكرد پيشنهادي ما قابل پياده‌سازي براي انواع داده‌ها و انواع طبقه‌بندي‌هاست و مي‌تواند درختي با دقت معادل با درخت‌هاي تصميم حاصل از رويكردهاي دقيق ارائه دهد. شايان ذكر است كه مدل پيشنهادي ما براي داده‌هاي دودويي و دسته‌اي، در عمق‌هاي كم، عملكرد بهتري از خود نشان مي‌دهد.
چكيده انگليسي :
Decision trees are a popular classification model in machine learning due to their interpretability and performance. Traditionally, decision trees are built using greedy heuristic algorithms, which do not guarantee the quality of the resulting trees. In contrast, recent studies have focused on using exact optimization approaches to construct optimal decision trees. An ideal decision tree has the minimum depth and maximum accuracy possible. Despite their simple structure, constructing an optimal decision tree is an NP-hard problem. Traditional decision tree algorithms, such as C4.5, ID3, and CART, are greedy and provide no guarantees about the accuracy or quality of the resulting tree. Therefore, using exact methods to build more accurate decision trees is particularly crucial. In this study, we implement, analyze, and review several existing exact approaches for constructing optimal decision trees, including SAT-based, branch-and-bound, and branch-and-price methods. Additionally, we propose a new exact method based on logic programming to construct optimal decision trees. In all the exact approaches considered, including our proposed method, the strategy is to assume a fixed depth for the decision tree. The resulting tree is binary, and the objective is to adjust node features, thresholds, and leaf labels to achieve maximum accuracy on the training data. The exact and heuristic approaches for constructing decision trees are often tailored to specific types of data or classification tasks. According to our results, the proposed method is applicable to various types of data and classification problems and can generate decision trees with accuracy equal to those produced by other exact approaches. Notably, our method performs better on binary and categorical datasets, especially with low-depth trees.
