發行項
08/13/2015

本文章是由機器翻譯。

測試回合

用於學習關聯規則的常用項目集

在機器學習和自然使用者介面（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 Studio2012年並創建新的主控台應用程式命名為 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，可以視為交易的使用者命令的清單 — 例如，搜索文字方塊中鍵入文字 — 和作出該命令的單詞的項。識別那些經常在一起出現的單詞可以説明生成更好的搜尋結果。

Dr.James McCaffrey* 為微軟在華盛頓州雷德蒙德的研究工作他曾在幾個 Microsoft 產品，包括互聯網資源管理器和 Bing。他可以在達成 jammc@microsoft.com。*

感謝以下協助校閱本篇文章的技術專家：理查 · 休斯（Microsoft 研究）

測試回合

用於學習關聯規則的常用項目集

為什麼是頻繁項集提取一個困難的問題？

整體程式結構

項集類

GetFrequentItemSets 方法

总结

其他資源