پوشش پیشوند

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

پوشش پیشوند(به انگلیسی: prefixspan) یک الگوریتم بهینه برای انجام دنباله‌کاوی است. پوشش پیشوند یک الگوریتم تصویر محور است که از روش گسترش الگو استفاده می‌کند. در این الگوریتم بصورت بازگشتی یک پایگاه‌داده به تعدادی پایگاه‌داده تصویرشده کوچکتر تبدیل می‌شود و الگوها برای هر پایگاه‌داده گسترش می‌یابند و برای هر کدام از پایگاه‌داده‌های کوچکتر الگوهای پرتکرار پیدا می‌شوند.^[۱]

صورت مسئله

$I=\{i_{1},i_{2},\cdots ,i_{n}\}$ مجموعه آیتم‌ها است. یک مجموعه‌آیتم زیرمجموعه‌ای از مجموعه $I$ است. دنباله یک دنباله از مجموعه‌آیتم‌ها مانند $<s_{1},\cdots ,s_{j}>$ است که هرکدام از $s_{i}$ ها یک مجموعه‌آیتم هستند. به هرکدام از $s_{i}$ ها یک عضو از دنباله می‌گوییم که به‌صورت $(x_{1},\cdots ,x_{m})$ است که هرکدام از $x_{i}$ ها یک آیتم هستند.

به دنباله $\alpha =<a_{1},\cdots ,a_{n}>$ زیردنباله‌ای از $\beta =<b_{1},\cdots ,b_{m}>$ می‌گوییم اگر $1\leq j_{1}<\cdots <j_{n}\leq m$ موجود باشد که برای هر $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)>$ و $<(ad)(c)(bc)(ae)>$ و $<(ef)(ab)(df)(c)(b)>$ باشد. دنباله $<(a)(abc)(ac)(d)(cf)>$ شامل پنج عضو (a) و (abc) و (ac) و (d) و (cf) است که هرکدام یک مجموعه‌آیتم هستند.

در اینصورت $<(ab)(c)>$ یک دنباله جواب است چون زیردنباله‌ای از دنباله‌های اول و سوم S است.^[۲]

الگوریتم

پیشوند و تصویر و پسوند

در ابتدا فرض می‌کنیم همه آیتم‌های آیتم‌مجموعه‌ها بصورت مرتب شده هستند. به دنباله $\beta =<e_{1},\cdots ,e_{m}>$ یک پیشوند از دنباله $\alpha =<i_{1},\cdots ,i_{n}>$ می‌گوییم اگر برای هر $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 ''$ باشد.

اگر $\beta =<e_{1},\cdots ,e_{m-1},e'_{m}>$ پیشوندی از $\alpha =<e_{1},\cdots ,e_{n}>$ باشد به دنباله $\gamma =<e''_{m},e_{m+1},\cdots ,e_{n}>$ پسوند $\alpha$ نسبت به $\beta$ می‌گوییم که $e''_{m}=e_{m}-e'_{m}$ .

به عنوان مثال $(a)(a)$ پیشوندی از $(a)(abc)$ است و پسوند مربوط به آن $(-bc)$ است.^[۳]

صورت الگوریتم

الگوریتم از این گذاره استفاده می‌کند که اگر $\{x_{1},\cdots ,x_{n}\}$ الگوهای پرتکرار با طول i باشند الگوهای به طول i + 1 را می‌توان به n دسته تقسیم کرد که اعضای دسته jام همگی دارای پیشوند $x_{j}$ باشند. با استفاده از گزاره قبل الگوریتم از سه مرحله تشکیل شده‌است:

پیدا کردن همه الگوهای پرتکرار که طول آنها j است (آنهارا $x_{1},\dots ,x_{m}$ بنامید).
تقسیم فضای مسئله از این طریق که همه دنباله‌هایی که $x_{i}$ زیردنباله‌ای از آن‌ها است را به $x_{i}$ منتسب می‌کنیم.
برای هر دنباله $x_{i}$ پایگاه‌داده تصویر شده را ایجاد می‌کنیم و بصورت بازگشتی به یافتن الگوهای پرتکرار می‌گردیم. لازم است ذکر شود پایگاه‌داده تصویر شده از تصویر $x_{i}$ روی همه دنباله‌های منتسب شده به $x_{i}$ بدست می‌آید.^[۴]

