بخشی از مقاله
-1 چکیده
کاوش کاربردی وب بهمنظور استخراج الگوهای کاربردی درست و مناسب از دادههای ثانویه استفاده میشود که خود بر اساس تعامل با کاربران هنگام گشت زنی و سیر در سایتهای مختلف وب به دست میآید. این الگوهای کاربردی بر مبنای گشت زنی کاربران در وب مشخص میشود و دارای کاربردهای زیادی است. قوانین وابستگی برای صفحات، وابستگی بین صفحات را توصیف میکند، بهعنوانمثال درصورتیکه کاربر صفحه A را ببیند و در زمان دیگری صفحه B را نیز ببیند، یک نوع وابستگی بین صفحات توسط الگوریتم قوانین وابستگی یا قوانین انجمنی کشف میشود. ازآنجاکه در قوانین وابستگی هیچ نوع ترتیب منظمی بین صفحات وب مطرح نیست، بهرهگیری از این قوانین برای پیشنهاد صفحات وبی که بهصورت ترتیبی به هم ربطی ندارند مؤثر است. در این مقاله روشی مبتنی بر کشف قواعد وابستگی و سپس الگوریتمهای خوشهبندی برای کشف الگوهای رفتاری کاربران وب معرفی میگردد. در این مقاله با استفاده از کاوش الگوهای پرتکرار و کشف قواعد وابستگی میتوان الگوی گشت زنی کاربران متفاوت را یافت و با استفاده از خوشهبندی میتوان سرویسهای وب خصوصی شده و سفارشی برای گروههای مختلف کاربران فراهم کرد و درنهایت گام آخر فرایند، یعنی تحلیل الگوها بهمنظور تحلیل و ارزیابی سودمندی و کار آیی دانش حاصله از گامهای پیشین به کار میرود. نتایج پیادهسازی، بیانگر کیفیت مناسب روش پیشنهادی بر اساس دقت و پوشش در مقایسه با روش انجامشده پیشین میباشد.
واژههای کلیدی: کاوش وب، شخصیسازی وب، دادهکاوی، کشف قواعد وابستگی، خوشهبندی
-2 مقدمه
کاوش کاربردی وب بهمنظور استخراج الگوهای کاربردی درست و مناسب از دادههای ثانویه استفاده میشود که خود بر اساس تعامل با کاربران هنگام گشت زنی 1و سیر در سایتهای مختلف وب به دست میآید .[1]روشهای کاوش کاربری وب در دودسته عمده قرار میگیرند: کاوش الگوهای دسترسی عمومی و پیگیری کاربردهای خاص. کاوش بر اساس دسترسی عمومی بر اساس همه فایلهای ثبت وقایع در دسترس در یک سایت عمل میکند .[2] نتایج حاصله بیشتر نمایشدهنده کیفیت آن سایت است و کمتر به رفتارهای فردی و خاص هر سایت توجه دارد، اما در پیگیری کاربردی، تمرکز اساسی کاوش بر روی درک و فهمیدن چگونگی سیر و حرکت کاربران در سایت است و چندان توجهی به ساختار آن سایت ندارد.[3]کل فرایند کاوش کاربری وب به سه فاز پیشپردازش2،کشف الگوها3و تحلیل الگوها4تقسیم میشود.در فاز پیشپردازش فایلهای ثبت وقایع بر مبنای جلسات کاربران تقسیم و دستهبندی و تبدیل به فایلهای تحت عنوان فایلهای تعاملی5میشوند که خلاصه مذاکرات در آنها قرار دارد.
در فاز کشف الگو فنون مختلف دادهکاوی مثل کاوش قوانین وابستگی6، کاوش الگوی ترتیبی7یا خوشهبندی8بهکاربرده میشود تا الگوهای جالب و موردنظر یافت شوند .[4]کشف قوانین وابستگی9 یکی از پرکاربردترین الگوهایی است که توسط دادهکاوی استخراج میگردند. کشف قوانین وابستگی به معنای یافتن همه قوانینی است که دارای مقدار پشتیبان10بیشتر یا مساوی یک مقدار از پیش تعریفشده توسط کاربر میباشند. کشف اقلام تکرارشونده11مهمترین فاز یافتن قوانین وابستگی را تشکیل میدهد. اقلام تکرارشونده به دادههایی میگویند که با یکدیگر حادث میگردند و این تکرار حجم قابلانتظاری از دادهها را تحت پوشش قرار میدهد .[5] قوانین وابستگی برای صفحات، وابستگی بین صفحات را توصیف میکند. ازآنجاکه در قوانین وابستگی هیچ نوع ترتیب منظمی بین صفحات وب مطرح نیست، بهرهگیری از این قوانین برای پیشنهاد صفحات وبی که بهصورت ترتیبی به هم ربطی ندارند مؤثر است. در این مقاله روشی مبتنی بر کشف قواعد وابستگی و سپس الگوریتمهای خوشهبندی برای کشف الگوهای رفتاری کاربران وب معرفی میگردد.
-3 مروری بر کارهای انجامشده
در این بخش به بررسی الگوریتمها و روشهایی که در کاوش ساختار وب به کار میروند، پرداخته میشود. دو الگوریتم اول که 1HITS و Page Rank نام دارند، برای بازیابی صفحات وب و رتبهبندی آنها بر اساس میزان ارتباط با پرسوجوی کاربر استفاده میشوند. الگوریتم سوم در تشخیص اجتماعات وب2و الگوریتم چهارم نیز برای محاسبه فاصله صفحات وب استفاده میشود.
1؛Page Rank -3
الگوریتم Page Rank که اولین بار در سال 1998 توسط Larry Page و [9] Sergey Brin ارائهشده است، یک روش مستقل از پرسوجو3میباشد. این روش یکبار به هر سند وب امتیاز اختصاص میدهد و از این امتیاز، با یا بدون در نظر گرفتن معیاری با توجه به پرسوجوی کاربر جهت رتبهبندی اسناد استفاده میکند. این الگوریتم رتبه هر صفحه را با اختصاص وزن به پیوندی که به آن صفحه دادهشده است به دست میآورد. مقدار این وزن به کیفیت صفحهای که پیوند دران قرارگرفته، بستگی دارد. در این صورت پیوندهای صفحات مهمتر وزن بیشتری میگیرند. جهت مشخص کردن کیفیت صفحههای رجوع کننده، در Page Rank از رتبه آن صفحه که بهصورت بازگشتی تعیین و مقدار اولیه آن اختیاری است، استفاده میشود. اگر n سند در دسترس باشد، مقدار اولیه رتبه سند را میتوان برابر 1/n در نظر گرفت. رتبه هر صفحه مانند P طبق فرمول زیر محاسبه میشود که BP مجموعه همه صفحات اشارهکننده به P میباشد در این رابطه مقدار ثابتی بین 0,1 و 0,2، n تعداد گرهها در گراف G - تعداد صفحات وب در مجموعه - و Outdegree - Q - تعداد پیوندهای خروجی موجود در صفحه Q است. رتبه مرحله j صفحه Pi طبق فرمول زیر محاسبه میشود:در این فرمول، رتبه صفحه P به رتبه صفحه Q که به آن اشاره میکند، بستگی دارد. این معیار بهخوبی صفحههای باکیفیت را از صفحههای فاقد کیفیت متمایز میسازد.
2؛-3 الگوریتم جریان بیشینه [10]
مسئله جریان بیشینهs-t4 به این صورت بیان میشود: در یک گراف که به یالهای آن ظرفیت جریانی مثبت اختصاص دادهشده است، هدف آن است که بیشینه جریانی که قابلانتقال از گره s به گره t است، محاسبه شود. ثابتشده است که این مسئله معادل با مسئله برش کمینه5است. در مسئله برش کمینه، تعداد حداقل یالهایی که باید از گراف حذف شود تا گره s از گره t جدا شود، به دست میآید. برای حل این مسئله الگوریتمی توسط Ford و Fulkerson ارائهشده است که در ادامه بررسی میشود.الگوریتم Ford و Fulkerson به شرح زیر است:
