Skip to content
Tutorials Center
My learning

Topics

Lesson 70 of 79 ยท Distributed Databases, NoSQL and Analytics

Data Mining and Knowledge Discovery Overview

Learn the KDD process and core data mining tasks: association rules, clustering and classification, with live Python demos of support, confidence, k-means and k-NN.

A warehouse holds years of data, and an OLAP cube lets you slice it by region, product and month. But what if you do not yet know what to ask? Which products are bought together? Which customers resemble each other? Which new customers are likely to leave? Data mining is the set of techniques for discovering patterns like these automatically, instead of querying for patterns you already suspect.

This lesson gives a database-course overview. It places data mining in the wider knowledge discovery in databases (KDD) process, explains the three classic tasks (association rules, clustering and classification) and lets you run a tiny version of each in Python. It is an introduction to the ideas, not a replacement for a machine learning course.

The KDD pipeline

Clean and select Fix errors, choose the data.
Transform Aggregate, encode, scale.
Mine Run the algorithm.
Interpret Judge and act on the patterns.
1 / 2

Data mining and KDD

Knowledge discovery in databases is the whole process of getting useful, previously unknown knowledge out of raw data. Data mining is the central step, but typically it is a small part of the effort. The standard stages are:

  1. Selection. Decide which data matters for the question and pull it from operational databases or the warehouse.
  2. Preprocessing (cleaning). Remove duplicates, fix or flag missing values and obvious errors. See Nulls and Three-Valued Logic for why missing values need care.
  3. Transformation. Aggregate, derive new attributes (age from birth date), encode text as numbers and scale values so one large-valued column does not dominate.
  4. Data mining. Apply an algorithm to find patterns.
  5. Interpretation and evaluation. Decide which patterns are real, useful and understandable. Many discovered patterns are trivial, accidental or wrong, and a person must judge them.
  6. Deployment. Use the knowledge: change a store layout, send an offer, flag fraud.

The process is iterative. A surprising result often sends you back to cleaning, because the "pattern" turns out to be a data-entry habit.

Most of the work is in steps 1 to 3, which is where database skills pay off: SQL for selection and aggregation, constraints for quality, and a warehouse as a clean source.

Descriptive and predictive mining

Mining tasks fall into two broad kinds:

  • Descriptive tasks summarize what is in the data: association rules, clustering, outlier detection and sequence patterns.
  • Predictive tasks use known cases to estimate unknown ones: classification (a category) and regression (a number).

Another distinction is supervised learning, where each training record carries the correct answer (a label), and unsupervised learning, where the algorithm only sees the records. Classification is supervised, clustering and association rules are unsupervised.

Association rules

The classic example is market-basket analysis. Given many transactions, each a set of items, find rules of the form if a customer buys A, they often also buy B, written A -> B. Three numbers describe a rule:

  • Support of an itemset is the fraction of all transactions that contain it. support(A -> B) is the support of A and B together.
  • Confidence of A -> B is how often B appears among transactions that contain A: support(A and B) / support(A).
  • Lift compares confidence with how common B is anyway: confidence / support(B). Lift above 1 means A and B occur together more than chance would predict. Lift near 1 means the rule is no better than guessing.

Counting every possible combination of items is impossible for a store with thousands of products, so algorithms use the Apriori principle: every subset of a frequent itemset is also frequent. If {beer, chips} is rare, there is no point looking at {beer, chips, bread}. Apriori therefore builds frequent itemsets level by level, discarding candidates that contain an infrequent subset. FP-growth does the same job with a compact tree and no candidate generation.

The program below runs Apriori by hand on eight small baskets and prints the rules whose confidence is at least 70 percent.

Python Support, confidence and lift with Apriori

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output with a critical eye. A rule with high confidence but lift close to 1 only says that the right-hand item is popular. A rule with a lift well above 1 is a real association. Even then, the rule says nothing about why: association is not causation.

Clustering

Clustering groups records so that records in the same cluster are similar and records in different clusters are not. There are no labels; the algorithm decides. Typical uses are customer segmentation, grouping documents and finding unusual records (outliers) that fit no cluster.

The best-known algorithm is k-means. You choose the number of clusters k, and then repeat two steps until nothing changes:

  1. Assign every point to its nearest centroid (the current cluster centre).
  2. Update every centroid to the average of the points assigned to it.

Other families include hierarchical clustering (build a tree of merges) and density-based methods such as DBSCAN (clusters are dense regions, sparse points are noise). Whatever the method, the notion of "similar" is a distance function that you must choose with care, and attributes should be scaled so that one does not dominate.

Classification

Classification learns from records whose class is known and then predicts the class of new records: fraud or not fraud, will the customer churn, which species. The model is built from a training set and judged on a separate test set that the model has never seen, because a model can memorize its training data (overfitting) and still fail on new data. Common techniques are decision trees (a series of if-then tests that are easy to read), naive Bayes, nearest neighbors, logistic regression and neural networks.

A simple method that needs no training is k-nearest neighbors (k-NN): to classify a new point, find the k closest labelled points and take a majority vote. The second demo clusters unlabelled points with k-means and then classifies unseen points with 3-NN, and reports the accuracy on a test set.

Python k-means clustering and k-NN classification

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three centroids land close to the true centres (2, 2), (8, 3) and (5, 8) even though k-means never saw the labels, and the classifier is accurate because the groups are well separated. Real data overlaps far more, which is why evaluation on held-out data matters.

Where data mining meets databases

Data mining is a database topic because of scale and data management:

  • Data preparation is done in SQL and ETL pipelines, as described in OLTP, OLAP and Data Warehouses.
  • Large data requires algorithms that scan the data a few times instead of loading it in memory, and parallel implementations.
  • In-database analytics pushes mining into the DBMS: some engines offer built-in functions for regression, clustering or model scoring, so data does not leave the server.
  • Privacy and ethics matter: mined patterns can reveal sensitive facts about individuals, so access control, anonymization and fair use are part of the job (see Database Security Threats).

Related fields have different emphases. Statistics focuses on inference from samples, machine learning on prediction algorithms, and data mining on finding patterns in very large stored data sets. In practice the tools overlap.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A rule {bread} -> {butter} appears in 3 of 8 baskets, and bread appears in 5 of 8. What is the confidence?

    Confidence is support(bread and butter) divided by support(bread): (3/8) / (5/8) = 0.6.
  2. 2. What does the Apriori principle state?

    This lets the algorithm discard any candidate that has an infrequent subset without counting it.
  3. 3. Which task is unsupervised?

    Clustering has no known answers to learn from. The other tasks learn from records whose outcome is known.
  4. 4. Why evaluate a classifier on a separate test set?

    Accuracy on the training data is optimistic. Unseen data shows how the model will behave in practice.
  5. 5. What are the two repeated steps of k-means?

    The assignment and update steps repeat until the assignments stop changing.

Summary

  • KDD is the whole process: selection, cleaning, transformation, mining, interpretation and deployment. Mining is only one step.
  • Tasks are descriptive (association rules, clustering, outliers) or predictive (classification, regression), and supervised or unsupervised.
  • Association rules are judged by support, confidence and lift, and Apriori prunes the search using the fact that subsets of frequent itemsets are frequent.
  • k-means clusters unlabelled points by alternating assignment and centroid update. k-NN and decision trees classify using labelled examples.
  • Always evaluate on unseen data and interpret patterns critically.

Continue with the practice material in DBMS Exercises, or revisit temporal and spatial databases.