• Customer groups clustered based on bought products
• Unsupervised malware family identification
• Outlier Detection

Flower family classification:

• Attributes (features)
  • Color of different parts
  • Shape of different parts
  • Size of different parts
• Solve it by training a multi-class NN with enough high-quality training data

For each attribute and each attribute value, select the most frequent class and predict it for this value. Select the attribute (and its rules) with the lowest error.

Supervised learning has labels during training, unsupervised learning does not.

Prioritizing accuracy at the cost of an overly complex decision function. This decision function does not generalize well to unseen data. Overfitting happens when minimizing the training error to a point where the validation error is on the rise.

• Numerical
  • Continuous
  • Discrete
• Categorical
  • Ordinal
  • Nominal

Examples for each are:

• Distributive: min, sum, count
• Algebraic: mean, midrange
• Holistic: median
• Self-maintainable (w.r.t. delete, insert): sum, count, mean
• Not self-maintainable (w.r.t. delete, insert): min, median

Self-maintainable ⇒ distributive or algebraic (i.e., not holistic)

$H(S) = -\sum_{i=1}^Np(x_i)\log(p(x_i))= -\sum_{i=1}^N\frac{1}{N}\log(\frac{1}{N})=-N(\frac{1}{N}\log(\frac{1}{N}))=\log(N)$

• Covariance: $\mathrm{Cov}(X,Y) = \mathbb{E}((X-\mathbb{E}(X))(Y-\mathbb{E}(Y)))$
• Pearson’s correlation coefficient: $\rho(X,Y) = \frac{\mathrm{Cov}(X,Y)}{\sqrt{\mathbb{V}(X)\mathbb{V}(Y)}}$

• Pearson’s Chi-Squared: For categorical data: Test if two random variables are not independent with significance $\alpha$
• Kolmogorov-Smirnov (continuous or discrete with many values)
  • One-sample: Test if a sample is drawn from a given reference distribution with significance $\alpha$
  • Two-sample: Test if two samples are drawn from the same distribution with significance $\alpha$
• Mann-Whitney U test: Rank-based test for two samples (numerical, ordinal): Test if values of one distribution tend to be larger than those of the other (for distributions of the same shape: if their medians differ) with significance $\alpha$

Dimensionality reduction is the task of finding a lower-dimensional feature space for the input data, without losing too much information.

PCA:

1. Center each feature $j$ (scaling by $\sigma_j$ is optional, but common if features have different units) $\tilde{A}_{ij} = \frac{x_{ij}-\mu_j}{\sigma_j}$
2. Do an orthogonal eigendecomposition of the covariance matrix $\frac{1}{N}\tilde{A}^T \tilde{A} = Cov = V D V^T$ (always exists, because covariance matrix is real and symmetric)
3. Sort eigenvectors by decreasing eigenvalues
4. Project the data onto the first t eigenvectors (change of basis into a lower-dimensional space)

We use binning with n bins. Our goal is to minimize the class entropy (impurity) or variance inside a bin. The two presented methods are entropy-based discretization (top-down with splits) and ChiMerge (bottom-up with merges).

• Best split (entropy-based): the boundary with the highest information gain, i.e., the lowest weighted entropy of the resulting intervals
• Best merge (ChiMerge): the pair of adjacent intervals with the lowest $\chi^2$ value, i.e., the most similar class distributions

An index is a redundant representation of the data in a data structure that allows certain operations to be performed efficiently, especially without scanning the whole database.

B-trees only index a single scalar value, spatial queries require indexing on multiple dimensions.

An R-tree is a balanced tree containing possibly overlapping rectangles. There is an upper bound on the number of data points / contained rectangles per rectangle.

We traverse the tree best-first with a priority queue sorted by MINDIST, the smallest possible distance between the query point and a rectangle. A rectangle (node) is only inspected if its MINDIST is smaller than the distance to the nearest neighbor found so far; all other rectangles are pruned.

R-trees can handle volumetric objects by placing bounding boxes around objects. We need to be careful though, because an overlap of the bounding box does not imply an overlap of the objects.

