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

چکیده

استخراج الگوهای مکرر یک کار، کلیدی برای کشف اطلاعات مفید است. با وجود کیفیت راه حل های داده شده توسط الگوریتم های یافتن الگوهای مکرر ، اکثر آنها با چالش چگونگی کاهش تعداد الگوهای مکرر بدون از دست رفتن اطلاعات مواجه می شوند. یافتن مجموعه های مکرر این مشکل را با کشف یک مجموعه کاهش یافته از مجموعه مکرر، به نام مجموعه های مکرر بسته، که از آن می توان تمام مجموعه الگوی مکرر را بازیابی کرد، حل می کند. با این حال، برای یافتن نمونه های مکرر مشابه، که در آن تعداد الگوها حتی از مجموعه یابی مکرر بزرگتر هستند، این مشکل هنوز حل نشده است. در این مقاله، ما مفهوم یافتن الگوی مشابه مکرر بسته را برای کشف تعدادی از الگوهای مکرر مشابه بدون از دست دادن اطلاعات معرفی می کنیم. علاوه بر این،یک الگوریتم جدید یافتن الگوی مشابه مکرر بسته با نام CFSP-Miner پیشنهاد شده است. الگوریتم، الگوهای مکرر را با عبور از یک درخت که شامل تمام الگوهای مشابه شبیه بسته است، می یابد. برای انجام این کار به صورت موثر، چندین لم برای پر کردن فضای جستجو معرفی و اثبات شده است. نتایج نشان می دهد که CFSP-Miner کارآمدتر از الگوریتم های مورد استفاده یافتن الگوی مشابه مکرر است، مگر اینکه در مواردی که تعدادی از الگوهای مشابه مکرر و الگوهای مشابه مکرر بسته تقریبا برابر باشند. با این حال، CFSP-Miner قادر به پیدا کردن الگوهای مشابه بسته،  تولید اندازه کاهش یافته از الگوی مشابه مکرر کشف شده بدون از دست دادن اطلاعات است. همچنین، CFSP-Miner در حین عملکرد قابل قبول در حین اجرا، مقیاس پذیری خوبی را نشان می دهد.

مقدمه

یافتن الگوهای مکرر یک تکنیک است که شامل یافتن الگوهایی است (یعنی مجموعه های ویژگی با مقادیر مربوطه) که اغلب رخ می دهد (بیشتر یا برابر با حداقل آستانه تکرار) در یک مجموعه داده. این یک کار کلیدی در داده کاوی به دلیل استفاده از آن برای کشف اطلاعات مفید است مانند عوامل خطر (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).

کارهای مرتبط

این مسئله استخراج الگوی مکرر موجب توجه جامعه پژوهشی داده کاوی به دلیل کاربرد بالقوه آن در بسیاری از حوزه های مختلف شده است. یک خط تحقیق بر کشف الگوهای مکرر در داده های مخلوط (مجموعه داده هایی که اشیاء آنها با ویژگی های عددی و غیر عددی توصیف می شوند) با استفاده از توابع شباهت برای مقایسه و شمارش اشیاء متمرکز است (الگوهای مکرر مشابه) (Danger et al.، 2004؛ Rodríguez González et al .، 2008؛ 2013). یک خط تحقیق دیگر متکی بر به دست آوردن یک مجموعه کاهش یافته از تمام الگوهای مکرر در مجموعه داده های بولی بدون از دست دادن اطلاعات است (مجموعه های مکرر بسته) (Prabha et al.، 2013؛ Uno et al.، 2003؛ Zaki & Hsiao، 2002).

نتایج این خطوط تحقیق مربوط به کار فعلی در زیر بخش های زیر ارائه شده است.

استخراج الگوی مشابه مکرر

در پیشینه دو الگوریتم برای استخراج ذکر شده وجود دارد: ObjectMiner (Danger et al.، 2004) و STreeDCMiner (Rodríguez-González et al.، 2013). هر دو الگوریتم کل مجموعه ای از الگوهای مشابه مکرر را با استفاده از توابع شباهت بولین پیدا می کنند. مجموعه ای از الگوهای ردیابی معمولا شامل الگوهای پنهان به رویکرد سنتی است.

مفاهیم و عبارات پایه

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

ترکیب مفهوم الگوی مشابه مکرر و الگوی مشابه مکرر بسته

در این بخش، مفاهیم الگوی بسته برای یافتن مجموعه نمونه مکرر، برای یافتن الگوی مشابه مکرر گسترش می یابد.

تعریف 15 (الگوی مشابه بسته شده). با توجه به یک مجموعه داده D = (O, A , V, P) و F ∈ N، یک الگوی مشابه بسته در D یک الگوی T e ∈ T | ∀ T eSup ∈ SupPatterns (T e ) Frequency F ( T eSup ) < Frequency F ( T e ) است، جایی که Eنشان دهنده مجموعه ای از تمام الگوی مشابه بسته در D با استفاده از Fاست.

الگوریتم مشابه الگوریتم مشابه (CFSP-Miner)

