482

Improving Apriori based Association Rule MiningMethodsusing Hashing Techniques

كارشناسي ارشد

كامپيوتر- گرايش نرم‌افزار

تهران شمال

1395

95/6/3

18/5

103ص.

فراهي، احمد

89-91ص.

,Direct Hashing an​d Pruning , Separate Chaining , Linear Probing

استخراج قواعد انجمني، نوعي عمليات داده‌كاوي است كه به جستجو براي يافتن ارتباط بين ويژگي‌ها در مجموعه داده‌ها مي‌پردازد. هم‌اكنون حوزه‌هاي استفاده از داده‌كاوي، گستره‌ي عظيمي از اطلاعات در عمق اقيانوس‌ها تا كهكشان‌ها را شامل مي‌شود. اين روش به دنبال استخراج قواعد، به‌منظور كمي كردن ارتباط ميان دو يا چند خصوصيت است. يكي از روش‌هاي كاوشمجموعه اقلاممكرردريكپايگاهتراكنش،Aprioriاست كه به‌صورت مكرر، مجموعه اقلام تكراريرا در پايگاه داده‌ مشخص مي‌كند. از زمان ايجاد نخستين نسخه اين الگوريتم، روش‌هاي متعددي براي ارتقاي عملكرد آن ارائه‌شده است. الگوريتمDHPبهبودي بر الگوريتم Apriori است كه با استفاده از درهم‌سازي در توليد اقلام‌ مكرر، تراكنش‌هايي را كه هيچ قلم داده مكرري ندارند، از پايگاه داده هرس مي‌نمايد. از تابعدرهم‌سازي در توليد اقلام‌ مكرر درالگوريتمDHPو برايپردازش مجموعه اقلام كانديداي مرحله دوم استفادهمي‌شود.مطابق تحقيقات صورت گرفته، شبيه‌سازي‌هاي متعددي از عملكرد الگوريتمDHP انجام‌شده است كه به‌صراحت نشان مي‌دهد الگوريتمDHP نسبت به ساير روش‌ها و الگوريتم‌هاي ارائه‌شده، تعداد كانديداهاي 2 تايي مرحله دوم را به‌طور مؤثرتري كاهش داده است؛ بااين‌حال، به دليل وجود برخي ضعف‌هامانند مسئله تصادم در جدول درهم‌ساز، لزوم استفاده از توابع درهم‌ساز مناسب كه بتواند تصادم در اين الگوريتم را به حداقل مقدار ممكن برساند، بيش‌ازپيش موردتوجه بوده است. با توجه به اهميت وقوع تصادم در توليد مجموعه اقلام مكرر، ايده اصلي ما بهبود كارايي الگوريتم DHP در جهت رفع مسئله تصادم و كاهش زمان اجرا در توليد مجموعه اقلام مكرر است. براي اين منظور از سه راهبرد تحليل تصادم با عناوين زنجيرسازي جداگانه، كاوش خطي و درهم‌سازي مضاعف، براي حل تصادم در توليد كانديداي مرحله دوم الگوريتم DHP استفاده‌شده است. بدين‌صورت كه با زبان برنامه‌نويسي جاوا، عملكرد توابع حل تصادم را بر روي مجموعه داده‌هاي آزمايشيبررسي كرده و به اين نتيجه رسيديم كه استفاده از راهبرد‌هاي درهم‌سازي حل تصادم موجب حصول نتايج بهتري نسبت به استفاده از تابع درهم‌ساز فعلي الگوريتم DHP مي‌گردد. متعاقبا نشان داده شد كه انتخاب بهترين راهبرد درهم‌سازيبراي جايگزين نمودن با تابع درهم‌ساز فعلي الگوريتم DHP، وابسته به شرايط موردبحث در مسئله است.در تلاش¬هاي اخيركه جهت بهبود الگوريتم‌هاي Apriori و DHP با استفاده از درهم‌سازي صورت گرفته،عموماً از رويكردهايي كه به تغيير روش درهم‌سازي پيشين بدون توجه به نوع تابع درهم‌سازي مي‌پردازند،استفاده‌شده است. براين اساس،حل تصادم تابع درهم‌سازي در توليد مجموعه اقلام مكرر الگوريتم DHP، مبحثي است كه به آن پرداخته نشده‌است.

39680