Yes, we want to reduce the amount of overlap, because a query may have to follow multiple paths through overlapping rectangles. In the worst case, this causes a linear component in the runtime instead of a log component.

We traverse the tree from the root to a leaf. At each level, we descend into the child whose rectangle requires the least enlargement to contain the new object (ties are broken by the smallest area). If a node exceeds its maximum capacity, we split it and propagate the split upwards. Finally, we adjust the bounding rectangles along the path.

k-NN, range, match, ranking

Non-parametric methods that predict based on the stored dataset without a classical training step.

• No training required (pro)
• Slow queries (con)
• Suffers from the curse of dimensionality (con)
• Sensitive to noise dimensions (con)
• Interpretable (pro)
• Only one hyperparameter (pro)
• Can be easily used as an active/online learner (pro)

Parametric classifiers need to calculate likely parameters from the training data before using them to make new predictions.

Comparison can be made along the following criteria:

• Performance (Accuracy and similar)
• Interpretability
• Robustness (noise, outliers, concept drift, adversarial examples, …)
• Efficiency (time & memory complexity/energy)
• Number of hyperparameters
• Applicability to high dimensional data, data streams, temporal data, …

If this question refers to linear regression, we can compute the closed form solution

$w_{1}=\frac{\operatorname{Cov}(x, y)}{\operatorname{Var}(x)} \quad w_{0}=\bar{y}-w_{1} \cdot \bar{x}$

This can easily be derived by minimizing the sum of squared errors, which is equivalent to maximizing the likelihood under Gaussian noise.

If the question refers to logistic regression (linear classification) we use gradient descent in training.

For an unseen data point, we compute the k-neighborhood (k nearest points) and choose the most frequent class in the k-neighborhood. For regression, we predict the (possibly distance-weighted) mean of the target values of the k nearest neighbors.

We use the ID3 algorithm, which works top-down recursively. Inner nodes test an attribute, edges correspond to attribute values, and leaves predict a class. Pseudocode:

id3(S, targetAttribute, attributes):
    if (all e in S have same targetAttribute value l):
        return Leaf(l, S)
    if attributes.empty():
        return Leaf(mostFrequent(S[targetAttribute]), S)
    bestAttribute = (find best attribute according to splitting criterion)
    node = Node(bestAttribute)
    for value in values(bestAttribute):
        Sv = S[S[bestAttribute] == value]
        if Sv.empty():
            node.add(value, Leaf(mostFrequent(S[targetAttribute]), S))
        else:
            node.add(value, id3(Sv, targetAttribute, attributes - {bestAttribute}))
    return node

We use the split with optimal splitting criterion value. For categorical attributes, we split on the attribute values. For numerical attributes, we sort the values and evaluate the candidate thresholds between consecutive values. Possible splitting criteria are:

Maximum Information Gain:

$IG(T) = H(T) - \sum_{i=1}^K\frac{|T_i|}{|T|}H(T_i)$

Minimum Gini Index:

$\operatorname{Gini}_A(T)=\sum_{i=1}^K \frac{|T_i|}{|T|} (1-\sum_{c=1}^C p_c(T_i)^2)$

Minimum Misclassification Error:

$\sum_{i=1}^K \frac{|T_i|}{|T|}(1-\max_{c\in [1,C]}p_c(T_i))$

• Prepruning
  • Minimum confidence: Stop when the points in a leaf are similar enough (misclassification error)
  • Minimum support: Stop when the minimum number of objects in a leaf is reached.
• Postpruning
  • Reduced-Error Pruning: Repeatedly replace the subtree whose removal reduces the error on a hold-out set the most by a leaf, until any further pruning would increase that error.
  • Minimal Cost Complexity Pruning: Trade off classification error on the training set with tree complexity: $CC(E, \alpha) = Error(E) + \alpha|E|$, where $|E|$ is the number of leaves of tree $E$. $\alpha$ is chosen with a validation set or cross validation.

