Алгоритм K-means кластеризации

Данный алгоритм был построен в диалоге с нейросетью ChatGPT. Неудачные примеры кода, предлагаемые нейросетью, отвергались - и ей предлагалось уточнить решение. После этого некоторые куски кода содержали незначительные ошибки, которые правились руками.

Итог - очень впечатляющая работа нейросети. Например, новый метод IndexMinBy из соседнего диалога был сразу задействован нейросетью в текущем диалоге.

Нейросети предлагались несколько функций из стандартной библиотеки, которые делали то же, но эффективнее - она мгновенно учитывала советы.

Несколько вопросов было по переработке алгоритма. Например, нейросеть инициализировала центроиды кластеров уже имеющимися точками, что могло приводить к ошибке общего алгоритма. Ей было предложено изменить алгоритм генерации центроидов на случайные точки в прямоугольнике - она сразу поняла, что прямоугольник, о котором идет речь, - это минимумы-максимумы координат точек. И предложила алгоритм GenerateRandomCentroids.

Руками правились части кода, где надо было генерировать точки с помощью нового модуля Coords, а также с помощью библиотеки Mathnet.Numerics.dll - нейросеть конечно этого не знала.

Но основная канва кода в крупных командах близка к идеальной.

Итак, перед нами алгоритм KMeans выделения кластеров. Задаётся набор точек, количество кластеров, максимальное число итераций и минимальное расстояние между первоначальными центроидами.

Код:

{$reference Mathnet.Numerics.dll}
uses Mathnet.Numerics;
uses Coords;

function GenerateCluster(X, Y, deviation: real; count: integer): array of Point;
begin
  var xx := Generate.Normal(count, X, deviation);
  var yy := Generate.Normal(count, Y, deviation);
  Result := ArrGen(count, i -> Pnt(xx[i],yy[i]));
end;

function Distance(p1, p2: Point): real := Sqrt(Sqr(p1.x - p2.x) + Sqr(p1.y - p2.y));

function GenerateRandomCentroids(k: integer; points: array of Point; minDistance: real): array of Point;
begin
  var minX := points.Min(p -> p.x);
  var maxX := points.Max(p -> p.x);
  var minY := points.Min(p -> p.y);
  var maxY := points.Max(p -> p.y);
  var centroids := new List<Point>();
  while centroids.Count < k do
  begin
    // Случайная точка в пределах прямоугольника
    var candidate := new Point(
      RandomReal(minX, maxX),
      RandomReal(minY, maxY)
    );
    // Проверяем, что расстояние до всех ранее выбранных центроидов больше minDistance
    var isFarEnough := centroids.All(c -> Distance(c,candidate) >= minDistance);
    if isFarEnough then
      centroids.Add(candidate);
  end;
  Result := centroids.ToArray();
end;

function KMeans(points: array of Point; k: integer; maxIterations: integer; minDistance: real): (array of List<Point>, array of Point);
begin
  var n := points.Length;
  if k > n then
    raise new System.ArgumentException('Число кластеров не может быть больше числа точек');
  // Генерируем начальные центроиды случайно в пределах прямоугольника
  var centroids := GenerateRandomCentroids(k, points, minDistance);
  // Инициализация кластеров как массив списков с помощью ArrGen
  var clusters := ArrGen(k, i -> new List<Point>);
  for var iteration := 1 to maxIterations do
  begin
    // Шаг 1: Назначаем каждую точку ближайшему центроиду
    foreach var cluster in clusters do
      cluster.Clear(); // Очищаем списки на каждой итерации
    foreach var point in points do
    begin
      var nearestCentroidIndex := centroids.IndexMinBy(c -> Distance(point,c));
      clusters[nearestCentroidIndex].Add(point); // Добавляем точку в ближайший кластер
    end;
    // Шаг 2: Обновляем центроиды как средние точки своих кластеров
    var newCentroids := Copy(centroids); // Копируем центроиды
    for var i := 0 to k - 1 do
      if clusters[i].Count > 0 then
        newCentroids[i] := new Point(
          clusters[i].Average(p -> p.x),
          clusters[i].Average(p -> p.y)
        );
    // Проверяем, если центроиды не изменились, то завершаем
    if newCentroids.SequenceEqual(centroids) then
      break;
    centroids := newCentroids;
  end;
  Result := (clusters, centroids);
end;

begin
  // Сгенерируем исходные кластеры точек
  var cluster1 := GenerateCluster(5, 3, 2.5, 50);
  var cluster2 := GenerateCluster(7, -6, 1.5, 25);
  var cluster3 := GenerateCluster(-7, 2, 1, 44);
  
  var allPoints := cluster1 + cluster2 + cluster3;
  
  // Применяем алгоритм K-means для кластеризации
  var (clusters, centroids) := KMeans(allPoints, 3, 100, 2);
  
  DrawPoints(clusters[0].ToArray,3);
  DrawPoints(clusters[1].ToArray,3);
  DrawPoints(clusters[2].ToArray,PointRadius := 3);
  
  DrawPoint(centroids[0].x,centroids[0].y,PointRadius := 5);
  DrawPoint(centroids[1].x,centroids[1].y,PointRadius := 5);
  DrawPoint(centroids[2].x,centroids[2].y,PointRadius := 5);
end.

Вывод в графическом окне:

Немного не нравится необходимость преобразовывать списки к массивам с помощью ToArray. В Distance можно брать квадрат расстояния для ускорения, но оставил как есть.

Решение о моделировании кластеров пополняемыми списками нейросеть принимала сама. А вычисление nearestCentroidIndex с помощью indexMinBy просто красиво.