Статья
09/23/2015

Август 2015

Том 30, выпуск 8

Тесты - Кластеризация данных по алгоритму k-средних++

Исходный код можно скачать по ссылке msdn.microsoft.com/magazine/msdnmag0815.

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

Существует несколько алгоритмов кластеризации. Один из самых распространенных называется алгоритмом k-средних (k-means). У этого алгоритма несколько вариаций. В этой статье поясняется сравнительно недавно появившаяся вариация — алгоритм k-средних++.

Взгляните на демонстрационную программу на рис. 1. Программа начинает с 20 элементами данных, каждый из которых состоит из роста (в дюймах) и веса (в фунтах) какой-либо персоны. Затем количество кластеров выставляется равным 3. В большинстве сценариев кластеризации данных число кластеров должно указываться пользователем.

Рис. 1. Кластеризация по алгоритму k-средних++ в действии

Далее демонстрационная программа кластеризует данные, используя алгоритм k-средних++. Каждый из 20 элементов данных назначается одному из кластеров с идентификатором 0, 1 или 2. Сопоставления с кластерами хранятся в массиве, индекс которого соответствует индексу данных, а значение ячейки массива сопоставляется с идентификатором кластера. Например, конечная кластеризация демонстрационных данных выглядит так:

0 2 1 1 2 . . . 1

Здесь элемент данных 0 (height = 65.0, weight = 220.0) назначен кластеру 0, элемент данных 1 — кластеру 2, элемент данных 2 — кластеру 1 и т. д. Демонстрация завершается отображением данных, сгруппированных по кластерам. После этого открывается очень четкая закономерность. У нас имеются восемь человек со средним ростом и большим весом, семь человек с малым ростом и малым весом и пятеро с высоким ростом и средним весом.

В этой статье предполагается, что владеете навыками программирования хотя бы на среднем уровне, но ничего не знаете об алгоритме k-средних++. Демонстрационная программа написана на C#, но у вас не должно возникнуть особых трудностей в рефакторинге кода под другой язык, такой как JavaScript или Python. Код демонстрационной программы слишком длинный, чтобы показать его по всей полноте, но весь исходный код доступен для скачивания как пакет, сопутствующий этой статье.

Вникаем в алгоритм k-средних++

Алгоритм k-средних++ является вариацией стандартного алгоритма k-средних, поэтому, чтобы понять алгоритм k-средних++, вы должны сначала разобраться в обычных k-средних. Алгоритм k-средних имеет интересную историю и иногда называется алгоритмом Ллойда. Буква «k» в k-средних относится к числу кластеров. В очень высокоуровневом псевдокоде самая распространенная форма стандартных k-средних выглядит обманчиво простой:

Выбираем k начальных средних
Цикл до тех пор, пока не будет изменений
  Присваиваем каждому элементу данных ближайшее среднее
  Вычисляем новые средние на основе новых кластеров
Конец цикла

Несмотря на кажущуюся простоту, стандартный алгоритм k-средних является очень изощренным, а его реализация на удивление трудна. Допустим, что данные, подлежащие кластеризации, состоят из 20 элементов данных, показанных на рис. 1, и k присвоено значение 3. Первый шаг — выбор трех элементов данных, которые будут выступать в роли начальных средних. Зачастую элементы данных выбираются случайным образом. Предположим, что три случайно выбранных элемента данных — это элемент 2 (59.0, 110.0) как среднее кластера 0, элемент 4 (75.0, 150.0) как среднее кластера 1 и элемент 6 (68.0, 230.0) как среднее кластера 2.

В основном цикле обработки каждый элемент данных проверяется и назначается кластеру с ближайшим средним. Поэтому элемент данных 0 (65.0, 220.0) был бы назначен кластеру 2 — элемент 0 (68.0, 230.0) ближе, чем остальные два средних. Каждый из оставшихся 19 элементов данных будет назначен какому-либо кластеру. Заметьте, что элементы данных, изначально выбранные в качестве средних, были бы назначены правильному кластеру, так как разница была бы нулевой.

Каждый элемент данных назначается одному из кластеров, и для каждого кластера вычисляется новое среднее. Пусть кластер 0 сейчас содержит всего три элемента данных: (59.0, 110.0), (70.0, 210.0), (61.0, 130.0). Новое среднее для этого кластера будет таким:

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

Новые средние для кластеров 1 и 2 вычисляются аналогично. Заметьте, что новые средние не обязательно являются одним из истинных элементов данных. С технической точки зрения, каждое из новых средних — это так называемый центроид, но обычно используется термин «среднее».

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

