close

Вход

Забыли?

вход по аккаунту

?

Информационный поиск. Лекция 9

код для вставкиСкачать
Выявление спам сайтов
на основе анализа контента
страниц
Москва 2016
План лекции
• Почему спам существует, в чем основная проблема
• Методы воздействия спама на поисковик и способы
противодействия
• Детекция спама на основе анализа контента страниц
• Методика выявление спам-сайтов
2
Объемы рекламного рынка
Интернет
0,31
Прочие
0,01
Наружная
реклама
0,12
Печатные
СМИ
Радио
0,08
0,05
Телевидение
0,44
Телевидение
Радио
Январь-Сентябрь
2015 года,
млрд.руб.
90,30
9,40
Печатные СМИ
16,10
Сегменты
Наружная
реклама
Интернет
Прочие
ИТОГО
24,10
64,70
2,60
208,50
3
Реклама в интернете
19%
81%
Медийная реклама
Январь-Сентябрь
Сегменты
2015 года,
млрд.руб.
Медийная
12,00
реклама
Контекстная
52,70
реклама
Контекстная реклама
4
Переходы с различных источников
Каталоги
0%
Поисковики
92%
По данным liveinternet.ru за 2015г.
Ссылки
1%
Соц. сети
7%
Источник
Переходы,
мл.
Соц. сети
212
Поисковики
2562
Каталоги
4
Ссылки
18
5
Eye-Tracking Study: Как пользователи
просматривают результаты поиска
53 – участника
43 – поисковых задачи
85% запросов получают
клики в 1 результат
Клики получают, в
основном, первые 3 – 5
позиций
THE EVOLUTION OF GOOGLE SEARCH RESULTS PAGES & THEIR EFFECTS ON USER BEHAVIOUR. (Mediative)
6
Мотивация
• Попадание в топ выдачи имеет под собой
чисто экономическое обоснование:
• Больше пользователей - больше выгода
7
А в чем проблема?
8
А в чем проблема?
Генерация большого количества мусорного
контента
9
Что мы хотим получить?
• Уменьшить вероятность попадания
спама в индекс
• Уменьшение количества поискового
спама в выдаче поиска
~10% - страниц в индексе это спам
10
Куда бьет спам?
Web
Index
Frontend
Query
processor
Searchers
(Ranking)
11
Куда бьет спам?
Web
Index
Frontend
Query
processor
Searchers
(Ranking)
12
Как воздействовать на систему
ранжирования?
13
Основные компоненты ранжирования
1. Поведенческое ранжирование
2. Ссылочное ранжирование
3. Текстовое ранжирование
14
Поведенческое ранжирование
CTR
Click Through Rate

 =

 - количество кликов для запроса q
 - количество показов для запроса q
15
Поведенческий спам
CTR

 +  
=
=
 + 


1 + ൘


1 + ൘

 - спам клики и показы
u – чистые клики и показы


Τ
ൗ ∝
ൗ ~ доля оригинальной статистики
 ∝
16
Поведенческий спам
CTR
Статистика запросов за месяц:
купить телевизор ~ 61 845,
купить холодильник ~ 50 074
…
На частотных запросах клик спам может стать экономически
невыгодным, требуется сгенерировать статистику равноценную
оригинальной.
17
Поведенческое ранжирование vs спам
Learning to Rank
Поведение как признаки модели.
X = 1 , … , 1 , …  , … ,  ; - полное пространство признаков
N – размер вектора, M – количество поведенческих признаков
 ; ,  = σ
=0  ∙ ℎ (,  ); - модель
 = {, } - параметры модели > arg min   | arg max  
тогда >  =  + 
 - клики реальных пользователей
с - спам клики, можно считать шумом
Выбрать алгоритм устойчивый к шуму.
18
Поведенческое ранжирование vs спам
Learning to Rank
Обучение на кликах.
Оцениваем влияние на качество.
Генерируем клики для 1,2,3,4,5
документов на запрос.
Спам клики на качество влияют
незначительно
Are Click-through Data Adequate for Learning Web Search Rankings? Zhicheng Dou
19
Ссылочное ранжирование
Модель веб графа:
 = , 