With conditional risk $R(c_i \mid x) = \sum_j p(c_j \mid x) L(c_i \mid c_j )$, where $L(c_i \mid c_j)$ is the cost of predicting $c_i$ when the true class is $c_j$. Instead of the most probable class, we predict the class with the lowest risk $\argmin_{c_i} R(c_i \mid x)$.

Given an object $o$, we want to predict the most probable label $c\in C$: $K(o) = \argmax_{c_j\in C} p(c_j\mid o).$

We can use Bayes Rule and notice that the result is not changed by the division by $p(o)$, to obtain the decision rule for Bayes Classifier:

$K(o) = \argmax_{c_j\in C} \frac{p(o\mid c_j)\cdot p(c_j)}{p(o)}= \argmax_{c_j\in C} p(o\mid c_j)\cdot p(c_j)$

The hard part is to compute $p(o\mid c_j)$.

The Naive Bayes Classifier further assumes that $o$ is a vector with dimensions that are conditionally independent for all $c_j\in C$. This helps us to express

$p\left(\left(o_{1}, \ldots, o_{d}\right) \mid c_{j}\right)=\prod_{i=1}^{d} p\left(o_{i} \mid c_{j}\right)$

Plugging this into the decision rule of the Bayes Classifier gives the decision rule of the Naive Bayes Classifier:

$K(o) = \argmax_{c_j\in C} p(c_j)\cdot\prod_{i=1}^{d} p(o_i\mid c_j)$

Without knowledge of the problem, there are no context-independent or usage-independent reasons to favor one learning method over another. Averaged over all possible problems, all classifiers perform equally well, i.e., if a classifier is better than another one on some problems, it is worse on others.

Yes, we can form ensembles of classifiers, by

• Bagging (bootstrap aggregating): Train classifiers on bootstrap samples of the training data and combine them by an equally weighted vote
• Boosting: Train classifiers sequentially, each on reweighted data that emphasizes the examples misclassified by the previous classifiers. The weight of each classifier in the decision depends on its accuracy (e.g., AdaBoost)
• Stacking: Train a meta-classifier that learns how to combine the predictions of the base classifiers

• Performance (Accuracy and similar)
• Compactness of the model
  • Decision tree size; number of decision rules; number of parameters
• Interpretability of the model
  • Insights and understanding of the model – In general, hard to quantify
• Efficiency
  • Time to train and to apply the model
• Scalability for large databases
  • Memory and runtime (big O notation)
  • Considering disk-access, out-of-core computation
• Robustness
  • How results are affected by noise, outliers, missing values

With the standard hold-out method, there can be a significant variance of accuracy between all possible splits. We can average out that variance with k-fold cross validation. For the case of 10-fold cross validation, we partition the data into 10 partitions of (almost) equal size. For each partition, we use the other partitions as training data and use that partition as test data. We then average the performance.

$G_{T e}(K)=\frac{|\{o \in T e, K(o)=C(o)\}|}{|T e|}$

False Positives: Classified as positive, although it belongs to the negative class

False Negatives: Classified as negative, although it belongs to the positive class

Cohen’s Kappa measures how much better a classifier is than random guessing.

Let $p_0=G_{Te}(K)$ be the Accuracy of the classifier $K$ and $p_e = \sum_{c_j\in C} \frac{|\{o\in Te\mid K(o)=c_j\}|}{|Te|}\cdot \frac{|\{o\in Te\mid C(o)=c_j\}|}{|Te|}$ the expected agreement between $K$ and the true labels by chance (guessing with the same class frequencies).

Cohen’s Kappa is the difference normalized for perfect Accuracy

$\kappa=\frac{p_0-p_e} {1-p_e}$

A perfect classifier has $\kappa=1$, random guessing has $\kappa = 0$, and a classifier that is always wrong has $\kappa=-\frac{p_e}{1-p_e}$ (which is $-1$ only in special cases, e.g., for two balanced classes)

Accuracy can be misleading for testing sets with imbalanced class sizes. Most commonly, we use the $F_1$ score, the harmonic mean of precision and recall.

$F_1 = 2\cdot\frac{Pr\cdot Re}{Pr+Re}$

