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

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

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

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

\subsubsection*{Aufgabe 32 \quad\rm Statistische Signifikanz}

Wir betrachten eine Transaktionsdatenbank mit 1000 Transaktionen "uber
100 Items. Nehmen Sie an, da"s jedes Item mit Wahrscheinlichkeit~0.05
in einer Transaktion auftritt, so da"s jedes Item im Durchschnitt in
50~Transaktionen enthalten ist. Weiter seien die Transaktionen
unabh"angig und die Items m"ogen unabh"angig von einander in ihnen
auftreten, d.h., die Wahrscheinlichkeit des gemeinsamen Auftretens
einer Menge von Items kann berechnet werden als Produkt der
Wahrscheinlichkeiten des einzelnen Auftretens der Items.
\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Mit welcher Wahrscheinlichkeit treten die Items mit den Nummern
     7, 16, 42 und 78 in {\em genau\/} vier Transaktionen zusammen
     auf?
\item[b)\hfill]
     Mit welcher Wahrscheinlichkeit treten die Items mit den Nummern
     7, 16, 42 und 78 in {\em mindestens\/} vier Transaktionen zusammen
     auf?
\item[c)\hfill]
     Wenn man die Wahrscheinlichkeit berechnen m"ochte, mit der
     irgendeine Menge mit vier Items ({\em nicht\/} eine bestimmte
     Menge wie in a) und b), sondern eine beliebige Menge mit vier
     Items) in mindestens vier Transaktionen zusammen auftritt, wie
     k"onnte man ansetzen? Wo liegen die wesentlichen Probleme?
     Warum ist eine direkte Erweiterung des Ergebnisses aus b) eine
     "Ubersch"atzung?
\end{enumerate}

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

\subsubsection*{Aufgabe 33 \quad\rm
                Surrogatdaten und Mustersignaturen}

Um die statistische Signifikanz von gefundenen Itemmengen zu bestimmen,
kann man einen auf Surrogat(transaktions)daten und Mustersignaturen
basierenden Ansatz verwenden
\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was ist ein Surrogatdatensatz? Wie k"onnte man einen
     Surrogatdatensatz aus einer gegebenen Transaktionsdatenbank
     erzeugen? Was repr"asentieren Surrogatdatens"atze?
\item[b)\hfill]
     Welche Eigenschaften des Originaldatensatzs sollten beim
     Erzeugen von Surrogatdatens"atzen erhalten werden?
\item[c)\hfill]
     Wie viele Surrogatdatens"atze sollte man erzeugen?
     Ist einer genug? Sind zehn genug? Sind 1000 genug?
     Gibt es eine allgemein richtige Anzahl?
\item[d)\hfill]
     Was ist eine Mustersignatur? Warum ist es besser, Mustersignaturen
     zu betrachten statt konkreter Muster?
\item[e)\hfill]
     Wie werden gefundene Itemmengen mit Hilfe von Surrogatdatens"atzen
     gefiltert? \\
     Liefert dieses Filtern nur relevante Muster?
\end{enumerate}

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

\subsubsection*{Aufgabe 34 \quad\rm Assoziationsregeln}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Was sind Assoziationsregeln?
     Mit welchen Ma\3en werden sie bewertet? \\
     Was ist der Support einer Assoziationsregel
     (zwei Versionen)? \\
     Was ist die Konfidenz einer Assoziationsregel?
\item[b)\hfill]
     Wie werden Assoziationsregeln induziert?
     Welche Schritte werden ben"otigt? \\
     Wie verh"alt sich die Induktion von Assoziationsregeln
     zum Finden h"aufiger Itemmengen?
\item[c)\hfill]
     Mit welchem minimalen Support m"ussen h"aufige Itemmengen
     in der Assoziationsregelinduktion gefunden werden?
     Ist es der minimale Support der Assoziationsregeln?
     Oder h"angt es von der Wahl der Definition des Regelsupports ab?
     Wenn ja, wie?
\item[d)\hfill]
     Welche Beziehung besteht zwischen den Konfidenzen verschiedener
     Assoziationsregeln, die aus der gleichen Itemmenge gebildet werden?
     Wie kann diese Beziehung bei der Erzeugung von Assoziationsregeln
     ausgenutzt werden?
\end{enumerate}

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

\subsubsection*{Aufgabe 35 \quad\rm Assoziationsregeln}

\begin{enumerate}\itemsep0pt
\item[a)\hfill]
     Sind die beiden Definitionen des Regelsupports "aquivalent? D.h.,
     gibt es eine Transaformation, die man auf den verwendeten minimalen
     Support anwenden kann, so da"s die gleichen Regeln gefunden werden?
     Begr"unden Sie Ihre Antwort!
\item[a)\hfill]
     Mit welchen anderen Ma\3en, au\3er dem minimalen Support und der
     minimalen Konfidenz, kann man Assoziationsregeln bewerten?
     Aus welchen Gr"o\3en werden diese Ma\3e gew"ohnlich berechnet?
\item[b)\hfill]
     Was ist der {\em lift (value)\/} einer
     Assoziationsregel und wie ist er definiert? \\
     Was ist der Informationsgewinn einer Assoziationsregel? \\
     Was ist das $\chi^2$-Ma\3 einer Assoziationsregel?
\item[c)\hfill]
     Sind Assoziationsregeln mit mehr als einem Item in Konsequens
     n"utzlich? \\ Welche zus"atzliche Information enthalten sie?
\end{enumerate}

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

\end{document}
