پوشش پیشوند

دنباله‌کاوی یکی از مسائل مهم و با استفاده‌های گسترده در داده‌کاوی است.
دنباله‌کاوی به این دلیل مسئله دشواری است که برای آن نیاز داریم تعداد زیادی زیردنباله تولید کنیم و آن‌ها را آزمایش کنیم.
تعداد زیادی از الگوریتم‌های دنباله‌کاوی مانند الگوریتم آپریوری از یک روش ساخت کاندید و آزمایش استفاده می‌کنند اما این روش برای پایگاه‌داده‌های شامل الگوهای متعدد یا زیاد مناسب و بهینه نیست.

پوشش پیشوند یک الگوریتم بهینه برای انجام دنباله‌کاوی است.
پوشش پیشوند یک الگوریتم تصویر محور است که از روش گسترش الگو استفاده می‌کند.
در این الگوریتم بصورت بازگشتی یک پایگاه‌داده به تعدادی پایگاه‌داده تصویرشده کوچکتر تبدیل می‌شود و الگوها برای هر پایگاه‌داده گسترش می‌یابند و برای هر کدام از پایگاه‌داده‌های کوچکتر الگوهای پرتکرار پیدا می‌شوند.

## صورت مسئله
I = \{i_1, i_2, \cdots, i_n \}
مجموعه آیتم‌ها است. یک مجموعه‌آیتم زیرمجموعه‌ای از مجموعه
I
است.
دنباله یک دنباله از مجموعه‌آیتم‌ها مانند  است که هرکدام از s_iها یک مجموعه‌آیتم هستند.
به هرکدام از s_iها یک عضو از دنباله می‌گوییم که به‌صورت (x_1,\cdots,x_m) است که هرکدام از x_iها یک آیتم هستند.

به دنباله \alpha =  زیردنباله‌ای از \beta =  می‌گوییم اگر
1 \leq j_1  موجود باشد که برای هر 1 \leq i \leq n مجموعه‌آیتم a_i زیرمجموعه‌ای از
b_{j_i} باشد و آنرا با علامت  \alpha \sqsubseteq \beta  نشان می‌دهیم.

اگر S مجموعه‌ای از دنباله‌ها باشد تعریف می‌کنیم:

Support_{S}(\alpha) = | \{ x  | x \in S \land \alpha \sqsubseteq x \} |

دنباله‌کاوی عددی به عنوان minSupport و مجموعه‌ای مانند S از دنباله‌ها دریافت می‌کند و همه دنباله‌های \alpha را می‌یابد که:

Support_S(\alpha) \geq minSupport

### مثال
اگر minSupport برابر ۲ باشد و اعضای S بترتیب  و  و
 باشد.
دنباله  شامل پنج عضو (a) و (abc) و (ac) و (d) و (cf) است که هرکدام یک مجموعه‌آیتم هستند.

در اینصورت  یک دنباله جواب است چون زیردنباله‌ای از دنباله‌های اول و سوم S است.

## الگوریتم
### پیشوند و تصویر و پسوند
در ابتدا فرض می‌کنیم همه آیتم‌های آیتم‌مجموعه‌ها بصورت مرتب شده هستند.
به دنباله \beta =  یک پیشوند از دنباله \alpha =  می‌گوییم اگر برای هر
j \leq m - 1 داشته باشیم i_j = e_j و e_m \subseteq i_m و همچنین آیتم‌های
i_m - e_m همگی بصورت الفبایی بعد از آیتم‌های e_m باشند.

اگر \beta زیردنباله‌ای از \alpha باشد تصویر \alpha با پیشوند \beta زیردنباله
\alpha ' از \alpha با شرایط زیر است:
# \beta پیشوندی از \alpha ' باشد.
# \alpha ' بیشینه باشد. یعنی هیچ \alpha ' \sqsubseteq \alpha * \sqsubseteq \alpha , \alpha ' \neq \alpha * موجود نباشد که \beta پیشوندی از \alpha * </math> باشد.

اگر <math>\beta = <e_1,\cdots, e_{m - 1}, e'_m></math> پیشوندی از <math>\alpha = <e_1,\cdots, e_n></math> باشد به دنباله
<math>\gamma = <e*_m,e_{m + 1}, \cdots, e_n> پسوند \alpha نسبت به \beta می‌گوییم که
e*_m = e_m - e'_m</math>.

به عنوان مثال <math>(a)(a)</math> پیشوندی از <math>(a)(abc)</math> است و پسوند مربوط به آن <math>(-bc)</math> است.

