دانلود رایگان ترجمه مقاله استخراج الگوی مشابه مکرر بسته (ساینس دایرکت – الزویر 2018)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

اولین الگوریتمی برای استخراج الگوهای مشابه مکرر بود که از تابع شباهت متفاوت با برابری استفاده می کرد و از الگوریتم Apriori الهام گرفته شده بود (Agrawal et al.، 1994). ObjectMiner با پیروی از یک استراتژی جستجوی اولیه در عرض چند ثانیه کار می کند. با توجه به مجموعه داده D، یک تابع شباهت و حداقل آستانه فرکانس، ObjectMiner الگوهای مشابهی را در D فقط با یک ویژگی پیدا می کند. فرکانس الگوها با اضافه کردن رخداد خود و رخداد الگوهای مشابه آن محاسبه می شود. هر الگوی با فرکانس بیشتر از حداقل آستانه فرکانس، الگوی مشابهی را در نظر می گیرد. در تکرار k (شروع با k = 2) ObjectMiner الگوهای مکرر مشابهی را در D با ویژگی k پیدا می کند. این کار با ادغام الگوهای مشابه مکرر با ویژگی های k-1 انجام می شود. این فرآیند پس از آنکه هیچ الگوهای مکرر دیگری پیدا نشد، پایان می یابد.
ضعف اصلی ObjectMiner، این است که شباهت بین یک الگوی و تکرار آن در هر تکرار الگوریتم محاسبه می شود، که باعث محاسبه اضافی و غیر ضروری می شود. ObjectMiner همچنین مجموعه ای از تمام زیر توصیف های مشابه (از جمله تکرار آن ها) را از هر یک از زیر فهرست های مکرر ذخیره می کند، که کارایی را کند می کند همانطور که در Rodríguez-González و همکاران نشان داده شده است. (2013).
StreeDC-Miner (Rodríguez-González ، 2013) یک الگوریتم دیگر برای استخراج نمونه های مکرر است. STreeDC-Miner با پیروی از یک استراتژی جستجوی اولیه عمق ، با استفاده از یک ترتیب کامل بر روی ویژگی که در D تنظیم شده است، کار می کند. STreeDC-Miner شروع به تجزیه و تحلیل هر مجموعه با تنها یک ویژگی A می کند و یک ویژگی جدید به این مجموعه اضافه می کند که بعد از آخرین ویژگی در مجموعه به ترتیب مشخص شده است. مورد پایه در بازگشت که الگوهای مشابه مکرر بیشتری برای مجموعه فعلی ویژگی های تحت تجزیه و تحلیل کشف نشده است کامل می شود. به منظور افزایش کارایی فرکانس الگوهای محاسبه، STreeDC-Miner از ساختار درختی به نام STree استفاده می کند. هر برگ در STree تکرار الگوی تحت این شاخه را ذخیره می کند و همچنین شباهت بین این الگو و الگوهای مشابه آن را ذخیره می کند. شباهت بین دو الگو در STree تنها اگر زیرالگوها در STree شبیه باشند و اگر یکی از آنها یک الگوی مشابه مکرر است، محاسبه می شود. به این ترتیب STreeDC-Miner تلاش محاسباتی را برای محاسبه فرکانس هر الگو با کاهش ترسیم تابع شباهت کاهش می دهد. با این حال، STreeDC-Miner مانند ObjectMiner همان نقص یافتن بسیاری از الگوهای مکرر مشابه را دارد.

