استفاده از شبکه ها و روش های طبقه بندی

دانلود پایان نامه

پس از آن که مجموعه های پرتکرار استخراج شدند، نوبت به استخراج قوانین قوی با اطمینان بالا می رسد. در این مرحله تمام زیر مجموعه های غیر تهی یک مجموعه پرتکرار نوشته شده و تمامی قواعد ممکن بر اساس آن استخراج می شود. سپس اطمینان را برای هر یک از قوانین محاسبه نموده و اگر بیشتر از حد قابل قبول بود به عنوان یک قانون پذیرفته می شود(آخوندزاده نوقانی،1388).
الگوریتم های طبقه بندی
الگوریتم ها و روش های مختلفی تا کنون برای طبقه بندی پیشنهاد شده اند که برای مثال می توان از روش های طبقه بندی با استفاده از درخت تصمیم C4.5، درخت طبقه بندی و رگرسیونCART، شبکه های بیزین، SVM، طبقه بندی مبتنی بر قواعد، طبقه بندی با استفاده از شبکه های عصبی و …. نام برد که در زیر برخی از آن ها تشریح شده اند:
الگوریتم درخت طبقه بندی و رگرسیون (CART)
روش درخت طبقه بندی و رگرسیون (CART) توسط Breiman و همکارانش در سال 1984 پیشنهاد شد(Larsed 2003).
درخت های تصمیم تولید شده توسط CART دودویی بوده و دقیقا دو شاخه برای هر گره تصمیم دارد. CART به صورت بازگشتی داده های آموزشی را بر اساس مقادیر مشابه مشخصه هدف به زیر مجموعه هایی تقسیم می کند. الگوریتم CART با انجام یک جستجوی گسترده در همه متغیرهای موجود و تمامی تقسیم های ممکن، نقطه تقسیم بهینه را برمبنای معیار زیر انتخاب نموده درخت تصمیم را توسعه می دهد.
فرض کنیم Ф(s|t) یک مقیاس برای تعیین میزان مناسب بودن یک کاندید تقسیم S در گره t باشد:
# classes
Ф(s|t) = 2PL PR Σ|P ( j |tL ) – P ( j |tR)
j=1
tL= فرزند چپ نود t
tR= فرزند راست نود t
PL= تعداد رکوردها در tL تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
PR= تعداد رکوردها در tR تقسیم بر تعداد رکوردها در مجموعه ی آموزشی
P (J|tL) = تعداد رکوردهای کلاس j در tL تقسیم بر تعداد رکوردها در t
P (j|tR) = تعداد رکوردهای کلاس j در tR تقسیم بر تعداد رکوردها در t
نقطه تقسیم بهینه جایی است که بیشترین مقدار را در بین تمام نقاط تقسیم در گره t داشته باشد. به طور کلی CART به صورت بازگشتی تمام نقاط تقسیم باقی مانده را ملاقات کرده و تابع فوق را برای یافتن نقطه تقسیم بهینه در هر گره اجرا می نماید. در نهایت هیچ گره تصمیمی باقی نمی ماند و درخت به طور کامل توسعه می یابد. البته ممکن است تمامی گره ها همگن نباشد که منجر به نوع خاصی از خطای طبقه بندی خواهد شد.
هم چنین در الگوریتم CART عملیات هرس کردن گره ها و شاخه ها انجام می گردد تا قابلیت تعمیم نتایج طبقه بندی افزایش یابد. هر چند که درخت کاملا توسعه یافته پایین ترین نرخ خطا را در مجموعه آموزشی دارد ولی مدل نهایی ساخته شده بر اساس آن ممکن است بسیار پیچیده شود. با توسعه هر گره تصمیم، زیر مجموعه رکوردهای موجود برای تجزیه و تحلیل کوچکتر شده و محدوده کمتری از جمعیت را شامل می شود. بنابراین هرس نمودن درخت، باعث عمومیت یافتن نتایج خواهد شد(Larsed 2003).
الگوریتم درخت تصمیم C4.5
الگوریتم C4.5 از نسل الگوریتم ID3 برای تولید درخت تصمیم است که از قانون هرس استفاده می کند. دقیقا مشابه الگوریتم CART، الگوریتم C4.5 نیز به صورت بازگشتی هر گره تصمیم را ملاقات کرده و نقطه تقسیم بهینه را انتخاب می کند تا جایی که دیگر انشعاب امکان پذیر نباشد. با این حال، تفاوت های جالبی بین CART و C4.5 وجود دارد(Larsed 2003).
الگوریتم C4.5 به تقسیم های دودویی محدود نمی باشد و قادر است درخت های با شاخه های بیشتر را تولید نماید. در این الگوریتم به طور پیش فرض برای هر یک از مقادیر صفات یک شاخه تولید می شود. از آن جا که ممکن است تعداد تکرار برخی از مقادیر کم باشد، در مواردی منجر به ایجاد درختی انبوه و بزرگتر از آن چه مورد نظر بوده می گردد که با استفاده از هرس سعی می شود درخت کوچکتر شده و این مشکل برطرف گردد. حتی اگر هیچ خطایی در داده های آموزشی وجود نداشته باشد باز هم هرس انجام می شود که این امر باعث
می شود درخت عام تر شده و وابستگی کمتری به مجموعه آموزشی داشته باشد.
الگوریتم C4.5 توانایی کار با داده ها و صفات پیوسته، گسسته، صفات فاقد مقدار و داده های نویزی را دارد. این الگوریتم بهترین صفت را با استفاده از معیار بی نظمی انتخاب می کند و به دلیل استفاده از عامل Gain Ratio قادر به بکارگیری صفات با مقادیر بسیار زیاد می باشد(Wu, Kumar 2006).
کلید ساختن درخت تصمیم در الگوریتم C4.5 این است که کدام صفت برای تقسیم استفاده شود. اکتشاف و ابتکار در این الگوریتم برای انتخاب صفت به صورت حداکثر بهره اطلاعات است. الگوریتم C4.5 از مفهوم دستیابی اطلاعاتGain Information یا کاهش آنتروپی ( بی نظمی) برای انتخاب تقسیم بهینه استفاده می نماید. آنتروپی آندازه گیری ناخالصی یا بی نظمی مجموعه داده D است. هرچه داده ها خالص تر و خاص تر باشد آنتروپی کوچک تر بوده و در واقع آنتروپی زیاد به معنی اطلاعات کم است. در آنتروپی، بیت واحد اطلاعات است. در واقع بیت ها نمادهای حامل اطلاعات هستند، نه خود اطلاعات.
m
Entropy (D) = - Pi log2(Pi )