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

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

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

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

\subsubsection*{Aufgabe 28 \quad\rm
                Geschlossene und maximale Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Nehmen Sie an, wir versuchten, all geschlossenen (oder alle
     maximalen) (h"aufigen) Itemmengen dadurch zu finden, da"s wir
     erst alle h"aufigen Itemmengen finden und dann das Ergebnis
     gem"a"s der definierenden Bedingungen f"ur geschlossene (oder
     maximale) Itemmengen filtern. Ist dies eine gute Idee?
     Begr"unden Sie Ihre Antwort!
\item[b)\hfill]
     Was bedeuten die Begriffe {\em Kopf\/} (``{\em head\/}''') und
     {\em Schwanz\/} (``{\em tail\/}'') eines Suchbaumknotens (oder
     eines Teilproblems)? Besteht eine Beziehung zu dem Begriff des
     {\em Pr"afix\/} eines Teilproblems?
\item[c)\hfill]
     Gegeben eine globale Itemordnung, gibt es eine (feste) Beziehung
     zwischen den Items im Kopf (head) und denen im Schwanz (tail)?
\item[d)\hfill]
     Gilt die Beziehung {\em head\/} $\cup$ {\em tail\/} ${}= B$ f"ur
     alle Suchbaumknoten? Falls nein, gibt es bestimmte Suchbaumknoten
     oder bestimmte Bedingungen, die erf"ullt sein m"ussen, damit dies
     gilt?
\end{enumerate}

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

\subsubsection*{Aufgabe 29 \quad\rm Ausgeschlossene Items}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist die Menge der {\em ausgeschlossenen Items\/}
     (``{\em excluded items\/}'') (relativ zu einem Suchbaumknoten
     oder einem Teilproblem)? Wie kann man diese Menge mit Hilfe der
     Zerlegungen in Teilprobleme charakterisieren, die wir im
     Teile-und-Herrsche-Algorithmus ausf"uhren? Was k"onnte man
     analog die Menge der {\em eingeschlossenen Items\/} nennen?
\item[b)\hfill]
     Nehmen Sie an, das Teile-und-Herrsche-Schema zum Finden h"aufiger
     Itemmengen werde mit dem Stutzen mit Hilfe perfekter Erweiterungen
     verbessert, so da"s Teilprobleme durch Tripel $S = (T,P,X)$
     beschrieben werden.
     Ist $P \cup X$ immer eine geschlossene Itemmenge?
     Ist es immer eine maximale Itemmenge? \\
     Begr"unden Sie Ihre Antwort!
\item[c)\hfill]
     Ist die folgende Aussage wahr? Wenn der Schwanz (tail) eines
     Suchbaumknotens nicht leer ist, dann ist sein Kopf eine maximale
     Itemmenge. Begr"unden Sie Ihre Antwort!
\item[d)\hfill]
     Ist die folgende Aussage wahr? Wenn der Schwanz (tail) eines
     Suchbaumknotens kein Item enth"alt, das den gleichen Support hat
     wie der Kopf (head), dann ist der Kopf eine geschlossene Itemmenge.
     Begr"unden Sie Ihre Antwort!
\end{enumerate}

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

\subsubsection*{Aufgabe 30 \quad\rm
                Geschlossene und maximale Itemmengen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Wie kann man die definierende Bedingung geschlossner Itemmengen
     mit Hilfe einer {\em horizontalen\/} Transaktionsdarstellung
     pr"ufen?
\item[b)\hfill]
     Wie kann man die definierende Bedingung geschlossner Itemmengen
     mit Hilfe einer {\em vertikalen\/} Transaktionsdarstellung
     pr"ufen?
\item[c)\hfill]
     Worin besteht eine Alternative zum Pr"ufen der definierenden
     Bedingung? Wie wird die Pr"ufung in diesem alternativen Ansatz
     ausgef"uhrt?
     Welche M"oglichkeiten gibt es (z.B.\ an Datenstrukturen), um
     diese Alternative zu implementieren?
\end{enumerate}

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

\subsubsection*{Aufgabe 31 \quad\rm
                Geschlossene und maximale Itemmengen: Stutzen}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     In den vorangehenden Aufgaben haben wir betrachtet, wie man
     herausfinden kann, ob eine Itemmenge geschlossen (oder maximal)
     ist und damit, wie man die Ausgabe nicht geschlossener (oder
     nicht maximaler) Itemmengen vermeiden kann. Ist dieses einfache
     Filtern der einzige Vorteil? Oder kann man auch die Suche selbst
     mit Hilfe dieser Methoden vereinfachen/stutzen? Wenn ja, wie?
\item[b)\hfill]
     Wie kann ein Stutzen mit perfekten Erweiterungen bei der Suche
     nach geschlossenen Itemmengen ausgenutzt werden?
     Warum ist es sicher, da"s wir mit diesem Stutzen keine
     geschlossenen Itemmengen verlieren?
\item[c)\hfill]
     Was versteht man unter Kopf-vereinigt-Schwanz-Stutzen (``head
     union tail pruning'') f"ur die Suche nach maximalen Itemmengen
     (zwei Varianten)?
\end{enumerate}

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

\subsubsection*{Zusatzaufgabe \quad\rm Alternativen zum Support}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Finden Sie ein vom Support verschiedenes Ma"s (oder mehrere Ma"se)
     auf der teilgeordneten Menge $(2^B,\subseteq)$
     das/die anti-monoton (oder nach unten abgeschlossen) sind!
\item[b)\hfill]
     Wir definieren den {\em Tr"ager\/}~$L_T(I)$ einer Itemmenge~$I$
     bzgl.\ einer Transaktionsdatenbank~$T$ als
     \begin{eqnarray*}
     L_T(I) & = & \{ k \in \{1,\ldots,n\} \mid
                     I \cap t_k \neq \emptyset \} \\
            & = & \{ k \in \{1,\ldots,n\} \mid
                     \exists i \in I\!: i \in t_k \} \\
            & = & \textstyle \bigcup_{i \in I} K_T(\{i\}).
     \end{eqnarray*}
     Die {\em Ausdehnung\/}~$r_T(I)$ einer Itemmenge~$I$ bzgl.\ einer
     Transaktionsdatenbank~$T$ ist die Gr"o"se ihres Tr"agers, d.h.,
     $r_T(I) = |L_T(I)|$. Ist die Ausdehnung anti-monoton (oder nach
     unten abgeschlossen)? Wenn nein, welches Verhalten zeigt sie?
\item[c)\hfill]
     K"onnte man Support und Ausdehnung kombinieren, um ein besseres
     Ma"s f"ur die Assoziation von Items zu erhalten?
     (Hinweis: Schauen Sie sich das Ma"s {\em Jaccard-Index\/} an
     und "uberlegen Sie, wie es verallgemeinert werden k"onnte.)
\end{enumerate}

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

\end{document}
