دانلود فایل پاورپوینت الگوریتم داده کاوی همراه با درخت تصمیم گیری

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

کلاسه بندی

■ فرايندی دو مرحله ای است :

■ساخت مدل :

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

■ يک تاپل X با يک بردار صفت X=(x1,x2,…,xn) نمايش داده می‌شود . فرض می شود که هر تاپل به يک کلاس از پيش تعريف شده متعلق است .

■هرکلاس با يک صفت که به آن صفت برچسب کلاس می‌گوييم مشخص می‌شود .

■ مجموعه آموزشی به صورت تصادفی از پايگاه انتخاب می شود .

■به اين مرحله ، مرحله يادگيری نيز می گويند .

■استفاده از مدل :

■از طريق يک تابع y=f(X) برچسب  کلاس هر تاپل X از پايگاه را پيش بينی می شود .

■اين تابع به صورت قواعد کلاسه‌بندی ، درخت‌های تصميم گيری يا فرمول‌های رياضی است .

اسلاید 2 :

درخت های تصميم گيری

■يکی از روش های کارآمد و با کاربرد گسترده کلاسه بندی است .

■مدل حاصل از اين روش به صورت درختهای تصميم گيری است :

■هر گره در اين درخت نشان دهنده يک آزمون بر روی يک صفت است .

■هر شاخه خارج شونده از يک گره نشان دهنده خروجی های ممکن آزمون است .

■هر برگ نشان دهنده يک برچسب کلاس است .

■نحوه استفاده از درخت تصميم گيری :

■اگر تاپلی چون X که برچسب کلاس آن نامشخص است داشته باشيم صفات اين تاپل در درخت مورد آزمون قرار می گيرند و يک مسير از ريشه به سمت يک برگ که برچسب يک کلاس را دارد ايجاد می شود .

اسلاید 3 :

مجموعه داده های آموزشی

اسلاید 4 :

درخت تصميم گيری برای buys_computer

اسلاید 5 :

الگوريتم برای درخت های تصميم گيری

■الگوريتم پايه

■درخت به صورت بالا-پايين بازگشتی ساخته می شود .

■در آغاز تمام مجموعه آموزشی در ريشه قرار دارند .

■فرض می کنيم صفات مقادير گسسته دارند .

■صفات به صورت بازگشتی بر حسب صفات انتخاب شده بخش بندی می شوند .

■صفات آزمون بر اساس يک روال هيوريستيک مانند بهره اطلاعاتی ، شاخص جينی يا نسبت بهره انتخاب می شوند .

■شرايط توقف الگوريتم

■تمام نمونه های مربوط به يک نود متعلق به يک کلاس باشند .

■صفتی برای بخش بندی بيشتر باقی نمانده باشد .

■نمونه ای باقی نمانده باشد .

اسلاید 6 :

چالش ها

■روش های ساختن درختان تصميم گيری فرض می کنند که تمام مجموعه آموزشی به طور همزمان می تواند در ديسک ذخيره شود .

■روش های مذکور بصورت پياپی مجموعه آموزشی را از ديسک می خوانند .

■هدف : طراحی درخت های تصميم گيری که هر نمونه آموزشی را فقط يکبار بخواند زمان کوتاه ثابتی را برای پردازش آن صرف کند .

اسلاید 7 :

نکات کليدی

■برای يافتن بهترين صفت در هر گره ، در نظر گرفتن يک زيرمجموعه کوچک از نمونه های آموزشی که از آن گره عبور می کنند کافی است .

■با در دست داشتن جريانی از نمونه ها ، اولين نمونه ها برای انتخاب صفت ريشه استفاده می شوند .

■با تعيين شدن صفت ريشه ، نمونه های بعدی به سمت پايين و برگهای مربوطه عبور داده می شوند تا برای انتخاب صفت در آنجا استفاده شوند .

■اين عمل به صورت بازگشتی تکرار می شود .

■چه تعداد نمونه در هر گره لازم است ؟

■از يک نتيجه آماری به نام Hoeffding bound  استفاده می کنيم .

اسلاید 8 :

Hoeffding Bound

■يک متغيير تصادفی با نام r که دارای مقادير حقيقی و برد R است را در نظر بگيريد .

■فرض کنيد که n مشاهده مستقل از اين متغير انجام می‌دهيم .

■ميانگين اين مشاهدات :

■Hoeffding Bound نشان می‌دهد که ميانگين واقعی متغير r  بعد از اين n مشاهده با احتمال 1-δ حداقل برابر –ε       است که در آن : 

اسلاید 9 :

چه تعداد نمونه کافی است ؟

■فرض کنيد G(Xi)  روال ابتکاری برای انتخاب صفات آزمون باشد مانند بهره اطلاعاتی و شاخص جينی .

■فرض کنيد که Xa  صفت دارای بالاترين مقدار ارزيابی بعد از n نمونه باشد .

■فرض کنيد که Xb صفت دارای دومين بالاترين مقدار ارزيابی بعد از n نمونه باشد .

■آنگاه با يک δ مناسب اگر  بعد از مشاهده n نمونه :                                            آنگاه :

■گره می تواند بر حسب Xa شکافته شود و نمونه های بعدی به سمت برگهای جديد عبور داده می شوند .

■

■

اسلاید 10 :

الگوريتم Hoeffding Tree

■Hoeffding Tree Input

■S: sequence of examples

■X: attributes

■G( ): evaluation function

■d : desired accuracy

■Hoeffding Tree Algorithm

■for each example in S

■  retrieve G(Xa) and G(Xb)   //2 highest G(Xi)

■  if ( G(Xa) - G(Xb) > ε )

■  split on Xa

■  recurse to next node

■  break