close

Вход

Забыли?

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

?

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

код для вставкиСкачать
Применение
самоорганизующихся карт в
поисковой машине
Дмитрий Соловьев, ведущий
разработчик группы ранжирования
проекта Поиск@Mail.Ru
Москва 2016
План занятия
• Постановка задачи анализа больших данных
• О визуализации данных
• Визуализация на основе SOM
• Что такое нейронные сети и SOM.
• Подходы к визуализации данных.
• Варианты использования самоорганизующихся карт в поисковой
машине.
• “Секитей” кластеризация урлов по выделенным признакам
• Семинар по выделению и анализу сегментов для преоритезации.
3
Что мы имеем:
• Алгоритм, который выбирает фичи из урлов.
• Данные - урлы с сайтов
• Знания о классах ссылок (qlink | !qlink)
• Знание, что таких сайтов ~1000
Цель:
Брать самое вкусное с
этих сайтов
segment_[0-9]_2
segment_[0-9]_3
segment_[0-9]_1
segment_len_3:24
segment_len_1:45
segment_name_0:news
/news/2012/07/13/mylo/lenta.ru/news/2011/07/01/pentax/
/most/2013/01/13/
/auto/2002/09/25/gm/picture.jpg
/news/2011/10/25/seat/_Printed.htm
/crime/2012/06/29/
/world/2004/04/26/qutar/
4
Что еще
• Протестировать алгоритм, т.е. оценить его работоспособность
• Получить знания об извлеченных фичах.
• Получить информацию о кластерах и выбросах.
• Понять что делать дальше.
Что нам может помочь ответить на эти вопросы?
5
Визуализации данных
• Мощный аналитический инструмент, представляет данные в виде
удобном для их изучения человеком
• Краткость - способность одновременного отображения большого
числа разнотипных данных;
• Относительность и близость — способность демонстрировать в
результатах запроса кластеры, относительные размеры групп,
схожесть и различие групп, выпадающие значения
6
Визуализации данных
• Концентрация и контекст — взаимодействие в некоторым
выбранным объектом с возможностью просмотра его положения
и связей с контекстом;
• Масштабируемость — способность легко и быстро перемещаться
между микро- и макропредставлением
• Ориентация на «правое полушарие» — предоставление
пользователю не только заранее установленных методов работы
с данными, но и поддержка его интуитивных, импровизационных
когнитивных процессов идентификации закономерностей
7
Визуализация данных
• Визуализация исходных данных.
• Визуализация выборки, загруженной в систему обработки.
• Визуализация результатов первичной обработки.
• Визуализация промежуточных результатов.
• Визуализация окончательных результатов.
8
Self-Organizing Map
• была представлена в 1984 Тейво Кохоненом
• это специальный вид нейронной сети
• обучается без учителя
• отображает пространство высокой размерности в
пространство низкой размерности
• является эффективным инструментом для визуализации.
10
Коротко о нейронных сетях
• История началась в 1943 Warren McCulloch и Walter Pitts.
• Общая схема нейронной сети:
Выход
Выходной слой
X
 = (෍ )
Y

Скрытый слой
Схема нейрона
Вход
11
Виды нейронных сетей
• Прямого распространения (Feed Forward)
• Радиальные базисные функции (Radial basis function RBF)
• Рекурентные (Recurrent )
• Модулярные (Modular)
• Самоорганизующиеся карты (SOM)
• ….
12
Методы обучения и применение НС
Обучение
С учителем
Без учителя
Ответ известен и используется для обучения сети.
Цель найти связь между входом и выходом
Ответ не известен. Цель найти структуру
данных или паттерны данных
Топология
Применение
Рекурентные сети
Сети прямого распространения
RBF
…
Предсказание
Карты кохонена
Машина больцмана
Автоэнкодер
…
Классификация,
кластеризация, сжатие
данных …
13
Применение SOM
• Обучение сети основано на обучение без учителя
• Применение в data mining и KDD
•
•
•
•
•
•
Анализ полнотекстовых данных
Анализ финансовых данных
Выявление шаблонов
Анализ картинок
Анализ процессов
Исследовательский анализ данных
14
Преимущества самоорганизующихся карт
• Упорядоченное уменьшение размерности
• Топологическое мапирование обучающего множества
• Повторение PDF в данных
• Устойчивость к пропущенным данным
• Простая визуализация
15
Что такое SOM?
Y
X
Одна размерность (1D) SOM
Решетка: прямоугольная или шестиугольная
Две размерности(2D) SOM
X
16
Что такое нейрон SOM?
• SOM состоит из K нейронов
• Нейрон имеет N-размерный прототип вектор
• N это размер входного пространства
•   - функция расстояния (distance function)
• Выход - расстояние между прототип вектором и
входным вектором
Y
 
