sl

شکل۲‑۱۰- مثال مقادیر پاداش در الگوریتم Q-Learning
اگر عامل از حالت sl شروع کرده و به سمت راست حرکت کند مقدار جدید Q برابر است با:
رابطه ۲-۴

۱۰۰
۹۰
۸۱
۶۶
شکل۲‑۱۱ – مثال از حرکت در حالتهای مختلف- Q-learning

اپیزود‌های یادگیری

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

آزمون کای

آزمون خی‌دو[۸۸] یا آزمون کی دو یا خی دو یا مربع کای یا χ² از آزمون‌های آماری و از نوع ناپارامتری است و برای ارزیابی همقوارگی متغیرهای اسمی‌به کار می‌رود:
رابطه ۲-۵
که در آن:
O : فراوانیهای مشاهده شده
E : فراوانیهای مورد انتظار
آزمون بدون توزیع است. فراوانی‌های مورد انتظار نباید در هیچ مقوله‌ای صفر باشد. مجموع مقوله‌هایی که مقدار مشاهدات مربوط به آنها کمتر از ۵ است، نباید بیش از ۲۰ درصد کل مقوله‌ها باشد. این آزمون تنها راه حل موجود برای آزمون همقوارگی در مورد متغیرهای مقیاس اسمی‌ با بیش از دو مقوله‌ است، بنابراین کاربرد بیشتری نسبت به آزمونهای دیگر دارد. این آزمون نسبت به حجم نمونه حساس است.[۲۸]

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

معیار دقت [۸۹] و معیار بازخوانی[۹۰]

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

معیارهای ارزیابی

معیار دقت: به حاصل تقسیم «تعداد مستندات بازیابی شده‌ی واقعاً مرتبط» بر «تعداد کل مستندات بازیابی شده» گفته می‌شود.[۲۹]
معیار بازخوانی: به حاصل تقسیم «تعداد مستندات بازیابی شده‌ی مرتبط» بر «تعداد کل مستندات باربط مرتبطی که در مجموعه‌ی اطلاعاتی موجود بوده است» گفته می‌شود.[۲۹]

شکل۲‑۱۲- معیار دقت و معیار بازخوانی [۴۵]

فصل سوم

روش‌شناسی تحقیق

مقدمه

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

مدل ارائه‌شده