V – вершины графа – страницы
E – ребра графа – ссылки между страницами.
 - вес ребра между страницами  и  ; ,  ∈ 
 =
1
|  |
|  | - количество исходящих ссылок со страницы 
Матрица переходов
01
 = 11
0
01
...
1
0
1 =>  = ቊ ,  ,  ∈ 
0

20
Ссылочное ранжирование
PageRank
Вес страницы подбирается итерационно:
 = 1 −    −  Ԧ
с – дампинг фактор
Ԧ - статический вектор.
 =
1
,…
||
,
1
||
- для не персонализированного PageRank. Гарантирует существование
стационарного распределения  соответствующей цепи Маркова, описанной не стохастической
матрицей М.
The pagerank citation ranking: Bringing order to the web. L. Page, S. Brin
21
Ссылочный спам
М – стохастическая матрица pij > 0; σ=1  = 1 ; ∀ для цепи Маркова
 - стационарное распределение матрицы М
Для влияния на стационарное распределение расширим матрицу М
…
…
M = 


…

…
…
..
…

…
…
…
… …
… …
… …
… …
… ...
Авторитетный сайт
страницы
ферма
Целевой сайт
Целевая страница
Увеличиваем ранк целевой страницы через
ферму ссылок
22
Ссылочный антиспам
Распространение меток
Ключевая идея:
 = {1 , … ,  } – множество страниц
෩ ⊆  - множество страниц с метками.
Цель: рассчитать значение меток для остальных сайтов через
правила распространения меток.
23
Ссылочный антиспам
Распространение меток
• TrustRank - ෨ - доверенные страницы + персонализированный PR
• Для определения доверия используем обратный PR
• Размечаем К лучших страниц получаем ෨
• Делаем персонализированный вектор Ԧ
•
Считаем PR
Combating web spam with trustrank. Z. Gyongyi
24
Ссылочный антиспам
Признаки из ссылок
Степень ссылочности (входные, выходные ссылки )
PageRank (PR, In-degree/PR, Out-degree/PR, STD(PR))
TrustRank (TrustRank, TrustRank/PR, TrustRank/In-degree)
X = 1 , … ,  ; - полное пространство признаков
 ; ,  = σ
=0  ∙ ℎ (,  ); - классификатор
 = {, } - параметры модели > arg min  
Link-Based Characterization and Detection of Web Spam. Luca.Becchetti
25
Ссылочный антиспам
Подкрепление меток
Маркируем спам страницы используя классификатор
Кластеризуем страницы, используя граф ссылок  = , 
Страница получает метку спам если большинство страниц в
кластере спам и наоборот
Know your Neighbors: Web Spam Detection using the Web Topology. Carlos Castillo
26
Текстовое ранжирование.
Модели для текстового ранжирования:
• Модель векторного пространства
• BM25
• Статистическая языковая модель
27
Текстовое ранжирование.
Модель векторного пространства
 = 1 , 2 , 3 , … ,  - вектор документа
t – размерность вектора. || - размерность словаря
 - вес j-го терма в документе i
(,  ) - Мера сходства документа и запроса
 = ∈  ,  ∙   , 
∈ - частота j слова в документе i
 - инвертированная частота слова j
A vector space Model for Automatic Indexing. G. Salton
28
Текстовое ранжирование
BM25
Вес слова j в документе i
(1 +1) ∙ 
 −  + 0.5
 =
log

 + 0.5
1 + ( 1 −  + 
)
( )
Вес документа d для запроса q:
 ,  = ෍   ∙ 

Simple BM25 Extension to Multiple Weighted Fields. Stephen Robertson
∝  ( , )
1 и  – параметры
 - длина документа
 - частота слова в
документе
 - частота слова в
коллекции
 - количество
документов
29
Текстовое ранжирование.
Вероятностная языковая модель
Модель – Бернулли. Слово w есть или нет в документе d
||
||
  = 1 , 2 , … ,   ) = ς=1; =1   = 1| ς=1; =0   = 0 | 
Мульти-номинальная модель. Моделирование частоты слов
||
||
  = 1 …  |  = ς=1   |    , ; σ=1   |  = 1
 = 1 , … ,  - слова запроса,
  ,  - частота слова i в запросе q
Ранжирование на основе правдоподобия запроса
||
log  | = σ=1   ,  ∙   |   |  =
 , +1
 +||
C (w, d) - частота
слова в документе
∝ 
- вероятность вхождения слова в документ
Statistical Language Models for Information Retrieval. ChengXiang Zhai
30
Текстовое ранжирование
Что общего?
(, ) =   ,  ∙   , 
 =
||
log

  ,  =
- инверсная частота терма

σ=1 
- частота терма j в документе i
Увеличивая частоту слова в документе,
увеличиваем вероятность его нахождения
31
Текстовое ранжирование
BM25 зоны
Зоны – различные части документа, по которым можно считать ранк BM25.
Пусть документ разбит на К зон тогда суммарный ранк документа:

 , ,  = ෍   , 
=1
v – вес зоны документа
Увеличение частоты слова в различных зонах документа, по разному влияет на его
вероятность нахождения.
32
Контекстный антиспам
классификатор
X = 1 , … ,  ; - полное пространство признаков
 ; , 
= σ
=0  ∙ ℎ (,  ); - классификатор
 = {, } - параметры модели > arg min  
Detecting Spam Web Pages through Content Analysis. Alexandros Ntoulas
33
Контекстный антиспам
прочее
Выявление спама через нахождение дубликатов
(“Detecting phrase-level duplication on the world wide web.” Dennis Fetterly )
Выявление спама через сравнение языковых моделей
(“Blocking Blog Spam with Language Model Disagreement ” Gilad Mishne)
 |1
 1 ||2 = ෍  |1 log
 |2
…

