پوشش پیشوند کیست؟ توضیح بده.
دنباله‌کاوی یکی از مسائل مهم و با استفاده‌های گسترده در داده‌کاوی است.دنباله‌کاوی به این دلیل مسئله دشواری است که برای آن نیاز داریم تعداد زیادی زیردنباله تولید کنیم و آن‌ها را آزمایش کنیم.تعداد زیادی از الگوریتم‌های دنباله‌کاوی مانند الگوریتم آپریوری از یک روش ساخت کاندید و آزمایش استفاده می‌کنند اما این روش برای پایگاه‌داده‌های شامل الگوهای متعدد یا زیاد مناسب و بهینه نیست.پوشش پیشوند یک الگوریتم بهینه برای انجام دنباله‌کاوی است.پوشش پیشوند یک الگوریتم تصویر محور است که از روش گسترش الگو استفاده می‌کند.در این الگوریتم بصورت بازگشتی یک پایگاه‌داده به تعدادی پایگاه‌داده تصویرشده کوچکتر تبدیل می‌شود و الگوها برای هر پایگاه‌داده گسترش می‌یابند و برای هر کدام از پایگاه‌داده‌های کوچکتر الگوهای پرتکرار پیدا می‌شوند.صورت مسئله.formula_1مجموعه آیتم‌ها است. یک مجموعه‌آیتم زیرمجموعه‌ای از مجموعهformula_2است.دنباله یک دنباله از مجموعه‌آیتم‌ها مانند formula_3 است که هرکدام از formula_4ها یک مجموعه‌آیتم هستند.به هرکدام از formula_4ها یک عضو از دنباله می‌گوییم که به‌صورت formula_6 است که هرکدام از formula_7ها یک آیتم هستند.به دنباله formula_8 زیردنباله‌ای از formula_9 می‌گوییم اگرformula_10 موجود باشد که برای هر formula_11 مجموعه‌آیتم formula_12 زیرمجموعه‌ای ازformula_13 باشد و آنرا با علامت formula_14 نشان می‌دهیم.اگر S مجموعه‌ای از دنباله‌ها باشد تعریف می‌کنیم:formula_15دنباله‌کاوی عددی به عنوان minSupport و مجموعه‌ای مانند S از دنباله‌ها دریافت می‌کند و همه دنباله‌های formula_16 را می‌یابد که:formula_17مثال.اگر minSupport برابر ۲ باشد و اعضای S بترتیب formula_18 و formula_19 وformula_20 باشد.دنباله formula_18 شامل پنج عضو (a) و (abc) و (ac) و (d) و (cf) است که هرکدام یک مجموعه‌آیتم هستند.در اینصورت formula_22 یک دنباله جواب است چون زیردنباله‌ای از دنباله‌های اول و سوم S است.الگوریتم.پیشوند و تصویر و پسوند.در ابتدا فرض می‌کنیم همه آیتم‌های آیتم‌مجموعه‌ها بصورت مرتب شده هستند.به دنباله formula_23 یک پیشوند از دنباله formula_24 می‌گوییم اگر برای هرformula_25 داشته باشیم formula_26 و formula_27 و همچنین آیتم‌هایformula_28 همگی بصورت الفبایی بعد از آیتم‌های formula_29 باشند.اگر formula_30 زیردنباله‌ای از formula_16 باشد تصویر formula_16 با پیشوند formula_30 زیردنبالهformula_34 از formula_16 با شرایط زیر است:اگر formula_42 پیشوندی از formula_43 باشد به دنبالهformula_44 پسوند formula_16 نسبت به formula_30 می‌گوییم کهformula_47.به عنوان مثال formula_48 پیشوندی از formula_49 است و پسوند مربوط به آن formula_50 است.صورت الگوریتم.الگوریتم از این گذاره استفاده می‌کند که اگر formula_51 الگوهای پرتکرار با طول i باشند الگوهای به طول i + 1 را می‌توان به n دسته تقسیم کرد که اعضای دسته jام همگی دارای پیشوند formula_52 باشند.با استفاده از گزاره قبل الگوریتم از سه مرحله تشکیل شده‌است:شبه کد. Algorithm (PrefixSpan) Prefix-projected sequential pattern mining Input: Database S, min_support Output: The complete set of sequential petterns Method: call PrefixSpan(&lt;&gt;, 0, S) Subroutine PrefixSpan(formula_59) The parameters are 1. formula_16 is sequential pattern 2. l is length of formula_16 3. formula_62 is formula_16-projected database if formula_64, otherwise, is the sequence database S Method : 1. Scan formula_62 once, find each frequent item, b, such that b can be assembled to the last element of formula_16 to form a sequential pattern. 2. For each frequent item b, append it to formula_16 to form a sequential pattern formula_68, and output formula_68. 3. For each formula_68, construct formula_68-projected database formula_72, and call PrefixSpan(formula_73).مثال.فرض کنید مجموعه دنباله‌ها بصورت زیر باشد:formula_74و مقدار min_support برابر ۲ باشد.ابتدا دنباله‌های پرتکرار با طول ۱ را می‌یابیم که بوضوح با در نظر گرفتن تکرار آیتم‌ها ۴ دنباله formula_75 قابل قبول هستند. حال باید پایگاه‌داده تصویرشده formula_76 را پیدا کنیم که چون formula_76 زیردنباله‌ای از سه دنباله هست پایگاه‌داده بصورت زیر می‌شود.formula_78حال با در نظر گرفتن آیتم‌هایی که حداقل دوبار در formula_79 تکرار شده‌اند در این مرحله دو دنباله به طول دو formula_80 پیدا می‌شود. با ادامه انجام این روند همه الگوهای پرتکرار یافت می‌شوند:frequent_patterns = formula_81بهبود دهی.اگر اندازه پایگاه داده های ساخته‌شده کوچک شود به افزایش کارایی الگوریتم کمک می‌کند. به این منظور هنگام ساخت هر پایگاه‌داده تصویری از یک هرس داده‌ها با استفاده از بررسی‌های الگوریتم آپریوری استفاده می‌کنیم. به این روش تصویر دولایه(bi level projection) می‌گویند.آزمایش‌ها نشان داده‌است که بیشتر هزینه این الگوریتم صرف ساخت پایگاه‌داده‌ها می‌شود و اگر اندازه پایگاه داده بزرگ باشد لازم است تعداد زیادی پایگاه‌داده تصویری تولید شود که هزینه زیادی دارد. به این منظور بجای ساخت فیزیکی پایگاه‌داده‌ها برای هر دنباله یک شماره در نظر می‌گیریم و در هر پایگاه‌داده تنها شماره دنباله‌ها و اندیس مکان شروع پسوند را نگه می‌داریم که باعث افزایش کارایی الگوریتم می‌شود.به این روش شبه تصویر(pseudo projction) می‌گویند.