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

Кластеризация данных с использованием наивного байесовского вывода

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

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

Visual Studio 2010, C#

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

• алгоритмы кластеризации данных;
• демонстрационная программа, основанная на наивном байесовском выводе;
• что такое наивный байесовский вывод;
• алгоритм INBIAC.

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

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

Существует много различных алгоритмов кластеризации — отчасти потому, что эффективность алгоритма кластеризации до некоторой степени зависит от характеристик данных. Наиболее распространенный алгоритм называется кластеризацией k-средних. К сожалению, этот алгоритм применим лишь для числовых элементов данных. В противоположность этому, алгоритм кластеризации, который я представлю в этой статье, основан на методике, называемой наивным байесовским выводом (Naive Bayes inference), и он работает либо с категориальными данными, либо с числовыми. Хотя все идеи, используемые в представленном здесь алгоритме кластеризации, хорошо известны, алгоритм в целом и конкретная реализация, насколько мне известно, никогда раньше не публиковались. Я называю этот алгоритм и его реализацию агломерационной кластеризацией итеративного наивного байесовского вывода (Iterative Naive Bayesian Inference Agglomerative Clustering, INBIAC), чтобы отличать его от других методологий кластеризации. Наивный байесовский вывод — очень распространенная методология для классификации данных, но, в целом, немногим известно, что его можно применять и для кластеризации данных.

Лучший способ понять, куда я клоню в этой статье, — взглянуть на рис. 1. Демонстрационная программа начинает с генерации восьми случайных последовательностей чисел (tuples), описывающих место жительства (город, пригород или сельская местность), доход (низкий, средний, высокий или очень высокий) и политические взгляды (либерал или консерватор) восьми гипотетических лиц. Затем программа загружает исходные строковые данные в память и преобразует данные в int-значения для эффективной обработки. Например, последняя последовательность («Rural», «Low», «Conservative») хранится как (2, 0, 1).

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

Многие алгоритмы кластеризации, в том числе INBIAC, требуют указывать набор кластеров. Здесь переменная numClusters равна 3. Демонстрационная программа организует данные в кластеры, а затем отображает окончательное объединение в кластеры [2, 0, 2, 1, 1, 2, 1, 0]. На внутреннем уровне алгоритм инициализирует кластеры 0, 1 и 2 последовательностями 1, 6 и 0 соответственно. Потом кластеру присваиваются оставшиеся пять последовательностей — по одной за раз. Этот тип алгоритма называют агломерационным.

Поскольку здесь не требуется ни обучающих данных, ни вмешательства пользователя, кластеризацию иногда называют неконтролируемым обучением (unsupervised learning). Каждый индекс в массиве кластерных данных представляет последовательность, а значение в массиве является идентификатором кластера. Итак, последовательность 2 («Suburban», «VeryHigh», «Conservative») назначается кластеру 0, последовательность 1 («Rural», «Medium», «Conservative»)— кластеру 2 и т. д.

Эффективность алгоритма кластеризации до некоторой степени зависит от характеристик данных.

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

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

Я удалил из программы всю обработку ошибок, чтобы не засорять общую картину. Исходный код демонстрационной программы слишком велик для этой статьи, поэтому я сосредоточусь на объяснении ключевых частей алгоритма. Полный исходный код демонстрационной программы можно скачать по ссылке archive.msdn.microsoft.com/mag201303INBIAC.

Структура программы

Общая структура программы показана на рис. 2 (часть комментариев и выражений WriteLine удалена).

Рис. 2. Структура программы кластеризации