…
…
 = 1 … 
Прототип вектор
17
SOM Learning algorithm
• Старт итерации
• Рассчитываем Евклидово расстояние для всех прототип векторов
• Выбираем ближайший нейрон по расстоянию ( BMU )
• Обновляем BMU и его окрестности
•  ≔ −1 + ∝  ℎ  ( − −1 )
• Конец итерации
x - входной вектор
t - номер шага
k - индекс нейрона
m – прототип вектор нейрона
∝ - коэффициент обучения
h - функция близости
Wikipedia.org
18
Алгоритмы Vector Quantization
• Уменьшают размер дата сета до меньшего, но все еще
репрезентативного размера.
• В тоже время уменьшает шум
Алгоритм
Описание
K-means
Only best matching cluster (center) of sample vector is updated
Maximum entropy
All clusters are centered according to their distance to the sample vector
Neural gas
All cluster centers are updated according to their ranking order in distance
to sample vector.
SOM
The cluster centers are updated according to their distance from BMU of
sample vector on the map grid (h).
19
Алгоритмы Vector Projection
• Проецируют оригинальное пространства в двух размерное
• Должны сохранять расстояние между векторами.
Алгоритмы
Функция энергии
Multi-dimensional
scaling
෍
Sammon’s projection
 − 
෍෍


SOM
2
<

Curvilinear component
analysis
෍  − 
Описание
2
<
2
෍ ෍ Xij − Yij ( )

<
෍

2
ℎ( )
෍ 

