Аналіз гіперпосилань в Web

1. Алгоритми аналізу гіперпосилань дозволяють механізмам пошуку створювати адекватні результати у відповідь...
2. Збір Web-сторінок
3. Ранжування обраних документів
4. Ранжування на основі зв'язків
5. Ранжування, яке залежить від запиту
6. Ранжування, залежне від запиту
7. висновок
8. література
9. Використання аналізу гіперпосилань для добування інформації з Web
10. Пошук за зразком
11. віддзеркалювати хости
12. Класифікація Web-сторінок
13. Країни, в яких
14. література

Алгоритми аналізу гіперпосилань дозволяють механізмам пошуку створювати адекватні результати у відповідь на запити користувачів. У статті розглядаються алгоритми ранжирування, використовувані при добуванні інформації з Web.

Витяг інформації (information retrieval) - це область комп'ютерних технологій, яка ставить собі за мету пошук всіх документів з даного безлічі, що відповідають умовам запиту користувача. В цьому випадку вилучення інформації, насправді, слід назвати вилученням документів. До появи Web системи вилучення інформації, як правило, встановлювалися в бібліотеках, де вони зазвичай використовувалися бібліографами-консультантами. Алгоритм вилучення в цих системах, в основному, базувався на аналізі слів в документі.

Всесвітня павутина все змінила. Тепер кожен користувач Web може звертатися до різноманітних механізмів пошуку, алгоритми вилучення в яких часто аналізують не тільки слова в документах, але і таку інформацію, як структура гіперпосилань Web або теги мови розмітки.

Навіщо потрібні гіперпосилання? Сама по собі гіперпосилання (т. Е. Гіперпосилання на Web-сторінку B, що міститься в Web-сторінці A) для добування інформації прямої користі не дає. Однак спосіб застосування гіперпосилань, який автори Web-сторінки використовують, дозволяє отримати адекватне інформаційне наповнення. Як правило, автори оформляють гіперпосилання, які, на їхню думку, можуть бути корисні читачам. Деякі з гіперпосилань надають допомогу в навігації, наприклад, дозволяють повернутися на домашню сторінку сайту; інші забезпечують доступ до документів, що доповнює інформацію, розміщену на поточній сторінці. Останні, як правило, вказують на дуже важливі сторінки, присвячені тій же темі, що і сторінка, що містить гіперпосилання. Системи вилучення інформації в Web можуть використовувати ці дані для поліпшення якості пошуку необхідних документів.

Аналіз гіперпосилань значно збільшує релевантність результатів пошуку, причому настільки, що всі провідні механізми пошуку в Web в тій чи іншій мірі використовують аналіз гіперпосилань. Однак компанії, що реалізують механізми пошуку, які не повідомляють подробиці про те, який вид аналізу гіперпосилань вони виконують. Це робиться головним чином для того, щоб запобігти різного роду маніпуляції з результатами пошуку, до яких вдаються компанії, що займаються позиціонуванням в Web.

Аналіз гіперпосилань в Web

В основу алгоритмів аналізу гіперпосилань належить одне або обидва з наступних припущень.

• Допущення 1. Гіперпосилання зі сторінки A на сторінку B - це свого роду рекомендація автора сторінки A.
• Допущення 2. Якщо сторінка A і сторінка B пов'язані гіперпосиланням, вони можуть бути присвячені одній і тій же темі.

Аналіз гіперпосилань при добуванні інформації в Web застосовується, в основному, в двох випадках - для «повзання» (crawling) і для «ранжирування» (ranking). Крім того, аналіз гіперпосилань використовується для обчислення географічних кордонів Web-сторінки, пошуку віддзеркалювати хостів і обчислення статистичних даних сторінок Web і механізмів пошуку. Ці можливості описані в урізанні «Використання аналізу гіперпосилань для добування інформації з Web».

Збір Web-сторінок

