رفتار خرید مشتریان و خرده فروشان

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

الگوریتم های مختلفی برای تعیین وابستگی قواعد وجود دارد که برخی از مهم ترین آن ها در زیر آورده شده است:
الگوریتم 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) در دو مرحله صورت می گیرد. یکی تولید اقلام کاندید و یکی هرس کردن اقلامی که پرتکرار نیستند. از مرحله اول تحت عنوان مرحله پیوست نیز یاد می شود(آخوندزاده نوقانی،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 نیستند.