از مزیت‏های درخت‏ تصمیم نسبت به بسیار دیگری از رده‏بندها همانند شبکه‏های عصبی قابلیت تفسیر آن است به راحتی می‏توان اطلاعات موجود در درخت را بصورت عبارات منطقی نمایش داد. مزیت دیگر درخت تصمیم رده‏بندی سریع است معمولا با چندین پرسش ساده رده‏بندی صورت می‏گیرد.

تصویر ۳-۳: نمونه‏ای از یک درخت تصمیم

الگوریتم C5 [53] یکی از الگوریتم‏هایی است که با بهره گرفتن از داده‏های آموزشی درخت تصمیم را می‏سازد درختی که توسط الگوریتم C5 تولید می‏شود می‏تواند برای رده‏بندی به کار برود. الگوریتم C5 به طریقی مشابه یا الگوریتم ID3 و با بهره گرفتن از مفهوم آنتروپی اطلاعات درخت تصمیم را از روی داده‏های آموزشی می‏سازد. داده‏های آموزشی یک مجموعه به صورت از نمونه‏های رده‏بندی شده است. هر نمونه یک بردار است که در آن ها نمایانگر ویژگی‏های آن نمونه هستند. داده‏های آموزشی با بردار نشانه‏گذاری شده‏اند که درآن‏ها ها رده متناظر با هر نمونه را نشان می دهد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

الگوریتم C5 از این حقیقت استفاده می‏کند که هر ویژگی داده می‏تواند برای تولید یک تصمیم به کار رود که بر اساس آن داده‏ها به زیر بخش‏های کوچک‏تری تقسیم می‏شوند این الگوریتم بهره اطلاعاتی نرمال شده ویژگی را محاسبه می‏کند و ویژگی برای ایجاد تصمیم انتخاب می‏شود که بهره اطلاعاتی نرمال شده بیشتری داشته باشد. تصمیم فهرست داده‏ها را براساس مقادیر مختلف آن ویژگی به چند زیر فهرست تقسیم می‏نماید پس از آن الگوریتم بر روی زیر فهرست‏ها دنبال می‏شود.
الگوریتم C5 موارد پایه کمی دارد. متداولترین مورد پایه هنگامی است که تمام نمونه‏های موجود در فهرست به یک رده یکسان تعلق داشته باشند. در چنین مواقعی، یک گره برگ حاوی برچسب آن رده تولید می‏شود. مورد پایه دیگر هنگامی است که هیچ ویژگی نتواند داده‏های مورد بررسی را افراز کند. در چنین مواردی مابین داده‏های باقیمانده رای اکثریت گرفته می‏شود و گره برگی با برچسب رده‏ای که اکثریت را داشته باشد ایجاد می‏شود علاوه بر این موارد ممکن است در یک زیر شاخه از یک گره هیچ نمونه‏ای وجود نداشته باشد (هیچ یک از نمونه‏ها در میان نمونه‏های مورد برسی مقدار خاص مورد نظر از ویژگی‏ای را که برای ساخت گره تصمیم به کار رفته بود نداشته‏اند) در این مورد گره برگی با برچسب رده اکثریت نمونه‏های مورد بررسی ساخته می‏شود. روال الگوریتم C5 را در شکل ۳-۴ مشاهده می‏نمایید.

1. 1. تست کردن موارد پایه

1. 1. به ازای هر ویژگی a مرحله ۳ را انجام بده

1. 1. بدست آوردن بهره اطلاعاتی نرمال شده هنگامی که داده‏ها براساس ویژگی a تفکیک شوند.

1. 1. انتخاب ویژگی ای که بالاترین بهره اطلاعاتی نرمال شده را دارد.

1. 1. تولید یک گره تصمیم که داده‏ها را بر اساس ویژگی انتخاب شده در مرحله قبل افراز می‏کند.

1. 1. تکرار عملیات فوق به ازای زیر لیست‏های بوجود آمده توسط افراز مرحله قبل

شکل۳-۴: الگوریتم C5
۳-۲. خوشه‏بندی
هدف از خوشه‏بندی که یکی از مهمترین روش‏های یادگیری بدونِ‏ناظارت محسوب می‏شود، کشف یک ساختارp در میان مجموعه داده‏ی D می‏باشد که تابع هدف بهینه شود. به عبارت دیگر، با توجه به انتظاراتی که با شنیدن نام خوشه‏بندی ایجاد می‏شود، پیش بینی می‏شود که یک الگوریتم مناسب قادر باشد تا از طریق بررسی شباهت‏ها یا تفاوت‏هایی (مانند فاصله‏ها) موجود میان نقاط داده‏ای در مجموعه داده مفروض به کشف ساختار بپردازد. به این ترتیب خوشه‏هایی ایجاد می‏شود که آیتم‏های موجود در هر خوشه بسیار شبیه به یکدیگر باشند و با آیتم‏های خوشه‏های دیگر نیز تا حد ممکن متفاوت باشند. از جنبه محاسباتی باید در نظر داشت که تقسیم N نمونه به C خوشه، ایجاد تعداد زیادی از افرازها را فراهم می‏سازد.[۲] استفاده از عدد استرلینگ را برای نشان دادن داده‏های ممکن برای این افرازها را معرفی کرده‏است.
رابطه (۳-۱۳) S_n^©
به طور کلی یک الگوریتم افراز یک مجموعه داده‏ی D را می‏گیرد و مجموعه‏ای از خوشه‏ها P={C_i,…,C_C} را که یک شِما از افراز نمونه‏ها از D است را برمی‏گرداند. این بدین معنا است که خوشه‏های C_i با هم اشتراک ندارند و اجتماع همه آنها مجموعه داده را کامل می‏کند.
[۵۶] الگوریتم افرازبندی را به دو دسته‏ی اصلی تقسیم بندی می‏کند؛ (۱) بسته‏ای، (۲) افزایشی. الگوریتم‏های خوشه‏بندی بسته‏ای، کل مجموعه داده‏ها را بررسی می‏کنند تا مناسب‏ترین راه را برای سازماندهی آنها پیدا کنند. الگوریتم‏های افزایشی، در هر بار، یک مرحله از افراز داده‏ها را انجام می‏دهد. به طوریکه هر مرحله شامل یک آیتم داده‏ای واحد باشد. الگوریتم‏های بسته‏ای در ابتدای کار به تمام داده‏های مجموعه داده نیاز دارند. در حالیکه الگوریتم‏های افزایشی برای برنامه‏های کاربردی برخطی که داده‏ها در جریان مشاهدات افزایش پیدا می کنند مناسب هستند.
۳-۲-۱. الگوریتم‏های افراز بسته‏ای
این الگوریتم‏ها شامل چهار دسته‏ی کلی برای خوشه‏بندی می‏باشند ۱) خوشه‏بندی مبتنی بر بخش‏بندی (تابع هدف)، ۲) خوشه‏بندی سلسله مراتبی، ۳) خوشه‏بندی مبتنی بر مدل، و ۴) خوشه‏بندی مبتنی بر گراف.
در خوشه‏بندی مبتنی بر بخش بندی، اساس کار یک تابع هدف است. که کمینه سازی آن ما را به کشف ساختار موجود در مجموعه رهنمون می‏سازد و (در بسیاری موارد مسئله ی بهینه ‏سازی را می‏توان به خوبی فرموله کرد) به طور معمول در این گروه از الگوریتم‏ها، تعداد خوشه‏ها از قبل مشخص است و کار با بهینه ‏سازی تابع هدف ادامه پیدا می‏کند. با اعمال برخی تغییرات روی الگوریتم‏ها می‏توان تعداد خوشه‏ها را به طور پویا تنظیم کرد. مسئله‏ی اصلی در خوشه‏بندی سلسله مراتبی توسعه‏ی متوالی خوشه‏ها است که می‏تواند توسط الگوریتم‏های حریصانه^[۲۰۳] و یا بهینگی مرحله‏ای^[۲۰۴] انجام شود. در این روش کار به دو طریق بالا به پایین و یا پایین به بالا انجام می‏پذیرد. در حالت بالا به پایین، ابتدا کل مجموعه داده‏ها بعنوان یک خوشه در نظر گرفته می‏شوند و کار با تقسیمات متوالی ادامه پیدا می‏کند تا در آستانه توقف برسد. در حالت پایین به بالا، هر یک از نقاط به عنوان خوشه اولیه در نظر گرفته‏می‏شود و سپس ادغام صورت می‏گیرد. ( این فرایند ما را به مفهوم خوشه‏بندی انباشتی^[۲۰۵] رهنمود می‏سازد). آنچه برای خوشه‏بندی سلسله مراتبی مهم است، انتخاب تابع فاصله مناسب و نحوه‏ی تعیین فاصله موجود میان الگوها و نقاط است. با توجه به این مورد، طیف وسیعی از روش‏ها (تک پیوندی، پیوند کامل^[۲۰۶] و…) به وجود می‏آید. خوشه‏بندی مبتنی بر داده‏ها در نظر می‏گیرد. سپس پارامترها برآورد می‏شوند.
۳-۲-۱-۱.خوشه‏بندی سلسله مراتبی پایین به بالا
الگوریتم‏های خوشه‏بندی سلسله مراتبی، داده‏ها را بصورت گراف نمایش می‏دهند. ساخت گراف‏ها (این روش‏ها با در نظر گرفتن هر یک از نمونه ها، ساختار را آشکار می‏سازند) را می‏توان با توجه به دو رویکرد انجام داد: پایین به بالا، و بالا به پایین، در رویکرد پایین به بالا، که به آن رویکرد انباشتی نیز گفته می‏شود، هر الگو را یک خوشه تک عنصری در نظر گرفته و سپس بطور متوالی نزدیک‏ترین خوشه‏ها را ادغام می‏کنیم. این فرایند تا جایی ادامه پیدا می‏کند که به یک خوشه منفرد یا یک آستانه از پیش تعریف شده دست پیدا کنیم. رویکرد بالا به پایین که به آن رویکرد تقسیم کننده نیز گفته می‏شود، در جهت مخالف رویکرد قبلی عمل می‏کند. در این رویکرد، کل مجموعه داده در ابتدا یک خوشه منفرد در نظر گرفته شده، و در ادامه بطورمتوالی به خوشه‏های کوچکتر تقسیم می‏شود. با توجه به طبیعت فرآیندهای بالا به پایین و پایین به بالا، درمی‏یابیم که این روش‏ها در اغلب موارد از نظر محاسباتی ناکارا هستند. تنها حالتی که امکان دارد در آن پیاده سازی روش‏های مذکور بصرفه باشد، زمانی است که با الگوهای دودویی مواجه هستیم.
نتایج حاصل از خوشه‏بندی سلسله مراتبی بصورت دندروگرام نمایش داده می‏شود. همانطور که در شکل۳-۵ ملاحظه می‏کنید، دندروگرام، یک درخت دودویی با ریشه معین است که برگ‏های آن از تمامیِ اجزای داده‏ها تشکیل شده‏است. فرایند ادغام متوالی خوشه‏ها، با توجه به مقادیرفاصله هدایت می‏شود. با توجه به مقدار فاصله، دنباله‏ای از خوشه‏های تودرتو تولید می‏گردد. دندروگرام‏ها، دارای ساختار جالبی هستند که ما را در ادغام خوشه‏ها یاری می‏رساند، گره‏هایی که در پایین گراف قرار می‏گیرند متناظر با نمونه‏های موجود می‏باشند و همانطور که در گراف به سمت بالا حرکت می‏کنیم، می‏بینیم نقاطی که با توجه به تابع تشابهِ مفروض به یکدیگر نزدیک هستند ادغام شده‏اند. با حرکت در جهت بالا، اندازه خوشه‏ها نیز افزایش می‏یابد. از طرف دیگر فرایند ادغام تا زمانی ادامه می‏یابد که یا تنها یک خوشه داشته باشیم و یا اینکه به یک آستانه مناسب برسیم.

شکل۳-۵: مثالی از نمودار دندوگرام در تشخیص عبارت‏های اسمی هم‏مرجع ^[۲۰۷]