Повзання - це процес збору Web-сторінок. Витяг інформації з Web відрізняється від класичного вилучення інформації тим, що початкового безлічі сторінок не існує і механізм пошуку в Web «знайти» документи, які увійдуть до цього безліч. Процес «повзання» (crawling) зазвичай починається з деякого безлічі вихідних Web-сторінок. Повзун (Web crawler) переміщається по гіперпосиланням вихідних сторінок в пошуках додаткових Web-сторінок. Розробники механізмів пошуку використовують метафору «повзання» павука стосовно створення гіперпосилань в Web. Цей процес повторюється з кожним новим набором сторінок і триває до тих пір, поки не перестануть з'являтися нові сторінки, або поки не буде зібрано зумовлене кількість сторінок. Повзун повинен вирішити, в якому порядку збирати сторінки з гіперпосиланнями, які ще не були перевірені. Повзуни різних механізмів пошуку приймають різні рішення і, таким чином, створюють різні набори Web-документів. Наприклад, повзун може спробувати спочатку обійти тільки Web-сторінки «високої якості». Для цього він поміщає всі виявлені, але не переглянуті сторінки в пріоритетну чергу, впорядковуючи їх за якістю.

Аналіз гіперпосилань дає кошти оцінки якості сторінок. Наприклад, згідно з першим допущенню алгоритмів аналізу гіперпосилань, сторінки, на які є посилання з багатьох сторінок, мають більш високу якість, ніж сторінки, на які вказує менше число сторінок. Це означає, що число гіперпосилань на дану сторінку може використовуватися для вимірювання якості. З іншого боку, в якості такого заходу може використовуватися PageRank [1], описаний далі.

Ранжування обраних документів

Коли користувач надсилає запит механізму пошуку, то останній повертає URL-адреси документів, в яких є все або хоча б один з термінів, в залежності від оператора запиту і алгоритму, що застосовується механізмом пошуку. Ранжування - це процес розміщення отриманих документів в порядку зниження їх релевантності, т. Е. Таким чином, що «найкращі» відповіді знаходяться на початку списку.

Класичне вилучення інформації, як правило, використовує алгоритми ранжирування виключно в залежності від слів, наявних в документах. Одним з таких алгоритмів є модель векторного простору, представлена Салтон і іншими [2]. Розглядається багатовимірне векторний простір, де кожному терміну відповідає свій вимір. Кожен документ або запит представлений вектором терміна в цьому векторному просторі. Входження термінів, що зустрічаються в документі позитивні, а входження термінів, які не зустрічаються в документі, дорівнює нулю. А саме, входження терміна зазвичай являє собою функцію, яка росте в залежності від частоти вживання терміна в документі і убуває в залежності від числа документів в наборі, що містить цей термін. Ідея полягає в тому, що чим більше документів, в яких присутній цей термін, тим в меншій мірі термін характеризує даний документ, і чим частіше термін зустрічається в документі, тим більшою мірою він характеризує документ. Вектора термінів документів можуть бути нормалізовані з урахуванням різної довжини документів. Адекватність документа запиту (релевантність) зазвичай обчислюється як скалярний твір їх векторів термінів. Для даного запиту кожному з документів присвоюється ненегативний показник. Щоб отримати відповідь на запит, документи з позитивними значеннями повертаються в порядку убування їх показників.

Чому класичні методи добування інформації не виправдовують себе в Web? Багато авторів Web-сторінок зацікавлені в тому, щоб їх сторінки у відповідях на певні запити мали високий рейтинг. Таким чином, щоб збільшити рейтинг, автори будуть по-різному «підкручувати» свої сторінки. Ці спроби маніпулювання алгоритмом ранжирування іноді доходять аж до того, що додаються фрагменти тексту, набрані невидимим шрифтом. Наприклад, якщо для ранжирування використовується модель векторного простору, додавання на сторінку 1000 слів «машина» збільшить рейтинг даної сторінки при пошуку за запитом «машина». Існують навіть агентства Web-маркетингу, які заробляють гроші, даючи поради своїм клієнтам, яким чином можна «поліпшити» результати ранжирування механізмів пошуку.

Будь алгоритм, який базується виключно на вмісті сторінки, сприйнятливий до такого роду маніпуляцій. Дієвість аналізу гіперпосилань проявляється в тому, що він використовує для визначення рейтингу поточної сторінки інформаційне наповнення інших сторінок. Якщо припустити, що ці сторінки були створені авторами незалежно від автора вихідної сторінки, то об'єктивність упорядкування при такому підході зростає.

