Главная   О компании   Разработки   АТ.Трейдинг  


АТ.Поиск   Сервисы   Форум

Статистические методы исследования алгоритмов текстового ранжирования поисковых систем.

Илья Зябрев, Олег Пожарков, 14.02.2010

Данный доклад был прочитан 27.11.2009 г. на конференции "Поисковая оптимизация и продвижение сайтов в Интернете 2009" и дополнен новыми данными в феврале 2010 г.



Одной из задач, возникающих в процессе продвижения сайта, является оптимизация структуры страниц. Как правило, решение этой задачи происходит вслепую, так как алгоритмы текстового ранжирования поисковых систем неизвестны. Поэтому проблема идентификации основных принципов, влияющих на формирование выдачи того или иного поисковика, довольно актуальна и важна.

Поисковые системы, как «черные ящики»

Любая поисковая система с точки зрения исследователя является, по сути, «черным ящиком», на «входы» которого мы можем воздействовать и получать на «выходе» результат, не имея представления о том, что при этом происходит внутри. Но для того, чтобы определить основные принципы функционирования такой системы, необязательно знать ее внутреннее устройство. В случае с поисковыми системами мы имеем дело с практически неограниченным множеством входных и выходных данных, анализируя которые можно составить представление об общих принципах их функционирования. За всю историю исследования «черных ящиков» наука выработала множество методов, простейшим из которых является статистический корреляционный анализ. Его цель, применительно к данной задаче, установить имеющиеся закономерности между входами и выходами системы. Входами поисковиков являются: множество страниц сети Интернет, запросы и их параметры, выходом – результат работы алгоритма ранжирования по запросу или «выдача». Использование автоматизированной системы позволяет накопить любой необходимый для анализа набор откликов поисковой системы на тестовые запросы.

Применяя к данным, полученным таким образом, корреляционный анализ, можно определять степень зависимости места в выдаче от той или иной характерной особенности структуры страниц. Если некоторая метрика имеет стабильно большой по модулю коэффициент корреляции для различных запросов, то можно предположить, что она определенно имеет сильное влияние на работу алгоритма текстового ранжирования исследуемой поисковой системы. Чтобы снизить влияние донорно-акцепторных связей на выдачу, для исследования следует выбирать «не интересные» с точки зрения поисковой оптимизации запросы.

Частотные метрики состава html-страниц

Как было сказано ранее, исходными данными для статистического исследования являются множества запросов и результатов ранжирования страниц, попавших на первые места выдач. По каждому запросу для страниц, попавших в топ, вычисляются различные числовые структурные характеристики. Это могут быть простые статистики, характеризующие распределение различных слов по тегам, более сложные частотно-зависимые характеристики и различные производные от них метрики.

В качестве простейших метрик можно использовать следующие:

Абсолютная теговая частота леммы слова – количество канонических форм слова в заданном теге html-страницы.
  (1)
- количество вхождений леммы слова L в заданный тег T.

Относительная теговая частота леммы слова – отношение абсолютной теговой частоты леммы слова к общему числу лемм заданного тега html-страницы.
  (2)

Различные производные от обратной частоты документа (IDF) или обратной частоты класса ICF метрик.
IDF(L)=D/DF(L)  (3),
где D-общее число документов коллекции, DF(L) - число документов, в которых встречается лемма L
ICF(L)=TCF/CF(L)  (4),
где TCF-общее число лемм коллекции, CF(L) - число вхождений леммы L во все документы коллекции.

Вопрос получения баз IDF/ICF – это отдельная и довольно сложная проблема, т.к. самостоятельный сбор данных для вычисления этих характеристик ресурсоемкая во многих смыслах задача. Более того, конкурировать с тем охватом сайтов, который доступен поисковым системам, крайне затруднительно. Но для решения задачи, которой посвящен настоящий доклад, этого не требуется. Во-первых, для анализа важны не абсолютные числовые значения величин, а относительные, т.к. в числителе каждой из этих характеристик стоит константа. Во-вторых, при достаточно большой и репрезентативной подборке страниц, на основе которых вычисляются метрики, полученные значения довольно близки к «истинным».

Нами для исследования использовалось несколько баз:

  • IDF-база сервиса miratools
  • IDF и ICF базы, вычисленные на основе коллекции ATR 2009, собранной нами при помощи собственных технологий.

Производных от IDF/ICF числовых характеристик можно придумать великое множество. Вот простейшие из них:

  • IDF(L)*N(L), IDF(L)*N%(L)  (5)
  •   (6),
    где li,j - все леммы j-го предложения, содержащего L, Lenj-количество слов j-го предложения.
  •   (7)

