Goal: Identify items that are bought together by sufficiently many customers. We will do so by finding dependencies among items from data collected. Our input is composed of a table of items and a table of baskets. Each basket is a list of items purchased together. Then, we use the baskets to find dependencies of the form $\{x, y, z\} \rightarrow \{v, w\}$. Definition: Support The support of a set of items $I$ is the number of baskets that contain all the items in $I$....
Tip: Vectorial product rule Let $F, G \colon \mathbb{R}^n \to \mathbb{R}^n$. Then, $$ \nabla (F(X)^\top G(X)) = \nabla F(X)^\top G(X) + \nabla G(X)^\top F(X) $$ $$ \DeclareMathOperator*{\argmax}{arg \,max \,} \DeclareMathOperator*{\argmin}{arg \,min \,} $$ Without constraints We are interested in minimizing an arbitrary function $f \colon \mathbb{R}^n \to \mathbb{R}$. To do so, we will use the gradient descent method. Let $\mathbf{x}^{(0)} \in \mathbb{R}^n$ be a random starting point. Then, for $k \in \mathbb{N}$, $$ \mathbf{x}^{(k + 1)} = \mathbf{x}^{(k)} - s^{(k)} \nabla f(\mathbf{x}^{(k)})....
Simplex We want to solve the following problem: $$ \max{z} = \sum_{j = 1}^n c_j x_j $$ where $$ \begin{cases} \sum_{j = 1}^n a_{ij} x_j &\leq b_i, \qquad i \in \{1, \dots, m\} \\ x_j &\geq 0, \qquad j \in \{1, \dots, n\} \end{cases} $$ Then, we find a tuple $x^\ast = (x_1^\ast, \dots, x_n^\ast)$ that is the solution of the optimization problem. To this end, we build dictionaries such that...
In mathematical morphology, the basic structure of an image is a complete lattice. Definition: Complete lattice A complete lattice is a set $K$ equipped with an order relation $\leq$ that satisfies: Reflexivity: $\forall x \in K$, $x \leq x$; Antisymmetry: $\forall x, y \in K$, $x \leq y$ and $y \leq x$ implies $x = y$; Transitivity: $\forall x, y, z \in K$, $x \leq y$ and $y \leq z$ implies $x \leq z$; $\forall x, y \in K$, the supremum and infimum of $x$ and $y$ exist and are denoted $x \lor y$ and $x \land y$ respectively....
We present different methods to test data against hypotheses. Statistical test We consider the null hypothesis ($H_0$) and the alternative hypothesis ($H_1$). We are interested in rejecting or not the null hypothesis. Definition: Null hypothesis The null hypothesis $H_0$ is that considered true in the absence of data (default choice). Here, let $\delta$ denote the decision function used to reject or not the null hypothesis. $$ \delta(x) = \begin{cases} 0 & \text{do not reject $H_0$} \\ 1 & \text{reject $H_0$ in favor of $H_1$} \end{cases} $$ Definition: Error types The Type-I error rate is the rate of false positives: $\alpha = \mathbb{P}(\delta(x) = 1 \mid H_0)$....
K-Nearest Neighbors classifier The idea is to represent each record in the data set as an element in $\mathbb{R}^n$ $\DeclareMathOperator*{\argmax}{arg \,max \,} \DeclareMathOperator*{\argmin}{arg \,min \,}$. Then, to predict the class of a new point $x$, compute the $k$ points that are nearest to $x$. The majority class of these $k$ points is the predicted class of $x$. To run this algorithm, we need to define a distance function and also a value for $k$....
Definition: Induced subgraph A graph $H = (V_H, E_H)$ is an induced subgraph of $G = (V_G, E_G)$ if $V_H \subseteq V_G$ and if $u, v \in V_H$ and $(u, v) \in E_G$, then $(u, v) \in E_H$. We will say that $\delta_G(v)$ is the number of edges incident to $v$ in $G$. Definition: $k$-core Given a graph $G$ and $k \geq 0$, a subgraph $H$ of $G$ is a $k$-core if:...
Tip: Beta distribution The Beta distribution is a continuous probability distribution defined on the interval $[0, 1]$. It has two parameters: $\theta = (\alpha, \beta)$. Then, we have: $$ \begin{align*} p_\theta(x) &= \frac{x^{\alpha - 1} (1 - x)^{\beta - 1}}{B(\alpha, \beta)} \\ \mathbb{E}[X] &= \frac{\alpha}{\alpha + \beta} \\ \mathrm{Var}(X) &= \frac{\alpha \beta}{(\alpha + \beta)^2 (\alpha + \beta + 1)} \end{align*} $$ where $B(\alpha, \beta)$ is the Beta function, defined as: $$ B(\alpha, \beta) = \frac{\Gamma(\alpha) \Gamma(\beta)}{\Gamma(\alpha + \beta)} $$ Here, we are considering $\theta \in \Theta$ as a random variable....
Perception Color is the result of 3 things: An illuminant: source of light ($I(\lambda)$); An object: absorbs and reflects light ($R(\lambda)$); An observer: sensor ($S(\lambda) = I(\lambda) R(\lambda)$). Our visual system consists of rods (sensible, imprecise) and cones (not so sensible, very precise). There are three types of cones: S (short) cones: blue; M (medium) cones: green; L (large) cones: red; Let $s(\lambda)$, $m(\lambda)$ and $l(\lambda)$ be the spectral sensibilities of these cones....
Definition: Segmentation To segment an image is to divide it into homogeneous regions, considering one or many attributes (gray level, color, texture, etc.). We call borders the boundaries between these regions. Classical methods of border detection We try to use the local variations of the image to find borders: the 1st and 2nd derivatives. Since we are looking for discontinuities in the image, we need to find the points where the derivative is maximum....