چکیده
استخراج الگوهای مکرر یک کار، کلیدی برای کشف اطلاعات مفید است. با وجود کیفیت راه حل های داده شده توسط الگوریتم های یافتن الگوهای مکرر ، اکثر آنها با چالش چگونگی کاهش تعداد الگوهای مکرر بدون از دست رفتن اطلاعات مواجه می شوند. یافتن مجموعه های مکرر این مشکل را با کشف یک مجموعه کاهش یافته از مجموعه مکرر، به نام مجموعه های مکرر بسته، که از آن می توان تمام مجموعه الگوی مکرر را بازیابی کرد، حل می کند. با این حال، برای یافتن نمونه های مکرر مشابه، که در آن تعداد الگوها حتی از مجموعه یابی مکرر بزرگتر هستند، این مشکل هنوز حل نشده است. در این مقاله، ما مفهوم یافتن الگوی مشابه مکرر بسته را برای کشف تعدادی از الگوهای مکرر مشابه بدون از دست دادن اطلاعات معرفی می کنیم. علاوه بر این،یک الگوریتم جدید یافتن الگوی مشابه مکرر بسته با نام CFSP-Miner پیشنهاد شده است. الگوریتم، الگوهای مکرر را با عبور از یک درخت که شامل تمام الگوهای مشابه شبیه بسته است، می یابد. برای انجام این کار به صورت موثر، چندین لم برای پر کردن فضای جستجو معرفی و اثبات شده است. نتایج نشان می دهد که CFSP-Miner کارآمدتر از الگوریتم های مورد استفاده یافتن الگوی مشابه مکرر است، مگر اینکه در مواردی که تعدادی از الگوهای مشابه مکرر و الگوهای مشابه مکرر بسته تقریبا برابر باشند. با این حال، CFSP-Miner قادر به پیدا کردن الگوهای مشابه بسته، تولید اندازه کاهش یافته از الگوی مشابه مکرر کشف شده بدون از دست دادن اطلاعات است. همچنین، CFSP-Miner در حین عملکرد قابل قبول در حین اجرا، مقیاس پذیری خوبی را نشان می دهد.
1. مقدمه
یافتن الگوهای مکرر یک تکنیک است که شامل یافتن الگوهایی است (یعنی مجموعه های ویژگی با مقادیر مربوطه) که اغلب رخ می دهد (بیشتر یا برابر با حداقل آستانه تکرار) در یک مجموعه داده. این یک کار کلیدی در داده کاوی به دلیل استفاده از آن برای کشف اطلاعات مفید است مانند عوامل خطر (Li، Fu و Fahey، 2009؛ Li و همکاران، 2005؛ ناهار، امام، تلخه و چن، 2013) پروفایل های کاربر (Chiu، Yeh، & Lee، 2013)، رفتار انسان (Wen، Zhong، & Wang، 2015)، نرم افزارهای مخرب (Fan، Ye، & Chen، 2016) و غیره. علاوه بر این، یافتن الگوی مکرر را می توان به عنوان قدم قبلی یا داخلی برای سایر وظایف استخراج داده ها، مانند استخراج قواعد مرتبط (Alatas، Akin & Karci، 2008؛ Kalpana & Nadarajan، 2008؛ Lopez، Blanco، Garcia، Cano، & مارین، 2008)، طبقه بندی (هرناندز-لون، کاراسکو-اوچوا، مارتینز-ترینیداد و هرناندز-پالانکار، 2012؛ نگوین و نگوین، 2015) و خوشه بندی (Beil، Ester، Xu، 2002) استفاده کرد.
از سال 1990، اکثر الگوریتم های یافتن الگوی مکرر بر اساس تطابق دقیق ویژگی های بولین برای مقایسه و شمارش الگوها بود. این زیرمجموعه الگوریتم های یافتن الگوهای مکرر، یافتن اقلام مکرر نامیده می شود (به عنوان روش معمول برای یافتن الگوی مکرر). با این حال، اشیاء واقعی زندگی مانند اشیاء در جامعه شناسی (Ruiz-Shulcloper & Fuentes-Rodríguez، 1981)، زمین شناسی (گومز-هررا، رودریگز مورن، والاداراس آمرو و همکاران، 1994)، پزشکی (Ortiz-Posadas، Vega - Alvarado، & Toni، 2009) یا بازیابی اطلاعات (Baeza-Yates، Ribeiro-Neto و همکاران، 1999)) به ندرت مساوی هستند و یا با ویژگی های غیر بولین توصیف می شوند. به این ترتیب، توابع تشابه متفاوت از تطبیق دقیق برای مقایسه توصیف های شیء ارائه شده است که به ایجاد یک رویکرد جدید به نام یافتن الگوی مشابه مکرر می پردازد که می تواند مجموعه داده های حاوی ویژگی های غیر بولین را با استفاده از توابع شباهت کنترل کند(Danger، Ruiz-Shulcloper، & Llavori، 2004؛ رودریگز گونزالز، مارتینز-ترینیداد، کاراسکو-اوچوا و رویز شولکلپر، 2008؛ 2011؛ 2013). این روش الگوهایی را ایجاد می کند که نمی تواند توسط آن الگوریتم ها بر اساس تطابق دقیق پیدا شود. الگوهای مکرر که با استفاده از یک تابع شباهت به دست می آیند، نامهای مرسوم مشابهی دارند (Rodríguez-González، Martínez Trinidad، Carrasco-Ochoa، & Ruiz-Shulcloper، 2013).
این مقاله در نشریه الزویر منتشر شده و ترجمه آن با عنوان شناسایی الگوهای مشابه در سایت ای ترجمه به صورت رایگان قابل دانلود می باشد. جهت دانلود رایگان مقاله فارسی و انگلیسی روی عنوان فارسی (آبی رنگ) کلیک نمایید.
منبع:
