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

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

\vskip3ex
\centerline{\bf Exercise Sheet 4}

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

\subsubsection*{Exercise 14 \quad\rm Eclat Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{100mm}{Execute the Eclat algorithm
     (using the prefix tree scheme)
     for the transaction database shown on the right
     and a minimum support of $s_{\min} = 3$!}\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[b)\hfill]
     How is support counted in the Eclat algorithm? \\
     How does this scheme differ from the scheme used in Apriori? \\
     What are the advantages/disadvantages of this counting scheme?
\item[c)\hfill]
     Why does Eclat (usually) not exploit the Apriori property fully? \\
     How could it be made to exploit the Apriori property fully?
\item[d)\hfill]
     Why is it advantageous in the Eclat algorithm
     to process less frequent items first? \\
     (Hint: Consider the average length of the
     transaction identifier lists.)
\end{enumerate}

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

\subsubsection*{Exercise 15 \quad\rm Eclat Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Why is a bit vector representation of the transaction identifier
     lists not necessarily better than an explicit list of transaction
     identifiers? (Hint: What happens to the transaction identifier
     lists in the recursive processing?)
\item[b)\hfill]
     In the conditional transaction databases occurring in the
     search for frequent item sets, it is often possible to combine
     transactions that have become equal after some items have been
     eliminated. How can this be exploited in the Eclat algorithm?
\item[c)\hfill]
     Show that the diffset for an item (w.r.t.\ some conditional
     database), that is, $D(a \mid I) = K(I) - K(I \cup \{a\})$,
     can be both larger and smaller than its cover
     (depending on the database).
\end{enumerate}

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

\subsubsection*{Exercise 16 \quad\rm Item Order}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How can one exploit a local item order in the Apriori algorithm?
\item[b)\hfill]
     How can one exploit a local item order in the Eclat algorithm? \\
     Why is it particularly easy to use a local item order in it?
\item[c)\hfill]
     How can one exploit the order in which a divide-and-conquer scheme
     visits the item sets to optimize the reporting of found frequent
     item sets? \\ Does this also work for a local item order? Why?
\end{enumerate}

%-----------------------------------------------------------------------
\newpage

\subsubsection*{Exercise 17 \quad\rm LCM Algorithm}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     How does the occurrence deliver scheme of LCM work? \\
     How is it related to the Eclat algorithm? How is it different? \\
     What additional data/information is needed for the LCM algorithm
     (compared to Eclat)?
\item[b)\hfill]
     Why does LCM allow mining with memory proportional to the
     database size and Eclat does not, even though their
     processing schemes are similar? \\
     (Hint: Consider the order in which the subproblems are processed.)
\item[c)\hfill]
     \parbox[t]{100mm}{Execute the LCM algorithm
     for the transaction database shown on the right
     and a minimum support of $s_{\min} = 3$!}\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}
\end{enumerate}

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

\end{document}
