2015-08-13

本文章是由機器翻譯。

測試回合

學習關聯規則

關聯規則學習是從的從一組資料中提取如果-那麼規則的機器學習領域的技術。例如，如果正在探索的資料是一組超市事務，一個關聯規則可能是，"如果客戶購買的蘋果和咖啡然後他還會買黃油和甜甜圈的可能性較高"。

有幾種類型的關聯規則。這篇文章解釋了如何提取高信任規則的特點是真被分析的交易記錄的指定的最小百分比。關聯規則學習可以應用於多種類型的資料除了採購交易，包括系統日誌檔、使用者搜索查詢和自然使用者介面命令。這篇文章解釋了如何高信心協會規則學習工程，並提供了完整的演示程式。

看到這篇文章去哪兒的最佳方法是要看一看在演示程式圖 1。演示設置 10 虛擬交易，編碼所以每個專案是一個基於 0 的值。例如，在第一個事務是（0 3 4 11），這意味著商品 0、 3、 4、 11 一起發生。在大多數情況下，允許重複交易，如交易 2 和 3。

圖 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)

圖 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 技術專家對本文的審閱：理查 · 休斯和KirkOlynik

共用方式為