頻出アイテムセット間のJaccard係数の計算

Jaccard係数(Jaccard index, Jaccard similarity coefficent)は,2つの集合間の類似性を表す指標.

パターンマイニングでは,2つの頻出パターンの共起を表す指標として用いられ,両方のパターンが現れるトランザクション数に対して,少なくとも一方のパターンが現れるトランザクション数の割合として定義される.すなわち,パターン p_{1}, p_{2}に対して,Jaccard係数 Jは,


 J=J(p_{1}, p_{2})=\frac{||T(p_{1}) \cap T(p_{2})||}{||T(p_{1}) \cup T(p_{2})||},

で定義される.ここで,
 T(p)はパターン pが現れたトランザクションの集合, ||S||は集合 Sの要素数を表す.

以下のテストデータを用意して,頻出パターン,特にここでは頻出アイテムセットに対するJaccard係数を算出してみよう.

test.dat

a b c
a d e
b c d
a b c d
b c
a b d
d e
a b c d
c d e
a b c

頻出アイテムセットの抽出

上記のデータに対してアソシエーションルールを実行して頻出アイテムセットを抽出する.ここでは,Christian Borgelt先生が公開されているパターンマイニングのアルゴリズムの実行ファイルからFP-Growthを選択する.

$ # 実行ファイルの取得
$ wget http://www.borgelt.net//bin64/fpgrowth
$ # 最小アイテム数2, サポート0.3, アイテム間のセパレータ","(-k,), アイテムセットの出現指標は出現数
$ ./fpgrowth -m2 -s30 -k, -v" %n" test.dat test.out

以下の10個の頻出パターンが"test.out"に出力される.この出力されたデータは,頻出アイテムセットとその出現回数に関する情報を保持していて,例えば

  • アイテムセット {c,b} が6回出現
  • アイテムセット {d,c} が4回出現

といったことが分かる.

test.out

c,b 6
d,c 4
d,b,c 3
d,b 4
a,b 5
a,d,b 3
a,d 4
a,c,b 4
a,c 4
e,d 3

Jaccard係数の算出

続いて,Jaccard係数を算出する.main関数を見れば分かるように,処理は大きく4つのステップ

  1. トランザクションデータの読み込み
  2. 頻出アイテムセットの読み込み
  3. 頻出アイテムセットとトランザクションデータのマッチング → 各アイテムセットが含まれるトランザクション番号の抽出
  4. アイテムセット間のJaccard係数の算出

からなる.

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <iterator>
#include <boost/tokenizer.hpp>
#include <boost/algorithm/string/join.hpp>

using namespace std;

// コンテナの定義
typedef vector<string> Tran; // トランザクション
typedef vector<Tran> TranSet; // トランザクションの集合
typedef vector<string> Pattern; // パターン
typedef vector<Pattern> PatternSet; // パターンの集合
typedef size_t tranid; // トランザクションID
typedef map<Pattern, vector<tranid>> PatTranSet; // 頻出パターンとトランザクションIDの対応

// トークナイザの設定
typedef boost::char_separator<char> char_separator; 
typedef boost::tokenizer<char_separator> tokenizer;

/**
 * @brief ファイルからトランザクションデータを読み込む
 * @param fn トランザクションデータのファイル名
 * @param trset トランザクションデータを格納するコンテナ
 */
void readTran(string fn, TranSet &trset) {
  string line; // 入力データのレコード
  Tran tr; // トランザクション
  string item; // アイテム
  ifstream ifs(fn.c_str());

  // 各トランザクションの読み込み
  while (ifs && getline(ifs, line)) {
    tr.clear();
    istringstream istrs((char *) line.c_str());
    // 各アイテムの読み込み
    while (istrs >> item) {
      // 同一のトランザクションで同一のアイテムはユニークにする
     vector<string>::iterator itr_tr;
     if (find(tr.begin(), tr.end(), item) == tr.end()) {
       tr.push_back(item);
     }
    }
    sort(tr.begin(), tr.end());
    trset.push_back(tr);
  }
}

/**
 * @brief ファイルから頻出アイテムセットを読み込む
 * @param fn 頻出アイテムセットのファイル名
 * @param patset 頻出アイテムセットを格納するコンテナ
 * @param sep_pat 頻出アイテムセットとその他の情報のセパレータ(頻出アイテムセットの位置が第1フィールドであることが前提)
 * @param sep_item 頻出アイテムセットのアイテム間のセパレータ
 */
