Классификация по консенсусу с использованием C#

Хотя есть много стандартных алгоритмов и методологий классификации, в том числе наивный байесовский классификатор (Naive Bayes classification), логистическая регрессия и классификация на основе нейронных сетей, для некоторых задач больше подходит собственный алгоритм классификации. В этой статье представлена такая методология, которую за неимением названия получше я называю классификацией по консенсусу (consensus classification). Лучший способ получить представление о том, что такое классификация по консенсусу, и понять, куда я клоню в этой статье, — взглянуть на демонстрационную программу (рис. 1).

Рис. 1. Классификация по консенсусу в действии

Цель этой демонстрации — создать модель, которая прогнозирует принадлежность к политической партии (democrat или republican) члена Палаты представителей США, основываясь на его голосовании по 16 законопроектам. Исходный набор данных состоит из 100 элементов, каждый из которых соответствует конкретному конгрессмену и имеет 17 полей. Первые 16 полей в каждом элементе — голос за («y») или против («n»). Последнее поле в каждом элементе — реальная политическая принадлежность конгрессмена. Вот как выглядят, например, первые два элемента:

n, y, y, n, y, y, n, n, n, n, n, n, y, y, y, y, democrat
n, y, n, y, y, y, n, n, n, n, n, y, y, y, n, y, republican

Эти демонстрационные данные являются подмножеством общеизвестного эталонного набора Congressional Voting Records Data Set. Полный набор эталонных данных содержит 435 элементов, часть из которых имеют значение vote, равное «?», а это указывает на то, что данный конгрессмен либо воздержался, либо не известно, как он голосовал. Демонстрационное подмножество содержит первые 100 элементов из полного набора, где нет значений «?». Кроме того, в исходном наборе данных принадлежность к политической партии указывается в первом поле; я сделал это поле последним, что гораздо удобнее при программировании.

Хотя не обязательно знать, каким законопроектам соответствуют результаты 16 голосований, тема каждого законопроекта предлагается в виде следующих 16 сокращенных терминов: handicapped-infants (дети-инвалиды), water-project (проект по водопользованию), adopt-budget (принятие бюджета), physician-fees (гонорары врачей), el-salvador (резолюция по Сальвадору), school-religion (религия в школе), anti-satellite (противоспутниковые средства), nicaraguan-contras (никарагуанские контрас), mx-missile (ракета MX), immigration-bill (закон об иммиграции), synfuels-cutback (сокращение синтетического топлива), education-spending (расходы на образование), superfund-sue (иск против закона о воздействии на окружающую среду), crime-bill (обвинительный акт), duty-free (беспошлинная торговля), south-africa (резолюция по Южной Африке).

Демонстрационная программа разделяет 100-элементный набор данных на наборы с 80 элементами (для обучения модели) и 20 элементами (для оценки точности полученной модели). Модель классификации по консенсусу состоит из набора простых правил вроде «если конгрессмен проголосовал за закон 0 и против закона 3 и за закон 15, то он относится к республиканцам». В демонстрации количество булевых условий в каждом простом правиле ограничено значением 5, а общее число правил задано равным 500. Более того, каждое простое правило должно быть минимум на 90% точным на элементах обучающих данных, к которым применимо это правило.

На внутреннем уровне в процессе обучения генерируются 500 простых правил. После создания модели в демонстрации правила модели были применены к обучающим данным, что дало точность 93.75%. Затем модель была применена к тестовому набору из 20 элементов, что дало точность на уровне 84.21%: 16 правильных предсказаний, три — неправильных и один элемент данных не подошел ни под одно из 500 правил модели.

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

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

Общая структура демонстрационной программы с удалением некоторых выражений WriteLine и небольшими правками для экономии места представлена на рис. 2. Чтобы создать эту программу, я запустил Visual Studio, создал новое консольное приложение на C# и назвал его Consensus­Classification. Эта программа не имеет значимых зависимостей от Microsoft .NET Framework, поэтому подойдет любая сравнительно недавняя версия Visual Studio. После загрузки сгенерированного шаблоном кода я переименовал файл Program.cs в окне Solution Explorer в ConsensusProgram.cs, а Visual Studio автоматически переименовал класс Program.

