テストの実行

[アーティクル]
06/15/2015

相関ルール学習の頻出項目セット

James McCaffrey

コードサンプルのダウンロード

機械学習やナチュラルユーザーインターフェイス (NUI) の分野で重要な課題の 1 つは、トランザクションリストから頻出項目セットを抽出することです。わかりやすいように例を使って説明しましょう。スーパーマーケットでさまざまな顧客が購入した項目のリストがあるとします。たとえば、ある顧客の購入内容、つまりトランザクションが (りんご, パン, セロリ) で、別の顧客のトランザクションが (パン, ドーナツ, 卵, レタス) の場合が考えられます。このようなトランザクションが数千件も存在することもあります。項目セットとは、(りんご, パン) など、考えられるすべての項目のサブセットです。ここでの課題は、全トランザクションのリストから任意の最小数に達した項目セットだけを抽出することです。最小数を 20 とし、項目セット (りんご, パン) がトランザクションリストに 25 回出現しているとすれば、(りんご, パン) は頻出項目セットです。

頻出項目セットの特定は、さまざまな場面で役に立ちます。スーパーマーケットの場合、同時に購入することが多い項目についての情報をプロダクトプレイスメントやターゲットマーケティングに活用できます。また、すべての頻出項目セットを特定した後で、頻出項目セットをさらに詳しく分析して、"りんごとパンの両方を購入した顧客は、レタスとミルクも購入する可能性が高い" といったルールを抽出できる場合もあります。このような、頻出項目セットを抽出してから条件と結果のルールを収集する処理全体を、相関ルール学習と呼びます。

このコラムでは、頻出項目セットの抽出処理について詳しく説明します。この課題は驚くほど難しく、以前から奥深い研究テーマとして扱われてきました。このコラムの目的を理解するには、図 1 のデモプログラムを見るのが一番です。

図 1 トランザクションからの頻出項目セットの抽出

このデモプログラムでは、10 件のトランザクションのダミーリストを作成します。トランザクションの項目として、架空のスーパーマーケットの商品が合計 12 個 (りんご、パン、セロリ、ドーナツ、卵、小麦、ぶどう、はちみつ、アイシング、ゼリー、キャベツ、およびレタス) あります。最初のトランザクションは (りんご, パン, セロリ, 小麦粉) です。続いて、デモでは処理効率化のために未処理のトランザクションを 0 から始まる整数にエンコードして、表示します。りんごは 0、パンは 1、セロリは 2 のように対応付けているので、最初のトランザクションをエンコードすると (0, 1, 2, 5) になります。

頻出項目セットを抽出するアルゴリズムには 3 つの入力パラメーターが必要です。1 つ目のパラメーターは、項目セットを頻出項目セットに分類するために必要な最小しきい値です。一般に、この値をサポート値と呼びます。このデモでは、サポート値を 0.30 に設定しています。つまり、0.30 * 10 = 3 回が、項目セットを頻出項目セットの結果リストに追加するために必要な、全トランザクションのリストでの項目セットの最小出現回数です。課題となる領域によって、有効なサポート値は異なります。

2 つ目の入力パラメーターは、項目セットの最小サイズです。デモではこの値を 2 に設定しているので、(りんご, ドーナツ) という項目セットは調査しますが、(りんご) だけの項目セットは調査しません。3 つ目の入力パラメーターは、項目セットの最大サイズです。ここでは、この値を 4 に設定しているので、(りんご, セロリ, 卵, ぶどう) など、4 項目以下の項目セットは調査しますが、(りんご, パン, ドーナツ, 小麦粉, はちみつ) など、5 項目以上の項目セットは調査しません。

デモプログラムでは、トランザクションリストから頻出項目セットを抽出するメソッドを呼び出し、合計 12 個の頻出項目セットを特定します。最初の頻出項目セットは (0, 1) で、トランザクションリストに 5 回出現します。最後の頻出項目セットは (0, 1, 2, 5) で、3 回出現しています。最後に、デモでは頻出項目セットを文字列形式で表示します。

