测试运行

项目
07/06/2015

关联规则学习

James McCaffrey 关联规则学习是从的从一组数据中提取如果-那么规则的机器学习领域的技术。例如，如果正在探索的数据是一组超市事务，一个关联规则可能是，"如果客户购买的苹果和咖啡然后他还会买黄油和甜甜圈的可能性较高"。

有几种类型的关联规则。这篇文章解释了如何提取高信任规则的特点是真被分析的交易记录的指定的最小百分比。关联规则学习可以应用于多种类型的数据除了采购交易，包括系统日志文件、用户搜索查询和自然用户界面命令。这篇文章解释了如何高信心协会规则学习工程，并提供了完整的演示程序。

看到这篇文章去哪儿的最佳方法是要看一看在演示程序图 1。演示设置 10 虚拟交易，编码所以每个项目是一个基于 0 的值。例如，在第一个事务是（0 3 4 11），这意味着商品 0、 3、 4、 11 一起发生。在大多数情况下，允许重复交易，如交易 2 和 3。

Finding High-Confidence Association Rules
图 1 找到高信心关联规则

虽然您可以直接在编码的交易数据上执行搜索的高信心关联规则，在大多数情况下频繁项目集第一次从提取的交易记录。项目集的一个子集的所有可能的交易，并频繁项集是那些满足一些用户指定最小出现次数（称为支持级别）中的交易记录集。在演示中，使用支持值为 0.30 （所以项目组必须发生在至少 0.30 * 10 = 3 交易），有八个频繁项集。第一是（2 5）。2 和 5 项一起发生在三个交易中：7、 8 和 9。频繁项目集消除异常交易可能会生成一个非常高信任规则，但它们如此罕见的规则并不是特别相关。在大多数情况下，频繁项集是不同的不含重复项允许。从交易中提取频繁项集是出人意料的困难的任务。在 MSDN 杂志在 2013 年 1 月问题中看到"频繁项目集的关联规则学习" msdn.microsoft.com/magazine/dn519928。

在幕后，演示使用频繁项集的列表生成候选规则。每个候选规则被评估，以确定是否该规则符合用户提供最低限度的可能性称为信心值。这些候选规则，达到或超过的可能性级别标识作为高-信心规则。在演示中，信心值设置为 0.700，意味着一个候选规则必须是真实的至少 70%的交易记录的规则是适用。

在演示中，发现 16 高信心规则。列出的第一个规则是如果（2）然后 (5) 与计算 0.75 信心值。你可以认为这作为，"是否某事务具有项目 2，然后交易可能还包含项目 5"。该规则，叫前面的任务，如果部分适用于四个交易记录：6、 7、 8 和 9。规则是真正为这些四个交易的三个：7、 8 和 9，所以计算的信心是 3/4 = 0.75。

注意到高信心的规则不一定对称。有没有如果（5）然后 (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）生成两个非高信心规则和四个高信心规则。算法开始通过生成所有数学组合为大小 k = 1 通过大小项集长度为-1。数学组合是学习本文中介绍的算法的关联规则的关键。数学组合是一组数字，它表示一个子集。例如，如果有 5 项 = （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)

Algorithm to Find High-Confidence Rules
图 2 算法来查找高信心规则

