موضوع مقاله: الگوریتم آپریوری | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم آپریوری | مقدمه: اپریوری< ، یک الگوریتم برای استخراج مکرر مجموعه‌های مورد و یادگیری قوانین مرتبط با پایگاه‌های داده رابطه‌ای است. | ## بخش 1: الگوریتم آپریوری | با شناسایی موارد فردی مکرر در پایگاه داده و گسترش آنها به مجموعه اقلام بزرگتر و بزرگتر تا زمانی که آن مجموعه موارد به طور کافی در پایگاه داده ظاهر شود، ادامه می‌یابد. مجموعه‌های مکرر موارد تعیین شده توسط ایپرایوری می‌تواند برای تعیین قوانین ارتباطی که روندهای کلی در پایگاه داده را برجسته می‌کند، مورد استفاده قرار گیرد: این الگوریتم در حوزه‌هایی مانند تجزیه و تحلیل سبد بازار کاربرد دارد. با توجه به آستانه ، الگوریتم اپریوری مجموعه مواردی را که زیرمجموعه حداقل معاملات در پایگاه داده هستند، شناسایی می‌کند. الگوریتم تلاش می‌کند تا زیرمجموعه‌هایی از آیتم‌ها را که حداقل بین C مجموعه آیتم مشترک است، بیابد. آپریوری یک الگوریتم پایین به بالا است، آنگونه که در هر مرحله یک آیتم به زیرمجموعه‌های مکرر اضافه می‌شود (تولید کاندید). اپریوری از وسعت جستجوی اول و یک ساختار درخت Hash برای شمارش کارآمد مجموعه آیتم‌های نامزد استفاده می‌کند. با توجه به لمای بسته شدن رو به پایین، مجموعه کاندید شامل همه مجموعه‌های آیتم مکرر است. پس از آن، پایگاه داده معاملات را برای تعیین مجموعه موارد مکرر در بین نامزدها اسکن می‌کند. نماد نظری مجموعه‌ای معمولی استفاده می‌شود، اگر چه توجه داشته باشید که یک چند مجموعه است. در هر مرحله، فرض بر این است که الگوریتم مجموعه‌های نامزد را از مجموعه‌های بزرگ سطح قبلی ایجاد می‌کند و به لمای بسته شدن رو به پایین توجه می‌کند. | ## بخش 2: الگوریتم آپریوری | به فیلدی از ساختار داده دسترسی دارد که نشان دهنده مجموعه نامزد است، که در ابتدا صفر فرض می‌شود. بسیاری از جزئیات در زیر حذف شده است، معمولاً مهمترین بخش پیاده‌سازی ساختار داده‌ای است که برای ذخیره مجموعه‌های نامزد و شمارش فرکانس آنها استفاده می‌شود. سپس، کاندیدهایی که زیرالگوهای نادر (زیرالگوهایی که کم اتفاق می‌افتد) را هرس می‌کند. پس از آن، پایگاه داده تراکنشی را برای تعیین آیتم ست‌های مکرر ار بین کاندیدها، اسکن می‌کند. مثال‌ها مثال ۱ پایگاه داده زیر را در نظر بگیرید ، جایی که هر سطر یک تراکنش است و هر سلول یک مورد جداگانه از معامله است: آلفا بتا اپسیلون آلفا بتا تتا آلفا بتا اپسیلون آلفا بتا تتا قوانین ارتباطی که می توان از این پایگاه داده تعیین کرد به شرح زیر است: 100% مجموعه‌های دارای آلفا همچنین حاوی بتا است 50% مجموعه‌های دارای آلفا و بتا همچنین حاوی اپسیلون است 50% مجموعه‌های دارای آلفا و بتا همچنین حاوی تتا است ما همچنین می‌توانیم این را از طریق مثال‌های مختلف نشان دهیم. مثال ۲ فرض کنید یک سوپرمارکت بزرگ اطلاعات فروش واحد نگهداری سهام (SKU) را برای هر مورد پیگیری می‌کند: هر مورد، مانند "کره" یا "نان"، با SKU عددی مشخص می‌شود. این سوپرمارکت دارای پایگاه داده‌ای از معاملات است که در آن هر معامله مجموعه‌ای از SKU است که با هم خریداری شده‌اند اجازه دهید پایگاه داده معاملات شامل مجموعه های زیر باشد: مجموعه آیتم‌ها {1,2,3,4} {1,2,4} {1,2} {2,3,4} {2,3} {3,4} {2,4} ما از اپریوری برای تعیین مجموعه موارد مکرر این پایگاه داده استفاده خواهیم کرد. برای انجام این کار، ما می‌گوییم که یک مجموعه مورد مکرر است اگر حداقل در 3 تراکنش پایگاه داده ظاهر شود: مقدار 3 «آستانه پشتیبانی» است. اولین قدم اپریوری شمارش تعداد وقایع، به نام پشتیبانی ، از هر مورد عضو به طور جداگانه است. با اسکن پایگاه داده برای اولین بار، نتیجه زیر را بدست می‌آوریم آیتمپشتیبانی {1}3 {2}6 {3}4 {4}5 همه مجموعه های اندازه 1 دارای پشتیبانی حداقل 3 هستند، بنابراین همه آنها مکرر هستند. | ## بخش 3: الگوریتم آپریوری | به عنوان مثال، در مورد جفت {1،2}: جدول اول مثال ۲ موارد ۱ و ۲ را در سه مورد از مجموعه‌ها نشان می‌دهد. در حال حاضر، چون {1،3} و {1،4} مکرر نیستند، هر مجموعه بزرگتر که حاوی {1،3} یا {1،4} باشد نمی‌تواند مکرر باشد. به این ترتیب، ما می‌توانیم مجموعه‌ها را «هرس» کنیم: اکنون به دنبال سه‌گانه‌های مکرر در پایگاه داده هستیم، اما می‌توانیم همه سه‌گانه‌های حاوی یکی از این دو جفت را حذف کنیم: آیتمپشتیبانی {2,3,4}2 در مثال، هیچ سه قلو مکرر وجود ندارد. {2،3،4} زیر حداقل آستانه است و سایر سه قلوها حذف شدند زیرا آنها مجموعه‌های فوق العاده‌ای از جفت بودند که قبلاً زیر آستانه بودند. ما این مجموعه‌های مکرر موارد را در پایگاه داده تعیین می‌کنیم و نشان می‌دهیم که چگونه برخی از اقلام شمارش نشده‌اند؛ زیرا یکی از زیر مجموعه‌های آنها قبلاً زیر آستانه شناخته شده است. محدودیت‌ها اپریوری، در حالی که از نظر تاریخی قابل توجه است، از تعدادی ناکارآمدی یا جبران رنج می برد، که الگوریتم‌های دیگری را ایجاد کرده است. تولید نامزد، تعداد زیادی زیر مجموعه ایجاد می‌کند (الگوریتم سعی می‌کند مجموعه نامزد را با حداکثر زیر مجموعه‌های ممکن قبل از هر بار اسکن پایگاه داده بارگذاری کند). اکتشاف زیر مجموعه از بالا (اساساً اولین عرض از شبکه زیرمجموعه) هر زیرمجموعه S را تنها پس از همه زیرمجموعه‌های مناسب خود پیدا می‌کند. این الگوریتم پایگاه داده را بیش از حد اسکن می‌کند، که باعث کاهش عملکرد کلی می‌شود. | ## جمع‌بندی | همچنین، هم پیچیدگی زمانی و هم مکانی این الگوریتم بسیار زیاد است: ، بنابراین نمایی، جایی که عرض افقی (تعداد کل اقلام) موجود در پایگاه داده است.