\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 03.05.2018

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

\vskip3ex
\centerline{\bf Exercise Sheet 2}

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

\subsubsection*{Exercise 5 \quad\rm Searching for Frequent Patterns}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What is the size of the search space
     of frequent item set mining? \\
     How does it grow with the number of items?
\item[b)\hfill]
     Why is an exhaustive search through all possible
     item sets not advisable? \\
     What is the (asymptotic) time complexity
     of an exhaustive search? \\
     Is the pruned/reduced search fundamentally more efficient? \\
     If yes, in what way? If no, why may it be useful nevertheless?
\end{enumerate}

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

\subsubsection*{Exercise 6 \quad\rm Searching for Frequent Patterns}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How many subsets of size $k-1$ does an item set
     with $k$ items have? \\
     Why is this a problem for the candidate generation?
\item[b)\hfill]
     Show why any frequent item set of size $k+1$ can be formed in
     $j = (k+1)k/2$ possible ways with the original version of the
     Apriori algorithm!
\item[c)\hfill]
     In how many ways can an {\em in\/}frequent item set
     of size $k+1$ be generated? \\
     Does this number differ from the answer for frequent item sets?
     Why?
\end{enumerate}

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

\subsubsection*{Exercise 7 \quad\rm Searching for Frequent Patterns}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What structure of the search space are we exploiting
     for the search? \\
     Why is this structure advantageous
     given the properties of support?
\item[b)\hfill]
     What is a Hasse diagram? What does it represent? \\
     For what are we using Hasse diagrams?
\item[c)\hfill]
     How is the Hasse diagram transformed to improve the search? \\
     What is the purpose of this transformation?
\item[d)\hfill]
     What do we achieve by assigning unique parent item sets? \\
     Could we also assign unique child item sets?
\item[e)\hfill]
     Are there any item sets
     that always have a unique parent item set, \\
     even in the unmodified Hasse diagram?
\end{enumerate}

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

\subsubsection*{Exercise 8 \quad\rm Searching for Frequent Patterns}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How can we actually define unique parent item sets
     (concrete method)? \\
     Are there alternatives? How do unique parents help in the search?
\item[b)\hfill]
     After assigning unique parent item sets:
     In how many ways can we generate an item set of size $k+1$
     from item sets of size~$k$?
\item[c)\hfill]
     What is the general scheme of searching with unique parents?
\end{enumerate}

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

\subsubsection*{Exercise 9 \quad\rm Canonical Form of Item Sets}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     What is a canonical form of an item set?
     How can it be defined? \\
     Is this concept actually needed for frequent item set mining? \\
     Why did we look at canonical forms for item sets anyway?
\item[b)\hfill]
     What is the prefix property?
     How is it stated (two versions)? \\
     What advantage results from the prefix property?
\item[c)\hfill]
     Describe how the recursive search for frequent patterns
     can be simplified \\
     if the chosen canonical form has the prefix property!
\item[d)\hfill]
     The prefix property is a necessary condition to ensure
     that the search by appending items to canonical code words
     is exhaustive. What is needed in addition to make it sufficient?
\item[e)\hfill]
     What is a canonical extension rule? \\
     Is there a canonical extension rule for frequent item set mining?
\end{enumerate}

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

\end{document}