数学组合中的元素不是交易项目，它们只是数字。在图 2，每个组合适用于频繁项集，以生成项目集，被解释为一个候选规则前面的任务（如果部分）的一个子集。例如，最后组合为 k = 2 是（1，2）所以在频繁项目集中 (3 4 7）在指数 1 和 2 项用作候选规则前面的任务："如果 (4 7)."候选规则的那部分包括的项集合正在审查中的那些项不在如果部件中使用。所以为的项集 (3 4 7)，如果前面的任务是 (4 7)、那部分（称为，因而）是（3）和全部候选规则是"如果 (4 7) 然后 (3)."

有些吃惊地候选规则的那部分不是需要计算的规则的信心值。如果考虑的候选规则 (4 7) 然后 (3)。若要计算信心，所需的交易记录的规则是适用的计数。这些将包含项目 4 和 7，，在演示的情况下是 3 （交易 2、 3 和 6）这些交易。计算所需的第二部分是适用交易候选规则结果为 true，换句话说，那些有项目 4、 7 的交易次数和也第 3 项。但这是只包含源频繁项目集 (3 4 7）的交易次数。

在图 2、每个六个候选规则的信心值的计算，和满足信任阈值的四个被确定为高信心的规则。

总之，从一组满足最低频率的发生的支持水平，为每个频繁的项目的频繁项目集开始生成所有数学组合从大小 1 通过一个小于数的项集合中的项。每个组合确定如果和一个候选规则的那一部分。标记为好 (高信心）规则候选人满足规则的最低信任级别，这是适用频繁项目集规则结果为 true 的比例，并将其保存。

程序的整体结构

若要创建演示计划我发起了 Visual Studio。演示计划没有任何重大的.NET 依赖项和任何版本的 Visual Studio 的支持 Microsoft.NET Framework 2.0 或更高版本应该很好地工作。我创建一个 C# 控制台应用程序，并将它命名为 AssocRuleLearn。由模板生成的代码加载到编辑器后，在解决方案资源管理器窗口中我重命名 Program.cs 为更具描述性的 AssocRuleProgram.cs 和 Visual Studio 自动重命名类的程序，对我来说。在源代码的顶部，删除所有引用不需要命名空间，离开只是那些对系统和 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 part
    public int[] consequent; // Then part
    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 类型的数组并设置硬编码事务的列表。你可能想要创建一个程序定义的项集类。在大多数情况下的原始交易数据将文字文件或 SQL 数据库中并需要进行编码。演示设置硬编码频繁项集。在所有但非常小的演示方案你会需要提取频繁项目集以编程的方式，这是一个非常困难的任务。

正在寻找高信心规则的所有工作是 GetHighConfRules 方法所都执行的。这种方法需要一个用户指定的最小信心百分比参数值。有意义的信心值将会发生变化从一个问题跳到另一个问题。

该演示程序使用一个程序定义的规则类。类成员是规则前面的任务（如果部分）、规则随后 (那部分) 和计算所得的信心的价值。类有只是一个构造函数和一个 ToString 方法，被黑客攻击演示设置数据格式，很好。

方法 GetHighConfRules 调用几个帮助器方法。方法 CountInTrans 的交易记录列表中的项集或规则延续或规则随后出现的次数进行计数。此帮助器方法调用分帮助器 IsSubsetOf，反过来调用 IndexOf 分帮助器。 NewCombination 方法创建数学组合。 NextCombination 方法返回下一个组合元素为给定的组合。方法 MakeAntecedent 和 MakeConsequent 返回如果部分和对于候选规则，鉴于频繁项集和数学相结合的那部分。

数学组合

如果您引用的关系图中图 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 确定大小的组合。新组合是通过 k-1，按顺序值 0。 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 是短而不是琐碎。它接受一个组合，并在组合中，可能项的数目。如果输入的组合是按字典序顺序中的最后一个，该方法返回输入的组合，或者为 null 辞书的继任者。例如，如果一个组合以 n = 6 和 k = 3 是（1、 4、 5）然后下一个组合是（2、 3、 4）。

生成规则的先例和 Consequents

帮助器方法 MakeAntecedent 接受频繁项集和数学组合，并返回一个候选规则如果部分。例如，如果一个频繁项目集是（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 生成候选规则的那部分。例如，如果一个频繁项目集是（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; // ptr into combination
  int p = 0; // ptr into result
  for (int i = 0; i < itemSet.Length; ++i) {
    if (j < comb.Length && i == comb[j])
      ++j;
    else
      result[p++] = itemSet[i];
  }
  return result;
}

我设计 MakeConsequent 以便它接受同一 parameters 作为 MakeAntecedent 的方法。某种程度的更简单但不对称替代方法是定义 MakeConsequent，这样，它接受一个项集和延续。

计数在交易中出现的次数

前面的任务发生或关键的帮助器方法 CountInTrans 接受 int 可以表示的频繁项目集或候选规则先行词、的交易，列表和字典集合，并返回的次数的项集的数组。字典对象存储的项集和先行计数和用作查找，因此这些项目集或已经过处理的先例不需要将叙述：

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 frequent item-set
  ctItemSet = count times item-set is in transactions
  for subset length 1 to item-set length - 1
    create a new math combination
    loop over each possible math combination
      create candidate rule if-part
      create candidate rule then-part
      compute confidence of candidate rule
      if candidate rule meets min confidence, save
    end loop
  end for
end for
return saved rules

GetHighConfRules 方法的实现中列出图 5。虽然您可以使用 GetHighConfRules 方法中列出图 5，有很多机会，以提高性能，通常影响内存或代码清晰。例如，如果你是指图 2，您会注意到每个候选规则前面的任务随后对已具有延续和随后被交换的镜子候选规则。例如，如果项目集是（2 5 7 9），然后一个候选规则与子集大小 k = 2 是如果 (2 7) 然后 (5 9) 和另一名候选人的规则是如果 (5 9) 然后 (2 7)。因此，而不是计算的所有可能值的频繁项集子集的大小的先例，只是可以计算的先例和一半的可能子集大小为 consequents。

图 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]; // for clarity
    int ctItemSet = CountInTrans(currItemSet, trans, itemSetCountDict);
    for (int len = 1; len <= currItemSet.Length - 1; ++len)
    {
      int[] c = NewCombination(len);
      while (c != null) // each combination makes a candidate rule
      {
        int[] ante = MakeAntecedent(currItemSet, c);
        int[] cons = MakeConsequent(currItemSet, c); // could defer
        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 each combination
    } // len each possible antecedent for curr item-set
  } // i each freq item-set
  return result;
}