If we want to weight one of the inputs more or less, we can use the $F_\beta$ score. For example, if we want to be sure that all positives are found and don’t mind having a few FPs, we can overweight recall ($\beta > 1$).

$F_\beta = (1+\beta^2)\frac{Pr\cdot Re}{(\beta^2\cdot Pr) + Re}$

The expected (squared) error of a model can be decomposed into three parts:

• Variance: the error we make because we only have a limited data set, so the fitted function changes with the training data
• Squared bias: the error we make because the function we are approximating is not contained in the class of functions we are fitting
• Inherent noise: the error that no model can avoid

The tradeoff: more complex models have a lower bias, but a higher variance (overfitting). Simpler models have a lower variance, but a higher bias (underfitting). The best model balances both.

It penalizes large errors more strongly. The informational loss $-\log_2 p(\text{true class})$ goes to infinity if the classifier assigns a probability close to 0 to the true class, while the quadratic loss is bounded.

• Is the data set highly imbalanced?
  • Then standard “accuracy” is probably not meaningful
• Do you care about one class (positives) in particular?
  • Then F-scores are useful
  • By setting β, you can control the trade-off between recall/precision
• Do you need to penalize “gross” errors more badly?
  • Then maybe informational loss
• Some measures are controversial
  • But still useful, e.g., Cohen’s Kappa
  • MCC (Matthews correlation coefficient) tends to be preferred

A lift chart is a 2D plot with the sample size by decreasing probability threshold on the x-axis and the TPs (Gain/Loss) on the y-axis. In contrast, the ROC curve plots the true positive rate against the false positive rate for all thresholds.

With the $R^2$ measure, which compares the squared error of the model to the inherent variance of the data. It measures the share of the variance of the target values that is explained by the model.

$R^{2}=1-\frac{\sum_{i}\left(f(x_{i})-y_{i}\right)^{2}}{\sum_{i}\left(y_{i}-\bar{y}\right)^{2}} \in (-\infty,1]$

An association rule $A\Rightarrow_p B$ means that if a transaction contains A, it also contains B with probability p (the confidence).

We find them in two steps:

1. Find all frequent itemsets, i.e., itemsets with at least minimum support (e.g., with Apriori or FP-growth)
2. Generate rules $A\Rightarrow B$ from each frequent itemset $A\cup B$ and keep those with at least minimum confidence

$A\Rightarrow B [\text{Support, Confidence}]$

A maximal itemset is an itemset that is frequent and not a proper subset of another frequent itemset.

A closed itemset is an itemset that is not a proper subset of another itemset with the same support.

Let’s stick with the supermarket example.

Low support, low confidence: {Kids’ Toys} ⇒ {Vodka} never bought together

Low support, high confidence: {Apples, Steak} ⇒ {Eggs} many people who bought apples and steak also bought eggs, but there are just not many people in the first place who bought apples and steak together.

High support, high confidence: {Cereal} ⇒ {Milk} many baskets contain both, and most people who buy cereal also buy milk.

High support, low confidence: {Milk} ⇒ {Cereal} the same frequent itemset, but milk is bought so often that most people who buy milk do not buy cereal.

Support and confidence are not the same as correlation. Something can be negatively correlated and still have high support and confidence. Example from the lecture:

Consider that among 5000 students
3000 play basketball (= 60%)
3750 eat cereal (=75%)
2000 both play basketball and eat cereal (=40%)

Play basketball ⇒ eat cereal [40%, 66.7%] vs. Play basketball ⇒ not eat cereal [20%, 33.3%]

The first rule looks strong, but its confidence of 66.7% is lower than the overall share of students who eat cereal (75%). Playing basketball actually makes eating cereal less likely; the two are negatively correlated (lift = 0.667 / 0.75 ≈ 0.89 < 1).

Multi-dimensional association rules are association rules applied to categorical relational data. Instead of looking at transactions of a single column, we now consider multiple columns. We can easily translate that into a standard association rule problem by having a transaction for each row that looks like this: {col1Name/val[i, 1], …, colNName/val[i, N]}

Normal association rules have a fixed level of abstraction. E.g., having one category for milk, but in a supermarket there are multiple subtypes. Multi-level association rules allow capturing effects across levels. The multi-level case can be transformed into a standard association rule problem by looking at the directed tree of types and having a category for every walk in the tree starting from the root and ending at any node. But we need to be aware of the exponential increase in categories for each full new layer in the tree.

Both produce rules: each path from the root to a leaf in a decision tree is a rule. For each consequent of an association rule, we can build a decision tree that predicts how likely it is that the consequent will happen. With that, we have a conditional decision, instead of just an occurrence in a set. But decision trees have a fixed target attribute, so we need to build a decision tree for each product instead of mining association rules from transactions.

The join step is expensive if there are many frequent itemsets, and gets more and more expensive if $L_i$ does not fall fast. This is the case when the minimum support is low or there are long frequent patterns. We can counter this by choosing a larger minimum support.

Also, support counting requires a full database scan for each level, which is expensive for large datasets. We can use a hash tree to speed up the lookups for counting, as our transactions are sorted.

Toivonen’s algorithm reduces the number of database scans: It mines a sample with a lowered minimum support, and then verifies the result and its negative border with a single full database scan.

Initialize $L_1$ with frequent 1-itemsets.

1. Given sorted frequent itemsets $L_k$, join them to get the candidates $C_{k+1}$. Efficient because of sorted itemsets.
2. Get $C_{k+1}^\text{pruned}$ by going through $C_{k+1}$ and only keep candidates where each k-subset is in $L_k$. Efficient because of sorted itemsets.
3. Get $L_{k+1}$ by counting the support of each itemset and delete the ones with less than minimum support.

Stop if $L_{k+1}$ is empty.

The negative border is the set of itemsets that are not frequent, but all of whose proper subsets are frequent. Apriori finds that negative border: these are exactly the candidates that fail the support check.

Any superset of a non-frequent itemset is non-frequent too. Equivalently, support is anti-monotone: $X\subseteq Y \Rightarrow \operatorname{supp}(Y)\leq\operatorname{supp}(X)$.

Frequent pattern trees contain all frequent patterns with their support and are not larger than the original database.

1. Scan the database once to find the frequent items. Remove the infrequent items from every transaction and sort the remaining items by descending frequency.
2. Scan the database a second time and insert each transaction as a path starting from the root. Transactions with a common prefix share nodes, and each node counts how many transactions pass through it. For efficiency, we have a header table with an entry for each frequent item that links to all nodes of that item in the FP-tree.
3. From the prefixes pointed to by the header table, we can further construct the conditional pattern base, for every frequent item. For each pattern base, we can repeat the process.

No candidate generation
Compact data structure
Only 2 database scans

• Partitioning Clustering
  • k-Means and variants
• Probabilistic Clustering
  • Expectation Maximization
• Density based Clustering
  • DBSCAN
• Hierarchical Clustering
  • Agglomerative/Divisive
  • OPTICS (density-based and hierarchical)

1. Pick k random centers
2. Assign each point to the closest center
3. Compute a new center, as the mean of all points in the current cluster
4. GOTO 2. until nothing changes anymore

We want to minimize the total distance $T D=\sum_{i=1}^{k} \sum_{\vec{x}_{j} \in C_{i}} \operatorname{dist}\left(\vec{x}_{j}, m_{i}\right)$

1. Pick k random objects (medoids)
2. Assign each object to the closest medoid
3. For each pair of medoid and non-medoid, compute how TD would change if we swapped the objects. Perform the swap that reduces TD the most and reassign the objects. Repeat this step until no swap reduces TD.

Like k-Means, but for categorical data. Use the mode of a cluster instead of the mean, and use the Hamming distance to compare points.

Choose hyperparameters $\varepsilon$ and MinPts

1. Calculate core objects: An object is core, if and only if $|N_\varepsilon(o)| \geq \mathrm{MinPts}$
2. Density-connected objects form density-based clusters!

1. Visit each point, remember core distance and reachability distance
2. Move from one point to another by the “shortest jump”
3. Maintain a priority list (sorted by increasing reachability-distance to already processed points)

