Кластеризация данных

  • Статья

Обнаружение аномальных данных методом k-средних

Джеймс Маккафри

Продукты и технологии:

C#, Visual Studio 2010

В статье рассматриваются:

  • алгоритм кластеризации k-средних (k-means clustering algorithm);
  • вычисление центров масс для кластеров (cluster centroids);
  • евклидова метрика (Euclidian distance);
  • поиск аномальных данных.

Исходный код можно скачать по ссылке.

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

Алгоритмов кластеризации много. Один из старейших и наиболее широко применяемых — алгоритм (или метод) k-средних (k-means algorithm). В этой статье я объясню, как работает алгоритм k-средних, и представлю законченную демонстрационную программу на C#. Существует много отдельных инструментов для кластеризации данных, но тогда зачем может понадобиться писать код кластеризации k-средних с нуля? Существующие инструменты может быть трудно или невозможно интегрировать в программную систему, они могут оказаться не адаптируемыми под необычные сценарии, а кроме того, с ними могут быть связаны проблемы авторского права или других прав на интеллектуальную собственность. Прочитав эту статью, вы сможете экспериментировать с кластеризацией k-средних и получить базовые познания, необходимые для добавления функциональности кластеризации в какое-либо .NET-приложение.

Лучший способ прочувствовать, для чего нужна кластеризация k-средних, и понять, к чему я клоню в этой статье, — взглянуть на рис. 1. Демонстрационная программа начинает с создания фиктивного набора из 20 элементов данных. В терминологии кластеризации элементы данных иногда называют последовательностью из n-чисел (tuples). Здесь каждая такая последовательность представляет некое лицо (person) и имеет два числовых атрибута: рост в дюймах и вес в фунтах. Одно из ограничений алгоритма k-средних в том, что он применяется только в случаях, где последовательности данных полностью числовые.

Кластеризация с применением k-средних
Рис. 1. Кластеризация с применением k-средних

Фиктивные данные загружаются в память в виде массива. Затем количество кластеров задается равным трем. Хотя существуют более совершенные методы кластеризации, способные предложить оптимальное количество кластеров, в целом, кластеризация данных — процесс исследовательский, и подходящее число кластеров обычно подбирается методом проб и ошибок. Как вы вскоре увидите, кластеризация k-средних — это итеративный процесс. В демонстрационной программе есть переменная maxCount, которая ограничивает количество выполнений основного цикла кластеризации. Здесь это значение произвольно выбрано равным 30.

Потом «за кулисами» демонстрационная программа использует алгоритм k-средних, чтобы поместить каждую последовательность данных в один из трех кластеров. Способов кодирования кластеризации много. В данном случае кластеризация определяется массивом значений типа int, где индекс массива представляет последовательность данных (tuple), а связанное с массивом значение — идентификатор кластера с нумерацией от 0. Итак, на рис. 1 последовательность 0 (65.0, 220.0) назначена кластеру 0, последовательность 1 (73.0, 160.0) — кластеру 1, последовательность 2 (59.0, 110.0) — кластеру 2, последовательность 3 (61.0, 120.0) — кластеру 2 и т. д. Обратите внимание на то, что восемь последовательностей назначено кластеру 0, пять последовательностей — кластеру 1, а семь последовательностей — кластеру 2.

Далее демонстрационная программа отображает данные, сгруппированные по кластерам. Если вы изучите кластеризованные данные, то заметите, что кластер 0 можно было бы назвать кластером полных людей, кластер 1 — высоких людей, а кластер 2 — низкорослых людей. Анализируя последовательности, назначенные кластеру 0, демонстрационная программа определяет по некоему критерию, что последовательность 5 (67.0, 240.0) является наиболее аномальной.

В следующих разделах я пошагово пройду по коду, с помощью которого был получен результат на экране (рис. 1), чтобы вы смогли потом модифицировать этот код под свои потребности. В этой статье предполагается, что вы по крайней мере на среднем уровне владеете навыками программирования на языках семейства C, но ничего не знаете о кластеризации данных. Я кодировал демонстрационную программу на C#, но избегал стиля объектно-ориентированного программирования (ООП), поэтому у вас не возникнет особых трудностей в рефакторинге этой программы под другой язык. Весь исходный код демонстрационной программы представлен в этой статье; его также можно скачать по ссылке archive.msdn.microsoft.com/mag201302kmeans.

