imported>Denaas: /* Assignment 10. */

2018-01-16T16:24:34Z

Assignment 10.

Новая страница

== Assignment 1. ==

1. Реализовать функцию fibonacci(n) вычисления n-ого числа Фибоначчи со сложностью не хуже O(n) по вренени

2. Реализуйте иерархию наследования с нетривиальной структурой (т.е. иерархия должна образовывать дерево / лес), не менее 6 классов. Например: группы языков, систематика животного мира и т.д. Продемонстрируйте на примере применение полиморфизма к решению какой то задачи. (Например, обслуживание зоопарка в случае животных).
P.S. укажите в комментариях к коду (например, в реализации класса зоопарка), в каком месте вы применяете полиформизм

3. Реализуйте средствами ООП паттерн поведения Singleton:
класс UniqObject реализует метод класса create_object, который возращает объект UniqObject. Объект UniqObject должен всегда существовать в единственном экземпляре.

Сделанная домашняя работа выкладывается в репозиторий в папку homework_1, решение каждого задания - в отдельный файл task_<номер задания>.py

== Assignment 2. ==

Цель задания - научится самостоятельно ориентроваться в документации к библиотекам.

[https://github.com/thedenaas/hse_seminars/blob/master/seminar_2/web%20mining.ipynb библиотека pattern]

[https://github.com/thedenaas/hse_seminars/blob/master/seminar_2/web%20mining.ipynb инструкция по установке]

[https://drive.google.com/file/d/0BzrfRHrbun42bWc1NjVIRlNKT1E/view?usp=sharing virtualbox image with preinstalled libraries] user: hse, password: hsepass

Вам необходимо написать программу, которая парсит статьи википедии (language=en) и считает по ним некоторые статистики.

1. Реализовать класс WikiParser с конструктором без аргументов и методом get_articles, который принимает название исходной статьи start, обходит все статьи википедии, на которые она ссылается, и возвращает список содержимого статей (с выполнением парсинга).
# При парсинге каждой статьи для того, чтобы убрать html теги, используется функция pattern.web.plaintext.
# В результате парсинга между соседними словами должно быть 1 пробел.
# В результате парсинга весь текст переводится в lowercase, знаки пунктуации выкидываются

Интерфейс:

class WikiParser:
def __init__(self):
pass
def get_articles(self, start, depth, max_count):
return list_of_strings

2. Реализовать класс TextStatistics с конструктором, который принимает в качестве аргумента список содержимого статей:
# get_top_3grams - возвращает tuple, первым элемент которого - список 3-грамм в порядке убывания их частот, второй элемент - соотвественно список сколько раз встретилась каждая 3грамма. Подсчет идет по всему корпусу articles. При подсчете 3-грамм исключить из рассмотрения все числа и пунктуацию.
# get_top_words - возвращает tuple, первым элемент которого - список слов в порядке убывания их частот, второй элемент - соотвественно список сколько раз встретилась каждое слово. Подсчет идет по всему корпусу articles. При подсчете слов исключить из рассмотрения все числа, предлоги, артикли и пунктуацию.

Интерфейс:

class TextStatistics:
def __init___(self, articles):
pass

def get_top_3grams(self, n):
return (list_of_3grams_in_descending_order_by_freq, list_of_their_corresponding_freq)

def get_top_words(self, n):
return (list_of_words_in_descending_order_by_freq, list_of_their_corresponding_freq)

3. Реализовать класс Experiment с методом show_results, который используя WikiParser и TextStatistics:
# Выполняет парсинг статей википедии для "Natural language processing"
# По полученному корпусу текстов считает топ-20 3-грамм и топ-20 слов.
# По статье "Natural language processing" (только по ней) считает топ-5 3-грамм и топ-5 слов.
# Печатает результаты эксперимента в структурированной форме

4. В комментариях после класса Experiment привести результаты выполнения метода show_results.

5. Результатом выполнения задания является код указанных классов и корректные результаты эксперимента

== Assignment 3. ==

Интерфейс
class WikiParser:
def __init__(self):
pass
def get_articles(self, start):
return list_of_strings

class TextStatistics:
def __init___(self, articles):
pass
def get_top_3grams(self, n, use_idf=False):
return (list_of_3grams_in_descending_order_by_freq, list_of_their_corresponding_freq)
def get_top_words(self, n, use_idf=False):
return (list_of_words_in_descending_order_by_freq, list_of_their_corresponding_freq)

Используя код из задания 2:
# Изменить логику работы WikiParser.get_articles - оставить знаки пунктуации, которые разделяют предложения.
# Изменить логику get_top_3grams - теперь под 3-граммами понимаются буквенные триграммы. Триграммы могут состоять из букв, цифр и не более 1 пробела подряд.
# Добавить в метод get_top_words параметр use_idf, при выставлении которого частоты умножаются на коэффициент IDF и соотвественно сортируются. IDF = log(<общее кол-во статей в корпусе> / <кол-во статей, в которых встретилось данное слово>)
# Добавить в метод get_top_3grams параметр use_idf, при выставлении которого частоты умножаются на коэффициент IDF и соотвественно сортируются. IDF = log (<общее кол-во предложений в корпусе> / <кол-во предложений, в которых встретилась данная триграмма>)
# написать unit тесты к классу TextStatistics, которые проверяют соблюдение описанных условий и корректность подсчета частот. Тесты должны покрывать граничные условия и разные варианты (в разумных пределах) аргументов, передаваемые в методы.
# выполнить эксперимент:
1 Выполнить парсинг статей википедии для "Natural language processing"
2 По полученному корпусу текстов посчитать топ-20 3-грамм и топ-20 слов с use_idf=True.
3 Печатает результаты эксперимента в структурированной форме
4 В комментариях после класса Experiment привести результаты выполнения метода show_results.
5 Результатом выполнения задания является код указанных классов в 1 файле *.py и корректные результаты эксперимента

!! обратите внимание, что вы кладете 3 дз в новый каталог homework_3, не внося изменения в каталог homework_2

!! обратите внимение, что теперь частоты - это действительные числа.

== Assignment 4. ==

По материалам 4 семинара:
# Модифицировать алгоритм Рабина-Карпа, чтобы он выполнял поиск нескольких паттернов в строке одновременно.
# Дать асимптотическую верхнюю оценку сложности O() реализованного алгоритма в зависимости от параметров T (длина текста), P_1, P_2, ..., P_n (длины паттернов)
# Написать юнит тесты к разработанному алгоритму
# работу оформить в виде скрипта *.py

Интерфейс:

def search_rabin_multi(text, patterns):
"""
text - строка, в которой выполняется поиск
patterns = [pattern_1, pattern_2, ..., pattern_n] - массив паттернов, которые нужно найти в строке text
По аналогии с оригинальным алгоритмом, функция возвращает массив [indices_1, indices_2, ... indices_n]
При этом indices_i - массив индексов [pos_1, pos_2, ... pos_n], с которых начинаетй pattern_i в строке text.
Если pattern_i ни разу не встречается в строке text, ему соотвествует пустой массив, т.е. indices_i = []
"""
pass

== Assignment 10. ==

По материалам 16 семинара провести исследование по тематическому моделированию и разработать рекомендательную систему.
# рекомендательная система обучается на корпусе текстов, в качестве корпуса текстов использовать 20 news groups из scikit-learn
# пользователь предъявляет образец текста (не обязательно из обучающего корпуса) и просит показать k похожих по тематике текстов
# в качестве моделей для тематического моделирования рассмотреть NMF, LSA, LDA
# в качестве метрик topic coherence рассмотреть [https://www.insight-centre.org/sites/default/files/publications/15.010_eswa2014_final_submit.pdf TC-W2C], [http://svn.aksw.org/papers/2015/WSDM_Topic_Evaluation/public.pdf UCI, Umass] для топ-20 слов-дескрипторов тем
# для каждой тематической модели определить оптимальное кол-во тем, а затем сравнить сами модели с помощью метрик topic coherence
# при выборе оптимального кол-ва тем постройте проверяйте дескрипторы тем
# таким образом, для каждой метрики вы получите свою оптимальную модель. Сравните дескрипторы тем у этих моделей, и выберите
# таким образом, вы получите тематическое представление для каждого документа. Выберите функцию расстояния между документами, посмотрите sklearn.metrics
# при поиске ближайших соседей используйте sklearn.neighbors
# работу оформить в виде ноутбука *.ipynb
# продемонстрируйте работу вашей рекомендательной системы на текстах из обучающего корпуса и текстах из bbc news за 2017 год

Интерфейс рекомендательной ситемы:

class NewsRecommender:
"""
обучить систему на корпусе текстов с помощью тематической модели и метрики, выбранных в результате исследования
"""
def train(self, texts):
pass
"""
выдать k самых пожих новостей для заданного заголовка по функции расстояния, выбранной в результате исследования
обратите внимание, что text_sample может содержать слова не из обучающего корпуса
"""
def recommend(self, text_sample, k):
return ["news_1", "news_2", ... , "news_k"]

Программирование (python) для лингвистов дз - История изменений

imported>Denaas: /* Assignment 10. */