با توجه به تاثیرات الگوریتم‌های هوش جمعی و توانایی منحصر به فرد آنها در حل مسئله، در این پژوهش یک روش محاسباتی برمبنای مدل مبتنی بر آموزش ، برای پیش‌بینی رفتار آتی یک اجتماع، پس از مشاهده‌ی رفتار آنها در دوره‌ی آموزش الگوریتم، معرفی می‌کنیم. اجتماع انتخاب شده به عنوان منبع داده‌های مسئله، وبلاگ‌های اینترنتی است. از آنجا که در مدل‌های مبتنی بر آزمایش طول دوره‌ی آموزش باید معقول باشد، می‌توان با کمک استخراج داده‌های توصیف‌گر از وبلاگ‌ها، زمان آموزش بر مبنای این داده‌ها را از مرتبه‌ی چندجمله‌ای نگاه داشت که این از مزایای انتخاب وبلاگ به عنوان منبع داده است.
همچنین از میان الگوریتم‌های مبتنی بر هوش جمعی الگوریتم،‌ PSO نتایج بهتری در خوشه‌بندی داده‌ها هم از نظر سرعت و هم از نظر دقت داشته [۲۴] ، و هم‌چنین کیفیت راه‌حل و نرخ موفقیت PSO نسبت به دیگر الگوریتم‌های هوش مصنوعی نیز بالاتر بوده است [۲۵] . البته در [۲۵] ، PSO با کلونی مورچه[۹۳] هم مقایسه شده و دقت و نرخ موفقیت بیشتری داشته اما سرعت آن کمی‌کمتر از کلونی مورچه بوده، این درحالی است که دقت کلونی مورچه بسیار کمتر PSO نشان داده شده است. (حدود ۱/۳ دقت PSO). با توجه به بررسی این نتایج و همچنین کمرنگ بودن تحقیقات با بهره گرفتن از الگوریتم PSO در این حوزه، در این پژوهش قصد داریم با بهره گرفتن از الگوریتم PSO به حل مسئله بپردازیم.
در این راه تاکید ما بر نحوه‌ی تاثیر الگوریتم بر حل مسئله ( و در عین حال مشاهده‌ی رفتار گروهی یک اجتماع در یک دوره‌ی زمانی کوتاه) است و همچنین اینکه چگونه این الگوریتم یک مدل مناسب از انتخاب‌های فردی و تصمیمات جمعی ارائه می‌دهد. برای این منظور به بحث پیرامون مسائل محاسباتی در آموزش، برای مدل کردن رفتار جمعی مشاهده‌شده در وبلاگ‌‌ها، با بهره گرفتن از الگوریتم‌های هوش جمعی (PSO به طور خاص) می‌پردازیم و یک فرایند انتقال را از مجموعه‌ی داده‌ی وبلاگ‌ها به مجموعه‌ی داده‌های PSO معرفی می‌کنیم و بر اساس اصول PSO یک سناریوی آموزش طراحی می‌کنیم. سپس در ادامه با بهره گرفتن از یک روش‌ تجربی خاص به مشاهده و ارزیابی مدل ارائه شده روی مجموعه داده‌های وبلاگ می‌پردازیم و سعی می‌کنیم این مشاهدات را با بهره گرفتن از آزمون‌های آماری مناسب ارزیابی کنیم تا بتوانیم به نمایش کمی‌از میزان رده‌بندی دست بیابیم و در نهایت به انتخاب بهینه‌ پارامترهای PSO بر مبنای خط مشی‌های تجربی می‌پردازیم. به منظور پاسخ‌دادن به سوالات اساسی این پژوهش که در فصل اول به آن اشاره شد مدلی ارائه می‌دهیم که این فصل به شرح و توضیح بخش‌های مختلف آن خواهد پرداخت. این مدل شامل جنبه‌های مختلف فرایندی است که در آن گرایش عمومی‌بلاگستان کشف می‌شود و در صورت موفقیت در این امر به پیش‌بینی گرایش‌های آتی خواهد پرداخت. این مدل شامل سه نما[۹۴] می‌باشد.
نمای منطقی[۹۵] که به شرح الگوریتم و منطق اجرای قدم‌های مختلف فرایند می‌پردازد و در آن مشخص می‌شود که ورودی‌های سیستم با چه روالی تبدیل به خروجی می‌شوند. در این نما به جزئیات اینکه داده‌ها از چه نوعی هستند و چگونه منتقل می‌شوند پرداخته نمی‌شود اما اینکه در هر مرحله از الگوریتم داده‌ها دارای چه ساختاری هستند و با چه روالی تحلیل می‌شوند بیان می‌شوند.
نمای داده[۹۶] که در آن به معرفی مجموعه‌ی‌ داده‌های مورد استفاده، نحوه‌ی جمع‌ آوری داده، روش قابل دسترس کردن[۹۷] داده‌های برای الگوریتم، فهرست کردن داده‌های توصیف‌گر[۹۸] پرداخته می‌شود. این نما برخلاف نمای منطقی به چگونگی انجام عملیات روی داده‌ها نمی‌پردازد و تنها به مدل کردن داده و جریان داده اکتفا می‌کند.
نمای سوم نمای مولفه‌ای[۹۹] است که در آن مولفه‌های نرم افزاری و محل استقرار[۱۰۰] آنها مشخص می‌شود. با توجه به اینکه مدل ارائه شده در این پژوهش روی سیستم‌های توزیع‌شده مستقر می‌شود، و اصولا این مدل تعیین گرایش در بلاگستان را با نگاه به سیستم‌های توزیع‌شده حل می‌کند، نگرانی‌هایی که پیرامون مقیاس‌پذیری در سیستم‌های توزیع‌شده وجود دارد با نمای مولفه‌ای واضح‌تر پاسخ داده می‌شود.

نمای منطقی

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

مسائل اساسی PSO

در فصل دوم با الگوریتم PSO و نحوه‌ی کارکرد آن آشنا شدید. در این الگوریتم برای آنکه ذرات[۱۰۱] بتوانند همراه با Swarm به سمت نقطه‌ی بهینه حرکت کنند باید پیش از اجرای الگوریتم با یکدیگر از نظر مقدار داده‌ای هم‌تراز[۱۰۲] شوند. این عمل در واقع در گام initialization رخ می‌دهد.
قبل از این اشاره کردیم که اگرچه دقت الگوریتم PSO 3 برابر الگوریتم کلونی مورچه است اما کارایی آن کمتر است و یکی از مسائلی که باعث کاهش کارایی الگوریتم PSO می‌شود همین مسئله Initialization است [۲۵].
الگوریتم‌هایی مانند کلونی مورچه و PSO ، برای یافتن مقادیر بهینه در فضاهای نمونه‌ی بزرگ طراحی شده‌اند، که پیمایش کل فضای حالت با الگوریتم‌های سنتی زمان‌بر است. همچنین مقادیر بهینه‌ای که این الگوریتم‌ها تولید می‌کنند برای یک مجموعه‌ی داده‌ای خاص است و اگر مجموعه‌ی داده‌ای تغییر کند باید مقدار بهینه مجدد محاسبه گردد.

