ocaml implementation of apriori algorithm

apriori.ml

let cmp = Pervasives.compare 

(* search : 'a list -> 'a list -> bool *)
(* trans 中の ptn 出現を探索 *)
let rec search ptn trans =
  match ptn with
    [] -> true
  | head :: tail ->
     List.mem head trans && search tail trans

(* search_set : 'a list -> 'a list list -> int *)
(* transset 中の ptn 出現を探索 *)
let rec search_set transset ptn =
  match transset with
    [] -> 0
  | head :: tail ->
     if search ptn head
     then 1 + search_set tail ptn
     else search_set tail ptn

(* f_search : 'a list list -> 'a list list -> int list *)
(* transset 中の各 ptn (ptn \in ptns) 出現を探索 *)
let rec f_search ptns transset =
  List.map (search_set transset) ptns
       
(* union : 'a list -> 'a list -> 'a list *)
(* 2 つの集合の整列リストから和集合を作成 *)
let union lst1 lst2 =
  List.merge cmp lst1
    (List.sort cmp
       (List.filter (fun x -> not (List.mem x lst1)) lst2))
    
(* unions : 'a list list -> 'a list *)
let rec unions lstoflst =
  match lstoflst with
    [] -> []
  | head :: tail ->
     List.sort cmp (List.rev_map (union head) tail)
     :: unions tail
       
(* set_of_list : 'a list -> 'a list *)
(* 重複を除く *)
let rec set_of_list lst =
  match lst with
    [] -> []
  | head :: tail when List.mem head tail -> set_of_list tail
  | head :: tail -> head :: set_of_list tail

(* make_ptn : 'a list list -> int -> 'a list list *)
(* 長さ n の探索リスト(pattern)を作成 *)
let rec make_ptn freq n =
  let lst =
    List.filter (fun l -> n = List.length l) (List.concat (unions freq)) in
  set_of_list lst

(* f : string list list -> int -> string list list *)
(* apriori の中身 *)
let rec f n len items trans result =
  (* ptnlst : string list list *)
  let ptnlst = match len with
      1 -> items
    | _ -> make_ptn result len
 in
  let intlst = f_search ptnlst trans in
  let ocrlst = List.combine intlst ptnlst in
  let res = snd (List.split (List.filter (fun (a,b) -> a >= n) ocrlst)) in
  match res with
    [] -> []
  | _  -> res :: (f n (len+1) items trans res)

(* usage : apriori freqency itemset transaction(table) *)
let apriori n items trans =
  List.concat (f n 1 items trans [])
	 
let t1 = ["きゅうり"; "トマト"; "水菜"]
let t2 = ["きゅうり"; "トマト"; "レタス"]
let t3 = ["水菜"]
let t4 = ["きゅうり"; "トマト"]
let t5 = ["トマト"; "水菜"]
let t6 = ["きゅうり"; "トマト"; "水菜"; "レタス"]
let t7 = ["きゅうり"; "水菜"; "レタス"]
let t8 = ["トマト"]
let table = [t1; t2; t3; t4; t5; t6; t7; t8;]
let itemset = [["きゅうり"]; ["トマト"]; ["水菜"]; ["レタス"]]	 
let test1 = apriori 4 itemset table = [["きゅうり"]; ["トマト"]; ["水菜"]; ["きゅうり"; "トマト"]]