دنباله‌کاوی - ویکی‌پدیا، دانشنامهٔ آزاد

دنباله کاوی یکی از مباحث داده‌کاوی است که سعی می‌کند بین داده‌های ورودی، الگوهایی که از لحاظ آماری به هم مرتبط هستند را پیدا کند. معمولاً فرض می‌شود که مقادیر دنباله‌ها گسسته است. دنباله‌کاوی یک حالت خاصی از داده کاوی ساختاری می‌باشد.

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

رشته‌کاوی به‌طور معمول با تعداد محدودی حروف الفبا سروکار دارد که در رشته‌ها ظاهر می‌شوند، در حالی که طول رشته‌ها ممکن است بسیار طولانی باشد. به عنوان مثالی از این حروف الفبا می‌توان به مجموعه حروف اسکی (استاندارد) که در زبان نوشتاری استفاده می‌شوند اشاره کرد یا حروف 'A' , 'G'،'C' و 'T' در رشته‌های دی‌ان‌ای یا اسید آمینه‌ها در رشته‌های پروتئین. در زیست‌شناسی، تجزیه و تحلیل چیدمان حروف الفبا در رشته به ما کمک می‌کند که ژن‌ها و پروتئین‌ها را شناخته و به خواص آن‌ها پی ببریم. در واقع پیدا کردن رشته‌ی یک دی‌ان‌ای یا پروتئین هدف اصلی نیست، بلکه هدف اصلی این است که به کمک رشته‌ی دی‌ان‌ای یا پروتئین پی به ساختار و عملکرد آن‌ها ببریم. برای این کار ابتدا باید مناطق مهم در رشته‌ها را تشخیص داده و سپس به هر منطقه یک عملکرد اختصاص دهیم. در بسیاری از مواقع این کار مستلزم این است که رشته‌ی داده شده را با رشته‌هایی که از قبل در اختیار داشتیم مقایسه کنیم. اگر فرض کنیم که در رشته‌ها عمل جایگیری، حذف و جهش رخ داده است، آن‌گاه مقایسه بین رشته‌ها دشوار می‌شود.

یک طبقه‌بندی بر الگوریتم‌های مقایسه رشته‌ها در بیوانفورماتیک در مقاله‌ی String Mining in Bioinformatics,^[۱] آمده‌است که شامل موارد زیر می‌شود:

• مسائل مربوط به تکرار: این مسائل روی یک رشته‌ی تنها تمرکز دارند و می‌توانند از الگوریتم‌های تطبیق کامل یا تطبیق تقریبی رشته‌ها برای پیدا کردن زیررشته‌های پراکنده و با طول بیشینه‌ی ثابت، تکرارهای پشت سر هم یا زیررشته‌های یکتا استفاده کنند.
• مسائل هم‌ترازی: این مسائل برای مقایسه بین رشته‌ها، ابتدا آن‌ها را با هم هم‌تراز می‌کنند. از جمله روش‌های معروف می‌توان به بلاست اشاره کرد که یک رشته‌ی تکی را با چندین رشته در پایگاه داده مقایسه می‌کند، و همچنین روش کلاستال که برای هم‌ترازسازی چندتوالی به کار می‌رود. الگوریتم‌های هم‌ترازسازی می‌توانند بر پایه‌ی روش‌های تطبیق کامل یا تطبیق تقریبی بنا شده و همچنین می‌توانند به سه دسته‌ی هم‌ترازسازی سراسری، شبه‌سراسری یا محلی تقسیم شوند. هم‌ترازسازی توالی را ببینید.

برخی از مسائل در دنباله‌کاوی به دنبال پیدا کردن مجموعه آیتم‌ها و ترتیب ظاهر شدنشان می‌باشند. به‌طور مثال دنبال قانونی به شکل "اگر {مشتری ماشین بخرد} او احتمالاً تا یک هفته‌ی بعد {بیمه می‌خرد}" می‌گردیم. به‌طور سنتی مجموعه آیتم‌کاوی در بازاریابی کاربرد داشته‌است. سعی بر این بوده است که در معاملات بزرگ به دنبال خریدهایی باشند که اکثراً با هم اتفاق می‌افتند و نظم حاکم بر آن‌ها را پیدا کنند. به‌طور مثال با مطالعه‌ی سبد خرید مشتری‌ها در یک سوپرمارکت این قانون را می‌توان استخراج کرد که "اگر مشتری پیاز و سیب زمینی بخرد، او احتمالاً در همان خرید همبرگر نیز خواهد خرید".

یک طبقه‌بندی بر الگوریتم‌های مجموعه آیتم‌کاوی در مقاله Frequent pattern mining: current status and future directions.^[۲] آمده‌است.

مشارکت‌کنندگان ویکی‌پدیا. «Sequence mining». در دانشنامهٔ ویکی‌پدیای انگلیسی.