2.2 استخراج آیتم های مکرر بسته
استخراج آیتم های مکرر بسته مکرر تنها یافتن آن مجموعه های مکرر است که در آن مجموعه های دیگری وجود دارد که حاوی آن با همان فرکانس باشد (Prabha et al.، 2013). مزیت محاسبه مجموعه های مکرر بسته این است که آنها تمام اطلاعات مورد نیاز برای به دست آوردن تمام الگوهای مکرر و فرکانس دقیق آنها بدون نیاز به مجموعه داده های اصلی را حفظ می کنند. دو الگوریتم استخراج مشتق شده مکرر اول و معروف ترین Closet و CHARM است.
Closet (پی و همکاران، 20 0 0) بر اساس: i) فشرده سازی الگوهای مکرر در ساختار درختی حاوی الگوهای مکرر برای مجموعه های استخراج بسته شده بدون تولید کاندید، II) فشرده سازی یک مسیر تک درخت برای انجام شناسایی سریع الگوهای مکرر بسته، iii) اجرای مکانیزم پیش بینی مبتنی بر پارتیشن برای کاوش مقیاس پذیر در پایگاه داده های بزرگ.
Closet با استفاده از روش تقسیم و فتح برای استخراج الگوهای مکرر بسته استفاده می کند. اولا موارد مکرر در فرکانس نزولی یافت می شوند و مرتب می شوند. سپس فضای جستجو به زیر مجموعه های غیر همپوشانی تقسیم می شود و هر زیر مجموعه ای از مجموعه های مکرر بسته به صورت مجزا با ساختن پایگاه های داده ی مشروط مرتبط استخراج می شود.
CHARM از سوی دیگر، (Zaki & Hsiao، 2002) از روش پایین به بالا برای استخراج مجموعه های مکرر بسته استفاده می کند. این روش فضاهای مجموعه نمونه ها و جابجایی ها را از طریق یک درخت جستجوی مجموعه نمونه – مجموعه زمان دوبعدی، با استفاده از یک جستجوی هیبریدی کارآمد که در طول جستجو در سطوح مختلف، از بین میرود، بررسی میکند. CHARM همچنین با استفاده از یک تکنیک به نام diffsets برای کاهش حافظه از محاسبات متوسط استفاده می کند. در نهایت، از یک رویکرد مبتنی بر هش استفاده می کند تا هر مجموعه غیر بسته که در طی جستجو پیدا می شود حذف شود.
LCM (Uno et al،) 2003 یکی دیگر از الگوریتم های استخراج معادلات مکرر بسته است. این تعریف یک رابطه پدر و کودک بین الگوهای بسته است. ثابت شد که هر رابطه والدین یک درخت را ایجاد می کند که از طریق آن می توان تمام الگوهای بسته را پیدا کرد. LCM همچنین یک روش کارآمد برای عبور از هر درخت در زمان چندجمله ای با توجه به مقدار مجموعه های مکرر بسته در مجموعه داده ها معرفی کرد.
از CHARM، Closet و LCM، دیگر الگوریتم ها نیز برای استخراج اقلام مکرر بسته شده از قبیل COBBLER (Pan، Tung، Cong، & Xu، 2004)، TD-Close (Han & Shao، 2006)، PGMiner (Moonesinghe، Fodeh ، TTD-Close (لیو و همکاران، 2009) CFIM-P (Nair)، TTD-Close (نجد و صدرالدینی، 2007)، ICMiner (لی، وانگ، ونگ، چن و وو، 2008) & Tripathy، 2011)، DBV-Miner (Vo، Hong، & Le، 2012)، NAFCP (Le & Vo، 2015) و اخیرا BVCL (هاشم، کریم، ساملی اله و احمد، 2017) پیشنهاد شده است.
بر خلاف همه این الگوریتم های قبلی، کار ما یک الگوریتم را برای استخراج الگوهای مکرر بسته در مجموعه داده ها ارائه می دهد که در آن اشیا با ویژگی های عددی و غیر عددی توصیف می شوند.

3. مفاهیم و عبارات پایه
در این بخش، برخی از مفاهیم مربوط به استخراج الگوی مشابه مکرر و یافتن الگوی مکرر بسته معرفی شده است. در ابتدا، مفاهیم رایج توصیف شده اند. سپس، مفاهیم یافتن الگوی مشابه مکرر ذکر شده است. سوم ، مفاهیم یافتن الگوی مکرر بسته نیز بیان شده اند.