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

\begin{document}

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

\noindent
{\bf Data Mining 2: Finden h"aufiger Muster} \hfill Sommer 2018 \\
Christian Borgelt \hfill ab 04.06.2018

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

\vskip3ex
\centerline{\bf 5.~"Ubungsblatt}

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

\subsubsection*{Aufgabe 18 \quad\rm SaM-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie wird im SaM-Algorithmus der Support bestimmt?
     Was mu\3 der SaM-Algo\-rithmus f"ur den Transaktionenarray
     sicherstellen, damit dies gelingt?
\item[b)\hfill]
     Was wird mit dem Merge-Schritt des SaM-Algorithmus erreicht? \\
     Warum kann der Merge-Schritt der SaM-Algorithmus ein
     Problem darstellen? \\
     (Hinweis: Was entspricht dem Merge-Schritt im Eclat-Algorithmus?)
\item[c)\hfill]
     \parbox[t]{100mm}{Bestimmen Sie die Anfangsdarstellung der
     Transaktionsdatenbank des SaM-Algorithmus f"ur die rechts
     gezeigten Transaktionen!}\hfill
     \begin{tabular}[t]{@{}l@{}}
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $a$ $c$ $d$ $e$ \\
     $a$ $e$ \\
     \end{tabular}\hskip10mm
     \begin{tabular}[t]{@{}l@{}}
     $a$ $c$ $d$ \\
     $b$ $c$ \\
     $a$ $c$ $d$ $e$ \\
     $c$ $b$ $e$ \\
     $a$ $d$ $e$ \\
     \end{tabular}
\end{enumerate}

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

\subsubsection*{Aufgabe 19 \quad\rm RElim-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie verbessert der RElim-Algorithm den SaM-Algorithm? \\
     Welches Sortierprinzip wird in SaM, welches in RElim ausgenutzt?
\item[b)\hfill]
     Wie k"onnen im RElim-Algorithmus "aquivalente Transaktionen
     (oder Transaktionssuffixe) zusammengefa"st werden?
     Wann sollte dies geschehen?
\item[c)\hfill]
     Bestimmen Sie die Anfangsdarstellung der
     Transaktionsdatenbank des RElim-Algorithmus f"ur die
     in Aufgabe~19c gezeigten Transaktionen!
\end{enumerate}

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

\subsubsection*{Aufgabe 20\quad\rm RElim-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist eine $k$-Items-Maschine?
     Warum kann sie nur f"ur wenige Items benutzt werden (kleines $k$)?
\item[b)\hfill]
     Wie ist eine $k$-Items-Maschine
     mit dem RElim-Algorithm verwandt? \\
     Worin bestehen Unterscheide und was sind die Vor- und Nachteile?
\item[c)\hfill]
     Obwohl die $k$-Items-Maschine nur f"ur wenige Items benutzt werden
     kann, ist sie f"ur das Finden h"aufiger Itemmengen h"ochst
     n"utzlich. Warum? Wie werden Items behandelt, die "uber die
     Grenze~$k$ einer $k$-Items-Maschine hinausgehen?
\end{enumerate}

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

\subsubsection*{Aufgabe 21 \quad\rm FP-growth-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist ein FP-Baum?
     Wie wird er aus einer Transaktionsdatenbank erzeugt? \\
     Wie vereinigt er eine horizontale und eine vertikale Darstellung?
\item[b)\hfill]
     Wie wird mit einem FP-Baum der Support bestimmt/gez"ahlt?
\item[c)\hfill]
     Wie wird ein FP-Baum projiziert? Was liefert die Projektion?
\item[d)\hfill]
     Wie erh"alt man im FP-growth-Algorithmus die bedingte
     Transaktionsdatenbank des zweiten Teilproblems?
\item[e)\hfill]
     \parbox[t]{100mm}{F"uhren Sie den FP-growth-Algorithmus
     f"ur die rechts gezeigte Transaktionsdatenbank und einen
     minimalen Support von $s_{\min} = 3$ aus! \\[1ex]
     Sie k"onnen die Schritte der H"aufigkeitsbestimmung der Items
     und des Umsortierens der Items in den Transaktionen nach
     H"aufigkeit weglassen (d.h.: verwenden Sie die
     alphabetische Ordnung).}\hfill
     \begin{tabular}[t]{@{}l@{}}
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $a$ $c$ $d$ $e$ \\
     $a$ $e$
     \end{tabular}\hskip10mm
     \begin{tabular}[t]{@{}l@{}}
     $a$ $c$ $d$ \\
     $b$ $c$ \\
     $a$ $c$ $d$ $e$ \\
     $b$ $c$ $e$ \\
     $a$ $d$ $e$
     \end{tabular}
\end{enumerate}

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

\end{document}
