itmo_conspects

Анализ данных и информационных поиск

Курс посвящен изучению анализа данных (в англ. Data Mining) и методов поиска данных

Анализ данных изучает такую задачу: есть запрос пользователя, на основе которого нужно проанализировать данные из базы и выдать подходящие отранжированные объекты

На курсе будут разбираться классические методы, рекомендательные системы, методы обучения ранжированию (Learning-to-Rank, LTR), семантический и генеративный поиск

Лекция 1. Методология и структурный анализ данных

Методология

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

Правильная методология предоставляет:

Популярной методологией является CRISP-DM (CRoss Industry Standard Process for Data Mining), которая разбивает анализ данных на 6 этапов:

CRISP-DM

По мере развития технологий выяснилось, что методология CRISP-DM, заточенная на статические данные, была недостаточной для машинного обучения, при котором данные имеют свойство меняться (такой процесс называется data drift), из-за чего модели устаревают и деградируют. Кроме этого часть проектов машинного обучения не оправдывают ожиданий из-за отсутствия системного контроля качества

Поэтому в 2021 году появилась методология CRISP-ML(Q) (Cross-Industry Standard Process for the development of Machine Learning applications with Quality assurance)

В CRISP-ML(Q) цикл разработки состоит из 6 фаз:

CRISP-ML(Q)

Структурный анализ на основе графов

Граф $G(V, E)$ - структура, состоящая из множества $V$ вершин и множества $E$ соединяющих их ребер

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

Граф можно представить:

В Python для работы с графами можно использовать библиотеку networkx. Так, например, создается граф по списку ребер

import pandas as pd
import networkx as nx

edges = pd.DataFrame({
    "source": ["A", "A", "B", "C", "D"],
    "target": ["B", "C", "C", "A", "C"]
})

G = nx.from_pandas_edgelist(
    edges,
    source="source",
    target="target",
    create_using=nx.DiGraph()
)

Рассмотрим два алгоритма для работы с графами:

  1. Алгоритм PageRank (“ранжирование страниц” или “ранжирование Пейджа”)

    В середине 1990-ых годов количество веб-страниц росло настолько быстро, что поисковые системы (такие как AltaVista, Lycos, Yahoo) перестали справляться с ранжированием результатов поиска, так как они оценивали HTML-документы в основном по количеству слов и их расположению

    Такой подход является уязвимым, так как можно увеличить частоту ключевых слов (тем самым увеличив позицию в выдаче) или увеличить число страниц-пустышек, ссылающихся на нужную страницу

    Поэтому в 1998 году Ларри Пейджем и Сергеем Брином был разработан алгоритм PageRank для поисковой системы BackRub (который был переименован в Google)

    Основная идея алгоритма PageRank состоит в том, что авторитет страницы определяется не количеством входящих ссылок, а авторитетностью страниц, которые на неё ссылаются. Для этого:

    • Строится граф страниц, где ребра - это ссылка на другую страницу

    • Далее со случайной страницы запускается робот, который:

      • с шансом 85% переходит по случайной ссылке на текущей странице
      • или с шансом 15% закрывает текущую и открывает случайную новую

    Таким образом:

    • Граф превращается в цепь Маркова, где переходы заданы вероятностями
    • Страницы-пустышки не будут посещены часто, так как на них никто не ссылается и единственным образом туда попасть - это случайный открытие новой
    • Поэтому переходы из таких страниц будут учитываться меньше
    • А из-за случайного перехода на новую страницу граф не обязан быть связным

    Рейтинг страницы определяется рейтингом страниц, которые на неё ссылаются - $PR(A) = \frac{1-d}{N} + d \sum_{i=1}^{n} \frac{PR(T_i)}{C(T_i)}$, где $N$ - число страниц, $T_i$ - страница, ссылающаяся на $A$, $n$ - число таких страниц, $C(T_i)$ - количество исходящих ссылок, , $d$ - коэффициент затухания (та самая вероятность в 85%)

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

    Наличие случайного перехода гарантирует существование единственного стационарного распределения вероятностей

    Интересно заметить, что с математической точки зрения алгоритм PageRank представляет собой вычисление собственного вектора матрицы переходных вероятностей марковской цепи

  2. Алгоритм HITS (Hyperlink Induced Topic Search)

    Алгоритм HITS был предложен в 1999 году Джоном Клейнбергом для нахождения веб-страниц

    HITS предполагает, что есть два вида страниц:

    • Авторитетные страницы, содержащие интересующие данные на заданный запрос
    • Хаб-страницы, которые содержат много ссылок на авторитетные страницы

    Затем HITS находит лучшие авторитетные и хаб-страницы

    Для этого алгоритм на каждой итерации:

    1. Обновляет ранг авторитетных страниц как сумму хаб-страниц, ссылающихся на нее: $a_i = \sum_{j \rightarrow i} h_j$
    2. Затем обновляет ранг хаб-страниц как сумму рангов авторитетных страниц, на которые хаб-страница ссылается: $h_i=\sum_{i\rightarrow j} a_j$
    3. Далее эти вектора нормируются: $\vec a = \frac{\vec a}{|\vec a|}$, $\vec h = \frac{\vec h}{|\vec h|}$

    Процесс повторяется до сходимости

    Алгоритм HITS используется значительно реже, чем алгоритм PageRank, так как:

    • Алгоритм зависит от запроса, для каждого поискового запроса необходимо сначала построить подграф релевантных страниц, а затем выполнить вычисления заново, что делает HITS более затратным
    • Если в подграф случайно попадает популярный, но слабо связанный с запросом узел, он может существенно исказить результаты ранжирования
    • Группы страниц, активно ссылающихся друг на друга, способны искусственно завышать значения $h_i$ и $a_i$

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

Такие признаки извлекаются на трех уровнях:

Текстовый анализ

За историю человечества было написано множество текстов: книг, статей, рассказов, повестей и так далее. Исследователи, изучавшие такие тексты, сформулировали два эмпирических закона:

  1. Закон Ципфа - частота слова $f(r)$ обратно пропорционально возведению в степень $s \approx 1$ ранга $r$ в списке: $f(r) \propto \frac{1}{r^s}$

    Пример: есть миллион статей, найдем частоту каждого слова

    Ранг Слово Частота
    1 и 8 700 000
    2 в 4 200 000
    3 не 3 100 000
    4 на 2 200 000
    … … …
    1000 иммерсивный 8200
    40000 эмерджентный 220
    70000 диегитический 100

    Слово и встретилось приблизительно в два раза чаще, чем в, приблизительно в три раза чаще, чем не и так далее

    Можно заметить, что часто употребимые слова содержатся в почти всех статьях, тогда как редкие слова могут служить ключевыми и быть связаны с темой документа

  2. Закон Хипса - словарь увеличивается пропорционально возведению в степень $\beta \approx 0.5$ суммарного числа слов в статьях $n$: $V \propto n^\beta$

    Параметр $\beta$ характеризует скорость появления новых слов (обычно $0.4 \leq \beta \leq 0.6$)

    Например, при чтении более новые статьи будут использовать более новые термины, имена, сокращения и так далее, таким образом словарь языка никогда не является конечным

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

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

Обычно делают такую предобработку (количество этапов зависит от задачи):

Этот сайт имеет открытый исходный код! Вы можете улучшить эту страницу или этот репозиторий!