Кластеризация

Кластеризация - процесс разбиения некоторого множества объектов на кластеры по тому или иному критерию сходства или близости. При этом обучающего примера распределения объектов по кластеры нет.

Пороговый алгоритм кластеризации

Разберем этот алгоритм - один из самых простых. Есть некоторая функция вычисления близости или сходства объектов:

Distance(x,y);

1	Distance(x,y);

Часто её нужно задать самим на основе анализа особенностей задачи. Например, это может быть обычное расстояние между объектами, если нужно объединять в один кластер объекты, которые находятся рядом. Может быть и что-то другое.

Есть некоторый массив объектов, которые нужно разбить на кластеры:

x[number_of_objects];

1	x[number_of_objects];

В результате своей работы пороговый алгоритм найдёт число кластеров (number_of_classes) и сформирует массив с номерами кластеров, которым принадлежат объекты массива x:

class_of_x[number_of_classes];

1	class_of_x[number_of_classes];

Сам пороговый алгоритм выглядит так:

class_center[0] = x[0];
number_of_classes = 1;
class_of_x[0] = 0;
for (i = 1; i < number_of_objects; i++)
{
  min_distance = Distance(class_center[0],x[i]);
  class_of_x[i] = 0;
  for (j = 0; j < number_of_classes; j++)
  {
    if (Distance(class_center[j],x[i]) < min_distance)
    {
      min_distance = Distance(class_center[j],x[i]);
      class_of_x[i] = j;
    }
  }
  if (min_distance > thresold)
  {
    class_of_x[i] = number_of_classes;
    number_of_classes++;
    class_center[number_of_classes] = x[i];
  }
}

class_center[0] = x[0];

number_of_classes = 1;

class_of_x[0] = 0;

for (i = 1; i < number_of_objects; i++)

{

min_distance = Distance(class_center[0],x[i]);

class_of_x[i] = 0;

for (j = 0; j < number_of_classes; j++)

{

if (Distance(class_center[j],x[i]) < min_distance)

{

min_distance = Distance(class_center[j],x[i]);

class_of_x[i] = j;

}

if (min_distance > thresold)

{

class_of_x[i] = number_of_classes;

number_of_classes++;

class_center[number_of_classes] = x[i];

}

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

Результаты работы порогового алгоритма зависят от перестановки элементов массива x и от параметра thresold.

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