此外，CountInTrans 方法使用保存计数查找字典。这是很有帮助时计数先行发生，因为不同的频繁项集可以生成相同的安特cedents。但是如果频繁项集是唯一的然后查找字典中的检查是在浪费时间。通知的字典参数是使用和更新，所以您可能想要将它定义为 ref 参数，使其双重目的明确。如果您跟踪通过 GetHighConfRules 方法，您将看到其他几种方式来修改的代码。

一个重要的优化可能利用到的事实对于给定的项目集，如果候选人的规则不符合的最低信心阈值，则包含的第一个规则产生的任何其他候选规则无法满足信任阈值。例如，假设一条规则，如果 (2 4 8 9）然后（3 5）不能满足最低限度的信心。然后（3 5）在其产生的例如，如果有任何规则 (4 8 9) 然后 (2 3 5），将不能满足最低限度的信心，也。

总结

关联规则和本文中介绍的演示代码的解释应启动及运行如果你想要尝试提取高信心关联规则，或创建一个独立协会规则实用程序，或协会规则功能添加一个软件应用程序。

不打算作出预测的几个机器学习技术，像协会规则学习是一种探索性的技术旨在揭示有趣和可能有用的项目之间的关系。这意味着你必须使用钻头的试验和错误时发现关联规则。

有一个大的关联规则学习有关的研究文献机构。如果你有兴趣在理论上，我推荐书，"引入到数据挖掘"（艾迪生-韦斯利，2005年）由体育第 6 的章 Tan，M。斯坦贝奇和 V。库马尔。 6 章就是免费的 PDF 格式在 bit.ly/1m3dbZ9。

**Dr。**James McCaffrey · 麦卡弗里为微软在华盛顿州雷德蒙德的研究工作他曾在几个 Microsoft 产品，包括互联网资源管理器和 Bing。博士。麦卡弗里也可以拨打 jammc@microsoft.com。

衷心感谢以下 Microsoft 技术专家对本文的审阅：理查德 · 休斯和柯克 Olynik