مقاله درباره ، الگوریتم، R، _Ref373604892، r، رکوردهایی، ابرصفحه، دادهها

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

توجه به وابستگی بین متغیرها نشان میدهد.
رابطه 2-6 px1,x2,..,xn=i=1npxi|parentsyi2-2-4 مدل قانونمحوردسته بندی با روش قانونمحور:
قوانین راه خوبی برای نشان داده یکسری اطلاعات است. یک دسته بندی قانون محور از مجموعهای از قانون if-then برای دسته بندی استفاده میکند.یک قاعده if-then بصورت زیر میباشد:
If condition then conclusion
که بخش if را پیش شرط و بخش then را نتیجه میگوییم.
هر قانون بوسیله دو معیار پوشش و درستی مورد ارزیابی قرار میگیرد.برای مجموعه داده D معیار یوشش قانون R به صورت رابطه 2-7 و درستی قانون R به صورت رابطه 2-8 تعریف میشود :
رابطه 2-7 CoverageR=ncoverDرابطه 2-8 accuracyR=ncorrectncoverکهD تعداد کل رکوردها و ncover تعداد رکوردهایی که توسط قانون R پوشش داده میشوند و ncorrect تعداد رکوردها پوشش داده شدهای است که بطور درست توسط R دسته بندی شدهاند.
اگر یک رکورد بوسیله چندین قانون ارضا شود تداخل پیش می آید که از قانون ترتیب اندازه یا ترتیب قانون بر طرف میشود.
ترتیب اندازه: قانونی انتخاب میشود که تعداد خصوصیت بیشتری را در برگیرد.
ترتیب قانون: قانونها از قبل به دو روش مبتنی بر قانون یا کلاس دسته بندی اولویتبندی میشوند. در روش مبتنی بر قانون، یک لیست اولویت دار از قوانین ساخته میشود که در آن قوانین بر پایه درستی، پوشش و تعداد صفات که در برمیگردند اولویت بندی میشوند.
در روش مبتنی بر کلاس، کلاسها بطور نزولی بر پایه اهمیت(تعداد تکرار) مرتب میشوند. بنابراین قانون با بیشترین تکرار همیشه در اول میآید و انتخاب میشود REF _Ref373604892 r h ‎[4].
الگوریتم های قانونمحور:
وش مستقیم: در این روش قانون IF-THEN بصورت مستقیم از دادهها بدون تولید درخت تصمیم با استفاده از الگوریتم توالی پوششبدست میآید. الگوریتم های مشهور مانندAQ،RIPPER و CN2 است. در شکل 2-5 شبه کد مربوط به الگوریتم توالی پوشش آمده است.
معیار توقف الگوریتم: برای توقف الگوریتم از معبارهای زیر استفاده میکنند در اینجا ابتدا به معرفی چند پارامتر میپردازیم:
اگر R بصورت
R: IF Condition then class=c
R´ بصورت زیر تعریف میشود
R: IFCondition´ then class=c
Pos: تعداد رکوردهایی که بطور صحیح توسط R پوشش داده شده است.
Neg: تعداد رکوردهایی که بطور غلط توسط R پوشش داده شده است.
pos´: تعداد رکوردهایی که بطور صحیح توسطR´ پوشش داده شده است.
neg´: تعداد رکوردهایی که بطور غلط توسطR´ پوشش داده شده است.
رابطه 2-9 FOILGAIN=pos´*log2pos´-neg´pos´-log2pos-negposو رابطه 2-10 Likehood_Ratio=2*i=1mlogfieifiاگر قانون بطور اتفاقی پیش بینی شود fi تعداد تکرار کلاس i میان رکوردهاست و ei مقدار مورد انتظار کلاس i است.
Cn2 از روشlikedhooh_ratio و RIPPER از FOIL برای خاتمه الگوریتم استفاده میکند[4].
روش غیر مستقیم: استخراج قوانین از روش های دسته بندی مانند درخت تصمیم
در مقایسه با درخت تصمیم بزرگ قوانین برای انسان راحتتر قابل فهم است برای ساختن قوانین از درخت تصمیم ما هر مسیر از ریشه تا برگ را پیمایش میکنیم. معیار جدا کننده نودها برای رسیدن تا برگ AND است و برگ نتیجه نگه میدارد که قبلش برگThen میآید. در اینجا شرط انحصار متقابل برقرار است و هیچ دو قانونی یک رکورد را ارضا نمیکند[4].

شکل 2-5: شبکه کد الگوریتم توالی پوشش [4]
2-2-5 مدل کاهلدر یک نگاه کلی میتوان دستهبندی را به دو گروه مشتاق و کاهل تقسیم کرد در نوع مشتاق، مدلی از دادهها در مرحله آموزش ساخته میشوند. درخت تصمیم نمونهای از این مدل است. در مدل کاهل نمونههای آموزشی دریافت و ذخیره شده و تنها هنگام دستهبندی از آن استفاده میشود. در واقع مدلی از دادهها ساخته نمیشود و یادگیری تا زمان دسته بندی به تعویق میافتد. به این نوع دسته بندی، یادگیری مبتنی بر نمونه میگوییم.
تفاوت بین این دو مدل در این است که نوع مشتاق زمان زیادی صرف ساخت مدل کرده و در زمان دسته بندی سریع عمل میکند و نوع کاهل زمان بیشتری صرف دسته بندی میکند[4].
در ادامه به بررسی الگوریتمهای مدل کاهل میپردازیم.
2-2-5-1 روش نزديکترين همسايگیاین الگوریتم از سه گام زیر تشکیل شده است:
محاسبه فاصله نمونه ورودی با تمام نمونههای آموزشی
مرتب کردن نمونههای آموزشی بر اساس فاصله و انتخاب k همسایه نزدیکتر
استفاده از دستهای که اکثریت را در همسایههای نزدیک، به عنوان تخمینی برای دسته نمونه ورودی دارد.
در گام اول روش نزدیکترین همسایگی، باید فاصله نمونه ورودی با تمام نمونه آموزشی محاسبه شود. برای انجام این کار باید فاصله بین دو نمونه تعریف شد که با فرض اینکه نمونه x دارایi ویژگی است بصورت زیر تعریف میشود.
رابطه2-11 distx1,x2=i=1nx2i-x2iK همسایه نزدیکتر انتخاب شده و دستهای که دارای اکثریت است داده جدید آموزشی به آن تعلق میگیرد.REF _Ref373604892 r h‎[4]
2-2-5-2 الگوريتمهايی برای اطمينان از عدم وجود داده مغشوشدر الگوریتم که قبلا گفتیم اگر مقدار k بسیار بزرگ باشد داده مغشوش تاثیر زیادی بر نتیجه ندارد. اما پیدا کردن k مناسب خود چالش بزرگی است در زیر به معرفی الگوریتمهایی میپردازیم که مبتنی بر این فرض هستند که نمونههایی را که کارایی خوبی برای دستهبندی دارند در مجموعه آموزشی نگه میدارند[4].
الگوریتم IB3 :
این الگوریتم در واقع یک پیش پردازش روی دادههای آموزشی است که در واقع اگر T مجموعه آموزشی باشد در واقع زیر مجموعه ای از آن s را نگه میداریم
در شکل 2- 6 شبکه کد الگوریتم IB3 آمده است.

شکل 2-6: شبکه کد الگوریتم [4] IB3
افزودن و حذف عناصر S با توجه به نرخ موفقیت نمونه و نرخ موفقیت پیش فرض آن صورت میگیرد.
نرخ موفقیت نمونه بصورت زیر تعریف میشود
رابطه 2-12 p=f+z22N+zfN-f2N-z24N21+z2Nدر این رابطه مقدار z از جدول مربوط به توزیع نرمال بدست میآید. متغیر f دقت دسته بندی در N بار امتحان استREF _Ref373604892 r h‎[4].
2-2-5-3 روش K-Dtreeمشکل الگوریتمهای بالا سرعت کم است که با تعداد نمونه آموزشی رابطه مستقیم دارد به عبارتیO(D) است اگر اندازه مجموعه آموزشیD باشد. برای جل این مشکل از روش K-Dtree استفاده میکنیم. این روش از روی نمونههای آموزشی درختی میسازد که گرههای آن نمونهها هستند.K ، تعداد ویژگیها است. در واقع نمونهها را به عنوان نقاطی در فضای k بعدی در نظر میگیرد. این درخت دودوی ی فضای ورودی را به بخشهای ی افراز میکند. روال کلی بدین صورت است که در هر مرحله یک ویژگی انتخاب شده و بر اساس آن تقسیم بندی مجدد انجام میشود. تمام تقسیمات موازی بوده و در نهایت هر ناحیه دارای حداکثر یک نقطه است[4].
شبه کد الگوریتم K-Dtreeدر شکل 2-7 آمده است. در این الگوریتم بازگشتی، در هر مرحله یک ویژگی به تناوب و با توجه به عمق انتخاب میشود. میانه حول آن محاسبه شده و نهایتا روال بصورت بازگشتی برای نقاط سمت چپ و راست میانه و با افزایش عمق فراخوانی میشود در واقع این روش یک روش شاخصگذاری برای جستجوی سریع است.REF _Ref373604892 r h‎[4]
6159522860000
شکل 2-7: شبکه کد مربوط به الگوریتم KDD [4]

2-2-6ماشين بردارپشتيبانماشین بردارپشتیبان در دسته بندی دادههای خطی و هم غیرخطی کاربرد دارد. در دستهبندی غیرخطی، این الگوریتم از یک نگاشت غیر خطی برای تبدیل دادههای اصلی به ابعاد بالاتر استفاده میکند. در بعد جدید از یک بهینه خطی برای جداسازی ابر صحفه استفاده میکند. دادهها از دو کلاس، همیشه توسط یک ابرصفحه جدا شده میشوند.ماشین بردار پشتیبان ابرصحفه را با استفاده از بردار پشتیبان(داده آموزشی) و حاشیه (توسط بردار پشتیان تعریف میشود) ایجاد میکند.REF _Ref373604892 r h * MERGEFORMAT ‎[4]
2-2-6-1 دادهها بطور خطی جدا پذير هستندمجموعه داده D بصورت x1,y1,x2,y2,..,xD,yDکه xi مجموعه داده آموزشی همراه با برچسب، و y یکی از دو مقدار +1 و -1 است. ما نیازبه خطی داریم که مقادیر y از هم جدا و بهترین باشد. چون داده خطی است میتوان گفت که کوتاهترین فاصله از ابرصفحه به یک طرف حاشیه آن برابر است با کوتاهترین فاصله از ابرصفحه به طرف دیگر از حاشیه آن، هدف پیدا کردن ابرصفحه جداکننده با بیشترین فاصله از نقاط حاشیهای است که نقاط با yi=1 را از نقاط باyi=-1 جدا کند. REF _Ref373604892 r h ‎[4]
هر ابر صحفه میتواند بصورت رابطه 2-13 تعریف شود
رابطه 2-13 W.x+b=0
که w بردار وزنها وn تعداد صفات و b یک عدد است اگرb به عنوان یک وزن اضافی در نظر بگیریم معادله بصورت رابطه 2-14 است.
رابطه 2-14 w0+w1x1+w2x2=0اگر این نقطه بالا جدا کننده ابر صحفه باشد معادله بصورت رابطه 2-15 است.
رابطه 2-15 w0+w1x1+w2x2>0اگر این نقطه پایین جدا کننده ابر صحفه باشد معادله بصورت رابطه 2-16 است
رابطه 2-16 w0+w1x1+w2x2<0وزن را می توان طوری تنظیم کرد به طوری که دارای مقدار حاشیه ماکزیمم شود رابطه 2-15 و 2-16 را میتوان بصورت رابطه 2-17 و 2-18 نِز نشان داد.
رابطه 2-17 H1:w0+w1x1+w2x2>1 for yi=+1رابطه 2-18 H2:w0+w1x1+w2x2>-1foryi=-1با ترکیب این دو رابطه 2-17 و 2-18 نامساوی 2-19 را داریم
رابطه 2-19 yiw0+w1x1+w2x2≥1 ∀iرکوردهای آموزشی که در ابرصفحه تعریف میشوند و در نامساوی بالا صدق میکنند بردار پشتیبانی نامیده می شود. اگر داده های آموزشی جدایی پذیر خطی باشند، ما می توانیم دو ابر

متن کامل در سایت homatez.com