Для каждой характеристики вместо IDF(L) можно использовать ICF(L), log(IDF(L)), log(ICF(L)). Все перечисленные выше метрики вычисляются как для каждой леммы из запроса отдельно, так и для их совокупности.

Метод исследования принципов текстового ранжирования поисковых систем

Основу предлагаемого метода составляет корреляционный анализ, главная цель которого в данном случае - определение степени влияния различных характеристик на позицию страницы в результатах поиска. Суть корреляционного анализа заключается в следующем. Пусть существуют две величины Х и У, для которых известны соответствующие друг другу пары значений (Xi,Yi), i=1,2..N. На основе имеющихся данных вычисляется коэффициент корреляции:

Пирсона (для количественных величин)
  (8),
где - математическое ожидание величины Х.

Кенделла (для ранговых величин)
K = 2*S/N*(N-1)  (9),
где S=P-Q, P- суммарное число наблюдений, следующих за текущими наблюдениями с большим значением рангов Y, Q — суммарное число наблюдений, следующих за текущими наблюдениями с меньшим значением рангов Y.

Спирмена (для ранговых величин)
  (10),
где di=r(Yi)-r(Xi), r(X)-ранг Х.

Значения коэффициентов корреляции, диапазон изменения которых лежит в интервале от -1 до 1, говорят о связи следующим образом: модуль определяет степень связи между величинами (чем он больше, тем связь сильнее). Знак определяет характер связи. Положительное значение коэффициента говорит о том, что при увеличении Х, соответствующее значение Y будет возрастать, если коэффициент отрицателен, то – убывать. При этом выявленная связь будет носить не функциональный, а принципиальный характер.

Если взять за Х характеристику, влияние которой на ранжирование мы исследуем, а за Y - позиции документов в результатах поиска, то можно при помощи коэффициента корреляции определить степень и характер статистической связи между ними. Естественно, никакой функциональной зависимости между этими величинами быть не может, т.к. места это качественные (или ранговые) меры, а значения характеристик документа – количественные. Однако наличие статистической связи между ними может говорить о том, что в текстовом ранжировании исследуемая метрика или некоторая функция от нее имеет определенное влияние, сила которого определяется модулем коэффициента корреляции, а характер – знаком. Так как одна из величин ранговая, то целесообразно использовать ранговые коэффициенты корреляции, однако для сравнения влияния двух похожих характеристик, например IDF- и ICF-зависимых, можно использовать и коэффициент корреляции Пирсона.

Предлагаемый метод исследования принципов текстового ранжирования состоит из следующих этапов.

Этап 1. Формирования множества данных для анализа. Делается подборка запросов, максимально исключающая влияние ссылочного фактора. Например, запросы из непопулярных слов или запросы, задающие поиск по одному сайту. Чем больше различных запросов используется для проведения анализа, тем выше их статистическая значимость.

Этап 2. Вычисление числовых характеристик. Характеристики для исследования выбираются на основе проведенных предварительных наблюдений или возникающих в процессе исследования поисковых систем гипотез. В докладе представлены простейшие из них.

Этап 3. Вычисление коэффициентов корреляции. Ранговые коэффициенты вычисляются по формулам (9) или (10), а Пирсона по формуле (8), когда ранги исследуемых характеристик равны, а анализ носит сравнительный характер.

Этап 4. Анализ результатов. Если некоторая характеристика на различных запросах имеет устойчиво высокий по модулю коэффициент корреляции, то делается вывод о том, что она влияет на текстовое ранжирование. При этом если коэффициент больше нуля, то зависимость прямая (с увеличением характеристики, увеличивается место документа в результатах поиска), если меньше нуля – обратная (с увеличением характеристики уменьшается место документа в результатах поиска).

Стоит подчеркнуть, что точно определить формулу вычисления структурной характеристики, используемой в том или ином методе ранжирования, затруднительно. Поэтому, если некоторая метрика по результатам анализа признана влияющей на формирование выдачи, то это не значит, что она присутствует в алгоритме именно в таком же виде, но вероятность ее тесной связи с истинной характеристикой высока.

Представленные выше формулы (8)-(10) предназначены для вычисления коэффициентов парной корреляции, т.е. между двумя величинами. При расчете коэффициента для каждой из характеристик влияние других факторов не учитывается. Поэтому если в алгоритме ранжирования одновременно используется несколько факторов, коэффициенты парной корреляции для каждого из них будут невысоки. Для решения этой проблемы следует использовать множественные и частные коэффициенты корреляции. Рассмотрение этих статистик выходит за рамки данного доклада.

Пример использования метода для анализа алгоритма текстового ранжирования Яндекса.