Алгоритм k-средних

По крайней мере в принципе, алгоритм k-средних довольно прост. Но, как вы еще увидите, некоторые детали реализации весьма изощренные. Главной концепцией алгоритма k-средних является центроид (centroid), или центр масс. В кластеризации данных центр масс набора последовательностей данных — это одна из последовательностей, которая является наиболее репрезентативной в группе. Эту идею лучше пояснить на примере. Допустим, у вас есть три последовательности «рост, вес», аналогичные показанным на рис. 1:

[a] (61.0, 100.0)
[b] (64.0, 150.0)
[c] (70.0, 140.0)

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

[m] = ((61.0 + 64.0 + 70.0) / 3, (100.0 + 150.0 + 140.0) / 3)
    = (195.0 / 3, 390.0 / 3)
    = (65.0, 130.0)

А теперь, какая из трех последовательностей ближе всего к (65.0, 130.0)? Есть несколько способов определить ближайшую последовательность. Самый распространенный способ, применяемый в демонстрационной программе, — использование евклидового расстояния, или метрики (Euclidean distance). Если на словах, то евклидово расстояние между двумя последовательностями является корнем квадратным суммы квадратов разностей между соответствующими компонентами каждой последовательности. И вновь это лучше пояснить на примере. Евклидово расстояние между последовательностью (61.0, 100.0) и средней последовательностью (65.0, 130.0) равно:

dist(m,a) = sqrt((65.0 - 61.0)^2 + (130.0 - 100.0)^2)
          = sqrt(4.0^2 + 30.0^2)
          = sqrt(16.0 + 900.0)
          = sqrt(916.0)
          = 30.27

Аналогично:

dist(m,b) = sqrt((65.0 - 64.0)^2 + (130.0 - 150.0)^2)
          = 20.02
dist(m,c) = sqrt((65.0 - 70.0)^2 + (130.0 - 140.0)^2)
          = 11.18

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

Освоив понятие центра масс кластера, вы довольно легко поймете алгоритм k-средних. В псевдокоде:

Назначаем каждую последовательность случайно выбранному кластеру
Вычисляем центр масс каждого кластера
loop пока нет улучшений или не будет достигнут maxCount
  Присваиваем каждую последовательность лучшему кластеру
   (кластеру с ближайшим центром масс к последовательности)
  Обновляем центр масс каждого кластера
   (на основе новых назначений кластерам)
end loop
return кластеризованные данные

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

Кластерные данные и центры масс

Рис. 2. Кластерные данные и центры масс

Weight (pounds) Вес (в фунтах)
Cluster 0 Кластер 0
Cluster 1 Кластер 1
Cluster 2 Кластер 2
Height (inches) Рост (в дюймах)

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

Общая структура демонстрационной программы с рис. 1 с небольшими правками показана на рис. 3. С помощью Visual Studio 2010 я создал новое консольное приложение на C# под названием «ClusteringKMeans»; для работы с этим проектом подойдет любая недавняя версия Visual Studio. В окне Solution Explorer я переименовал файл Program.cs в ClusteringKMeansProgram.cs, что автоматически повлекло переименование класса, генерируемого шаблоном. Я удалил ненужные выражения using в начале файла.

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

using System;
namespace ClusteringKMeans
{
  class ClusteringKMeansProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin outlier data detection demo\n");
        Console.WriteLine("Loading all (height-weight) data into memory");
        string[] attributes = new string[] { "Height", "Weight" };
        double[][] rawData = new double[20][];
        rawData[0] = new double[] { 65.0, 220.0 };
        rawData[1] = new double[] { 73.0, 160.0 };
        rawData[2] = new double[] { 59.0, 110.0 };
        rawData[3] = new double[] { 61.0, 120.0 };
        rawData[4] = new double[] { 75.0, 150.0 };
        rawData[5] = new double[] { 67.0, 240.0 };
        rawData[6] = new double[] { 68.0, 230.0 };
        rawData[7] = new double[] { 70.0, 220.0 };
        rawData[8] = new double[] { 62.0, 130.0 };
        rawData[9] = new double[] { 66.0, 210.0 };
        rawData[10] = new double[] { 77.0, 190.0 };
        rawData[11] = new double[] { 75.0, 180.0 };
        rawData[12] = new double[] { 74.0, 170.0 };
        rawData[13] = new double[] { 70.0, 210.0 };
        rawData[14] = new double[] { 61.0, 110.0 };
        rawData[15] = new double[] { 58.0, 100.0 };
        rawData[16] = new double[] { 66.0, 230.0 };
        rawData[17] = new double[] { 59.0, 120.0 };
        rawData[18] = new double[] { 68.0, 210.0 };
        rawData[19] = new double[] { 61.0, 130.0 };
        Console.WriteLine("\nRaw data:\n");
        ShowMatrix(rawData, rawData.Length, true);
        int numAttributes = attributes.Length;
        int numClusters = 3;
        int maxCount = 30;
        Console.WriteLine("\nk = " + numClusters + " and maxCount = " + maxCount);
        int[] clustering = Cluster(rawData, numClusters, numAttributes, maxCount);
        Console.WriteLine("\nClustering complete");
        Console.WriteLine("\nClustering in internal format: \n");
        ShowVector(clustering, true);
        Console.WriteLine("\nClustered data:");
        ShowClustering(rawData, numClusters, clustering, true);
        double[] outlier = Outlier(rawData, clustering, numClusters, 0);
        Console.WriteLine("Outlier for cluster 0 is:");
        ShowVector(outlier, true);
        Console.WriteLine("\nEnd demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
   // Здесь находятся 14 определений статических методов
  }
}

Для простоты я использовал подход со статическими методами и убрал всю проверку на ошибки. Первая часть демонстрационного кода подготавливает данные по росту и весу к кластеризации. Поскольку последовательностей всего 20, я «зашил» эти данные в код и помещаю их в памяти в виде массива rawData. Обычно данные хранятся в текстовом файле или SQL-таблице. В таких случаях вы должны написать вспомогательную функцию для загрузки данных в память. Если ваш источник данных слишком велик, вам придется модифицировать код так, чтобы он перебирал источник внешних данных, а не массив.

По крайней мере в принципе, алгоритм k-средних довольно прост. Но, как вы еще увидите, некоторые детали реализации весьма изощренные.

После подготовки исходных данных демонстрационная программа вызывает вспомогательную функцию ShowMatrix для отображения данных. Затем переменным numAttributes, numClusters и maxCount присваиваются значения 2 (height и weight), 3 и 30 соответственно. Вспомните, что maxCount ограничивает число итераций основного цикла обработки алгоритма. Алгоритм k-средних имеет тенденцию к быстрому схождению, но вам может понадобиться немного поэкспериментировать со значением maxCount.

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

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

Вычисление центров масс кластеров

Вспомните, что центр масс (центроид) кластера — это последовательность, наиболее репрезентативная среди остальных последовательностей, назначенных кластеру, и один из способов определить центр масс кластера — вычисление средней последовательности с поиском последовательности, ближайшей к средней. Среднюю последовательность в каждом кластере вычисляет вспомогательный метод UpdateMeans (рис. 4).

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

static void UpdateMeans(double[][] rawData, int[] clustering,
  double[][] means)
{
  int numClusters = means.Length;
  for (int k = 0; k < means.Length; ++k)
    for (int j = 0; j < means[k].Length; ++j)
      means[k][j] = 0.0;
  int[] clusterCounts = new int[numClusters];
  for (int i = 0; i < rawData.Length; ++i)
  {
    int cluster = clustering[i];
    ++clusterCounts[cluster];
    for (int j = 0; j < rawData[i].Length; ++j)
      means[cluster][j] += rawData[i][j];
  }
  for (int k = 0; k < means.Length; ++k)
    for (int j = 0; j < means[k].Length; ++j)
      means[k][j] /= clusterCounts[k]; // опасность
  return;
}

Метод UpdateMeans предполагает, что массив массивов с именем means уже существует, а вовсе не создает его и не возвращает. Так как предполагается, что массив means имеется, вы, вероятно, предпочтете сделать его параметром, передаваемым по ссылке (ref parameter). Массив means создается вспомогательным методом Allocate:

static double[][] Allocate(int numClusters, int numAttributes)
{
  double[][] result = new double[numClusters][];
  for (int k = 0; k < numClusters; ++k)
    result[k] = new double[numAttributes];
  return result;
}

Первый индекс массива means представляет идентификатор кластера, а второй — указывает атрибут. Например, если means[0][1] = 150.33, то среднее значение веса (1) в последовательности в кластере 0 составляет 150.33.

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

Метод ComputeCentroid (рис. 5) определяет значения центра масс, т. е. значения одной последовательности, ближайшей к последовательности с усредненными значениями для данного кластера.

Рис. 5. Метод ComputeCentroid

static double[] ComputeCentroid(double[][] rawData, int[] clustering,
  int cluster, double[][] means)
{
  int numAttributes = means[0].Length;
  double[] centroid = new double[numAttributes];
  double minDist = double.MaxValue;
  for (int i = 0; i < rawData.Length; ++i) // Перебираем каждую последовательность данных
  {
    int c = clustering[i]; 
    if (c != cluster) continue;
    double currDist = Distance(rawData[i], means[cluster]);
    if (currDist < minDist)
    {
      minDist = currDist;
      for (int j = 0; j < centroid.Length; ++j)
        centroid[j] = rawData[i][j];
    }
  }
  return centroid;
}

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

Метод UpdateCentroids вызывает ComputeCentroid для каждого кластера, чтобы определить центры масс всех кластеров:

static void UpdateCentroids(double[][] rawData, int[] clustering,
  double[][] means, double[][] centroids)
{
  for (int k = 0; k < centroids.Length; ++k)
  {
    double[] centroid = ComputeCentroid(rawData, clustering, k, means);
    centroids[k] = centroid;
  }
}

Метод UpdateCentroids предполагает, что массив массивов с именем centroids уже существует. Массив centroids очень похож на массив means: первый индекс представляет идентификатор кластера, а второй — указывает атрибут данных.

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

Функция Distance и нормализация данных

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

static double Distance(double[] tuple, double[] vector)
{
  double sumSquaredDiffs = 0.0;
  for (int j = 0; j < tuple.Length; ++j)
    sumSquaredDiffs += Math.Pow((tuple[j] - vector[j]), 2);
  return Math.Sqrt(sumSquaredDiffs);
}

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

Другой важный фактор, связанный с выбором функции вычисления метрики в алгоритме кластеризации k-средних, — нормализация данных. Демонстрационная программа использует исходные, ненормализованные данные. Поскольку значения веса в последовательностях — это обычно величины вроде 160.0, а значения роста — на уровне 67.0, разница в значениях веса имеет гораздо большее влияние, чем разница в значениях роста. Во многих ситуациях, исходные данные полезно нормализовать перед кластеризацией. Сделать это можно разными методами. Распространенный способ — вычисление среднего (m) и стандартного отклонения (standard deviation, sd) для каждого атрибута, а затем вычисление для значения каждого атрибута (v) нормализованного значения nv = (v–m)/sd.

Назначение каждой последовательности кластеру

Располагая методом вычисления центроида каждого кластера, можно написать метод для назначения каждой последовательности кластеру. Метод Assign представлен на рис. 6.

Рис. 6. Метод Assign

static bool Assign(double[][] rawData, 
  int[] clustering, double[][] centroids)
{
  int numClusters = centroids.Length;
  bool changed = false;
  double[] distances = new double[numClusters];
  for (int i = 0; i < rawData.Length; ++i)
  {
    for (int k = 0; k < numClusters; ++k)
      distances[k] = Distance(rawData[i], centroids[k]);
    int newCluster = MinIndex(distances);
    if (newCluster != clustering[i])
    {
      changed = true;
      clustering[i] = newCluster;
    }
  }
  return changed;
}

Метод Assign принимает массив centroids и перебирает каждую последовательность данных. Для каждой из последовательностей вычисляется расстояние до каждого центроида кластера и сохраняется локальный массив с именем distances, индекс которого представляет идентификатор кластера. Затем вспомогательный метод MinIndex определяет индекс в массиве distances, где хранится наименьшее значение метрики, и это соответствует кластеру, центр масс которого находится ближе всего к данной последовательности.

