|
Axborotlarni izlash va ajratib olish
|
| bet | 1/10 | | Sana | 16.05.2024 | | Hajmi | 345,87 Kb. | | #237900 |
Bog'liq Mustaqil ish 4
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT
AXBOROT TEXNOLOGIYALARI UNIVERSITETI
KOMPYUTER INJIRINGI FAKULTETI 211-23 ADVLO‘ GURUH TALABASI SATVOLDIYEV ABRORJONNING “ AXBOROTLARNI IZLASH VA AJRATIB OLISH” FANIDAN TAYYORLAGAN
Mustaqil ishi
Mavzu: Mavzuga aloqador Sahifalar Reytingi (
Mavzuga aloqador(topic-sensitive) sahifa reytingi(PageRank), reyting jarayonida ba'zi mavzularga boshqalarga qaraganda ko'proq muhimlikini taqdim etishni istagan holatlar uchun mo'ljallangan. “Shaxsiylashtirish” keng ko'lamli tijorat qidiruv tizimlarida kamroq qo’llanilsa-da, u kichikroq saytlarga xos qidiruv ilovalarida keng taqrqalgan.( "Shaxsiylashtirish"- internetda foydalanuvchining talablari yoki qiziqishlari asosida qidiruv natijalarini taqdim etish jarayonini ifodalaydi. Bu, foydalanuvchilarning qidiruv tarixi, tanlovlari, joylashuvi va boshqa muhim ko'rsatgichlarni hisobga olgan holda qidiruv natijalarini tadqim etish. Shaxsiylashtirilgan qidiruv, har bir foydalanuvchiga maxsus ravishda mos keladigan ma'lumotlarni taklif etadi. Boshqacha qilib aytganda qidiruv tizimlaridagi “Rekomendatsiya”)
Odatda, foydalanuvchilar ma'lum bir mavzularga boshqa mavzularga qaraganda ko'proq qiziqish bildirishi mumkin. Qidiruv tizimi, bunday qiziqishlar haqidagi ma’lumotlarni foydalanuvchi ro'yxatdan o'tganligi sababli shaxsiylashtirgan bo'lishi mumkin. Misol uchun, ma'lum bir foydalanuvchi, avtomobillar mavzusiga qiziqishi ko'proq. Shuning uchun, bu foydalanuvchi soʻrov yuborganda tegishli sahifalar, avtomobillarni yuqoriroqda tartiblaydi. Bu reyting qiymatlarini shaxsiylashtirish sifatida ham ko'rish mumkin. Bunga qanday erishish mumkin?
Birinchi qadam - asosiy mavzular ro'yxatini tuzatish va ushbu mavzularning har biridan sahifalarning yuqori sifatli namunasini aniqlash. Bunga, har bir mavzu uchun asosiy mavzularning ro'yxati va namunaviy veb-sahifalarni taqdim etishi mumkin bo’lgan Ochiq Katalog Loyihasi(OKL)(Open Directory Project(ODP), kabi resursdan foydalanish orqali erishish mumkin. Sahifa Reytinggi(PageRank) tenglamalari o'zgartirildi, shuning uchun teleportatsiya qilish aynan ushbu namunaviy veb-hujjatlar to'plamida amalga oshiriladi, veb-hujjatlarning butun hujjatlar uchun maydonida emas. Deylik, ep, n o'lchovli shaxsiylashtirish vektori (ustun) bo'lsin, har bir sahifa uchun bitta yozuv bilan,. Agar ushbu sahifa namunaga kiritilgan bo'lsa, ep-dagi yozuv 1 qiymatini oladi, aks holda 0.
ep dagi nolga teng bo'lmagan yozuvlar soni np bilan belgilansin.
PageRank Eq. 18.4-formula quyidagicha o’zgaradi:
(18.7)
Xuddi shu quvvatni takrorlash (power iteration) usulidan Shaxsiylashtirilgan saxifa reytingi (PageRank) muammosini hal qilish uchun foydalanish mumkin.
Tanlangan teleportatsiyalar tasodifiy tanlashni amalga oshiradi, shuning uchun namunadagi sahifalarning strukturaviy joylashuvining ichidagi sahifalar yuqori o'rinni egallaydi.
Toki sahifalar namunasi, turli (tuzilmaviy) joylarining Veb-grafikning yaxshi vakili bo’lar ekan, qaysiki sahifalarida ayni mavzular mavjud bo'lsa, bunday yondashuv yaxshi ishlaydi. Shuning uchun, har xil mavzularning xar biri uchun, alohida PageRank vektorini so'rov vaqtida foydalanish uchun oldindan hisoblash va saqlash mumkin.
Ba'zi hollarda, foydalanuvchi mavzularning o'ziga xos kombinatsiyasi qiziqish bildiradi, masalan: sport va avtomobillar kabi. Shubhasiz, mumkin bo'lgan qiziqishlar kombinatsiyasi soni juda katta bo'lishi mumkin va har bir shaxsiylashtirilgan PageRank vektorini oldindan saqlash, zarur yoki oqilona hisoblanmaydi. Bunday hollarda faqat asosiy mavzular uchun PageRank vektorlari hisoblab chiqiladi. Yakuniy natija foydalanuvchi uchun mavzuga oid PageRank vektorlarining muhimlilik chiziqli birikmasi sifatida aniqlanadi, bu erda muhimlilik foydalanuvchi tomonidan turli mavzularga bo'lgan qiziqish bilan belgilanadi.
18.4.1.2 SimRank
SimRank(simmetrik reyting) tushunchasi tugunlar orasidagi strukturaviy o'xshashlikni hisoblashni anglatadi. SimRank tugunlar orasidagi simmetrik o'xshashlikni aniqlaydi. Boshqacha aytganda, i va j tugunlari orasidagi o'xshashlik j va i tugunlari bilan bir xil. SimRankni muhokama qilishdan oldin, biz shunga aloqador, ammo bir oz farq qiladigan assimetrik reyting masalani ko’rib chiqamiz:
G = (N, A) grafikdan iq tugun va S ⊆ N tugunlar to’plami berilgan, S to’plamdagi tugunlarni iq nisbatan o’xshashlikdagi ketma-ketlikda reytinglang.
Bunday so'rov, foydalanuvchilar va elementlar ikki tomonlama afzalliklarning grafigi shaklidagi tartibga solinadigan tavsiya tizimlarida juda foydali, bunda tugunlar foydalanuvchilar va elementlarga, qirralar esa afzalliklariga to’g’ri keladi.
iq tugun, element tuguniga to’g’ri kelishi mumkin, va S to'plami foydalanuvchi tugunlariga mos kelishi mumkin. Shu bilan bir qatorda, iq tugun foydalanuvchi tuguniga to’g’ri kelishi mumkin va S to'plami element tugunlariga mos kelishi mumkin. Tavsiya qiluvchi tizimlar haqida 18.5. bo'limida muhokama qilinadi. Tavsiya tizimlari qidiruv bilan chambarchas bog'liq, ya'ni ular ham ob'ektlarning reytingini amalga oshiradi, lekin foydalanuvchining afzalliklarini hisobga olgan holda.
Ushbu muammoni mavzuga aloqador PageRankning cheklovchi holati sifatida ko'rish mumkin, unda teleportatsiya yagona tugun iq ga amalga oshiriladi. Shuning uchun, shaxsiylashtirilgan PageRank 18.7-formula teleportatsiya vektori ep = eq, ya'ni bu bitta iq tuguniga mos keladigan 1dan tashqari barcha 0 larning vektori hisoblanadi.
Bundan tashqari, np qiymati bu holda 1 ga o'rnatiladi:
π = αe q + (1 - α)P T π (18.8)
Yuqorida aytib o'tilgan tenglamaning yechimi iq ning strukturaviy joylashuvidagi tugunlarga yuqori darajali qiymatlarni beradi. O'xshashlikning bu ta'rifi assimetrikdir, chunki i so'rov tugunidan boshlab j tuguniga tayinlangan o'xshashlik qiymati, j so'rov tugunidan boshlab i tuguniga berilgan o'xshashlikdan qiymat farq qiladi. Bunday assimetrik o'xshashlik o'lchovi qidiruv tizimlari va tavsiya qiluvchi kabi so'rovlarga asoslangan ilovalar uchun mos keladi, lekin cheklovsiz tarmoqqa asoslangan ma'lumotlarni qidirish ilovalari uchun shart emas.
Simmetrik o’lcho’vlarni yaratish uchun ikkita mavzuga aloqador PageRank qiymatini qarama-qarshi yo'nalishda o'rtacha hisoblash mumkin bo'lsa-da, ba'zi ilovalarda tugunlar orasidagi simmetrik juftlik o'xshashligi talab qilinadi. SimRank usuli sodda va intuitiv yechimni taqdim etadi.
SimRank yondashuvi quyidagicha. In(i) i ning ichki bog‘lovchi tugunlarini ifodalasin. SimRank tenglamasi tabiiy ravishda quyidagi tarzda rekursiv tarzda aniqlanadi:
(18.9)
Bu yerda C (0, 1) dagi konstanta bo'lib, uni rekursiyaning o'ziga xos yemirilish tezligi sifatida ko'rish mumkin. Chegara sharti sifatida SimRank(i, j) qiymati
i = j bo'lganda 1 ga o'rnatiladi. Agar i yoki j ning ichki bog'lovchi tugunlari bo'lmasa, SimRank(i, j) qiymati 0 ga o'rnatiladi. SimRankni hisoblash uchun iterativ yondashuv qo'llaniladi. SimRank(i, j) qiymati 1ga ishga tushiriladi agar
i = j bo’lsa, aks holda 0 ga. Algoritm barcha tugun juftlari orasidagi SimRank qiymatlarini 18.9 tenglik yordamida iterativ ravishda yaqinlashuvga erishilgunga qadar yangilaydi.
SimRank tushunchasi tasodifiy o’lcho’v nuqtai nazaridan qiziqarli intuitiv talqinga ega. Ikkita tasodifiy internet foydalanuvchisini ko'rib chiqaylik, ular i va j tugunlaridan bir vaqtning o’zida uchrashgunlaricha orqaga qadam tashlab yurishdi. U holda ularning har biri tomonidan bajarilgan qadamlar soni tasodifiy o'zgaruvchi L(i, j) bo'ladi. Bunda SimRank(i, j), CL(i,j) ning kutilgan qiymatiga teng ekanligini ko'rsatish mumkin. C parchalanish doimiysi l uzunlikdagi tasodifiy yurishlarni C ning o'xshashlik qiymatiga xaritalash uchun ishlatiladi. E'tibor bering, chunki C < 1, kichikroq masofalar yuqori o'xshashlikka olib keladi va aksincha.
Tasodifiy o’lcho’vga asoslangan usullar odatda tugunlar orasidagi o'xshashlikni o'lchash uchun, eng qisqa yo'l masofasidan ko'ra yaxshiroqdir. Buning sababi shundaki, tasodifiy yurish o'lchovlari tugunlar orasidagi yo'llar sonini bilvosita hisobga oladi, eng qisqa yo'llar esa yo'q. Batafsil bu masalani muhokamani 3. bo'limning 3.5.1.2-bob. da topish mumkin.
|
| |
