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

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

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

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

\subsubsection*{Aufgabe 14 \quad\rm Eclat-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{100mm}{F"uhren Sie den Eclat-Algorithmus
     (auf der Grundlage des Pr"afixbaum-Schemas)
     f"ur die rechts gezeigte Transaktionsdatenbank
     und einen minimalen Support von $s_{\min} = 3$ aus!}\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]
     Wie wird im Eclat-Algorithm der Support bestimmt? \\
     Wie unterscheidet sich dieses Schema von dem, das vom
     Apriori-Algorithmus benutzt wird?
     Was sind die Vor- und Nachteile dieses Z"ahlverfahrens?
\item[c)\hfill]
     Warum nutzt Eclat (normalerweise) die Apriori-Eigenschaft nicht
     vollst"andig aus?
     Wie k"onnte man die Apriori-Eigenschaft vollst"andig ausnutzen?
\item[d)\hfill]
     Warum ist es im Eclat-Algorithmus vorteilhaft, die weniger
     h"aufigen Items zuerst zu verarbeiten?
     (Hinweis: Betrachten Sie die durchschnittliche L"ange der
     Listen von Transaktionskennungen.)
\end{enumerate}

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

\subsubsection*{Aufgabe 15 \quad\rm Eclat-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Warum ist eine Bitvektor-Darstellung der Transaktionslisten
     nicht unbedingt besser als eine explizite Liste der
     Transaktionskennungen? (Hinweis: Was passiert mit den
     Listen der Transaktionskennungen in der rekursiven Verarbeitung?)
\item[b)\hfill]
     In den bedingten Datenbanken, die in der Suche nach
     h"aufigen Itemmengen auftreten, kann man oft Transaktionen
     zusammenfassen, die durch Eliminieren von Items gleich
     geworden sind. Wie kann man dies im Eclat-Algo\-rithmus ausnutzen?
\item[c)\hfill]
     Zeigen Sie, da\3 eine Differenzmenge ({\em diffset\/}) eines
     Items (bzgl.\ einer bedingten Datenbank), d.h.,
     $D(a \mid I) = K(I) - K(I \cup \{a\})$, sowohl gr"o\3er als auch
     kleiner sein kann als ihre "Uberdeckung ({\em cover\/})
     (abh"angig von der Datenbank).
\end{enumerate}

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

\subsubsection*{Aufgabe 16 \quad\rm Item-Reihenfolge}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie kann man im Apriori-Algorithmus eine lokale Item-Reihenfolge
     ausnutzen?
\item[b)\hfill]
     Wie kann man im Eclat-Algorithmus eine lokale Item-Reihenfolge
     ausnutzen? \\
     Warum ist dies in diesem Algorithmus besonders einfach?
\item[c)\hfill]
     Wie kann man die Ausgabe der gefundenen h"aufigen Itemmengen
     durch die Reihenfolge, in der die Itemmengen in einem
     Teile-und-Herrsche-Verfahren besucht werden, optimieren?
     Geht dies auch f"ur eine lokale Item-Reihenfolge? Warum?
\end{enumerate}

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

\subsubsection*{Aufgabe 17 \quad\rm LCM-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie funktioniert das Occurrence-Deliver-Schema
     des LCM-Algorithmus? \\
     Wie verh"alt es sich zum Eclat-Algorithmus?
     Wie unterscheidet es sich? \\
     Welche zus"atzlichen Informationen/Daten werden f"ur den
     LCM-Algorithmus \linebreak ben"otigt (verglichen mit Eclat)?
\item[b)\hfill]
     Warum erlaubt der LCM-Algorithmus, die Suche nach h"aufigen
     Itemmengen mit einem Speicherbedarf proportional zur Gr"o\3e
     der Transaktionsdatenbank durchzuf"uhren, w"ahrend der
     Eclat-Algorithmus dies nicht erlaubt, obwohl die
     Verarbeitungsschemata "ahnlich sind? \\
     (Hinweis: Betrachten Sie, in welcher Reihenfolge die
     Teilprobleme gel"ost werden.)
\item[c)\hfill]
     \parbox[t]{100mm}{F"uhren Sie den LCM-Algorithmus
     f"ur die rechts gezeigte Transaktionsdatenbank und einen
     minimalen Support von $s_{\min} = 3$ aus!}\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}
