بخشی از مقاله
چکیده
درخت ID3 ساده ترین نوع درخت تصمیم گیری از انواع درختان قطعی می باشـد کـه بـه دلیـل کـارایی، سـادگی درک و اسـتفاده در کاربردهای داده کاوی و یادگیری ماشین به صورت مکرر مورد استفاده قرار گرفته است. این روش با استفاده از یکی از قواعد اساسی در نظریه اطلاعات عمل می کند مطابق این روش در هر زمان ویژگی از اطلاعات برای تعیـین دسـته مـورد اسـتفاده قـرار مـیگیـرد کـه بیشترین بار اطلاعاتی را داشته و یا به عبارت بهتر موجب کاهش بی نظمی یا آنتروپی گردد. مطابق این الگوریتم زمانی که چند صفت شرایط یکسان و یا بسیار نزدیک به هم داشته باشند این الگوریتم هیچ گونه پیش بینی برای انتخاب آن هـا نـدارد و اولـین صـفتی کـه بالاترین بار اطلاعاتی را داشته باشد انتخاب و دسته بندی را بر اساس آن انجام میدهد.
در تحقیق انجام گرفته این پایان نامه با استفاده از الگوریتم Hoeffding ، که نحوه انتخاب صفت در زمانی کـه صـفات دارای شـرایط یکسان یا نزدیک به هم را تا حدودی قاعده مند می کند؛ درخت تصمیم ID3 را بهبود بخشیدهایم؛ و با انجام آزمونهای اجرائـی نشـان دادهایم که با استفاده از الگوریتم Hoeffding، تشخیص صفات مربوطه، در مقایسه با الگوریتم اصلی درخـت ID3 بهبـود یافتـه و در نتیجه درخت ID3 به صورت کاراتری عمل نموده است.
کلمات کلیدی
الگوریتم ID3، الگوریتم Hoeffding، آنتروپی .
-1 مقدمه
امروزه در عصر انفجار اطلاعـات اسـتخراج دانـش از اطلاعـات یکـی از گلوگاههای علوم مهندسی میباشد. تـاکنون روشهـای بسـیاری بـرای فایق آمدن بر این مشکل ارایه شـده اسـت کـه در ایـن میـان یکـی از عمومیترین آن ها ساختارهای درختی است که برای تصمیم گیـری یـا دستهبندی مورد استفاده قرار میگیرند. این ساختار به دلیل استفاده از نمادها و برقراری ارتباط میان آن ها، ساختاری است که به سهولت قابل درک میباشد.
یک درخت تصمیم گیری نمـای گرافیکـیای از مجموعـه ای از قـوانین کلاسبندی میباشد. یک رکورد داده درخت از گره ریشه تا یک بـرگ میباشد. هر گره درونی درخت یک صـفت خاصـه پـیشگـویی کننـده است. این صفت اغلب یک صفت جداکننده نامیده مـیشـود. چـرا کـه داده بر مبنای شرایط این صفت خاصه، جدا میشود. لبههـایی کـه بـه یک گره درونی میرسند با پیش گویی در نظـر گرفتـه شـده، برچسـب میخورند. هر رکورد داده که وارد گره میشـود بایـد پیشـگوییای کـه روی لبه بوده است را داشته باشـد. ترکیـب اطلاعـات در مـورد صـفت
جداکننده و پیشگویی روی لبـهی مربوطـه ضـابطه جـدا کـردن گـره نامیده میشود. گرهای که هیچ لبهای از آن خارج نشود، یک گره بـرگ است. هر گره برگ با مقدار یک صفت خاصه وابسـته برچسـب گـذاری میشود. درخت ID3 ساده تـرین نـوع درخـت تصـمیم گیـری از انـواع درختان قطعی می باشد که به دلیل کارایی، سادگی درک و استفاده در کاربردهای داده کاوی و یادگیری ماشین به صورت مکرر مورد اسـتفاده قرار گرفته است. این روش با استفاده از یکی از قواعد اساسی در نظریه اطلاعات عمل میکند مطابق این روش در هر زمان ویژگی از اطلاعـات بــرای تعیــین دســته مــورد اســتفاده قــرار مــیگیــرد کــه بیشــترین بهره اطلاعاتی را داشته و یا به عبارت بهتر موجب کاهش بی نظمـی یـا آنتروپی گردد.
تــاکنون تحقیقــات و نــوآوریهــای زیــادی در جهــت بهبــود الگــوریتم درختID3 انجام گرفته اسـت، اکثـر ایـن تحقیقـات در جهـت بهبـود فرمول محاسبه بهره اطلاعاتی از حالت لگاریتمی به حالت خطـی بـوده است و یا اینکه بـه صـفاتی کـه دارای ارزش بیشـتری از لحـاظ کـاربر بوده اند ضریبی اختصاص داده شده تا آن ها در فرمـول بهـرهاطلاعـاتی، ارزش بالاتری پیدا کنند.
به طور مثـال در [1] محققـان توانسـتند بـا ترکیـب فرمـول محاسـبه بهرهاطلاعاتی با فرمول تیلور به نتایج جدیدی در محاسبه بهرهاطلاعاتی برسند، ایشان همچنین ضریبی را برای صفات جـدول تعیـین کردنـد، سپس هر دو روش ایجاد درخت (اصلی و جدید) را بر روی یـک بانـک داده در 4 مرحله تست کردند و در هر مرحله تعداد رکوردهـای داده را افزایش دادند که بر این اساس توانستند دقت الگوریتم را 3% افزایش و مدت زمان آن را به 65% درصد الگوریتم اصلی کاهش دهند.
همچنین در [2] گروهی از محققان نیـز توانسـتند بـا ترکیـب فرمـول محاسبه بهره اطلاعاتی با تئوری تیلـور بـه نتـایج جدیـدی در محاسـبه بهره اطلاعاتی برسند، ایشان همچنین به صفات خاصی از جدول، وزنـی اختصاص دادند که بر اساس آن توانستند فرمول جدید بـرای محاسـبه بهره اطلاعاتی بدست آورند، سپس هر دو روش ایجاد درخـت ( اصـلی و جدید) را بر روی دو بانک داده تست کردند که نتـایج حاصـله نشـانگر افزایش دقت الگوریتم و کاهش مدت زمان آن نسبت درصـد الگـوریتم اصلی بود.
در پژوهشی دیگر [ 3] نیز تغییراتی را در فرمول محاسبه بهرهاطلاعـاتی ایجاد کردند، آن ها ضریبی را به صفات اختصاص دادند که مقدار آن به صورت 0≤ q<1 در نظر گرفته شده بود. این مقدار بر اساس آزمایشات متعدد و همچنین موقعیت صفت مربوطه در بانـک داده بدسـت آمـده بود. این ضریب موجب میشد که صفاتی کهقبلاً دارای اهمیت زیـادی بودند ولی در زمان محاسبه بهره اطلاعاتی انتخاب نمیشدند برجسته تر شوند و در محاسبات استفاده شوند. نتایج حاصله از کار این گـروه نیـز نشانگر افزایش دقت درخت ID3 بود.
بعضی از محققان[4] نیز روشی برای افـزایش دقـت الگـوریتم درخـت ID3 ارائه کرده اند. آن ها الگوریتم درخت را به صورت موازی به کمـک MPI اجرا کردهاند و توانستهاند دقت الگوریتم را بالاتر ببرند.
گروهی دیگر [5] نیز بر روی وابستگی بین صفات یک بانک اطلاعـاتی کار کردند آن ها توانستند با استفاده از وابستگی و ارتباط بین صـفات و همچنین میزان افزونگی داده های موجـود در هـر صـفت دسـته بنـدی اطلاعات را تحت تأثیر قرار دهند. همچنین پارامتری را در اختیار کاربر قرار داده بودند که صفات دلخواه خود را ارزش گذاری کند.
جمعی دیگر از محققین [6] بر روی درخت ID3 کار کرده اند بـه نظـر آن ها درختی که به وسیله داده های آموزشی تولید میشود دارای نـویز بوده و درخت مناسبی نیست و از طرفی ممکن است داده های موجـود در زمان تست دارای MissValue باشد که با داده های زمان آمـوزش تفاوت داشته باشـد، آن هـا در ایـن تحقیـق ایـن مشـکلات را برطـرف کردهاند.