using System;
using System.Collections.Generic;
namespace ClusteringBayesian
{
  class ClusteringBayesianProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin data clustering using Naive Bayes demo\n");
        random = new Random(6); // зародыш, равный 6, дает
                                // хорошую демонстрацию
        int numTuples = 8;
        Console.WriteLine("Generating " + numTuples +
          "tuples of location-income-politics data");
        string[] rawData = MakeData(numTuples);
        Console.WriteLine("\nRaw data in string form is:\n");
        ShowData(rawData, numTuples);
        string[] attNames = new string[] { "Location", "Income", "Politics" };
        string[][] attValues = new string[attNames.Length][];
        // Место жительства
        attValues[0] = new string[] { "Urban", "Suburban", "Rural" };
        // Доход
        attValues[1] = new string[] { "Low", "Medium", "High", "VeryHigh" };
        // Политические убеждения
        attValues[2] = new string[] { "Liberal", "Conservative" };
        Console.WriteLine("Loading raw data into memory\n");
        string[][] tuples = LoadData(rawData, attValues);
        Console.WriteLine("Converting raw data to int form and"
          + "storing in memory\n");
        int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
        Console.WriteLine("Data in int form is:\n");
        ShowData(tuplesAsInt, numTuples);
        // Получаем хорошие зародышевые индексы
        // (разные последовательности)
        int numClusters = 3;
        int numTrials = 10;
        Console.WriteLine("\nSetting numClusters to " + numClusters);
        Console.WriteLine("\nInitializing Naive Bayes joint " +
          "counts with Laplacian smoothing");
        int[][][] jointCounts = InitJointCounts(tuplesAsInt,
          attValues, numClusters);
        int[] clusterCounts = new int[numClusters];
        Console.WriteLine("\nBegin clustering data using " +
          "Naive Bayes (with equal priors) ");
        int[] clustering = Cluster(tuplesAsInt, numClusters, numTrials,
          jointCounts, clusterCounts, true);
        Console.WriteLine("Clustering complete");
        Console.WriteLine("\nClustering in internal form is:\n");
        for (int i = 0; i < clustering.Length; ++i)
          Console.Write(clustering[i] + " ");
        Console.WriteLine("Raw data displayed in clusters is:\n");
        DisplayClustered(tuplesAsInt, numClusters, clustering, attValues);
        Console.WriteLine("\nEnd demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
    // Остальные методы размещаются здесь
  } // конец класса
} // ns

Я использовал Visual Studio 2010 для создания консольного приложения на C# — ClusteringBayesian. В окне Solution Explorer я переименовал файл Program.cs в более описательный ClusteringBayesianProgram.cs, что привело к автоматическому переименованию единственного класса. Лишние ссылки на пространства имен .NET, сгенерированные шаблоном, я удалил; заметьте, что у программы мало зависимостей, и ей требуется лишь пространство имен Systems.Collections.Generic.

Я объявил в рамках класса объект Random с именем random. Это объект используется для генерации псевдослучайных исходных данных и для того, чтобы определить, какие последовательности следует задействовать для инициализации каждого кластера. В методе Main я создал экземпляр random с зародышевым значением, равным 6, — это значение позволяет создать вполне приличную демонстрацию.

В следующих нескольких строках демонстрационной программы вспомогательные методы MakeData и ShowData генерируют и отображают восемь строк фиктивных данных. MakeData вызывает другие вспомогательные методы: MakeParty, MakeLocation, MakeIncome и MakePolitics. Если вы хотите поэкспериментировать с «зашитыми» в код последовательностями данных, замените этот код, например, таким:

int numTuples = 4;
string[] rawData = new string[] { "Urban,VeryHigh,Liberal",
  "Rural,Medium,Conservative", "Urban,Low,Liberal",
  "Suburban,Medium,Liberal" };

Далее в демонстрационную программу «зашиваются» атрибуты Location, Income и Politics. В некоторых сценариях, например, если ваши исходные данные находятся в текстовом файле с заголовком или в SQL-таблице с именами полей, вы, возможно, захотите просканировать свои данные и программным способом определить имена атрибутов.

В демонстрационную программу также «зашиты» значения атрибутов: Urban, Suburban и Rural (для Location), Low, Medium, High и VeryHigh (для Income) и Liberal и Conservative (для Politics). И вновь в некоторых сценариях вы предпочтете сканировать исходные данные и программным способом определять значения атрибутов.

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

Хотя можно напрямую работать с исходными строковыми данными, гораздо эффективнее иметь дело с данными, кодированными как тип int. Поэтому далее вспомогательный метод TuplesToInts принимает массив массивов строк, сканирует его, преобразует каждую строку в индекс, отсчитываемый от 0, и сохраняет все данные в массиве массивов типа int. И вновь в случае очень больших наборов данных вам, вероятно, понадобится считывать исходные данные по строке за раз и «на лету» преобразовывать значения атрибута в int-значения.

