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

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

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

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

\subsubsection*{Aufgabe 10 \quad\rm Apriori-Algorithmus}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{100mm}{F"uhren Sie den Apriori-Algorithmus
     (nach Pseudo-Kode) f"ur die rechts gezeigte Transaktionsdatenbank
     und einen minimalen Support von $s_{\min} = 3$ aus! \\[1ex]
     \hbox to0pt{\hss\hbox to1.4em{b)\hss}}%
     F"uhren Sie den Apriori-Algorithmus unter Verwendung
     eines Pr"afixbaumes zur Organisation der Z"ahler 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[c)\hfill]
     Wie wird der Support im Apriori-Algorithmus bestimmt
     (Pseudo-Kode)? \\
     Was sind die Vor- und Nachteile dieses Z"ahlschemas? \\
     Wie wird der Support bei Organisation der Z"ahler als
     Pr"afixbaum bestimmt? \\
     (Hinweis: Vergleiche Teilmengentests und Erzeugen und
     Finden von Teilmengen.)
\item[d)\hfill]
     Was sind die Vorteile der Organisation der Transaktionen
     als Pr"afixbaum? \\
     (Hinweis: Welche Redundanz kann durch diesen Ansatz
     vermieden werden?) \\[1ex]
     (Achtung: Verwechseln Sie nicht den Pr"afixbaum zur Organisation
     der Supportz"ahler mit dem Pr"afixbaum zur Darstellung der
     Transaktionen!)
\end{enumerate}

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

\subsubsection*{Aufgabe 11 \quad\rm Teile-und-Herrsche-Suche}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie kann die Suche nach h"aufigen Itemmengen als
     Teile-und-Herrsche-Verfahren beschrieben werden?
     Wie kommt man so zu einem rekursiven Suchverfahren?
\item[b)\hfill]
     Wie kann das Teile-und-Herrsche-Verfahren formal as Menge von
     Teilproblemen beschrieben werden? Wie wird jedes Teilproblem
     beschrieben?
\item[c)\hfill]
     Wie wird ein Teilproblem gel"ost? Insbesondere, wie werden
     die Elemente der Teilprobleme bestimmt, in die das
     zu l"osende Teilproblem aufgeteilt wird?
\item[d)\hfill]
     Warum sind die Transaktionsdatenbanken, die zur L"osung der
     beiden Teilprobleme ben"otigt werden, {\em keine\/} Komplemente
     voneinander?
\end{enumerate}

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

\subsubsection*{Aufgabe 12 \quad\rm Perfekte Erweiterungen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist eine perfekte Erweiterung? Wie wird sie formal definiert?
\item[b)\hfill]
     Seien $a$ und $b$ perfekte Erweiterungen einer Itemmenge~$I$ und
     sei $c \notin I$ ein weiteres Item (keine perfekte Erweiterung). \\
     Ist $a$ perfekte Erweiterung von $I \cup \{ b \}$?
     Ist $a$ perfekte Erweiterung von $I \cup \{ c \}$? \\
     Ist $b$ perfekte Erweiterung von $I \cup \{ a \}$?
     Ist $b$ perfekte Erweiterung von $I \cup \{ c \}$? \\
     Was kann man allgemein aus den Antworten auf die obigen Fragen
     ablesen?
\item[c)\hfill]
     Falls im Teile-und-Herrsche-Verfahren das Aufteilungsitem
     eine perfekte Erweiterung ist, wie verhalten sich die L"osungen
     der beiden Teilprobleme zueinander? Warum?
     (Hinweis: Vergleichen Sie die zugeh"origen
     Transaktionsdatenbanken.)
\item[d)\hfill]
     Wie kann man mit perfekten Erweiterungen das
     Teile-und-Herrsche-Suche vereinfachen?
     (Hinweis: M"ussen immer beide Teilprobleme gel"ost werden?)
\end{enumerate}

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

\subsubsection*{Aufgabe 13 \quad\rm
                Darstellung von Transaktionsdatenbanken}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Bestimmen Sie horizontale und vertikale Darstellungen der Matrix
     \begin{center}\unskip
     \begin{tabular}{rlllllll}
         &$a$&$b$&$c$&$d$&$e$&$f$&$g$\\
      1: & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
      2: & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\
      3: & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
      4: & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      5: & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
      6: & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
      7: & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
      8: & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\
      9: & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\
     10: & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
     \end{tabular}
     \end{center}\unskip
\item[b)\hfill]
     Kann man den Apriori-Algorithmus mit einer vertikalen Darstellung
     der Transktionsdatenbank ausf"uhren?
\item[c)\hfill]
     Kann man eine horizontale Darstellung der Transaktionsdatenbank
     im Teile-und-Herrsche-Verfahren zum Finden h"aufiger Itemmengen
     verwenden?
\item[d)\hfill]
     Charakterisieren Sie eine Pr"afixbaumdarstellung einer
     Transaktionsdatenbank in Begriffen horizontaler/vertikaler
     Darstellungen!
\end{enumerate}

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

\end{document}
