Principles and Techniques of Computational Data Pre-Processing

Module 1: Introduction to Knowledge Discovery and Data Mining

Data Mining is a non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data. Knowledge Discovery in Databases (KDD) maps out this cycle through sequential but iterative phases: Data Cleaning, Data Integration, Data Selection, Data Transformation, Data Mining, Pattern Evaluation, and Knowledge Presentation.

A more refined process model is the CRISP-DM (Cross-Industry Standard Process for Data Mining) model, representing the cyclical nature of business understanding, data understanding, data preparation, modeling, evaluation, and deployment.

OLTP vs. OLAP

• On-line Transaction Processing (OLTP): Supports order processing and billing, typically executing simple queries across isolated databases.
• On-line Analytical Processing (OLAP): Designed for decision-makers requiring complex, multi-dimensional queries. OLAP operates on a Data Cube, an efficient structure allowing dimensions like products, time, and region to be cross-analyzed.
• Data Cube Operations:
  • Slice: Vertical selection by a single value.
  • Dice: Subcube selection by multiple values and dimensions.
  • Roll-Up: Aggregating data upwards in a hierarchy (e.g., $month \rightarrow quarter \rightarrow year$ ).
  • Drill-Down: Moving downwards in a hierarchy of values.

Module 2: Data Pre-Processing

Data pre-processing accounts for roughly $80\%$ of a data mining task. It includes Feature Subset Selection, Feature Transformation (e.g., discretization), Feature Construction, Sampling, and Data Cleaning.

Outlier Detection

The 2-Sigma Rule is a standard unsupervised statistical method. It classifies an example as an outlier if there is a numerical attribute $A$ whose value deviates from the mean by more than two standard deviations:

Discretization

• Top-down (Splitting): Starts with a single interval and recursively splits.
• Bottom-up (Merging): Starts with points as intervals and merges neighbours.
• Chi-Merge Algorithm (Supervised): Sorts examples by feature value and iteratively merges adjacent intervals with the lowest $\chi^2$ value. The $\chi^2$ statistic is calculated as:

where $A_{ij}$ is the number of examples in the $i$ -th interval of class $j$, and $E_{ij}$ is the expected number of examples.

Module 3: Rule Learning and Subgroup Discovery

Subgroups and predictive models are frequently represented as logical rules providing a balance of human understandability and machine executability. Attributes can be viewed as statements in propositional logic using conjunctions ( $\wedge$ ), disjunctions ( $\vee$ ), negations ( $\neg$ ), and implications ( $\rightarrow$ ).

Separate-and-Conquer Rule Learning

Predictive learning requires sets of rules to handle complexity. The Separate-and-Conquer (Covering) strategy builds a theory $T$ by learning a single consistent rule $R$ from the set $E$, adding it to $T$, and deleting the covered examples before repeating the search.

Anti-Monotonicity and Generality

A key operational property in finding hypotheses is the generality relation. A rule is more general if its set of conditions is a subset of another's.

$$C \subseteq D \Rightarrow support(C) \geq support(D)$$

Adding a condition (specializing the rule) may never increase the support or frequency of a rule.

Overfitting and Pruning

Overfitting occurs when algorithms fit error or noise in the training data, leading to rules that do not generalize.

• Incremental Reduced Error Pruning (I-REP): Efficient pruning method ( $O(n \log^2 n)$ ) splitting data into growing and pruning sets, dropping conditions as long as the error on the pruning set does not increase.

• Multi-Class Rule Learning: Pairwise classification decomposes a problem into binary models. The total number of training examples for all binary classifiers in a pairwise classification ensemble with $c$ classes and $n$ examples is:

  $$(c - 1) \cdot n$$

Module 4: Association Rule Mining

Association rules capture frequent co-occurrences. The base itemset must surpass a minimum support ( $s_{min}$ ) and minimum confidence ( $c_{min}$ ).

• Support: The proportion of examples for which both the head and body of the rule are true.

  $$support(A \rightarrow B) = support(A \cup B) = \frac{n(A \cup B)}{n}$$

• Confidence: The proportion of examples for which the head is true among those where the body is true.

  $$confidence(A \rightarrow B) = \frac{support(A \cup B)}{support(A)} = \frac{n(A \cup B)}{n(A)}$$

Module 5: Evaluation Methods

Validating learned models on separate, out-of-sample datasets prevents biased estimates. Evaluation relies on the confusion matrix extracting true positives ( $tp$ ), false positives ( $fp$ ), true negatives ( $tn$ ), and false negatives ( $fn$ ).

Core Evaluation Formulas

• True Positive Rate: $$tpr = \frac{tp}{tp + fn}$$
• False Positive Rate: $$fpr = \frac{fp}{fp + tn}$$
• Accuracy:
  $$accuracy = \frac{tp + tn}{P + N}$$
  $$accuracy = \frac{P}{P+N} \cdot tpr + \frac{N}{P+N} \cdot (1 - fpr)$$
• Error Rate:
  $$error = \frac{fp + fn}{P + N} = 1 - accuracy$$
  $$error = \frac{P}{P+N} \cdot (1 - tpr) + \frac{N}{P+N} \cdot fpr$$

Cost-Sensitive Evaluation

Predicting class $i$ instead of correct class $j$ carries a cost $C(i|j)$. The overall expected cost (Loss) incorporates the base confusion rates:

$$L = tpr \cdot C(+|+) + fpr \cdot C(+|-) + fnr \cdot C(-|+) + tnr \cdot C(-|-)$$

If there are no costs for correct classifications ( $C(+|+) = C(-|-) = 0$ ), the formula condenses to:

$$L = fpr \cdot C(+|-) + (1 - tpr) \cdot C(-|+)$$

Stream Mining Evaluation Complexity

When attempting naive stream sampling, maintaining $10\%$ of queries creates an incorrect bias for estimating unique duplicates ( $d$ ) over single searches ( $s$ ). The expected sample-based result calculates as:

$$\frac{18d}{100}$$

Which leads to the false total estimate of:

$$\frac{d}{10s + 19d} \neq \frac{d}{s + 2d}$$.