Distances in the input space are approximated by
distances in output space.
Local distances in input space are emphasized. This
projection has instability.
Local distances in input space are emphasized. ( ) is a
function monotonically decreasing in output space.
Input space distances  are measured between
prototype k and data vector i. Similarity in inputs space
distances are measured between map units 
20
Преимущества SOM визуализации
Метод SOM включает vector quantization и projection
SOM имеет проекционную решетку правильной формы
что делает легким сравнение различных визуализаций
21
Множество визуализаций и привязка
Как визуализировать данные?
Одна визуализация
Немного визуальных представлений
Позиция, размер и цвет.
Может быть движение и форма
Множество визуализаций
Как связать различные
визуализации?
Связываем по позициям
SOM – отличное решение
22
SOM для 石庭
• Построим SOM для некоторой малой выборки сайтов
• Размер 5x5=25 кластеров
• Используем пакет “somtoolbox”
http://www.ifs.tuwien.ac.at/dm/somtoolbox/
23
Гистограмма хитов
• Показывает баланс примеров на
карте интенсивностью цвета
• Можно понять соотношение
получившихся кластеров
Минимальные значение
Максимальные значения
24
Наложим диаграмму классов
• Получаем визуализацию
распределение классов по кластерам
Посещаемые сегменты
Пустые сегменты
qlink
!qlink
25
Сделаем Карты признаков
• Для каждого признака построим карту
его влияния
• Интенсивностью цвета выделим
уровень значения признака
• Можно изучить влияние каждого
признака на кластера
segment_name:news
max
min =0
26
Охота за корреляциями
• Каждую фичу представляем
вектором корреляций между
признаками
• Строим новую SOM, используя как
вход вектора корреляций признаков
• Размещаем на этой карте признаки
по максимальной близости к
опорным векторам карты
27
Анализируем корреляции
Можно удалить сильно коррелирующие признаки
28
После удаления признаков длин
segment_name_1:2010
Новости 2010
/news/2010/[0-9]
segment_name_0:news
29
После удаления признаков длин
segment_name_1:2014
Новости 2014
/news/2014/[0-9]
segment_name_0:news
30
Выводы
• Получаем информацию о:
• структуре данных,
• распределении классов,
• распределении примеров по кластерам
• Анализируем влияния признаков
• Ищем корреляции между признаками
Что еще?
31
Поисковая машина
“дальше выше быстрее”
Web
Index
ML
ML
Frontend
Query
processor
ML
Searchers
ML
33
Машинное обучение в ранжировании
Model
Assessors
ML Train
Set
Что представляет обучающее
множество? Черный ящик.
Запросов: ~ 105
Оценок асессоров: ~ 3 × 106
Размер вектора признаков: ~ 2 × 103
34
Что мы можем сказать о черном ящике?
• Каково качество оценок асессоров?
• Какова структура данных?
• Каково качество представленных данных?
• Каково качество признаков в дата сете?
?
35
Структура и форма ‘Black Box’
• Каковы, и где, кластера и выбросы?
• Какова форма облака данных?
• Каковы корреляции признаков ?
• Что еще мы можем найти в нашем ‘Black Box’ ?
?
36
Гистограмма хитов (Hit Histogram)
• Количество примеров в нейроне
• Помогает анализировать баланс
• и, возможную ребалансировку
low
Hit legend
high
37
Матрицы расстояний (Distance Matrices)
• U-Matrix
• Показывают границы кластеров
• Определяют интерполирующие
юниты и выбросы
• Показывают регионы плотности
(density region)
low
Distance legend
high
38
Distance Matrices & Кластера
• U-Matrix показывает кластера
• Недостатки:
• Вычисляет расстояние статически
• Не показывает взаимодействие
кластеров
low
Distance legend
high
39
Smoothed Data Histogram
• Визуализирует кластера
• Использует оценку плотности
вероятности
• Есть сглаживающая константа
• Позволяет делать иерархическую
кластеризацию
low
Density legend
high
40
Влияние признаков кластера
• Оценка влияния признаков на
кластер
• Анализ предположений по
расщеплению данных
• Анализ размера кластера
41
Анализ Component Planes
• Поиск влияния компонент
• Анализируем воздействие на
разделение кластеров
low
Impact legend
visible-feature
high
44
Охота за корреляциями признаков
Реорганизуем
плоскости согласно
матрице корреляций
45
Контроль признаков
• По параметрам (дисперсия, среднее)
Before
After
Mean
0.242768
0.242784
Variance
0.0363817
0.0363741
• Анализ распределения на SOM
46
Карта классов
• Распределение классов по данным
• Распределение классов по кластерам
• Оценка качества маркирования
• Оцениваем качество признаков
Class Legend
Spam
Not Spam
47
Человек vs. Машина “еще, дай еще”
• Формула ранжирования
U-Matrix
Class map Data Histogram
Smoothed
• Запросов: ~ 105
• Оценок: ~ 3 x 106
• Размер вектора признаков: ~ 2 103
• Работа человека дорогая
• Как заменить человека машиной?
Density
legend
Distance
legend
Class
legend
low
high
48
Использование SOM
• Отбор примеров для формулы ранжирования
• Обнаружение новых примеров
• Проверка качества разметки
49
Отбор примеров для формулы
• Цель – создание сбалансированного обучающего множества
• Как это работает?
• Старт итерации
• Выбираем запрос из дата сета
• Строим SOM
• Выбираем наиболее удаленные примеры на SOM для запроса
• Конец итерации
50
Обнаружение новых примеров
• Цель обнаружить неизвестные примеры
• Используем иерархию SOM’s
• Как это работает?
• Выбираем N случайных примеров
• Строим SOM
• Начало итерации
• Выбрать примеры которые имеют большую ошибку квантирования
на SOM (quantization error)
• Строим следующую карту на отобранных примерах
• Конец итерации
51
Проверка качества асессоров
• Цель – проверка качества оценок асессоров
• Используем карту классов
• Как это работает?
• Выбираем нейроны с максимальной ошибкой классификации
• Рассчитываем вероятность класса в нейроне
• Переоцениваем примеры с низкой вероятностью
• Бонус A: удаляем поврежденные примеры
• Бонус B: удаляем (наказываем) асессоров
52
Домашнее задание
• Реализовываем приоритизацию спайдера
• Выделяем фичи из урлов и преобразуем их (урлы) в вектора.
• Делаем сегментацию сайта, используя выделенные фичи и знания о
квоте при помощи кластеризации. (пакет sklearn или пишем сами)
• Прогоняем алгоритм по оценке урлов
• Оцениваем качество
• Если качество не устраивает, делаем анализ результатов и данных.
http://www.ifs.tuwien.ac.at/dm/somtoolbox/ . Выполняем перезапуск с
новыми параметрами.
• Два датасета: тренировочный и валидационный.
53
Вопросы
References:
T. Kohonen, Self-Organizing Maps, Springer.
J. Vesanto Som-Based Data Visualization Methods
Автор
tekhnostrim
Документ
Категория
Наука
Просмотров
31
Размер файла
3 033 Кб
Теги
лекция
1/--страниц
Пожаловаться на содержимое документа