测试运行

用于关联规则学习的频繁项目集

James McCaffrey

下载代码示例

在机器学习和自然用户界面 (NUIs) 等领域的一项重要任务频繁项目集提取交易记录的列表。问题是最好的例子解释。假设您有一个由不同的客户在一家超市购买的项目列表。例如,一个客户的交易可能是 (苹果、 面包、 芹菜),另一人的可能是 (面包、 甜甜圈、 鸡蛋、 生菜)。可能有数以千计的这些交易。项目集是一个子集的所有可能的项目,如 (苹果、 面包)。问题是要从列表中的所有交易记录提取满足一些最小计数只是这些项目集。假设最小计数是 20,项目组 (苹果、 面包) 发生的交易记录列表中 25 倍 ; 因此,(苹果,面包) 会频繁项集。

查明频繁项目集可以在许多方面非常有用。在一家超市,其中的项目经常一起购买的知识可以用于产品定位、 目标市场营销,等等。此外,一旦确认了所有频繁项集,这些项集可以被分析进一步提取规则如,"如果客户购买的苹果和面包,然后有高概率他们将还购买生菜和牛奶"。第一次提取频繁项集,然后收获如果-那么规则的这个整体过程称为关联规则学习。

这篇文章详细地解释了的频繁项集提取工艺。这个问题是非常困难的事情,还受到了相当多的研究。看到这篇文章去哪儿的最佳方法是要看一看在演示程序图 1


图 1 提取交易频繁项目集

演示计划设置虚拟 10 交易记录的列表。在幕后,总共有一个假设的超市中的 12 项:苹果、 芹菜、 甜甜圈、 鸡蛋、 面包、 面粉、 葡萄、 蜂蜜、 糖霜、 果冻、 羽衣甘蓝生菜。在第一个事务是 (苹果、 面包、 芹菜、 面粉)。演示然后显示如何将原始交易可以编码到有效处理基于 0 的整数。因为苹果地图为 0,1,2,依此类推,到芹菜面包在第一个事务被编码为 0、 1、 2 5)。

要提取频繁项集的算法,需要三个输入的参数。第一个参数是必要的项集被归类为频繁的最低门槛值。这通常称为支持的值。在演示中,支持值设置为 0.30,这意味着 0.30 * 10 = 3 项集必须出现在列表中的所有交易的要添加到结果列表的频繁项目集的项集的最小次数。不同的问题域将具有不同有意义的支持值。

第二个输入的参数是最小的项集的大小。在演示的值设置为 2,所以一项目组的 (苹果、 甜甜圈) 被审查但公正 (苹果) 项目组不是。第三个输入的参数是项目组的最大大小。在这里的值设置为 4,所以唯一项目集与最多四个项目,例如 (苹果、 芹菜、 鸡蛋、 葡萄)、 被审查时较大项目集如 (苹果、 面包、 甜甜圈、 面粉、 蜂蜜) 不是。

该演示程序调用方法来频繁项目集提取的交易记录列表,找到共 12 频繁项集。第一次的频繁项目集的 (0,1),在交易列表中出现五次。最后一个频繁项目集是 (0、 1、 2、 5),出现三次。演示在结论中以字符串的形式显示频繁项集。

本文假定您有至少中间级的编程技巧,但并不假定你知道协会规则学习的事。在这篇文章,并还可从下载提出了完整的演示产品的程序代码 msdn.microsoft.com/magazine/msdnmag0114。演示是在 C# 中,但你不应该有太多的麻烦重构到另一种语言,如 Python。删除了所有正常的错误检查以保持代码的大小更小。

为什么是频繁项集提取一个困难的问题?

起初以为,频繁项集提取的交易记录列表看起来那么困难。一个简单的破解方法将只生成所有可能的项目-集并循环访问每个候选人,点票的候选人将出现以查看该项目集是否符合最低支持计数次数的交易记录。不幸的是,在所有但人工小问题,可能的项集的数量是极大。例如,一个典型的超市可能有存货远远超过 10,000 的不同项目。项目集的大小为 2 的数量为选择 (10,000,2) = 的 49,995,000,选择 (n,k) 在哪里如何从 n 个项目中选择 k 项的数目。项目组可能的大小 9 的数是选择 (10,000,9) = 2,745,826,321,280,434,929,668,521,390,000,是......恩,很多。

有几个巧妙的算法,有效地将频繁项集提取的交易,包括先验、 Eclat 和 FP 增长算法列表。每种算法有很多变化。该演示程序使用变化的先验算法,所示的图 2


图 2 分割算法在行动

简单地说,分割算法开始与所有频繁项集的大小 k = 1 — 满足支持阈值的交易记录列表中的单个项目。然后施工过程以迭代方式添加频繁项集的大小 k = 2、 3 等等,直到发现没有新的频繁项集。

中的图像图 2 显示如何项集的大小 k = 4 构造。保持频繁项集的所有尺寸的单个列表。在图中,目前有三个频繁项目集与大小 k = 3:(0、 2、 3)、 (0,2,8) 和 (0,3,6)。该算法也保持的时间是在任何给定的点有效的项的列表。这里有五个有效项目:{0, 2, 3, 6, 8}.有效的项目来构造频繁项集的大小 k = 4 是截然不同的项的所有频繁项集的大小 k-1 = 3。

该算法扫描每个频繁项集的大小 k = 3。对于每个现有的项目组,一个新的候选频繁项集的大小 k = 4 生成的。所以,第一位候选人是 (0,2,3,?)。对吗?可以填写一个有效的项目。该算法假定对项目组内的项目总是顺序存储的所以呢?可以在这种情况下是唯一 6 或 8。检查每个新的候选人,以计数它在交易列表中出现多少次。如果事务计数符合最低支持计数,该候选人被添加到频繁项目集的列表。

该算法大大减少了大量的计算需要,强力代方法相比。例如,请注意,第二个现有频繁项目集与大小 k = 3 是 0、 2 8)。潜在候选人将有窗体 (0,2,8,?)。但由于没有有效的项目是大于 8,没有可能的候选人,生成。

程序的总体结构

整体结构的演示程序中删除某些 WriteLine 语句和一些少量的编辑,提交在图 3。若要创建演示,我发起了 Visual Studio 2012 并创建新的控制台应用程序命名为 FreqItemSets。演示没有任何重大的.NET 依赖项,和任何相对较新版本的 Visual Studio 将可以正常工作。加载到编辑器中的模板代码后,在解决方案资源管理器窗口中改名 Program.cs 文件到 FreqItemSetProgram.cs,和 Visual Studio 自动重命名类的程序,对我来说。

图 3 演示的程序结构

 

using System;
using System.Collections.Generic;
namespace FreqItemSets
{
  class FreqItemSetProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin frequent item-set extraction demo\n");
        string[] rawItems = new string[] { "apples", "bread ", "celery", "donuts",
          "eggs  ", "flour ", "grapes", "honey ", "icing ", "jelly ",
             "kale  ", "lettuce" };
        int N = rawItems.Length; // total number of items to deal with ( [0..11] )
        string[][] rawTransactions = new string[10][];
        rawTransactions[0] = new string[] { "apples", "bread ", "celery",
           "flour " };
        rawTransactions[1] = new string[] { "bread ", "eggs  ", "flour " };
        rawTransactions[2] = new string[] { "apples", "bread ", "donuts",
           "eggs  " };
        rawTransactions[3] = new string[] { "celery", "donuts", "flour ",
           "grapes" };
        rawTransactions[4] = new string[] { "donuts", "eggs  " };
        rawTransactions[5] = new string[] { "donuts", "eggs  ", "jelly " };
        rawTransactions[6] = new string[] { "apples", "bread ", "donuts",
           "icing " };
        rawTransactions[7] = new string[] { "bread ", "grapes", "honey " }; 
        rawTransactions[8] = new string[] { "apples", "bread ", "celery",
           "flour ", "kale  " };
        rawTransactions[9] = new string[] { "apples", "bread ", "celery",
           "flour " };
        for (int i = 0; i < rawTransactions.Length; ++i) {
          Console.Write("[" + i + "] : ");
          for (int j = 0; j < rawTransactions[i].Length; ++j)
            Console.Write(rawTransactions[i][j] + "   ");
          Console.WriteLine("");
        }
        List<int[]> transactions = new List<int[]>();
        transactions.Add(new int[] { 0, 1, 2, 5 });
        transactions.Add(new int[] { 1, 4, 5 });
        transactions.Add(new int[] { 0, 1, 3, 4 });
        transactions.Add(new int[] { 2, 3, 5, 6 });
        transactions.Add(new int[] { 3, 4 });
        transactions.Add(new int[] { 3, 4, 9 });
        transactions.Add(new int[] { 0, 1, 3, 8 });
        transactions.Add(new int[] { 1, 6, 7 });
        transactions.Add(new int[] { 0, 1, 2, 5, 10 });
        transactions.Add(new int[] { 0, 1, 2, 5 });
        for (int i = 0; i < transactions.Count; ++i) {
          Console.Write("[" + i + "] : ");
          for (int j = 0; j < transactions[i].Length; ++j)
            Console.Write(transactions[i][j].ToString() + " ") ;
          Console.WriteLine("");
        }
        Console.WriteLine("");
        double minSupportPct = 0.30;
        int minItemSetLength = 2;
        int maxItemSetLength = 4;
        List<ItemSet> frequentItemSets =
          GetFrequentItemSets(N, transactions, minSupportPct,
          minItemSetLength, maxItemSetLength);
        Console.WriteLine("\nFrequent item-sets in numeric form are:");
        for (int i = 0; i < frequentItemSets.Count; ++i)
          Console.WriteLine(frequentItemSets[i].ToString());
        Console.WriteLine("\nFrequent item-sets in string form are:");
        for (int i = 0; i < frequentItemSets.Count; ++i) {
          for (int j = 0; j < frequentItemSets[i].data.Length; ++j) {
            int v = frequentItemSets[i].data[j];
            Console.Write(rawItems[v] + "   ");
          }
          Console.WriteLine("");
        }
        Console.WriteLine("\nEnd frequent item-set extraction demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);  Console.ReadLine();
      }
    }
    static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
      double minSupportPct, int minItemSetLength, int maxItemSetLength) { . . }
    static int CountTimesInTransactions(ItemSet itemSet,
      List<int[]> transactions) { . . }
  }
  public class ItemSet { . . }
} // ns

