کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6862336 676866 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Pattern discovery via constraint programming
ترجمه فارسی عنوان
کشف الگو از طریق برنامه ریزی محدودیت
کلمات کلیدی
ترجمه چکیده
کشف الگو یکی از اساسی ترین مشکلات در داده کاوی است. الگوهای مختلف با الگوریتم های کشف آنها در برنامه ها و حوزه های مختلف ارائه شده است. تقاضای زیادی برای تعیین الگوهای جدید معنی دار با الزامات جدید وجود دارد، زیرا هر برنامه دارای مشخصات منحصر به فرد آن است. مطالعات موجود، پیشنهاد می کند که زبان های پرس و جو جدید برای توصیف این الگوهای زمانبندی استفاده شوند. با این حال، اکثر آنها بر روی تغییرات کوچکی از مجموعه موارد مکرر و قوانین انجمنی تمرکز می کنند. بسیاری از الگوهای معنی دار در حوزه های دیگر، مانند الگوهای زمانی و فضایی، پوشش داده نمی شوند. این مقاله یک دیدگاه مبتنی بر محدودیت برای کشف الگو را بدون معرفی زبان های جدید ارائه می دهد که در آن الگوهای با مجموعه ای از محدودیت های داده شده در زمان اجرا توصیف می شوند. در این دیدگاه، یک مشکل کشف الگو به عنوان یک مسئله رضایت از محدودیت دیده می شود. این دیدگاه یک چارچوب کلی برای کشف الگوی جهانی فراهم می کند. بسیاری از الگوهایی که قبلا شناخته شده بودند می توانند به عنوان تغییرات متفاوت از این چارچوب کلی با محدودیت های مختلف در نظر گرفته شوند. برای حل مسئله رضایت از محدودیت، دو الگوریتم عمومی ارائه شده است. ارزیابی تجربی بر روی دو مدل به خوبی مطالعه شده نشان می دهد که (1) هزینه زمان یک الگوریتم ژنریک نزدیک به آن الگوریتم های معدن تخصصی است و (2) هزینه فضایی الگوریتم ژنتیک به صورت خطی بر اساس حجم داده های ورودی افزایش می یابد. دو مورد مطالعات دیگر همچنین اثربخشی دیدگاه مبتنی بر این محدودیت را برای حل مشکلات جدید در سناریوهای جدید نشان می دهد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش مقاله
کشف الگو از طریق برنامه ریزی محدودیت
چکیده انگلیسی
Pattern discovery is one of the most fundamental problems in data mining. Various patterns with their discovering algorithms are proposed in different applications and domains. There is still a great demand for defining new meaningful patterns with new requirements since every application has its unique characteristics. Existing studies propose new query languages to describe these ad-hoc patterns. However, most of them focus on small variations of frequent item sets and association rules. Many meaningful patterns in other domains, such as temporal and spatial patterns, are not covered. This paper proposes a constraint based view for pattern discovery without introducing new languages, where the patterns are described by a collection of constraints given at run time. In this view, a pattern discovery problem is seen as a constraint satisfaction problem. This view provides a general framework for universal pattern discovery. Many previously known patterns can be regarded as different variations derived from this general framework with different constraints. Two generic algorithms are proposed for solving the constraint satisfaction problem. Empirical evaluation on two well-studied patterns shows that (1) the time cost of one generic algorithm is close to that of those specialized mining algorithms, and (2) the space cost of the generic algorithm increases linearly according to the input data volume. Two other case studies also demonstrate the effectiveness of this constraint based view for solving new problems in new scenarios.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Knowledge-Based Systems - Volume 94, 15 February 2016, Pages 23-32
نویسندگان
, , , ,