MinHashクラスタリング

MinHash法を使ったクラスタリング
ユーザ毎のクリックページや購入商品など，ユーザに紐付けられたデータに対して，お互いのアイテムの共通性から，ユーザをクラスタリングする手法のひとつ．
K-means法など伝統的なクラスタリングとは異なり，非常に小さい多数のクラスタに分かれやすい．
実行するごとに，乱数を発生させており，かなり異なるクラスタが作られるので，１ユーザに何通りものクラスタを与えることができる．

*****************************************************************
MinHash.sas
MinHash法によるクラスタリング
20080706 翔
*****************************************************************;

options nocenter compress=yes;

/*
行動履歴の読み込み
データは，最初の30レコードのみ
*/
data tran;
  length user $ 20;
  length item $ 20;
  input user $ item $;
cards;
U2939130 P06
U2939130 P13
U2939130 P22
U2939130 P26
U2939130 P62
U2939130 P75
U2939130 P76
U2939262 P05
U2939262 P12
U2939262 P23
U2939262 P31
U2939262 P41
U2939262 P62
U2939262 P81
U2939262 P94
U2939522 P09
U2939522 P17
U2939522 P51
U2939522 P78
U2939522 P88
U2939624 P04
U2939624 P11
U2939624 P23
U2939624 P26
U2939624 P62
U2939624 P83
U2939624 P86
U2939624 P89
U2939624 P95
U2939645 P04
;

/*
user単位にまとめておく
 */
proc sort tagsort data=tran;by user;run;



/*
item に乱数をふる
 */
proc sort nodupkey data=tran(keep=item) out=item;by item;run;

data item;set item;
  ranuni=ranuni(0);
run;

data item;
  length label $ 10;
  keep label start end fmtname type hlo;
  set item end=last;
  label=put(ranuni,10.9);
   start=item;
   end=start;
   fmtname="ranuni";
   type="c";
   output;
   if last then do;
     hlo="O";
	 label=".";
	 output;
    end;
run;

proc format library=work cntlin=item;run;


/*
MinHashを計算
 */

data cluster;set tran;by user;
  keep user minhash1 minhash2;
  retain minhash1 minhash2;
  if first.user then do;
    minhash1=.;
    minhash2=.;
  end;
  ranuni=input(put(item,ranuni.),10.9);
  if ranuni=. then;
  /* アイテムの乱数値の最小のもの２つをハッシュ値(MinHash1+2)をとする*/
  else if minhash1=. then minhash1=ranuni;
  else if ranuni<minhash1 then do;minhash2=minhash1;minhash1=ranuni;end;
  else if minhash2=. then minhash2=ranuni;
  else if ranuni<minhash2 then minhash2=ranuni;
  if last.user then output;
run;

proc print data=cluster(obs=10);run;

/*
minhash1+2 の同じユーザが同一クラスタとなる

  OBS      user      minhash1    minhash2

    1    U2939130     0.08741     0.16014
    2    U2939262     0.05792     0.05796
    3    U2939522     0.18194     0.48213
    4    U2939624     0.18710     0.22409
    5    U2939645     0.15961     0.42424
    6    U2939752     0.18194     0.63608
    7    U2939807     0.24899     0.48343
    8    U2939828     0.02459     0.05796
    9    U2939849     0.18194     0.22260
   10    U2939863     0.20073     0.54641
 */

/*
MinHash1+2によるクラスタの度数を集計
 */

proc freq data=cluster;tables minhash1*minhash2/list missing;run;


/*

                                                          累積         累積
   minhash1       minhash2      度数      パーセント      度数      パーセント
------------------------------------------------------------------------------
0.008413406    0.023739537           3        0.01             3        0.01
0.008413406    0.024594917         375        1.26           378        1.27
0.008413406     0.02649894         237        0.80           615        2.07
0.008413406    0.029261659         110        0.37           725        2.44
0.008413406    0.057917905         254        0.86           979        3.30
0.008413406    0.057961735         317        1.07          1296        4.36
0.008413406    0.058181255         392        1.32          1688        5.68
0.008413406    0.062432269          51        0.17          1739        5.85
0.008413406    0.078596963          87        0.29          1826        6.15

0.793964447    0.806899802           1        0.00         29704      100.00
 */