ساخت بهينه درخت تصميم با بهره گيري از رويكرد برنامه ريزي منطقي

اصفهان : دانشگاه صنعتي اصفهان

مهندسي كامپيوتر

كارشناسي ارشد

درخت‌هاي تصميم به دليل قابليت تفسير و عملكردشان، يك مدل طبقه‌بندي محبوب در يادگيري ماشين هستند. به‌طور سنتي، درخت‌هاي تصميم با استفاده از الگوريتم‌هاي حريصانه و ابتكاري ساخته مي‌شوند اما اين الگوريتم‌ها تضميني در مورد كيفيت درخت‌هاي توليدشده ارائه نمي‌دهند. در مقابل، در پژوهش‌هاي اخير از رويكردهاي بهينه‌سازي دقيق براي ساخت درخت‌هاي تصميم بهينه استفاده شده‌است. يك درخت تصميم ايده‌آل، درخت تصميمي با كم‌ترين عمق و بيش‌ترين دقت ممكن است. با وجود سادگي اين ساختار، ساخت درخت تصميم بهينه يك مسئله NP- سخت مي‌باشد. الگوريتم‌هاي سنتي ساخت درخت تصميم، اعم از C4.5، ID3 و CART، حريصانه هستند و تضميني درمورد كيفيت و دقت درخت تصميم ارائه نمي‌دهند. بنابراين استفاده از رويكردهاي دقيق براي ساخت درخت تصميم با دقت بيش‌تر، از اهميت ويژه‌اي برخوردارند. در اين پژوهش، به پياده‌سازي و تحليل و بررسي چند رويكرد دقيق موجود براي ساخت درخت تصميم بهينه، مانند رويكرد مبتني بر مسئله ارضاپذيري دودويي، شاخه و كران و شاخه و هزينه مي‌پردازيم. همچنين يك رويكرد دقيق را براي ساخت درخت تصميم بهينه با بهره‌گيري از برنامه‌ريزي منطقي معرفي مي‌كنيم. در همه رويكردهاي دقيق موجود و رويكرد پيشنهادي، استراتژي بر اين است كه عمق ثابتي براي درخت تصميم در نظر گرفته مي‌شود. همچنين درخت تصميم حاصل، يك درخت دودويي بوده و هدف، تنظيم ويژگي‌ها و آستانه‌هاي گره‌ها و برچسب‌هاي برگ‌ها به نحوي است كه بيش‌ترين دقت بر روي مجموعه داده آموزشي به دست آيد. رويكردهاي دقيق و غيردقيقي كه براي ساخت درخت تصميم مطرح شده‌اند، بعضاً مناسب نوع خاصي از داده يا طبقه‌بندي‌ها هستند. طبق نتايج به دست آمده، رويكرد پيشنهادي ما قابل پياده‌سازي براي انواع داده‌ها و انواع طبقه‌بندي‌هاست و مي‌تواند درختي با دقت معادل با درخت‌هاي تصميم حاصل از رويكردهاي دقيق ارائه دهد. شايان ذكر است كه مدل پيشنهادي ما براي داده‌هاي دودويي و دسته‌اي، در عمق‌هاي كم، عملكرد بهتري از خود نشان مي‌دهد.

231874

علوم داده

مهندسي برق و كامپيوتر

دانشگاه صنعتي اصفهان