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


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

Реализация и анализ эффективности метода построения оптимального множества доноров для продвижения сайта в поисковых системах

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



В статье [1] был описан алгоритм отбора максимально эффективного множества доноров на основе частотных паттернов. Предварительный анализ эффективности метода был проведен на базе одного компьютера малой вычислительно мощности, накладывающей довольно жесткие ограничениях на размерность исходной ссылочной базы (D). И, несмотря на показанную экспериментально высокую эффективность подхода, время построения оптимального множества было довольно велико. При отсутствии ограничений на размерность множества D встает вопрос о физической реализуемости метода. Настоящая статья посвящена описанию реализации технологии на базе сервиса Amazon Elastic MapReduce (EMR)[3].

1. Подготовка исходных данных для сервиса Elastic Map Reduce.

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

Во-первых, было построено множество доноров на основе ссылочной базы, предоставленной нашими партнерами. Из исходной базы доноров было исключено значительное количество документов (около 40%), вероятность неэффективности которых по нашим оценкам превышала 0.5. Фильтрация проводилась в несколько этапов – применялись наши собственные методы проверки неэффективности, фильтрация по маске URL и использовался объединенный блэк-лист от нескольких сео-компаний и крупных фрилансеров.

Во-вторых, для каждого донора были вычислены значения независимых от акцептора и запроса факторов. Вся ссылочная база была проиндексирована так, чтобы, во-первых, отсечь заведомо неподходящих доноров для конкретных запросов и акцепторов, во-вторых, существенно сократить время вычисления факторов на основе построенного индекса. Говоря о факторах, рассмотрим подробнее их природу. Для предварительных исследований, посвященных решению задачи построения оптимального множества доноров, было отобрано около 300 различных факторов, большую часть которых составляют разработанные нами метрики, остальные - это «классические» факторы, использующиеся поисковыми системами. В качестве «неклассических» метрик использовались, в том числе, основанные на спектральных характеристиках слов, биграмм, пар слов в одном предложении и пар слов в документе [2]. Данные распределения считались как по всему документу, так и по его началу и по отдельным тегам. Для уменьшения частотных баз и увеличения скорости расчета вместо SLM-метрик использовались аппроксимированные aSLM-метрики, которые кроме перечисленных выше достоинств позволяют также улучшить качество оценки веб-документов (в настоящее время статья об аппроксимированных спектральных метриках находится в печати). После проведенного анализа на основе баз доноров, запросов и коллекций документов, построенных нами самостоятельно и предоставленных партнерами, было выделено немногим более 200 слабокоррелирующих друг с другом факторов.

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

Построенный на серверах EMR индекс ссылочной базы позволил производить поиск на основе модифицированного генетического алгоритма, используя параллельные вычисления, что существенно сокращает время решения задачи. Для проведения эксперимента по оценке быстродействия реализации алгоритма, а также его эффективности было выбрано 80 пар (запрос; документ), находящихся на продвижении у одного из наших партнеров. Первые 40 из них – новые запросы, не продвигавшиеся ранее, вторые 40 - «проблемные» запросы, которые продвигаются не менее полугода, но так и не вошли в топ-10 Яндекса, находясь на второй или третьей странице поисковой выдачи. Пары подбирались таким образом, чтобы охватить как можно больше разнообразных тематических категорий. Бюджет для каждого запроса считался с помощью системы автоматического продвижения сайтов SeoPult.

Для каждого запроса Q, согласно технологии, предложенной в [1], было построено запросное дерево QT(Q) с глубиной топа равной 50. Т.е. по каждому запросу во множество акцепторов A графа QT включались документы, занимающие первые 50 позиций выдачи поисковой системы. Здесь отдельно подчеркнем существенный недостаток предлагаемого метода. Если целевой запрос представляет собой малый коммерческий интерес, то множество доноров его запросного дерева будет иметь небольшую размерность и, как следствие, полученные на его основе частотные паттерны (FP) будут иметь малую статистическую значимость. Качество решения задачи оптимизации множества доноров при этом существенно снижается.

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

2. Оценка эффективности метода построения оптимального множества доноров.

Для каждой пары запрос-документ (Q,A) на основе исходных данных (множество доноров, множество акцепторов) решается задача построения оптимального множества доноров:

  1. Для запроса Q, строится запросное дерево QT(Q)
  2. На основе QT(Q) строится частотный паттерн FP
  3. Решается задача оптимизации, минимизирующая невязку:

    между распределениями свойств эффективного множества доноров OD и FP при действующем ограничении на суммарную стоимость доноров:

    Подчеркнем, что задача решается с учетом уже имеющегося множества доноров у оптимизируемого акцептора.

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

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

где b - коэффициент.

Оптимизация функции I позволяет построить эффективное множество доноров с минимальными изменениями исходного множества.

Далее, в течение четырех месяцев производились наблюдения за изменениями позиций документов в выдаче поисковой системы Яндекс по целевым запросам. Результаты представлены в таблице 1.

Таблица 1. Демонстрация изменения позиций документов после оптимизации

Диапазон позиции
документа до
оптимизации
Диапазон позиции
документа после
оптимизации
Число документов,
соответствующих
изменению
11-201-31
11-204-56
11-206-1013
11-20>100
21-301-30
21-304-58
21-306-1012
21-30>100
>501-33
>504-514
>506-1023
>50>100

Полученные результаты говорят о высокой эффективности метода: все оптимизируемые документы улучшили свои позиции и вышли в топ-10 поисковой выдачи Яндекса.

3. Оценка эффективности метода динамической коррекции множества доноров

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

Общее время эксперимента было непродолжительным, поэтому разладка была обнаружена лишь дважды: по разу у двух разных документов. В таблице 2 представлены результаты эксперимента.

Таблица 2. Изменения позиций документов

ДокументПозиция до
исходной
оптимизации
Устойчивая
позиция
после
исходной
оптимизации
Позиция до
разладки
Устойчивая
позиция после
коррекционной
оптимизации
117887
22110109

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

4. Заключение

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

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

Каждый донор дает вклад в распределения значений свойств всего множества. Эффективность определяется невязкой между частотным паттерном и свойствами множества доноров

Если исключить одного из доноров, невязка возрастет, а эффективность снизится. Поэтому в качестве оценки эффективности единичного донора можно использовать его вклад в сокращение целевой функции K(OD,q,a):

E(d) – безразмерная величина, отражающая долю донора в уменьшении невязки. Чем выше значение оценки эффективности, тем больше вклад донора. Отметим, что данная оценка «физически» не имеет ничего общего с реальным влиянием донора на позицию документа, т.к. это влияние комплексное. Однако E(d) может использоваться для сравнения доноров друг с другом, для удобства проведения которого можно ввести ранговую шкалу.

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

Список использованных источников

[1] Зябрев И.Н., Пожарков О.В., Пожаркова И.Н. Алгоритм отбора максимально эффективного множества доноров для продвижения сайта в поисковых системах..

[2] Зябрев И.Н., Пожарков О.В., Пожаркова И.Н. Использование спектральных характеристик лексем для улучшения поисковых алгоритмов.. Труды РОМИП 2010. Казань: Казан. ун-т: С. 40–48, 2010.

[3] Amazon Elastic MapReduce.



Нравится


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

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


 

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

Design: af@altertrader.com