داده‌کاوی جريان‌داده‌ها با درخت‌های تصميم‌گيری

داده‌کاوي جريان‌داده‌ها با درخت‌هاي تصميم‌گيري رهگذرآقايدکتر  ناب  جاستاد  لیعباس  عقديمي يوحناکنندهتهيه پاشاييکاوهی 1 کالسه بندی ■ ■ ■ 2 فرايندی دو مرحله ای است : ساخت مدل : ■ تحليل يک مجموعه آموزشی که مجموعه‌ایازتاپل‌هایپايگاه است و مشخص کردن برچسب کالس‌های مربوط به اين تاپل‌ها . ■ يک تاپل Xبا يک بردار صفت ) X=(x1,x2,…,xnنمايش داده می‌شود .فرض می شود که هر تاپل به يک کالس از پيش تعريف شده متعلق است . ■ هرکالس با يک صفت که به آن صفت برچسب کالس می‌گوييم مشخص می‌شود . ■ مجموعه آموزشی به صورت تصادفی از پايگاه انتخاب می شود . ■ به اين مرحله ،مرحله يادگيری نيز می گويند . استفاده از مدل : ■ از طريق يک تابع ) y=f(Xبرچسب کالس هر تاپل Xاز پايگاه را پيش بينی می شود . کالسهبندی ،درخت‌های تصميم گيری يا فرمول‌های رياضی است . ‌ ■ اين تابع به صورت قواعد درخت های تصميم گيری ■ يکی اLز روش های کارآمد و با کاربرد گسترده کالسه بندی است . ■ مدل حاصل از اين روش به صورت درختهای تصميم گيری است : ■ هر گره در اين درخت نشان دهنده يک آزمون بر روی يک صفت است . ■ هر شاخه خارج شونده از يک گره نشان دهنده خروجی های ممکن آزمون است . ■ هر برگ نشان دهنده يک برچسب کالس است . ■ نحوه استفاده از درخت تصميم گيری : ■ اگر تاپلی چون Xکه برچسب کالس آن نامشخص است داشته باشيم صفات اين تاپل در درخت مورد آزمون قرار می گيرند و يک مسير از ريشه به سمت يک برگ که برچسب يک کالس را دارد ايجاد می شود . 3 مجموعه داده های آموزشی ag e <=30 <=30 31…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40 in co me st u d e n t h ig h no h ig h no h ig h no me d iu m no low ye s low ye s low ye s me d iu m no low ye s me d iu m ye s me d iu m ye s me d iu m no h ig h ye s me d iu m no cre d it _ra t in g fa ir e xce l l e n t fa ir fa ir fa ir e xce l l e n t e xce l l e n t fa ir fa ir fa ir e xce l l e n t e xce l l e n t fa ir e xce l l e n t b u ys_co mp u t e r no no ye s ye s ye s no ye s no ye s ye s ye s ye s ye s no 4 buys_computer درخت تصميم گيری برای age? <=30 overcast 30..40 student? yes >40 credit rating? no yes excellent fair no yes no yes 5 الگوريتم برای دLرخت های تصميم گيری ■ الگوريتم پايه ■ ■ ■ ■ ■ درخت به صورت باال-پايين بازگشتی ساخته می شود . در آغاز تمام مجموعه آموزشی در ريشه قرار دارند . فرض می کنيم صفات مقادير گسسته دارند . صفات به صورت بازگشتی بر حسب صفات انتخاب شده بخش بندی می شوند . صفات آزمون بر اساس يک روال هيوريستيک مانند بهره اطالعاتی ،شاخص جينی يا نسبت بهره انتخاب می شوند . ■ شرايط توقف الگوريتم ■ تمام نمونه های مربوط به يک نود متعلق به يک کالس باشند . ■ صفتی برای بخش بندی بيشتر باقی نمانده باشد . ■ نمونه ای باقی نمانده باشد . 6 چالش ها ■ روش های ساختن درختان تصميم گيری فرض می کنند که تمام مجموعه آموزشی به طور همزمان می تواند در ديسک ذخيره شود . ■ روش های مذکور بصورت پياپی مجموعه آموزشی را از ديسک می خوانند . ■ هدف :طراحی درخت های تصميم گيری که هر نمونه آموزشی را فقط يکبار بخواند زمان کوتاه ثابتی را برای پردازش آن صرف کند . 7 نکات کليدی ■ برای يافتن بهترين صفت در هر گره ،در نظر گرفتن يک زيرمجموعه کوچک اLز نمونه های آموزشی که از آن گره عبور می کنند کافی است . ■ با در دست داشتن جريانی از نمونه ها ،اولين نمونه ها برای انتخاب صفت ريشه استفاده می شوند . ■ با تعيين شدن صفت ريشه ،نمونه های بعدی به سمت پايين و برگهای مربوطه عبور داده می شوند تا برای انتخاب صفت در آنجا استفاده شوند . ■ اين عمل به صورت بازگشتی تکرار می شود . ■ چه تعداد نمونه در هر گره الزم است ؟ ■ از يک نتيجه آماری به نام Hoeffding boundاستفاده می کنيم . 8 Hoeffding Bound ■ يک متغيير تصادفی با نام rکه دارای مقادير حقيقی و برد Rاست را در نظر بگيريد . ■ فرض کنيد که nمشاهده مستقل از اين متغير انجام می‌دهيم . ■ ميانگين اين مشاهدات : ‏r مLیLهد کLLه مLيانLگينواLقLعیمLتغير rبLLعد از اLيLن nمLشاهده LبLLا ■ Hoeffding BoundنLLشان ‌د اLسLتکLLه در آLن: اLحLتماLل δ-1حLداLقLلبLLراLبر –ε ‏r ) R2 ln(1/  ‏ 2n 9 چه تعداد نمونه کافی است ؟ ■ فرض کنيد ) G(Xiروال ابتکاری برای انتخاب صفات آزمون باشد مانند بهره اطالعاتی و شاخص جينی . ■ فرض کنيد که Xaصفت دارای باالترين مقدار ارزيابی بعد از nنمونه باشد . ■ فرض کنيد که Xbصفت دارای دومين باالترين مقدار ارزيابی بعد از nنمونه باشد . ■ آنگاه با يک δمناسب اگر بعد از مشاهده nنمونه : آنگاه : ‏G G( Xa )  G( Xb )   ■ گره می تواند بر حسب Xaشکافته شود و نمونه های بعدی به سمت برگهای جديد عبور داده می شوند . 10 Hoeffding Tree الگوريتم ■ Hoeffding Tree Input ■ S: sequence of examples ■ X: attributes ■ G( ): evaluation function ■  : 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 11 Hoeffding Tree الگوريتم Packets > yes 10 no Data Stream Protocol = http Packets > yes 10 no Bytes > 60K ye s Protocol = ftp Data Stream Protocol = http O(leaves * attributes * values * classes) : حافظه مورد نياز 12 درختان تصميم گيری بسيار سريع VFDT ■ برابریها : ‌ ■ وقتی که دو يا بيشتر صفت در Gبسيار شبيه هستند نمونه‌های زيادی برای تصميم‌گيری بين آنها ،با اطمينان باال نياز است . ■ در اين مورد ،اينکه چه صفتی انتخاب می شود اختالف اندکی را بوجود می‌آورد VFDT. بصورت انتخابی تصميم می‌گيرد که يک برابری وجود دارد و شکاف را روی يکی از بهترين صفتهای جاری انجام می‌دهد . ‌ ■ محاسبه : G ■ بخش قابل توجهی از زمان به ازای هر نمونه برای محاسبه Gصرف می شود . ■ محاسبه دوباره Gبرای هر نمونه جديد ناکارا است ،چون احتمال تصميم برای شکاف در آن نقطه مشخص غير محتمل است . ■ بنابراين VFDTبه کاربر اجازه می‌دهد تا يک حداقل تعداد برای نمونه های جديد يا nmin را مشخص کند که بايد در هر برگ انباشته شود قبل از اينکه Gدوباره محاسبه شود . 13 درختان تصميم گيری بسيار سريع VFDT ■ حافظه : ■ ■ ■ ■ 14 بسياری از برنامه های کاربردی RAMمحدودی برای يادگيری مدلهای پيچيده دارند . حافظه مورد استفاده VFDTهمان حافظه مورد نياز برای نگهداری شمارنده‌ها در برگهای در حال رشد است . اگر به حداکثر حافظه برسيم VFDTبرگهايی را که احتمال شکاف در آنها کم است غيرفعال می کند تا حافظه برای برگهای جديد فراهم شود . هنگامی که احتمال شکاف يک برگ غيرفعال از برگهای موجود بيشتر شود آن برگ دوباره می‌تواند فعال شود . مقايسه‌ای بين VFDTوC4.5 15 )1( منابع ■ ■ B. Babcock, S. Babu, M. Datar, R. Motwani and J. Widom, “ Models and Issues in Data Stream Systems”, Proc. 2002 ACM-SIGACT/SIGART/SIGMOD Int. Conf. on Principles of Data base (PODS'02), Madison, WI, June 2002. (Conference tutorial) Gurmeet Singh Manku, Rajeev Motwani.. Approximate Frequency Counts over Data Streams, VLDB’02 ■ C. Giannella, J. Han, J. Pei, X. Yan and P.S. Yu, “Mining Frequent Patterns in Data Streams at Multiple Time Granularities”, H. Kargupta, A. Joshi, K. Sivakumar, and Y. Yesha (eds.), Next Generation Data Mining, 2003. ■ Geoff Hulten, Laurie Spencer, Pedro Domingos: Mining time-changing data streams. KDD 2001: 97-106 ■ J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate generation. In Proc. Of 2000 ACM SIGMOD,pages 1-12,2000. 16 )2( منابع ■ S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003. ■ Mohamed Medhat Gaber , Shonali Krishnaswamy , Arkady Zaslavsky . Ubiquitous Data Stream Mining , 2003 ■ Andrew Wu . Mining Data Streams : A Review . 2003 17 پايان پرسش و پاسخ باتشکر 18