Skip to content
This repository has been archived by the owner on Sep 1, 2023. It is now read-only.

Latest commit

 

History

History
274 lines (180 loc) · 19.8 KB

README.md

File metadata and controls

274 lines (180 loc) · 19.8 KB
Raw

Лабораторная работа №1

Дано

  1. Текст сказки Ганса Христана Андерсена "Дюймовочка" на русском языке (ссылка)
  2. Список стоп-слов (предлоги, союзы, местоимения и другие неполнозначные слова русского языка) (ссылка)
  3. Словарь с Inverse Document Frequency значениями для каждого из слов коллекции сказок Г. Х. Андерсена (ссылка)
  4. Словарь с корпусными частотами для каждого из слов коллекции сказок Г. Х. Андерсена (ссылка)

Необходимо выделить ключевые слова из текста сказки "Дюймовочка".

Код, считывающий все перечисленные выше материалы, уже написан для вас в start.py:

Вы найдете эти ресурсы в следующих переменных:

  • target_text - текст "Дюймовочки", откуда необходимо выделить ключевые слова
  • stop_words - список стоп-слов
  • idf - словарь вида {слово: idf}
  • corpus_freqs - словарь вида {слово: количество вхождений в корпус}

Что надо сделать

Шаг 0. Подготовка (проделать вместе с преподавателем на практике).

  1. Создать форк репозитория
  2. Установить необходимые инструменты для работы
  3. Изменить файлы main.py и start.py
  4. Закоммитить изменения и создать pull request

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

if __name__ == '__main__':  
 # your code goes here

В рамках данной лабораторной работы нельзя использовать сторонние модули и модуль collections.

Шаг 1. Очистить и токенизировать текст

Функция принимает на вход текст в виде строки.

Возвращаемым значением функции должен быть список строк. Эти строки не должны содержать:

  • знаков препинания
  • буквенных символов в верхнем регистре
  • лишних пробелов (лишними пробелами считаются пробелы в начале текста, в конце текста, рядом с другим пробелом)

Если на вход подаются некорректные значения, возвращается None. Некорректным значением считается значение не того типа, который ожидается.

Интерфейс:

def clean_and_tokenize(text: str) -> list[str]: 
    pass

Шаг 2. Получить список токенов без стоп-слов. Выполнение Шагов 1-2 соответствует 4 баллам

Функция принимает на вход список токенов и список стоп-слов.

Возвращаемым значением функции должен быть список токенов без стоп-слов.

Если на вход подаются некорректные токены или некорректный список стоп-слов, возвращается None. Пустой список стоп-слов не считается некорректным значением.

Интерфейс:

def remove_stop_words(tokens: list[str], stop_words: list[str]) -> list[str]:
 pass

Шаг 3. Получить частотный словарь по заданному тексту.

Функция принимает на вход список токенов.

Возвращаемым значением функции должен быть частотный словарь. Формат словаря: {токен: количество вхождений в список}. Например, для списка ['a', 'b', 'c', 'c', 'c', 'b'] частотный словарь должен выглядеть так: {'a': 1, 'b': 2, 'c': 3}

Если на вход подается некорректный аргумент, возвращается None. Некорректным аргумент считается в следующих случаях:

  • его тип отличается от ожидаемого типа
  • тип его содержимого отличается от ожидаемого
  • у него нет содержимого

Интерфейс:

def calculate_frequencies(tokens: list[str]) -> dict[str, int]:
 pass

Шаг 4. Получить список первых N по популярности слов. Выполнение Шагов 1-4 соответствует 6 баллам

Функция принимает на вход частотный словарь и число топ N слов.

Функция возвращает список первых N по популярности слов. Первый элемент списка - самое популярное слово. Последний элемент списка - N-ное по популярности слово.
Если число N больше числа слов в словаре, то возвращаются все слова в порядке убывания их частоты.

Если на вход подаются некорректные значения, возвращается None.

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

Интерфейс:

def get_top_n(frequencies: dict[str, int | float], top: int) -> list[str]:
 pass

Шаг 5. Рассчитать значения Term Frequency для каждого из слов в тексте

Term Frequency - это отношение числа вхождений некоторого слова к общему числу слов документа. Таким образом оценивается важность слова в пределах отдельного документа.

$$tf(t, d) = \frac{n_t}{N_d}$$

  • $n_t$ - количество вхождений слова $t$ в документ $d$,
  • $N_d$ - общее количество слов в документе $d$.

Напишите функцию, которая рассчитывает Term Frequency для токенов. Функция принимает на вход частотный словарь. Возвращаемым значением функции должен быть словарь, в котором ключами являются токены, а значениями - соответствующие им значения TF.

Если на вход подаются некорректные значения, возвращается None.

Интерфейс:

def calculate_tf(frequencies: dict[str, int]) -> dict[str, float]:
 pass

Шаг 6. Рассчитать значения TF-IDF для каждого из слов в тексте

TF-IDF - статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью
коллекции документов или корпуса. Она состоит из двух множителей - Term Frequency и Inverse Document Frequency.

$$TFIDF(t, d, D) = TF(t, d) \times IDF(t, D)$$

Множитель Inverse Document Frequency - инверсия частоты, с которой некоторое слово встречается в документах коллекции.

$$idf(t, D) = log(\frac{|D|}{|{d_i \in D : t \in d_i}| + 1})$$