شبه کد

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( $\alpha ,l,S|_{\alpha }$ )
 The parameters are
 1.  $\alpha$  is sequential pattern
 2. l is length of  $\alpha$ 
 3.  $S|_{\alpha }$  is  $\alpha$ -projected database if  $\alpha \neq <>$ , 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=\{<(a)(abc)(d)>,<(ad)(c)(bc),<(e)(g)(af)>\}$

و مقدار min_support برابر ۲ باشد. ابتدا دنباله‌های پرتکرار با طول ۱ را می‌یابیم که بوضوح با در نظر گرفتن تکرار آیتم‌ها ۴ دنباله $<(a)>,<(b)>,<(c)>,<(d)>$ قابل قبول هستند. حال باید پایگاه‌داده تصویرشده $<(a)>$ را پیدا کنیم که چون $<(a)>$ زیردنباله‌ای از سه دنباله هست پایگاه‌داده بصورت زیر می‌شود.

$S|_{\alpha }=\{<(abc)(d)>,<(-d)(c)(bc)>,<(-f)>\}$

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

frequent_patterns = $\{<(a)>,<(b)>,<(c)>,<(d)>,<(a)(b)>,<(a)(c)>,<(a)(bc)>,<(bc)>\}$

بهبود دهی

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

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

جستارهای وابسته

منابع

↑ Pei, Jian (2000-10-04). "Mining sequential patterns by pattern-growth: the PrefixSpan approach". IEEE (به انگلیسی). 16 (11): 1424–24. doi:10.1109/TKDE.2004.77. ISSN 1558-2191.
↑ Mabroukeh, N. R.; Ezeife, C. I. (2010). "A taxonomy of sequential pattern mining algorithms". ACM Computing Surveys. 43: 1–41. CiteSeerX 10.1.1.332.4745. doi:10.1145/1824795.1824798.
↑ Han, Jiawei (2001-02-01). "PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth". IEEE (به انگلیسی). doi:10.1109/ICDE.2001.914830. ISSN 1063-6382.
↑ Pei, Jian (2000-10-04). "Mining sequential patterns by pattern-growth: the PrefixSpan approach". IEEE (به انگلیسی). 16 (11): 1430–32. doi:10.1109/TKDE.2004.77. ISSN 1558-2191.
↑ Han, Jiawei (2001-02-01). "PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth". IEEE (به انگلیسی). doi:10.1109/ICDE.2001.914830. ISSN 1063-6382.

[1] Pei, Jian (2000-10-04). "Mining sequential patterns by pattern-growth: the PrefixSpan approach". IEEE (به انگلیسی). 16 (11): 1424–24. doi:10.1109/TKDE.2004.77. ISSN 1558-2191.

[2] Mabroukeh, N. R.; Ezeife, C. I. (2010). "A taxonomy of sequential pattern mining algorithms". ACM Computing Surveys. 43: 1–41. CiteSeerX 10.1.1.332.4745. doi:10.1145/1824795.1824798.

[3] Han, Jiawei (2001-02-01). "PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth". IEEE (به انگلیسی). doi:10.1109/ICDE.2001.914830. ISSN 1063-6382.

[4] Pei, Jian (2000-10-04). "Mining sequential patterns by pattern-growth: the PrefixSpan approach". IEEE (به انگلیسی). 16 (11): 1430–32. doi:10.1109/TKDE.2004.77. ISSN 1558-2191.

[5] Han, Jiawei (2001-02-01). "PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth". IEEE (به انگلیسی). doi:10.1109/ICDE.2001.914830. ISSN 1063-6382.

[۱]

[۲]

[۳]

[۴]

[۵]