بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
معرفي الگوريتم هاي رتبه بندي
چکيده
با رشد فوق العاده و روز افزون حجم اطلاعات روي وب جستجوي اطلاعات در وب توسط کاربران اهميت ويژه اي دارد. يکي از مهمترين قسمت هاي موتورهاي جستجوي فعلي واحد رتبه بندي مي باشد . رتبه بندي مرتب کردن صفحات مبتني بر کيفيت آنها است . هدف از ارائه اين مقاله معرفي تعدادي از الگوريتم هاي رتبه بندي که تاکنون مطرح شده اند و اينکه هر کدام از اين الگوريتم ها از چه اطلاعاتي براي رتبه بندي استفاده مي کنند مي باشد. در ادامه اطلاعات روي وب دسته بندي شده وسپس الگورتم هاي رتبه بندي معرفي مي شوند.
کلمات کليدي : وب کاوي , الگوريتم هاي رتبه بندي
١-مقدمه
وب جهان گستر بزرگترين و پهناورترين منبع اطلاعاتي شناخته شده است که به سادگي قابل دستيابي و جستجو است و شامل ميليون ها سند به هم پيوسته است که صفحات وب ناميده مي شوند . رشد سريع وب در دهه هاي اخير آنرا به بزرگترين منبع داده اي قابل دسترسي در جهان تبديل کرده است . تحقيقات و پژوهشهاي فراواني در زمينه بازيابي اطلاعات (IR)در سراسر جهان انجام گرفته است . از آخرين تکنيکهاي ارائه شده جهت بازيابي اطلاعات مي توان به موتورهاي جستجو اشاره نمود. يکي از اهداف مهم در موتور هاي جستجو پيدا کردن صفحاتي با کيفيت بالا است کيفيت صفحات مبتني بر خواست و سليقه کاربر تعريف مي شود معمولا ميليون ها صفحه مرتبط با هر پرسش ٢ کاربر وجود دارد ولي کاربر ١٠ تا ٢٠ تاي آنها را ملاحظه مي کند بنابراين مسئله رتبه بندي مرتب کردن صفحات مبتني بر کيفيت آنها است .در ادام ه مقاله در بخش ٢ وب کاوي ٣ و دسته بندي آن مطرح شده است .در بخش ٣ انواع رتبه بندي و تعدادي الگوريتم رتبه بندي معرفي شده است و بخش ٤ نتيجه گيري مي باشد.
٢-مروري بر وب کاوي
طبق تعريف ارائه شده در[٢] وب کاوي کاربرد تکنيک هاي داده کاوي براي استخراج اطلاعات مفيد از وب است . هدف وب کاوي بازيابي اطلاعات يا دانش مفيد از ساختار ابر پيوندهاي وب ،محتوي صفحه و داده هاي کاربرد وب است . وب کاوي به سه دسته تقسيم مي شود :
١ -محتوي کاوي وب
٢ -ساختار کاوي وب
٣ -کاربرد کاوي وب
ساختار کاوي وب اطلاعات مفيد از ابر پيوند ها که ساختار وب را نشان مي دهند بازيابي مي کند. محتوي کاوي وب اطلاعات مفيد را از محتواي صفحات وب استخراج مي کند اين اطلاعات عبارتنداز متن , تصوير , ويدئو و غيره و کاربرد کاوي وب از تکنيک هاي داده کاوي براي کشف الگوهاي دستيابي کاربر وب بر اساس داده هاي کاربرد وب که در فايل هاي ثبت وب ٧ ذخيره شده اند استفاده مي کند.
٣- الگوريتم هاي رتبه بندي
يکي از اهداف مهم در موتور هاي جستجو پيدا کردن صفحاتي با کيفيت بالا است کيفيت صفحات مبتني بر خواست و سليقه کاربر تعريف مي شود معمولا ميليون ها صفحه مرتبط با هر پرسش کاربر وجود دارد ول ي کاربر ١٠ تا ٢٠ تاي آنها را ملاحظه مي کند بنابراين مسئله رتبه بندي مرتب کردن صفحات مبتني بر کيفيت آنها است الگوريتم هاي رتبه بندي ٨ به دو دسته تقسيم مي شوند[٥,٦]
١-الگوريتم هاي رتبه بندي مبتني بر محتوي (روش هاي IR سنتي )
٢-الگوريتم هاي رتبه بندي مبتني بر اتصال (روش هاي فعلي )
در بازيابي اطلاعات سنتي [٧] سيستم سعي در کشف صفحاتي مرتبط با پرسش کاربر دارد و الگوريتم هاي اين دسته مبتني بر مطابقت کلمات پرسش با محتوي اسناد وب هستند . چهار مدل اصلي براي IRوجود دارد[٨] مدل بولي ، مدل فضاي بردار ٩، مدل زبان و مدل احتمالي. در مدل بولي بودن يا نبودن کلمه در سند بررسي مي شود.مدل فضاي بردار TF-IDF که بهترين و پر استفاده ترين مدل است اسناد و پرسش ها به صورت يک بردار وزني نمايش داده مي شوند[٩,١٠] .مدل هاي زبان آماري روي احتمال مبتني هستند و پايه در نظريه آماري دارند.نمونه هايي از آن در [١١,١٢]مطرح شده است .
نمونه ديگري از الگوريتم هاي مبتني بر محتوي LSI [١٣]است که توسط ديروستر براي حل مشکل تعدد معاني و کلمات هم معني مطرح شد. اين الگوريتم ها بيشتر براي محيط هاي ساختيافته مانند کتابخانه هاي ديجيتال که داراي پرسش هاي بلند و مشخص و فرهنگ لغات کوتاه مي باشند مناسب است . اما وب داراي اسناد غير ساختيافته و معمولا پرسش هاي کوتاه مي باشد .علاوه بر آن اين روش ها چون مبتني بر محتوي هستند ومحتوي صفحات ممکن است متناقض و شامل اطلاعات غلط باشد بنابراين نتايجي با دقت و فراخواني ١٠پايين خواهند داش ت و مشکل پهنش رتبه ١١[١٤]بوجود مي آيد يعني صفحات بازگردانده شده توسط اين الگوريتم ها ممکن است مرتبط با پرسش کاربر باشد اما صفحات معتبر و معروفي نباشند . براي رفع اين مشکلات الگوريتم هاي رتبه بندي مبتني بر اتصال مطرح شدند .اين الگوريتم ها از اطلاعات ابرپ وندها ي ب ن صفحات راي رتبه بندي استفاده مي کنند. ابر پيوندهاي بين صفحات حامل اطلاعاتي است که مي تواند بر ي ارزيا ي ر به صفحات استفاده شود . مهمترين الگوريتم هاي مطرح شده در اين زمينه PageRank[15,16], Hits[17] و DistanceRank[18]است . الگوريتم هاي رتبه بندي مبتني بر اتصال در[١٩] با هم مقايسه شده اند . اگرچه الگوريتم هاي اين دسته براي عضي موقعيت ها من سب هستند اما دق آ ها در مقا سه ا الگوريتم هاي مبتني بر محتوي پايين است [٢٠] و داراي مشکلاتي مانند "غني تر شدن اغنيائ " ١٢که موجب مي شود صفحات معروف در صدر ليست نتايج قرار داده مي شوندوصفحات تازه ايجاد شده با کيفيت بالا شانس کمتري دارندکه توسط کاربرانتخاب شوند[٢١]. در بازيابي اطلاعات وب کاربرها مهمترين نقش را دارند و هدف اصلي رتبه بندي کسب رضايت آنها است . بنابراين مي توان از داده هاي کاربرد وب که در فايل هاي ثبت ذخيره مي شود براي رتبه بندي استفاده نمود تا نتايج مطلوب تري حاصل شود .در ادامه اين بخش الگوريتم هاي رتبه بندي مطرح شده در اين دو دسته معرفي شده همچنين الگوريتم هايي که ترکيبي از هر سه زمینه (ساخت ر کاوي ،محتوي کاوي و کاربرد کاوي وب ) مي باشند مطرح مي شوند و علاوه بر آن کارهاي انجام شده با استفاده از اتوماتا نيز بحث شده اند.
٣-١- مدل بولي
مدل بولي قديمي ترين وساده ترين مدل lRاست .دراين مدل اسناد وپرسش ها به صورت مجموعه اي ازواژه ها نشان داده مي شوند که براي هرواژه بودن يا نبودنش درسند مورد توجه قرار گرفته است . اگر واژه ti درسند dj باشد يک درغير اين صورت صفر مي باشد . سيستم هر سندي که پرسش درآن به طور منطقي درست باشد را بازيابي مي کند.
٣-٢- مدل فضاي بردار
اين مدل بهترين وپر استفاده ترين مدل lRشناخته شده است . دراين مدل يک سند به عن وان بردار وزني نمايش داده مي شود وهرجزء وزن مبتني برروش تکرار واژه (TF)١٣ يا روش تکرار واژه - تکرار معکوس سند (TF-lDF)١٤ محاسبه شده است .که وزن wij مربوط به واژه tiدرسند dj بزرگتراز [١ ٠] نيست .
روش TF: دراين روش وزن واژه tiدر سند djتعداد دفعاتي است که tiدر سند dj ظاهر شده است که به وسيله fij مشخص مي شود. ضعف اين روش در اين است که به وضيعتي که يک واژه ممکن است در سند هاي زيادي رخ داده باشد توجه نمي کند.
روش TF-IDF:که بهتروشناخته شده تر از TF است . فرض کنيدN تعداد کلي اسناد در سيستم يا مجموعه باشد و dfiتعداد اسنادي که واژه tiدر آنها ظاهر شده باشد و fij تعداد تکرار واژه tiدر سندdj باشد. بنابراين تعداد تکرار واژه نرمال شده و تکرار معکوس سند واژه tiبه صورت زير محاسبه مي شود:
اگر واژه tiدر سند dj ظاهر نشده باشد ٠=tfij.وزن واژه tf-ldf نهايي به صورت زير محاسبه مي شود:
يک پرسش عينا مانند يک سند در مجموعه اسناد نشان داده مي شود. وزن واژه tiدرq مي تواند به شيوه اي يکسان با سند محاسبه شده يا اندکي متفاوت مانند آنچه سالتون و بوکلي [١٠] پيشنهاد دادند. در مدل فضاي بردار اسناد براساس درجه ارتباط آنها با کوئري رتبه بندي مي شوند. يک راه محاسبه درجه ارتباط محاسبه تشابه بين کوئري q با هر سند dj در مجموعه اسنادD است . مقياس هاي تشابه زيادي وجود دارد که شناخته شده ترين آنها کوسينوس تشابه است . روش هاي ديگري نيز وجود دارد مانند okapiوpnw [٩].
٣-٣-مدل زبان آماري
مدل هاي زبان آماري روي احتمال مبتني هستند[١١]. ابتدا يک مدل زبان براي هر سند تخمين مي زند وسپس اسناد را به وسيله همساني با مدل زبان پرسش داده شده رتبه بندي مي کند فرض کنيد پرسش q يک توالي ازواژه هاي باشد و Dيک مجموعه از سندهاي در روش مدل سازي زبان ، به احتمال اين که پرسش q به وسيله يک مدل احتمالي مبتني روي سند dj ايجاد شده باشد يعني توجه مي کنيم که به تخمين عکس آن علاقه مند هستيم يعني وطبق قانون Bayes :
براي رتبه بندي نياز نيست چون براي هر سندي يکسان است مدل کليn-gram است يعني واژه n ام روي ١-n ام شرط شده است :
که f q تعداد دفعاتی ست که واژه ti در q رخ مي دهد و fij تعداد تکرار واژه ti در سند dj و |dj| تعداد کلي کلمات در dj است .
٣-٤-شاخص گذاري معنايي پنهان 15(LSI)
مدل هاي بازيابي اطلاعات روي مطابقت کلمات و عبارات مبتني بودند اما مفاه م و اشياء زيادي با ک م ت متفاوت وصيف ي شوند مثلا "picture" ،image"" و"photo" مترادف هايي در مفهوم دوربين هاي ديجيتالي هستند LSI به وسيله ديروستر[١٤] مطرح شد. هدف بررسي اين مسئله از طريق شناسايي وابستگي هاي آماري واژه هاست .
فرض مي شود ساختار معنايي پنهاني در داده ها وجود دارد که به طور جز ي به وسيله انتخاب تصاد ي کلمه م هم شده است . و تکنيک آماري را که تجزيه ارزش منفرد ١٦[٢٢] ناميده مي شود استفاده مي کند . که ساختار پنهان ارزيابي شده و نويزها حذف مي شود . نتايج اين تجزيه تش ريح واژه ها و اسناد مبتني بر ساختار معنايي پنهان مشتق شده از SVD است . اين ساختار همچنين فضاي مفهومي پنهان شده ناميده مي شود . که تفاوت نحوي اما معنايي مشابه را پيوند مي زند . واژه هاي اسناد دگرگون شده درفضاي مفهومي براي ارزيابي استفاده مي شو د ه وا ه ها يا سناداوليه . علاوه بر آن پرس نيز به فضاي مفهومي منتقل مي شود.
فرض کنيد D مجموعه اسناد با m کلمه مشخص و N سند باشد .
LSI با يک ماتريس m*n که هر درايه آن مانند Aij تعداد تکرار واژه i در سند j را نشان مي دهد البته مي تواند تکرار نباشد و مثلا توسط Tf- lDF محاسبه شده باشد . آنچه SVD انجام مي دهد فاکتور ماتريس در سه ماتريس است :
U ماتريس يک ماتريس n*r و ∑يک ماتريس قطري r*r و که مقادير قطر اصلي آن به صورت نزولي مرتب شده اند .
ويژگي مهم SVD اين است که مي توان ابعاد ناچيز را در فضاي تغيير يافته ب راي بهينه کردن تقريب ماتريس Aحذف کرد . بعد ناچيز ممکن است نويزي در داده ها را نشان مي دهد و بايد حذف شود و فقط kارزش بزرگتر منفرد را استفاده مي کنيم . تقريب ماتريس A با AK نشان داده مي شود و مي توان اندازه ماتريس هاي و u وv را با حذف r-k ستون آخر به دست آورد :
فضاي جديد بردار "k- مفهوم " ناميده مي شود . پرسش q نيز به وسيله بردارستوني مثل A نشان داده مي شود ابتدا آن را در يک سند در فضاي k– مفهوم تبديل کرده و بوسيله q k نشان داده مي شود.اين تبديل ضروري است زيرا SVDسند اصلي رادر
