دنباله‌کاوی

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

رشته کاوی

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

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

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

مجموعه آیتم کاوی

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

منابع

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

[1] String M. Abouelhoda, M. Ghanem. String Mining in Bioinformatics. In M. M. Gaber (Editor) Scientific Data Mining and Knowledge Discovery. Springer2009

[2] J. Han, H. Cheng, D. Xin and X. Yan Frequent pattern mining: current status and future directions. In Data Mining and Knowledge Discovery Volume 15, Number 1, 55-86, doi:10.1007/s10618-006-0059-1