Ранжування на основі зв'язків

Схеми ранжирування на основі зв'язків можна розділити на два класи:

• схеми, які не залежать від запитів, які привласнюють показник сторінці незалежно від даного запиту;
• схеми, що залежать від запитів, в яких показник присвоюється сторінці в контексті даного запиту.

Схеми ранжирування, що залежать від запитів, привласнюють показник документу один раз, а потім використовують цей показник для обробки всі майбутні запити. Схеми ранжирування, що залежать від запитів, вимагають виконання аналізу гіперпосилань для кожного запиту, але при цьому сам аналіз гіперпосилань адаптується спеціально для кожного запиту.

Щоб спростити опис представлених тут алгоритмів, спочатку слід змоделювати набір Web-сторінок у вигляді графа. Це можна зробити різними способами. Методи ранжирування на основі зв'язків зазвичай припускають найочевидніше уявлення: кожна Web-сторінка в наборі моделюється вузлом графа. Якщо сторінка A містить гіперпосилання на сторінку B, то в графі є направлене ребро (A, B). Якщо A не має гіперпосилання на B, спрямованого ребра (A, B) не існує. Цей спрямований граф називається графом посилань G.

Деякі алгоритми використовують ненаправленої граф коцітірованія (co-citation graph). У ненаправленим графі цитування вузли A і B пов'язані ненаправленим ребром тоді і тільки тоді, коли існує третя сторінка C, яка має гіперпосилання на A і на B. Кажуть, що A і B коцітіруются за допомогою C.

Граф зв'язків використовується для ранжирування, пошуку пов'язаних сторінок і вирішення інших завдань вилучення документів. Граф коцітірованія використовується для класифікації та пошуку пов'язаних сторінок.

Ранжування, яке залежить від запиту

Ранжування, яке залежить від запиту, служить для визначення «істинного» якості сторінок. В цьому випадку показник присвоюється кожній сторінці незалежно від конкретного запиту користувача. Під час обробки запиту цей показник використовується (з урахуванням або без урахування критерію ранжирування, що залежить від запиту) для ранжирування всіх документів, що відповідають умовам запиту.

Перше припущення методів на основі зв'язків породжує простий критерій: чим більше гіперпосилань вказує на сторінку, тим краще ця сторінка. Основний недолік такого підходу полягає в тому, що він не робить різниці між якістю сторінки, на яку вказує кілька сторінок низької якості і якістю сторінки, на яку вказує те ж число сторінок високої якості. Очевидно, що рейтинг сторінки можна збільшити, просто створивши безліч інших сторінок, що посилаються на дану.

Брін і Пейдж розробили алгоритм PageRank, що дозволяє вирішити цю проблему [3, 4]. Вони обчислюють коефіцієнт PageRank кожної сторінки, привласнюючи кожному посиланні на сторінку ваговий коефіцієнт пропорційний якості сторінки, що містить гіперпосилання. Щоб визначити якість посилається, вони використовують її коефіцієнти PageRank рекурсивно, причому початкові значення PageRank задаються довільно. Точніше, R (A) - коефіцієнт PageRank сторінки A можна визначити як

Ця формула показує, що коефіцієнт PageRank сторінки A залежить від PageRank сторінки B, що вказує на A. Оскільки визначення PageRank породжує таке лінійне рівняння для кожної сторінки, щоб обчислити PageRank для всіх сторінок, необхідно вирішити величезну кількість лінійних рівнянь.

PageRank дозволяє ефективно відрізнити високоякісні сторінки Web від низькоякісних, і даний параметр використовується в механізмі пошуку Google.

Ранжування, залежне від запиту

При ранжируванні, що залежить від запиту, алгоритм привласнює показник, який змінює якість і адекватність обраного безлічі сторінок для даного запиту користувача. Основна ідея полягає в тому, щоб створити граф для кожного конкретного запиту, званий графом сусідів і виконати з цього графу аналіз гіперпосилань. В ідеалі цей граф буде містити тільки сторінки по темі, зазначеної в запиті користувача.

