پایان نامه ها

پایان نامه ارشد رایگان درمورد توسعه مدل

دانلود پایان نامه

عنوان u و افزایش مقدار k (k++)
اگر u در خصوص آیتم هدف i دارای نظر و امتیاز باشد پیمایش تصادفی متوقف میشود و نظر کاربر u در خصوص آیتمi (r_(u,i)) به عنوان جواب بازگردانده میشود.
در صورتیکه کاربر u در خصوص آیتمi دارای نظر و امتیاز نباشد دو حالت مختلف در نظر گرفته میشود:
5-1- با احتمال ∅_(u,i,k) پیماش شبکه متوقف شود و به صورت تصادفی یکی از آیتمهای شبیه آیتم i (مانند آیتمj ) که توسط u به آنها امتیازی داده شده است انتخاب گردد و r_(u,j) به عنوان جواب بازگردانده شود.
5-2- با احتمال 〖1-∅〗_(u,i,k) پیمایش شبکه ادامه پیدا کند و یکی از کاربران مورد اعتماد u مانند vبه صورت تصادفی انتخاب و این چرخه ادامه پیدا نماید.
با توجه به روند فوق ممکن است حالتی در شبکه وجود داشته باشد که این روند تا بینهایت ادامه پیدا کند که برای جلوگیری از این مطلب و عدم پیشروی بیش از حد در عمق شبکه، حداکثر عمق مجاز با توجه به ایده مطرح شده در [77] مقدار 6 در نظر گرفته شده است. بنابراین در صورتیکه مقدار متغیر k بزرگتر از 6 گردد اجرای روند متوقف شده و مقداری بازگردانده نخواهد شد که در پیادهسازی انجام شده توسط اینجانب مقدار بازگشتی 1- در نظر گرفته شده است.

4-2-3- انتخاب تصادفی یک کاربر

در صورتیکه در اجرای روند پیمایش تصادفی شبکه اعتماد، مقرر شد یکی از کاربران مورد اعتماد کاربر u به صورت تصادفی انتخاب گردد، با توجه به این نکته که در مدل TrustWalker مقدار رابطه اعتماد میان کاربران به صورت باینری (وجود یا عدم وجود اعتماد) در نظر گرفته شده است لذا احتمال انتخاب هریک از همسایگان مستقیم کاربر u از رابطه زیر محاسبه میگردد.
(15)
P(S_u=v)=t_(u,v)/(∑_(w∈TU_u)▒t_(u,w) )=1/|TU_u |

