Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Data mining and the KDD process

Overview of Data Mining and the KDD (Knowledge Discovery in Databases) process: definitions, steps, key tasks, formulas (support/confidence/lift, entropy, information gain), worked examples, common exam mistakes and practice questions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Data mining is used by engineers to convert large raw data into useful knowledge for decision making, prediction and automation. The KDD (Knowledge Discovery in Databases) process gives a structured, repeatable workflow so engineering solutions are reliable, reproducible and maintainable. It is iterative and interactive; you often revisit earlier steps based on evaluation results.

Key ideas

  • Steps of the KDD process (exact sequence often used in exam answers):

    1. Selection — choose the data relevant to the task. Assumption: relevant sources exist and are accessible.
    2. Preprocessing (Data cleaning) — remove noise and handle missing values. Assumption: errors are correctable or ignorable after inspection.
    3. Transformation (Feature construction, reduction) — convert data into formats or features suitable for mining (e.g. aggregation, discretisation). Assumption: transformed features preserve the information needed for the task.
    4. Data mining — apply algorithms (classification, clustering, association, regression, anomaly detection) to extract patterns/models. Assumption: models capture true patterns, not noise.
    5. Interpretation/Evaluation — assess patterns for validity, novelty, usefulness; validate on holdout or cross-validation. Assumption: evaluation metrics align with business objectives.
    6. Deployment — use discovered knowledge in applications (reports, integrated systems, alerts). Assumption: deployment environment will not invalidate the model (data drift considered).

    Draw diagram instruction: on your answer paper draw seven boxes left-to-right labeled: Data Sources → Selection → Preprocessing → Transformation → Data Mining → Interpretation / Evaluation → Deployment. Connect them with arrows left to right. Under the Data Mining box, draw a small branching to list methods: Classification, Regression, Clustering, Association Rules, Anomaly Detection, Summarization.

  • Definition: Pattern — a compact description of regularities in data (examples: rules, clusters, decision trees, frequent itemsets).

  • Definition: Model — a mathematical or algorithmic representation that maps inputs to outputs; used for prediction or explanation.

  • Common data mining task types (define before use):

    • Classification — predict a discrete class label.
    • Regression — predict a continuous value.
    • Clustering — group similar records without pre-existing labels.
    • Association rule mining — find itemsets that frequently occur together; rules are of form X → Y with X ∩ Y = ∅ (disjoint antecedent and consequent).
    • Anomaly detection — find rare or deviant records.
    • Summarization and trend analysis — provide concise descriptions of large data. Classification and regression are supervised learning; clustering, association rule mining, and most anomaly detection are unsupervised.
  • Overfitting vs underfitting: Overfitting — model fits training data noise (low training error, high test error); Underfitting — model too simple (high training and test error). Always mention validation or cross-validation (see other topics) to detect overfitting.

  • Evaluation: after mining, measure usefulness through accuracy, precision/recall, ROC, support/confidence for rules, or domain-specific costs.

Formulas

support(X) = (number of transactions containing X) / (total number of transactions) — support of itemset X, unitless; applies to association rule mining. confidence(X → Y) = support(X ∪ Y) / support(X) — conditional probability estimate that Y appears given X, unitless. lift(X → Y) = confidence(X → Y) / support(Y) — ratio showing dependence; unitless; lift > 1 indicates positive association, lift = 1 indicates independence, and lift < 1 indicates negative association. Entropy(S) = - Σ_{c ∈ classes} p_c · log2(p_c) — entropy of dataset S measured in bits; p_c is probability of class c; applies to categorical class distributions. InformationGain(S, A) = Entropy(S) - Σ_{v ∈ values(A)} (|S_v| / |S|) · Entropy(S_v) — expected reduction in entropy when splitting S by attribute A; units: bits.

(For each symbol: |S| = number of examples in set S; |S_v| = number in S with attribute A = v; p_c = |examples of class c| / |S|.)

Worked examples