Вот как выглядит вспомогательный метод MinIndex:

static int MinIndex(double[] distances)
{
  int indexOfMin = 0;
  double smallDist = distances[0];
  for (int k = 0; k < distances.Length; ++k)
  {
    if (distances[k] < smallDist)
    {
      smallDist = distances[k]; indexOfMin = k;
    }
  }
  return indexOfMin;
}

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

Эта реализация алгоритма k-средних предполагает, что каждому кластеру всегда назначена хотя бы одна последовательность данных. Как видно на рис. 6, метод Assign не предотвращает ситуации, где кластеру вообще не назначается ни одной последовательности. На практике это обычно не проблема. Предотвратить ошибочную ситуацию не так-то просто. Подход, который я обычно применяю, заключается в создании массива centroidIndexes, работающий в сочетании с массивом centroids. Вспомните, что массив centroids содержит значения центров масс, например (61.0, 120.0) — это центр масс для кластера 2 на рис. 2. Массив centroidIndexes хранит сопоставленный индекс последовательности, скажем [3]. Затем в методе Assign мы первым делом назначаем каждому кластеру последовательность данных, которая содержит значения центра масс, и только после этого метод перебирает остальные последовательности и назначает их кластерам. Такой подход гарантирует, что в каждом кластере будет минимум одна последовательность.

Метод Cluster

Метод Cluster (рис. 7) — высокоуровневая процедура, которая вызывает все вспомогательные методы, выполняющие реальную работу по кластеризации данных.

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

static int[] Cluster(double[][] rawData, int numClusters,
  int numAttributes,  int maxCount)
{
  bool changed = true;
  int ct = 0;
  int numTuples = rawData.Length;
  int[] clustering = InitClustering(numTuples, numClusters, 0);
  double[][] means = Allocate(numClusters, numAttributes);
  double[][] centroids = Allocate(numClusters, numAttributes);
  UpdateMeans(rawData, clustering, means);
  UpdateCentroids(rawData, clustering, means, centroids);
  while (changed == true && ct < maxCount)
  {
    ++ct;
    changed = Assign(rawData, clustering, centroids);
    UpdateMeans(rawData, clustering, means);
    UpdateCentroids(rawData, clustering, means, centroids);
  }
  return clustering;
}

Основной цикл while повторно назначает каждую последовательность данных кластеру, вычисляет новую последовательность усредненных значений для каждого кластера, а затем использует ее для вычисления новых значений центра масс для каждого кластера. Цикл прекращается, когда не происходит изменений в назначениях кластеров или когда достигается максимальное количество итераций. Поскольку массив means применяется только для вычисления центров масс, вы, возможно, захотите провести рефакторинг Cluster, поместив вызов UpdateMeans внутрь метода UpdateCentroids.

Перед запуском цикла обработки метод InitClustering инициализирует массив clustering:

static int[] InitClustering(int numTuples, 
  int numClusters, int randomSeed)
{
  Random random = new Random(randomSeed);
  int[] clustering = new int[numTuples];
  for (int i = 0; i < numClusters; ++i)
    clustering[i] = i;
  for (int i = numClusters; i < clustering.Length; ++i)
    clustering[i] = random.Next(0, numClusters);
  return clustering;
}

Метод InitClustering сначала назначает последовательности от 0 до numClusters–1 кластерам от 0 до numClusters–1 соответственно, благодаря чему изначально в каждом кластере будет минимум одна последовательность. Остальные последовательности назначаются случайно выбранным кластерам.

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

Поиск аномальных данных

Один из способов использования кластеризации данных — простой анализ различных кластеров и поиск неожиданных или выпадающих результатов. Другая возможность — поиск необычных последовательностей данных в кластере. Демонстрационная программа проверяет кластер 0, чтобы найти последовательность в этом кластере, находящуюся дальше всего от центра масс кластера, используя метод Outlier, показанный на рис. 8.

Рис. 8. Метод Outlier

