عنوان : بهینه سازی خوشه ها با استفاده از الگوریتم های تکاملی برای شخصی سازی وب
تعداد صفحات : 82
چکیده:
گرانبار شدن اطلاعات یک مشکل عمده در وب کنونی به شمار میرود. برای مقابله با این مشکل، سیستمهای شخصی سازی وب ارائه شده اند که محتوا و سرویس های یک وب سایت را با افراد براساس علایق و رفتار گردشی آنها سازگار میکنند. یک مؤلفهی اساسی در هر سیستم شخصیسازی وب، مدل کاربر آن است. هدف از شخصی سازی وب، مهیا ساختن محتوا و سرویس های مورد نیاز کاربران به وسیله دانش به دست آمده از تعاملات قبلی کاربران در صفحات وب است. در حال حاضر، برای شخصی سازی وب چندین متد خوشه بندی در دسترس است. روشهایی که تاکنون ارائه شده اند، در مواردی دارای اشکالاتی بودند. البته تکنیک های جدیدی در رفع این مشکلات و بهبود آنها ارائه شده است. اما در بیشتر این تکنیکها، مسائل افزونگی داده و مقیاس بندی بالا وجود دارد. با توجه به اینکه افزایش کاربران وب منجر به افزایش اندازه‌ی خوشه می‌گرد، نیاز به بهینهسازی خوشه‌ها اجتناب‌ناپذیر خواهد بود. در تحقیق، یک متدولوژی بهینه سازی خوشه بر اساس سیستم فازی ارائه شده است. به منظور افزایش دقت نهایی خوشه بندی، برای تنظیم پارامترهای توابع عضویت از الگوریتم ژنتیک استفاده شده است. نتایج حاصل از شبیهسازی نشان میدهد که روش پیشنهادی دقت خوشه بندی صفحات وب را تا حد قابل توجهی افزایش میدهد.
فصل اول: کلیات تحقیق
1-1- مقدمه
با توسعه سیستمهای اطلاعاتی، داده به یکی از منابع پراهمیت سازمان‌ها مبدل گشته است. بنابراین روشها و تکنیک‌هایی برای دستیابی کارا به داده، اشتراک داده، استخراج اطلاعات از داده و استفاده از این اطلاعات، مورد نیاز میباشد. با ایجاد و گسترش وب و افزایش چشم گیر حجم اطلاعات، نیاز به این روشها و تکنیکها بیش از پیش احساس میشود. وب، محیطی وسیع، متنوع و پویا است که کاربران متعدد اسناد خود را در آن منتشر میکنند. در حال حاضر بیش از دو بیلیون صفحه در وب موجود است و این تعداد با نرخ 7.3 میلیون صفحه در روز افزایش می‌یابد. با توجه به حجم وسیع اطلاعات در وب، مدیریت آن با ابزارهای سنتی تقریباً غیر ممکن است و ابزارها و روشهایی نو برای مدیریت آن مورد نیاز است. به طور کلی کاربران وب در استفاده از آن با مشکلات زیر روبرو هستند:
1- یافتن اطلاعات مرتبط: یافتن اطلاعات مورد نیاز در وب دشوار میباشد. روشهای سنتی بازیابی اطلاعات که برای جستجوی اطلاعات در پایگاه داده‌ها به کار می‌روند، قابل استفاده در وب نمی‌باشند و کاربران معمولاً از موتورهای جستجو که مهمترین و رایج ترین ابزار برای یافتن اطلاعات در وب می باشند، استفاده میکنند. این موتورها، یک پرس و جوی مبتنی بر کلمات کلیدی از کاربر دریافت کرده و در پاسخ لیستی از اسناد مرتبط با پرس و جوی وی را که بر اساس میزان ارتباط با این پرس و جو مرتب شده اند، به وی ارائه میکنند. اما موتورهای جستجو دارای دو مشکل اصلی هستند (Baeza-Yates, 2004). اولاً دقت موتورهای جستجو پایین است، چراکه این موتورها در پاسخ به یک پرس و جوی کاربر صدها یا هزاران سند را بازیابی میکنند، در حالی که بسیاری از اسناد بازیابی شده توسط آنها با نیاز اطلاعاتی کاربر مرتبط نمی‌باشند (Bharat, and et. al., 2001). ثانیاً میزان فراخوان این موتورها کم میباشد، به آن معنی که قادر به بازیابی کلیه اسناد مرتبط با نیاز اطلاعاتی کاربر نیستند. چرا که حجم اسناد در وب بسیار زیاد است و موتورهای جستجو قادر به نگهداری اطلاعات کلیه اسناد وب، در پایگاه دادههای خود نمی‌باشند (Chakrabarti, and et. al., 1999).
2- ایجاد دانش جدید با استفاده از اطلاعات موجود در وب: در حال حاضر این سوال مطرح است که چگونه میتوان دادههای فراوان موجود در وب را به دانشی قابل استفاده تبدیل کرد، به طوری که یافتن اطلاعات مورد نیاز در آن به سادگی صورت بگیرد. همچنین چگونه میتوان با استفاده از دادههای وب به اطلاعات و دانشی جدید دست یافت.
3- خصوصی سازی اطلاعات: از آن جا که کاربران متفاوت هر یک درباره نوع و نحوهی بازنمایی اطلاعات سلیقه خاصی دارند، این مسئله باید توسط تأمین کنندگان اطلاعات در وب مورد توجه قرار بگیرد. برای این منظور با توجه به خواسته‌ها و تمایلات کاربران متفاوت، نحوه ارائه اطلاعات به آنها باید سفارشی گردد.
تکنیکهای وب کاوی قادر به حل این مشکلات میباشند (Chakrabarti, 2000).
2-1- تعریف مسئله
وب به یک بخش تسلیم نشدنی جهان تبدیل شده است و گشت و گذار وب، یک فعالیت مهم برای مشتریانی که خرید آنلاین دارند، به شمار میآید (Varghese, 2012). همانطور که گفته شد، با توجه به حجم وسیع اطلاعات در وب، مدیریت آن با ابزارهای سنتی تقریباً غیر ممکن است و ابزارها و روشهایی نو برای مدیریت آن مورد نیاز است. یکی از این روشها وبکاوی است. به طور کلی وبکاوی را میتوان داده کاوی بر روی دادههای محتوا، ساختار و کاربرد وب به حساب آورد. هدف وبکاوی کشف مدلها و الگوهای نهفته در منابع وب میباشد. هدف وب کاوی کاربرد وب به طور خاص کشف الگوهای رفتاری کاربران وب میباشد. کشف چنین الگوهایی از حجم عظیمی از دادههای تولید شده توسط وب سرورها کاربردهای مهمی دارد (Anand, and Mobasher, 2005). از جملهی آنها میتوان به سیستم هایی که میزان مؤثر بودن یک سایت را در برآوردن انتظارات کاربر ارزیابی میکنند، تکنیک هایی برای متعادل کردن پویای بار و بهینهسازی وب سرورها برای دستیابی مؤثرتر کاربران و کاربردهای مربوط به ساختاردهی مجدد و تطبیق یک سایت براساس نیازهای پیش بینی شدهی کاربر اشاره کرد.
کشف استخراج اطلاعات مفید از دادهی وب یا فایلهای وبلاگ، بهبود کارایی اطلاعات وب و فراهم کردن تکنولوژی برای کاربردهای وب به عنوان مثال، شخصیسازی و غیره از جمله اهداف دیگر وبکاوی میباشد. برای مدیریت تصمیمگیری، نتیجه کاوش کاربرد وب میتواند برای تبلیغات، بهبود طراحی وب، بهبود رضایت مشتری، هدایت استراتژی تصمیم آنالیز بازار و سازمان مورد استفاده قرار گیرد (Naveena Devi et al., 2012).
در سال های اخیر تکنیکهای وبکاوی کاربرد وب به عنوان رویکردی دیگر که مبتنی بر کاربر است در شخصیسازی وب ارائه شده است که برخی از مشکلات مربوط به فیلترکردن جمعی را کاهش میدهد. به طور خاص وب کاوی کاربرد وب برای افزایش گسترش‌پذیری سیستم های شخصیسازی شدهی سنتی که برمبنای تکنیکهای فیلترکردن جمعی میباشند استفاده شده است.
شخصیسازی صفحه وب شامل خوشهبندی صفحات مختلف وبی است که الگوی مشابهی دارند. شخصیسازی وب از تکنیک کاربرد وب کاوی برای سفارشی کردن صفحات وب برای یک کاربر خاص استفاده میکند. این مسئله شامل استخراج جلسات کاربر از فایلهای ورود به سیستم میشود. یک جلسه کاربر، دنبالهی صفحات وبی که توسط کاربر در یک دوره زمانی خاص مورد دسترسی قرار گرفته، میباشد.
3-1- اهمیت و ضرورت تحقیق
با رشد ناگهانی اندازه وب و استفاده از وب گسترده جهانی، برای کاربران بسیار مشکل شد که بتوانند به طور مؤثر به اطلاعات مرتبط و مورد علاقه خود دسترسی پیدا کنند. نیاز به پیشبینی نیازهای کاربر به منظور بهبود قابلیت استفاده و حفظ کاربر سایت، آشکار است و میتواند با استفاده از شخصیسازی آدرسدهی شود. شخصیسازی وب، پردازشی از یک سایت برای بر طرف کردن نیاز یک کاربر خاص یا مجموعهای از کاربران با استفاده از دانش به دست آمده از طریق تحلیل رفتار گشت و گذار کاربر است. هدف از سیستم شخصی سازی وب، مهیا ساختن اطلاعات و نیازهای کاربران، بدون این که صریحاً از آنها سوالی پرسیده شود.
هر اقدامی که اطلاعات یا سرویسهای فراهم شده توسط یک وبسایت با نیازهای یک کاربر یا گروه خاصی از کاربران با به کارگیری دانش بدست آمده از رفتار گردشی کاربر و علایق خاص او به صورت ترکیب با محتوا و ساختار وبسایت سازگار میکند شخصی سازی وب نامیده میشود (Eirinaki, 2003).
بطور کلی اهداف شخصی سازی وب عبارتند از:
– شخصی سازی سرویسهای ارائه شده توسط یک وبسایت نقش مهمی در کاهش گرانبار شدن اطلاعات ایفا میکند و وبسایت را به یک محیط کاربر پسندتر برای افراد تبدیل میکند.
– با فراهم کردن اطلاعات دلخواه کاربر به روش مناسب و در زمان مناسب، باعث بهبود گردش کاربر در وب سایت میشود.
– در تجارت الکترونیکی مکانیزیمی برای درک بهتر نیازهای مشتری، شناسایی تمایلات آیندهی او و در نهایت افزایش پابرجایی مشتری به سرویس ارائه شده فراهم میکند.
در سال های اخیر تکنیکهای وبکاوی کاربرد وب به عنوان رویکردی دیگر که مبتنی بر کاربر است در شخصیسازی وب ارائه شده است که برخی از مشکلات مربوط به فیلترکردن جمعی را کاهش میدهند. به طور خاص وب کاوی کاربرد وب برای افزایش گسترش پذیری سیستمهای شخصیسازی شدهی سنتی که برمبنای تکنیکهای فیلترکردن جمعی میباشند استفاده شده است.
به طور نمونه شخصی سازی برروی پردازش شناسایی کاربر وب، جمع آوری اطلاعات از طریق اولویت یا علاقهمندی های کاربر، تمرکز دارد. به طور مختصر شخصی سازی وب میتواند برای مهیا ساختن سرویس با کیفیت تر استفاده شود و برنامه کاربردی از وب را برای کاربران در طول گشت و گذار آنها در وب مهیا سازد. این فعالیتها می تواند با مشخص کردن لینکها و لینکهای جدید مورد علاقه کاربر به صورت اتوماتیک و ایجاد صفحات ایندکس جدید، ساخته شود.
رویکرد تنها مبتنی بر کاربرد در شخصیسازی وب یک عیب مهم دارد و آن این است که فرآیند توصیه به کاربر تنها براساس دادههای تراکنشی موجود او صورت میگیرد و از این رو اقلام یا صفحاتی که اخیراً به سایت اضافه شدهاند نمیتوانند به او توصیه شوند. این مشکل عموماً مشکل قلم جدید نامیده میشود. از سوی دیگر اگرچه الگوهای کشف شدهی مربوط به کاربرد منابع وب از طریق وبکاوی کاربرد وب در کشف ارتباطات اقلام با یکدیگر یا کاربران با یکدیگر و نیز تعیین شباهت در جلسات کاربر مفیدند اما بدون استفاده از دانش عمیقتری از دامنهی وب سایت مورد نظر چنین الگوهایی درک اندکی از دلایل آن که چرا اقلام یا کاربران در گروه هایی با هم قرار میگیرند در اختیار ما قرار میدهند. یک رویکرد معمول برای حل این مشکل در فیلتر کردن جمعی آن است که مشخصات محتوای صفحات را با رتبه بندی ها و قضاوت های کاربر ادغام کنیم. به طور کلی در این رویکردها کلمات کلیدی از محتوای وبسایت استخراج میشوند و برای اندیسگذاری صفحات براساس محتوا یا طبقهبندی آنها به دسته های مختلف مورد استفاده قرار میگیرند. در حوزهی شخصی سازی وب این رویکرد به سیستم اجازه می دهد تا صفحات را نه تنها براساس افراد مشابه بلکه براساس شباهت محتوایی آنها به صفحاتی که کاربر اخیراً بازدید کرده است به او توصیه کند.
یک ضعف عمده در بیشتر رویکردهای موجود که از محتوای وب برای بهبود مدل کاربر استفاده میکنند این است که این روشها معمولاً از بردار عبارات برای نمایش علایق کاربر استفاده میکنند و ارتباطات معنایی بین این عبارات را نادیده میگیرند. در صورتی که میتوان با استفاده از معنا این روش نمایش را بهبود داد.
روشهایی که تاکنون ارائه شدهاند، در مواردی دارای اشکالاتی بودند. البته تکنیکهای جدیدی در رفع این مشکلات و بهبود آنها ارائه شده است. اما در بیشتر این تکنیکها، مسائل افزونگی داده و مقیاس‌بندی بالا وجود دارد. الگوریتمهای خوشهبندی متعددی براساس تکنیک های مختلف وجود دارد. بیشتر این الگوریتم ها، اشکالات متعددی دارند. همانطور که اندازه خوشه در طی افزایش کاربران وب افزایش می‌یابد، نیاز به بهینهسازی خوشه ها اجتناب ناپذیر خواهد بود. در این پایاننامه قصد بر آنست تا یک متدولوژی بهینهسازی خوشه بر اساس سیستم فازی و الگوریتم ژنتیک ارائه شود.
فهرست مطالب:
چکیده
فصل اول
1-1-مقدمه
1-2-تعریف مسئله
1-3-اهمیت و ضرورت تحقیق
1-4-شیوه پژوهش
1-5-چارچوب پایان نامه
مراجع
فصل دوم
2-1-مقدمه
2-2-مروی بر کارهای انجام شده
مراجع
فصل سوم
3-1-مقدمه
3-2-مراحل وب کاوی
3-2-1-انواع وبکاوی
3-3-شخصیسازی وب
3-3-1-دلایل نیاز به شخصیسازی وب
3-3-2-مراحل شخصی سازی وب
3-3-2-1-جمع‌آوری داده
3-3-2-2-پردازش داده
3-3-2-3-کشف الگو
3-3-2-4-تحلیل دانش
3-3-3-تکنیک های مدلسازی کاربر در شخصیسازی وب
3-3-3-1-تکنیک tf-idf
3-3-3-2-تکنیک متا مدل و ابزار OLAP
3-3-3-3-تکنیک براساس محتوای وب
3-3-3-4-تکنیک براساس فراهم کردن دادههای موثر (ODP)
3-3-3-5-شخصیسازی وب با استفاده از روشهای ترکیبی
3-3-3-6-شخصیسازی وب براساس الگوریتم استقرایی و تکنولوژی tf-idf
3-3-3-7-شخصیسازی وب با استفاده از کندوکاو الگوی ترتیبی و درخت الگو
3-4-خوشهبندی برای شخصیسازی وب
3-4-1-خوشه بندی فازی
3-4-1-1-الگوریتم پایه‌ای خوشهبندی فازی
3-4-1-2-الگوریتم فازی کامینز
3-4-1-3-خوشهبندی صفحات وب با استفاده از خوشه بندی فازی k-means
3-4-2-الگوریتم ژنتیک
3-4-2-1-بهینهسازی خوشهبندی فازی با استفاده از الگوریتم ژنتیک
3-4-3-روش پیشنهادی در این تحقیق
3-4-4-شمای کلی سیستم پیشنهادی
3-4-5-مثالی از سیستم پیشنهادی
3-4-6-شبه کد روش پیشنهادی
3-5-جمع بندی
مراجع
فصل چهارم
4-1-مقدمه
4-2-مجموعه داده ها
4-2-1-دیتاست YANDEX
4-2-1-1-پیش پردازش انجام شده با مجموعه دادههای خام قبل از انتشار
4-3-پارامترهای ارزیابی
4-4-آزمایشات انجام شده
4-4-1-سخت افزار مورد استفاده
4-4-2-نتایج آزمایشات
4-5-جمع بندی
مراجع
فصل پنجم
5-1-مقدمه
5-2-نتایج و دستاوردهای پروژه
5-3-پیشنهادات
مراجع
