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

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