|
HITS
Gipermatnli mavzularni qidirish (HITS
|
| bet | 2/10 | | Sana | 16.05.2024 | | Hajmi | 345,87 Kb. | | #237900 |
Bog'liq Mustaqil ish 418.4.2 HITS
Gipermatnli mavzularni qidirish (HITS. The Hypertext Induced Topic Search) algoritmi sahifalarni tartiblash uchun soʻrovga bogʻliq algoritmdir. Yondashuv ortidagi sezgi, markazlar(HUB) va ma’muriyat(Authority)dan tashkil etilgan Internetning odatiy tuzilishini tushunishda yotadi.
Ma’muriyat - bu juda ko'p havolalarga ega sahifa. Odatda, u ma'lum bir mavzu bo'yicha ishonchli tarkibni o'z ichiga oladi va shuning uchun ko'plab veb-foydalanuvchilar ushbu sahifaga ishonchli manba sifatida qarashlari mumkin.
Markaz va Ma’muriyatga misollar (b) Aloqa tashkiloti markaz va ma’muriyat o’rtasidagi
18.3 rasm. Markaz va Ma’muriyat
Bu avtoritet sahifasiga bog'langan ko'plab sahifalarga olib keladi.
A markaz(hub) - bu rasmiylarga ko'plab havolalarga ega sahifa. Bular ma'lum bir mavzu bo'yicha havolalar to'plamini ifodalaydi. Shunday qilib, markaz sahifasi veb-foydalanuvchilarga ma'lum bir mavzu bo'yicha resurslarni qaerdan topishlari mumkinligi haqida ko'rsatmalar beradi. Veb-grafikdagi markazlar va vakolatlarning tipik tugun-markazli topologiyasiga misollar 18.3a-rasmda ko'rsatilgan.
Gipermatnli mavzularni qidirish (HITS) algoritmi tomonidan qo'llaniladigan asosiy tushuncha shundaki, yaxshi joylashgan markazlar ko'plab yaxshi ma’muriyatga ishora qiladi. Aksincha, yaxshi ma’muriyat sahifalar ko'plab markazlar tomonidan ko'rsatiladi. Hublar va hokimiyatlarning odatiy tashkil etilishiga misol 18.3b-rasmda ko'rsatilgan. Ushbu o'zaro mustahkamlovchi munosabatlar Gipermatnli mavzularni qidirish (HITS) algoritmi tomonidan qo'llaniladi. Foydalanuvchi tomonidan berilgan har qanday so'rov uchun Gipermatnli mavzularni qidirish (HITS) algoritmi tegishli sahifalar ro'yxatidan boshlanadi va ularni markaz reytingi va vakolatlar reytingi bilan kengaytiradi.
HITS algoritmi ayni shu vaqtdagi qidiruv so'roviga eng mos keladigan top-r natijalarni to'plashdan boshlanadi. r ning odatiy qiymati 200. Bu ildiz to'plamini R ni belgilaydi. Odatda, ildiz to'plamini aniqlash uchun tijorat qidiruv tizimiga so'rov yoki kontentga asoslangan baholash ishlatiladi. R dagi har bir tugun uchun, algoritm R ga darhol ulangan barcha tugunlarni (ichki bog’langan yoki tashqi bog’langan) aniqlaydi. Bu kattaroq S tayanch to'plamini ta'minlaydi. Chunki S tayanch to'plami ancha katta bo'lishi mumkin, S ga qo'shilgan R ning istalgan tuguniga ulanish tugunlarining maksimal soni k bilan cheklangan. Amaldagi k ning odatiy qiymati 50 ga yaqin. E'tibor berish kerakki, bu ancha katta baza to'plamiga tashkil qiladi, chunki 200 ta ildiz tugunlarining har biri tashqi bog’lovchi tugunlar bilan birga 50 ta ichki bog'lovchi tugunlar olib kelishi mumkin.
G = (S, A) S (kengaytirilgan) tayanch to'plamida aniqlangan veb-grafaning pastki grafigi bo'lsin, bu erda A - S ildiz to'plamidagi tugunlar orasidagi qirralar to'plami. HITS algoritmining butun tahlili cheklangan. ushbu subgraf. Har bir sahifa (tugun) i ∈ S, ham markaz ko’rsatgichi h(i) ham ma’muriyat ko’satgichi a(i) biriktirilgan. Markaz va ma’muriyat ko'rsatkichlari normallashtirilgan deb taxmin qilinadi, shuning uchun markaz ko’rsatgich kvadratlari yig'indisi va ma’muriyat kvadratlarning yig'indisi har biri 1 ga teng.
Ko’rsatgichlarning yuqori qiymatlari sifatni yaxshiroq ko'rsatadi.
Markaz va ma’muriyat ko’rsatgichlari bir-biri bilan quyidagi tarzda bog'langan:
Asosiy g'oya, markazlarni yaxshi ma’muriyatga ko'rsatgani uchun mukofotlash va ma’muriyatni yaxshi markazlar tomonidan ko'rsatilgani uchun mukofotlash. Yuqorida aytib o'tilgan tenglamalar tizimi bu o'zaro mustahkamlovchi munosabatlarni mustahkamlashini ko'rish mumkin. Bu iterativ usul yordamida yechilishi mumkin bo'lgan chiziqli tenglamalar tizimi.
Algoritm h0(i) = a0(i) = 1/ ni ishga tushurishdan boshlandi. Aytaylik ht(i) va at(i) lar mos ravishda, t-iteratsiya oxirgi va i-tugunning hub va ma’muriyat ko’rsatgichlarini bildirsin.
Har bir t ≥ 0 uchun algoritm (t + 1) iteratsiyada quyidagi iterativ bosqichlarni bajaradi:
har bir i ∈ S uchun belgilanadi;
har bir i ∈ S uchun belgilanadi;
Markaz va ma’muriyat har birining L2-normasini vektorlarining 1 ga normallashtirish;
Hub-vektor uchun h = [h(1) . . . h(n)]T va avtoritet-vektor a = [a(1) . . . a(n)]T , yangilanishlar mos ravishda a = AT h va h = Aa sifatida ifodalanishi mumkin, A chekka to'plami sifatida qaralganda |S| × |S| qo'shnilik matritsasi. Takrorlash konvergentsiyaga qadar takrorlanadi. Ko'rsatish mumkin hub vektor h va avtoritet a vektori mos ravishda AAT va AT A ning dominant xos vektorlariga proportsional yo'nalishlarda yaqinlashadi (6-mashqga qarang). Buning sababi shundaki, tegishli yangilanishlar juftligi AAT ning quvvatli iteratsiya va mos ravishda AT A angilanishlariga ekvivalent bo'lishi mumkin.
|
| |
