More Related Content
Viewers also liked (20)
L8: Л7 Em-алгоритм
- 1. Введение в Data Science Занятие 7. Ноунейм Николай Анохин Михаил Фирулик 18 апреля 2014 г.
- 2. Работа в группе Задача. Оценить, какой вклад внес в общий результат каждый участник группы Шаг 1. Каждый студент анонимно и независимо распределяет 100 очков между всеми участниками своей группы в зависимости того, какую пользу (по его/её мнению) каждый из участников принес Пример. Студент Вклад Геральт 50 Лютик 10 Мильва 20 Регис 20 Шаг 2. Из всех оценок вычисляется общая аггрегированная оценка на основе алгоритма PageRank
- 4. Жизнь до Google 1. Поисковые роботы используются для парсинга интернет-страниц 2. Составляется обратный индекс, в котором каждому слову соответствовал набор страниц 3. Слова из поискового запроса пользователя используются для поиска страниц в индексе 4. Из близких к запросу страниц формируется выдача Проблема: Term Spam
- 5. Что придумали парни из Google Дополнительно 1. Страницы ранжируются в соответствии с их “важностью” с помощью алгоритма PageRank 2. О релевантности страниц судят не только по словам, находящимся на текущей странице, но и по словам “соседних” страниц
- 6. Random Surfer Интуиция Пользователь начинает с просмотра случайной страницы, после чего с равной вероятностью переходит по одной из ссылок на этой странице. Процесс продолжается до бесконечности. PageRank страницы – вероятность обнаружить пользователя на этой странице. Пользователь с большей вероятностью посещает “полезные” страницы, чем “бесполезные” Создатели страниц размещают ссылки на “полезные” страницы
- 7. PageRank Представим интернет, как направленный граф со страницами в качестве вершин и ссылками между страницами в качестве ребер Матрица вероятностей перехода M = 0 1/2 1 0 1/3 0 0 1/2 1/3 0 0 1/2 1/3 1/2 0 0
- 8. PageRank Элементы матрицы перехода mij = P(v (k) i |v (k−1) j ) Изначально все страницы равновероятны v(0) = 1/n . . . 1/n Вектор вероятностей на k шаге v(k) = Mv(k−1) Предельное значение v – собственный вектор M, соответствующий собственному числу λ = 1. Процесс сходится, если из любой вершины можно попасть в любую.
- 10. Проблемы PageRank Dead End Spider Trap Решение. разрешим пользовалю “телепортироваться” на случайную страницу с вероятностью 1 − β v(k) = βMv(k−1) + (1 − β) e n
- 11. Пример Матрица перехода M = 0 1/2 0 0 1/3 0 0 1/2 1/3 0 1 1/2 1/3 1/2 0 0 Без телепортов v = 0 0 1 0 С телепортами β = 0.8 v = 15 148 19 148 95 148 19 148 Spider Trap
- 12. Методика оценки Геральт Лютик Мильва Регис Индивидуально Геральт 50 10 30 30 20 Лютик 10 70 10 5 5 Мильва 20 10 30 30 15 Регис 20 10 30 35 15 Матрица перехода, β = 0.9 M = 0.5 0.1 0.3 0.3 0.1 0.7 0.1 0.05 0.2 0.1 0.3 0.3 0.2 0.1 0.3 0.35 v = 0.31 0.23 0.23 0.24 Групповая оценка: 30/40 Итог: Геральт: 29, Лютик: 12, Мильва: 22, Регис: 22