using System;
using System.Collections.Generic;
namespace ConsensusClassification
{
  class ConsensusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin consensus classification demo");
      Console.WriteLine("Goal is predict political party");
      string[][] allData = new string[100][];
      allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
        "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
      allData[1] = new string[] { "n", "y", "n", "y", "y", "y", "n", "n",
        "n", "n", "n", "y", "y", "y", "n", "y", "republican" };
      // И т. д.
      allData[99] = new string[] { "y", "n", "y", "n", "n", "y", "y", "y",
        "y", "y", "y", "n", "n", "n", "y", "y", "democrat" };
      Console.WriteLine("All data: ");
      ShowData(allData, 5, true);
      Console.WriteLine("Creating 80-20 train-test data");
      string[][] trainData;
      string[][] testData;
      MakeTrainTest(allData, 0, out trainData, out testData); // 0 = начальное значение
      Console.WriteLine("Training data: \n");
      ShowData(trainData, 3, true);
      Console.WriteLine("Test data: \n");
      ShowData(testData, 3, true);
      int numConditions = 5; // условий на правило
      int maxNumRules = 500;
      double minAccuracy = 0.90; // мин. точность (%) правила
      Console.WriteLine("Setting number conditions per rule = " +
        numConditions);
      Console.WriteLine("Setting max number simple rules    = " +
        maxNumRules);
      Console.WriteLine("Setting simple rule min accuracy   = " +
        minAccuracy.ToString("F2"));
      ConsensusClassifier cc =
        new ConsensusClassifier(numConditions, maxNumRules);
      Console.WriteLine("Starting training");
      cc.Train(trainData, minAccuracy);
      Console.WriteLine("Done");
      Console.WriteLine("Created " + cc.RuleCount() + " simple rules");
      double trainAcc = cc.Accuracy(trainData);
      Console.WriteLine("Accuracy on train data = " +
        trainAcc.ToString("F4"));
      int numCorrect, numWrong, numUnknown;
      double testAcc = cc.Accuracy(testData, out numCorrect,
        out numWrong, out numUnknown);
      Console.WriteLine("Accuracy on test data  = " +
        testAcc.ToString("F4"));
      Console.WriteLine("Number correct = " + numCorrect);
      Console.WriteLine("Number wrong   = " + numWrong);
      Console.WriteLine("Number unknown = " + numUnknown);
      Console.WriteLine("End consensus classification demo\n");
      Console.ReadLine();
    }
    static void MakeTrainTest(string[][] allData, int seed,
      out string[][] trainData, out string[][] testData) { . . }
    static void ShowData(string[][] rawData, int numRows,
      bool indices) { . . }
  } // Program
  public class ConsensusClassifier { . . }
} // ns

Вся логика программы содержится в методе Main. В демонстрационной программе есть два статических вспомогательных метода: MakeTrainTest и ShowData. Логика классификации размещается в единственном классе ConsensusClassifier, определенном в программе. Классификатор предоставляет шесть открытых методов: один конструктор, RuleCount (реальное количество простых правил в модели), ComputeOutput (для прогнозов после создания модели), Train (для создания модели) и перегруженная версия Accuracy (для вычисления процента правильных прогнозов).

В методе Main демонстрационная программа «зашивает» исходные данные со 100 элементами в строковую матрицу в стиле «массив массивов»:

string[][] allData = new string[100][];
allData[0] = new string[] { "n", "y", "y", "n", "y", "y", "n", "n",
  "n", "n", "n", "n", "y", "y", "y", "y", "democrat" };
...

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

string[][] trainData;
string[][] testData;
MakeTrainTest(allData, 0, out trainData, out testData);

Соотношение 80/20 при разделении «зашито» в код. Аргумент с нулевым значением, передаваемый в метод MakeTrainTest, — это начальное (зародышевое) значение для объекта Math.Random, чтобы разделение на обучающие и проверочные данные проходило случайным образом. Альтернатива — применение такого подхода, чтобы пропорции элементов данных с демократами и республиканцами в обучающей и проверочной матрицах примерно совпадали с их долями в исходных данных.

