Классификация отсеиванием с помощью C#

Очень простая и интересная методика классификации — алгоритм отсеивания (Winnow algorithm). (Английское слово «winnow» означает удаление нежелательных элементов.) Лучший способ прочувствовать, что такое классификация отсеиванием, и понять, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1.

Рис. 1. Демонстрация классификации по алгоритму отсеивания

Цель демонстрационной программы — предсказать принадлежность к политической партии (демократической или республиканской) члена Палаты представителей США на основе его голосований по 16 законопроектам. В Палате представителей 435 членов. Общеизвестный эталонный набор данных содержит 435 элементов, хранящихся в простом текстовом файле. Первые три элемента данных таковы:

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

Первый столбец содержит либо «democrat», либо «republican». Следующие 16 столбцов содержат n (голос против), y (голос за) или ? (missing, т. е. нет данных, неизвестен или отсутствовал на момент голосования). Первый из этих столбцов отражает голосование члена Палаты представителей по законопроекту, относящемуся к детям с ограниченными возможностями, второй — по законопроекту о водопользовании и т. д. Вам незачем знать, какой законопроект сопоставлен с каждым столбцом, но, если вас это интересует, вы можете найти этот набор данных (с описанием) во многих местах в Интернете поиском по «UCI voting data».

Классификация отсеиванием предназначена для решения очень специфического типа задач классификации: той, где предсказываемый класс может принимать одно из двух возможных значений (такие задачи классификации называют бинарными), а предикторные переменные (predictor variables) (часто называемые характеристиками [features] в терминологии ML) тоже могут принимать одно из двух возможных значений. Исходный набор электоральных данных отвечает этим требованиям, если вы обрабатываете значения «missing». Самый распространенный подход к обработке таких значений — простое удаление любого элемента данных, где есть одно или более значений «missing». Однако в случае электоральных данных это значение часто подразумевает голос против («no»), поэтому демонстрационная программа заменяет все значения «missing» на значения «no».

Демонстрационная программа использует первые 100 элементов в наборе электоральных данных, а не все 435. Она кодирует независимую переменную для голосов против как 0, а для голосов за — как 1. Аналогично кодируются значения независимой переменной X для принадлежности к политической партии: «democrat» — 0 и «republican» — 1. Демонстрационная программа перемещает зависимую переменную Y из первого столбца в последний, потому что использовать последний столбец для Y удобнее при кодировании.

Демонстрационная программа случайным образом делит 100-элементный набор кодированных данных на 80-элементный обучающий набор для генерации модели и на 20-элементный проверочный набор для оценки точности модели. В демонстрации применяется алгоритм отсеивания (Winnow algorithm) для поиска 16 весовых значений (по одному для каждого входа): 0.2500, 0.500, …, 0.0625. Используя эти весовые значения, модель в демонстрации правильно прогнозирует принадлежность к политической партии на уровне 97.50% обучающих элементов (78 из 80) и 95.00% проверочных (19 из 20).

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

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

Вникаем в алгоритм отсеивания

Для простоты предположим, что обучающие данные основаны всего на пяти голосах, а не на 16. Например:

1, 0, 1, 1, 0 -> 0
1, 1, 1, 0, 1 -> 1
0, 0, 0, 1, 0 -> 1

Поэтому первая строка означает «yes-vote», «no-vote», «yes-vote», «yes-vote», «no-vote», «democrat». Теперь допустим, что модель обучена и дает весовые значения {0.75, 3.00, 1.00, 0.50, 0.40}. Чтобы вычислить прогнозируемый результат, алгоритм просто умножает каждое входное значение на соответствующее весовое, суммирует значения и сравнивает накопленную сумму с пороговым значением. Например, для первого элемента накопленная сумма составит:

(1 * 0.75) + (0 * 3.00) + (1 * 1.00) + (1 * 0.50) + (0 * 0.40) = 2.25

Если пороговое значение равно 5.0, то, поскольку накопленная сумма (2.25) меньше, прогнозируемая Y равна 0, что в данном случае правильный прогноз.

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

Инициализация весовых значений
Цикл до завершения
  for each обучающий элемент
    вычисляем Y
    if правильно, ничего не делаем
    else if неправильно
      if вычисленное значение Y слишком велико
        делим все релевантные веса на 2.0
      else if вычисленное значение Y слишком мало
        умножаем все релевантные веса на 2.0
  end for
Конец цикла

Допустим, что для трех элементов данных, упомянутых ранее, весовые значения инициализируются как:

{ 2.50, 2.50, 2.50, 2.50, 2.50 }

Вычисленное значение Y для первого обучающего элемента (1, 0, 1, 1, 0 -> 0) равно:

Y = (1 * 2.50) + (0 * 2.50) + (1 * 2.50) + (1 * 2.50) + (0 * 2.50) = 7.50 -> 1

Это неправильный прогноз, где вычисленное значение Y, равное 1, слишком велико по сравнению с нужным значением Y (0), поэтому релевантное весовое значение делится на 2.0. Релевантные весовые значения — это те, которые сопоставлены с входными значениями 1. Новые весовые значения:

{ 2.50 / 2, (no change), 2.50 / 2, 2.50 / 2, (no change) }
= { 1.25, 2.50, 1.25, 1.25, 2.50 }

Теперь второй обучающий элемент (1, 1, 1, 0, 1 -> 1) обрабатывается новыми весовыми значениями:

Y = (1 * 1.25) + (1 * 2.50) + (1 * 1.25) + (0 * 1.25) + (1 * 2.50) = 7.50 -> 1

Это правильный прогноз, поэтому все весовые значения принимаются. Третий обучающий элемент (0, 0, 0, 1, 0 -> 1) обрабатывается текущими весовыми значениями:

Y = (0 * 1.25) + (0 * 2.50) + (0 * 1.25) + (1 * 1.25) + (0 * 2.50) = 1.25 -> 0

Это неправильный прогноз, где вычисленное значение Y, равное 0, слишком мало в сравнении с нужным (1), поэтому релевантные весовые значения умножаются на 2.0:

{ (no change), (no change), (no change), 1.25 * 2.0, (no change) }
= { 1.25, 2.50, 1.25, 2.50, 2.50 }

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

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

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

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
      // И т. д.
      // Создаем, обучаем и проверяем матрицы из данных.
      // Создаем экземпляр классификатора отсеиванием.
      // Обучаем, используя обучающие данные.
      // Вычисляем точность модели.
      // Прогнозируем партийность гипотетической персоны.
      Console.WriteLine("End Winnow demo");
      Console.ReadLine();
    } // Main
    static void MakeTrainTest(int[][] data, int seed,
      out int[][] trainData, out int[][] testData) { . . }
    static void ShowVector(double[] vector, int decimals,
      int valsPerRow, bool newLine) { . . }
    static void ShowMatrix(int[][] matrix, int numRows,
      bool indices) { . . }
  }
  public class Winnow
  {
    private int numInput;
    private double[] weights;
    private double threshold;
    private double alpha;
    private static Random rnd;
    public Winnow(int numInput, int rndSeed) { . . }
    public int ComputeOutput(int[] xValues) { . . }
    public double[] Train(int[][] trainData) { . . }
    public double Accuarcy(int[][] trainData) { . . }
    private static void Shuffle(int[][] trainData) { . . }
  }
}

Демонстрационная программа довольно длинна, чтобы ее можно было представить в статье во всей ее полноте, но вы можете найти полный исходный код (WinnowProgram.cs) в сопутствующем этой статье пакете кода. Вся логика классификации отсеиванием содержится в программно определенном классе Winnow.

Метод Main начинает с подготовки 100-элементного набора данных, как показано на рис. 3.

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm prediction demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
...

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

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

Console.WriteLine("\nFirst few lines of all data are: \n");
ShowMatrix(data, 4, true);
Console.WriteLine("\nSplitting data into 80% train" +
  " and 20% test matrices");
int[][] trainData = null;
int[][] testData = null;
MakeTrainTest(data, 0, out trainData, out testData);

Такие разделение на 80 и 20 «зашито» в код метода MakeTrainTest (вероятно, вы предпочтете передавать процент обучающих данных как параметр). После отображения части обучающих данных, чтобы убедиться в том, что ничего не пошло наперекосяк, демонстрационная программа создает экземпляр объекта классификатора Winnow и с помощью метода Train создает модель, т. е. находит набор правильных весовых значений:

Console.WriteLine("First few rows of training data are:");
ShowMatrix(trainData, 3, true);
Console.WriteLine("Begin training using Winnow algorithm");
int numInput = 16;
Winnow w = new Winnow(numInput, 0);
weights = w.Train(trainData);
Console.WriteLine("Training complete");

Конструктор Winnow требует передачи ряда x-переменных и начального значения для генерации случайных чисел, что используется для обработки обучающих элементов в случайном порядке. Затем демонстрационная программа показывает конечные весовые значения, найденные методом Train, и вычисляет точность модели применительно к обучающему и проверочному наборам:

Console.WriteLine("Final model weights are:");
ShowVector(weights, 4, 8, true);
double trainAcc = w.Accuarcy(trainData);
double testAcc = w.Accuarcy(testData);
Console.WriteLine("Prediction accuracy on training data = " +
  trainAcc.ToString("F4"));
Console.WriteLine("Prediction accuracy on test data = " +
  testAcc.ToString("F4"));

Программа завершает работу прогнозом о принадлежности к политической партии гипотетического члена Палаты представителей США, который голосовал за все 16 законопроектов (рис. 4).

...
  Console.WriteLine("Predicting party of Representative" + "
    with all 'yes' votes");
  int[] unknown = new int[] { 1, 1, 1, 1, 1, 1, 1, 1,
  1 , 1, 1, 1, 1, 1, 1, 1 };
  int predicted = w.ComputeOutput(unknown);
  if (predicted == 0)
    Console.WriteLine("Prediction is 'democrat'");
  else
    Console.WriteLine("Prediction is 'republican'");
  Console.WriteLine("End Winnow demo");
  Console.ReadLine();
} // Main

