الگوریتم آپریوری

اپریوری (به انگلیسی: Apriori)، یک الگوریتم برای استخراج مکرر مجموعه‌های مورد و یادگیری قوانین مرتبط با پایگاه‌های داده رابطه‌ای است. با شناسایی موارد فردی مکرر در پایگاه داده و گسترش آنها به مجموعه اقلام بزرگتر و بزرگتر تا زمانی که آن مجموعه موارد به طور کافی در پایگاه داده ظاهر شود، ادامه می‌یابد. مجموعه‌های مکرر موارد تعیین شده توسط ایپرایوری می‌تواند برای تعیین قوانین ارتباطی که روندهای کلی در پایگاه داده را برجسته می‌کند، مورد استفاده قرار گیرد: این الگوریتم در حوزه‌هایی مانند تجزیه و تحلیل سبد بازار کاربرد دارد.

بررسی اجمالی

الگوریتم اپریوری، توسط Agrawal و Srikant در سال 1994 پیشنهاد شد. اپریوری طوری طراحی شده است که در معاملات پایگاه داده (مانند مجموعه‌ای از اقلام خریداری شده توسط مشتریان، یا جزئیات فراوانی وب سایت یا آدرس IP) عمل کند .

الگوریتم‌های دیگر برای یافتن قوانین ارتباط در داده‌های بدون تراکنش (Winepi و Minepi) یا فاقد زمان (توالی DNA) طراحی شده‌اند. هر معامله به عنوان مجموعه‌ای از اقلام (یک «مجموعه اقلام») دیده می‌شود. با توجه به آستانه $C$، الگوریتم اپریوری مجموعه مواردی را که زیرمجموعه حداقل معاملات $C$ در پایگاه داده هستند، شناسایی می‌کند.

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

اپریوری از وسعت جستجوی اول و یک ساختار درخت Hash برای شمارش کارآمد مجموعه آیتم‌های نامزد استفاده می‌کند. این مجموعه آیتم‌های نامزد با طول $K$ را از مجموعه آیتم‌های طول $K-1$ تولید می‌کند. سپس نامزدهایی را که الگوی فرعی نادر دارند، هرس می‌کند. با توجه به لمای بسته شدن رو به پایین، مجموعه کاندید شامل همه مجموعه‌های آیتم $K$ مکرر است. پس از آن، پایگاه داده معاملات را برای تعیین مجموعه موارد مکرر در بین نامزدها اسکن می‌کند.

کد شبه الگوریتم در زیر برای پایگاه داده تراکنش $T$ و آستانه پشتیبانی $\ varepsilon$ آورده شده است. نماد نظری مجموعه‌ای معمولی استفاده می‌شود، اگر چه توجه داشته باشید که $T$ یک چند مجموعه است. $C_{k}$ نامزدی است که برای سطح $k$ تنظیم شده است. در هر مرحله، فرض بر این است که الگوریتم مجموعه‌های نامزد را از مجموعه‌های بزرگ سطح قبلی ایجاد می‌کند و به لمای بسته شدن رو به پایین توجه می‌کند. $\ mathrm{count}[c]$ به فیلدی از ساختار داده دسترسی دارد که نشان دهنده مجموعه نامزد $c$ است، که در ابتدا صفر فرض می‌شود. بسیاری از جزئیات در زیر حذف شده است، معمولاً مهمترین بخش پیاده‌سازی ساختار داده‌ای است که برای ذخیره مجموعه‌های نامزد و شمارش فرکانس آنها استفاده می‌شود.

Apriori(T, ε)
    L1 ← {large 1 - itemsets}
    k ← 2
    while Lk−1 is not empty
        Ck ← Apriori_gen(Lk−1, k)
        for transactions t in T
            Dt ← {c in Ck : c ⊆ t}
            for candidates c in Dt
                count[c] ← count[c] + 1

        Lk ← {c in Ck : count[c] ≥ ε}
        k ← k + 1

    return Union(Lk)
    
Apriori_gen(L, k)
     result ← list()
     for all p ⊆ L, q ⊆ L where p1 = q1, p2 = q2, ..., pk-2 = qk-2 and pk-1 < qk-1
         c = p ∪ {qk-1}
         if u ⊆ c for all u in L
             result.add(c)
      return result

آپریوری، از آیتم ست‌هایی با طول k-1، آیتم ست‌های کاندید با طول k را تولید می‌کند. سپس، کاندیدهایی که زیرالگوهای نادر (زیرالگوهایی که کم اتفاق می‌افتد) را هرس می‌کند. با توجه به downward closure lemma، مجموعه کاندید، شامل همه آیتم ست‌های مکرر با طول k هستند. پس از آن، پایگاه داده تراکنشی را برای تعیین آیتم ست‌های مکرر ار بین کاندیدها، اسکن می‌کند.

مثال‌ها

مثال ۱

پایگاه داده زیر را در نظر بگیرید ، جایی که هر سطر یک تراکنش است و هر سلول یک مورد جداگانه از معامله است:

آلفا	بتا	اپسیلون
آلفا	بتا	تتا
آلفا	بتا	اپسیلون
آلفا	بتا	تتا