static double[] Outlier(double[][] rawData, int[] clustering,
  int numClusters, int cluster)
{
  int numAttributes = rawData[0].Length;
  double[] outlier = new double[numAttributes];
  double maxDist = 0.0;
  double[][] means = Allocate(numClusters, numAttributes);
  double[][] centroids = Allocate(numClusters, numAttributes);
  UpdateMeans(rawData, clustering, means);
  UpdateCentroids(rawData, clustering, means, centroids);
  for (int i = 0; i < rawData.Length; ++i)
  {
    int c = clustering[i];
    if (c != cluster) continue;
    double dist = Distance(rawData[i], centroids[cluster]);
    if (dist > maxDist)
    {
      maxDist = dist;
      Array.Copy(rawData[i], outlier, rawData[i].Length);
    }
  }
  return outlier;
}

После инициализации массивов means и centroids метод Outlier перебирает каждую последовательность в указанном кластере и вычисляет евклидово расстояние (метрику) от текущей последовательности до центра масс (центроида) кластера, а затем возвращает значения последовательности, которая имеет наибольшее расстояние до центроида. В качестве альтернативы можно возвращать индекс самой дальней последовательности данных.

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

Процедуры отображения

Для полноты картины ниже показаны некоторые упрощенные процедуры отображения. В пакете исходного кода эти процедуры посложнее. Если вы используете упрощенные процедуры, то должны будете модифицировать их вызовы в методе Main. Чтобы отобразить исходные данные, средние и центры масс, вы можете применить:

static void ShowMatrix(double[][] matrix)
{
  for (int i = 0; i < numRows; ++i)
  {
    Console.Write("[" + i.ToString().PadLeft(2) + "]  ");
    for (int j = 0; j < matrix[i].Length; ++j)
      Console.Write(matrix[i][j].ToString("F1") + "  ");
    Console.WriteLine("");
  }
}

Для вывода массива clustering можно использовать:

static void ShowVector(int[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i] + " ");
  Console.WriteLine("");
}

Чтобы показать выпадающие данные:

static void ShowVector(double[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i].ToString("F1") + " ");
  Console.WriteLine("");
}

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

static void ShowClustering(double[][] rawData, 
  int numClusters, int[] clustering)
{
  for (int k = 0; k < numClusters; ++k) // Каждый кластер
  {
    for (int i = 0; i < rawData.Length; ++i) // Каждая последовательность
      if (clustering[i] == k)
      {
        for (int j = 0; j < rawData[i].Length; ++j)
          Console.Write(rawData[i][j].ToString("F1") + " ");
        Console.WriteLine("");
      }
    Console.WriteLine("");
  }
}

Заключение

Кластеризация данных тесно связана с классификацией (категоризацией) данных, и эти концепции иногда путают. Кластеризация — это неконтролируемая методика, которая обеспечивает группирование элементов данных без предварительного знания того, что представляют собой эти группы. Кластеризация, как правило, является исследовательским процессом. Классификация, напротив, представляет собой контролируемую методику, которая требует спецификации известных групп в обучающих данных (training data), после чего каждая последовательность данных помещается в одну из этих групп. Классификация обычно применяется в целях прогнозирования.

Код и пояснения, представленные в этой статье, должны дать вам достаточно информации для экспериментов с кластеризацией k-средних, для создания обособленных полностью настраиваемых средств кластеризации или для добавления средств кластеризации в .NET-приложение, не полагающиеся ни на какие внешние зависимости. Существует много других алгоритмов кластеризации, помимо вычисления k-средних, и я представляю некоторые из них в будущих статьях, в том числе минимизацию энтропии данных, оценку категорий (category utility) и байесовский вывод (naive Bayes inference).

Джеймс Маккафри (Dr. James McCaffrey) — руководит в компании Volt Information Sciences Inc. повышением квалификации инженеров ПО из Microsoft, работающих в Редмонде (штат Вашингтон). Принимал участие в создании нескольких продуктов Microsoft, в том числе Internet Explorer и MSN Search. Автор книги «.NET Test Automation Recipes» (Apress, 2006). С ним можно связаться по адресу jammc@microsoft.com.

Выражаю благодарность за рецензирование статьи эксперту Даррену Герингу (Darren Gehring).