Тесты

Обучение ассоциативным правилам

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

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

Обучение ассоциативным правилам (association rule learning) — методика из области машинного обучения, которая обеспечивает извлечение правил «if-then» из набора данных. Например, если исследуемыми данными является набор транзакций в супермаркете, одно из ассоциативных правил может быть таким: «IF клиент покупает яблоки и кофе THEN есть высокая вероятность того, что он также купит масло и пончики».

Есть несколько типов ассоциативных правил. В этой статье объясняется, как извлекать правила с высокой степень достоверности (high-confidence rules), которые характеризуются как истинные в указанной минимальной процентной доле анализируемых транзакций. Обучение ассоциативным правилам можно применить ко многим видам данных, помимо транзакций покупок товаров, в том числе к файлам системных журналов, поисковым запросам пользователей и командам естественного пользовательского интерфейса (NUI). В этой статье также рассказывается, как работает обучение ассоциативным правилам с высокой степенью достоверности (high-confidence association rule learning), и представлена полная демонстрационная программа.

Лучший способ понять цель этой статьи — взглянуть на демонстрационную программу на рис. 1. В ней устанавливаются 10 выдуманных транзакций, кодируемых так, чтобы значение каждого элемента начиналось от 0. Например, первая транзакция — (0 3 4 11), т. е. элементы 0, 3, 4 и 11 встречаются вместе. В большинстве случаев допускаются дублирующие транзакции, такие как транзакции 2 и 3.

Рис. 1. Поиск ассоциативных правил с высокой степенью достоверности

Хотя вы можете выполнять поиск ассоциативных правил с высокой степенью достоверности непосредственно в данных кодированных транзакций, в большинстве ситуаций из транзакций сначала извлекаются наборы часто встречающихся элементов (frequent item-sets). Набор элементов — это подмножество всех возможных транзакций, и наборы часто встречающихся элементов являются теми, которые отвечают некоему заданному минимальному числу вхождений (называемому уровнем поддержки) в наборе транзакций. В демонстрационной программе, использующей значение поддержки 0.30 (т. е. набор элементов должен встречаться минимум в 0.30 * 10 = 3 транзакциях), имеются восемь наборов часто встречающихся элементов. Первый набор — (2 5). Элементы 2 и 5 встречаются вместе в трех транзакциях: 7, 8 и 9. Наборы часто встречающихся элементов исключают обособленные транзакции, которые могли бы сгенерировать правило с очень высокой степенью достоверности, но настолько редки, что это правило оказывается нерелевантным. В большинстве случаев наборы часто встречающихся элементов различны, дубликаты в них недопустимы. Извлечение наборов часто встречающихся элементов из транзакций — на удивление трудная задача. По этой тематике см. мою статью «Frequent Item-Sets for Association Rule Learning» в номере «MSDN Magazine» за январь 2013 г. по ссылке msdn.microsoft.com/magazine/dn519928.

«За кулисами» демонстрационная программа использует список наборов часто встречающихся элементов для генерации правил-кандидатов. Каждое правило-кандидат оценивается, чтобы определить, отвечает ли оно указанному минимальному пороговому значению правдоподобия, называемому уровнем достоверности (confidence value). Правила-кандидаты, отвечающие или превышающие уровень достоверности, идентифицируются как правила с высокой степенью достоверности. В демонстрационной программе этот уровень задан равным 0.700, т. е. правило-кандидат должно быть истинным минимум для 70% транзакций, к которым применимо это правило.

В демонстрационной программе найдено 16 правил с высокой степенью достоверности. Первым перечислено правило IF (2) THEN (5) с вычисленным уровнем достоверности 0.75. Вы можете интерпретировать это как «Если в транзакции есть элемент 2, то транзакция вероятно содержит и элемент 5». IF-часть правила, которая называется первым членом (antecedent), применима к четырем транзакциям: 6, 7, 8 и 9. Правило истинно для трех из этих четырех транзакций: 7, 8 и 9; поэтому вычисленный уровень достоверности равен 3/4 = 0.75.

Заметьте, что правила с высокой степенью достоверности не обязательно являются симметричными. Правила IF (5) THEN (2) нет, потому что это правило применимо к транзакциям 1, 4, 5, 7, 8 и 9, но истинно только для транзакций 7, 8 и 9, поэтому уровень достоверности, равный 3/6 = 0.50, не отвечает минимальному значению 0.700.