このコラムは、読者が少なくとも中級レベルのプログラミングスキルを有していることを前提としますが、相関ルール学習の知識は必要ありません。このコラムにはデモプログラムのコード全体を掲載しており、msdn.microsoft.com/magazine/msdnmag0114(英語) からダウンロードすることもできます。デモは C# でコーディングしていますが、Python など、他の言語へのリファクタリングもそれほど難しくないでしょう。コードのサイズを小さくするために、通常のエラーチェックはすべて省略しています。

頻出項目セットの抽出が難しい理由

一見すると、トランザクションリストからの頻出項目セットの抽出はそれほど難しそうに思えません。単純な総当たり手法なら、考えられるすべての項目セットを生成し、頻出項目セットの候補ごとにトランザクションを反復処理しながら候補の出現回数を数えれば、項目セットが最小サポート数に達したかどうかを判断できるでしょう。残念ながら、意図的に規模を抑えている課題以外では、考えられる項目セットは想像が付かないほど膨大です。たとえば、一般的なスーパーマーケットの在庫商品は、おそらく 10,000 種類をはるかに上回っています。その場合、サイズ 2 の項目セットの数は C(10,000, 2) = 49,995,000 種類です (C(n, k) は n 個の項目から k 個の項目を選ぶ方法が何とおりあるかを表します)。サイズが 9 の項目セットの数は、最大で C(10,000, 9) = 2,745,826,321,280,434,929,668,521,390,000 種類という莫大な量になります。

トランザクションリストから頻出項目セットを効率的に抽出する優れたアルゴリズムは、Apriori アルゴリズム、Eclat アルゴリズム、FP-growth アルゴリズムなど、いくつも存在し、各アルゴリズムに多数のバリエーションがあります。このデモプログラムでは、Apriori アルゴリズムのバリエーションの 1 つを使用します (図 2 参照)。

図 2 Apriori アルゴリズムのしくみ

要約すると、この Apriori アルゴリズムでは、まずサイズ k = 1 となるすべての頻出項目セット (トランザクションリストのサポートしきい値を満たす個別の項目) を処理します。作成プロセスでは、サイズが k = 2、k = 3 などの頻出項目セットを、新しい頻出項目セットが見つからなくなるまで繰り返し追加します。

図 2 の画像は、サイズ k = 4 の項目セットの作成方法を示しています。アルゴリズムでは、あらゆるサイズの頻出項目セットを含んだ単一のリストを保持します。図の例では、サイズ k = 3 の頻出項目セットは、現在 (0, 2, 3)、(0, 2, 8)、および (0, 3, 6) の 3 つです。また、このアルゴリズムでは、常に有効な項目のリストも保持します。図の例では、有効な項目は {0, 2, 3, 6, 8} の 5 つです。サイズ k = 4 の頻出項目セットを作成する有効な項目は、サイズ k-1 = 3 となるすべての頻出項目セットに含まれている個別の項目です。

アルゴリズムでは、サイズ k = 3 の頻出項目セットをそれぞれスキャンし、既存の各項目セットから新しいサイズ k = 4 の頻出項目セット候補を生成します。したがって、最初の頻出項目セット候補は (0, 2, 3, ?) で、? に有効な項目を追加します。このアルゴリズムでは、項目セット内の項目が必ず順序正しく並んでいると想定しているため、今回の場合、? には 6 または 8 だけを追加できます。新しい頻出項目セット候補を 1 つずつ確認して、トランザクションリストに出現する回数を数えます。トランザクション数が最小サポート数に達したら、頻出項目セットリストに候補を追加します。

このアルゴリズムを使用すると、総当たりの生成方式と比べて必要な計算の量が大幅に減少します。たとえば、サイズ k = 3 となる既存の頻出項目セットのうち 2 つ目が (0, 2, 8) である点に注目してください。考えられる頻出項目セット候補の形式は (0, 2, 8, ?) です。しかし、8 を超える有効な項目が存在しないので、候補を生成しません。

プログラムの全体構造

