ارائه یک سیستم توصیه‌گر در وب بر اساس فرآیند مارکوف وزن‌دار

پیاده سازی این مقاله آماده است و به منظور دریافت متن کامل مقاله و پیاده سازی آن در صورت تمایل به Research.moghimi@gmail.com ایمیل بزنید یا با آی دی تلگرام Research_moghimi@ از طریق تلگرام در ارتباط باشید

این مقاله توسط یکی از مشتریان سایت که بنده به ایشون در انجام پایان نامه کمک کردم منتشر شده است

ارائه یک سیستم توصیه‌گر در وب بر اساس فرآیند مارکوف وزن‌دار

معصومه شریعتی، علی هارون آبادی۲

۱٫ دانشجوی کارشناسی ارشد دانشگاه آزاد اسلامی واحد علوم تحقیقات- تبریز

۲٫ عضو هیئت علمی دانشگاه آزاد اسلامی واحد تهران شمال- تهران

چکیده

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

کلمات کلیدی: مدل مارکوف، مدل مارکوف همه مراتب، خوشه‌بندی

 

  1. مقدمه

در فرآیند پیش بینی صفحات وب تلاش می‌شود مجموعه بعدی از صفحات وب را که کاربر ممکن است ملاقات کند بر اساس دانش به دست آمده ازصفحات ملاقات شده قبلی به دست آوریم. [۱۲] وسعت شبکه جهانی وب همراه با تغییر در الگوهای پیمایشی کاربران باعث می شود مشکل مدل سازی دنباله ای بسیار دشوار شود [۱۱]. از طرفی داده‌کاوی[۱] به عنوان تکنیکی  جهت استخراج اطلاعات نهان یا الگوها و روابط مشخص، در حجم زیادی از داده‌ها در یک یا چند بانک اطلاعاتی، مورد توجه است.

روش های کاوش وب  با استفاده از تکنیک‌های داده‌کاوی در سه حوزه ساختار کاوی وب[۲]، محتوی‌کاوی وب[۳] و کاربردکاوی وب[۴] به کاوش و کشف دانش از داده‌های مربوط به وب می‌پردازد. ساختار کاوی وب عبارت است از کاوش ساختار وب به منظور طبقه‌بندی صفحات وب، اندازه‌گیری شباهت‌ها و روابط بین وب‌سایت‌های مختلف. محتوی‌کاوی وب عبارت است از کاوش متن، تصویر، صدا، فیلم، ابرداده و … به منظور استخراج مفاهیم و قوانین مهم و خلاصه کردن محتوی وب. کاربردکاوی وب فرآیند به کاربردن تکنیک‌های داده‌‌کاوی به منظور کشف الگو‌های استفاده از لاگ فایل وب است تا رفتار کاربران وب شناسایی شود. در کاربردکاوی وب سه وظیفه اصلی پیش‌پردازش، کشف الگو و تجزیه و تحلیل الگوهای کشف شده انجام می شود. در مرحله پیش‌پردازش، اطلاعات غیرضروری از لاگ فایل وب حذف و بعد از آن نشست‌های کاربران شناسایی می‌شوند. سپس با استفاده از روش‌ها و الگوریتم‌های داده‌کاوی مانند الگوریتم‌های تجزیه و تحلیل مسیر، قوانین انجمنی، خوشه بندی و الگو‌های ترتیبی اطلاعات مفید و جدید کشف می‌شود. در مرحله تجزیه و تحلیل الگو، الگو‌های کشف شده مورد بررسی قرار می‌گیرند و بهترین الگو با توجه به کارایی پیش‌بینی آن  برای ارائه پیشنهاد به کاربر استفاده می شود.

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

  1. تاریخچه

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

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

در [۱]  به نوشته ها مراجعه شود

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

[۳] مقاله ۲ بدون خوشه بندی- مقایسه با مدل مارکوف معمولی و مدل مارکوف هرس شده(مارکوف و قوانین انجمنی)

[۸] یک مدل ترکیبی برای پیش بینی ارائه کرده است که مبتنی بر قانون Dempster می باشد و برای ترکیب احتمالات به دست آمده با استفاده از ANN و مدل های مارکوف به عنوان بدنه های احتمالات، در نظر گرفته شده است. ANN یک روش طبقه بندی بسیار قدرتمند است که در بسیاری کاربردها و حوزه ها استفاده می شود. در این مقاله  یک شبکه دو لایه به کار گرفته شده است که هر یک از دو مدل مارکوف و  ANN به طور جداگانه در یک لایه استفاده می شوند. در مرحله آموزش از الگوریتم پس انتشار استفاده می کند. مدل ارائه شده با هر یک از مدل های مارکوف، ANN و قوانین انجمنی مقایسه شده است و همواره صحت بهتری را نشان داده است. همچنین ترکیب ANN با مدل مارکوف همه مراتب صحت بالاتری را به دست آورده است.

[۲] یک مدل ترکیبی شامل سه مدل خوشه بندی، مارکوف و قوانین انجمنی ارائه کرده است.  به منظور کاهش تعداد تراکنش های انجام شده (transations used) ابتدا کل نشست ها با توجه به اندازه ویژگی  انتخاب شده به مجموعه هایی تقسیم و پس از آن هر مجموعه با استفاده از الگوریتم کامیانه و اندازه فاصله کسینوسی خوشه بندی می‌شود. مدل مارکوف مرتبه دو برای پیش‌بینی نتایج روی خوشه‌ها اعمال می گردد. زمانی که مدل مارکوف نتواند تصمیم بگیرد، از قوانین انجمنی برای ارائه پیشنهاد به کاربر استفاده خواهد شد. مدل ارائه شده از نظر صحت و پیچیدگی فضای حالت از مدل مارکوف معمولی، قوانین انجمنی و مدل ترکیبی مبتنی بر مدل مارکوف وقوانین انجمنی بهتر است.

در [۱۰] مانند [۲] از سه روش خوشه‌بندی، مدل مارکوف و قوانین انجمنی به منظور به دست‌آوردن صحت پیش‌بینی بهتر استفاده شد با این تفاوت که ابتدا کشف الگو از داده‌ها به وسیله الگوریتم Apriori با قوانین انجمنی روی نشست‌های وب اعمال شده و پس از آن خوشه‌بندی به صورت زیر انجام می‌شود: شباهت بین انتقال‌ها جستجو شده و k نزدیکترین مقدار اول که شباهت بیشتری به مقدار آستانه دارند شناسایی می‌شوند. سپس الگوریتم خوشه‌بندی کامیانه برای خوشه‌بندی داده‌های انتخاب شده اعمال می‌شود. هنگام ورود نشست تست به سیستم نزدیکترین خوشه به نشست تست پیدا شده و مدل مارکوف برای یافتن حالت‌هایی برای تست نشست از خوشه مربوط به آن پیاده می‌شود. صفحه با بیشترین احتمال به عنوان صفحه پیش‌بینی انتخاب می‌شود. روش پیشنهادی نسبت به مدل مارکوف سنتی کارایی بهتری دارد و صحت پیش‌بینی در آن بهبود یافته است.

در [۷] به تجزیه و تحلیل و بررسی مدل مارکوف و مدل مارکوف همه مراتب پرداخته و یک مدل مارکوف اصلاح شده برای ارزیابی موضوع مقیاس‌پذیری در تعداد مسیرها پیشنهاد شده است. به عنوان نمونه S1=(P1,P2) و S2=(P2,P1) دو نشست متفاوت با احتمال پیش‌بینی متفاوت هستند. در مدل پیشنهاد شده همه نشست‌هایی که شامل صفحات مشابه ولی با ترتیب‌های مختلف هستند یکسان در نظر گرفته شده‌اند. دلیل این کار این است که یک وظیفه روی وب می‌تواند با استفاده از مسیرهای مختلف بدون در نظر‌ گرفتن ترتیبی که کاربران انتخاب می‌کنند، انجام شود. به این ترتیب اندازه مدل پیش‌بینی کاهش می‌یابد و علاوه بر آن در مراتب بالاتر مدل مارکوف همه مراتب، صحت نیز افزایش می‌یابد.

مدل پیشنهاد شده در [۹] در دو فاز آفلاین و آنلاین کار می‌کند. فاز آفلاین در سرور و فاز آنلاین در سرور و کلاینت اجرا می‌شود. در فاز آفلاین داده‌ها خوشه‌بندی می‌شوند و سپس در فاز آنلاین نشست جاری به نزدیکترین خوشه تعلق می‌گیرید و صفحات بعدی به او پیشنهاد می‌شود. خوشه‌بندی با استفاده از الگوریتم کامیانه اصلاح شده انجام شده. اندازه فاصله استفاده شده برای محاسبه شباهت بین خوشه‌ها با استفاده از متدهای فاصله SAM و SABDM است. متد SAM الگوهای پیمایش را بر اساس ترتیب صفحات درخواست شده بوسیله کاربر پارتیشن‌بندی می‌کند. صفحات یکسان از یک جفت نشست دوباره مرتب می‌شوند تا با یکدیگر تراز شوند و صفحات منحصربفرد درج یا حذف می‌شوند به طوری که هر دو نشست دقیقا شبیه یکدیگر شوند. تعداد عملیات درج و حذف و مرتب سازی برای محاسبه فاصله بین جفت سشن ها استفاده می شود. متد SABDM  یک روش اندازه گیری فاصله بر اساس توالی را ارائه می دهد که در آن فاصله بین دو نشست بر اساس تعداد هم ترازی های انجام شده برای صفحات دو نشست مورد مقایسه به دست می آید.

در [۱۴] از ترکیب تکنیک خوشه‌بندی و مدل مارکوف استفاده شده است. به این صورت که ابتدا کل داده‌ها خوشه‌بندی شده‌اند و سپس مدل مارکوف مرتبه پایین روی هر خوشه اعمال شده است. توجه به ویژگی‌های داده‌ها و گروه‌بندی آنها بر اساس این ویژگی‌ها قبل از خوشه‌بندی پیچیدگی فضای حالت را کاهش می‌شود و خوشه‌بندی را ساده‌تر می‌کند. با این حال انتخاب نامناسب ویژگی‌ها صرف‌نظر از نوع الگوریتم خوشه‌بندی که استفاده می‌شود، می تواند منجر به خوشه‌‌های اشتباه شود[۱۵]. بر این اساس در روش پیشنهاد شده ابتدا نشست‌ها بر اساس معیار تعداد دفعات مشاهده صفحات که به عنوان وزن آنها در نظر گرفته شده، در چند مجموعه قرار می‌گیرند. در مرحله بعد و قبل از انجام خوشه‌بندی، تعداد خوشه‌ها و مناسب‌ترین فاصله اندازه‌گیری برای همه دیتاست‌های مورد آزمایش ارزیابی شد و فاصله کسینوسی برای استفاده در الگوریتم خوشه‌بندی انتخاب شد. روش پیشنهاد شده صحت بهتری را نسبت به مدل مارکوف مرتبه پایین و همیچنین مدل مارکوف مرتبه بالا نشان می‌دهد.

۲ Comments

Add a Comment

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


پاسخ من را به ایمیلم ارسال کن

مشاوره می خواهید؟ ما همیشه آنلاین هستیم. در هر حوزه ای در تلگرام یا واتس آپ با شماره تلفن 09367938018 ارتباط بگیرید
+