Все это звучит сравнительно просто, но при наивной реализации стандартного алгоритма k-средних много чего может пойти не так. В частности, плохой выбор начальных средних может привести к очень плохой кластеризации данных или к очень долгому выполнению до стабилизации, или к тому и другому. Оказывается, хорошие начальные средние — те, которые не близки друг другу. Алгоритм k-средних++ выбирает начальные средние, не близкие друг другу, а затем использует для кластеризации стандартный алгоритм k-средних.

Механизм инициализации k-средних++

В высокоуровневом псевдокоде этот механизм для выбора средних выглядит так:

Выбираем один элемент данных случайным образом
  в качестве первого среднего
Цикл k-1 раз
  Вычисляем расстояние (отклонение) от каждого элемента
    до ближайшего среднего
  Выбираем элемент, имеющий большой квадрат расстояния
    в качестве следующего начального среднего
Конец цикла

И вновь псевдокод обманчиво прост. Механизм инициализации k-средних++ представлен на рис. 2. Здесь девять точек данных, каждая из которых имеет два компонента. Количество кластеров равно 3, поэтому в качестве начальных средних нужно отобрать три элемента данных.

Рис. 2. Механизм инициализации k-средних++

Nine data items in two-dimension into three clusters	Девять элементов данных в двух измерениях в трех кластерах
Least likely third mean (smallest distance^2)	Наименее вероятное третье среднее (наименьшее расстояние^2)
First initial mean	Первое начальное среднее
Second initial mean	Второе начальное среднее
Most likely third mean (largest distance^2)	Наиболее вероятное третье среднее (наибольшее расстояние^2)

Схема на рис. 2 показывает процесс инициализации k-средних++ после того, как были выбраны два из трех начальных средних. Первое начальное среднее в точке (3, 6) было выбрано случайно. Затем был вычислен квадрат расстояния между первым средним и остальными восемью элементами данных; на основе этой информации было выбрано второе среднее в точке (4, 3) (способом, о котором я вскоре расскажу).

Чтобы выбрать элемент данных в качестве третьего начального среднего, вычисляется квадрат расстояния от каждой точки данных до ее ближайшего среднего. Расстояния отображены пунктирными линиями. Используя эти значения квадрата расстояния, третье среднее будет выбрано по следующему принципу: элементы данных с малыми значениями квадрата расстояния имеют низкую вероятность выбора, а элементы данных с большими значениями квадрата расстояния — высокую вероятность выбора. Этот метод иногда называют выбором пропорционально качеству (proportional fitness selection).

Выбор пропорционально качеству занимает центральное место в механизме инициализации k-средних++. Существует несколько способов реализации выбора пропорционально качеству. В демонстрационной программе используется метод, называемый выбором с помощью колеса рулетки (roulette wheel selection). В высокоуровневом псевдокоде одна из форм выбора с помощью колеса рулетки выглядит так:

p = случайное значение между 0.0 и 1.0
Создаем массив накопленных вероятностей
Цикл по каждой ячейке массива накопленных вероятностей
  if cum[i] >= p
    return i
  end if
Конец цикла

Конкретный пример поможет прояснить выбор с помощью колеса рулетка. Допустим, у нас есть четыре элемента-кандидата (0, 1, 2, 3) с сопоставленными значениями (20.0, 10.0, 40.0, 30.0). Сумма значений равна 20.0 + 40.0 + 10.0 + 30.0 = 100.0. Метод выбора пропорционально качеству отберет элемент 0 с вероятностью 20.0/100.0 = 0.20, элемент 1 — с вероятностью 10.0/100.0 = 0.10, элемент 2 — с вероятностью 40.0/100.0 = 0.40 и элемент 3 — с вероятностью 30.0/100.0 = 0.30.

Если вероятности выбора хранятся в массиве как (0.20, 0.10, 0.40, 0.30), накопленные вероятности (cumulative probabilities) можно хранить в массиве со значениями (0.20, 0.30, 0.70, 1.00). Теперь предположим, что для p случайным образом генерируется значение 0.83. Если i — индекс в массиве накопленных вероятностей, то, когда i = 0, cum[i] = 0.40, что не превышает p = 0.83, то i увеличивается на 1. Теперь cum[i] = 0.60, что по-прежнему не больше p, поэтому i увеличивается до 2. Теперь cum[i] = 0.70, что больше p, и i = 2 возвращается как выбранный элемент.

Заметьте, что расстояния между накопленными вероятностями различаются, причем большие различия соответствуют элементам с более высокими вероятностями выбора.

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