در این فرمول S_u یک متغیر تصادفی است که بر اساس مقدار آن یکی از همسایگان مستقیم u انتخاب میشود. به عنوان مثال، در صورتیکه تعداد همسایگان مستقیم کاربر u، 3 باشد در این صورت احتمال انتخاب هر یک از آنها 1/3 خواهد بود و با توجه به مقدار متغیر S_u می توان به صورت توزیع نرمال یکی از آنها را گزینش نمود یا به صورت تصادفی یک عدد صحیح در بازه ]5,1[ تولید و از طریق آن کاربر مورد نظر را انتخاب نمود.

4-2-4- انتخاب یک آیتم مشابه

در روند اجرای الگوریتم اگر مقرر گردد که با احتمال ∅_(u,i,k) در گره کاربر u توقف شود و یکی از آیتمهایی که توسط u به آنها امتیاز داده شده است و شبیه آیتم i نیز هستند انتخاب گردد باید معیار تشابهی میان آیتمها تعریف گردد و به ازای هر آیتم j∈〖RI〗_u (〖RI〗_u مجموعه آیتمهایی است که توسط کاربر u به آنها امتیازی تخصیص داده شده است) احتمال انتخابی متناسب با تشابه آن با آیتم i تعریف و در نظر گرفته شود. این مسئله در قالب فرمول شماره 16 بیان شده است.
(16)
P(Y_(u,i)=j)=(Sim(i,j))/(∑_(l∈〖RI〗_u)▒〖sim(i,l)〗)

با توجه به توزیع احتمال بیان شده در قالب فرمول فوق، احتمال انتخاب هر یک از آیتمهایی که توسط u به آنها امتیاز داده شده است بستگی به تشابه آنها با آیتم هدف i دارد و عددی در بازه ]1,0[ خواهد بود که مجموع تمامی آنها 1 خواهد بود. در فرمول فوق Y_(u,i) یک متغیر تصادفی در بازه ]1,0[ است که بر اساس مقدار آن و متناسب با احتمال انتخاب هر یک از آیتمهای مجموعه 〖RI〗_u یکی از آیتمها برگزیده خواهد شد.
نکته مهم: در روند اجرای الگوریتم لزوما آیتمی از مجموعه〖RI〗_u که دارای بیشترین تشابه با آیتم i باشد انتخاب نخواهد شد و کاملا به صورت تصادفی گزینش انجام میشود.

4-2-5- تشابه آیتم ها

در این مدل برای محاسبه تشابه آیتم ها با یکدیگر از فرمول پیرسون استفاده شده است که با توجه به علائم و نشانه های بکار رفته در مدل TrustWalker یک بار دیگر فرمول پیرسون در قالب فرمول زیر تعریف میگردد .
(17)
corr(i,j)=(∑_(u∈UC_(i,j))▒〖(r_(u,i)-r ̅_u)(r_(u,j)-r ̅_u)〗)/√(∑_(u∈UC_(i,j))▒〖〖(r_(u,i)-r ̅_u)〗^2 ∑_(u∈UC_(i,j))▒〖(r_(u,j)-r ̅_u)〗^2 〗)

مقادیر محاسبه شده از فرمول فوق در بازه ]1+,1-[ است. مقادیر منفی نشان دهنده این مطلب است که امتیازات تخصیصی به آیتم های i و j در تضاد با یکدیگر میباشد لذا در مدل TrustWalker این آیتمها سودمند نیستند و تنها آیتمهایی که دارای مقادیر مثبت باشند در نظر گرفته می شود.
در فرمول فوق UC_(i,j) مجموعه تمام کاربرانی می باشد که به صورت مشترک به دو آیتم i و j امتیاز داده اند و r ̅_u میانگین امتیازات کاربر u به آیتمهای مختلف می باشد. اندازه مجموعه UC_(i,j) نیز از اهمیت برخوردار است، به عنوان مثال در صورتیکه corr(i,j)=corr(i,m) اما اندازه مجموعه کاربرانی که به صورت مشترک به i و j امتیاز داده اند از اندازه مجموعه کاربرانی که به صورت مشترک به i و m امتیاز دادهاند بزرگتر باشد در این صورت ارتباط correlation میان آیتم i و j قویتر خواهد بود که نتیجه، تشابه بیشتر میان i و j به نسبت تشابه میان i و m خواهد بود. با توجه به مطالب فوق تشابه میان دو آیتم i و j در قالب فرمول زیر تعریف شده است.
(18)
sim(i,j)=1/(1+e^(-|〖UC〗_(i,j) |/2) )×corr(i,j)

مطلب مشابه :  منابع مقاله با موضوعکارکرد خانواده، خانواده گسترده، آموزش خانواده

در فرمول فوق از تابع سیگموید جهت کنترل عدم توجه بیش از حد، به اندازه مجموعه UC_(i,j) و نگه داشتن مقدار تابع تشابه در محدوده ]1,0[ استفاده شده است. در صورتیکه اندازه مجموعه UC_(i,j) به اندازه کافی بزرگ باشد در اینصورت مقدار تابع سیگموید به 1 همگرا خواهد شد اما برای مجموعه UC_(i,j) کوچک، مقدار تابع سیگموید 0.6 خواهد بود . مقدار عدد 2 در مخرج کسر توان e نیز به این جهت است که در صورتیکه اندازه مجموعه UC_(i,j) بزرگتر از 5 باشد مقدار بازگشتی تابع سیگموید عددی بزرگتر از 0.9گردد.

4-2-6- محاسبه احتمال ماندن در یک گره شبکه اعتماد (∅_(u,i,k))

در هر کاربر u از شبکه اعتماد به احتمال ∅_(u,i,k)، این امکان وجود دارد که پیمایش تصادفی متوقف گردد و یکی از آیتمهایی که توسط کاربر u به آنها امتیاز داده شده است و دارای تشابه با آیتم هدف i باشد در مرحله k از یک پیمایش تصادفی انتخاب گردد. این احتمال باید دارای رابطهای با تشابه آیتمهایی که توسط u به آنها امتیاز داده شده است و آیتم هدف i باشد. با توجه به این مطلب که مقدار تشابه دو آیتم مقداری اعشاری در محدوده ]1,0[ میباشد لذا می توان آنرا به عنوان احتمال نیز در نظر گرفت. در مدل TrustWalker حداکثر مقدار تشابه آیتمهایی که توسط u دارای امتیاز هستند با آیتم هدف i، به عنوان احتمال توقف در گره کاربر u در نظر گرفته شده است و علاوه بر آن با توجه به این نکته که هرچه در عمق شبکه اعتماد حرکت شود امتیازات و نظرات کاربران از صحت و اعتماد کمتری برخوردار خواهد بود بنابراین هرچه که در عمق شبکه حرکت شود احتمال ادامه پیمایش باید کاهش یابد و در نتیجه مقدار احتمال ∅_(u,i,k) افزایش پیدا کند. برای لحاظ نمودن فاکتور عمق k باید از تابعی کمک گرفته شود که برای مقادیر بالای k خروجی 1 را بازگشت دهد و برای مقادیر کوچک k مقدار اندکی را به عنوان خروجی بازگرداند که تابع سیگموید به خوبی می تواند این نیاز را برطرف نماید. با توجه به مطالب فوق تابع احتمال توقف در مرحله k از پیمایش تصادفی در کاربر u به جستجوی امتیاز آیتم هدف i به صورت زیر تعریف شده است.
(19)
∅_(u,i,k)=(_j∈RI_u^max) sim(i,j)×1/(1+e^(-k/2) )

4-2-7- چگونگی انجام پیشبینی امتیاز

در مدل TrustWalker در هر پیمایش تصادفی این احتمال وجود دارد که امتیاز تخصیصی توسط کاربران به آیتم هدف i و یا آیتمی شبیه آن به عنوان جواب بازگردانده شود بنابراین پیشبینی و تخمین امتیاز کاربر مبدا u به آیتم هدف i از تجمیع امتیازات حاصل از اجرای پیمایشهای تصادفی مختلف خواهد بود. این مطلب را می توان در قالب فرمول زیر بیان نمود.
(20)
r ̂_(u,i =∑_{(v,j)│R_(v,j) }▒〖P(XY_(u,i)=(v,j))*r_(v,j) 〗)

در فرمول فوق XY_(u,i) یک متغیر تصادفی برای تصمیمگیری در خصوص توقف پیمایش تصادفی در کاربر v و انتخاب آیتم j از میان آیتمهای امتیاز داده شده توسط v میباشد و P(XY_(u,i)=(v,j)) در واقع مقدار احتمال توقف در کاربر v و انتخاب آیتم j از میان آیتمهای امتیاز داده شده توسط v در شرایطی می باشد که پیمایش تصادفی از کاربر u و به دنبال امتیاز آیتم هدف i آغاز شده است. R_(v,j) نیز یک متغیر بولی است و نشان دهنده این مطلب است که آیا کاربر v دارای امتیاز و نظری برای آیتم j است. با توجه به توضیحات فوق می توان فرمول فوق را به صورت زیر تفسیر کرد:
“پیشبینی امتیاز کاربر مبدا u به آیتم هدف i، به صورت میانگین وزنی (بر اساس احتمال رخداد) امتیازات حاصل از پیمایش های تصادفی موفقی خواهد بود که امتیازی را به عنوان جواب بازگردانده اند.”
یا به عبارت دیگر:
“پیشبینی امتیاز کاربر مبدا u به آیتم هدف i به صورت مجموع حاصل ضرب امتیاز حاصل از یک پیمایش تصادفی موفق در احتمال وقوع و دستیابی به آن امتیاز میباشد.”

مطلب مشابه :  منابع پایان نامه ارشد با موضوععناصر داستان، ضرب المثل

4-2-8- چگونگی محاسبه احتمال P(XY_(u,i)=(v,j))

با توجه به تعریف و توضیح ارائه شده در بخش قبلی، چگونگی محاسبه مقدار احتمال P(XY_(u,i)=(v,j)) از طریق فرمول ترکیبی زیر محاسبه میگردد.
(21)

همان طور که در فرمول فوق قابل مشاهده است احتمال P(XY_(u,i)=(v,j)) از حاصل ضرب سه احتمال ∅_(u,i,k) و P(Y_(v,i)=j) و P(X_(u,i)=v) حاصل می گردد که هر کدام از آنها به تفصیل در بخشهای پیشین توضیح داده شده است .
نکته قابل ذکر در فرمول فوق این است که بجای ∅_(u,i,k) از ∅_(u,i) استفاده شده است زیرا تعداد مراحلی که باید طی شود تا به گره کاربر v دسترسی پیدا شود مشخص نیست، بنابراین از پارامتر k استفاده نشده است و به عبارت دیگر مقدار k=1 فرض شده است. نکته قابل ذکر دیگر این است که نمی توان حالتی را متصور بود که در آن v=u و i=j باشد چراکه در این حالت خود کاربر مبدا u برای آیتم هدف i دارای امتیاز است و دیگر اجرای الگوریتم معنا و مفهومی ندارد.

4-2-9- چگونگی محاسبه عملی r ̂_(u,i)

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

4-2-10- شرط اتمام کلی مدل

نتایج اجرای پیمایشهای تصادفی شبکه با شروع از کاربر مبدا u و به دنبال یافتن امتیاز آیتم هدف i در واقع جواب فرمول شماره 19 را تخمین می زنند و هرچه تعداد پیمایشهای تصادفی اجرا شده بیشتر باشد دقت بالاتری را به همراه خواهد داشت. نکته قابل تامل این است که چه تعداد پیمایش تصادفی باید اجرا گردد تا دقت مورد نظر را تامین کند. در مدل TrustWalker برای تعیین و حل این مسئله از واریانس کلیه نتایج حاصل از پیمایشهای تصادفی مختلف استفاده شده است.
(22)
σ^2=(∑_(i=1)^T▒〖(r_i-r ̅)〗^2 )/T

در این فرمول r_i نتیجه اجرای iمین پیمایش تصادفی است و r ̅ بیانگر میانگین پیمایشهای تصادفی اجرا شده است. T تعداد پیمایشهای تصادفی اجرا شده است، همچنین σ_i^2 به عنوان واریانس تعداد اولین i پیمایش تصادفی است که اجرا شده است، به عنوان م
ثال σ_5^2 بیانگر واریانس اولین 5 پیمایش تصادفی اجرا شده است. با توجه به این مطلب که نتایج در بازه ]5,1[ میباشد میتوان ثابت نمود95 که σ^2 به یک مقدار ثابت همگرا خواهد شد بنابراین اجرای مدل TrustWalker را میتوان با توجه به شرط زیر خاتمه داد.
(23)
|σ_(i+1)^2-σ_i^2 |≤ε

4-3- بهبود و توسعه مدل TrustWalker

جهت بهبود و توسعه این مدل، تکنیکها، راهکارها و مکانیزمهای مختلف و متفاوتی مورد بررسی و آزمایش قرار گرفت تا بتوان یکی یا تعدادی از حالتهای زیر را برآورده

دیدگاهتان را بنویسید