В этой статье предполагается, что вы по крайней мере на среднем уровне владеете навыками программирования, но ничего не знаете об обучении ассоциативным правилам. Демонстрационная программа написана на C#, но у вас не возникнет особых трудностей в рефакторинге этой программы под другой .NET-язык вроде Visual Basic или IronPython. Большая часть обычной обработки ошибок убрана для большей ясности основных идей. Весь исходный код демонстрационной программы представлен в этой статье; кроме того, его можно скачать по ссылке msdn.microsoft.com/magazine/msdnmag0514.

Алгоритм поиска правил

Алгоритм, используемый демонстрационной программой для поиска правил с высокой степенью достоверности, показан на рис. 2. Эта схема иллюстрирует, как набор часто встречающихся элементов (3 4 7) генерирует два правила с невысокой степенью достоверности и четыре правила с высокой степенью достоверности. Алгоритм начинает с генерации всех математических комбинаций при размере (size) от k = 1 до длины набора элементов минус 1. Математические комбинации являются ключом к алгоритму обучения ассоциативным правилам, представленным в этой статье. Математическая комбинация — это набор чисел, который представляет некое подмножество. Например, если у вас есть пять элементов — (0, 1, 2, 3, 4) и размер k подмножества равен 3, то возможны 10 комбинаций элементов:

(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 2, 3)
(0, 2, 4)
(0, 3, 4)
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)

Рис. 2. Алгоритм поиска правил с высокой степенью достоверности

Элементы математической комбинации не являются элементами транзакции — это просто числа. На рис. 2 каждая комбинация применяется к набору часто встречающихся элементов, чтобы сгенерировать подмножество набора элементов, которое интерпретируется как первый член (antecedent) (IF-часть) правила-кандидата. Например, последняя комбинация для k = 2 — (1, 2), поэтому элементы в наборе часто встречающихся элементов (3 4 7) с индексами 1 и 2 используются как первый член правила-кандидата: «IF (4 7)». THEN-часть правила-кандидата состоит из тех элементов в анализируемом наборе элементов, которые не используются в IF-части. Таким образом, для набора элементов (3 4 7), если первый член равен (4 7), то THEN-часть (называемая вторым членом [consequent]) равна (3), и полное правило-кандидат выглядит как «IF (4 7) THEN (3)».

Несколько удивительно, что THEN-часть правила-кандидата не требует вычисления уровня достоверности правила. Возьмем правило-кандидат IF (4 7) THEN (3). Чтобы вычислить достоверность, нужно знать количество транзакций, к которым применимо это правило. К этим транзакциям относятся те, что содержат элементы 4 и 7, которые в случае данной демонстрации равны 3 (транзакции 2, 3 и 6). Для второй части вычислений необходимо знать количество применимых транзакций, для которых истинно правило-кандидат; иначе говоря, транзакции, содержащие элементы 4, 7, а также элемент 3. Но это просто число транзакций, которые содержат исходный набор часто встречающихся элементов (3 4 7).

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

Подведем итог. Алгоритм начинает с набора наборов часто встречающихся элементов, которые удовлетворяют минимальному уровню поддержки (частоте вхождений), и для каждого часто встречающегося элемента генерируются все математические комбинации от size=1 до количества элементов в наборе за вычетом единицы. Каждая комбинация определяет IF- и THEN-части правила-кандидата. Правила-кандидаты, удовлетворяющие минимальному уровню достоверности, помечаются как хорошие (с высокой степенью достоверности) и сохраняются.

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

Чтобы создать демонстрационную программу, я запустил Visual Studio. Демонстрационная программа не имеет значимых зависимостей от .NET, поэтому подойдет любая из версий Visual Studio, которая поддерживает Microsoft .NET Framework 2.0 или выше. Я создал консольное приложение на C# и назвал его AssocRuleLearn. После загрузки сгенерированного шаблоном кода в редактор я переименовал файл Program.cs в окне Solution Explorer в более описательный AssocRuleProgram.cs, и Visual Studio автоматически переименовал класс Program за меня. В начале исходного кода я удалил все ссылки на ненужные пространства имен, оставив лишь те, которые ссылаются на System и Collections.Generic.

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

Рис. 3. Структура демонстрационной программы обучения ассоциативным правилам