=== صورت الگوریتم ===
الگوریتم از این گذاره استفاده می‌کند که اگر <math>\{ x_1,\cdots,x_n\}</math> الگوهای پرتکرار با طول i باشند الگوهای به طول i + 1 را می‌توان به n دسته تقسیم کرد که اعضای دسته jام همگی دارای پیشوند <math>x_j</math> باشند.
با استفاده از گزاره قبل الگوریتم از سه مرحله تشکیل شده‌است:
# پیدا کردن همه الگوهای پرتکرار که طول آنها j است (آنهارا <math>x_1,\dots,x_m</math> بنامید).
# تقسیم فضای مسئله از این طریق که همه دنباله‌هایی که <math>x_i</math> زیردنباله‌ای از آن‌ها است را به <math>x_i</math> منتسب می‌کنیم.
# برای هر دنباله <math>x_i</math> پایگاه‌داده تصویر شده را ایجاد می‌کنیم و بصورت بازگشتی به یافتن الگوهای پرتکرار می‌گردیم. لازم است ذکر شود پایگاه‌داده تصویر شده از تصویر <math>x_i</math> روی همه دنباله‌های منتسب شده به <math>x_i</math> بدست می‌آید.

=== شبه کد ===

 *'Algorithm** (PrefixSpan) Prefix-projected sequential pattern mining
 **Input**: Database S, min_support
 **Output**: The complete set of sequential petterns
 **Method**: call PrefixSpan(<>, 0, S)
  **Subroutine** PrefixSpan(<math>\alpha, l, S|_\alpha</math>)
  The parameters are
  1. <math>\alpha</math> is sequential pattern
  2. l is length of <math>\alpha</math>
  3. <math>S|_\alpha</math> is <math>\alpha</math>-projected database if <math>\alpha \neq <></math>, otherwise, is the sequence database S
  **Method''' :
  1. Scan S|_\alpha once, find each frequent item, b, such that b can be assembled to the last element of \alpha to form a sequential
  pattern.
  2. For each frequent item b, append it to \alpha to form a sequential pattern \alpha', and output \alpha'.
  3. For each \alpha', construct \alpha'-projected database S|_{\alpha'}, and call PrefixSpan(\alpha', l+1, S|_{\alpha'}).

### مثال
فرض کنید مجموعه دنباله‌ها بصورت زیر باشد:

S = \{, \}

و مقدار min_support برابر ۲ باشد.
ابتدا دنباله‌های پرتکرار با طول ۱ را می‌یابیم که بوضوح با در نظر گرفتن تکرار آیتم‌ها ۴ دنباله ,,, قابل قبول هستند. حال باید پایگاه‌داده تصویرشده  را پیدا کنیم که چون  زیردنباله‌ای از سه دنباله هست پایگاه‌داده بصورت زیر می‌شود.

S|_{\alpha} = \{, ,  \}

حال با در نظر گرفتن آیتم‌هایی که حداقل دوبار در S|_{\alpha} تکرار شده‌اند در این مرحله دو دنباله به طول دو ,  پیدا می‌شود. با ادامه انجام این روند همه الگوهای پرتکرار یافت می‌شوند:

frequent_patterns = \{,,,,,,, \} 

## بهبود دهی
اگر اندازه پایگاه داده های ساخته‌شده کوچک شود به افزایش کارایی الگوریتم کمک می‌کند. به این منظور هنگام ساخت هر پایگاه‌داده تصویری از یک هرس داده‌ها با استفاده از بررسی‌های الگوریتم آپریوری استفاده می‌کنیم. به این روش تصویر دولایه(bi level projection) می‌گویند.

آزمایش‌ها نشان داده‌است که بیشتر هزینه این الگوریتم صرف ساخت پایگاه‌داده‌ها می‌شود و اگر اندازه پایگاه داده بزرگ باشد لازم است تعداد زیادی پایگاه‌داده تصویری تولید شود که هزینه زیادی دارد. به این منظور بجای ساخت فیزیکی پایگاه‌داده‌ها برای هر دنباله یک شماره در نظر می‌گیریم و در هر پایگاه‌داده تنها شماره دنباله‌ها و اندیس مکان شروع پسوند را نگه می‌داریم که باعث افزایش کارایی الگوریتم می‌شود.به این روش شبه تصویر(pseudo projction) می‌گویند. 
## جستارهای وابسته
* ‌دنباله‌کاوی
* الگوریتم آپریوری
## منابع

رده:الگوریتم‌های بیوانفورماتیک
رده:بیوانفورماتیک