الگوریتم آپریوری
اپریوری ، یک الگوریتم برای استخراج مکرر مجموعه‌های مورد و یادگیری قوانین مرتبط با پایگاه‌های داده رابطه‌ای است. با شناسایی موارد فردی مکرر در پایگاه داده و گسترش آنها به مجموعه اقلام بزرگتر و بزرگتر تا زمانی که آن مجموعه موارد به طور کافی در پایگاه داده ظاهر شود، ادامه می‌یابد. مجموعه‌های مکرر موارد تعیین شده توسط ایپرایوری می‌تواند برای تعیین قوانین ارتباطی که روندهای کلی در پایگاه داده را برجسته می‌کند، مورد استفاده قرار گیرد: این الگوریتم در حوزه‌هایی مانند تجزیه و تحلیل سبد بازار کاربرد دارد.
الگوریتم اپریوری، توسط Agrawal و Srikant در سال 1994 پیشنهاد شد. اپریوری طوری طراحی شده است که در معاملات پایگاه داده (مانند مجموعه‌ای از اقلام خریداری شده توسط مشتریان، یا جزئیات فراوانی وب سایت یا آدرس IP) عمل کند .
الگوریتم‌های دیگر برای یافتن قوانین ارتباط در داده‌های بدون تراکنش (Winepi و Minepi) یا فاقد زمان (توالی DNA) طراحی شده‌اند. هر معامله به عنوان مجموعه‌ای از اقلام (یک «مجموعه اقلام») دیده می‌شود. با توجه به آستانه formula_1، الگوریتم اپریوری مجموعه مواردی را که زیرمجموعه حداقل معاملات formula_1 در پایگاه داده هستند، شناسایی می‌کند.
الگوریتم تلاش می‌کند تا زیرمجموعه‌هایی از آیتم‌ها را که حداقل بین C مجموعه آیتم مشترک است، بیابد. آپریوری یک الگوریتم پایین به بالا است، آنگونه که در هر مرحله یک آیتم به زیرمجموعه‌های مکرر اضافه می‌شود (تولید کاندید). مجموعه کاندیدها روی داده مورد ارزیابی قرار می‌گیرند. شرط خاتمه الگوریتم، عدم وجود شیوه توسعه موفق دیگری است.
اپریوری از وسعت جستجوی اول و یک ساختار درخت Hash برای شمارش کارآمد مجموعه آیتم‌های نامزد استفاده می‌کند. این مجموعه آیتم‌های نامزد با طول formula_3 را از مجموعه آیتم‌های طول formula_4 تولید می‌کند. سپس نامزدهایی را که الگوی فرعی نادر دارند، هرس می‌کند. با توجه به لمای بسته شدن رو به پایین، مجموعه کاندید شامل همه مجموعه‌های آیتم formula_3 مکرر است. پس از آن، پایگاه داده معاملات را برای تعیین مجموعه موارد مکرر در بین نامزدها اسکن می‌کند.
کد شبه الگوریتم در زیر برای پایگاه داده تراکنش formula_6 و آستانه پشتیبانی formula_7 آورده شده است. نماد نظری مجموعه‌ای معمولی استفاده می‌شود، اگر چه توجه داشته باشید که formula_6 یک چند مجموعه است. formula_9 نامزدی است که برای سطح formula_10 تنظیم شده است. در هر مرحله، فرض بر این است که الگوریتم مجموعه‌های نامزد را از مجموعه‌های بزرگ سطح قبلی ایجاد می‌کند و به لمای بسته شدن رو به پایین توجه می‌کند. formula_11 به فیلدی از ساختار داده دسترسی دارد که نشان دهنده مجموعه نامزد formula_12 است، که در ابتدا صفر فرض می‌شود. بسیاری از جزئیات در زیر حذف شده است، معمولاً مهمترین بخش پیاده‌سازی ساختار داده‌ای است که برای ذخیره مجموعه‌های نامزد و شمارش فرکانس آنها استفاده می‌شود. آپریوری، از آیتم ست‌هایی با طول k-1، آیتم ست‌های کاندید با طول k را تولید می‌کند. سپس، کاندیدهایی که زیرالگوهای نادر (زیرالگوهایی که کم اتفاق می‌افتد) را هرس می‌کند. با توجه به downward closure lemma، مجموعه کاندید، شامل همه آیتم ست‌های مکرر با طول k هستند. پس از آن، پایگاه داده تراکنشی را برای تعیین آیتم ست‌های مکرر ار بین کاندیدها، اسکن می‌کند.
پایگاه داده زیر را در نظر بگیرید ، جایی که هر سطر یک تراکنش است و هر سلول یک مورد جداگانه از معامله است:
قوانین ارتباطی که می توان از این پایگاه داده تعیین کرد به شرح زیر است:
ما همچنین می‌توانیم این را از طریق مثال‌های مختلف نشان دهیم.
فرض کنید یک سوپرمارکت بزرگ اطلاعات فروش واحد نگهداری سهام (SKU) را برای هر مورد پیگیری می‌کند: هر مورد، مانند "کره" یا "نان"، با SKU عددی مشخص می‌شود. این سوپرمارکت دارای پایگاه داده‌ای از معاملات است که در آن هر معامله مجموعه‌ای از SKU است که با هم خریداری شده‌اند
اجازه دهید پایگاه داده معاملات شامل مجموعه های زیر باشد:
ما از اپریوری برای تعیین مجموعه موارد مکرر این پایگاه داده استفاده خواهیم کرد. برای انجام این کار، ما می‌گوییم که یک مجموعه مورد مکرر است اگر حداقل در 3 تراکنش پایگاه داده ظاهر شود: مقدار 3 «آستانه پشتیبانی» است.
اولین قدم اپریوری شمارش تعداد وقایع، به نام پشتیبانی ، از هر مورد عضو به طور جداگانه است. با اسکن پایگاه داده برای اولین بار، نتیجه زیر را بدست می‌آوریم
همه مجموعه های اندازه 1 دارای پشتیبانی حداقل 3 هستند، بنابراین همه آنها مکرر هستند.
گام بعدی این است که لیستی از همه جفت موارد متداول تهیه کنید.
به عنوان مثال، در مورد جفت {1،2}: جدول اول مثال ۲ موارد ۱ و ۲ را در سه مورد از مجموعه‌ها نشان می‌دهد. بنابراین، ما می‌گوییم مورد {1،2} از سه پشتیبانی می‌کند.
جفت های {1،2}، {2،3}، {2،4} و {3،4} همگی از حداقل 3 پشتیبانی می‌کنند یا فراتر می‌روند، بنابراین مکرر هستند. جفت‌های {1،3} و {1،4} نیستند. در حال حاضر، چون {1،3} و {1،4} مکرر نیستند، هر مجموعه بزرگتر که حاوی {1،3} یا {1،4} باشد نمی‌تواند مکرر باشد. به این ترتیب، ما می‌توانیم مجموعه‌ها را «هرس» کنیم: اکنون به دنبال سه‌گانه‌های مکرر در پایگاه داده هستیم، اما می‌توانیم همه سه‌گانه‌های حاوی یکی از این دو جفت را حذف کنیم:
در مثال، هیچ سه قلو مکرر وجود ندارد. {2،3،4} زیر حداقل آستانه است و سایر سه قلوها حذف شدند زیرا آنها مجموعه‌های فوق العاده‌ای از جفت بودند که قبلاً زیر آستانه بودند.
ما این مجموعه‌های مکرر موارد را در پایگاه داده تعیین می‌کنیم و نشان می‌دهیم که چگونه برخی از اقلام شمارش نشده‌اند؛ زیرا یکی از زیر مجموعه‌های آنها قبلاً زیر آستانه شناخته شده است.
اپریوری، در حالی که از نظر تاریخی قابل توجه است، از تعدادی ناکارآمدی یا جبران رنج می برد، که الگوریتم‌های دیگری را ایجاد کرده است. تولید نامزد، تعداد زیادی زیر مجموعه ایجاد می‌کند (الگوریتم سعی می‌کند مجموعه نامزد را با حداکثر زیر مجموعه‌های ممکن قبل از هر بار اسکن پایگاه داده بارگذاری کند). اکتشاف زیر مجموعه از بالا (اساساً اولین عرض از شبکه زیرمجموعه) هر زیرمجموعه S را تنها پس از همه formula_13 زیرمجموعه‌های مناسب خود پیدا می‌کند.
این الگوریتم پایگاه داده را بیش از حد اسکن می‌کند، که باعث کاهش عملکرد کلی می‌شود. به همین دلیل، الگوریتم فرض می‌کند که پایگاه داده به طور دائم در حافظه است.
همچنین، هم پیچیدگی زمانی و هم مکانی این الگوریتم بسیار زیاد است: formula_14، بنابراین نمایی، جایی که formula_15 عرض افقی (تعداد کل اقلام) موجود در پایگاه داده است.