using System;
using System.Collections.Generic;
namespace AssocRuleLearn
{
  class AssocRuleProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin demo\n");
        List<int[]> transactions = new List<int[]>();
        transactions.Add(new int[] { 0, 3, 4, 11 });
        transactions.Add(new int[] { 1, 4, 5 });
        transactions.Add(new int[] { 3, 4, 6, 7 });
        transactions.Add(new int[] { 3, 4, 6, 7 });
        transactions.Add(new int[] { 0, 5 });
        transactions.Add(new int[] { 3, 5, 9 });
        transactions.Add(new int[] { 2, 3, 4, 7 });
        transactions.Add(new int[] { 2, 5, 8 });
        transactions.Add(new int[] { 0, 1, 2, 5, 10 });
        transactions.Add(new int[] { 2, 3, 5, 6, 7, 9 });
        ShowList(transactions);
        List<int[]> freqItemSets = new List<int[]>();
        freqItemSets.Add(new int[] { 2, 5 });
        freqItemSets.Add(new int[] { 3, 4 });
        freqItemSets.Add(new int[] { 3, 6 });
        freqItemSets.Add(new int[] { 3, 7 });
        freqItemSets.Add(new int[] { 4, 7 });
        freqItemSets.Add(new int[] { 6, 7 });
        freqItemSets.Add(new int[] { 3, 4, 7 });
        freqItemSets.Add(new int[] { 3, 6, 7 });
        ShowList(freqItemSets);
        double minConPct = 0.70;
        List<Rule> goodRules =
          GetHighConfRules(freqItemSets, transactions, minConPct);
        Console.WriteLine("\nDone. Rules are:\n");
        for (int i = 0; i < goodRules.Count; ++i)
          Console.WriteLine(goodRules[i].ToString());
        Console.WriteLine("\nEnd demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    static void ShowList(List<int[]> trans)
    {
      for (int i = 0; i < trans.Count; ++i)
      {
        Console.Write(i.ToString().PadLeft(2) + ": ( ");
        for (int j = 0; j < trans[i].Length; ++j)
          Console.Write(trans[i][j] + " ");
        Console.WriteLine(")");
      }
    }
    static List<Rule> GetHighConfRules(List<int[]> freqItemSets,
      List<int[]> transactions, double minConfidencePct) { . . }
    static int[] NewCombination(int k) { . . }
    static int[] NextCombination(int[] comb, int n) { . . }
    static int[] MakeAntecedent(int[] itemSet, int[]comb) { . . }
    static int[] MakeConsequent(int[] itemSet, int[]comb) { . . }
    static int CountInTrans(int[] itemSet,
      List<int[]> trans, Dictionary<int[], int> countDict) { . . }
    static bool IsSubsetOf(int[] itemSet, int[] trans) { . . }
    static int IndexOf(int[] array, int item, int startIdx) { . . }
  }
  public class Rule
  {
    public int[] antecedent; // IF-часть
    public int[] consequent; // THEN-часть
    public double confidence;
    public Rule(int[] antecedent, int[] consequent, double confidence)
    {
      this.antecedent = new int[antecedent.Length];
      Array.Copy(antecedent, this.antecedent, antecedent.Length);
      this.consequent = new int[consequent.Length];
      Array.Copy(consequent, this.consequent, consequent.Length);
      this.confidence = confidence;
    }
    public override string ToString()
    {
      string s = "IF ( ";
      for (int i = 0; i < antecedent.Length; ++i)
        s += antecedent[i] + " ";
      s += ")";
      s = s.PadRight(13);
      string t = " THEN ( ";
      for (int i = 0; i < consequent.Length; ++i)
        t += consequent[i] + " ";
      t += ") ";
      t = t.PadRight(17);
      return s + t + "conf = " + confidence.ToString("F2");
    }
  }
}

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

Вся работа по поиску правил с высокой степенью достоверности выполняется методом GetHighConfRules. Этот параметр требует передачи заданного пользователем минимального порогового значения уровня достоверности. Эти значения варьируются в зависимости от конкретных задач.

В демонстрационной программе используется класс Rule, определенный в программе. Членами этого класса являются первый член правила (IF-часть), второй (THEN-часть) и вычисленное значение уровня достоверности. В этом классе есть только конструктор и метод ToString, который корректно форматирует демонстрационные данные.

Метод GetHighConfRules вызывает несколько вспомогательных методов. Метод CountInTrans подсчитывает, сколько раз набор элементов, первый или второй член правила встречаются в списке транзакций. Этот вспомогательный метод в свою очередь вызывает другой вспомогательный метод IsSubsetOf, а тот — IndexOf. Метод NewCombination создает математическую комбинацию. Метод NextCombination возвращает следующий элемент для данной комбинации. Методы MakeAntecedent и MakeConsequent возвращают IF- и THEN-части правила-кандидата, принимая набор часто встречающихся элементов и математическую комбинацию.

Математические комбинации

Если вы вернетесь к схеме на рис. 2, то увидите, что алгоритм, используемый демонстрационной программой, требует создания математических комбинаций и возможность генерировать последующий элемент для данной комбинации. Метод NewCombination определен как:

static int[] NewCombination(int k)
{
  int[] result = new int[k];
  for (int i = 0; i < result.Length; ++i)
    result[i] = i;
  return result;
}

Здесь комбинация является массивом значений типа int. Входной параметр k определяет размер комбинации. Новая комбинация представляет собой значения от 0 до k–1 по порядку. Метод NextCombination определен так:

static int[] NextCombination(int[] comb, int n)
{
  int[] result = new int[comb.Length];
  int k = comb.Length;
  if (comb[0] == n - k) return null;
  Array.Copy(comb, result, comb.Length);
  int i = k - 1;
  while (i > 0 && result[i] == n - k + i) --i;
  ++result[i];
  for (int j = i; j < k - 1; ++j)
    result[j + 1] = result[j] + 1;
  return result;
}

Математические комбинации сами по себе являются интереснейшей темой, причем довольно сложной. Метод NextCombination короткий, но не тривиальный. Он принимает комбинацию и количество возможных элементов в комбинации. Метод возвращает лексикографический последующий элемент (lexicographical successor) для входной комбинации или null, если входная комбинация — последняя в лексикографическом порядке. Например, если комбинация с n = 6 и k = 3 равна (1, 4, 5), то следующей комбинацией будет (2, 3, 4).

Генерация первых и вторых членов правил

Вспомогательный метод MakeAntecedent принимает набор часто встречающихся элементов и математическую комбинацию, а возвращает IF-часть правила-кандидата. Например, если набор часто встречающихся элементов — (1 3 4 6 8) и комбинация — (0, 2), то извлекаются значения элементов с индексами 0 и 2, что дает первый член правила (1 4):

static int[] MakeAntecedent(int[] itemSet, int[] comb)
{
  int[] result = new int[comb.Length];
  for (int i = 0; i < comb.Length; ++i) {
    int idx = comb[i];
    result[i] = itemSet[idx];
  }
  return result;
}

Хоть и короткий, этот код может оказаться не столь простым в понимании, потому что целые числа представляют значения элементов комбинации, значения элементов набора и значения индексов в наборе элементов. Если вы внимательно проследите один-два примера, то обязательно поймете, как работает этот метод.

Метод MakeConsequent генерирует THEN-часть правила-кандидата. Скажем, если набор часто встречающихся элементов — (1 3 4 6 8), а комбинация — (0, 2), то извлекаются значения элементов под этими индексами, не равные 0 и 2, давая последовательность (3 6 8):

static int[] MakeConsequent(int[] itemSet, int[] comb)
{
  int[] result = new int[itemSet.Length - comb.Length];
  int j = 0; // указатель на комбинацию
  int p = 0; // указатель на результат
  for (int i = 0; i < itemSet.Length; ++i) {
    if (j < comb.Length && i == comb[j])
      ++j;
    else
      result[p++] = itemSet[i];
  }
  return result;
}

Я спроектировал MakeConsequent так, чтобы он принимал те же параметры, что и метод MakeAntecedent. Немного более простая, но асимметричная альтернатива — определить MakeConsequent так, чтобы он принимал набор элементов и первый член правила-кандидата.

Подсчет вхождений в транзакциях

Ключевой вспомогательный метод CountInTrans принимает массив int, который может представлять набор часто встречающихся элементов или первый член правила-кандидата, список транзакций и набор Dictionary, а возвращает число вхождений набора элементов или первого члена правила. Объект Dictionary хранит счетчики набора элементов и первого члена и используется для проверки того, что, если эти наборы элементов или первых членов уже обрабатывались, то их не требуется засчитывать заново:

static int CountInTrans(int[] itemSet, List<int[]> trans,
  Dictionary<int[], int> countDict)
{
  if (countDict.ContainsKey(itemSet) == true)
    return countDict[itemSet];
  int ct = 0;
  for (int i = 0; i < trans.Count; ++i)
    if (IsSubsetOf(itemSet, trans[i]) == true)
      ++ct;
  countDict.Add(itemSet, ct);
  return ct;
}

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

static bool IsSubsetOf(int[] itemSet, int[] trans)
{
  int foundIdx = -1;
  for (int j = 0; j < itemSet.Length; ++j) {
    foundIdx = IndexOf(trans, itemSet[j], foundIdx + 1);
    if (foundIdx == -1) return false;
  }
  return true;
}

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

static int IndexOf(int[] array, int item, int startIdx)
{
  for (int i = startIdx; i < array.Length; ++i) {
    if (i > item) return -1;
    if (array[i] == item) return i;
  }
  return -1;
}

