منبع پایان نامه ارشد با موضوع الگوريتم، تقسيم، زير

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

ي قواعد
الگوريتم هاي مختلفي براي تعيين وابستگي قواعد وجود دارد که برخي از مهم ترين آن ها در زير آورده شده است:
الگوريتم Naïve
اين الگوريتم پردازه اي براي کشف تمام قواعد وابستگي با حداقل Support=p% و Confidence=q% مي باشد. در اين الگوريتم ليستي از تمامي ترکيب هاي ممکن تهيه شده و سپس تعداد تکرار آن ها در مجموعه تراکنش هاي محاسبه مي شود سپس با توجه به مقدار Support داده شده ليست ترکيب هايي که تعداد تکرار آن ها برابر يا بيشتر از تعداد مورد نظر است جدا شده و براي تمامي ترکيب هاي آن ميزان Confidence محاسبه و با مقدار داده شده مقايسه مي شود. سپس ليست قواعد با Confidence مورد نظر استخراج مي گردد.(Gupta 2006)
در نسخه بهبود يافته اين الگوريتم به جاي شمارش تمامي ترکيب ها، تراکنش ها يموجود شمارش شده و ترکيب هاي با تعداد تکرار صفر منظور نمي شوند.
الگوريتم Apriori
الگوريتم Apriori را مي توان يکي از مهم ترين يافته ها در تاريخ استخراج وابستگي قواعد دانست که توسط چيونگ در سال 1996 ابداع گرديد. يکي از کاربردي ترين مسائل مربوط به اين تکنيک، تجزيه و تحليل سبد بازار است. خرده فروشان با تجزيه و تحليل سبد بازار مي توانند رفتار خريد مشتريان را پيش بيني کنند. اينکار به آن ها کمک مي کند تا بتوانند کالاهاي خود را بهتر ساماندهي کرده و چيدمان بهتري از محصولات خود داشته باشند و از اين طريق سودآوري خود را افزايش دهند.
در حالت معمولي براي يافتن مجموعه هاي پرتکرار بايد تمام مجموعه هاي تک عضوي پر تکرار را پيدا کرد، سپس بر اساس آن مجموعه هاي دو عضوي پر تکرار را پيدا کرد و …
بنابراين در هر مرحله بايد کل فضا جستجو شود. اما اين الگوريتم از يک خصوصيت به نام خصوصيت Apriori استفاده مي کند. به اين صورت که اگر يک مجموعه از عناصر پرتکرار باشد، تمام زير مجموعه هاي غير تهي آن نيز پر تکرار خواهند بود. مثلا اگر مجموعه A به صورت A={C,D,E} پر تکرار باشد، آن گاه تمام مجموعه هاي زير نيز پرتکرار هستند:
{C, D}, {C, E}, {D, E}, {C}, {D}, {E}
اين خصوصيت را به اين صورت نيز مي توان توصيف کرد که اگر مجموعه I به يک تعداد مرتبه تکرار شده باشد، اگر A را نيز به آن اضافه کنيم تعداد تکرار مجموعه ي جديد از تعداد تکرار مجموعه قبلي بيشتر نخواهد بود. پس اگر اولي پرتکرار نباشد دومي هم پرتکرار نخواهد بود. اي الگوريتم نيز اي اين خصوصيت استفاده مي کند. الين الگوريتم در يافتن مجموعه هاي پرتکرار به اين صورت عمل مي کند:
فرض مي کنيم Ck و Fk به ترتيب برابر با مجموعه اقلام کانديد و مجموعه اقلام پرتکرار با اندازه K باشند.
در ابتدا K=1 قرار مي دهد.
در ابتدا تمامي اقلام پرتکرار تک عضوي با عنوان F1 را پيدا مي کند.
مراحل زير را زماني که هيچ مجموعه پرتکرار جديدي يافت نشود تکرار مي کند.
3-1 مجموعه اقلام کانديد (K+1) عضوي که همان Ck+1 است را از مجموعه اقلام پرتکرار K عضوي (Fk) مي يابد.
3-2 مجموعه اقلام پرتکرار FK+1 را با در نظر گرفتن شرط حداقل پشتيبان و حذف اقلام غير پرتکرار، پيدا مي کند.
لازم به ذکر است که گام (3-1) در دو مرحله صورت مي گيرد. يکي توليد اقلام کانديد41 و يکي هرس کردن42 اقلامي که پرتکرار نيستند. از مرحله اول تحت عنوان مرحله پيوست43 نيز ياد مي شود(آخوندزاده نوقاني،1388).
مرحله توليد اقلام کانديد و يا پيوست
در اين مرحله به دليل جلوگيري از مجموعه هاي تکراري از قانون لگزيکوگرافي استفاده مي شود و عناصر براساس قاعده الفبايي با يکديگر ترکيب مي شوند. بنابراین در ابتدا بايد عناصر بر مبناي ترتيب حروف الفبا مرتب شده باشند. در ضمن دو مجموعه در صورتي با يکديگر قابل پيوست هستند که عناصر آن ها غير از عنصر آخر با يکديگر برابر باشند(آخوندزاده نوقاني،1388).
مرحله هرس
نکته اي که در مورد مجموعه به دست آمده از مرحله قبل وجود دارد اين است که ممکن است برخي از عناصر آن پرتکرار نباشند، البته تمام عناصر پرتکرار در آن قرار دارند. بنابراين لازم است تا مرحله هرس کردن انجام شود.
به اين منظور بايد تمامي اعضاي اين مجموعه بررسي شوند تا مشخص شود که آيا پرتکرار هستند يا خير؟ اما چون ممکن است تعداد آن ها زياد باشد لذا براي کاهش حجم محاسبات از اصل APriori استفاده مي شود. به اين صورت که اگر يکي از زير مجموعه ها پرتکرار نباشد، آن مجموعه نيز پرتکرار نخواهد بود. بنابراين براي پيدا کردن مجموعه هاي پرتکرار کافي است مجموعه هاي غير پرتکرار را از آن ها جدا کرد. به عنوان نمونه مجموعه F3 که مجموعه اقلام پرتکرار 3 عضوي است را در نظر بگيريد.
F3 = {{A, B, C}, {A, B, D}, {A,B, E}, {A,C,E}, {A,D,E}, {B,D,E}}
با ترکيب اقلام پرتکرار فوق 3 مجموعه جديد به دست مي آيد که عبارتند از:
C4 = {{A, B, C, D}, {A, B, C, E}, {A, B, E, D}}
تنها عضوي از مجموعه فوق که به عنوان اقلام کانديد 4 تايي پيشنهاد مي شود، {A, B, D, E} است. به علت اين که ساير موارد غير پرتکرار هستند. به عنوان نمونه {A, B, C, D} در مرحله هرس حذف مي شود. زيرا برخي از زير مجموعه هاي آن عبارتند از {A, C, D} و {B, C, D} متعلق به F3 نيستند.
پس از آن که مجموعه هاي پرتکرار استخراج شدند، نوبت به استخراج قوانين قوي با اطمينان بالا مي رسد. در اين مرحله تمام زير مجموعه هاي غير تهي يک مجموعه پرتکرار نوشته شده و تمامي قواعد ممکن بر اساس آن استخراج مي شود. سپس اطمينان را براي هر يک از قوانين محاسبه نموده و اگر بيشتر از حد قابل قبول بود به عنوان يک قانون پذيرفته مي شود(آخوندزاده نوقاني،1388).
الگوريتم هاي طبقه بندي
الگوريتم ها و روش هاي مختلفي تا کنون براي طبقه بندي پيشنهاد شده اند که براي مثال مي توان از روش هاي طبقه بندي با استفاده از درخت تصميم C4.5، درخت طبقه بندي و رگرسيونCART، شبکه هاي بيزين، SVM، طبقه بندي مبتني بر قواعد، طبقه بندي با استفاده از شبکه هاي عصبي و …. نام برد که در زير برخي از آن ها تشريح شده اند:
الگوريتم درخت طبقه بندي و رگرسيون (CART)
روش درخت طبقه بندي و رگرسيون (CART) توسط Breiman و همکارانش در سال 1984 پيشنهاد شد(Larsed 2003).
درخت هاي تصميم توليد شده توسط CART دودويي بوده و دقيقا دو شاخه براي هر گره تصميم دارد. CART به صورت بازگشتي داده هاي آموزشي را بر اساس مقادير مشابه مشخصه هدف به زير مجموعه هايي تقسيم مي کند. الگوريتم CART با انجام يک جستجوي گسترده در همه متغيرهاي موجود و تمامي تقسيم هاي ممکن، نقطه تقسيم بهينه را برمبناي معيار زير انتخاب نموده درخت تصميم را توسعه مي دهد.
فرض کنيم Ф(s|t) يک مقياس براي تعيين ميزان مناسب بودن يک کانديد تقسيم S در گره t باشد:

# classes
Ф(s|t) = 2PL PR Σ|P ( j |tL ) – P ( j |tR)
j=1
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(Pi )
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 به عنوان ريشه به کاربرده شود برابر است با:
EntropyA (D)=∑|Dj|/|D|* Entropy(Dj )
اطلاعات حاصل از انشعاب بر حسب صفت A را به صورت زير تعريف مي کنيم:
[Gain(A) = Entropy(D)-EntropyA(D))]
هرچه مقدار بهره صفت A يعني (GainA) بيشتر باشد يا به عبارت ديگر هرچه (Entropy D) کمتر باشد، صفتA گزينه مناسب تري براي انتخاب به عنوان صفت تقسيم مي شود.
الگوريتم هاي شبکه هاي بيزين
در برخي از الگوريتم هاي طبقه بندي تعدادي شي موجود است که همگي داراي يک بردار از خصيصه ها مي باشند. مدل شبکه بيزين يک مدل بر مبناي احتمال است که رويدادهاي مشاهده شده و ذخيره شده را بررسي کرده و مشابهت رويدادها را با استفاده از خصيصه هاي به ظاهر نامشابه تعيين مي کند. شبکه بيزين يک مدل گرافيکي است که متغيرها در يک مجموعه داده44 را به صورت گره45 نشان داده و احتمال يا شرط

پایان نامه
Previous Entries منبع پایان نامه ارشد با موضوع سلسله مراتب Next Entries منبع پایان نامه ارشد با موضوع مشارکت مردم