Output: Ordered list of points: Core distance and reachability distance of points

This can be visualized as a reachability plot, and interpreted as a dendrogram.

Partitioning clustering (e.g., k-Means) is typically more efficient, has only one main hyperparameter (k), and works well for compact, convex clusters. Density-based clustering, in contrast, can find clusters of arbitrary shape and handles noise.

$\mathcal{O}(tk(n-k)^2)$

We can improve the runtime with CLARA (PAM on samples of the data) or CLARANS (randomized search over swaps).

The silhouette coefficient captures the goals of clustering: Similarity within the clusters, dissimilarity between clusters, in a distance based way.

$a(o)=\frac{1}{|C(o)|-1} \sum_{p \in C(o), p \neq o} \operatorname{dist}(o, p)$

$b(o)=\min _{C_{i} \neq C(o)} \frac{1}{\left|C_{i}\right|} \sum_{p \in C_{i}} \operatorname{dist}(o, p)$

$s(o)=\left\{\begin{array}{cc} 0 & \text { if }|C(o)|=1 \\ \frac{b(o)-a(o)}{\max \{a(o), b(o)\}} & \text { otherwise } \end{array}\right.$

$\operatorname{silh}(\mathcal{C})=\frac{1}{n} \sum_{C_{i} \in \mathcal{C}} \sum_{o \in C_{i}} s(o)\in [-1,1]$

We can look at a dendrogram, e.g., generated with OPTICS.

Or we can try different k and plot a quality measure. For the silhouette coefficient, we choose the k with the highest value. For the total distance (TD), which always decreases with k, we choose the k where it stops decreasing sharply; this point is called the elbow.

Do some reasonable initialization of distribution parameters, e.g., with k-Means.

Expectation: Compute cluster probabilities aka responsibilities for each sample (Bayes rule) $q_{i k}=p\left(k_{i}=k \mid \boldsymbol{x}_{i}\right)=\frac{p\left(\boldsymbol{x}_{i} \mid k\right) p(k)}{\sum_{j} p\left(\boldsymbol{x}_{i} \mid j\right) p(j)}=\frac{\pi_{k} \mathcal{N}\left(\boldsymbol{x}_{i} \mid \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k}\right)}{\sum_{j=1}^{K} \pi_{j} \mathcal{N}\left(\boldsymbol{x}_{i} \mid \boldsymbol{\mu}_{j}, \boldsymbol{\Sigma}_{j}\right)}$

Maximization: Compute (weighted) maximum likelihood estimate $\pi_{k}=\frac{\sum_{i} q_{i k}}{N} \quad \boldsymbol{\mu}_{k}=\frac{\sum_{i} q_{i k} \boldsymbol{x}_{i}}{\sum_{i} q_{i k}} \quad{\Sigma}_{k}=\frac{\sum_{i} q_{i k}\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}_{k}\right)\left(\boldsymbol{x}_{i}-\boldsymbol{\mu}_{k}\right)^{T}}{\sum_{i} q_{i k}}$

Core objects: Objects with $|N_\varepsilon(o)| \geq \mathrm{MinPts}$

Border objects: Objects that are not core themselves, but lie in the $\varepsilon$-neighborhood of a core object (directly density-reachable)

Noise: Other points

We can fix MinPts, typically $2\cdot d$, and plot the sorted distances of all points to their MinPts-th nearest neighbor (k-distance plot). A good $\varepsilon$ is at the elbow of this plot, where the distances start to increase sharply.

A tree that represents a hierarchical clustering. The root represents the whole data set, and a leaf represents a single object in the data set. Each node is the union of its children. The height of a node is the distance (dissimilarity) at which its children are merged. Cutting the dendrogram at a certain height gives a flat clustering.

Minimum distance: $\operatorname{dist}_{s l}(X, Y)=\min _{x \in X, y \in Y} \operatorname{dist}(x, y)$

Maximum distance: $\operatorname{dist}_{c l}(X, Y)=\max _{x \in X, y \in Y} \operatorname{dist}(x, y)$

