دنباله‌کاوی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

رشته کاوی[ویرایش]

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

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

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

مجموعه آیتم کاوی[ویرایش]

برخی از مسائل در دنباله کاوی به دنبال پیدا کردن مجموعه آیتم ها و ترتیب ظاهر شدنشان میباشند. به طور مثال دنبال قانونی به شکل "اگر {مشتری ماشین بخرد} او احتمالاً تا یک هفته ی بعد {بیمه میخرد}" میگردیم. به طور سنتی مجموعه آیتم کاوی در بازاریابی کاربرد داشته است. سعی بر این بوده است که در معاملات بزرگ به دنبال خرید هایی باشند که اکثراً با هم اتفاق می افتند و نظم حاکم بر آنها را پیدا کنند. به طور مثال با مطالعه ی سبد خرید مشتری ها در یک سوپرمارکت این قانون را میتوان استخراج کرد که "اگر مشتری پیاز و سیب زمینی بخرد، او احتمالاً در همان خرید همبرگر نیز خواهد خرید". یک طبقه بندی بر الگوریتم های مجموعه آیتم کاوی در مقاله Frequent pattern mining: current status and future directions.[۲] آمده است.

منابع[ویرایش]

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