egison-4.0.0: sample/generalized-sequential-pattern-mining.egi

---
--- Yu Hirate, Hayato Yamana: Generalized Sequential Pattern Mining with Item Interval, Journal of Computer Vol. 1, No 3, June 2006
---

--
-- Configuration
--

items := [a, b, c, d, e, f]

ISDB :=
  [[[(0, [a]), (86400, [a, b, c]), (259200, [a, c])]]
  ,[[(0, [a, d]), (259200, [c])]]
  ,[[(0, [a, e, f]), (172800, [a, b])]]]

N := length ISDB
minSup := ceiling (0.5 * N)

C1 := 0      -- min_interval
C2 := 172800 -- max_interval
C3 := 0      -- min_whole_interval
C4 := 300000 -- max_whole_interval

I t := floor (rtof (t / (60 * 60 * 24)))

--
-- Utils
--

query := list (integer, eq)

sequence := list (time, list eq)

time := matcher
  | interval $ $ as (integer, integer) with
    | $t -> [(I t, t)]
  | $ as something with
    | $tgt -> [tgt]


--
-- Algorithm
--

-- calculate ISDB|α
project α ISDB := match α as query with
  | (#0, $x) :: $α' -> project' α' (map (\xss -> matchAllDFS xss as set sequence with
                                                 | (_ ++ ($t, _ ++ #x :: $cs) :: $ls) :: _
                                                 -> (0, cs) :: (map (\t' xs -> (t' - t, xs)) ls))
                                        ISDB)

project' α ISDB := match α as query with
  | [] -> ISDB
  | ($a, $x) :: $α' -> project' (map (\b y -> (b - a, y))  α')
                                (map (\xss -> matchAllDFS xss as set sequence with
                                              | (_ ++ (interval #a $t, _ ++ #x :: $cs) :: $ls) :: _
                                              -> (0, cs) :: (map (\t' xs -> (t' - t, xs)) ls))
                                     ISDB)
  
-- main function
gspm items ISDB I minSup C1 C2 C3 C4 :=
  let φ := [] in
  let R := [] in
  let fs := filter (\α ISDB' -> match ISDB' as multiset sequence with
                                | loop $i (1, minSup) (![] :: ...) _ -> True
                                | _ -> False)
                   (map (\α -> (α, project α ISDB)) (map (\x -> [(0, x)]) items)) in
  let iss := map (\α ISDB' -> α) fs in
  iss ++ concat (map (\α ISDB' -> projection α ISDB' I minSup C1 C2 C3 C4) fs)

projection α ISDB' I minSup C1 C2 C3 C4 :=
  let fs := filter (\a t x -> C1 <= t && t <= C2) (freqItem ISDB' minSup C1 C2 C3 C4) in
  let iss' := map (\a t x -> α ++ [(a, x)]) fs in
  -- TODO: apply C4
  -- TODO: apply C3
  iss' ++ concat (map (\α' -> projection α' (project α' ISDB) I minSup C1 C2 C3 C4)
                      iss')

freqItem ISDB minSup C1 C2 C3 C4 :=
  matchAll ISDB as list (list sequence) with
  | first (interval $a $t) $x
      (loop $i (2, minSup)
         (first (interval #a _) #x ...)
         !(first (interval #a _) #x _))
  -> (a, t, x)

first := \pt px ps =>
  {@ ++ (@ ++ (@ ++ ((interval $t _ & ~pt), _ ++ ($x & ~px) :: _) :: _) :: _) :: @,
   (!(_ ++ (_ ++ (_ ++ (interval #t _, _ ++ #x :: _) :: _) :: _) :: _),
    !(_ ++ (_ ++ (interval #t _, _ ++ #x :: _) :: _) :: _),
    !(_ ++ (interval #t _, _ ++ #x :: _) :: _),
    ~ps)}

--
-- Execute
--

--gspm items ISDB I minSup C1 C2 C3 C4


--
-- Test
--


assertEqual "project (level 1)"
  (project [(0, a)] ISDB)
  [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]], [[(0, [d]), (259200, [c])]], [[(0, [e, f]), (172800, [a, b])], [(0, [b])]]]

assertEqual "project (level 2)"
  (project [(0, a),(0, b)] ISDB)
  [[[(0, [c]), (172800, [a, c])]], [], [[(0, [])]]]

assertEqual "project (level 2)"
  (project [(0, a),(2, a)] ISDB)
  [[[(0, [c])]], [], [[(0, [b])]]]

assertEqual "freqItem"
  (freqItem
     [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]], [[(0, [d]), (259200, [c])]], [[(0, [e, f]), (172800, [a, b])], [(0, [b])]]]
     minSup C1 C2 C3 C4)
  [(0, 0, b), (3, 259200, c), (2, 172800, a)]

(filter (\a t x -> C1 <= t && t <= C2)
  (freqItem
     [[[(0, []), (86400, [a, b, c]), (259200, [a, c])], [(0, [b, c]), (172800, [a, c])], [(0, [c])]],
      [[(0, [d]), (259200, [c])]],
      [[(0, [b])]]]
     minSup C1 C2 C3 C4))
--[(0, 0, b)]

gspm items ISDB I minSup C1 C2 C3 C4
[[(0, a)],
 [(0, b)],
 [(0, c)],
 [(0, a), (0, b)],
 [(0, a), (2, a)]]