Как рассчитать центроиды в k-средних ++, используя расстояния?

Question

Я использую кластер k-means ++ от Apache Commons Math в интерактивном генетическом алгоритме, чтобы уменьшить количество индивидуумов, оцениваемых пользователем.

Commons Math делает его очень простым в использовании. Пользователь должен только реализовать Clusterable интерфейс. У него есть два метода:

double distanceFrom(T p), что совершенно ясно, и T centroidOf(Collection<T> p), что позволяет пользователю выбрать центр тяжести кластера.

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

Мой вопрос: существует ли эффективный общий способ выбора центроида, не зависящий от проблемной области? (Например, используя расстояние)

---

EDIT

Хорошо, вот мой код для расчета центроида. Идея: точка, которая имеет наименьшее общее расстояние до всех остальных точек, является ближайшей к центроиду.

public T centroidOf(Collection<T> c) {
  double minDist = Double.MAX_VALUE;
  T minP = null;

  // iterate through c
  final Iterator<T> it = c.iterator();
  while (it.hasNext()) {
    // test every point p1
    final T p1 = it.next();
    double totalDist = 0d;
    for (final T p2 : c) {
      // sum up the distance to all points p2 | p2!=p1
      if (p2 != p1) {
        totalDist += p1.distanceFrom(p2);
      }
    }

    // if the current distance is lower that the min, take it as new min
    if (totalDist < minDist) {
      minDist = totalDist;
      minP = p1;
    }
  }
  return minP;
}

Answer 1

k-означает требует усреднения метрики (например, евклидово).Не определяя такую ​​метрику и пространство, вы даже не знаете, является ли среднее число точек на самом деле точкой внутри пространства.

Однако вы можете использовать k-medoids , чторассматривает только исходные точки в качестве кандидатов на медоиды (в то время как k-means находит средние / центроиды, которые не обязательно находятся в исходных точках).Алгоритм ищет точки, которые минимизируют попарные различия (т. Е. distanceFrom).