Advertisement
Guest User

Untitled

a guest
Oct 17th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.35 KB | None | 0 0
  1. В этом задании мы рассмотрим задачу кластеризации объектов. Вам необходимо реализовать два алгоритма кластеризации, которые разбирались на лекциях:
  2.  
  3. 1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;
  4. 2) Кластеризация жадным алгоритмом, приближенно минимизирующая максимальное внутрикластерное расстояние.
  5.  
  6. Мы будем работать с текстами в виде векторов, где каждому отдельному слову соответсвует координатная ось.
  7. Текст разбивается на слова и для каждого слова считается количество его повторений.
  8. Такие вектора обычно содержат много нулей, поэтому мы их будем хранить в виде списка пар - id слова и количество повторений
  9.  
  10. Вам дается код с заготовкой на Python, в котором реализованы три функции растояния, а также наборы текстов.
  11. test_5 - стартовый набор содержащий всего 50 тестов.
  12. test_4, test_10, test_50, test_100 - наборы на 400, 1000, 5000, 10000 соотвественно.
  13. Код python работает недостаточно эффективно для 1000+ текстов, поэтому рекомендуем запастить терпением или переписать существующий код на C++
  14. Запишите вашу реализацию в функцию cluster.
  15. Приведите примеры удачных и неудачных разбиений для каждого алгоритма.
  16.  
  17. Каждый файл теста имеет вид
  18. N
  19. M
  20. K
  21. TextId WordID count
  22. ...
  23. TextId WordID count
  24. Где N - колчество текстов, M - количество уникальных слов, K - количество строк, TextId [1, N], WordId [1, M]
  25.  
  26. Также вы можете найти файлы вида map_test_...txt - отображение слов для соответсвующих тестов в GlobalWordId
  27. vocab.nytimes.txt - содержит последовательно все слова. То есть iое слово в этом файле есть слово с GlobalWordId == i
  28. Обращаю внимание, что вся нумерация текстов и слов начинается с 1!!!
  29.  
  30. Пояснения по коду:
  31. 1) filename - имя файла с тестом
  32. 2) distance - функция, используемая для подсчета расстояния
  33. 3) clusters_num(num_of_clusters) - желаемое количество кластеров
  34. 4) min_count и max_count - границы частоты учитываемых слов. То есть, слова которые встречаются во всех текстах менее чем min_count или более чем max_count не учитываются
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement