یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
تابع ارزیابی مبتنی بر اطلاعات - تابع تولید کننده مکاشفه ای

در این دسته دو روش وجود دارد:

1)     روش درخت تصمیم(DTM)

در روش درخت تصمیم، نمونه­ها به یک الگوریتم C4.5­[Qui93]، که یکی از درخت­های تصمیم­گیری است اعمال می­شوند، سپس درخت هرس شده حاصل از الگوریتم C4.5را گرفته و کلیه ویژگی­هایی که در ان وجود دارد را به عنوان جواب مساله مشخص می­کنیم [Card93].

الگوریتم  C4.5

C4.5در اصل یک معیار استاندارد در یادگیری ماشین و الگوریتمی برای تولید درخت تصمیم است. این الگوریتم توسعه یافته الگوریتم ID3می­باشد که توسط Ross Quinlanایجاد شده است [Quin93]. درخت­های تولید شده توسط C4.5به منظور کلاس بندی بکار رفته و اغلب همانند روش­های اماری که در این زمینه کاربرد دارند، عمل می­کنند.

C4.5درخت­های تصمیم را از یک مجموعه داده­ازمایشی، با استفاده از مفهوم انتروپی اطلاعات[1] می­سازد. داده ازمایشی،مجموعه‌ای مثل S = s1,s2,…از نمونه­های کلاس بندی شده می‌باشد. هر نمونه si = x1,x2مانند برداری است که مختصات x1,x2,…، صفت یا ویژگی ان نمونه را نشان می­دهند. این داده­های ازمایشی با بردار C = c1,c2,…تکمیل می­شوند که مولفه­های c1,c2,…بیان­گر کلاسی هستند که هر نمونه به ان تعلق دارد.

انتخاب صفت درC4.5بر اساس حداقل کردن مقیاس اطلاعات در یک گره است. هر مسیر از ریشه به سمت یک گره، نمایان­گر یک قانون دسته­بندی می­باشد. تئوری بر این اساس است که تعداد ازمون­هایی که باعث می­شود یک نمونه جدید در داخل پایگاه داده، دسته­بندی شود، حداقل گردد. پیچیدگی درخت تصمیم به شدت وابسته به مقدار اطلاعاتی است که با ان صفت در ارتباطند. با انتخاب ان صفت، اطلاعات بیشتری از صفات دیگر، جدا و تقسیم می­شود.  الگوریتم اصولا صفتی که حداکثر توان جداسازی بین دسته­ها را دارد، انتخاب می­کند و درخت تصمیم را بر اساس ان می­سازد. تولید درخت تصمیم اولیه از روی مجموعه داده­ای، مهم­ترین بخش الگوریتم C4.5می­باشد. الگوریتم در نهایت یک دسته­بندی را در قالب یک درخت تصمیم تولید می­کند که دارای دو نوع گره است. یک گره به صورت برگ که یک دسته را مشخص می­کند و یک گره تصمیم که ازمون­هایی روی یک صفت انجام می­دهد تا یک شاخه یا زیر درخت به عنوان خروجی ازمون تولید شود. همچنین درخت­های مشابه­، به صورت بازگشتی به هر زیر مجموعه از نمونه­ها اعمال می­شود. این رویه ادامه می­یابد تا زیر مجموعه­ها شامل نمونه­هایی باشند که همگی به یک دسته تعلق داشته باشند. فرایند ساخت درخت، یک فرایند واحد نمی­باشد.متاسفانه، مشکل پیدا کردن کوچکترین درخت تصمیم از روی یک نمونه داده­ای مساله­ایNP-Completeاست. بنابراین، باید روش­های ساخت درخت غیر عقب­گرد باشند و به صورت حریصانه عمل نمایند.

الگوریتم C4.5چند حالت اساسی دارد:

1.     تمام نمونه­ها در لیست متعلق به یک کلاس باشند. وقتی این حالت رخ می­دهد، الگوریتم به سادگی، یک گره برگ برای درخت تصمیم می­سازد تا ان کلاس را انتخاب کند.

2.     هیچ­کدام از صفات، اطلاعات لازم را برای جداسازی و دسته بندی نداشته باشند. در این حالت الگوریتم یک گره تصمیم را در بالای درخت با استفاده از مقدار مورد انتظار کلاس می­سازد.

3.     به نمونه­ای متعلق به کلاسی که قبلا دیده نشده، برخورد شود. در این حالت نیز الگوریتم، دوباره یک گره تصمیم را در بالای درخت با استفاده از مقدار مورد انتظار کلاس می­سازد.

به عنوان شبه برنامه، الگوریتم عمومی ساخت درخت تصمیم دارای مراحل زیر است [Kots07]:

  1. حالت اساسی مربوطه را بررسی کن.
  2. برای هر ویژگی a، اطلاعات مورد نیاز برای دسته­بندی را پیدا کن.
  3. a_bestرا به عنوان ویژگی با بالاترین اطلاعات برای دسته­بندی، قرار بده.
  4. یک گره تصمیم که بر روی a_bestعمل جداسازی را انجام می­دهد، بساز.
  5. این مراحل را بر روی زیر لیست­های بدست امده از جداسازی روی a_bestتکرار کن و گره­های حاصله را فرزندان گره قبلی قرار بده.

الگوریتم C4.5نسبت به ID3دارای مزیت­هایی است که در زیر عنوان می­شود:

  • کار با هر دو ویژگی گسسته و پیوسته- به منظور کار با ویژگی­های پیوسته، C4.5یک استانه حداکثر می­سازد و لیست را به دو قسمت تقسیم می­کند، بطوریکه در یک قسمت مقادیر ویژگی بزرگتر از حد استانه و در قسمت دیگر، مقادیر ویژگی کوچکتر یا مساوی ان باشند [Quin96].
  • کار با داده­های ازمایشی با مقادیر ویژگی نامعلوم-  C4.5اجازه می­دهد تا مقادیر نامعلوم با علامت ?مشخص شوند. این مقادیر به سادگی در محاسبات انتروپی استفاده نخواهند شد.
  • کار با ویژگی­هایی که مقادیر متفاوت دارند.
  • هرس کردن درخت- C4.5 پس از ساختن درخت، یک بار به عقب برمی­گردد و انشعاب­های بی­فایده را با جایگزین کردن گره برگ بجای ان­ها، حذف می­کند.

C4.5از یک تابع مکاشفه بر پایه اطلاعات استفاده می­کند، یک فرم ساده این توابع برای مسائل دو کلاسه به صورت زیر است:


که در ان p  تعداد نمونه­های کلاس اول وnتعداد نمونه­های کلاس دوم است. فرض کنید که صفت F1به عنوان ریشه درخت در نظر گرفته شده است و مجموعه اموزشی را به دو زیرمجموعه T1و T0تقسیم کرده است. انتروپی ویژگی F1برابر است با:

الگوریتم درخت تصمیم به صورت زیر است[Car93]:


شکل 5- الگوریتم درخت تصمیم

شکل 5- الگوریتم درخت تصمیم

2)     روش استفاده شده توسط Kollerو Sahami­

روش استفاده شده توسط Kollerو Sahami­که اخیرا ارایه شده است، بر این پایه استوار است که ویژگی­هایی که اطلاعات مفید چندانی را در بر ندارند و یا اصلا اطلاعات مفیدی را در اختیار قرار نمی­دهند و می­توان ان‌ها را با سایر ویژگی­ها نمایش داد، یا ویژگی­هایی که بی­ربط هستند و یا اطلاعات اضافی هستند، را شناسائی و حذف می­کنیم. برای پیاده سازی این مطلب، تلاش می­کنیم تا با پوشش مارکوف ان‌ها را پیدا کنیم، به این صورت که یک زیرمجموعه از اطلاعات مانند T، یک پوشش مارکوف برای ویژگی fiاست، اگر fiبرای زیرمجموعه Tبصورت مشروط هم از کلاس و هم از سایر ویژگی­هایی که در Tنیستند، مستقل باشد [Kol96].

پوشش مارکوف[2]

پوشش مارکوف (MB)، کوچکترین مجموعه مطلوب از ویژگی­ها است که ان­ها را از تمام ویژگی­های دیگر مستقل می­سازد. TsamardinosوAliferisبیان کرده­اند، پوشش مارکوف از ویژگی­های به شدت وابسته تشکیل شده­اند که باعث بهینه شدن دسته­بندی خواهد شد [Tsam03]. پوشش مارکوف به طور خاص برای مجموعه داده­هایی مفید است که دارای تعداد بسیار زیادی ویژگی هستند. برای مثال، داده­های حاوی اطلاعات ژنی ده­ها هزار ویژگی دارند. Arnoneتخمین زده است که بطور متوسط چهار تا هشت ژن در ارگانیسم بالاتر، بر یکدیگر اثر می­کنند[Arno97] .

یک <V,G,J>Bayesian Network، تشکیل شده است از مجموعه­ای از متغیر­های V، یک گراف بدون دور جهت­دار Gو یک توزیع احتمال مشترک Jبر روی متغیر­های V. به بیان دیگر Bayesian Networkگرافی است که گره­های ان نشان دهنده متغیر­های تصادفی و یال­های ان نمایان­گر ارتیاط بین متغیر­ها می­باشد. در این شبکه­ها مقادیر والدین و فرزندان ان گره، دربردارنده اطلاعاتی درباره ان گره هستند، با این وجود همسران این گره نیز باید در نظر گرفته شوند، زیرا می­توانند به روشن شدن مسئله کمک کنند.

 
   

شکل 6- مثالی از گراف Bayesian Network


شکل 6- مثالی از گراف Bayesian Networ

پوشش مارکوف برای یک گره یا متغیر، مجموعه­ای از والدین و فرزندان و همسران است. تعریف رسمی­تر بدین صورت است که فرض کنید Vمجموعه تمام متغیرها باشد و Tزیرمجموعه­ای از متغیر­ها باشد که شامل Xنباشد، در این حالت Tیک پوشش مارکوف برای Xاست به شرطی که Xمستقل از V-T-Xباشد [Koll96].

به بیان اماری اگر داشته باشیم M ÍV-X-T،ان­گاه خواهیم داشت؛ P(T|XUM )= P(T|X).

در Bayesian Networks (BN)، اتحاد فرزندان و والدین T، همچنین والدین فرزندان T(همسران) معادل است با پوشش مارکوف [Pear88].  به عنوان مثال در شکل فوق، پوشش مارکوف برای Tبرابر {A, C, D, E}می­باشد.

پوشش مارکوف برای یک گره، شامل تمام متغیر­هایی می­شود که از ان گره در برابر بقیه گره­های شبکه محافظت می­کنند. این بدین معنا است که پوشش مارکوف برای یک گره، تنها دانش مورد نیاز برای پیش­بینی رفتار یک گره است[Pear88] .


[1]information entropy

[2]Markov Blanket

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26