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

\begin{document}

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

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

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

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

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

\subsubsection*{Aufgabe 25 \quad\rm Carpenter-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie nutzt der Carpenter-Algorithmus die alternative
     Charakterisierung geschlossener Item-Mengen aus (d.h., diejenige,
     die auf einem Abschlu"soperator basiert)? Was ist das Kernproblem
     dieser Charakterisierung? (Hinweis: minimaler Support)
\end{enumerate}\unskip\vskip-1ex
\parbox{134mm}{\begin{enumerate}\itemsep0pt
\item[b)\hfill]
     Welche Datenstruktur benutzt der Carpenter-Algorithmus? \\
     K"onnte er auch eine horizontale Transaktionsdarstellung nutzen? \\
     Woran k"onnte es liegen, das er so meist {\em nicht\/}
     implementiert wird?
\item[c)\hfill]
     \parbox[t]{126mm}{F"uhren Sie den Carpenter-Algorithm f"ur die
     rechts gezeigte Transaktionsdatenbank aus! Verwenden Sie eine
     einfache Menge zum Speichern der Item-Mengen, nicht, wie in der
     Vorlesung, einen Pr"afixbaum!}
\end{enumerate}\unskip}\hfill
     \begin{tabular}{@{}l@{}}
     \\
     $a$ $d$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $c$ $e$ \\
     $b$ $c$ $d$ \\
     $a$ $e$ \\
     \end{tabular}
\begin{enumerate}\itemsep0pt
\item[d)\hfill]
     Wie kann man die Carpenter-Suche mit dem minimalen
     Support stutzen?
\end{enumerate}

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

\subsubsection*{Aufgabe 26 \quad\rm Carpenter-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Kann Stutzen mit perfekten Erweiterungen im Carpenter-Algorithmus
     verwendet werden? Wenn ja, wie?
     Wie ist dies analog zum Stutzen mit perfekten
     Erweiterungen in Item-Mengen-Aufz"ahlungsalgorithmen
     (wie Eclat, FP-Growth etc.)?
\item[b)\hfill]
     Kann man den Carpenter-Algorithmus benutzen, um die
     maximalen (h"aufigen) Item-Mengen zu finden?
\item[c)\hfill]
     K"onnte man den Carpenter-Algorithm verwenden, um
     {\em alle\/} h"aufigen Item-Mengen zu finden?
\item[d)\hfill]
     Warum ist der Carpenter-Algorithmus f"ur die Warenkorbanalyse
     nicht empfehlenswert?
     F"ur welche Art von Daten ist er empfehlenswert? Warum? \\
     (Hinweis: Zeitkomplexit"aten in den Parametern der Datenbank.)
\end{enumerate}

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

\subsubsection*{Aufgabe 27 \quad\rm IsTa-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Welche rekursive Beziehung nutzt der IsTa-Algorithmus aus,
     um geschlossene Item-Mengen zu finden? Wo liegt die Komplexit"at?
\item[b)\hfill]
     Nehmen wir an, der IsTa-Algorithmus hat Arbeit beendet und der
     wir haben daher den fertigen Pr"afixbaum der gefundenen
     geschlossenen h"aufigen Item-Mengen vorliegen. Wie
     werden diese geschlossenen h"aufigen Item-Mengen aus diesem
     Pr"afixbaum ausgegeben? Welche Bedingungen m"ussen beim Durchlaufen
     des Pr"afixbaumes gepr"uft werden?
\item[c)\hfill]
     Wie k"onnte man aus diesem Pr"afixbaum heraus die
     {\em maximalen\/} Itemmengen ausgeben?
     Welche Bedingungen m"ussen in diesem Fall
     gepr"uft werden?
\item[d)\hfill]
     Warum ist der IsTa-Algorithmus f"ur die Warenkorbanalyse
     nicht empfehlenswert? \\
     F"ur welche Art von Daten ist er empfehlenswert? Warum? \\
     (Hinweis: Zeitkomplexit"aten in den Parametern der Datenbank.)
\end{enumerate}

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

\end{document}