Класс Winnow

В классе Winnow пять полей (элементов данных):

private int numInput;
private double[] weights;
private double threshold;
private double alpha;
private static Random rnd;

Поле threshold хранит значение, используемое, чтобы определить, каково вычисленное значение Y — 0 (ниже порога) или 1 (выше порога). Поле alpha — это множитель для уменьшения (в научной литературе называемый понижением в ранге [demotion]) или для увеличения (называемый повышением в ранге [promotion]) весовых значений, когда вычисляется неправильный Y. Стандартное значение для alpha — 2.0, как было показано ранее в этой статье. Возможно, вы захотите поэкспериментировать, используя разные значения для повышения и понижения в ранге вместо единого значения alpha для обоих случаев.

Конструктор Winnow определен так:

public Winnow(int numInput, int rndSeed)
{
  this.numInput = numInput;
  this.weights = new double[numInput];
  for (int i = 0; i < weights.Length; ++i)
    weights[i] = numInput / 2.0;
  this.threshold = 1.0 * numInput;
  this.alpha = 2.0;
  rnd = new Random(rndSeed);
}

Значение threshold инициализируется числом входных переменных (numInput), например 16.0 в этой демонстрации. Это значение является стандартным для алгоритма отсеивания, но при желании можно поэкспериментировать с альтернативными значениями. Здесь происходит умножение без эффекта (no-effect multiplication) на 1.0, предполагая, что могут использоваться разные значения, но они должны быть связаны с количеством входных переменных.

Массив weights создается по числу входных переменных, здесь — 16. Каждое из весовых значений инициализируется количеством входных переменных, деленным на 2, т. е. в этой демонстрации 8.0. Это значение произвольное и вы опять же можете поэкспериментировать. Алгоритм отсеивания пока исследован не слишком глубоко по сравнению со многими другими, чаще применяемыми алгоритмами классификации.

Метод ComputeOutput достаточно прост:

public int ComputeOutput(int[] xValues)
{
  double sum = 0.0;
  for (int i = 0; i < numInput; ++i)
    sum += weights[i] * xValues[i];
  if (sum > this.threshold)
    return 1;
  else
    return 0;
}

Заметьте, что значение 1 возвращается, если накопленная сумма строго больше, чем пороговое значение, в противоположность случаю, когда она больше или равна threshold. Это произвольно и использование «>=» вместо «>» не окажет заметного влияния на алгоритм.

Метод обучения

Процедура обучения алгоритма отсеивания — одна из самых коротких и простых среди всех алгоритмов классификации в ML. Определение метода начинается с:

public double[] Train(int[][] trainData)
{
  int[] xValues = new int[numInput];
  int target;
  int computed;
  Shuffle(trainData);
...

Локальный массив xValues хранит входные значения из обучающего элемента, но не целевое выходное значение. Локальная переменная target содержит нужно значение Y из элемента обучающих данных, локальная переменная computed — вычисленное значение Y для данного набора входных x-значений и текущего набора весовых значений. Метод Shuffle вносит элемент случайности в порядок обучающих данных, используя мини-алгоритм Фишера-Йетса.

Затем начинается основной цикл обучения:

for (int i = 0; i < trainData.Length; ++i)
{
  Array.Copy(trainData[i], xValues, numInput); // входные
  target = trainData[i][numInput]; // последнее - целевое
  computed = ComputeOutput(xValues);
  // Здесь обновляем весовые значения
}

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

В основном цикле обучения весовые значения обновляются, используя код с рис. 5.

if (computed == 1 && target == 0) // уменьшение
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // не релевантные
    weights[j] = weights[j] / alpha; // понижение в ранге
  }
}
else if (computed == 0 && target == 1) // увеличение
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // не релевантные
    weights[j] = weights[j] * alpha; // повышение в ранге
  }
}

Метод Train завершается копированием найденных лучших весовых значений в локальный массив, возвращаемый основной программе:

...
  } // end for
  double[] result = new double[numInput]; // Число весовых значений
  Array.Copy(this.weights, result, numInput);
  return result;
} // Train

Заключение

Эта статья основана на исследовательском документе, в котором изначально был представлен алгоритм отсеивания: N. Littlestone «Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm» (1998). Вы найдете этот документ в PDF-формате в Интернете в нескольких местах.

Занимаясь подготовкой к написанию этой статьи, я наткнулся на интересную реализацию алгоритма отсеивания, написанную с использованием языка F#. Реализация представлена в блоге Матиаса Брандевиндера (Mathias Brandewinder) (bit.ly/1z8hfj6).

Хотя классификация отсеиванием рассчитана специально на задачи бинарной классификации, где все независимые x-переменные являются бинарными, вы можете поэкспериментировать с задачами, где одна или более x-переменных являются категориальными. Допустим, к примеру, что одна предикторная переменная — это «color» и что она может принимать одно из трех возможных значений: «red», «green» или «blue». Если вы используете кодирование 1-из-N, то «red» станет (1, 0, 0), «green» — (0, 1, 0), «blue» — (0, 0, 1), и вы сможете применить алгоритм отсеивания.