void readPattern(string fn, PatternSet &patset, 
                 string sep_pat=" ", string sep_item=",") {
  string line; // 入力データのレコード
  Pattern pat; // 頻出アイテムセット
  string item; // アイテム
  ifstream ifs(fn.c_str());

  char_separator separator(sep_pat.c_str(), "", boost::keep_empty_tokens);

  // 各アイテムセットの読み込み
  while (ifs && getline(ifs, line)) {
    pat.clear();
    // 各アイテムへの分割と格納
    tokenizer tokens(line, separator);
    string str = *tokens.begin();
    istringstream istrs((char *) str.c_str());
    while (std::getline(istrs, item, ',')) {
       pat.push_back(item);
    }
    sort(pat.begin(), pat.end());
    patset.push_back(pat);
  }
}

/**
 * @brief 一方のベクタが他方のベクタの部分集合になっているかについて調べる(a is a subset of b)
 * @param a 他方のベクタからの被包含を調べる対象のベクタ
 * @param b 他方のベクタの包含を調べる対象のベクタ
 */
template <typename T>
bool isSubset(vector<T> a, vector<T> b)
{
  return includes(b.begin(), b.end(), a.begin(), a.end());
}

/**
 * @brief 頻出アイテムセットとトランザクションデータをマッチングして,各アイテムセットが含まれるトランザクション番号を抽出する
 * @param ps 頻出アイテムセットを格納するコンテナ
 * @param ts トランザクションを格納するコンテナ
 * @param pts 頻出アイテムセットが含まれるトランザクション番号を格納するコンテナ
 */
void patmatch(PatternSet& ps, TranSet& ts, PatTranSet & pts)
{
  // 各アイテムセットに対するトランザクションデータとのマッチング
  PatternSet::iterator ps_itr = ps.begin(); 
  while (ps_itr != ps.end()) {
    tranid tn = 1; // トランザクション番号(1からの連番)
    vector<tranid> tn_set; // トランザクション番号を格納するコンテナ
    // 各トランザクションとのマッチング
    TranSet::iterator tr_itr = ts.begin();
    while (tr_itr != ts.end()) {
      bool matched = isSubset(*tr_itr, *ps_itr);
      // マッチした場合はトランザクション番号を格納する
      if (matched) {
        tn_set.push_back(tn);
      }
      tr_itr++;
      ln++;
    }
    pts.insert(map<Pattern, vector<tranid>>::value_type(*ps_itr, ln_set));
    ps_itr++;
  }
}

/**
 * @brief 2つの頻出アイテムセット間のjaccard係数を算出する
 * @param p1 頻出アイテムセット
 * @param p2 頻出アイテムセット
 */
double jaccard(const Pattern &p1, const Pattern &p2)
{
  // アイテムセットの共通集合を求める
  Pattern intersec;
  set_intersection(p1.begin(), p1.end(), p2.begin(), p2.end(), 
                    back_inserter(intersec));

  // Jaccard係数を算出する
  int size_intersec = intersec.size();
  int size_union = p1.size() + p2.size() - size_intersec;

  return (double)size_intersec/size_union;
} 

/**
 * @brief 与えられた全ての頻出アイテムセット間のJaccard係数を算出する
 * @param pts 各頻出アイテムセットのトランザクション番号を保持したコンテナ
 */
void jaccard_all(const PatTranSet &pts)
{
  // 各頻出アイテムセットに対して他のアイテムセットとのJaccard係数を算出する
  PatTranSet::const_iterator itr1 = pts.begin();
  while (itr1 != pts.end()) {
    Pattern pat1 = itr1->first;
    string p1 = "{" + boost::algorithm::join(pat1, ",") + "}";
    // Jaccard係数を算出する対象のアイテムセットを抽出する
    PatTranSet::const_iterator itr2 = ++pts.begin();
    while (itr1 != itr2 && itr2 != pts.end()) {
      Pattern pat2 = itr2->first;
      string p2 = "{" + boost::algorithm::join(pat2, ",") + "}";
      // Jaccard係数を算出する
      cout << " Jaccard(" << p1 << "," << p2 << ") = " <<
              jaccard(pat1, pat2) << endl;
      itr2++;
    }
    itr1++;
  }
}

