Data Warehousing and Data Mining

Two types of knowledge are declarative knowledge (facts, what is true) and procedural knowledge (how to do something, rules and procedures). Others include structural and heuristic knowledge.

Data warehousing is the process of collecting, integrating, cleaning and storing data from multiple sources in a central repository organised by subject and time, to support analysis and decision making rather than daily transactions.

Clustering accuracy is evaluated by internal measures, which use only the data (e.g. silhouette coefficient, Davies-Bouldin index, cohesion and separation), and external measures, which compare with known class labels (e.g. purity, Rand index, F-measure).

Two approaches are statistical (model-based) methods, which flag objects that deviate from an assumed distribution, and distance-based (or density-based) methods, which flag objects that are far from, or have few, neighbours. Others: clustering-based and proximity-based.

A frequent pattern is a pattern (itemset, subsequence or substructure) that appears in a data set with frequency at least a user-given minimum support threshold, e.g. milk and bread bought together often in transactions.

A lazy learner simply stores the training data and delays building a model until a query arrives; it classifies by comparing the new tuple with stored ones. Training is fast but prediction is slow. Example: k-nearest neighbour.

K-means uses the mean of a cluster as its centre and minimises the squared distance. An outlier with an extreme value pulls the mean towards itself, shifting the centroid and distorting the cluster shape and membership.

Accuracy can be improved with ensemble methods such as bagging, boosting (AdaBoost) and random forests, which combine multiple classifiers. Other methods: better data preprocessing and feature selection, parameter tuning and cross-validation.

Outliers are not always noise: studying them helps in applications like fraud detection (credit card misuse), intrusion detection, fault detection and medical diagnosis, where the rare objects themselves are the interesting events.

A data cube is a multidimensional data structure that stores aggregated measures (e.g. sales) along several dimensions (e.g. time, item, location), allowing OLAP operations such as roll-up, drill-down and slice-dice.

Data transformation converts data into forms suitable for mining. Common techniques:

• Smoothing: removes noise using binning, regression or clustering.
• Aggregation: summarises data, e.g. daily sales into monthly totals.
• Generalization: replaces low-level data by higher-level concepts using a hierarchy (city to country).
• Normalization: scales attributes to a small range. Min-max: $v' = \frac{v - \min}{\max - \min}$; z-score: $v' = \frac{v - \mu}{\sigma}$; decimal scaling.
• Attribute construction: builds new attributes from existing ones.
• Discretization: converts numeric values into intervals or labels.

Main components of a data warehouse:

• Data sources: operational databases, flat files and external sources feeding the warehouse.
• ETL tools (Extract, Transform, Load): extract data from sources, clean and transform it, and load it into the warehouse.
• Data warehouse database (central repository): stores the integrated, subject-oriented, time-variant data, along with data marts and metadata.
• Metadata: data about data, such as definitions, structure, mappings and rules.
• Access/front-end tools: query and reporting tools, OLAP, data mining and dashboards used by analysts.
• Warehouse management/ monitoring: security, backup and administration.

Hyperplane: a decision boundary that separates data of different classes in an n-dimensional space. It is a flat subspace of dimension $n-1$, defined by $\mathbf{w}\cdot\mathbf{x} + b = 0$ (a line in 2D, a plane in 3D).

Support vectors: the training points closest to the hyperplane, lying on the margin boundaries $\mathbf{w}\cdot\mathbf{x} + b = \pm 1$. They alone determine the position and orientation of the hyperplane; removing other points changes nothing.

Role in a linear classifier (SVM): the classifier chooses the hyperplane that maximises the margin, $\frac{2}{\lVert\mathbf{w}\rVert}$, between the two classes, and a new point is classified by the sign of $\mathbf{w}\cdot\mathbf{x} + b$. A larger margin gives better generalisation.

k-Means algorithm (partitioning clustering)

Input: dataset $D$ of $n$ objects, number of clusters $k$. Output: $k$ clusters.

1. Randomly choose $k$ objects from $D$ as the initial cluster centres (centroids).
2. Assign: for every object, compute its distance (usually Euclidean) to each centroid and assign it to the nearest one.
3. Update: recompute each centroid as the mean of all objects currently in its cluster: $\mu_j = \frac{1}{|C_j|}\sum_{x \in C_j} x$
4. Repeat steps 2 and 3 until the assignments no longer change (centroids stop moving) or a maximum number of iterations is reached.

The algorithm minimises the sum of squared errors $E=\sum_{j=1}^{k}\sum_{x\in C_j}\lVert x-\mu_j\rVert^2$. It is simple and fast but sensitive to the initial centroids and to outliers, and $k$ must be given in advance.

Proximity-based outlier detection assumes that an object is an outlier if its nearest neighbours are far away, i.e. its proximity to the rest of the data is significantly different from that of most objects.

There are two main approaches:

• Distance-based: an object $o$ is a $DB(r,\pi)$ outlier if fewer than a fraction $\pi$ of the objects lie within distance $r$ of it. Alternatively, rank objects by the distance to their $k$-th nearest neighbour (or average distance to $k$ neighbours); the objects with the largest scores are outliers.
• Density-based: the local density around an object is compared with the density around its neighbours (for example the Local Outlier Factor, LOF). An object whose density is much lower than that of its neighbours has a high LOF and is declared an outlier.

Steps: choose a distance measure and $k$ (or $r$), compute each object's score, then flag objects whose score exceeds a threshold or take the top-$n$ scores. Density-based methods handle datasets with clusters of different density better than plain distance-based methods.

Closed itemset: an itemset $X$ is closed in a dataset if it is frequent and there is no proper superset $Y \supset X$ with the same support count as $X$. Closed itemsets give a compact, lossless representation of all frequent itemsets (supports of all frequent itemsets can be derived from them).

Types of association rules:

• Based on the types of values: Boolean association rules (presence/absence of items) and quantitative association rules (numeric attributes, e.g. age(30..39) $\Rightarrow$ buys(laptop)).
• Based on dimensions: single-dimensional rules (one predicate, e.g. buys) and multi-dimensional rules (several predicates such as age, income, buys).
• Based on levels of abstraction: single-level and multilevel rules (e.g. milk $\Rightarrow$ bread vs. skim milk $\Rightarrow$ wheat bread).
• Based on kinds of patterns: frequent-itemset-based rules, sequential, and correlation rules.

Reconstruction-based methods assume that normal data have structure that can be compressed and reconstructed accurately, while outliers do not follow this structure and are reconstructed poorly.

Autoencoder is a neural network trained to reproduce its input. It has:

• an encoder that maps input $x$ to a low-dimensional latent code $z=f(x)$ (the bottleneck), and
• a decoder that reconstructs $\hat{x}=g(z)$ from $z$.

Working:

1. Train the autoencoder on the (mostly normal) data by minimising the reconstruction error $L=\lVert x-\hat{x}\rVert^2$
2. Because the bottleneck is small, the network learns only the dominant patterns of normal data.
3. For each object compute the reconstruction error $\lVert x-\hat{x}\rVert^2$ and use it as the outlier score.
4. Objects whose error is above a threshold (for example mean plus 3 standard deviations, or the top few percent) are declared outliers.

Normal points are reconstructed with small error; anomalous points, being unlike the training patterns, give large error. The method works without labels (unsupervised) and handles high-dimensional data, but training data should be mostly free of outliers.

Why clean the data?

Real-world data is dirty: incomplete (missing values), noisy (errors, outliers) and inconsistent (different formats, duplicates, conflicting values). Poor-quality data gives poor mining results ("garbage in, garbage out"), misleading patterns, and inaccurate models. Cleaning improves accuracy, consistency and the reliability of decisions.

How to clean data:

1. Handling missing values
   • Ignore/delete the tuple (when many attributes are missing).
   • Fill manually.
   • Fill with a global constant (e.g. "Unknown").
   • Fill with the attribute mean or median (or the class-wise mean).
   • Fill with the most probable value using regression, decision tree or Bayesian inference.
2. Handling noisy data
   • Binning: sort values, divide into bins and smooth by bin means, medians or boundaries.
   • Regression: fit the data to a function and smooth.
   • Clustering / outlier analysis: detect and remove values lying outside clusters.
3. Resolving inconsistencies and duplicates: correct typing errors, standardise formats and units (e.g. date formats), use constraints or reference data, and remove duplicate records.

Cleaning is an iterative process: detect discrepancies, apply transformations to correct them, and re-check.

The minimum support is not given, so assume a minimum support count of 3 (60% of 5 transactions).

Step 1: Item counts

A = 4, B = 4, C = 4, D = 4, E = 4, F = 2, G = 2, H = 2.

F, G and H are infrequent and are removed. The remaining items all have equal support, so they are ordered alphabetically: A, B, C, D, E.

Step 2: Ordered transactions

Step 3: FP-tree (item:count)

null
├─ A:4
│   ├─ B:3
│   │   └─ C:3
│   │       ├─ E:1
│   │       └─ D:2
│   │           └─ E:1
│   └─ C:1
│       └─ D:1
│           └─ E:1
└─ B:1
    └─ D:1
        └─ E:1

Step 4: Conditional pattern bases and frequent patterns (processing from the least frequent item upwards)

Check for E: within its conditional base, AB = 2, AD = 2, BC = 2, BD = 2, CD = 2, all below 3, so only AC is added.

Frequent itemsets (support count $\ge 3$):

• 1-itemsets: A, B, C, D, E
• 2-itemsets: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
• 3-itemsets: ABC, ACD, ACE

There are no frequent 4-itemsets.