Керіер і Кацман пропонують наступний підхід до створення графа сусідів [5].

• Початкове безліч документів, що відповідають запиту, формується механізмом пошуку.
• Початкове безліч розширюється за рахунок своїх «сусідів», до яких відносяться або документи, на які є посилання зі сторінок, що входять в початкове безліч, або документи, що посилаються на елементи початкового безлічі (див. Малюнок 3). Оскільки кількість вхідних вузлів (indegree), т. Е. Число документів, що мають посилання на хоча б один документ з початкового безлічі, може бути дуже великим, на практиці включається лише обмежене число цих документів, скажімо, 50.
• Кожен документ в початковому безлічі і безлічі сусідів моделюється вузлом. Ребро їх вузла A в вузол B існує тоді і тільки тоді, коли документ A має гіперпосилання на документ B. Гіперпосилання між сторінками одного і того ж Web-хоста іноді пропускаються, оскільки автори можуть виявитися колегами і така гіперпосилання може не задовольняти вказаним вище першого допущенню .

У графі сусідів можуть застосовуватися різні схеми ранжирування. Як і у випадку зі схемами ранжирування, що не залежать від запитів, підхід на основі вхідних вузлів [5] впорядковує вузли в графі сусідів в залежності від числа документів, що мають на них гіперпосилання. І знову-таки, при такому підході все гіперпосилання вважаються рівнозначними.

Графи сусідів, як правило, складаються з декількох тисяч вузлів (т. Е., Відносно невеликі). Обчислення PageRank на графі сусідів породжує ранжування аналогічне тому, яке виконується при ранжування по «вхідним» вузлів [6].

Інший підхід до ранжирування сторінок в графі сусідів передбачає, що інформація по темі може розподілитися приблизно порівну між сторінками з хорошим інформаційним наповненням по темі, званим «авторитетами», і сторінками, що нагадують каталоги, з безліччю посилань на інші сторінки, присвячені даній темі, звані «концентраторами» [7].

Алгоритм Кляйнберг пошуку документів по заданій темі на базі гіперпосилань (hyperlink-induced topic search - HITS) намагається виявити хороші концентратори і авторитети [7]. З урахуванням призначеного для користувача запиту алгоритм итеративно обчислює показник концентрації і авторитетності для кожного вузла графа сусідів, а потім впорядковує вузли в Відповідно до цих показників. Вузли, що мають високі показники авторитетності, повинні бути хорошими авторитетами, а вузли з високими показниками концентрації повинні бути хорошими концентраторами. Алгоритм виходить з того, що документ, який посилається на велику кількість інших документів - хороший концентратор, а документ, на який вказує безліч інших документів - хороший авторитет. Рекурсивно, документ, який вказує на велике число хороших авторитетів - ще кращий концентратор, а документ, на який посилається безліч хороших концентраторів - ще кращий авторитет. Це дає наступний рекурсивний алгоритм.

Елементарні обчислення показують, що вектори Hub і Aut в кінцевому підсумку будуть сходитися, але обмеження на число ітерацій не відомо. На практиці, вектори сходяться дуже швидко.

Зауважимо, що алгоритм не стверджує, що будуть знайдені всі високоякісні сторінки, що задовольняють умовам запиту, оскільки деякі з таких сторінок можуть не належати графу сусідів або входити до його складу, але не мати посилань з багатьох сторінок.

У зв'язку з алгоритмом HITS виникає дві проблеми.

• Оскільки розглядається відносно невелика частина графа Web, додавання ребер до декільком вузлам може серйозно змінити показники концентраторів і авторитетів [8]. В силу чого маніпулювати цими показниками досить просто. Як уже зазначалося, маніпуляція ранжированием механізму пошуку - серйозна проблема для Web.
• Якщо велика частина сторінок в графі сусідів відноситься до теми, яка відрізняється від теми запиту, авторитети і концентратори, які отримали високий рейтинг, можуть ставитися до іншої теми. Ця проблема називається «зміщенням теми». Додавання терезів до ребер з урахуванням тексту документів або їх тез значно пом'якшує негативний ефект цієї проблеми [9-11].