int main()
{
  // 1. トランザクションデータの読み込み
  string fn_tran="test.dat";
  TranSet trset;
cout << "Reading transaction: " << fn_tran << endl;
  readTran(fn_tran, trset);

  // 2. 頻出アイテムセットの読み込み
  string fn_pat="test.out";
  string sep_pat=" ";
  string sep_item=",";
  PatternSet patset;
cout << "Reading frequnet itemset: " << fn_pat << endl;
  readPattern(fn_pat, patset, sep_pat, sep_item);

  // 3. 頻出アイテムセットとトランザクションデータのマッチング
  PatTranSet pts;
cout << "Pattern matching" << endl;
  patmatch(patset, trset, pts);

  // 4. アイテムセット間のJaccard係数の算出
cout << "Calculating Jaccard coefficient" << endl;
  jaccard_all(pts);

  return 0;
}

以上のプログラムをコンパイル,実行してみよう.Boostライブラリは/usr/includeに入っているものとする.

$ g++ -Wall -std=c++11 -I /usr/include -o patsim patsim.cpp 
$ ./patsim 
Reading transaction: test.dat
Reading frequnet itemset: test.out
Pattern matching
Calculating Jaccard coefficient
 Jaccard({a,b},{a,b,c}) = 0.666667
 Jaccard({a,b},{a,b,d}) = 0.666667
 Jaccard({a,b},{a,c}) = 0.333333
 Jaccard({a,b},{a,d}) = 0.333333
 Jaccard({a,b},{b,c}) = 0.333333
 Jaccard({a,b},{b,c,d}) = 0.25
 Jaccard({a,b},{b,d}) = 0.333333
 Jaccard({a,b},{c,d}) = 0
 Jaccard({a,b},{d,e}) = 0
 Jaccard({a,b,d},{a,b,c}) = 0.5
 Jaccard({a,c},{a,b,c}) = 0.666667
 Jaccard({a,c},{a,b,d}) = 0.25
 Jaccard({a,d},{a,b,c}) = 0.25
 Jaccard({a,d},{a,b,d}) = 0.666667
 Jaccard({a,d},{a,c}) = 0.333333
 Jaccard({b,c},{a,b,c}) = 0.666667
 Jaccard({b,c},{a,b,d}) = 0.25
 Jaccard({b,c},{a,c}) = 0.333333
 Jaccard({b,c},{a,d}) = 0
 Jaccard({b,c,d},{a,b,c}) = 0.5
 Jaccard({b,c,d},{a,b,d}) = 0.5
 Jaccard({b,c,d},{a,c}) = 0.25
 Jaccard({b,c,d},{a,d}) = 0.25
 Jaccard({b,c,d},{b,c}) = 0.666667
 Jaccard({b,d},{a,b,c}) = 0.25
 Jaccard({b,d},{a,b,d}) = 0.666667
 Jaccard({b,d},{a,c}) = 0
 Jaccard({b,d},{a,d}) = 0.333333
 Jaccard({b,d},{b,c}) = 0.333333
 Jaccard({b,d},{b,c,d}) = 0.666667
 Jaccard({c,d},{a,b,c}) = 0.25
 Jaccard({c,d},{a,b,d}) = 0.25
 Jaccard({c,d},{a,c}) = 0.333333
 Jaccard({c,d},{a,d}) = 0.333333
 Jaccard({c,d},{b,c}) = 0.333333
 Jaccard({c,d},{b,c,d}) = 0.666667
 Jaccard({c,d},{b,d}) = 0.333333
 Jaccard({d,e},{a,b,c}) = 0
 Jaccard({d,e},{a,b,d}) = 0.25
 Jaccard({d,e},{a,c}) = 0
 Jaccard({d,e},{a,d}) = 0.333333
 Jaccard({d,e},{b,c}) = 0
 Jaccard({d,e},{b,c,d}) = 0.25
 Jaccard({d,e},{b,d}) = 0.333333
 Jaccard({d,e},{c,d}) = 0.333333

Jaccard係数を算出できていることが分かる.
ただし,上記のコードにはいろいろと改善の余地がある.例えば,

  • パターンマイニングを実行して頻出アイテムセットを抽出した後,改めてトランザクションデータとのマッチングを行っているため計算効率が悪い*1
  • 仮にトランザクションデータのマッチングを行う方針でも,全件マッチングとなっているため計算効率が悪い.

などである.改善方法については別途記事を書きたいところ.

*1:頻出アイテムセットを抽出した時点で,各アイテムセットが含まれるトランザクションデータは判明しているはず・・・