На основе предложенного метода нами было проведено исследования алгоритма текстового ранжирования Яндекса. В таблицах 1-3 представлены результаты анализа.

Таблица 1. Коэффициенты корреляции для характеристик без учета тегов
Запрос12345678
гонор-0,523-0,495-0,644-0,484-0,673-0,549-0,497-0,097
банальность-0,3890,181-0,6380,173-0,6920,195-0,1840,083
клюв-0,712-0,249-0,654-0,246-0,674-0,250-0,241-0,046
зло-0,6280,318-0,6600,317-0,7070,3450,290-0,551
струпья-0,679-0,694-0,759-0,650-0,783-0,765-0,669-0,095
маньяк-0,417-0,635-0,738-0,601-0,861-0,687-0,694-0,322
подзатыльник-0,676-0,635-0,748-0,657-0,826-0,684-0,640-0,095
традиции-0,604-0,578-0,785-0,629-0,818-0,629-0,581-0,467
ученый-0,736-0,539-0,784-0,533-0,850-0,543-0,537-0,371
выдумка-0,405-0,660-0,827-0,667-0,905-0,713-0,698-0,582

Таблица 2. Коэффициенты корреляции для характеристик тега body
Запрос12345678
гонор-0,514-0,496-0,658-0,501-0,665-0,512-0,491-0,192
банальность-0,3440,181-0,6140,186-0,6500,188-0,1930,032
клюв-0,699-0,226-0,677-0,229-0,784-0,246-0,214-0,041
зло-0,6270,311-0,6570,302-0,6900,3250,291-0,647
струпья-0,424-0,442-0,520-0,451-0,528-0,485-0,440-0,068
маньяк0,151-0,618-0,789-0,588-0,801-0,680-0,683-0,368
подзатыльник-0,701-0,730-0,783-0,691-0,862-0,752-0,679-0,159
традиции-0,613-0,622-0,784-0,618-0,835-0,640-0,592-0,544
ученый-0,730-0,546-0,790-0,593-0,844-0,590-0,548-0,585
выдумка-0,407-0,664-0,837-0,672-0,954-0,732-0,690-0,561

Таблица 3. Коэффициенты корреляции для характеристик тега title
Запрос12345678
гонор0,0260,499-0,3560,483-0,3590,5360,416-0,445
банальность-0,3470,128-0,7250,129-0,7260,1310,178-0,537
клюв-0,065-0,054-0,169-0,049-0,183-0,057-0,349-0,631
зло0,1790,002-0,0020,002-0,0020,002-0,004-0,761
струпья-0,1700,333-0,4280,340-0,4800,3670,174-0,546
маньяк-0,210-0,536-0,436-0,571-0,462-0,545-0,179-0,568
подзатыльник-0,0140,122-0,3310,124-0,3530,1270,226-0,450
традиции0,2270,193-0,3600,182-0,3990,1950,256-0,443
ученый0,0000,748-0,2860,723-0,2980,7510,000-0,404
выдумка-0,0390,159-0,3410,166-0,3520,169-0,150-0,432

Номера столбцов в таблицах соответствуют характеристикам:

  • 1,2. Характеристики, вычисленные по формулам (6) на основе IDF сервиса miratools
  • 3,4. Характеристики, вычисленные по формулам (6) на основе IDF коллекции ATR 2009
  • 5,6. Характеристики, вычисленные по формулам (6) на основе ICF коллекции ATR 2009
  • 7,8. Характеристики, вычисленные по формулам (1) и (2)

По приведенным таблицам можно сделать следующие выводы. Наибольшее влияние на результаты анализа из рассматриваемых характеристик имеют метрики, вычисленные по формуле для всего документа и тега body. Небольшое преобладание значений таблицы 1 над соответствующими величинами таблицы 2 говорит о том, что в ранжировании учитываются не только леммы, находящиеся в «теле» документа.

Таблица 3 показывает, что в заголовке документа более важна относительная частота слова из запроса, нежели различные IDF/ICF-метрики.

Отдельно стоит отметить схожий характер зависимостей коэффициентов корреляции от запросов для различных исходных частотных баз и метрик. Это следствие того, что IDF и ICF разных баз сильно коррелируют друг с другом. Что подтверждает сделанное выше замечание о том, что полнота коллекции не является необходимым условием для построения адекватных частотных баз.

Регрессионное оценивание места оптимизируемой страницы в результатах поиска/

Чем ближе модуль коэффициента корреляции к 1, тем ярче выражена линейная зависимость между исследуемыми величинами. Что позволяет использовать еще один интересный инструмент статистического анализа – регрессионное оценивание. Суть данного метода применительно к решаемой задаче заключается в получении численных значений позиции некоторой страницы при известных ее характеристиках.

