Apriori-Algorithmus

Einfache Sprache

Im Kontext der Assoziationsanalyse ist das Ziel des Apriori-Algorithmus die Menge aller frequenten Itemsets zu finden. Bei löst der Apriori-Algorithmus das Problem mit hilfe von Dynamische Programmierung, indem die Apriori Eigenschaft ausgenutzt wird.

	\begin{algorithm}
	\caption{Apriori-Algorithmus}
	\begin{algorithmic}
	\Input $\textrm{Datenbasis } \mathcal D,\textrm{Minimal-Support } minsupp$
    \Procedure{Apriori-Gen}{$L,k$}
	\State $r\gets \emptyset$
	\Comment{$p$ and $q$ differ in exactly one element.}
	\ForAll{$p,q\in \{p,q\in L: |p\cap q| = k-2\}$}
		\State $a \gets p \cup q$
		\If{$\forall u\subseteq a \land |u| = k-1 : u\in L$}
	        \State $r\gets r\cup a$
        \EndIf
    \EndFor
    \return r
    \EndProcedure
    \Procedure{Apriori}{$\mathcal D,minsupp$}
    \State $L_1 \gets \{X\in\mathcal I\mid|X|=1 \land \textrm{support}(X)\geq s\}$
	\State $k \gets 2$
	\While{$L_{k-1}\not=\emptyset$}
		\State $C_k \gets$ \Call{Apriori-Gen}{$L_{k-1},k$}
		\State\Comment{Berechne den tatsächlichen Support der Itemsets.}
		\ForAll{$t\in\mathcal D$}
			\State $D_t \gets \{c\in C_k\mid c\subseteq t\}$
			\ForAll{$c\in D_t$}
				\State count[$c$] $\gets$ count[$c$] $+1$
            \EndFor
        \EndFor
        \State\Comment{Filter Itemsets mit zu niedrigem Support aus.}
        \State $L_k \gets \{c\in C_k\mid\textrm{count}[c]\geq minsupp\}$
        \State $k\gets k+1$
    \EndWhile
    \Return $\bigcup_{i=1}^{k+1}L_i$
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}