احمدرضا رستمانی
احمدرضا رستمانی
خواندن ۳ دقیقه·۳ سال پیش

کاوش مجموعه آیتم‌های سودمند HUIM

یکی از مسائل مطرح در حوزه داده‌کاوی، مسئله Frequent Itemset mining یا همان کاوش مجموعه آیتم‌های پرتکرار است. هدف از این مسئله، یافتن مجموعه آیتم‌هایی است که در یک پایگاه داده، بیش از یک آستانه تعریف شده تکرار شده باشند. یکی از کاربردهای عمده این مسئله در فروشگاه‌ها و تحلیل سبدهای خرید مشتریان است. به عنوان مثال، یافتن مجموعه‌ای از کالاهای موجود در بیش از تعداد مشخصی از سبدهای خرید، این امکان را برای فروشندگان فراهم کرده تا با پیشنهاد کردن این کالاها در کنار هم به مشتریان، میزان فروش آن‌ها را افزایش داده و به سود بیشتری دست یابند. اما در این مسئله، به میزان سودی که از فروش این مجموعه کالاها حاصل می‌گردد، توجهی نمی‌شود و ممکن است یک مجموعه پرتکرار، فاقد سود مناسبی برای فروشگاه باشد و یا مجموعه ای از کالاها که سود مناسبی را برای فروشگاه رقم زده‌اند، به عنوان مجموعه پرتکرار شناسایی نشوند.

در مسئله High utility itemset mining یا کاوش مجموعه آیتم‌های پرسود که به کاوش مجموعه آیتم‌های با سودمندی بیشتر از آستانه تعریف شده می‌پردازد، تلاش شده تا راه حل مناسبی برای این چالش پیشنهاد شود. در سال های اخیر الگوریتم های متعددی برای این مسئله پیشنهاد شده و مورد پیاده‌سازی قرار گرفته‌اند. عمده این الگوریتم‌ها، در ابتدا مجموعه‌هایی را به عنوان مجموعه آیتم‌های پرسود کاندید ایجاد می‌کنند و سپس با محاسبه میزان سود دقیق این مجموعه‌ها، اقدام به شناسایی مجموعه آیتم‌های پرسود می‌نمایند. این رویکرد عموما دارای 2 مشکل اساسی است:

  • مصرف زیاد حافظه برای ذخیره‌سازی مجموعه آیتم‌های پرسود کاندید
  • زمان اجرای بسیار بالا برای ایجاد و سپس محاسبه سود دقیق مجموعه آیتم‌های کاندید

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

برای حل این چالش‌ها، الگوریتم‌های TKU و TKO پیشنهاد شده‌اند. در این الگوریتم‌ها دیگر نیازی به تعیین آستانه سودمندی نبوده و صرفا با مشخص کردن تعداد مجموعه آیتم‌های سودمند مطلوب، میزان آستانه سودمندی توسط خود الگوریتم مرحله به مرحله افزایش یافته و مجموعه آیتم‌های سودمند مورد شناسایی قرار می‌گیرند. افزایش بهینه و سریع میزان آستانه سودمندی به گونه‌ای که بدون از دست دادن هیچ مجموعه آیتم پرسودی، در سریع‌ترین زمان ممکن مجموعه آیتم های پرسود مورد شناسایی قرار گیرند؛ و همچنین هرس و محدودسازی فضای جست و جو، از ویژگی‌های اصلی و اساسی این الگوریتم‌ها به شمار می‌رود. آن‎چه این الگوریتم‌ها را از یکدیگر متمایز می‌سازد، ساختمان‌ داده‌های به کار رفته در پیاده‌سازی آن‌ها و نیز رویکردهای مورد استفاده برای هرس فضای جست و جو و افزایش سریع‌ و بهینه میزان آستانه سودمندی می‌باشد.

نتایج اجرای این دو الگوریتم روی مجموعه داده های مختف نشان می‌دهد که در مجموعه داده های dense، دو الگوریتم عملکرد تقریبا یکسانی دارند. اما در مجموعه داده های sparse الگوریتم TKO به مراتب عملکرد بهتری دارد.

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





داده‌کاویدیتا ماینینگ
شاید از این پست‌ها خوشتان بیاید