قوانین ارتباطی که می توان از این پایگاه داده تعیین کرد به شرح زیر است:

1. 100% مجموعه‌های دارای آلفا همچنین حاوی بتا است
2. 50% مجموعه‌های دارای آلفا و بتا همچنین حاوی اپسیلون است
3. 50% مجموعه‌های دارای آلفا و بتا همچنین حاوی تتا است

ما همچنین می‌توانیم این را از طریق مثال‌های مختلف نشان دهیم.

مثال ۲

فرض کنید یک سوپرمارکت بزرگ اطلاعات فروش واحد نگهداری سهام (SKU) را برای هر مورد پیگیری می‌کند: هر مورد، مانند "کره" یا "نان"، با SKU عددی مشخص می‌شود. این سوپرمارکت دارای پایگاه داده‌ای از معاملات است که در آن هر معامله مجموعه‌ای از SKU است که با هم خریداری شده‌اند

اجازه دهید پایگاه داده معاملات شامل مجموعه های زیر باشد:

مجموعه آیتم‌ها
{1,2,3,4}
{1,2,4}
{1,2}
{2,3,4}
{2,3}
{3,4}
{2,4}

ما از اپریوری برای تعیین مجموعه موارد مکرر این پایگاه داده استفاده خواهیم کرد. برای انجام این کار، ما می‌گوییم که یک مجموعه مورد مکرر است اگر حداقل در 3 تراکنش پایگاه داده ظاهر شود: مقدار 3 «آستانه پشتیبانی» (به انگلیسی: support threshold) است.

اولین قدم اپریوری شمارش تعداد وقایع، به نام پشتیبانی (به انگلیسی: support)، از هر مورد عضو به طور جداگانه است. با اسکن پایگاه داده برای اولین بار، نتیجه زیر را بدست می‌آوریم

آیتم	پشتیبانی
{1}	3
{2}	6
{3}	4
{4}	5

همه مجموعه های اندازه 1 دارای پشتیبانی حداقل 3 هستند، بنابراین همه آنها مکرر هستند.

گام بعدی این است که لیستی از همه جفت موارد متداول تهیه کنید.

به عنوان مثال، در مورد جفت {1،2}: جدول اول مثال ۲ موارد ۱ و ۲ را در سه مورد از مجموعه‌ها نشان می‌دهد. بنابراین، ما می‌گوییم مورد {1،2} از سه پشتیبانی می‌کند.

آیتم	پشتیبانی
{1,2}	3
{1,3}	1
{1,4}	2
{2,3}	3
{2,4}	4
{3,4}	3

جفت های {1،2}، {2،3}، {2،4} و {3،4} همگی از حداقل 3 پشتیبانی می‌کنند یا فراتر می‌روند، بنابراین مکرر هستند. جفت‌های {1،3} و {1،4} نیستند. در حال حاضر، چون {1،3} و {1،4} مکرر نیستند، هر مجموعه بزرگتر که حاوی {1،3} یا {1،4} باشد نمی‌تواند مکرر باشد. به این ترتیب، ما می‌توانیم مجموعه‌ها را «هرس» کنیم: اکنون به دنبال سه‌گانه‌های مکرر در پایگاه داده هستیم، اما می‌توانیم همه سه‌گانه‌های حاوی یکی از این دو جفت را حذف کنیم:

آیتم	پشتیبانی
{2,3,4}	2

در مثال، هیچ سه قلو مکرر وجود ندارد. {2،3،4} زیر حداقل آستانه است و سایر سه قلوها حذف شدند زیرا آنها مجموعه‌های فوق العاده‌ای از جفت بودند که قبلاً زیر آستانه بودند.

ما این مجموعه‌های مکرر موارد را در پایگاه داده تعیین می‌کنیم و نشان می‌دهیم که چگونه برخی از اقلام شمارش نشده‌اند؛ زیرا یکی از زیر مجموعه‌های آنها قبلاً زیر آستانه شناخته شده است.

محدودیت‌ها

اپریوری، در حالی که از نظر تاریخی قابل توجه است، از تعدادی ناکارآمدی یا جبران رنج می برد، که الگوریتم‌های دیگری را ایجاد کرده است. تولید نامزد، تعداد زیادی زیر مجموعه ایجاد می‌کند (الگوریتم سعی می‌کند مجموعه نامزد را با حداکثر زیر مجموعه‌های ممکن قبل از هر بار اسکن پایگاه داده بارگذاری کند). اکتشاف زیر مجموعه از بالا (اساساً اولین عرض از شبکه زیرمجموعه) هر زیرمجموعه S را تنها پس از همه $2^{|S|}-1$ زیرمجموعه‌های مناسب خود پیدا می‌کند.

این الگوریتم پایگاه داده را بیش از حد اسکن می‌کند، که باعث کاهش عملکرد کلی می‌شود. به همین دلیل، الگوریتم فرض می‌کند که پایگاه داده به طور دائم در حافظه است.

همچنین، هم پیچیدگی زمانی و هم مکانی این الگوریتم بسیار زیاد است: $O\ left(2^{|D|}\ right)$، بنابراین نمایی، جایی که $|D|$ عرض افقی (تعداد کل اقلام) موجود در پایگاه داده است.