Общая структура программы

Общая структура программы с небольшими правками для экономии места представлена на рис. 3. Чтобы создать демонстрационную программу, я запустил Visual Studio и создал новое консольное приложение на C# с названием KMeansPlus. В этой программе нет значимых зависимостей от .NET, поэтому подойдет любая сравнительно недавняя версия Visual Studio.

Рис. 3. Общая структура программы

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // Сюда помещается весь код программы
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

После загрузки кода шаблона в редактор Visual Studio я переименовал в окне Solution Explorer файл Program.cs в более описательный KMeansPlusProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все выражения using, которые указывали на ненужные пространства имен, оставив только ссылки на System и Collections.Generic.

Метод Main начинает с подготовки 20 исходных элементов данных:

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

В реальном сценарии вы, вероятно, считывали бы данные из текстового файла или база данных SQL. После отображения исходных данных вызовом вспомогательного метода ShowData происходит кластеризация данных:

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

Хотя существуют некоторые методы, позволяющие догадаться, какое количество кластеров лучшее, в принципе, следует идти по пути проб и ошибок. Метод Cluster принимает числовые исходные данные для кластера в матрице в стиле массив массивов, количество используемых кластеров (я мог бы использовать обозначение «k», но numClusters более удобочитаемое имя) и зародышевое значение (seed value) для рандомизации.

Метод Main завершается отображением кластерного массива и выводом исходных данных, сгруппированных по кластерам:

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

Я использовал подход со статическими методами, а не ООП. Метод Cluster вызывает четыре вспомогательных метода. Вспомогательный метод Normalized принимает матрицу исходных данных и возвращает матрицу с нормализованными данными, чтобы все значения были примерно одного порядка (обычно в диапазоне между –6.0 и +6.0). Метод InitMeans реализует механизм инициализации k-средних++. Методы UpdateClustering и UpdateMeans реализуют базовые части стандартного алгоритма k-средних.

Методы InitMeans и UpdateClustering вызывают вспомогательный метод Distance, который возвращает евклидово расстояние (Euclidean distance) между двумя элементами данных. Например, если один кортеж данных (data tuple) равен (3.0, 9.0, 5.0), а второй — (2.0, 6.0, 1.0), то евклидово расстояние между двумя элементами составит:

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

Можно использовать другие определения расстояния. В целом, алгоритмы k-средних и k-средних++ применяются для кластеризации строго численных данных, а не категориальных.

Реализация k-средних++

Код для метода Cluster представлен на рис. 4. Метод Cluster начинает с нормализации исходных данных, так чтобы большие компоненты в элементах данных (например, значения веса в демонстрации) не доминировали над меньшими компонентами (значениями роста). В демонстрации применяется гауссово распределение (Gaussian normalization). Две распространенные альтернативы — нормализация min-max (min-max normalization) и нормализация порядка величин (order of magnitude normalization). В качестве проектировочной альтернативы нормализацию исходных данных можно выполнять на стадии предобработки, а затем передавать нормализованные данные непосредственно в метод Cluster.

Рис. 4. Метод Cluster

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

Метод InitMeans реализует механизм инициализации k-средних++ и возвращает набор средних, которые находятся далеко друг от друга в терминах евклидова расстояния. В основном цикле кластеризации метод UpdateClustering перебирает в цикле каждый элемент данных, назначая его кластеру, который сопоставлен с ближайшим текущим средним/центроидом. Метод возвращает false, если в назначениях кластеров больше никаких изменений нет (указывая на завершение кластеризации) или если новая кластеризация привела бы к появлению кластера без элементов данных (указывая на какую-то проблему). Альтернатива — генерировать исключение в ситуации с пустым кластером.

Метод UpdateMeans перебирает в цикле данные, назначенные каждому кластеру, и вычисляет новое среднее/центроид для каждого кластера. Этот метод возвращает false, если одно или более средних нельзя вычислить из-за того, что в кластере нет никаких элементов данных.

В основном цикле кластеризации используется проверка «вменяемости счетчика» (sanity count check), чтобы предотвратить бесконечный цикл. Алгоритм k-средних обычно стабилизируется очень быстро, но нет никаких гарантий, что этот алгоритм вообще когда-нибудь стабилизируется. Значение maxCount устанавливается в 10 раз большим количества элементов данных, что выбрано произвольно, но хорошо работало у меня на практике.

Определение метода InitMeans начинается с:

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