Average distance: $\operatorname{dist}_{a l}(X, Y)=\frac{1}{|X| \cdot|Y|} \sum_{x \in X, y \in Y} \operatorname{dist}(x, y)$

• We can capture clusters in clusters.
• We do not need to know the number of clusters k upfront.
• The dendrogram is an informative visualization of the cluster structure.

• Partitioning
  • k-{Means, Mode, Median, Medoid}
• Probabilistic
  • EM
• Density based
  • DBSCAN, OPTICS
• Hierarchical
  • OPTICS, BIRCH, DIANA

An outlier is an observation which deviates so much from the other observations as to arouse suspicions that it was generated by a different mechanism.
~ Hawkins, 1980

Because we do not have ground truth for outliers.

For outlier detection, we want an unsupervised partitioning of the data into normal data and outliers.

We may also find outliers by clustering and looking for small clusters or noise.

An antivirus company that wants to find samples of a new malware family.

• Multivariate density functions are difficult to estimate
  • Statistical methods are themselves sensitive to outliers
• Most tests are for single attributes only
• In many cases, data distribution may not be known

An outlier ranking is preferable, because it carries more information and can be converted to a binary decision just with a threshold value.

LOF is the average ratio of the local reachability densities (lrd) of o’s k nearest neighbors to the lrd of o. An LOF of about 1 means o is as dense as its neighbors; an LOF much greater than 1 means o is an outlier.

$\operatorname{reach-dist}_{k}(o, p)=\max\{k\text{-}\operatorname{dist}(p), \operatorname{dist}(o, p)\}$

$\operatorname{lrd}_{k}(o)=1 / \left(\frac{\sum_{p \in N_{k}(o)} \operatorname{reach-dist}_{k}(o, p)}{\left|N_{k}(o)\right|}\right)$

$LOF_{k}(o)=\frac{\sum_{p \in N_{k}(o)} \frac{\operatorname{lrd}_{k}(p)}{\operatorname{lrd}_{k}(o)}}{\left|N_{k}(o)\right|}=\frac{\sum_{p \in N_{k}(o)} \operatorname{lrd}_{k}(p)}{\left|N_{k}(o)\right| \cdot \operatorname{lrd}_{k}(o)}$

• Global outliers
  • Deviate from the majority of data
• Local outliers
  • Deviate from their local neighborhood (e.g., a point in a sparse region next to a dense cluster)
• Contextual outliers
  • Deviate only in a specific context: “The temperature is 28°C today, is that exceptional?” (depends on the season)
• Collective outliers
  • Abnormal “burst” of observations

We can use:

• Autoencoders
• Restricted Boltzmann Machines
• Self-Organizing Maps

Because we do not have meaningful distances: In high-dimensional spaces, the distances between all pairs of points become similar (concentration of distances).

The internationally recognized definition of big data is: A dataset so large, that it can’t be dealt with in Excel!

• Volume: amount of data
• Variety: type and nature of data
• Velocity: speed of new data arriving
• Veracity: truthfulness
• Value: worth in information

In Theory:

• Data attributes are immutable
• All data collected from a single source
• Classification: Labels are given
• Streaming: Time is equidistant
• Outlier Detection: Outliers are rare and very recognizable

In Practice:

• Data attributes can change rapidly due to new business requirements
• Data is distributed among many systems
• Classification: Labels are subject to interpretation
• Streaming: Everything is event based
• Outlier Detection: Outliers blend easily into the mass

Data Engineers:

• Data Collection
• Data Cleaning

Data Analysts (additionally):

• Coming up with a problem statement
• Exploratory Analysis

Data Scientists (additionally):

• Model Building
• Model Deployment

The most common one is CRISP-DM (Cross-Industry Standard Process for Data Mining). It structures a project into six phases (business understanding, data understanding, data preparation, modeling, evaluation, deployment) and is iterative: phases are revisited when needed.

It is fast in responding to changing demands from the customer.

1. Decision Tree: Fast to train, interpretable, and a good baseline that shows which features matter
2. Random Forest: Usually better performance than a single tree, robust against overfitting, and works well with little hyperparameter tuning

But remember, there is no free lunch.