در این بخش، الگوریتم CFSP-Minerبرای استخراج الگوهای مشابه مکرر را به وجود می آوریم که در آن تابع شباهت ویژگی بسته شدن از پایین را از لم 2 نگه میدارد. الگوریتم با عبور از یک درخت عمل می کند، که توسط یک رابطه پدر و کودک تعریف شده است که شامل تمام الگوهای مشابه بسته است. قبل از اینکه تعریف رابطه پدر و فرزند را معرفی کنیم، باید تعریف جدیدی را ارائه دهیم:

تعریف 22 (پیشوند کوچک با FCLبرابر). پیشوند جزئی با FCL برابر یک الگوی مشابه بسته، کاربرد PRFCL: E → A است.

تجزیه و تحلیل پیچیدگی

برای تحلیل پیچیدگی محاسباتی CFSP-Miner، بدترین حالت را مورد بررسی قرار می دهیم. ورودی CFSP-Miner شامل یک مجموعه داده از mاشیاء Oاست که هر کدام با مجموعه ای از ویژگی های A شرح داده شده است. بنابراین اندازه ورودی MN است. از سوی دیگر، اندازه خروجی، تعداد c از الگوهای مکرر مشابه بسته است. فرض می کنیم که هزینه محاسبه شباهت بین یک الگو و یک شیء، O (n) است، زیرا صفات nباید مقایسه شوند.

نتایج تجربی

در این بخش عملکرد الگوریتم پیشنهادی CFSP-Miner ارزیابی می شود. ما نتایج تجربی را به دو بخش تقسیم می کنیم. در بخش اول (بخش 6.1) مقایسه ای از لحاظ زمان مورد نیاز برای استخراج الگوهای مشابه مکرر توسط هر الگوریتم (CFSP-Miner، ObjectMiner و STreeDC-Miner) ارائه شده است. مهم است که مشخص شود هر الگوریتم ObjectMiner و STreeDC-Miner مجموعه ای از همه الگوهای مشابه مرسوم S را بدست آورده است، در حالی که الگوریتم پیشنهادی، CFSP-Miner، تنها مجموعه ای از تمام الگوهای مشابه بسته S ∩ E را به دست می آورد. در بخش دوم (بخش 6.2) مقیاس پذیری الگوریتم CFSP-Miner نشان داده شده است.

کارایی الگوریتم CFSP-Miner

جدول 1 شرح مجموعه داده ها 1 مورد استفاده را نشان می دهد. یک تابع تشابه متفاوت می تواند برای هر یک از مشکلات خاص تعریف شود. با این حال، هدف از این آزمایش ها حل کردن یک مشکل خاص نیست، بلکه صرفا به منظور ارزیابی کارایی الگوریتم پیشنهاد شده است. به همین دلیل توابع شباهت به هیچ مشکلی خاص در این کار وابسته نیستند.

نتیجه گیری

در این مقاله ما مفهوم یافتن الگوی مشابه مکرر بسته را برای کشف یک مجموعه کاهش یافته از الگوهای مشابه مکرر بدون از دست دادن اطلاعات ارائه دادیم. ما همچنین یک الگوریتم استخراج الگوی مشابه مکرر را ، به نام CFSP-Miner پیشنهاد کردیم ، که با استفاده از توابع مشابه شباهت های ریاضی برای پیدا کردن همه الگوهای مشابه بسته به کار می رود.

نتایج نشان می دهد که الگوریتم پیشنهادی CFSP-Miner کارآمدتر از سایر الگوریتم های یافتن الگوهای مشابه مکرر موجود در پیشینه است، مگر اینکه در مواردی که تعداد الگوهای مشابه مکرر و تعدادی از الگوهای مشابه بسته مکرر تقریبا برابر باشند. یکی دیگر از قدرت های CFSP-Minerتوانایی آن در پیدا کردن الگوهای مشابه "بسته" بدون از دست دادن اطلاعات است. در بسیاری از مجموعه داده های تجزیه و تحلیل شده، CFSP-Miner مقدار تقریبی نمونه های مکرر کشف شده را تقریبا 50٪ کاهش داد. CFSP-Minerهمچنین می تواند برای استفاده در مجموعه داده های با ابعاد بزرگ مورد استفاده قرار گیرد زیرا نتایج تجربی نشان می دهد که افزایش تعداد اشیاء، تعداد ویژگی ها یا اندازه هر دامنه ویژگی، زمان اجرا را در محدوده قابل قبول حفظ می کند.

برای کار آتی، ما بهبود بهره وری CFSPMiner، کاوش در ایده های ارائه شده در کارهای اخیر برای بهبود بهره وری از الگوریتم های یافتن الگوهای مکرر بسته سنتی و مطالعه امکان سنجی گسترش این نتایج به یافتن الگو مکرر مشابه بسته را تجسم. می کنیم. گسترش روش های یافتن الگوهای مشابه مکرر بسته، یافتن قوانین ارتباطات برای توابع شباهت غیر بولین و توابع شباهت غیر مونوتونی یکی دیگر از کارهای جالب آینده است.

این مقاله ISI در سال 2018 در نشریه الزویر و در مجله سیستم های خبره با برنامه های کاربردی، توسط گروه علوم کامپیوتر منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله شناسایی الگوهای مشابه مکرر بسته شده در سایت ای ترجمه مراجعه نمایید.