Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- В этом задании мы рассмотрим задачу кластеризации объектов. Вам необходимо реализовать два алгоритма кластеризации, которые разбирались на лекциях:
- 1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;
- 2) Кластеризация жадным алгоритмом, приближенно минимизирующая максимальное внутрикластерное расстояние.
- Мы будем работать с текстами в виде векторов, где каждому отдельному слову соответсвует координатная ось.
- Текст разбивается на слова и для каждого слова считается количество его повторений.
- Такие вектора обычно содержат много нулей, поэтому мы их будем хранить в виде списка пар - id слова и количество повторений
- Вам дается код с заготовкой на Python, в котором реализованы три функции растояния, а также наборы текстов.
- test_5 - стартовый набор содержащий всего 50 тестов.
- test_4, test_10, test_50, test_100 - наборы на 400, 1000, 5000, 10000 соотвественно.
- Код python работает недостаточно эффективно для 1000+ текстов, поэтому рекомендуем запастить терпением или переписать существующий код на C++
- Запишите вашу реализацию в функцию cluster.
- Приведите примеры удачных и неудачных разбиений для каждого алгоритма.
- Каждый файл теста имеет вид
- N
- M
- K
- TextId WordID count
- ...
- TextId WordID count
- Где N - колчество текстов, M - количество уникальных слов, K - количество строк, TextId [1, N], WordId [1, M]
- Также вы можете найти файлы вида map_test_...txt - отображение слов для соответсвующих тестов в GlobalWordId
- vocab.nytimes.txt - содержит последовательно все слова. То есть iое слово в этом файле есть слово с GlobalWordId == i
- Обращаю внимание, что вся нумерация текстов и слов начинается с 1!!!
- Пояснения по коду:
- 1) filename - имя файла с тестом
- 2) distance - функция, используемая для подсчета расстояния
- 3) clusters_num(num_of_clusters) - желаемое количество кластеров
- 4) min_count и max_count - границы частоты учитываемых слов. То есть, слова которые встречаются во всех текстах менее чем min_count или более чем max_count не учитываются
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement