سامانه پژوهشی – کاربرد داده کاوی در کشف دانش پنهان میان داده های سامانه ۱۳۷ …

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(P)
i=1
m تعداد کلاس های موجود است و pi احتمال آن است که یک متغیر دلخواه در D متعلق به کلاس Ci باشد که این احتمال به صورت |Ci,D|/|D| تخمین زده می شود. ( |D|و |Ci,D| تعداد رخداد در D و Ci,D را نشان می دهد)
فرض می کنیم صفت A دارای v مقدار متمایز به صورت {a1, a2, … ,av} باشد یا به عبارت دیگر A یک صفت گسسته است. اگر بخواهیم D را برحسب صفت A تقسیم کنیم v بخش یا زیرمجموعه مانند {D1,D2,….Dv} حاصل می شود. آنتروپی مورد انتظار اگر Ai به عنوان ریشه به کاربرده شود برابر است با:
Entropy(D)=|Dj|/|D|* Entropy(D)
اطلاعات حاصل از انشعاب بر حسب صفت A را به صورت زیر تعریف می کنیم:
[Gain(A) = Entropy(D)-EntropyA(D))]
هرچه مقدار بهره صفت A یعنی (GainA) بیشتر باشد یا به عبارت دیگر هرچه (Entropy D) کمتر باشد، صفتA گزینه مناسب تری برای انتخاب به عنوان صفت تقسیم می شود.
الگوریتم های شبکه های بیزین
در برخی از الگوریتم های طبقه بندی تعدادی شی موجود است که همگی دارای یک بردار از خصیصه ها می باشند. مدل شبکه بیزین یک مدل بر مبنای احتمال است که رویدادهای مشاهده شده و ذخیره شده را بررسی کرده و مشابهت رویدادها را با استفاده از خصیصه های به ظاهر نامشابه تعیین می کند. شبکه بیزین یک مدل گرافیکی است که متغیرها در یک مجموعه داده[۴۴] را به صورت گره[۴۵] نشان داده و احتمال یا شرط استقلال بین آن ها را بیان می کند. ارتباط سببی ( علی) بین گره ها هم می تواند توسط شبکه بیزین نمایش داده شود.
هم چنین خطوط[۴۶] شبکه لزوماً ارتباط یا تاثیرهای مستقیم بین متغیرها را نشان نمی دهد. در صورتی که مقادیر گم شده برای دانلود فایل متن کامل پایان نامه به سایت ۴۰y.ir مراجعه نمایید.

ta.org/wp-admin/post-new.php#footnote-47″>[۴۷] در داده ها زیاد باشد، این نوع شبکه بسیار بزرگ و گسترده شده و بهترین پیش بنی ممکن را با استفاده از اطلاعات موجود ارائه می دهد(Wu, Kumar 2006).
در این مدل ابتدا فرض می شود که هر شی به یکی از کلاس های مشخص متعلق است. سپس احتمال درست بودن این فرضیه محاسبه می شود. برای این کار تمامی اشیا یک بار پویش شده و با توجه به داده های آموزشی صحت احتمال منظور شده به طور قابل توجهی افزایش یا کاهش می یابد. هدف استخراج قواعدی است که بر اساس ن ها بتوان با دادن خصیصه های یک شی کلاس آن را تعیین نمود.
الگوریتم بیزین با توجه به سادگی پیاده سازی وعدم نیاز به روش های پیچیده برای تخمین پارامترهای تکراری مورد توجه می باشد. این ویژگی ها بدین معنی است که به راحتی بر روی داده های بسیار بزرگ اعمال می شود و به دلیل امکان تفسیر و تحلیل ساده، کاربران غیر متخصص نیز می توانند دلایل طبقه بندی انجام شده توسط این کاربر را درک نماید.
در این الگوریتم Ci کلاس های تعریف شده و X شی مورد نظر است که تعدادی خصیصه دارد.
احتمال های زیر برای اجرای مدل محاسبه می گردد:
P(ci|x): احتمال این که شی x متعلق به کلاس ci باشد.
P(x|ci): احتمال این که در صورتی که شی x متعلق به کلاس ci باشد، مقادیر خصیصه های آن برای ساخت قواعدی انتخاب شود.
P(c): احتمال این که هر شی متعلق به کلاس ci باشد.
P(x): احتمال این که مقادیر خصیصه های شی x بدون توجه به کلاس آن برای ساخت قواعد انتخاب شود.
فرضیه الگوریتم بیزین بر اساس فرمول زیر می باشد:
P(ci|x)=P(x|ci) P(ci) / P(x)