شکل۳‑۱- محاسبه‌ی مقدار بهینه به طور مداوم
در چنین شرایطی (شکل ۳-۱) چون الگوریتم به تعداد بسیاز زیاد (و احتمالا برای حجم داده زیاد ) فراخوانی می‌شود، بسیار مهم است که گامهای الگوریتم چگونه طراحی شوند و در حد امکان کارهای تکراری حذف شده و گام‌های پیچیده‌ی الگوریتم که توان محاسباتی زیادی نیاز دارند حتی‌الامکان ساده شوند. در الگوریتم PSO گامی‌که مربوط بهinitialize کردن ذرات است بدون توجه به باقی گامهای الگوریتم هر بار برای همه‌ی داده‌ها اجرا می‌شود.
از طرفی یکسان کردن ذرات در ابتدای الگوریتم، نیازی اساسی برای ایجاد شرایط قابل پیش‌بینی در فضای حالت مسئله است. اساسا در الگوریتم PSO پارامترهای ثابت r1 و r2 که به شکل تصادفی باید انتخاب شوند برای حالتی تولید شده‌اند که در آن ذرات در گام اول initialize شده‌اند و پیدا کردن مجدد این پارامترها، برای تولید حالت بهینه، به ازای مقادیر مختلف ذرات بسیار پرهزینه است. بنابراین در حالت سنتی الگوریتم PSO، نمی‌توان بدون پرداخت هزینه‌ی زمانی و پردازشی زیاد گام initialize را حذف کرد.
اما اگر با دقت به الگوریتم PSO نگاه کنیم واضح است که مهم‌ترین تاثیر گام initialize هنگامی‌که است که قرار است fitness value برای آن محاسبه شود. در این مرحله اگر مقدار r1 و r2 بر اساس مقدار اولیه‌ی ذره محاسبه نشده باشد، جواب بهینه حاصل نخواهد شد و اگر بر اساس مقدار اولیه‌ی ذره باشد باید قبلا آنرا initialize کرده باشیم.
اما همانطور که بیان شد در محیط برخی سیستم‌ها الگوریتم‌های یافتن مقدار بهینه به دفعات اجرا می‌شوند. بنابراین می‌توان از تکرار‌های قبلی Initialize استفاده کرد به شرطی که ذرات Initialize شده جایی در حافظه نگه‌داری شوند. بدین ترتیب می‌توان گام initialize را تنها برای ذراتی که برای اولین بار به مجموعه‌ی داده اضافه شده‌اند انجام داد و عملا کارایی الگوریتم را افزایش داد.
اما در محیط بلاگستان که روزانه بالغ بر چند ده میلیون پُست وبلاگ در آن منتشر می‌شود[۲۶] و نیاز است که گرایش کاربران به صورت بلادرنگ[۱۰۳] تولید شود نگه‌داری اطلاعات همه ذرات بسیار هزینه‌بر است. فرض کنید اگر اطلاعات هر پست وبلاگ ۱MB باشد[۲۷] ، به کامپیوتری با ۱۰TB حافظه اصلی نیاز است – فقط برای نگه‌داری این داده‌ها برای یک روز- به این معنی که استخراج گرایش مبتنی بر روزهای پیشین نیز نخواهد بود که عملیاتی بسیار پر هزینه است.
چنین حجمی‌از حافظه اصلی تنها توسط اشکال مختلف سیستم‌های توزیع‌شده قابل دسترسی است و هیچ MainBoard وجود ندارد که بتوان در آن ۱۰TB حافظه اصلی قرار داد و حتی اگر کامپیوتری با این حجم از حافظه اصلی وجود داشته باشد گذرگاه[۱۰۴] مناسبی برای عبور دادن این حجم از داده به صورت آنی وجود ندارد. در اینجا نیاز به اجرای الگوریتم روی کامپیوترهایی با تعداد بیشتر و یک بستر پردازشی توزیع شده بیشتر نمایان می‌شود. بنابراین به بیش از یک ایستگاه کاری[۱۰۵] و یا سرور[۱۰۶] برای پردازش این حجم از داده نیازمندیم که در این به هرکدام یک نود پردازشی می‌گوییم.

اصلاح PSO بر اساس مسئله

بنابراین نیاز است که اولا اطلاعات ذراتی که initialize شده‌اند در جایی نگه‌داری شود تا در تکرارهای[۱۰۷] بعدی الگوریتم مجددا محاسبه نشوند، ثانیا این عمل باید توسط تعدادی کامپیوتر انجام شود تا محدودیت‌های فیزیکی که در حال حاضر با آنها مواجه هستیم برطرف گردد. به تعبیر دیگر الگوریتم‌ باید به صورت توزیع شده اجرا شود. به همین منظور الگوریتم سنتی PSO که در شبه کد (۱) آورده شد به صورت زیر بازنویسی می‌شود:
If there is new element in CAQ
For each new element
initialize particle
END
DO
For new particle (new post)
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history
set current value as the new pBest
End
Send the particle with best fitness value to Aggregator
Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according equation (a)
Update particle position according equation (b)
End
End
v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[]) (a)
present[] = persent[] + v[] (b)