OLAP (Online Analytical Processing) operations let users view and analyse multidimensional data (a data cube) interactively. The main operations are:

1. Roll-up (drill-up): aggregates data by climbing up a concept hierarchy or by reducing dimensions. Example: city $\rightarrow$ country, or month $\rightarrow$ quarter, giving totals at a higher level.
2. Drill-down: the reverse of roll-up; moves from summarised data to more detailed data by going down a hierarchy or adding a dimension. Example: quarter $\rightarrow$ month $\rightarrow$ day.
3. Slice: selects a single value on one dimension, producing a sub-cube of one lower dimension. Example: sales for time = "Q1" only.
4. Dice: selects values on two or more dimensions, giving a smaller sub-cube. Example: time = Q1 or Q2, location = Kathmandu or Pokhara, item = "mobile".
5. Pivot (rotate): rotates the axes of the cube to give an alternative view of the data, such as swapping rows and columns of a report.

Other operations include drill-across (querying more than one fact table) and drill-through (going down to the back-end relational tables).

Evaluation metrics for classifiers

They are computed from the confusion matrix:

• Accuracy $=\dfrac{TP+TN}{TP+TN+FP+FN}$: fraction of correct predictions. Error rate $=1-$ accuracy.
• Precision $=\dfrac{TP}{TP+FP}$: of the predicted positives, how many are truly positive.
• Recall (sensitivity) $=\dfrac{TP}{TP+FN}$: of the actual positives, how many are found.
• Specificity $=\dfrac{TN}{TN+FP}$: proportion of actual negatives correctly identified.
• F1-score $=\dfrac{2\cdot \text{Precision}\cdot\text{Recall}}{\text{Precision}+\text{Recall}}$: harmonic mean of precision and recall.
• ROC curve / AUC: plot of true positive rate against false positive rate at different thresholds; the larger the area, the better the classifier.

Example: TP = 40, FN = 10, FP = 5, TN = 45 gives accuracy $=85/100=0.85$, precision $=40/45=0.89$, recall $=40/50=0.80$, specificity $=45/50=0.90$, F1 $\approx 0.84$.

How a decision is created (decision tree)

A decision tree classifier builds a tree top-down. At each node the attribute giving the best split (highest information gain) is chosen; the data is partitioned by its values and the process repeats until a node is pure or no attributes remain. A new tuple follows the tests from the root to a leaf, and the leaf's class label is the decision.

$\text{Info}(D)=-\sum p_i\log_2 p_i,\qquad \text{Gain}(A)=\text{Info}(D)-\sum_j \frac{|D_j|}{|D|}\text{Info}(D_j)$

Example (14 days of the "play tennis" data, 9 Yes and 5 No):

$\text{Info}(D)=-\tfrac{9}{14}\log_2\tfrac{9}{14}-\tfrac{5}{14}\log_2\tfrac{5}{14}=0.940$

Splitting on Outlook: Sunny (2 Yes, 3 No) has entropy 0.971; Overcast (4 Yes, 0 No) has 0; Rain (3 Yes, 2 No) has 0.971.

$\text{Info}_{Outlook}(D)=\tfrac{5}{14}(0.971)+\tfrac{4}{14}(0)+\tfrac{5}{14}(0.971)=0.694$

$\text{Gain}(Outlook)=0.940-0.694=0.246$

This is the highest gain among the attributes, so Outlook becomes the root. The Overcast branch is a pure leaf (Yes); the Sunny and Rain branches are split further (for example by Humidity and Wind). A tuple with Outlook = Overcast is therefore classified as "Play = Yes".

Partitioning vs. hierarchical clustering

DBSCAN on the given points

The values of $\varepsilon$ and MinPts are not given, so assume $\varepsilon = 1.5$ and MinPts $=3$ (counting the point itself), with Euclidean distance.

Points: A(4,8), B(5,7), C(6,6), D(7,5), E(8,4), F(7,3), G(8,3), H(9,5).

Relevant distances: AB = BC = CD = DE = EF = EH = $\sqrt2\approx1.41$; EG = FG = 1. Other pairs are larger, for example DF = DH = 2, DG = GH = $\sqrt5\approx2.24$, AC = $\sqrt8\approx2.83$.

$\varepsilon$-neighbourhoods:

Clustering: start at A: it has only 2 points in its neighbourhood, so it is tentatively noise. Take B (core) and start cluster 1 with {A, B, C}; A is now reached as a border point. Expand from C (core), adding D; from D adding E; from E adding F, G, H; F and G are core but add nothing new, and H is a border point.

Result: one cluster $C_1=\{A,B,C,D,E,F,G,H\}$ and no noise points. The core points are B, C, D, E, F, G and the border points are A and H. (With a smaller $\varepsilon$ such as 1.2, the chain breaks and most points become noise, which shows how sensitive DBSCAN is to its parameters.)