Здесь числитель - общее количество документов в коллекции, а знаменатель - количество таких документов в коллекции, в которых встречается слово $t$.

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

Напишите функцию, которая вычисляет значение TF-IDF для каждого токена. Функция принимает на вход два словаря: словарь со значениями TF и словарь со значениями IDF. Функция должна возвращать словарь следующего формата: {слово: значение TF-IDF}. Если на вход подаются некорректные значения, возвращается None.

Готовые значения IDF, посчитанные с использованием коллекции сказок Г. Х. Андерсена, загружены для Вас в файле start.py. Они хранятся в переменной idf. Обратите внимание, что если какого из слов документа не окажется в словаре IDF, то это значит, что оно ни разу не встречалось ни в одном из документов коллекции. Поэтому IDF для этого слова можно рассчитать по формуле выше, подставив 0 вместо $|{d_i \in D : t \in d_i}|$ и 47 вместо $|D|$ (именно столько текстов содержится в рассматриваемой нами коллекции сказок).

Интерфейс:

def calculate_tfidf(term_freq: dict[str, float], idf: dict[str, float]) -> dict[str, float]:
 pass

Шаг 7. Продемонстрируйте топ-10 ключевых слов согласно TF-IDF. Выполнение Шагов 1-7 соответствует 8 баллам

Выведите 10 наиболее важных слов согласно значению TF-IDF при помощи функции print. Напомним, что чем выше значение TF-IDF, тем более важным считается слово.

В этом задании обязательно использование функции get_top_n.

Шаг 8. Рассчитать ожидаемую частотность слов

Попробуем выделить ключевые слова при помощи статистических методов.

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

$H_0:$ частотность слова $t$ в документе $d$ статистически значимо превышает его частотность в документах из коллекции $D$

$H_1:$ частотность слова $t$ в документе $d$ не превышает его частотность в документах из коллекции $D$

В этом задании вам нужно написать функцию, которая рассчитывает ожидаемую встречаемость слова. Это та встречаемость, которую слово бы имело, если бы оно не было ключевым.

Для этого необходимо найти следующие значения:

d D
t j k
~t l m
  • $j$ - количество вхождений слова $t$ в документ $d$
  • $k$ - количество вхождений слова $t$ во все тексты коллекции $D$
  • $l$ - количество вхождений всех слов, кроме $t$, в документ $d$
  • $m$ - количество вхождений всех слов, кроме $t$, в коллекцию документов $D$

Ожидаемая частотность слова $t$ в документе $d$ рассчитывается следующим образом:

$$Expected = \frac{( j + k ) \times (j + l)}{j + k + l + m}$$

Напишите функцию, которая рассчитывает значение ожидаемой частотности для каждого из слов документа. Функция должна принимать на вход два словаря: частотный словарь для документа, частотный словарь для коллекции. Возвращаемым значением должен быть словарь с ожидаемой частотностью. Если на вход подаются некорректные значения, возвращается None.

Частотный словарь для коллекции сказок Г. Х. Андерсена загружен для Вас в файле start.py. Он хранится в переменной corpus_freqs.

Интерфейс:

def calculate_expected_frequency(doc_freqs: dict[str, int], corpus_freqs: dict[str, int]) -> dict[str, float]:
 pass

Шаг 9. Рассчитать значения хи-квадрат

Для того, чтобы понять, достаточно ли сильно ожидаемая частотность превышает наблюдаемую, необходимо воспользоваться статистическим критерием. Для сравнения распределений хорошо подходит $\chi^2$ (хи-квадрат). Посчитать его можно по следующей сокращенной формуле:

$$\chi^2 = \frac{(observed - expected)^2}{expected}$$

При этом за наблюдаемую (observed) частотность мы принимаем то, сколько раз слово встретилось в анализируемом тексте.

Напишите функцию, которая рассчитывает $\chi^2$ для каждого из слов документа. Функция принимает на вход два словаря: словарь с ожидаемой частотностью и словарь с наблюдаемой частотностью.

Если на вход подаются некорректные значения, возвращается None

Интерфейс:

def calculate_chi_values(expected: dict[str, float], observed: dict[str, int]) ->  dict[str, float]:
 pass

Шаг 10. Выделить статистически значимые слова

Статистически значимыми словами считаются те, для которых значение $\chi^2$ превышает некое критическое значение.

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

Вероятность назвать неключевое слово ключевым называется уровнем значимости. Ниже представлен словарь с критическими значениями для разных уровней значимости: CRITERION = {0.05: 3.842, 0.01: 6.635, 0.001: 10.828} Здесь ключи - это уровень значимости, а значение - критическая точка хи-квадрат.

Напишите функцию, которая выделяет статистически выделенные ключевые слова.

Функция принимает на вход словарь со значениями хи-квадрат и уровень значимости. Функция должна вернуть словарь, в который помещены исключительно статистически значимые слова. Если на вход подаются некорректные значения, возвращается None.

Интерфейс:

def extract_significant_words(chi_values: dict[str, float], alpha: float) -> dict[str, float]:
 pass

Шаг 11. Вывести топ-10 ключевых слов согласно $\chi^2$. Выполнение Шагов 1-11 соответствует 10 баллам

Чем выше значение хи-квадрат для токена, тем больший вес имеет это слово. Выведите на экран 10 самых важных ключевых слов с точки зрения статистики. Ранжирование токенов необходимо производить с помощью функции get_top_n.

Узнать больше