デモプログラムの全体構造を図 3に示します。いくつかの WriteLine ステートメントを削除し、少し編集しています。デモを作成するには、Visual Studio 2012 を起動し、FreqItemSets という名前の新しいコンソールアプリケーションプログラムを作成します。このデモは .NET との大きな依存関係がないため、最近のどのバージョンの Visual Studio でも正常に機能します。エディターにテンプレートコードが読み込まれたら、ソリューションエクスプローラーウィンドウで Program.cs ファイルの名前を FreqItemSetProgram.cs に変更します。これにより、Prograｍクラスの名前が 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 &lt; rawTransactions.Length; ++i) {
           Console.Write("[" + i + "] : ");
           for (int j = 0; j &lt; rawTransactions[i].Length; ++j)
             Console.Write(rawTransactions[i][j] + "   ");
           Console.WriteLine("");
         }
         List transactions = new List();
         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 &lt; transactions.Count; ++i) {
           Console.Write("[" + i + "] : ");
           for (int j = 0; j &lt; 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 frequentItemSets =
           GetFrequentItemSets(N, transactions, minSupportPct,
           minItemSetLength, maxItemSetLength);
         Console.WriteLine("\nFrequent item-sets in numeric form are:");
         for (int i = 0; i &lt; frequentItemSets.Count; ++i)
           Console.WriteLine(frequentItemSets[i].ToString());
         Console.WriteLine("\nFrequent item-sets in string form are:");
         for (int i = 0; i &lt; frequentItemSets.Count; ++i) {
           for (int j = 0; j &lt; 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 GetFrequentItemSets(int N, List transactions,
       double minSupportPct, int minItemSetLength, int maxItemSetLength) { . . }
     static int CountTimesInTransactions(ItemSet itemSet,
       List transactions) { . . }
   }
   public class ItemSet { . . }
 } // ns

ソースコードの先頭では、System と Collections.Generic だけを残して、.NET 名前空間の不要な参照をすべて削除しました。デモでは、まず架空のスーパーマーケットにあるすべての項目のコレクションを作成します。

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 transactions = new List();
 transactions.Add(new int[] { 0, 1, 2, 5 });
 transactions.Add(new int[] { 1, 4, 5 });
 ...
 transactions.Add(new int[] { 0, 1, 2, 5 });

トランザクションリストを表示したら、3 つの入力パラメーター値を設定します。ここでは、頻出項目セットの最大サイズを 4 に設定します。場合によっては、トランザクションリストをスキャンして、この値をトランザクションの最大サイズに設定することもできます。

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

GetFrequentItemSets メソッドを呼び出して、すべての処理を実行します。

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

返す結果として、プログラム定義の ItemSet クラスを使用していることに注意してください。最後に、数値形式と文字列形式の両方で頻出項目セットを表示します。

ItemSet クラス

基本的に項目セットは単なる整数配列なので、プログラム定義のクラスは必要ありません。しかし、個人的な意見としては、今回はクラスを使用するとコードが簡単になります。ItemSet クラスの定義を図 4 に示します。

図 4 ItemSet クラス

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" -&gt; 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 フィールドは項目セットのサイズです。data 配列には項目値を保存します。hashValue フィールドは、項目セットが重複しないように項目セットを特定する一意の整数です。ct フィールドは、トランザクションリストでの項目セットの出現回数です。以下に、ItemSet コンストラクターの定義を示します。

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 &lt; 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 &lt; 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 &lt; array.Length; ++i) {
     if (i &gt; 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 &lt; data.Length; ++i)
     s += data[i] + " ";
   return s + "}" + "   ct = " + ct; ;
 }

GetFrequentItemSets メソッド

GetFrequentItemSets メソッドの定義は次のように始まります。

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

トランザクションの割合としてサポートしきい値の入力パラメーターを指定する代わりに、トランザクションの絶対数を使用することもできます。続いて、3 つの重要なコレクションのインスタンスを作成します。

Dictionary frequentDict = new Dictionary();
 List frequentList = new List();
 List validItems = new List();
 ...

frequentList コレクションには、見つかったすべての頻出項目セットを格納します。すべてのサイズの頻出項目セットを単一のリストに格納する代わりに、重要な代替手法として、リストの配列を使用してこの配列に項目セットサイズごとの個別のリストを格納できます。frequentDict コレクションには、重複を回避できるよう、frequentList に追加した項目セットの ID を格納します。validItems コレクションには、項目値を格納します。アルゴリズムの任意の段階でこの項目値をサイズ k-1 の既存の頻出項目セットに追加すると、サイズ k の頻出項目セット候補を生成できます。次に、トランザクションリストの個別の項目値を数えます。

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

続いて、サポート値に達している項目値を使用して、サイズ k = 1 の頻出項目セット ItemSet オブジェクトを作成し、このオブジェクトを頻出項目のリストに追加します。

for (int i = 0; i &lt; counts.Length; ++i)
 {
   if (counts[i] &gt;= 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 &lt;= maxItemSetLength && done == false; ++k)
 {
   done = true;
   int numFreq = frequentList.Count;
 ...

メインループは、指定したすべてのサイズの調査が終了した場合、または現在のサイズの項目セットが新しく見つからない場合に終了します。すべての頻出項目セットを単一のリストに保存する (さらにこのリストに追加していく) ので、内側のループで使用するためにリストの元のサイズを保存します。内側のループの構造は次のとおりです。

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

このアルゴリズムの 2 つの重要な特徴は、前回の反復処理の頻出項目セットのみを使用して新しい頻出項目セット候補を作成することと、候補を構成する有効な項目値のみを調査することです。頻出項目セット候補は、次のように作成します。

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

このコードは少し複雑です。まず、現在の頻出項目セットのデータを頻出項目セット候補にコピーします。候補は現在の有効な項目値で構成され、前述のとおり、項目セットの順序に関する性質に基づいて候補を削除することもあります。トランザクションに頻出項目セット候補が出現する回数はまだ不明なので、ItemSet コンストラクターの ct フィールドにはダミー値 -1 を渡します。

内側の 2 つのループを結び付けるコードを図 5に示します。

図 5 内側の 2 つのループの連結

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

頻出項目セット候補が既に頻出項目セットリストに存在している場合、それ以上解析する必要はありません。候補がリストに存在していない場合に最小サポート数に達しているときは、その候補を本物の頻出項目セットとして頻出項目セットリストに追加します。done というブール値は、新しい項目セットが見つかったかどうかを追跡します。k がどのような値でも、新しい頻出項目セットが見つからなければ、頻出項目セットが見つかる可能性はありません。

現在のサイズ k についての全候補の作成と調査が完了したら、次回の反復処理に使用する有効な項目のリストを更新します (図 6 参照)。

図 6 有効な項目のリストの更新

...
   validItems.Clear();
   Dictionary validDict = new Dictionary();
   for (int idx = 0; idx &lt; frequentList.Count; ++idx) {
     if (frequentList[idx].k != k) continue;
     for (int j = 0; j &lt; 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-1 の既存の頻出項目セットを使用してサイズ k の新しい頻出項目セット候補を作成する場合、候補を構成する有効な項目は、サイズ k-1 の頻出項目セットに出現する項目値だけです。この更新処理には時間がかかるため、シナリオによっては、この処理を省略して、最初にサイズ k = 1 で作成した有効な項目のリストを使用すると、パフォーマンスが向上します。

GetFrequentItemSets メソッドでは、最後に項目セットの最小サイズで結果をフィルター処理します。

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

以下に、先ほど使用した CountTimesInTransactions ヘルパーメソッドの定義を示します。

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

まとめ

このコラムのコードと説明を知っていれば、Apriori アルゴリズムを使用してトランザクションリストの頻出項目セットを特定する必要が生じた場合に実行できるようになります。スーパーマーケットのトランザクションを直接扱う可能性は低いでしょうが、頻出項目セットの抽出が役に立つシナリオは多数あります。NUI の場合、トランザクションをユーザーコマンドのリスト (検索テキストボックスに入力するテキストなど) と考えることができ、項目をコマンドを構成する単語と考えることができます。このような同時に出現する頻度が高い単語を特定すれば、検索結果の精度向上に役立ちます。

Dr. James McCaffrey は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。連絡先は jammc@microsoft.com(英語のみ) です。

この記事のレビューに協力してくれた技術スタッフの Richard Hughes (Microsoft Research) に心より感謝いたします。