Example 1 — association rule measures (university exam style): Given six transactions (each transaction lists items bought):

  1. T1: {bread, butter}
  2. T2: {bread}
  3. T3: {bread, butter, milk}
  4. T4: {milk, butter}
  5. T5: {bread, milk}
  6. T6: {butter} Calculate support, confidence and lift for the rule {bread} → {butter}. Steps:
  7. Count transactions: total = 6.
  8. Count transactions containing {bread}: T1, T2, T3, T5 → 4 transactions. So support(bread) = 4/6 = 0.6667.
  9. Count transactions containing {bread, butter}: T1, T3 → 2 transactions. So support(bread, butter) = 2/6 = 0.3333.
  10. confidence(bread → butter) = support(bread, butter) / support(bread) = (2/6) / (4/6) = 2/4 = 0.5.
  11. support(butter): butter appears in T1, T3, T4, T6 → 4/6 = 0.6667.
  12. lift(bread → butter) = confidence / support(butter) = 0.5 / 0.6667 ≈ 0.75. Answer: support = 0.3333, confidence = 0.5, lift ≈ 0.75. Interpretation: lift < 1 indicates bread and butter co-occur less often than expected by independence.

Example 2 — entropy and information gain for a binary class Dataset: 10 examples. Class distribution: 6 Yes, 4 No. Attribute A has two values: High (4 examples: 3 Yes, 1 No) and Low (6 examples: 3 Yes, 3 No). Compute InformationGain(S, A). Steps and formulas:

  1. Entropy(S) = - (6/10)·log2(6/10) - (4/10)·log2(4/10) = -0.6·(-0.736966) - 0.4·(-1.321928) = 0.44218 + 0.52877 = 0.97095 bits. (parent entropy)
  2. Entropy(S_High) = -0.75·log2(0.75) - 0.25·log2(0.25) = -0.75·(-0.415037) -0.25·(-2) = 0.31128 + 0.5 = 0.81128 bits.
  3. Entropy(S_Low) = -0.5·log2(0.5) -0.5·log2(0.5) = 1.0 bit.
  4. Weighted average = (4/10)·0.81128 + (6/10)·1.0 = 0.32451 + 0.6 = 0.92451 bits.
  5. InformationGain = 0.97095 - 0.92451 = 0.04644 bits. Answer: Information gain ≈ 0.0464 bits. Small gain — attribute A is not a strong splitter.

Example 3 — short model answer (theory): Question: Explain how preprocessing affects data mining results. Model answer outline: define preprocessing (cleaning, imputation, noise smoothing, normalization, discretisation), then give three precise effects: reduces noise and variance (improving model generalization), changes feature scale (affects distance-based methods like k-NN and clustering), reduces dimensionality (faster mining, less overfitting). Conclude by noting evaluation after preprocessing is essential.

Common mistakes

  • Using percentages inconsistently (mixing fraction and percent without conversion).
  • Forgetting to validate patterns on unseen data (no test/validation split) — leads to overfitting.
  • Miscomputing entropy signs or using natural log instead of log base 2 when reporting bits (specify units).
  • Omitting data-cleaning as a required step: many exam answers lose marks by skipping preprocessing.

For your exam

Types of questions you will get from this topic:

  • Definitions and short notes: define KDD, data mining, pattern, model, and list KDD steps.
  • Diagrams: draw the KDD pipeline and label steps and techniques; describe each box in 1–2 sentences.
  • Derivations and formulas: show entropy and information gain derivations, and derive support/confidence formulas from counts.
  • Numericals: compute support/confidence/lift on small transaction sets; compute entropy and information gain on small labelled datasets. Show all steps and units (bits) for entropy.
  • Short programs / pseudocode: explain a simple frequent itemset miner (Apriori logic) or show pseudo-steps of a decision tree splitter (use info gain). Mention the Apriori downward-closure (anti-monotonicity) property: if an itemset is frequent, all its subsets are frequent; if an itemset is infrequent, all its supersets are infrequent.

What a full-marks answer includes: exact definitions (bold naming words), the ordered KDD steps, clear diagram, correct formulas with symbols explained, step-by-step numeric work (show counts and conversions), and a short interpretation of results (e.g., what lift means or what low info gain implies).

Quick check

  1. What is the difference between KDD and data mining?
  2. Define support and confidence for a rule X → Y.
  3. If a dataset has class proportions 8 Yes and 2 No, what is Entropy(S) in bits?
    Answers: KDD is the whole process (selection, preprocessing, transformation, mining, evaluation, deployment); data mining is the core step that finds patterns. support(X) = |transactions with X| / total; confidence(X→Y) = support(X∪Y)/support(X). Entropy = -0.8·log2(0.8) - 0.2·log2(0.2) ≈ 0.7219 bits.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?