آوریل 23, 2021

جستجوی مقالات فارسی – ضرورت وجود سیستم های فروش آنلاین- قسمت ۴

1 min read

شکل ۲-۴ : نمایش پیشامد بازدید
شکل ۳-۴ : پیشامد بازدید برای یک کاربرخاص در حالت کلی
با توجه به تعاریف ارائه شده ، بدیهی است که همواره متغیر L بزرگتر از ۲ میباشد و همچنین برای مدل سازی تابع هدف ، پیشامد کلی شکل ۳-۴ را برای یک کاربر خاص در نظر گرفته و رابطه احتمالی آن را مینویسیم:
با توجه به رابطه احتمالی به دست آمده ، هدف ما یافتن مقدارهایی برای متغیر تصادفی K به گونه ای است که احتمال کل یا همان P(A) حداکثر شود.
۴٫۲٫۲٫۲- مدل ریاضی پیش بینی مسیر حرکت یک کاربر
در ادامه برای یافتن max{k1,k2,….,kl}P(K) با استفاده از برنامه ریزی صفر و یک ، ابتدا تابع هدف P(K) را که با استفاده از مدل زنجیره مارکوف درجه ۱ مدل سازی میشود ، با به کار گیری تبدیل مناسب به تابع هدف روش برنامه ریزی صفر و یک تبدیل میکنیم. سپس محدودیتهای این مدل برنامه ریزی را نوشته و مدل نهایی را میابیم.
۴٫۲٫۲٫۳- مدل سازی تابع هدف برنامه ریزی صفر و یک
فرض کنید وب سایت ما ۱۰ صفحه متمایز دارد. مسیر حرکت موجه در شکل زیر نمایش داده شده است. در این پیشامد فردی در یک بار بازدید خود از وب سایت ابتدا وارد سایت شده و صفحه ۲ را به عنوان اولین صفحه مشاهده میکند. سپس به ترتیب صفحات ۷و۲و۷و۴ را دیده و از سایت خارج میشود. مسیر و گراف حرکت این کاربر معادل شکل ۴-۴ میباشد.
شکل ۴-۴ : مسیر و گراف حرکت کاربری با ترتیب صفحات ۲و۷و۲و۷و۴
برای مدل سازی تابع هدف این مساله با فرض اینکه پارامتر n برابر تعداد صفحات وب سایت باشد ، متغیر عدد صحیح xij را برابر با تعداد دفعات حرکت کاربر از صفحه i به صفحه j تعریف میکنیم . بنابر این در مثال فوق داریم :
X02=1 , x27=2 , x72=1 , x74=1 , x40=1
For all other i,j xij=0
به این ترتیب ابتدا به نظر میرسد که مسئله ما یک مساله برنامه ریزی عدد صحیح میباشد . اما یک ویژگی بسیار مهم در مدلهای مارکوفی درجه ۱ ، مدل ما را به یک مدل برنامه ریزی صفر و یک تبدیل میکند. ویژگی مذکور به شرح زیر است :
در مدل مارکوف درجه ۱ ، هر مسیر دارای گره تکراری به جز گره صفر قابل تبدیل به مسیر بدون گره تکراری بجز گره صفر با مقدار تابع هدف بیشتر میباشد.
شکل ۵-۴ : پیشامد بازدید عمومی S که دارای حداقل یک گره تکراری k است.
برای اثبات این ادعا شکل ۵-۴ را در نظر بگیرید که پیشامد بازدید عمومی S را که حداقل دارای یک گره تکراری k است ، نشان میدهد. این پیشامد بازدید عمومی را میتوان به سه بخش اصلی افراز کرد. بخش A که در برگیرنده توالی صفحات طی شده در این پیشامد از ابتدا تا قبل از اولین گره k است. بخش B که در بر گیرنده خود دو تکرار گره k و تمامی گره های بین این دو تکرار است و در نهایت بخش c که در بر گیرنده توالی صفحات مشاهده شده بعد از دومین گره k تا انتهای این پیشامد بازدید عمومی است. احتمال رخ دادن پیشامد عمومی S به شرح زیر است.
حال اگر قسمت B را که در بر گیرنده هر دو گره تکراری و کلیه گره های بین آنهاست از پیشامد عمومی S حذف کرده و فقط یک گره k را جایگزین آن کنیم پیشامد حاصل میشود که در شکل ۶-۳ نمایش داده شده است :
شکل ۶-۴: مشاهده جریان حرکتی کاربر
با توجه به این مطلب که احتمال همواره مقداری بین صفر و یک دارد ، داریم :
پس میتوان نتیجه گرفت که همواره > است.
همانطوری که دیدیم با حذف دو گره تکراری و تمامی گره های بین آنها و جایگزینی یک گره از همان نوع به جای آنها پیشامدی با احتمال وقوع بیشتر حاصل شد. حال اگر به ازای تمامی گره های تکراری این پیشامد ، این کار را انجام دهیم در نهایت یک پیشامد بازدید بدون گره تکراری با مقدار احتمال وقوع بیشتری نسبت به تمام پیشامدهای قبلی حاصل میشود و ویژگی مذکور به اثبات رسیده است.
با توجه به ویژگی مذکور در میابیم که جوابها با xij های بزرگتر از یک گرچه ممکن است موجه باشند اما هرگز بهینه نیستند. بنابر این برای یافتن جواب بهینه مسئله برنامه ریزی عدد صحیح قبلی کافی است جواب مسئله برنامه ریزی صفر و یک جدید را یافت چرا که جواب بهینه مسئله برنامه ریزی صفر و یک جدید قطعا جواب بهینه مسئله برنامه ریزی عدد صحیح قبل هم میباشد.
در این حالت متغیر جدید xij در صورتی که کاربر از صفحه i به j رفته باشد برابر ۱ و در غیر این صورت برابر ۰ خواهد بود. برای محاسبه تابع هدف P(K) برای این پیشامد جدید با استفاده از مدل زنجیره مارکوف درجه ۱ داریم.
P(K)= P(K1=0, K2=2, K3=7, K4=4, K5=0)=P|k
با استفاده از مدل زنجیره مارکوف درجه ۱ احتمال پیشامد بالا برابر است با :
P|k=P(0|4)p(4|7)P(7|2)P(2|0) =>
ln P|k=ln(p(0|4))+ln(P(4|7))+ln(P(7|2))+ln(P(2|0)) =>
ln P|k=x40 ln(f(0|4)) + x74ln(f(4|7)) + x27ln (f(7|2)) + x02 ln(f(2|0))
بنابر این در حالت کلی برای هر توالی ممکن (موجه) از صفحات بازدید شده میتوان تابع هدف صفر و یک زیر را تعریف نمود :
لازم به ذکر است که در اینجا منظور از f(j|i) ، درایه واقع در سطر i ام و ستون j ام ماتریس انتقال مدل مارکوف درجه یک برای کاربر مورد نظر است که برابر احتمال رفتن از صفحه i ام به صفحه j ام میباشد و با ساتفاده از فراوانی نسبی حرکت کاربر از صفحه iام به صفحه jام نسبت به کل حرکات او در لاگ فایلهای سرور مورد نظر محاسبه میشود.
مدل سازی محدودیتهای برنامه ریزی صفر و یک
با در نظر گرفتن گراف مسیر طی شده در مثال قبل میتوان کلیه محدودیتهای این مساله برنامه ریزی صفر و یک را به این صورت بیان نمود :
در هیچ یک از مسیرهای بازدید موجه این مساله ، یک صفحه خاص چند بار پشت سر هم بلافاصله مشاهده نمیشود. در واقع تکرار چند بار پشت سر هم و بلافاصله یک صفحه خاص در یک مشاهده بازدید را یک بار مشاهده آن در نظر میگیریم . در واقع در گراف مسیر بازدید ، لوپ (حلقه) به طول صفر نداریم (شکل ۷-۳). در واقع داریم : xij=0 if i=j
در طول مسیر بازدید به هر گره ای که وارد میشویم باید بتوانیم از آن خارج شویم :
هر پیشامد مسیر بازدید از گره مجازی صفر شروع و به آن هم ختم میشود :
محدودیت زیر که همان محدودیت شروع از گره مجازی صفر است ، خود به خود و با در نظر گرفتن محدودیتهای ۲ و۳ با هم همواره برقرار میباشد.
در هیچ یک از مسیرهای موجه برای این مساله برنامه ریزی صفر و یک مسیر بدون گره صفر نداریم.
محدودیت حذف کلیه جواب ها با گره های تکراری به شرح زیر است
Yi={0,1} for all i
در نهایت کلیه متغیرهای Xijاز نوع عدد صفر و یک میباشند

دانلود متن کامل پایان نامه در سایت jemo.ir موجود است

Copyright © All rights reserved. | Newsphere by AF themes.