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

این الگوریتم پردازه ای برای کشف تمام قواعد وابستگی با حداقل Support=p% و Confidence=q% می باشد. در این الگوریتم لیستی از تمامی ترکیب های ممکن تهیه شده و سپس تعداد تکرار آن ها در مجموعه تراکنش های محاسبه می شود سپس با توجه به مقدار Support داده شده لیست ترکیب هایی که تعداد تکرار آن ها برابر یا بیشتر از تعداد مورد نظر است جدا شده و برای تمامی ترکیب های آن میزان Confidence محاسبه و با مقدار داده شده مقایسه می شود. سپس لیست قواعد با Confidence مورد نظر استخراج می گردد.(Gupta 2006)
در نسخه بهبود یافته این الگوریتم به جای شمارش تمامی ترکیب ها، تراکنش ها یموجود شمارش شده و ترکیب های با تعداد تکرار صفر منظور نمی شوند.
الگوریتم APRIORI
الگوریتم Apriori را می توان یکی از مهم ترین یافته ها در تاریخ استخراج وابستگی قواعد دانست که توسط چیونگ در سال ۱۹۹۶ ابداع گردید. یکی از کاربردی ترین مسائل مربوط به این تکنیک، تجزیه و تحلیل سبد بازار است. خرده فروشان با تجزیه و تحلیل سبد بازار می توانند رفتار خرید مشتریان را پیش بینی کنند. اینکار به آن ها کمک می کند تا بتوانند کالاهای خود را بهتر ساماندهی کرده و چیدمان بهتری از محصولات خود داشته باشند و از این طریق سودآوری خود را افزایش دهند.
در حالت معمولی برای یافتن مجموعه های پرتکرار باید تمام مجموعه های تک عضوی پر تکرار را پیدا کرد، سپس بر اساس آن مجموعه های دو عضوی پر تکرار را پیدا کرد و …
بنابراین در هر مرحله باید کل فضا جستجو شود. اما این الگوریتم از یک خصوصیت به نام خصوصیت Apriori استفاده می کند. به این صورت که اگر یک مجموعه از عناصر پرتکرار باشد، تمام زیر مجموعه های غیر تهی آن نیز پر تکرار خواهند بود. مثلا اگر مجموعه A به صورت A={C,D,E} پر تکرار باشد، آن گاه تمام مجموعه های زیر نیز پرتکرار هستند:
{C, D}, {C, E}, {D, E}, {C}, {D}, {E}
این خصوصیت را به این صورت نیز می توان توصیف کرد که اگر مجموعه I به یک تعداد مرتبه تکرار شده باشد، اگر A را نیز به آن اضافه کنیم تعداد تکرار مجموعه ی جدید از تعداد تکرار مجموعه قبلی بیشتر نخواهد بود. پس اگر اولی پرتکرار نباشد دومی هم پرتکرار نخواهد بود. ای الگوریتم نیز ای این خصوصیت استفاده می کند. الین الگوریتم در یافتن مجموعه های پرتکرار به این صورت عمل می کند:
فرض می کنیم Ck و Fk به ترتیب برابر با مجموعه اقلام کاندید و مجموعه اقلام پرتکرار با اندازه K باشند.

برای دانلود متن کامل پایان نامه به سایت  jemo.ir  مراجعه نمایید.

  1. در ابتدا K=1 قرار می دهد.
  2. در ابتدا تمامی اقلام پرتکرار تک عضوی با عنوان Fرا پیدا می کند.
  3. مراحل زیر را زمانی که هیچ مجموعه پرتکرار جدیدی یافت نشود تکرار می کند.

۳-۱ مجموعه اقلام کاندید (K+1) عضوی که همان Ck+1 است را از مجموعه اقلام پرتکرار K عضوی (Fk) می یابد.
۳-۲ مجموعه اقلام پرتکرار FK+1 را با در نظر گرفتن شرط حداقل پشتیبان و حذف اقلام غیر پرتکرار، پیدا می کند.
لازم به ذکر است که گام (۳-۱) در دو مرحله صورت می گیرد. یکی تولید اقلام کاندید[۴۱] و یکی هرس کردن[۴۲] اقلامی که پرتکرار نیستند. از مرحله اول تحت عنوان مرحله پیوست[۴۳] نیز یاد می شود(آخوندزاده نوقانی،۱۳۸۸).

  • مرحله تولید اقلام کاندید و یا پیوست