Демонстрационная программа подготавливает процедуру кластеризации, присваивая значения двум параметрам. Параметр numClusters — это число генерируемых кластеров. В целом, кластеризация данных является исследовательским процессом, и вы должны поэкспериментировать с различными значениями numClusters (впрочем, есть некоторые изящные методологии для программного определения оптимального количества кластеров). Параметр numTrials используется процедурой кластеризации при генерации начальной кластеризации, как я поясню несколько позже.

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

Метод кластеризации требует двух массивов для хранения счетчиков назначенных на данный момент последовательностей в алгоритме INBIAC. Массив jointCounts хранит число помещенных в кластер последовательностей, имеющих определенное значение атрибута и определенный кластер. Массив jointCounts не так прост, и вскоре я расскажу о нем подробнее. Но каждое значение в jointCounts инициализируется единицей, и это важный этап в байесовской методологии, называемый сглаживанием Лапласа (Laplacian smoothing). Второй массив, clusterCounts, хранит количество последовательностей, назначенных на данный момент каждому кластеру. Индекс clusterCounts представляет кластер, а значение — сопоставленный счетчик.

Кластеризация выполняется методом Cluster. Этот метод возвращает массив, который кодирует, какой кластер назначен каждой последовательности. Демонстрационная программа завершает свою работу, отображая массив кластеризации и исходные данные, сгруппированные по кластеру; при этом используется вспомогательный метод DisplayClustered.

Наивный байесовский вывод

Ключ к познанию алгоритма INBIAC, который позволит вам модифицировать демонстрационный код под свои потребности, — понимание наивного байесовского вывода. Наивный байесовский вывод лучше всего пояснять на примере. Допустим, у вас имеются восемь последовательностей, показанных на рис. 1, и вы хотите поместить каждую последовательность в один из трех кластеров:

[0] Suburban VeryHigh  Liberal
[1] Rural    Medium    Conservative
[2] Suburban VeryHigh  Conservative
[3] Suburban Low       Liberal
[4] Suburban High      Liberal
[5] Suburban Low       Conservative
[6] Urban    Low       Liberal
[7] Rural    Low       Conservative

Для начала предположим, что каждый кластер принимает единственную зародышевую последовательность (способом, который я поясню позже), и в итоге последовательность 1 назначается кластеру 0, последовательность 6 — кластеру 1, а последовательность 0 — кластеру 2. Есть несколько способов представить эту кластеризацию, но алгоритм INBIAC сохранил бы информацию в виде массива:

[  2,  0, -1, -1, -1, -1,  1, -1 ]

В этом массиве индексы являются последовательностями, значения — кластерами, а значение –1 указывает соответствующую последовательность, еще не назначенную какому-либо кластеру. Поэтому, с концептуальной точки зрения, кластеризация к этому моменту выглядит так:

c0 : Rural    Medium   Conservative  (tuple 1)
c1 : Urban    Low      Liberal       (tuple 6)
c2 : Suburban VeryHigh Liberal       (tuple 0)

Теперь цель — назначить первую еще не назначенную последовательность, последовательность 2 (Suburban, VeryHigh, Conservative), одному из трех кластеров. При наивном байесовском выводе вычисляются вероятности того, что последовательность 2 может относиться к кластерам 0, 1 и 2, а затем последовательность назначается кластеру с наибольшей вероятностью. Выражая это в символическом виде, если X = (Suburban, VeryHigh, Conservative), а c0 обозначает кластер 0, мы хотим:

P(c0 | X)
P(c1 | X)
P(c2 | X)

Первую вероятность можно интерпретировать как «вероятность кластера 0 при данных значениях X». Теперь потерпите минутку. Чтобы вычислить эти условные вероятности (conditional probabilities), вы должны вычислить элементы, которые я называю частными производными вероятностями (partial probabilities, PP). Получив частные вероятности для каждой из условных вероятностей (conditionals), можно сказать, что вероятность для каждого кластера равна PP для каждого кластера, деленной на сумму всех PP. В символьном виде это выглядит так:

P(c0 | X) = PP(c0 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c1 | X) = PP(c1 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c2 | X) = PP(c2 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]

Частная вероятность для P(c0 | X) равна:

PP(c0 | X) = P(Suburban | c0) *
             P(VeryHigh | c0) *
             P(Conservative | c0) *
             P(c0)
           = count(Suburban     & co) / count c0 *
             count(VeryHigh     & co) / count c0 *
             count(Conservative & c0) / count c0 *
             P(c0)

Эти уравнения взяты из теории Байеса и совсем не очевидны. Термин «наивный» в байесовском выводе означает, что каждый из членов вероятности (probability terms) в частных вероятностях предполагается математически независимым, что сильно упрощает вычисления по сравнению с тем, если бы члены вероятности были математически зависимы.

Последний член, P(c0), является «вероятностью кластера 0». Этот член иногда называют априорной вероятностью (prior), и его можно вычислить одним из двух способов. Первый способ — предположить равные априорные вероятности, и тогда P(c0) = P(c1) = P(c2) = 1/3. Другой способ — исходит из неравенства априорных вероятностей и использовать текущие счетчики назначенных последовательностей, в каковом случае P(c0) = count(c0) / (count(c0) + count(c1) + count(c2)). В случае алгоритма INBIAC предпочтительно предполагать равные априорные вероятности.

Заметьте, что в уравнениях нужны так называемые объединенные счетчики (joint counts). Например, count(Suburban & c0) — это счетчик назначенных последовательностей, где кластер — c0, а атрибут Location последовательности равен Suburban.

Если вы вернетесь к текущей кластеризации, то увидите проблему: в данный момент, когда кластерам назначены лишь первые три зародышевые последовательности, count(Suburban & c0) равен 0, а значит, его член тоже — 0, что обнуляет всю частную производную вероятность. Чтобы избежать этого, все объединенные счетчики инициализируются значением 1. Это называют сглаживанием Лапласа. При сглаживании Лапласа в знаменатели условных вероятностей (но не в член безусловной вероятности [unconditional probability term]) также добавляется 3 — количество кластеров. Поэтому модифицированное вычисление частной вероятности для c0 выглядит следующим образом:

PP(c0 | X) = P(Suburban     | c0) *
             P(VeryHigh     | c0) *
             P(Conservative | c0) *
             P(c0)
           = count(Suburban     & co) / (count c0 + 3) *
             count(VeryHigh     & co) / (count c0 + 3) *
             count(Conservative & c0) / (count c0 + 3) *
             1 / numClusters
           = (1 / 4) * (1 / 4) * (2 / 4) * (1 / 3)
           = 0.0104

Аналогично частные вероятности для c1 и c2 равны:

PP(c1 | X) = count(Suburban     & c1) / (count c1 + 3) *
             count(VeryHigh     & c1) / (count c1 + 3) *
             count(Conservative & c1) / (count c1 + 3) *
             1 / numClusters
           = (1 / 4) * (1 / 4) * (1 / 4) * (1 / 3)
           = 0.0052
PP(c2 | X) = count(Suburban     & c2) / (count c2 + 3) *
             count(VeryHigh     & c2) / (count c2 + 3) *
             count(Conservative & c2) / (count c2 + 3) *
             1 / numClusters
           = (2 / 4) * (2 / 4) * (1 / 4) * (1 / 3)
           = 0.0208

Рассчитав частные вероятности для каждого кластера, легко вычислить вероятности для каждого кластера, которые нужны для назначения последовательности 1 какому-либо кластеру. Вот эти вычисления:

P(c0 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
          = 0.0104 / (0.0104 + 0.0052 + 0.0208)
          = 0.2857
P(c1 | X) = PP(X | c1) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
          = 0.0052 / (0.0104 + 0.0052 + 0.0208)
          = 0.1429
P(c2 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
          = 0.0208 / (0.0104 + 0.0052 + 0.0208)
          = 0.5714

Последовательность назначается кластеру с наивысшей вероятностью, а это в данном случае кластер c2.

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

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

Ключевые структуры данных

Существует несколько способов хранения разнообразных данных, используемых алгоритмом кластеризации INBIAC. На рис. 3 показана большая часть структур данных, используемых демонстрационной программой. Массив jointCounts предназначен для вычисления частных вероятностей, которые в свою очередь применяются для расчета вероятностей кластеров, а те — для назначения последовательности кластеру. Для каждой комбинации значения атрибута и кластера имеется один объединенный счетчик. Значит, для демонстрационной программы, поскольку в ней девять значений атрибутов (Urban, Suburban,... Conservative) и три кластера, существуют 9 * 3 = 27 объединенных счетчиков. Первый индекс в jointCounts указывает атрибут, второй — значение атрибута, а третий — кластер. Например, jointCounts[1][3][2] хранит счетчик назначенных последовательностей, где Income (1) равен VeryHigh (3), а кластер — (2).

Рис. 3. Ключевые структуры данных

Алгоритм INBIAC инициирует каждый кластер одной последовательностью. Важно, чтобы эти зародышевые последовательности как можно сильнее отличались друг от друга.

Массив кластеризации кодирует, как последовательности назначаются кластерам. Индекс массива кластеризации представляет последовательность, а значение ячейки — кластер. Например, если clustering[0] = 2, то последовательность 0 назначена кластеру 2. Значения ячеек, равные –1, указывают на то, что соответствующие последовательности пока не назначены какому-либо кластеру.

Реализация метода кластеризации

Метод Cluster показан на рис. 4. Этот метод принимает массив tuplesAsInt (данные, подлежащие кластеризации), numClusters (число используемых кластеров), numTrials (присваивает начальные последовательности кластерам), jointCounts (уже пояснялось), clusterCounts (количество последовательностей, назначенных каждому кластеру; необходимо при вычислениях с неравными априорными вероятностями) и equalPriors (булево значение, указывающее, как вычислять вероятности каждого кластера при расчете частных вероятностей).

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

static int[] Cluster(int[][] tuplesAsInt, int numClusters,
  int numTrials, int[][][] jointCounts, int[] clusterCounts,
  bool equalPriors)
{
  int numRows = tuplesAsInt.Length;
  int[] clustering = new int[numRows];
  for (int i = 0; i < clustering.Length; ++i)
    clustering[i] = -1;
  int[] goodIndexes = GetGoodIndexes(tuplesAsInt, numClusters, numTrials);
  for (int i = 0; i < goodIndexes.Length; ++i)
  {
    int idx = goodIndexes[i];
    clustering[idx] = i;
  }
  for (int i = 0; i < goodIndexes.Length; ++i)
  {
    int idx= goodIndexes[i];
    for (int j = 0; j < tuplesAsInt[idx].Length; ++j)
    {
      int v = tuplesAsInt[idx][j];
      ++jointCounts[j][v][i];     // очень хитрая индексация
    }
  }
  for (int i = 0; i < clusterCounts.Length; ++i)
    ++clusterCounts[i];
  for (int i = 0; i < tuplesAsInt.Length; ++i)
  {
    if (clustering[i] != -1) continue; // последовательность
                                       // уже кластеризована
    double[] allProbabilities = AllProbabilities(tuplesAsInt[i],
      jointCounts, clusterCounts, equalPriors);
    int c = IndexOfLargestProbability(allProbabilities);
    clustering[i] = c;  // назначаем последовательность i
                        // кластеру c
    for (int j = 0; j < tuplesAsInt[i].Length; ++j)
    {
      int v = tuplesAsInt[i][j];
      ++jointCounts[j][v][c];
    }
    ++clusterCounts[c];
  } // Основной цикл
  return clustering;
}

Метод Cluster начинает с выделения памяти для массива кластеризации и присваивания значений –1 каждой ячейке, указывая, что ни одному кластеру не была назначена какая-либо последовательность. Затем вызывается вспомогательный метод GetGoodIndexes, чтобы получить индексы последовательностей, которые максимально отличаются друг от друга. Я вскоре поясню метод GetGoodIndexes. Потом метод Cluster использует «хорошие индексы» («good indexes») для инициализации массива кластеризации и обновляет массивы jointCounts и clusterCounts.

Основной цикл обработки перебирает каждую последовательность данных по порядку и вычисляет вероятности того, что текущая последовательность может принадлежать каждому из кластеров; при этом используется метод AllProbabilities. Далее определяется индекс с наивысшей вероятностью с помощью вспомогательного метода IndexOfLargestProbability. Поскольку нумерация кластеров отсчитывается от 0, этот индекс также представляет лучший кластер, и он используется для назначения текущей последовательности кластеру (в массиве кластеризации), а затем для обновления массивов jointCounts и clusterCounts.

Поскольку цикл обработки всегда начинает с последовательности [0], это в конечном счете дает больший вес последовательностям с меньшими номерами индексов. Альтернативный вариант — перебирать последовательности в случайном порядке. Заметьте, что алгоритм INBIAC присваивает последовательности на основе наивысшей вероятности членства в кластере. Вы также могли бы вычислять и возвращать среднее этих наивысших вероятностей. Это было бы мерой достоверности (confidence) в назначениях кластеров. Затем можно было бы вызвать метод Cluster несколько раз и вернуть результаты кластеризации, полученные вызовом, который дал максимальную достоверность.

Другой вариант, который я часто использую, — постобработка результата кластеризации, полученного методом Cluster, чтобы попытаться сгенерировать более качественный результат кластеризации. Эта идея в псевдокоде выражается так:

цикл n раз
  выбор случайного индекса последовательности
  отмена назначения последовательности ее текущему кластеру
  назначение последовательности, применяя вычисления
    с неравными априорными вероятностями
конец цикла

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

Получение хороших начальных зародышевых последовательностей

Алгоритм INBIAC инициирует каждый кластер одной последовательностью. Важно, чтобы эти зародышевые последовательности (seed tuples) как можно сильнее отличались друг от друга. Существует много критериев расхождения (dissimilarity), применяемых в алгоритмах кластеризации. Метод GetGoodIndexes генерирует набор случайных индексов-кандидатов (candidate indexes), а затем вычисляет общее количество отличающихся атрибутов последовательностей — эта метрика называется расстоянием Хемминга (Hamming distance). Данный процесс повторяется numTrials раз, и возвращаются индексы последовательностей, имеющих наибольшее расхождение.

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

Рассмотрим, например, данные на рис. 1. Предположим, что индексы-кандидаты — 0, 1, 2. Соответствующие последовательности данных:

[0] Suburban VeryHigh Liberal
[1] Rural    Medium   Conservative
[2] Suburban VeryHigh Conservative

Последовательности [0] и [1] различаются по трем позициям, последовательности [0] и [2] — по одной, а последовательности [1] и [2] — по двум, что дает общую дельту 3 + 1 + 2 = 6. В псевдокоде метод GetGoodIndexes выглядит так:

инициализация массива result
цикл numTrials раз
  генерация numClusters разных случайных
    индексов последовательностей
  вычисление их расхождения
  if текущее расхождение > самого большого расхождения
    самое большое расхождение = текущее расхождение
    сохранение текущих индексов в массиве result
  end if
конец цикла
возврат массива result

Возможно, вы захотите изучить альтернативные подходы. Один из «продвинутых» вариантов — обратить внимание на то, что атрибут Income со значениями Low, Medium, High и VeryHigh по своей природе является числовым. Поэтому вы могли бы модифицировать метод GetGoodIndexes так, чтобы разница между Low и VeryHigh была больше, чем между Low и Medium.

Генерация индексов-кандидатов представляет собой интересную часть проблемы. Процедура осуществляется вспомогательным методом GetRandomIndexes. В псевдокоде этот метод работает примерно так:

инициализация словаря для хранения индексов результатов
инициализация массива result
set count = 0
while count < numClusters
  генерация случайного индекса последовательности
  if индекс не в словаре
    добавить индекс в набор результатов
    добавить индекс в словарь
    увеличить счетчик на 1
  end if
end while
возврат результата

Это довольно похоже на метод решения «в лоб», но на практике он нормально работал.

Заключение

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

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

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

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