34
Методы воздействия на поисковый механизм:
• Перенасыщение заголовков ключевыми словами.
• Перенасыщение текстов ключевыми словами.
• Оптимизация текстов под одно ключевое слово.
• Оптимизация текстов под большое количество ключевых слов.
• Оптимизация анкоров ссылок под ключевые слова.
• Активный обмен ссылками.
• Фермы ссылок.
•
...
35
Классификация воздействий на
поисковый механизм
• Воздействие при помощи оптимизации контента страницы.
• Воздействие при помощи оптимизации ссылок.
• Воздействие на поведенческие факторы.
…
Вопрос:
Разработка в каком направлении даст
лучшие результаты?
36
В 2006 году в рамках материалов конференции IW3C2
была опубликована статья: «Выявление спам-страниц через
анализ контента» («Detecting Spam Web Pages through Content
Analysis”. A. Ntoulas и коллектив авторов).
В статье показано, что 86% спама можно вычислить на
основе анализа контента страниц.
Разработка в
направлении детекции
контекстного спама даст
лучший профит.
37
Нам интересны более простые методы выявления
искусственности страниц.
Достаточно просто
поддерживать в актуальном
состоянии.
Использовать для
классификации спама с
высокой точностью.
38
Рассмотрим проблему обнаружения спам страниц как задачу
бинарной классификации.
1 — спам
0 — не спам
Требуется:
1. Определить пространство признаков.
2. Определиться с методом классификации.
39
Качество классификации напрямую зависит от качества
признаков, описывающих пространство.
Линейно
разделимые
признаки
Линейно
неразделимые
признаки.
Выделение небольшого количества хорошо разделимых
признаков позволит нам решить задачу классификации с большей
эффективностью.
40
Распределение количества слов на странице в спамовых и
неспамовых множествах
% страниц множества
8
7
6
5
4
3
2
1
0
Не спам
Спам
Количество слов на странице
41
Распределение количества слов в заголовке страниц в
спамовых и неспамовых множествах.
% страниц множества
50
45
40
35
30
25
20
15
10
5
0
Количество слов в заголовке на странице
Не спам
Спам
42
Распределение средней длины слова в спамовых
и неспамовых множествах
% страниц множества
40
35
30
25
20
15
10
5
0
0
2
Не спам
Спам
4
6
8
10
12
14
16
Средняя длина слова
43
Количество слов в анкорах ссылок для спамовых
и неспамовых множеств
% страниц множества
12
10
8
6
4
2
0
Не спам
Спам
Количество слов в анкорах ссылок
44
% документов множества
Степень сжатия документов в спамовых
и неспамовых множествах
40
35
30
25
20
15
10
5
0
Не спам
Спам
Степень сжатия
45
Сравнивая приведенные данные с ранними
исследованиями, приходим к выводу, что спам
подвергается мутациям, в сторону обычных страниц.
Хотя, в распределениях все еще присутствует явная
«искусственность».
46
Распределение усредненного веса ключевых слов для спам- и
обычных страниц
% страниц множества
25
20
15
Не спам
Спам
10
5
0
Усредненное значение веса ключевых слов
N
∑ wi
Усредненное значение веса ключевых слов документа:
wi
N
w
̄ dkw = i=1
N
вес ключевого слова
количество ключевых слов
47
Распределение отношения веса значимых ключевых слов к
общему количеству слов в спамовых и неспамовых множествах
% страниц множества
25
20
15
Не спам
Спам
10
5
0
Усредненное значение веса значимых ключевых слов.
K
∑ wi
Усредненное значение веса значимых ключевых слов документа:
wi
N
K
imp
w
̄ d =
i=1
N
вес ключевого слова
количество ключевых слов
количество значимых слов
48
Мы привели несколько характеристических языковых признаков
и увидели, что они дают лучшее разделение, чем признаки,
полученные на основе параметров страницы.
В
эксперименте мы
рассчитали
10
дополнительных
признаков, основанных на статистике распределения слов в
текстах. Теперь, имея хороший набор факторов, перейдем к
решению поставленной задачи, а именно – попробуем создать
классификатор на основе описанных признаков.
49
Карта классов (SOM)
Class Legend
Spam
Not Spam
50
Классификатор — многослойный персептрон:
Входной слой — 80 нейронов ,
Скрытый слой — 96 нейронов
Выходной слой — 2 нейрона спам=1 и не-спам=0
Функция активации — сигмоид
Для тренировки нашего
классификатора мы использовали
страницы, отобранные асессорами.
Обучающий вектор - 80 признаков.
Размер обучающего множества — 20000 страниц.
Размер тестового множества — 50000 страниц.
Точность - 0,97
Полнота - 0,94
- 0,96
F-мера
_______________
51
Что делать дальше.
Можно ли использовать информацию,
полученную из контентента страниц, для
классификации сайтов?
53
Спам или нет?
Спам сайт
Не спам сайт
100% = спам
0% = не спам
54
Спам или нет?
Спам сайт
?
Не спам сайт
?
?
55
Причины:
• Хороший сайт со спам страницами:
• Ошибка классификатора.
• Взломанный сайт.
• Переоптимизированный контент.
• Спам сайт с полезными страницами:
• Ошибка классификатора.
• Разбавление спама не спам страницами.
56
Характеристики сайта:
1. Доля спам страниц.
2. Расположение спам страниц.
3. Вероятность прихода/ухода на спам страницу с сайта.
4. На какие страницы ведут входящие/исходящие
ссылки.
5. Вероятность участия в спам-ферме.
57
Доля сайтов
Доля спам страниц
Доля спам страниц
58
Участие в спам ферме
20%
100%
60%
0%
50%
45%
Дорвеи
P=0,3
Целевой сайт
1. Вычисляем вероятность того, что сайт раскручивается спам- сайтами.
2. Вычисляем вероятность участия в спам-ферме.
59
Вероятность участия в спам-ферме
60
На отобранных признаках строим
классификатор
Всего получили 20 признаков
Используем алгоритм Еxpectation Maximization для
выделения из множества сайтов двух центров,
соответствующих классам: спам и не спам.
Используем полученные центры как исходные данные для
классификации при помощи алгоритма k-nearest neighbor.
61
Результаты:
Уменьшение количества спама в выдаче
в среднем на 20%.
Точность анализатора - 90%.
Доля спам сайтов - 17%.
62
Спасибо!
Вопросы.
63
Автор
tekhnostrim
Документ
Категория
Без категории
Просмотров
57
Размер файла
2 205 Кб
Теги
лекция
1/--страниц
Пожаловаться на содержимое документа