Демонстрационная программа создает модель с помощью такого кода:

int numConditions = 5;
int maxNumRules = 500;
double minAccuracy = 0.90;
ConsensusClassifier cc =
  new ConsensusClassifier(numConditions, maxNumRules);
cc.Train(trainData, minAccuracy);

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

В завершение демонстрационная программа вычисляет и отображает точность модели:

double trainAcc = cc.Accuracy(trainData);
Console.WriteLine("Accuracy on train data = " + trainAcc.ToString("F4"));
int numCorrect, numWrong, numUnknown;
double testAcc = cc.Accuracy(testData, out numCorrect, out numWrong,
  out numUnknown);
Console.WriteLine("Accuracy on test data  = " + testAcc.ToString("F4"));
Console.WriteLine("Number correct = " + numCorrect);
Console.WriteLine("Number wrong   = " + numWrong);
Console.WriteLine("Number unknown = " + numUnknown);

Первый перегруженный Accuracy возвращает просто процент правильных классификаций. Второй перегруженный Accuracy возвращает дополнительно количество корректных, некорректных и неприменимых элементов данных, где под неприменимыми подразумевается, что ни одно из правил модели не годится для этих элементов данных. Например, параметр количества условий был задан равным 3, а один из элементов данных имеет vote0 = 'y', vote1 = 'y' и vote2 = 'n'. Даже при 500 правилах возможен пропуск такой комбинации голосования. В качестве альтернативы можно разработать метод Accuracy так, чтобы неприменимые элементы данных были бы невозможны. Один из распространенных способов для этого — добавление заключительного правила наподобие «…else Representative is a Democrat», где Democrat — значение по умолчанию, которое обычно является наиболее часто встречающимся значением зависимой переменной.

Предсказание принадлежности конгрессмена к политической партии, который голосовал за законопроекты от [0] до [7] и против законопроектов от [8] до [15], могло бы напоминать нечто вроде:

string[] newData = new string[] { "y", "y", "y", "y", "y", "y", "y", "y",
  "n", "n", "n", "n", "n", "n", "n", "n" };
int party = cc.ComputeOutput(newData);
Console.WriteLine("Predicted party = " + party);

Метод ComputeOutput возвращает целое значение, 0 или 1, где 0 — республиканец, а 1 — демократ.

Алгоритм консенсуса

Сердцевиной классификатора по консенсусу является набор правил. Здесь нужно решить две задачи: как представлять правила и как их генерировать. Демонстрационная программа представляет правило в виде целочисленного массива. Схему лучше всего пояснить на конкретном примере, показанном на рис. 3. Допустим, количество булевых условий в каждом правиле задается равным трем. Тогда одно правило будет представлено массивом с семью ячейками. Если в массиве были значения { 3, 0, 8, 1, 15, 1, 0 }, значит, правило соответствует «если vote [3] равно 0 AND vote [8] равно 1 AND vote [15] равно 1, то party равно 0». Набор правил является обобщенным набором List правил.

Смысл 0 и 1 может варьироваться для каждого столбца/голоса. Демонстрационная программа конструирует массив наборов Dictionary — по одному на каждый столбец/голос. Каждому строковому значению по мере того, как они встречаются в каждом столбце обучающих данных, назначается целочисленный идентификатор с отсчетом от нуля. Например, в столбце [0] для голоса [0] в обучающих данных «n» встречается первым и присваивается равным 0, а «y» — вторым и получает значение 1. Но в столбце [1] «y» встречается первым и присваивается равным 0, а «n» — вторым и получает значение 1.

Аналогично в столбце [16] обучающих данных последний столбец, где хранятся значения «democrat» и «republican» зависимой переменной, «republican» встречается первым и получает значение 0, а «democrat» — 1. Информация о сопоставлении строк с целыми числами хранится в члене класса — массиве stringToInt, как показано на рис. 3. Поэтому выражение stringToInt[1]["y"] возвращает значение индекса с отсчетом от нуля для голосования «за» (yes) в случае голоса [1], что в демонстрационных обучающих данных соответствует 0.