Наскільки відомо, алгоритм HITS зараз в комерційних пошукових системах не використовується.

висновок

Вивчення структури гіперпосилань Web тільки починається, і в майбутньому з'явиться ще більше чудових програм (подібно до тих, які описані в урізанні). Коли механізми пошуку в Web почали застосовувати аналіз гіперпосилань, компанії, що займаються Web-позиціонуванням, стали маніпулювати гіперпосиланнями, створюючи гіперпосилання, що дозволяють збільшити рейтинг сторінок їхніх клієнтів, тим самим перешкоджаючи механізмам пошуку в Web повертати високоякісні результати. Щоб компенсувати таке спотворення, компаніям, які підтримують механізми пошуку в Web, доводиться створювати більш досконалі методи і зберігати їх в таємниці, оскільки будь-яка нова інформація стимулює нові спроби маніпулювання.

література

[1] J. Cho, H. Garcia-Molina, and L. Page, «Efficient Crawling through URL Ordering», Proc. Seventh Int? L World Wide Web Conf., Elsevier Science, New York, 1998..
[2] G. Salton et al., «The SMART System-Experiments in Automatic Document Processing», Prentice-Hall, Englewood Cliffs, NJ, 1971
[3] S. Brin and L. Page, «The Anatomy of a Large-Scale Hypertextual Web Search Engine», Proc. Seventh Int? L World Wide Web Conf., Elsevier Science, New York, 1998.
[4] L. Page et al., «The PageRank Citation Ranking: Bringing Order to the Web», Stanford Digital Library Technologies, Working Paper 1999-0120, Stanford Univ., Palo Alto, Calif., 1998.
[5] J. Carriere and R. Kazman, «Webquery: Searching and Visualizing the Web through Connectivity», Proc. Sixth Int? L World Wide Web Conf., Elsevier Science, New York, 1997.
[6] B. Amento, L. Terveen, and W. Hill, «Does Authority Mean Quality? Predicting Expert Quality Ratings of Web Documents », Proc. 23rd Int? L ACM SIGIR Conf. Research and Development in Information Retrieval (SIGIR 00), ACM Press, New York, 2000.
[7] J. Kleinberg, «Authoritative Sources in a Hyperlinked Environment», Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, ACM Press, New York, 1998.
[8] R. Lempel and S. Moran, «The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect», Proc. Ninth Int? L World Wide Web Conf., Elsevier Science, New York, 2000.
[9] S. Chakrabarti et al., «Experiments in Topic Distillation», Proc. ACM SIGIR Conf. Research and Development in Information Retrieval (SIGIR 98), Post-Conference Workshop on Hypertext Information Retrieval for the Web
[10] S. Chakrabarti et al., «Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text», Proc. Seventh Int? L World Wide Web Conf., Elsevier Science, New York, 1998.
[11] K. Bharat and M. Henzinger, «Improved Algorithms for Topic Distillation in Hyperlinked Environments», Proc. 21st Int? L ACM SIGIR Conf. Research and Development in Information Retrieval (SIGIR 98), ACM Press, New York, 1998.

Моніка Хензінгер ( [email protected] ) - директор з досліджень компанії Google, що пропонує механізми пошуку в Web наступного покоління. До області її наукових інтересів належать питання вилучення інформації, Web-аналіз і алгоритміка.

Monika R. Henzinger, Hyperlink Analysis for the Web. IEEE Internet Computing, January / February 2001. IEEE CS, 2001. All rights reserved. Reprinted with permission.

Використання аналізу гіперпосилань для добування інформації з Web

Структура гіперпосилань в Web може використовуватися не тільки для аналізу якості Web-сторінки. Вона також корисна для пошуку Web-сторінок, аналогічних цієї Web-сторінці або Web-сторінок, цікавих для даного географічного регіону. Нижче описані ці та інші можливості застосування аналізу гіперпосилань для вилучення інформації.

Пошук за зразком

