\documentclass[12pt,a4paper]{article}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth     155mm
\topmargin     -15mm
\textheight    240mm

\begin{document}

%-----------------------------------------------------------------------

\noindent
{\bf Data Mining 2: Frequent Pattern Mining} \hfill Summer 2018 \\
Christian Borgelt \hfill from 14.05.2018

%-----------------------------------------------------------------------

\vskip3ex
\centerline{\bf Exercise Sheet 3}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 10 \quad\rm Apriori Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{100mm}{Execute the Apriori algorithm
     (using the pseudo-code from the slides)
     for the transaction database shown on the right
     and a minimum support of $s_{\min} = 3$! \\[1ex]
     \hbox to0pt{\hss\hbox to1.4em{b)\hss}}%
     Execute the Apriori algorithm again, using the
     organization of the counters as a prefix tree!}\hfill
     \begin{tabular}[t]{@{}l@{}}
     $a$ $d$ $f$ \\
     $a$ $c$ $d$ $e$ \\
     $b$ $d$ \\
     $b$ $c$ $d$ \\
     $b$ $c$
     \end{tabular}\hskip10mm
     \begin{tabular}[t]{@{}l@{}}
     $a$ $b$ $d$ \\
     $b$ $d$ $e$ \\
     $b$ $c$ $e$ $g$ \\
     $c$ $d$ $f$ \\
     $a$ $b$ $d$
     \end{tabular}
\item[c)\hfill]
     How is support counted in the (pseudo-code) Apriori algorithm? \\
     What are the advantages/disadvantages of this counting scheme? \\
     How is it counted if the support counters are organized
     as a prefix tree? \\
     (Hint: Consider subset tests versus generating
     and finding subsets.)
\item[d)\hfill]
     What are the advantages of organizing
     the transactions as a prefix tree? \\
     (Hint: What redundant work can be avoided by this scheme?) \\[1ex]
     (Attention: Do not confuse the prefix tree for organizing the
     support counters with the prefix tree that is used to represent
     the transaction database!)
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 11 \quad\rm Divide-and-Conquer Search}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How can the search for frequent item sets be described
     as a divide-and-conquer algorithm? How does this give rise
     to a recursive search scheme?
\item[b)\hfill]
     How can the divide-and-conquer scheme be described formally
     as a set of subproblems? How is each subproblem described?
\item[c)\hfill]
     How is a subproblem processed? Especially, how are the elements
     of the subproblems it is split into derived from the subproblem
     that is processed?
\item[d)\hfill]
     Why are the two transaction databases that are needed for the
     two subproblems of a split {\em not\/} complementary?
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 12 \quad\rm Perfect Extensions}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What is a perfect extension? How is it defined formally?
\item[b)\hfill]
     Let $a$ and $b$ be perfect extensions of an item set~$I$ and
     let $c \notin I$ be some other item (not a perfect extension). \\
     Is $a$ a perfect extension of $I \cup \{ b \}$?
     Is $a$ a perfect extension of $I \cup \{ c \}$? \\
     Is $b$ a perfect extension of $I \cup \{ a \}$?
     Is $b$ a perfect extension of $I \cup \{ c \}$? \\
     What can be seen generally from the answers to the above questions?
\item[c)\hfill]
     If in the divide-and-conquer scheme the split item is a perfect
     extension, how are the solutions of the two subproblems related
     to each other? Why are they related in this way?
     (Hint: Consider the respective transaction databases.)
\item[d)\hfill]
     Based on this insight, how can perfect extensions be used
     to simplify the divide-and-conquer search?
     (Hint: Does one always have to solve both subproblems?)
\end{enumerate}

%-----------------------------------------------------------------------

\subsubsection*{Exercise 13 \quad\rm
                Transaction Database Representation}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Construct horizontal and vertical representations of the matrix
     \begin{center}\unskip
     \begin{tabular}{rlllllll}
         &$a$&$b$&$c$&$d$&$e$&$f$&$g$\\
      1: & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
      2: & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\
      3: & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
      4: & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      5: & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
      6: & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
      7: & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
      8: & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\
      9: & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\
     10: & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
     \end{tabular}
     \end{center}\unskip
\item[b)\hfill]
     Can one execute the Apriori algorithm with a vertical
     transaction representation?
\item[c)\hfill]
     Can one use a horizontal transaction representation in the
     divide-and-conquer approach to frequent item set mining?
\item[d)\hfill]
     Characterize a prefix tree representation of a transaction
     database in terms of horizontal/vertical representations!
\end{enumerate}

%-----------------------------------------------------------------------

\end{document}