Вот высокоуровневый псевдокод для создания правил, которые определяют модель классификации:

Цикл while numRules < maxRules && trial < maxTrials
  ++trial
  Выбираем произвольную строку обучающих данных
  Выбираем numConditions случайных столбцов из выбранной строки
  Создаем правило-кандидат по выбранным столбцам этой строки
  if правило-кандидат уже в списке правил, продолжаем
  if правило-кандидат не отвечает мин. точности, продолжаем
  Правило-кандидат хорошее, добавляем в список
Конец цикла

Конкретный пример поможет прояснить алгоритм. Допустим, в основном цикле случайно выбрана строка [0] обучающих данных. Затем предположим, что numConditions установлено равным 3 и случайным образом были выбраны столбцы [1], [2] и [15]. В обучающих данных эти столбцы имеют значения «y», «n» и «y», а значение зависимой переменной — «republican». Значения столбцов проверяются в массиве наборов Dictionary, и они равны 0, 0 и 0. Значит, правило-кандидат является целочисленным массивом со значениями { 1, 0, 2, 0, 15, 0, 0 }, что можно интерпретировать как «если столбец 1 равен 0 AND столбец 2 равен 0 AND столбец 15 равен 0, то party равно 0».

Затем 80 элементов в обучающих данных сканируются, чтобы увидеть, отвечает ли правило-кандидат критерию минимальной точности. Заметьте, что правило-кандидат будет точным хотя бы для одного элемента данных — того элемента, который был использован для создания правила. Однако правило-кандидат не обязательно будет применимо ко всем элементам обучающих данных. Например, правило-кандидат { 1, 0, 2, 0, 15, 0, 0 }, сгенерированное по элементу данных [0], неприменимо к элементу данных [1], так как столбец [2] имеет значение 1, а не 0.

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

Несколько комментариев

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

Я заметил, что применение наивного байесовского классификатора вроде бы дало лучшие результаты изо всех попыток. В этом алгоритме предполагается, что каждая переменная-предиктор математически независима. Хотя это предположение часто оказывается неверным, данный алгоритм иногда работает очень хорошо. В моей задаче переменные-предикторы почти наверняка так или иначе были связаны, но я не был уверен, какие именно из них связаны. Поэтому я решил задействовать части нескольких ML-методологий для создания подхода, описанного в этой статье. В конечном счете я сумел создать модель прогнозирования, которая оказалась значительно точнее, чем любая модель из стандартных методологий.

В этой демонстрации решается задача бинарной классификации, поскольку зависимая переменная может принимать одно из двух значений: «democrat» или «republican». Более того, все предикторы являются бинарными категориальными переменными, так как они могут иметь значение либо «yes», либо «no». Классификация по консенсусу может справляться с задачами полиномиальной классификации (например, демократ, республиканец, независимый) и обрабатывать категориальные предикторы, имеющие более двух значений (скажем, yes, no, absent [отсутствует], abstained [воздержался]). В моих экспериментах было не ясно, насколько эффективна классификация по консенсусу для задач, где переменные-предикторы являются числовыми, как в случае возраста, и распределяются по категориям (например, молодой, среднего возраста и пожилой).

Комбинирование нескольких правил или моделей для генерации результата классификации в лексиконе ML часто называют множественным обучением (ensemble learning). Идея генерации множества отдельных правил используется в ML-методологиях, и их иногда называют методами бустинга. Позвольте заметить, что в своей рубрике «Тесты» я почти всегда представляю ML-методологии, имеющие твердую исследовательскую базу. Эта статья является исключением. Представленная здесь методология официально не изучалась и никогда не рассматривалась в серьезных исследованиях. Несколько моих коллег из академической науки сделали мне выговор за вопиющее нахальство использовать собственную, нетрадиционную ML-методологию, но на это я обычно слегка язвительно отвечаю, что меня больше интересует получение результатов, чем выведение изящной математической теории. По моему мнению, применение стандартных ML-методологий — лучший способ начального подхода к задаче ML, но, когда традиционные методы не работают, создание собственного решения иногда бывает на удивление эффективным.