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

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

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

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

\subsubsection*{Aufgabe 22 \quad\rm
                Maximale und geschlossene Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     \parbox[t]{100mm}{Finden Sie die h"aufigen / maximalen /
     geschlossenen Itemmengen f"ur die rechts gezeigte
     Transaktionsdatenbank und einen minimalen Support $s_{\min} = 3$
     (Sie k"onnen einen konkreten Algorithmus verwenden
     oder auch nicht):}\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]
     Finden Sie ein Beispiel einer (kleinen) Transaktionsdatenbank
     f"ur die die Anzahl der maximalen Itemmengen abnimmt, wenn der
     minimale Support verringert wird; oder erkl"aren Sie auf andere
     Weise, warum dies m"oglich ist!
\item[c)\hfill]
     Kann die Anzahl aller h"aufigen Itemmengen oder
     die Anzahl aller geschlossenen Itemmengen abnehmen, wenn der
     minimale Support verringert wird? Wenn ja, geben Sie ein Beispiel
     an! Wenn nein, zeigen Sie, warum dies nicht m"oglich ist!
\item[d)\hfill]
     Wie stehen maximale und geschlossene Itemmengen zueinander
     in Beziehung? \\
     Kann die eine Menge in Begriffen der anderen ausgedr"uckt werden?
     Welche Informationen erhalten/verlieren maximale/geschlossene
     Itemmengen? Wie?
\item[e)\hfill]
     Definieren Sie geschlossene Itemmengen in Begriffen
     perfekter Erweiterungen!
\end{enumerate}

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

\subsubsection*{Aufgabe 23 \quad\rm
                Maximale und geschlossene Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Charakterisieren Sie die Menge $M_T(1)$
     f"ur beliebige Transaktionsdatenbanken~$T$
     (d.h., g"ultig f"ur alle m"oglichen Transaktionsdatenbanken~$T$).
\item[b)\hfill]
     Angenommen, es gilt
     $\forall s_{\min}:
     F_T(s_{\min}) = C_T(s_{\min}) = M_T(s_{\min})$. \\
     Wie sieht die Transaktionsdatenbank~$T$ aus?
\item[c)\hfill]
     Angenommen, es gilt nur
     $\forall s_{\min}: C_T(s_{\min}) = M_T(s_{\min})$. \\
     Wie sieht die Transaktionsdatenbank~$T$ aus?
\item[d)\hfill]
     Angenommen, es gilt nur
     $\forall s_{\min}: C_T(s_{\min}) - \{ \emptyset \}
                     = M_T(s_{\min}) - \{ \emptyset \}$. \\
     Wie sieht die Transaktionsdatenbank~$T$ aus?
\end{enumerate}

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

\subsubsection*{Aufgabe 24 \quad\rm Finden geschlossener Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Die Menge der geschlossenen (h"aufigen) Itemmengen kann definiert
     werden als
     \[ C_T(s_{\min}) = \{ I \subseteq B \mid s_T(I) \ge s_{\min}
                          \wedge \forall J \supset I:
                          s_T(I) > s_T(J) \}. \]
     Wie kann man geschlossene Itemmengen alternativ mit Hilfe eines
     Abschlu"soperators definieren? Warum sind diese beiden Definitionen
     "aquivalent?
\item[b)\hfill]
     Wie verhalten sich geschlossene Itemmengen und geschlossene Mengen
     von Trans\-aktions\-bezeichnern/-indizes zueinander?
     Was bedeutet es f"ur eine Menge von Transaktionsbezeichnern,
     da\3 sie geschlossen ist?
\item[c)\hfill]
     Welche M"oglichkeit der Suche nach geschlossenen (h"aufigen)
     Itemmengen legt die Beziehung aus b) nahe?
\end{enumerate}

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

\end{document}
