یک روش سریع برای استخراج الگوهای پرتکرار K- درجه بالا از داده های غیر قطعی

امروزه استخراج الگوهای پرتکرار از داده های غیر قطعی به یکی از زمینه های تحقیقاتی بسیار مهم در داده کاوی تبدیل شده است. روش های پیشنهادی با رویکردهای سنتی اغلب با مشکل کشف بیش از حد الگوهای پرتکرار غیرقطعی روبرو می شوند، بنابراین زمان و منابع زیادی را صرف رتبه بندی و یافتن امیدوار کننده ترین الگوها می کنند. اخیرا روشی برای استخراج الگوهای پرتکرار k-درجه بالا ارائه شده است که بدون نیاز به استخراج تمامی الگوها، تنها k الگوی با بیشترین پشتیبانی مورد انتظار را استخراج می کند؛ اما این الگوریتم به دلیل استفاده از ساختار مبتنی بر لیست و تکنیک جستجوی اول عمق در فرآیند استخراج الگوها، الگوهای کاندید بسیار زیادی تولید می کند که به زمان زیادی برای استخراج الگوها نیاز دارد. حال آن که در ساختار لیستی الگوریتم TUFP اکثر الگوها با بالاترین پشتیبانی مورد انتظار در سطح های اولیه لیست ها تولید می شوند و جستجوی عمقی تنها باعث افزایش تعداد الگوهای کاندید و صرف زمان بالا برای استخراج الگوها می شود. بر همین اساس برای اولین بار در این تحقیق الگوریتم پیشنهادی الگوها را با استفاده از روش جستجوی اول سطح از ساختار مبتنی بر لیست استخراج می نماید که باعث می شود الگوهای کاندید غیر پرتکرار بیشتری شناسایی و زیرشاخه های مربوطه به آن هرس شوند. بنابراین، الگوریتم پیشنهادی نسبت به الگوریتم TUFP تعداد کاندید کمتری تولید می نماید و هرچه K افزایش می یابد این تفاوت بیشتر می شود. به عنوان مثال الگوریتم پیشنهادی نسبت به الگوریتم TUFP، 79 درصد زمان اجرا را برای استخراج الگوها از پایگاه داده T25I10D10K در K=1900 بهبود و تا 45 درصد تولید الگوهای کاندید را نسبت به الگوریتم TUFP برای پایگاه داده Chess در K=18 کاهش دهد.

کلیدواژه ها:

داده کاوی ، استخراج الگوهای پرتکرار ، الگوهای پرتکرار k-درجه بالا ، داده های غیرقطعی