Локальная матрица в стиле массив массивов с именем means хранит то, что вернул метод; в этой матрице индекс строки — идентификатор кластера, а каждая строка — это массив, хранящий компоненты сопоставленного среднего. List<int> с именем used содержит индексы элементов данных, назначенные в качестве начальных средних, поэтому можно предотвратить дублирование начальных средних. Этот подход предполагает отсутствие элементов данных с одинаковыми значениями. При кластеризации способ обработки дублирующихся элементов данных зависит от вашей конкретной задачи. Одна из альтернатив удаления дублирующихся элементов из исходных данных — весовая оценка дублирующихся элементов по их частоте.

Затем выбирается и сохраняется первое начальное среднее:

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

Первое начальное среднее выбирается случайным образом изо всех элементов данных. Начальные средние — это существующие элементы данных, и они иногда называются медоидами (medoids).

Затем конструируется цикл for для выбора оставшихся k–1 средних:

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

Массив dSquared хранит квадраты расстояний между каждым элементом данных и ближайшим существующим начальным средним. Переменная newMean содержит индекс элемента данных, который будет следующим начальным средним. Далее каждый (нормализованный) элемент данных проверяется, а затем вычисляется и сохраняется его значение dSquared:

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

Проверка для определения того, что элемент данных уже использовался в качестве начального среднего, на самом деле не требуется, так как, если элемент использовался, квадрат расстояния до ближайшего среднего будет расстоянием до него самого, т. е. нулевым. Массив distances содержит евклидовы расстояния от текущего элемента данных до каждого из существующих начальных k-средних, выбранных на данный момент.

Вспомните, что евклидово расстояние в методе Distance — это квадратный корень от суммы квадратов разности между компонентами элемента данных. Поскольку алгоритм k-средних++ использует квадраты расстояний, операция возведения в квадрат в InitMeans отменяет операцию извлечения квадратного корня в Distance. Поэтому вы могли бы упростить код, определив метод, который напрямую возвращает квадрат расстояния.

Далее подготавливается цикл сканирования накопленных вероятностей для метода выбора с помощью колеса рулетки:

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

Генерируется случайное значение в диапазоне от 0.0 до 1.0, и вычисляется сумма квадратов расстояний, как пояснялось в разделе, описывающем выбор пропорционально качеству. Вместо того чтобы явно создавать массив накопленных вероятностей, эффективнее генерировать текущую накопленную вероятность «на лету».

Каждая накопленная вероятность вычисляется и анализируется в цикле while, который реализует метод выбора с помощью колеса рулетки:

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // выбранный индекс
    used.Add(newMean); // не выбираем повторно
    break;
  }
  ++ii; // следующий кандидат
  if (ii >= dSquared.Length) ii = 0; // мимо конца
  ++sanity;
}

Цикл while продвигается, пока значение накопленной вероятности больше или равно случайного значения p. Однако нельзя допускать появления дублирующихся начальных средних, поэтому, если выбранное среднее присутствует в used типа List<int>, выбирается следующий доступный элемент данных. Если индекс ii выходит за конец данных, он сбрасывается в 0. Заметьте: если элемент данных уже выбран в качестве начального среднего, следующий доступный элемент данных, возможно, не будет следующим наиболее приемлемым элементом.

Метод InitMeans завершается сохранением выбранного начального среднего и возвратом массива выбранных средних:

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, каждое остающееся среднее
  return means;
} // InitMean

Цель метода InitMeans — найти k неодинаковых элементов данных для использования в качестве начальных средних. Выбор с помощью колеса рулетки не гарантирует, что выбранные средние максимально отличаются друг от друга, и есть очень малый шанс того, что выбранные средние могут оказаться довольно близкими друг другу. Поэтому вы, возможно, предпочтете переработать метод InitMeans так, чтобы метод выбора с помощью колеса рулетки применялся несколько раз для генерации кандидатов наборов средних с последующим возвратом набора, содержащего средние, наиболее отличные друг от друга.

Заключение

Эта статья основана на научно-исследовательской статье 2007 года «K-means++: The Advantages of Careful Seeding» за авторством Д. Артура (D. Arthur) и С. Вассилвицкого (S. Vassilvitskii). Как почти всегда в научно-исследовательских статьях, практически никаких деталей реализации не дается. Однако эта статья исчерпывающе разъясняет, как работает инициализация k-средних++, и определяет теоретические границы для ее поведения.

Джеймс Маккафри (Dr. James McCaffrey) работает на Microsoft Research в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и Bing. С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Microsoft Research Кирку Олинику (Kirk Olynyk).