Чтобы сделать матрицу расстояний или многократно рассчитать расстояние

Я работаю над алгоритмом K-medoids. Это алгоритм кластеризации, и один из его шагов включает в себя поиск наиболее представительной точки в кластере.

Итак, здесь вещь

  • У меня есть определенное количество кластеров
  • Каждый кластер содержит определенное количество точек
  • Мне нужно найти точку в каждом кластере, которая приводит к наименьшей ошибке, если она выбрана в качестве представителя кластера.
  • Необходимо рассчитать расстояние от каждой точки до всего остального в кластере
  • Этот расчет расстояний может быть простым, как евклидово или более сложным, как DTW (динамическое временное деформирование) между двумя сигналами

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

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

С другой стороны, если вы не построите матрицу расстояний, вы повторите некоторые вычисления в определенном количестве итераций.

Каков наилучший подход?

Я также рассматриваю реализацию MapReduce, поэтому мнения с этой точки зрения также приветствуются.

Спасибо

Ответы

Ответ 1

Третий подход может быть комбинацией обоих и лениво оценивает матрицу расстояний. Инициализируйте матрицу со значениями по умолчанию (нереалистичными значениями, например отрицательными), и когда вам нужно рассчитать расстояние между двумя точками, если значения уже присутствуют в матрице - просто возьмите ее. В противном случае вычислите его и сохраните в матрице.

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

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

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