در این مرحله به دلیل جلوگیری از مجموعه های تکراری از قانون لگزیکوگرافی استفاده می شود و عناصر براساس قاعده الفبایی با یکدیگر ترکیب می شوند. بنابراین در ابتدا باید عناصر بر مبنای ترتیب حروف الفبا مرتب شده باشند. در ضمن دو مجموعه در صورتی با یکدیگر قابل پیوست هستند که عناصر آن ها غیر از عنصر آخر با یکدیگر برابر باشند(آخوندزاده نوقانی،۱۳۸۸).

  • مرحله هرس

نکته ای که در مورد مجموعه به دست آمده از مرحله قبل وجود دارد این است که ممکن است برخی از عناصر آن پرتکرار نباشند، البته تمام عناصر پرتکرار در آن قرار دارند. بنابراین لازم است تا مرحله هرس کردن انجام شود.
به این منظور باید تمامی اعضای این مجموعه بررسی شوند تا مشخص شود که آیا پرتکرار هستند یا خیر؟ اما چون ممکن است تعداد آن ها زیاد باشد لذا برای کاهش حجم محاسبات از اصل APriori استفاده می شود. به این صورت که اگر یکی از زیر مجموعه ها پرتکرار نباشد، آن مجموعه نیز پرتکرار نخواهد بود. بنابراین برای پیدا کردن مجموعه های پرتکرار کافی است مجموعه های غیر پرتکرار را از آن ها جدا کرد. به عنوان نمونه مجموعه F3 که مجموعه اقلام پرتکرار ۳ عضوی است را در نظر بگیرید.
F3 = {{A, B, C}, {A, B, D}, {A,B, E}, {A,C,E}, {A,D,E}, {B,D,E}}
با ترکیب اقلام پرتکرار فوق ۳ مجموعه جدید به دست می آید که عبارتند از:
C4 = {{A, B, C, D}, {A, B, C, E}, {A, B, E, D}}
تنها عضوی از مجموعه فوق که به عنوان اقلام کاندید ۴ تایی پیشنهاد می شود، {A, B, D, E} است. به علت این که سایر موارد غیر پرتکرار هستند. به عنوان نمونه {A, B, C, D} در مرحله هرس حذف می شود. زیرا برخی از زیر مجموعه های آن عبارتند از {A, C, D} و {B, C, D} متعلق به F3 نیستند.
پس از آن که مجموعه های پرتکرار استخراج شدند، نوبت به استخراج قوانین قوی با اطمینان بالا می رسد. در این مرحله تمام زیر مجموعه های غیر تهی یک مجموعه پرتکرار نوشته شده و تمامی قواعد ممکن بر اساس آن استخراج می شود. سپس اطمینان را برای هر یک از قوانین محاسبه نموده و اگر بیشتر از حد قابل قبول بود به عنوان یک قانون پذیرفته می شود(آخوندزاده نوقانی،۱۳۸۸).
الگوریتم های طبقه بندی
الگوریتم ها و روش های مختلفی تا کنون برای طبقه بندی پیشنهاد شده اند که برای مثال می توان از روش های طبقه بندی با استفاده از درخت تصمیم C4.5، درخت طبقه بندی و رگرسیونCART، شبکه های بیزین، SVM، طبقه بندی مبتنی بر قواعد، طبقه بندی با استفاده از شبکه های عصبی و …. نام برد که در زیر برخی از آن ها تشریح شده اند:
الگوریتم درخت طبقه بندی و رگرسیون (CART)
روش درخت طبقه بندی و رگرسیون (CART) توسط Breiman و همکارانش در سال ۱۹۸۴ پیشنهاد شد(Larsed 2003).
درخت های تصمیم تولید شده توسط CART دودویی بوده و دقیقا دو شاخه برای هر گره تصمیم دارد. CART به صورت بازگشتی داده های آموزشی را بر اساس مقادیر مشابه مشخصه هدف به زیر مجموعه هایی تقسیم می کند. الگوریتم CART با انجام یک جستجوی گسترده در همه متغیرهای موجود و تمامی تقسیم های ممکن، نقطه تقسیم بهینه را برمبنای معیار زیر انتخاب نموده درخت تصمیم را توسعه می دهد.
فرض کنیم Ф(s|t) یک مقیاس برای تعیین میزان مناسب بودن یک کاندید تقسیم S در گره t باشد:
# classes
Ф(s|t) = 2PL PR Σ|P ( j |tL ) – P ( j |tR)
j=1