顶部的源代码中删除所有不必要的引用的.NET 命名空间,离开只是系统和 Collections.Generic。 演示开始通过设置的一个假设性的超市中的所有项的集合:

string[] rawItems = new string[] { "apples", "bread ", "celery",
  "donuts", "eggs  ", "flour ", "grapes", "honey ", "icing ",
  "jelly ", "kale  ", "lettuce" };
int N = rawItems.Length; // total items in inventory

下一步程序设置 10 硬编码的交易记录。 在大多数情况下,将文字文件或 SQL 数据库中存储您的交易。 请注意允许重复的交易记录,并不是所有物料在库存中一定在一个事务中:

string[][] rawTransactions = new string[10][];
rawTransactions[0] = new string[] { "apples", "bread ", "celery", "flour "};
rawTransactions[1] = new string[] { "bread ", "eggs  ", "flour " };
...
rawTransactions[9] = new string[] { "apples", "bread ", "celery", "flour "};

在显示的原始交易记录后, 演示设置基于 0 编码事务的列表。 而不是硬编码的在大多数情况下您将以编程方式创建数字交易从原始交易。 注意每个交易记录中的项目都独特和排序:

List<int[]> transactions = new List<int[]>();
transactions.Add(new int[] { 0, 1, 2, 5 });
transactions.Add(new int[] { 1, 4, 5 });
...
transactions.Add(new int[] { 0, 1, 2, 5 });

在显示的交易记录列表后, 三个输入的参数值设置。 在这里,频繁项集的最大大小设置为 4。 你可能想要扫描的事务列表和值设置为最长事务的长度:

double minSupportPct = 0.30;
int minItemSetLength = 2;
int maxItemSetLength = 4;

通过调用 GetFrequentItemSets 方法执行的所有工作:

List<ItemSet> frequentItemSets =
  GetFrequentItemSets(N, transactions, minSupportPct,
  minItemSetLength, maxItemSetLength);

请注意,返回的结果使用程序定义的项集类。 演示通过在数值和字符串的窗体中显示频繁项目集的结论。

项集类

本质上,项目组是只是一个整数数组,所以没有程序定义的类是必需的。 但是,在我看来,在这种情况下使用一类简化代码。 在中定义的项集类图 4

图 4 项集类

public class ItemSet
{
  public int N; // data items are [0..N-1]
  public int k; // number of items
  public int[] data; // ex: [0 2 5]
  public int hashValue; // "0 2 5" -> 520 (for hashing)
  public int ct; // num times this occurs in transactions
  public ItemSet(int N, int[] items, int ct) { . . }
  private static int ComputeHashValue(int[] data) { . . }
  public override string ToString() { . . }
  public bool IsSubsetOf(int[] larger) { . . }
  private static int IndexOf(int[] array, int item, int startIdx) { . . }
}

N 的成员字段是在库存中的总项数。 字段 k 是项集的大小。 数组数据保存的项值。 字段 hashValue 是一个唯一的整数来标识的项集,因此可以避免重复的项目集。 字段 ct 是交易列表中的项集出现的次数。 项集构造函数的定义:

public ItemSet(int N, int[] items, int ct)
{
  this.N = N;
  this.k = items.Length;
  this.data = new int[this.k];
  Array.Copy(items, this.data, items.Length);
  this.hashValue = ComputeHashValue(items);
  this.ct = ct;
}

要计算 hashValue 的帮助器方法是:

private static int ComputeHashValue(int[] data)
{
  int value = 0;
  int multiplier = 1;
  for (int i = 0; i < data.Length; ++i) {
    value = value + (data[i] * multiplier);
    multiplier = multiplier * 10;
  }
  return value;
}

佣工将项值转换为一个整数在背面。 例如,如果项目是 0、 2 5) 的哈希值是 520。 该方法的工作在反向处理领先 0-项目,因为否则为 0、 2 5) 和 2 5) 两个哈希到 25。

IsSubsetOf 方法返回 true 如果项目组的对象是一个事务的一个子集:

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

该方法是短但略有微妙。 因为交易和项目集已排序后一项值的项集的事务内被发现,,为项目的下一个值搜索没有索引 0 处开始 — 它可以在以下地方找到以前的项值的位置的下一个索引开始。 帮助器 IndexOf 的定义:

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

IndexOf 方法还利用订购。 如果当前的搜索索引大于所搜索的目标项值,搜索已走得太远,并将永远找不到该项目。 例如,假设一个事务是 (0、 2、 4、 5、 6、 8),所搜索的目标项是 3。 因为交易记录进行排序,可以发生 3 的最新值将是在事务具有窗体中 (0、 1、 2、 3、 x、 x)。 ToString 方法为简单起见使用字符串串联:

public override string ToString()
{
  string s = "{ ";
  for (int i = 0; i < data.Length; ++i)
    s += data[i] + " ";
  return s + "}" + "   ct = " + ct; ;
}

GetFrequentItemSets 方法

GetFrequentItemSets 方法的定义开始:

static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
  double minSupportPct, int minItemSetLength, int maxItemSetLength)
{
  int minSupportCount = (int)(transactions.Count * minSupportPct);
...

而不是交易的百分比指定支持阈值的输入的参数,您可能想要使用一个绝对计数。 下一步,实例化的三个重要的收藏:

Dictionary<int, bool> frequentDict = new Dictionary<int, bool>();
List<ItemSet> frequentList = new List<ItemSet>();
List<int> validItems = new List<int>();
...

集合 frequentList 持有所有频繁项集发现。 而不是存储在单个列表中的频繁项集的所有尺寸,重要的替代方法是使用列表的数组有单独的列表,对于每个项集的大小。 集合 frequentDict 持有的已添加到 frequentList 因此可以避免重复这些项目集的 Id。 集合 validItems 持有的项值,在任何给定的算法,可以添加到现有频繁项集的大小 k-1 生成一个候选频繁项集的大小 k。 下一步,交易记录列表中的单个项值进行计数:

int[] counts = new int[N];
for (int i = 0; i < transactions.Count; ++i)
{
  for (int j = 0; j < transactions[i].Length; ++j) {
    int v = transactions[i][j];
    ++counts[v];
  }
}
...

然后满足的最小支持计数的那些项值用于创建频繁项集对象的大小 k = 1,然后添加到的频繁项的列表:

for (int i = 0; i < counts.Length; ++i)
{
  if (counts[i] >= minSupportCount) {
    validItems.Add(i); // i is the item-value
    int[] d = new int[1]; // ItemSet ctor wants an array
    d[0] = i;
    ItemSet ci = new ItemSet(N, d, 1); // size 1, ct 1
    frequentList.Add(ci); // it's frequent
    frequentDict.Add(ci.hashValue, true); // record
  } // else skip this item
}
...

主要加工循环中的,在伪代码是:

loop for size k = 2, 3, until done
  foreach existing freq item-set of size k-1
    foreach valid item
      create a candidate item-set
      count times candidate in transactions
      if candidate meets support threshold
        if candidate not already in frequent list
          add candidate to frequent, rec list
    end each valid item
    update valid items
  end each freq item-set
end main loop

主要处理循环设置像这样:

bool done = false;
for (int k = 2; k <= maxItemSetLength && done == false; ++k)
{
  done = true;
  int numFreq = frequentList.Count;
...

主循环将退出时所有指定的大小已经考试­三四年,或时发现在没有新的项目集的当前大小。 因为所有频繁项集都存储在单个列表 (该列表添加到),列表中的初始大小由内部循环,设置存储为使用像这样:

for (int i = 0; i < numFreq; ++i)
{
  if (frequentList[i].k != k - 1) continue;
  for (int j = 0; j < validItems.Count; ++j)
  {
    int[] newData = new int[k]; // data for a candidate item-set
...

算法的两个重要功能是该算法使用只有频繁项目集从上一次迭代来构造新的候选项集和它检查完成候选人的唯一有效的项目值。候选频繁项集被创建:

 

for (int p = 0; p < k - 1; ++p)
  newData[p] = frequentList[i].data[p];
if (validItems[j] <= newData[k - 2]) continue;
newData[k - 1] = validItems[j];
ItemSet ci = new ItemSet(N, newData, -1);
...

此代码是轻度棘手。 第一,从当前频繁项目集的数据复制到该候选人。 候选人完成与有效的项目的当前值,并且,如前面所述,候选人可能会被淘汰基于项目集的排序属性。 项集构造函数接受伪值为-1,ct 字段,因为该候选人在交易中出现的次数不尚未已知。

两个内部循环被栓在所示的代码与图 5

图 5 绑两个内部循环

...
    if (frequentDict.ContainsKey(ci.hashValue) == true)
      continue;
    int ct = CountTimesInTransactions(ci, transactions);
    if (ct >= minSupportCount)
    {
      ci.ct = ct;
      frequentList.Add(ci);
      frequentDict.Add(ci.hashValue, true);
      done = false;
    }
  } // j
} // i
...

如果该候选人已经出现在频繁项目集列表中,没有必要进一步对其进行分析。 如果不是,并且如果该候选人满足最低支持计数,该候选人是一个赢家和它添加到频繁项目集的列表。 做轨道,无论已发现任何新的项目集的布尔值。 K 任何给定值,如果没有新的频繁项集发现,没有过将找到的频繁项目集的可能性。

当前大小 k 所有候选人已经建成并审查后,会更新的有效项的下一次迭代列表,如中所示图 6

图 6 更新的有效项目的列表

...
  validItems.Clear();
  Dictionary<int, bool> validDict = new Dictionary<int, bool>();
  for (int idx = 0; idx < frequentList.Count; ++idx) {
    if (frequentList[idx].k != k) continue;
    for (int j = 0; j < frequentList[idx].data.Length; ++j) {
      int v = frequentList[idx].data[j]; // item
      if (validDict.ContainsKey(v) == false) {
        validItems.Add(v);
        validDict.Add(v, true);
      }
    }
  }
        validItems.Sort();
} // next k
...

虽然不完全明显起初,原来当构建新候选人频繁项目集的大小 k 使用现有频繁项集的大小 k-1,要完成候选人的唯一有效的项目是发生在频繁项集的大小 k-1 的项值。 此更新过程是非常耗时的和在某些情况下你会更好的性能通过跳过它而不使用的有效项的原始列表创建为大小 k = 1。

该方法通过按项集的最小长度过滤结果得出结论认为:

...
  List<ItemSet> result = new List<ItemSet>();
  for (int i = 0; i < frequentList.Count; ++i)
  {
    if (frequentList[i].k >= minItemSetLength)
    result.Add(new ItemSet(frequentList[i].N,
      frequentList[i].data, frequentList[i].ct));
  }
  return result;
}

帮助器方法 CountTimesInTransactions,较早前,使用的定义:

static int CountTimesInTransactions(ItemSet itemSet,
  List<int[]> transactions)
{
  int ct = 0;
  for (int i = 0; i < transactions.Count; ++i) {
    if (itemSet.IsSubsetOf(transactions[i]) == true)
      ++ct;
  }
  return ct;
}

总结

代码与本文中介绍的解释应让你起来和运行如果你需要,确定从列表中使用先验的算法交易的频繁项集。 虽然它不太可能你会过工作直接与超市的交易,有提取频繁项集可能会用到的很多方案。 在 NUI,可以视为交易的用户命令的列表 — 例如,搜索文本框中键入文字 — 和作出该命令的单词的项。 识别那些经常在一起出现的单词可以帮助生成更好的搜索结果。

James McCaffrey詹姆斯 · 麦卡弗里为微软在华盛顿州雷德蒙德的研究工作 他曾在几个 Microsoft 产品,包括互联网资源管理器和 Bing。他可以在达成 jammc@microsoft.com

由于以下的技术专家对本文的审阅:理查德 · 休斯 (Microsoft 研究)