Генерация правил с высокой степенью достоверности

Располагая всеми этими вспомогательными методами, метод GetHighConfRules можно определить без особого труда. На рис. 4 этот метод показан в виде высокоуровневого псевдокода.

Рис. 4. Псевдокод для метода GetHighConfRules

for each набора часто встречающихся элементов
  ctItemSet = сколько раз набор элементов найден в транзакциях
  for длины подмножества от 1 до длины набора элементов - 1
    создаем новую математическую комбинацию
    перебираем в цикле каждую возможную комбинацию
      создаем IF-часть правила-кандидата
      создаем THEN-часть правила-кандидата
      вычисляем достоверность правила-кандидата
      if правило-кандидат удовлетворяет
        минимальной достоверности, сохраняем
    конец цикла перебора
  end for
end for
return сохраненные правила

Реализация метода GetHighConfRules приведена на рис. 5. Хотя вы можете использовать метод GetHighConfRules в том виде, в каком он показан на рис. 5, есть масса возможностей улучшить производительность — обычно за счет занимаемой памяти или ясности кода. Например, если вы вернетесь к рис. 2, то заметите, что каждая пара из первого и второго членов правила-кандидата имеет зеркальное правило-кандидат, где первый и второй члены меняются местами. Так, если набор элементов — (2 5 7 9), тогда одно правило-кандидат с размером подмножества k = 2 — IF (2 7) THEN (5 9), а другое — IF (5 9) THEN (2 7). Поэтому вместо вычисления первых членов для всех возможных значений размера подмножества набора часто встречающихся элементов можно вычислять только первые и вторые члены для половины возможных размеров подмножества.

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

static List<Rule> GetHighConfRules(List<int[]> freqItemSets,
  List<int[]> trans, double minConfidencePct)
{
  List<Rule> result = new List<Rule>();
  Dictionary<int[], int> itemSetCountDict = 
    new Dictionary<int[], int>();
  for (int i = 0; i < freqItemSets.Count; ++i)
  {
    int[] currItemSet = freqItemSets[i]; // для ясности
    int ctItemSet = CountInTrans(currItemSet, trans, itemSetCountDict);
    for (int len = 1; len <= currItemSet.Length - 1; ++len)
    {
      int[] c = NewCombination(len);
      while (c != null) // Каждая комбинация дает правило-кандидат
      {
        int[] ante = MakeAntecedent(currItemSet, c);
        int[] cons = MakeConsequent(currItemSet, c);
        int ctAntecendent = CountInTrans(ante, transactions,
          itemSetCountDict);
        double confidence = (ctItemSet * 1.0) / ctAntecendent;
        if (confidence >= minConfidencePct) {
          Rule r = new Rule(ante, cons, confidence);
          result.Add(r);
        }
        c = NextCombination(c, currItemSet.Length);
      } // конец while для каждой комбинации
    } // len каждого возможного первого члена
      // для текущего набора элементов
  } // i для каждого набора часто встречающихся элементов
  return result;
}

Кроме того, метод CountInTrans использует словарь поиска в сохраненных счетчиках. Это полезно при подсчете количества вхождений первого члена, потому что разные наборы часто встречающихся элементов могут генерировать одинаковые первые члены. Но, если наборы часто встречающихся элементов уникальны, проверка по словарю поиска — пустая трата времени. Заметьте, что параметр Dictionary используется и обновляется, поэтому вы, вероятно, предпочтете определить его как ref-параметр, чтобы сделать явным его двойное предназначение. Если вы пошагово пройдете по методу GetHighConfRules, то обнаружите несколько других способов модификации кода.

Одна из возможных важных оптимизаций использует тот факт, что для данного набора элементов, если правило-кандидат не отвечает минимальному порогу достоверности, любое другое правило-кандидат, которое содержит второй член первого правила, тоже не может удовлетворять пороговому уровню достоверности. Например, правило IF (2 4 8 9) THEN (3 5) не удовлетворяет минимальному уровню достоверности. Тогда любое правило, имеющее (3 5) в своем втором члене, скажем, IF (4 8 9) THEN (2 3 5), тоже не будет отвечать этому уровню.

Заключение

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

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

По обучению ассоциативным правилам имеется огромный объем научной литературы. Если вас интересует теоретическая часть, советую прочитать главу 6 из книги П. Тэн (P. Tan), М. Штейнбаха (M. Steinbach) и В. Кумара (V. Kumar) «Introduction to Data Mining» (Addison-Wesley, 2005). Эта глава доступна бесплатно в формате PDF по ссылке bit.ly/1m3dbZ9.

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

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