Підхід до вилучення інформації в Web, званий пошуком за зразком, передбачає вибір сторінок, схожих на дану сторінку. Наприклад, за даною www.nytimes.com , знайти www.washington-post.com и www.wsj.com . В цьому випадку добре працюють і алгоритм HITS, і простий алгоритм пошуку по графу цитування [1, 2]. Останній алгоритм заснований на тому, що частота цитування показує схожість, особливо в тих випадках, коли посилання на сторінці розміщені близько один до одного. Таким чином, сторінки з множинним цитуванням, при якому посилання на сторінці цитуючи розташовуються близько один до одного, як правило, схожі.

віддзеркалювати хости

Маршрутне ім'я Web-сторінки - це частина URL, наступна за адресою хоста, т. Е. Після третього символу /. Наприклад, якщо URL сторінки http://www.google.com/about.html , То адреса www.google.com - це адреса хоста, а /about.html - маршрутне ім'я. Два хоста, H1 і H2, є дзеркалами тоді і тільки тоді, коли для кожного документа на H1 існує дуже схожий документ на H2 з одним і тим же шляхом, і навпаки.

Дзеркала мають дуже схожу структуру гіперпосилань всередині хоста і між віддзеркалювати хостом і іншими хостами. Віддзеркалювати Web-хости займають місце в індексному структурі даних і можуть привести до дублювання результатів. Поєднання аналізу гіперпосилань з аналізом IP-адрес і аналізом шаблонів URL дозволяє виявити безліч практично дзеркальних хостів [3].

Класифікація Web-сторінок

Аналіз гіперпосилань може використовуватися для обчислення в групах Web-сторінок статистичних даних, таких як середня довжина, частка інформації на французькій мові і тому подібних показників. Випадкове блукання, аналогічне алгоритму PageRank, може бути виконано на Web для відбору зразків Web-сторінок при майже нормальному розподілі [4]. Ці майже випадкові вибірки можуть потім використовуватися для визначення різних властивостей Web-сторінок, а також для того, щоб порівняти число сторінок в індексах різних комерційних механізмах пошуку. Наприклад, в листопаді 1999 року за допомогою цієї методики було з'ясовано, що майже 47% всіх Web-сторінок належать домену .com.

Країни, в яких

Чи буде дана Web-сторінка цікава тільки людям, які проживають в даному регіоні, в конкретній країні або по всьому світу - важливе завдання аналізу гіперпосилань. Наприклад, сторінка з прогнозом погоди цікава тільки людям, які проживають в регіоні, дані про який на цій сторінці розміщуються, в той час як Web-сторінка Служби внутрішніх доходів (американське податкове відомство - Прим. Ред.) Може бути цікава американським платникам податків по всьому світу . Структура гіперпосилань сторінки також відображає діапазон цього інтересу [5, 6]. Локальні сторінки в основному мають гіперпосилання на сторінки з одного і того ж регіону, в той час як гіперпосилання на сторінки, що представляють національний інтерес, приблизно рівномірно розподілені по всій країні. Ця інформація дозволяє механізмам пошуку налаштовувати результати, які генеруються у відповідь на запит, з урахуванням того регіону, де знаходиться користувач.

література

[1] J. Kleinberg, «Authoritative Sources in a Hyperlinked Environment», Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms, ACM Press, New York, Jan. 1998
[2] J. Dean and MR Henzinger, «Finding Related Web Pages in the World Wide Web», Proc. Eighth Int? L World Wide Web Conf., Elsevier Science, New York, 1999.
[3] K. Bharat et al., «A Comparison of Techniques to Find Mirrored Hosts on the World Wide Web», J. American Soc. for Information Science, Vol. 51, No.12, Nov. 2000
[4] MR Henzinger et al., «On Near-Uniform URL Sampling», Proc. Ninth Int? L World Wide Web Conf., Elsevier Science, Amsterdam, 2000.
[5] O. Buyukkokten et al., «Exploiting Geographical Location Information of Web Pages», Proc. ACM SIG-MOD Workshop on the Web and Databases (WebDB 99), INRIA, Philadelphia, 1999.
[6] J. Ding, L. Gravano, and N. Shivakumar, «Computing Geographical Scopes of Web Resources», Proc. 26th Int? L Conf.Very Large Databases (VLDB 00), Morgan Kaufmann, San Francisco, 2000.