Рассмотрим двухмерную модель, т.к. одномерную линейную регрессионную модель прекрасно заменяет простое ранжирование страниц в зависимости от значений их характеристик. Пусть имеются три величины Х1, Х2 и У, для которых известны соответствующие друг другу тройки значений (X1i X2i,Yi), i=1,2..N. Необходимо так подобрать параметры линейного регрессионного уравнению вида Y(X1,Х2)=a2X2+a1X1+a0 (11), чтобы оно как можно лучше отображало зависимость между величинами. Для этой цели обычно применяется метод наименьших квадратов. Система уравнений построенная по этому методу имеет вид:
  (12)

Решением системы будут значения параметров регрессионного уравнения:
  (13)

Тогда, подставляя значения вычисленных характеристик Х1,Х2 для некоторой html-страницы, в полученное уравнение можно оценить ее позицию в результатах ранжирования. Для более достоверного оценивания можно использовать доверительный интервал, в который с заданной вероятностью попадет значение места исследуемого документа в выдаче.

Важно подчеркнуть, что полученная регрессионная модель основана лишь на выявленной статистической зависимости между метрикой состава страницы и ее местом в выдаче, и она не имеет никакого отношения к истинной формуле используемой для текстового ранжирования. Более того, представленная регрессионная зависимость линейно учитывает только два фактора Х1, Х2. Для более сложных зависимостей следует использовать нелинейную множественную регрессию. И отдельно стоит отметить, что для коммерческих запросов регрессионная модель бесполезна из-за сильного влияния ссылочного фактора.

Заключение.

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

К недостаткам метода можно отнести труднодоступность для простого оптимизатора IDF/ICF-баз и небольшую эффективность при большом числе неучтенных факторов, влияющих на результаты ранжирования.

Достоинства метода - вычислительная простота, возможность статистической проверки различных гипотез о принципах алгоритмов ранжирования поисковых систем, сравнение влияния различных факторов на результаты выдачи.

Update.

Приведенные выше данные и выводы были актуальны в октябре 2009 года. С внедрением поискового алгоритма «Снежинск» ситуация несколько поменялась. В связи с этим ниже представлены данные расчета, проведенного в начале февраля 2010 года (таблица 4):

Таблица 4. Коэффициенты корреляции для характеристик без учета тегов
Запрос12345678
гонор-0,234-0,210-0,289-0,196-0,286-0,196-0,204-0,038
банальность-0,1570,074-0,2710,067-0,2920,076-0,0780,031
клюв-0,282-0,097-0,246-0,106-0,275-0,094-0,109-0,019
зло-0,2830,131-0,2560,126-0,2630,1420,127-0,220
струпья-0,306-0,255-0,286-0,260-0,347-0,293-0,267-0,039
маньяк-0,151-0,254-0,329-0,249-0,346-0,305-0,308-0,133
подзатыльник-0,300-0,229-0,318-0,268-0,344-0,249-0,277-0,035
традиции-0,217-0,241-0,326-0,281-0,346-0,246-0,213-0,173
ученый-0,334-0,218-0,313-0,201-0,322-0,198-0,242-0,133
выдумка-0,146-0,273-0,366-0,259-0,347-0,258-0,316-0,220

Как видно, полученные парные коэффициенты корреляции имеют абсолютные значения в 2-3 меньше, чем аналогичные в таблицах 1-3, что говорит о сравнительно менее выраженной зависимости результатов ранжирования от исследуемых метрик. Однако, относительная степень влияния метрик осталась прежней, т.е. по-прежнему наибольшее влияние на результаты анализа из рассматриваемых характеристик имеют метрики, вычисленные по формуле . Причин снижения абсолютных значений парных коэффициентов корреляции может быть множество, одна из них - увеличение количества факторов, учитываемых при ранжировании снижает абсолютный вклад каждой из характеристик в итоговую формулу релевантности документа, что в свою очередь снижает значение КК. В таком случае целесообразно использовать множественный коэффициент корреляции, который позволяет определять зависимость результата от каждого из факторов, при неизменных значениях остальных характеристик.

Для примера в таблице 5 представлены средние значения множественных КК по результатам расчетов по ТОП-100 для 10 запросов:

Таблица 5. Множественные коэффициенты корреляции для характеристик без учета тегов
 12345678
Среднее значение МКК0,630,920,850,920,890,960,870,73



Нравится


Поисковые исследования:

Алгоритмы ранжирования Яндекса:


 

Copyright AlterTrader Research Ltd. 2004-2017.
All Rights Reserved.

Design: af@altertrader.com