相関ルール学習
.jpg)
相関ルール学習は、一連のデータから if-then ルールを抜き出す機械学習テクニックの 1 つです。たとえば、スーパーマーケットの一連の取引データを調べると、「りんごとコーヒーを購入した顧客は、バターとドーナツも購入する可能性が高い」という相関ルールを導き出せることがあります。
相関ルールには、いくつか種類があります。今回は、解析対象の一連の取引のうち、指定した最小限の割合で真となる信頼度の高いルールを取り出す方法について説明します。相関ルール学習は、購入取引以外にも、システム ログ ファイル、ユーザー検索クエリ、ナチュラルな UI コマンドなど、さまざま種類のデータに応用できます。今回は、信頼性の高い相関ルール学習のしくみを説明し、完成したデモ プラグラムを示します。
コラムの趣旨を理解するには、図 1 のデモ プログラムを見るのが一番です。デモでは、各商品を 0 から始まる値にコード化した 10 件のダミー取引を用意します。たとえば、最初の取引 (0 3 4 11) は、商品 0、3、4、11 が同時に購入されたことを示します。取引 2 と取引 3 のように、ほとんどの場合、取引の重複は許可されています。
.png)
図 1 信頼度の高い相関ルールを見つける
コード化した取引データを調べて信頼度の高い相関ルールを直接探してもかまいませんが、多くの状況では、まず取引の中からよく一緒に購入される商品の組み合わせ (頻出項目セット) を抜き出します。商品の組み合わせは、すべての可能な取引のサブセットで、頻出項目セットとは、一連の取引の中でユーザーが指定する最少出現回数 (支持度と呼ぶ) を満たす組み合わせを指します。デモでは、支持度 0.30 (つまり、0.30 * 10 = 3 件以上の取引に出現する商品の組み合わせ) を使用します。今回の例の頻出項目セットは 8 個あります。1 つ目の組み合わせは (2 5) です。商品 2 と商品 5 は、3 件の取引 (7、8、9) に同時に出現します。頻出項目セットにより外れ値の取引が除外されます。外れ値の取引が非常に信頼度の高いルールを導き出すこともありますが、そのようなことはめったに起こりません。ほとんどの場合、頻出項目セットは一意にし、重複を許可しません。この頻出項目セットを取引から抜き出すのは想像以上に難しい作業です。詳細については、MSDN マガジン 2013 年 1 月号の「相関ルール学習の頻出項目セット」( msdn.microsoft.com/magazine/dn519928) を参照してください。
デモでは、頻出項目セットのリストを使用して相関ルールの候補を導き出します。各候補ルールを評価して、ユーザーが指定する確率の最小しきい値 (信頼度) を満たしているかどうか判断します。指定した信頼度を満たすか、それを超える相関ルールの候補を、信頼度の高いルールとします。デモでは、信頼度を 0.700 に設定します。つまり、信頼度の高いルールと見なされるには、相関ルールの候補は取引の 70 % 以上で真でなければなりません。
デモでは、信頼度の高いルールが 16 個見つかりました。リスト最初のルールは IF (2) THEN (5) で、信頼度は 0.75 と算出されています。これは、「取引に商品 2 が含まれる場合、その取引には商品 5 も含まれる確率が高い」と解釈できます。このルールの IF 部分 (前提部) は、6、7、8、9 の 4 件の取引に当てはまります。このルールは、これら 4 件の取引のうち 3 件 (7、8、9) で真になるため、信頼度は 3/4 = 0.75 と算出されます。
信頼度の高いルールは、必ずしも IF 部分と THEN 部分を入れ替えられるわけではありません。たとえば、IF (5) THEN (2) のルールは、取引 1、4、5、7、8、9 に当てはまりますが、真になるのは取引 7、8、9 のみなので、信頼度は 3/6 = 0.50 となり、最小しきい値 0.700 に満たないため、このルールは信頼度の高いルールと見なされません。
今回のコラムは、高度なプログラミング スキルを備えた読者を想定していますが、相関ルール学習についてはまったく知らなくても問題ありません。デモ プログラムは C# を使ってコーディングしましたが、Visual Basic や IronPython などの他の .NET 言語へのコードのリファクタリングもそれほど難しくないはずです。コードを小さく抑え、中心となる考え方を明瞭にするため、通常のエラー チェックの大部分は削除しています。デモの完全なソース コードをこのコラムに掲載していますが、msdn.microsoft.com/magazine/msdnmag0514 (英語) からダウンロードすることもできます。
ルール検出アルゴリズム
信頼度の高いルールを見つけるためにデモ プログラムで使用したアルゴリズムを、図 2 に示します。この図からは、頻出項目セット (3 4 7) から信頼度の高くないルール 2 個と信頼度の高いルール 4 個を導き出す方法がわかります。アルゴリズムは、まず 1 から "項目セットの長さ - 1" までのサイズ k について、すべての数学的組み合わせを生成します。数学的組み合わせは、このコラムで紹介する相関ルール学習アルゴリズムの鍵となります。数学的組み合わせは、サブセットを表す数のセットです。たとえば、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)
.png)
図 2 信頼度の高いルールを見つけるアルゴリズム
数学的組み合わせの要素は取引商品ではなく、単なる数値です。図 2 では、各組み合わせを頻出項目セットに当てはめ、項目セットのサブセットを生成します。このサブセットは、相関ルールの候補の前提部 (IF 部分) と解釈されます。たとえば、k = 2 の最後の組み合わせは (1, 2) なので、頻出項目セット (3 4 7) のインデックス 1 と 2 に当たる項目を相関ルールの候補の前提部 "IF (4 7)" として使用します。相関ルール候補の THEN 部分は、調べている項目セットの項目のうち IF 部分で使用しなかった項目で構成されます。そのため、項目セット (3 4 7) で前提部が (4 7) の場合、THEN 部分 (結論部) は (3) となり、相関ルール候補全体は "IF (4 7) THEN (3)" になります。
少し意外な感じもしますが、相関ルール候補の THEN 部分はルールの信頼度の計算には必要ありません。相関ルール候補 IF (4 7) THEN (3) について考えてみます。信頼度を計算するには、ルールを当てはめる取引数が必要です。これは項目 4 と 7 を含む取引に相当し、デモでは 3 件あります (取引 2、3、6)。必要な計算の第 2 の部分は、相関ルール候補が真になる取引、つまり項目 4 と 7 に加えて項目 3 も含む取引の数です。しかし、これは元の頻出項目セット (3 4 7) を含む取引数にすぎません。
図 2 では、6 個の相関ルール候補のそれぞれについて信頼度を計算し、信頼度のしきい値を満たす 4 個のルールが信頼度の高いルールと見なされています。
要するに、最小限の出現頻度の支持度を満たす一連の頻出項目セットから開始し、それぞれの頻出項目について、サイズ 1 からその項目セットの項目数から 1 を引いた数のサイズまでのすべての数学的組み合わせを生成します。その各組み合わせによって、相関ルール候補の IF 部分と THEN 部分が決まります。最小限の信頼度 (ルールが真になる頻出項目セットの割合) を満たす相関ルール候補に、適切な (信頼度の高い) ルールとしてラベルを付け保存します。
プログラムの全体構造
デモ プログラムの作成には、Visual Studio を使用しました。デモ プログラムには .NET との大きな依存関係はないため、Microsoft .NET Framework 2.0 以降をサポートするすべてのバージョンの Visual Studio で適切に動作します。C# コンソール アプリケーション プログラムを作成し、「AssocRuleLearn」という名前を付けます。テンプレートが生成したコードがエディターに読み込まれたら、Program.cs の名前を内容がわかりやすいようにソリューション エクスプローラーで 「AssocRuleProgram.cs」に変更します。これにより、Visual Studio が自動的に Program クラスの名前を変更します。ソース コードの先頭にある不要な名前空間への参照をすべて削除し、System と Collections.Generic への参照のみを残します。
プログラムの全体構造を図 3 に示します。スペース節約するため少し編集し、WriteLine ステートメントをいくつか削除しています。
図 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 型の配列として定義し、取引のリストはハードコーディングしています。実際には、プログラム定義の ItemSet クラスを作成することになります。ほとんどの場合、取引データそのものをテキスト ファイルや SQL データベースに保存し、コード化する必要があります。デモでは、頻出項目セットもハードコーディングしています。ごく小さなデモ シナリオ以外では、頻出項目セットをプログラムで抜き出す必要があります。これは、非常に難しい作業です。
信頼度の高いルールを見つけるすべての作業は、GetHighConfRules メソッドで実行します。このメソッドには、ユーザーが指定する最小信頼度の割合を表すパラメーター値が必要です。適切な信頼度は問題によって異なります。
デモ プログラムでは、プログラム定義の Rule クラスを使用します。クラス メンバーは、ルールの前提部 (IF 部分)、ルールの結論部 (THEN 部分)、および算出した信頼度です。クラスには、コンストラクターと、デモ データを適切に書式設定する ToString メソッドしかありません。
GetHighConfRules メソッドは、いくつかヘルパー メソッドを呼び出します。CountInTrans メソッドは、取引リストに出現する項目セットや、ルールの前提部または結論部の数を集計します。このヘルパー メソッドは IsSubsetOf サブヘルパー メソッドを呼び出し、IsSubsetOf は IndexOf サブヘルパー メソッドを呼び出します。NewCombination メソッドは、数学的組み合わせを作成します。NextCombination メソッドは、ある組み合わせの次の組み合わせ要素を返します。MakeAntecedent メソッドと MakeConsequent メソッドは、頻出項目セットと数学的組み合わせを使って、相関ルール候補の IF 部分と THEN 部分を返します。
数学的組み合わせ
図 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 は、組み合わせのサイズを決めます。新しい組み合わせは、値 0 から k-1 の順番になります。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) になります。
ルールの前提部と結論部の生成
MakeAntecedent ヘルパー メソッドは、頻出項目セットと数学的組み合わせを受け取り、相関ルール候補の IF 部分を返します。たとえば、頻出項目セットが (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;
}
短いコードですが、整数は組み合わせの要素値、項目セットの項目値、および項目セットのインデックス値を表すため、少しわかりにくいかもしれません。1 つか 2 つの例を自分でトレースしてみると、メソッドの動作方法がわかります。
MakeConsequent メソッドは、相関ルール候補の THEN 部分を生成します。たとえば、頻出項目セットが (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;
}
ここでは、MakeAntecedent メソッドと同じパラメーターを受け取るように MakeConsequent を設計しました。非対称にはなりますが、MakeConsequent を項目セットと前提部を受け取るように定義するという、もう少しシンプルな方法もあります。
取引出現数の集計
重要なヘルパー メソッドである CountInTrans は、頻出項目セットまたは相関ルール候補の前提部、取引リスト、および Dictionary コレクションを表す int 型の配列を受け取り、項目セットまたは前提部の出現回数を返します。Dictionary オブジェクトには項目セットと前提部の集計を格納し、処理済みの項目セットや前提部を再集計しなくてもよいように参照として使用します。
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 にリストします。図 5 にリストした GetHighConfRules メソッドをそのまま使用することもできます。ただし、パフォーマンスや、通常はメモリ消費量やコードの明瞭さを改良する多くの余地があります。たとえば、図 2 を見ると、それぞれの相関ルール候補について、前提部と結論部を交換しただけの別の候補があるのがわかります。たとえば、項目セットが (2 5 7 9) の場合、サブセット サイズ k = 2 の相関ルール候補の 1 つは IF (2 7) THEN (5 9) で、もう 1 つの候補は IF (5 9) THEN (2 7) です。そこで、頻出項目セットのサブセット サイズすべての値に対して前提部を計算するのではなく、サブセット サイズの半数だけに対して前提部と結論部を計算できます。
図 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 メソッドは保存した集計の参照辞書を使用します。これは、異なる頻出項目セットが同じ前提部を生成する場合があるため、前提部の出現を集計する際に役立ちます。しかし、頻出項目セットを一意にすれば、参照辞書の確認は時間の無駄です。Dictionary パラメーターには使用と更新の 2 つの目的があるため、それを明示するために参照パラメーターとして定義する必要があります。GetHighConfRules メソッドをよく見ると、いくつか別の方法にコードを変更できることがわかります。
一例を挙げると、所定の項目セットで、ある相関ルール候補が信頼度の最小しきい値を満たさない場合、同じ結論部を持つすべての候補が信頼度のしきい値を満たさないという性質を利用すれば、著しく効率が向上します。たとえば、IF (2 4 8 9) THEN (3 5) というルールが最小信頼度を満たさないとします。この場合、結論部に (3 5) を持つすべてのルール (IF (4 8 9) THEN (2 3 5) など) も、最小信頼度を満たさないことになります。
まとめ
今回のコラムの相関ルールについての説明とデモ コードは、信頼度の高い相関ルールの抜き出しを検討する場合や、スタンドアロン相関ルール ユーティリティ プログラムの作成、またはソフトウェア アプリケーション プログラムへの相関ルール機能の追加が必要なときに役に立ちます。
予測を目的としたいくつかの機械学習テクニックとは異なり、相関ルール学習は興味深く、役に立つ項目間の関係を明らかにすることを目的とした探索的手法です。つまり、相関ルールを見つけるにはいくらか試行錯誤が必要になります。
相関ルール学習については、たくさんの研究書籍があります。理論に関心がおありなら、P. Tan, M. Steinbach と V. Kumar の共著『Ｉntroduction to Data Mining』(Addison-Wesley、2005 年) の第 6 章をお勧めします。第 6 章の PDF ファイルは無料で入手できます (bit.ly/1m3dbZ9、英語)。
James McCaffrey 博士は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。McCaffrey 博士の連絡先は、jammc@microsoft.com (英語のみ) です。
この記事のレビューに協力してくれた技術スタッフの Richard Hughes と Kirk Olynik に心より感謝いたします。