استفاده از مجموعه اقلام پرتکرار در بهبود الگوریتم SPAM

کشف توالی های پرتکرار یکی از وظایف مهم داده کاوی است که دارای کاربردهای فراوانی است.الگوریتم های ارائه شده برای این مسئله بهسه دسته تقسیم می شوند. رویکرد مبتنی بر Apriori ، رویکرد عمودی و رویکرد مبتنی بر توسعه الگو. از بین این روشها، روشهایعمودی در مجموعه داده هایی با توالی های طولانی و با چگالی بالاتر کاراتر می باشند. در الگوریتمهای عمودی، از روش تولید توالی هایکاندید و چک کردن تعداد تکرارشان استفاده می شود که برای مجموعه داده های بزرگ زمانبر است.دراین مقاله روشی پیشنهاد شده است که هدفش هرس نمودن الگوهای کاندید، قبل از محاسبه تعداد تکرارشان است. مطابق خاصیتApriori تمام مجموعه آیتم های موجود در یک توالی پرتکرار، خود پرتکرار هستند؛ بنابراین در روش پیشنهادی، از مجموعه آیتم هایپرتکرار برای هرس کردن توالی های کاندید استفاده شده است. به عبار دیگر، اگر یک توالی کاندید، دارای مجموعه آیتمی باشد که عضومجموعه آیتم های پرتکرار نباشد آنگاه به طور حتم پرتکرار نیست و نیاز به اشتراک گیری و محاسبه تعداد تکرارش نخواهد بود. بنابراینابتدا به کمک روش FP-growth تمامی مجموعه اقلام پرتکرار ساخته می شود؛ سپس از این مجموعه ها، در مرحله هرس کردن استفادهمی شود. آزمایش های انجام شده بر روی مجموعه داده های مصنوعی نشان داد الگوریتم پیشنهادی توانسته است تا حد زیادی الگوهای کاندیدرا هرس نماید.

کلیدواژه ها:

داده کاوی ، الگوهای پرتکرار ، توالی های پرتکرار ، خاصیت apriori