3

Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Формат входного файла: на первой строке — разделенные пробелом число битовых строк n и число бит в строке m; на каждой следующей из n строк — битовая строка, заданная последовательностью из m нулей и единиц (см. примеры по ссылкам выше). Алгоритм должен вычислять число кластеров, сами кластеры возвращать не нужно.

Подскажите подход к решение задачи? Как эффективнее решать?

1 ответ 1

2

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

Суть его заключается в следующем:

  1. Исходные данные представляются в виде графа. Вершины -- это исходные объекты, веса рёбер -- это расстояния между объектами. Естественно, каждая вершина соединена с каждой.
  2. Из графа удаляются все ребра, веса которых больше заданного значения (в вашем случае больше 2).
  3. Граф разваливается на несколько связных компонент, каждая из которых представляет отдельный кластер.

Такой алгоритм хорошо сработает, если ваши исходные данные четко бьются на кластеры.

6
  • Вообще непонятно, имеет ли задача решение в общем случае... Например, возьмем для простоты, скажем, все 16 чисел от 0000 до 1111. Удалим все ребра >=3. Все равно все числа будут одним связным компонентом (см. код Грея).
    – Harry
    18 окт 2016 в 6:15
  • 1
    @Harry этот метод хорошо выделяет кластеры типа сгущений и лент. Последовательность -- это как раз лента, поэтому получится один кластер. В данном случае это недостаток, конечно. Данные обычно не случайны и имеют некоторые особенности. Исходя из этих особенностей и подбирается нужный алгоритм и его параметры. Одним из источников для принятия решения об алгоритме служит гистограмма попарных расстояний. В случае ленты она будет ровной. А для алгоритма выделения связных компонент лучше всего подходят данные с двумя пиками (один -- это внутрикластерные расстояния, второй -- межкластерные).
    – andreycha
    18 окт 2016 в 9:39
  • @Harry решить же задачу в общем случае для рандомных данных сложновато: придется динамически выбирать алгоритмы и не факт, что получится хороший результат. Что у вас в задаче? Есть какая-то особенность в данных?
    – andreycha
    18 окт 2016 в 9:40
  • У меня? ничего, это не моя задача. Меня просто заинтересовал ваш метод, не более того. Захотелось просто растолкать небольшой набор данных вручную - и тут у меня ничего не получилось. Вот я и задумался, а что будет в общем случае. Получается, при наличии цепочки решение не существует в принципе...
    – Harry
    18 окт 2016 в 9:57
  • @Harry ой, простите, не обратил внимания на ник, подумал, что вы автор вопроса :). Если в данных одна цепочка, то надо либо менять метрику, чтобы получить новую форму кластеров, либо использовать алгоритмы типа k-средних, но быть готовым к тому, что они вам эту ленту просто разобьют на N кластеров, и вы всегда найдете некоторое количество объектов из разных кластеров, у которых расстояние не (сильно) больше внутрикластерного.
    – andreycha
    18 окт 2016 в 12:11

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.