—

Data Mining

Data Reduction, Discretization, and Classification

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Data reduction and histograms — covered in Lecture 4 (Data Reduction: Compression and Histograms)
Sampling as tuple-level reduction — covered in Lecture 4 (Sampling: Simple Random Sampling; Stratified and Cluster Sampling)
Discrete and continuous attributes — covered in Lecture 3 (Discrete and Continuous Attributes)
Classification — covered in Lecture 2 (Classification; The Classification Dataset: Attributes, Train and Test)
Regression — covered in Lecture 2 (Regression)
Clustering and structure finding — covered in Lecture 2 (Clustering; Clustering Applications)
Data preprocessing and normalization — covered in Lectures 3 and 4 (Data Preprocessing; Min-Max and Z-Score Normalization)

5.1 Attribute Subset Selection

5.1.1 The Two Ways to Reduce Data: Volume versus Features

Your data table has hundreds of columns, and only some of them decide the answer. What if you could delete half the columns and still build a model of the same quality? This section is about how to answer that question — and why asking it is one of the most valuable preprocessing moves you can make.

We are finishing the data preprocessing part of the course. Preprocessing covers data cleaning, data integration, data transformation, data reduction, and discretization. In data cleaning we fix missing values, smooth curves by binning and by linear regression, identify and remove outliers (clustering is one removal tool), and resolve inconsistencies. Data integration comes with its own list of things to keep in mind. Data transformation covers normalization (min-max, z-score, and similar methods) and aggregation. This lecture finishes the list with data reduction and discretization, and then opens the classification module.

Data reduction splits into two broad directions. The first is reducing by volume: if your data is a table, you shrink the number of tuples, the rows. Sampling is the way we explored; sampling can work at the tuple level or at the feature level, but here we think of it as picking a subset of the rows. The second direction is reducing the number of features, the columns, and that splits again into two methods. Attribute subset selection (picking a subset of the original columns and keeping them as they are) and attribute creation (combining columns into brand-new ones). Attribute subset selection keeps a subset of the original attributes: out of five attributes A1 to A5 you keep, say, A1, A2, and A3. Attribute creation method combines two or more attributes and produces a new attribute, so you compress A1, A2, and A3 into one new attribute, call it A1'. PCA (principal component analysis) belongs to this second family.

Why reduce features at all? Because you want to avoid the curse of dimensionality, and because you want to detect attributes that are irrelevant or weakly relevant — attributes that contribute very little to a classification model's performance. Instead of feeding them to the model, you drop them.

The curse of dimensionality: as the number of attributes grows, the data becomes increasingly sparse inside the space it occupies. In a high-dimensional space, every object looks far from every other object, distances lose their meaning, and classification models need many more records to find reliable boundaries between classes. The practical consequence: more columns does not automatically mean more information — it can mean a worse model. This is the single strongest motivation for every feature-reduction method in this lecture.

5.1.2 Redundant and Irrelevant Features

Some attributes can be deleted by common sense or domain knowledge. Two kinds of features are the usual targets, and they fail for different reasons.

A redundant feature is one that carries the same, or nearly the same, information as another feature. The classic example: the purchase price of a product and the amount of tax paid on it. Tax is a fixed percentage of the price, so the two columns differ only by a multiplication factor. If the tax rate is 18%, then every value in the tax column is exactly $0.18 \times price$ . Both columns carry almost the same information, so can we drop one? Sometimes yes, sometimes no — that is a judgment call we revisit with data in hand. The model cannot learn anything from the tax column that it could not already learn from the price column, but you may still keep both if, for example, tax is needed as a separate output or if the rate is not actually constant across all rows.

An irrelevant feature is one that contains no information for the data mining algorithm being used, at least for the task at hand. Suppose we have five attributes and build a classification model; if A1 contributes nothing to separating the classes, it is irrelevant to that model and can be dropped. For example, a student ID or a name is irrelevant to the task of predicting a student's grade — you cannot predict a grade from a name — and other personal attributes, like a hobby, are usually irrelevant for the same reason.

Redundant feature: repeats information that another feature already carries (price and tax; height and width for a rectangle). Dropping it loses almost nothing.
Irrelevant feature: holds no information for the specific mining task, no matter how informative it looks elsewhere (student ID when predicting grades). Dropping it loses nothing at all.
Redundant and irrelevant features do not just waste space — they can reduce classification accuracy and the quality of the clusters you find, because the algorithm spends effort on columns that mislead or repeat.

So one route is manual: human analysis and domain knowledge. The other route is automated: numerical methods that find a good subset for you. Manual deletion works when the data is well understood; automated methods take over when there are too many attributes for a human to judge, or when the behavior of the data is not yet known — which is, after all, usually the reason we are mining it.

5.1.3 The Cost of Exhaustive Search

The naive way to find the best subset is to try them all. With $n$ attributes, the number of non-empty subsets is:

$2^{n} - 1$

Where does this count come from? Each attribute is in one of two states — inside the subset or outside it — so $n$ attributes produce $2^{n}$ possible combinations. The empty subset (nothing selected) is the one combination we never want to test, which leaves $2^{n} - 1$ candidates. With two attributes, A1 and A2, you have three combinations: A1 alone, A2 alone, and A1 with A2 together. You build a classification model on each combination and keep the best one. With three attributes the count is $2^{3} - 1 = 7$ combinations. The number was stated as eight in class: that is $2^{3} = 8$ , the count that includes the empty subset. The running formula for the candidates we actually evaluate is $2^{n} - 1$ ; both counts are consistent once you note which one you are reporting.

Check the formula on small $n$ :

$n = 1$ : $2^{1} - 1 = 1$ — the only subset is {A1}.
$n = 2$ : $2^{2} - 1 = 3$ — {A1}, {A2}, {A1, A2}.
$n = 3$ : $2^{3} - 1 = 7$ — the three singletons, the three pairs, and the full set {A1, A2, A3}.
$n = 5$ : $2^{5} - 1 = 31$ — already 31 models to build and compare.

Sense-check: each added attribute doubles the number of candidates. From 3 to 31 between $n = 2$ and $n = 5$ — the growth is exponential, and that is precisely the problem.

Now scale up: with 100 features you face $2^{100} - 1$ subsets — a number with about 30 digits, larger than the number of atoms in the observable universe. Building a model on each one and comparing performance is far too expensive, so nobody does an exhaustive search. The standard substitute is a greedy algorithm.

5.1.4 Greedy Selection: the Shared Idea

A greedy algorithm relies on a local factor — some local calculation that says which attribute is best right now. With 100 attributes, the local metric says A2 is the best attribute at this moment, so we choose A2 and remove it from the set. In the next iteration the same local calculation picks the best attribute from the remaining 99, say A5, and so on, iterating until performance reaches a threshold we define in advance.

Think of greedy selection like packing a suitcase for a trip you have never taken. You cannot see the whole trip in advance, so at every moment you grab the single item that seems most useful now; you never take something back because a better item shows up later. Greedy feature selection works the same way: it commits to a locally best attribute at each step and hopes the final collection is good. The analogy breaks where greedy breaks too — a locally best choice now can lock you out of a better combination later, which is exactly why greedy gives no guarantee of global optimality.

You have seen greedy algorithms before. The point is that you keep making locally optimal choices and hope they lead to a globally optimal solution. Greedy gives no guarantee of global optimality; it is a practical shortcut, not a promise. Three concrete methods implement this idea: forward selection, backward elimination, and decision tree induction.

5.1.5 Forward Selection

Forward selection starts with an empty set and adds attributes one at a time. There are two variants: forward selection based on accuracy and forward selection based on error; the walkthrough below uses accuracy.

Walkthrough: forward selection on six features A1 to A6.

Step 1 — The baseline method picks a random attribute first; some random computation hands us, say, A1. We build a classification model using only A1 and measure its accuracy on the test set: 70%.

Step 2 — We go back to the original six-attribute set and pick one more random attribute, say A4. Our subset becomes A1 and A4. We rebuild the model — a fresh model, because the feature set changed — and the accuracy climbs to 80%. Since A4 improved performance, it stays in the subset; it contributes positively.

Step 3 — We repeat. The next random pick is A6, so the subset is A1, A4, A6. The rebuilt model gives 60%. Accuracy fell from 80% to 60%, so A6 contributed negatively; we drop A6 and keep A1 and A4.

Step 4 — We repeat once more. A3 gets picked; the subset is A1, A4, A3; the model reaches 85%. If 85% was our target threshold, we stop here with the subset {A1, A4, A3}.

The sequence of accuracies, in order:

Iteration	Subset	Accuracy	Decision
1	{A1}	70%	keep going
2	{A1, A4}	80%	keep A4
3	{A1, A4, A6}	60%	drop A6
4	{A1, A4, A3}	85%	stop at threshold

Sense-check: every kept attribute raised or held accuracy (A4: 70% → 80%), every dropped one lowered it (A6: 80% → 60%). The rule of thumb matches the numbers.

Why rebuild the model at every step? The model trained on one attribute is not the same model you need for two attributes; each candidate subset gets its own model, trained and tested. We discuss train/test splitting later in this lecture; for now, the rule is that every subset's performance comes from a model built and evaluated on the data.

The method has the name stepwise, and it is based on forward selection accuracy. The number of candidate subsets is still bounded: $2^{n} - 1$ , not infinite. No one claims this is the best method; it is one legitimate way to select features.

Here is a homework-style pointer: search Google Scholar for "forward selection feature selection". The baseline version picks attributes randomly, and improved versions replace the random pick with an empirical calculation — a local, greedy rule that decides which feature enters the subset. The intuition behind the improvements: random selection wastes trials, a targeted rule does not.

5.1.6 Backward Elimination

Backward elimination works in the opposite direction. The initial set contains all six attributes, A1 to A6, and the model built on all six gives 80% accuracy. Now we drop attributes one by one and check performance. If accuracy does not drop sharply — or even improves — the dropped attribute stays out. If accuracy drops, we keep that attribute.

Walkthrough: backward elimination on the same six features.

Step 1 — Start with {A1, A2, A3, A4, A5, A6}; the model on all six gives 80%.

Step 2 — Drop A2 at random. The model built on the remaining five attributes still gives 80%. A2 was an irrelevant or redundant feature, so it stays dropped.

Step 3 — Drop A3. Accuracy is still 80%, so A3 also contributed nothing and stays out.

Stopping rule 1 (accuracy threshold): say we want at least 70% accuracy. We stop as soon as we hit 70% regardless of how many features remain.

Stopping rule 2 (feature count): say we want exactly five features. We drop exactly one attribute and stop.

Both stopping rules are legitimate; which one you choose depends on whether you care more about model quality or about a fixed model size.

Sense-check: attributes whose removal leaves accuracy unchanged were carrying no unique information — exactly the redundant or irrelevant features from Section 5.1.2. If removing A2 had crashed accuracy to 50%, that would be the signal to put A2 back.

As with forward selection, the baseline does the dropping randomly, and optimized versions replace randomness with an intelligent, greedy choice of which attribute to try dropping next.

Contrast the two methods: forward selection starts empty and adds attributes as long as performance is maintained or improved; backward elimination starts full and removes attributes as long as accuracy holds. In backward elimination, a sudden accuracy drop is the signal to retain the attribute you were about to remove.

5.1.7 Decision Tree Induction

The third method, decision tree induction, is derived from the greedy strategy. The local formula is information gain: a calculation that tells you which attribute, out of the ones left, is most important right now. Information gain comes from something called entropy. Both get their full treatment in the decision tree lecture that follows this one; for now we treat information gain as a magic box with a clear contract: higher information gain means the feature holds more information, so it is the feature to keep.

You already met entropy in this course as a measure of surprise: a coin that always lands heads has zero entropy (no surprise ever), a fair coin has maximum entropy (every toss is a surprise). Information gain measures how much an attribute reduces that surprise — how much clearer the class becomes once you know the attribute's value. The decision tree lecture formalizes both definitions; here we only need the ordering they produce.

Walkthrough: decision tree induction on A1 to A6.

Step 1 — Compute information gain for all six attributes. Suppose A4 has the highest gain, so A4 is the most relevant feature and becomes the root of the tree.

Step 2 — Iterate on the remaining set {A1, A2, A3, A5, A6}: recompute information gain for these five — note we recalculate, we do not reuse the old values, because the attribute set changed — and suppose A1 now has the highest gain; A1 is selected next.

Step 3 — Iterate on {A2, A3, A5, A6}: suppose A6 has the highest gain; A6 is selected.

The result is an ordering — A4, then A1, then A6 — and the tree is built level by level in that order: A4 at the root, A1 on the next level, A6 below it, with leaves that carry the class predictions. The tree itself reveals which features matter and which do not: attributes that never appear in the tree are treated as irrelevant and dropped.

Sense-check: the method selected exactly the same style of ordering as forward selection, but the local rule is information gain instead of a random pick — that is the "intelligent" upgrade mentioned in Section 5.1.5.

Do not worry yet about why the tree takes the shape it does; the tree-building mechanics are explained in the decision tree class. The point for feature selection is that a local formula picks the best local choice at every step, and the local choice never claims to produce a globally optimal subset.

Where do we stop? The tree is used for prediction. If the tree's prediction accuracy is 80% and our threshold is 80%, we stop there. If we set the threshold at 90% and the tree already delivers 90%, we can keep dropping attributes until accuracy would fall below 90%; at that point we retain the attributes we would have dropped.

5.1.8 Key Ideas to Take Away

Feature reduction fights the curse of dimensionality.
Redundant = same information twice; irrelevant = no information for the task.
Exhaustive subset search costs $2^{n} - 1$ model builds, which is hopeless at scale.
Forward selection adds, backward elimination removes, decision tree induction ranks by information gain; all three are greedy.

Common pitfalls:

Assuming greedy selection finds the best subset. It never guarantees global optimality — a locally good attribute chosen early can block a better combination later.
Reusing information gain values after the candidate set changes. Gain must be recomputed on the remaining attributes, because the context changed.
Forgetting that every candidate subset needs its own model. A model trained on one attribute is not valid for a two-attribute subset.
Confusing redundant with irrelevant. Tax is redundant given price (same information, different scale); a student ID is irrelevant (no information at all for the task). The two require different reasons to drop.

Recap: data reduction shrinks either the rows (sampling) or the columns (subset selection and attribute creation). Subset selection is a search for the small set of columns that keeps the class distribution intact, and because exhaustive search costs $2^{n} - 1$ model builds, all practical methods — forward selection, backward elimination, decision tree induction — are greedy. The next section turns to the second family: creating brand-new attributes instead of choosing old ones.

5.2 Attribute Creation

5.2.1 The Idea

Attribute subset selection asks "which columns do I keep?" Attribute creation asks a harder question: "which brand-new columns could do the work of several old ones?" Combining three noisy, overlapping columns into one clean column is often better than choosing among them.

Attribute creation is the second family of feature reduction. Instead of picking a subset of what you have, you combine multiple features into new ones. With five original attributes you can combine three of them and represent the data with only three attributes, so the representation is more efficient.

The sense of "creation" matters: you are creating new information — a new attribute that captures important information in the data more efficiently than the original attributes did. Compressing two or three attributes into one is exactly how you soften the curse of dimensionality. PCA is the flagship example of an attribute creation method.

The contrast that will keep returning in this lecture:

Subset selection keeps columns exactly as they are. Every surviving column is one of the originals (A1, A2, A3 from {A1, A2, A3, A4, A5}).
Attribute creation manufactures new columns. Every surviving column is a combination of originals (A1' from A1 + A2 + A3).

Subset selection chooses, attribute creation transforms. Both shrink the column count; they differ in whether the survivors are original or synthetic.

5.2.2 Feature Extraction

Feature extraction reduces the number of features by pulling out a condensed version of the data. It is typical in images: an image has a huge number of pixels, and instead of choosing all pixels we choose only the edges of the image, because edges carry a lot of information. You cut the image in a particular fashion to get those edges and apply masking operations; that is feature extraction in practice.

A photograph stored at 1 megapixel is one million columns if each pixel is a feature. But an object in the picture is recognized mostly by its edges — the boundary between the object and its background. Feature extraction runs a mask over the image that responds strongly where brightness changes sharply (an edge) and weakly elsewhere. The result replaces a million pixel values with a few hundred edge descriptors, and the classifier loses almost nothing: the edges carried the information, the uniform regions did not. Sense-check: a line drawing of a face is recognizable, even though it contains almost none of the original pixel values — the edge information survived.

5.2.3 Feature Construction

Feature construction computes a brand-new feature from existing ones. The example given: density. Mass and volume are two features in the original data set; both contribute to the curse of dimensionality. Define density as mass divided by volume:

$ρ = \frac{m}{V}$

where $m$ is the mass of the object and $V$ is its volume. The two original features are removed from the data set, and the single new attribute $ρ$ replaces them: two columns become one, and the information the pair carried is now compressed into the density column.

Why is density better than mass and volume separately? The original pair has a hidden relationship: objects made of the same material have the same mass-to-volume ratio. Mass and volume store that ratio twice, in different units; the density column stores it once, and it is the ratio that actually separates materials (wood floats, iron sinks). A textbook builds the same attribute: adding area = height × width when you have height and width. Construction is a modeling decision — the new attribute expresses a relationship the original columns only implied.

Work the construction with numbers. Object 1: mass $m_{1} = 200 kg$ , volume $V_{1} = 0.25 m^{3}$ , so $ρ_{1} = 200/0.25 = 800 kg/m^{3}$ — this object floats on water (water is about 1000 kg/m³). Object 2: mass $m_{2} = 400 kg$ , volume $V_{2} = 0.20 m^{3}$ , so $ρ_{2} = 400/0.20 = 2000 kg/m^{3}$ — this one sinks. The two objects differ in both mass and volume, but the single ratio column already separates them. Sense-check: doubling mass and volume together leaves density unchanged — the ratio, not the size, is what matters.

5.2.4 Fourier and Wavelet Transforms, and Averaging

Another way to create attributes is the Fourier or wavelength transform — this is the broad area PCA also sits under. Averages are a simpler member of the same family: you can average out several values and use the average rating as one attribute.

The idea behind the transform family: rewrite the data on a new set of axes so that the information concentrates in a few coefficients. A Fourier transform (DFT) decomposes a signal into sines and cosines at different frequencies; a wavelet transform (DWT) does the same with localized wavelets. For data reduction you keep only the strongest coefficients and discard the rest, which is why the textbooks call these lossy compression. The wavelet version has a practical advantage: it preserves local detail (a sudden spike stays visible) and gives better lossy compression than Fourier for the same number of kept coefficients. Averaging is the same philosophy without the math: replace several ratings by their mean and you have compressed several columns into one.

5.2.5 PCA as an Attribute Creation Method

Given a data set $D$ with $N$ attributes, PCA reduces $N$ to $K$ . The data set ends up with $K$ attribute vectors that represent the data best, where $K$ is far smaller than $N$ :

$K ≪ N$

The professor's statement is the operational version of the standard definition: PCA searches for $K$ orthogonal vectors that best represent the data, with $K \leq N$ . When PCA is used for reduction, $K$ is chosen much smaller than $N$ , which is what the notation $K ≪ N$ records.

Spell out the pieces of the formula:

$N$ is the number of attributes (columns) in the original data set $D$ .
$K$ is the number of principal components we keep — the new attributes.
$≪$ reads "far smaller than": $K$ is chosen so that $N - K$ weak directions are dropped.

Each of the $K$ kept vectors is a combination of the original $N$ attributes, not a copy of one of them — that is what makes PCA an attribute creation method, not a subset selection method.

The idea is to project the original data into a lower-dimensional space. Contrast with attribute subset selection: subset selection keeps a subset of the original attributes, so every surviving column is one of the originals; PCA compresses the data and creates new attributes, so the surviving columns are combinations of the originals.

Recap: attribute creation builds new columns from old ones — extraction pulls condensed versions out of raw data (edges from pixels), construction computes ratios or products that carry hidden relationships (density from mass and volume), and transforms (Fourier, wavelet) or averages compress information into fewer coefficients. PCA is the flagship creation method, reducing $N$ attributes to $K$ new orthogonal vectors with $K ≪ N$ . The next section builds the intuition for exactly how PCA finds those directions.

5.3 Principal Component Analysis: Intuition and Visualization

5.3.1 Distributions in One Dimension

Start with one attribute and a one-dimensional axis, say the x-axis. Given values like 10, 0, and 14 for points A, B, C, D, we project the values onto the line. Two shapes are possible. A uniform distribution spreads values across the whole axis — there are values at many places. A non-uniform distribution piles values in one region, leaving big gaps elsewhere — a lot of values in one place and the rest of the space empty.

Why do shapes of distributions matter for PCA at all? PCA is a hunt for where the variation is. A uniform spread means variation everywhere along the axis; a non-uniform pile means the variation is concentrated — most points sit in a narrow band, and the empty gaps carry no data. The first case needs the whole axis to describe the data, the second does not. That difference is the seed of the entire method.

5.3.2 Correlation in Two Dimensions

In two dimensions we project two attributes, cell one on the x-axis and cell two on the y-axis. Two kinds of data emerge. Correlated data: increasing the value of cell one brings an equal-proportion increase in cell two; the attributes rise together. Uncorrelated data: changing cell one produces no predictable change in cell two; there is no relation between the movements.

Correlated attributes are not redundant in the strict sense of Section 5.1.2 — they are not the same column twice — but they move together, so much of the information in one is present in the other. When two attributes rise together, the scatter plot collapses into a tilted band instead of a round cloud. PCA exploits exactly that: a tilted band has a long axis, and that long axis carries most of the variation. Uncorrelated attributes produce a round cloud, where every direction holds roughly equal variation — the hardest case for compression.

5.3.3 Why Visualization Fails in Higher Dimensions

With one attribute we read the graph in one dimension, with two attributes in two dimensions, with three in three dimensions — and by looking at those graphs we can directly see uniformity, correlation, or the absence of both. With 200 attributes there is no graph we can look at. PCA is the mathematical version of the thing we did by eye: it finds, without a picture, which directions carry the variation.

The honest problem behind the curse of dimensionality: human eyes stop working at three dimensions, but data does not. A 200-attribute data set lives in a 200-dimensional space, and no sheet of paper can show it. The eye cannot be replaced by "more careful staring" — the method must compute what the eye would see, and that computation is PCA.

5.3.4 Flattening a Low-Variance Axis

Take two-dimensional data that varies heavily along the x-axis and barely moves along the y-axis. The claim about this data: the points are heavily dependent on x and essentially constant in y. So cell two is not contributing — its values do not vary, so it carries little information — while cell one varies a lot and contributes a great deal to a classification model.

The move is to drop the dead axis: take only the x-axis and flatten the data onto it, projecting every point straight down onto the line. Even after flattening, the points are nearly the same as before; the loss of information is minimal. We replaced a two-dimensional representation with a one-dimensional one, and this happens all the time: flattening is a standard compression.

Worked example: flattening in numbers.

Points A, B, C, D with coordinates (x, y):

Point	x	y
A	1	3.05
B	2	2.98
C	4	3.02
D	5	2.96

The y values wobble between 2.96 and 3.05 — a spread of 0.09 — while x spans 1 to 5, a spread of 4. In the classification task, x separates the points; y barely distinguishes them. Projection onto the x-axis replaces each point with its x alone: A becomes 1, B becomes 2, C becomes 4, D becomes 5. Every point keeps its identity — the ordering along the axis is untouched — and the dropped coordinate varied so little that nothing was lost. Sense-check: two points close in y but far in x stay far apart after flattening; the axis that separated them survived.

5.3.5 Rotating the Axes: Principal Components

Now take data with real variation in both directions. On the x-axis there is a good amount of variation; on the y-axis there is also a good amount. But we can do better: draw a diagonal line through the data — connect the two extreme points and extend — and along that direction the variation is huge. Draw the perpendicular to it, and along that perpendicular there is variation too, but far less.

So we have two new axes: call them X1 (the diagonal, high variation) and Y1 (the perpendicular, low variation). We tilted the original axes: the original x and y are replaced by X1 and Y1. X1 holds the maximum amount of information, Y1 holds little, and we can drop Y1 if we like.

The formal definition (in words, then in symbols). The direction of maximum variance is called the first principal component, PC1; the direction of the second-highest variance, perpendicular to the first, is PC2; and the sequence continues. What we create is a set of orthogonal vectors in the data space, one per principal component. Orthogonal means every pair of them is at right angles — perpendicular — so none of them repeats information that another already carries. With two-dimensional data we produced two new attributes, X1 and Y1, out of X and Y, and whether we keep both is our choice; the ideal case keeps fewer attributes to reduce the feature count. We drop PC2 by projecting all points onto the PC1 line, losing a bit of information, which is fine — more on that in a moment.

Standard terminology, matching the lecture: the first principal component is called the primary PC, the second the secondary PC. Textbooks sometimes write PC1 and PC2 instead; the terms mean the same two directions, ordered by decreasing variance.

Visual intuition. Picture the scatter plot: x-axis horizontal, y-axis vertical, points forming a cigar-shaped cloud tilted at about 45 degrees. The long axis of the cigar is X1: it runs from one extreme corner of the cloud to the opposite corner, and the spread of the points along it is large — the dots are far apart when measured along this line. The short axis of the cigar is Y1, perpendicular to X1, and the spread along it is small — the dots cluster tightly around the middle line. Landmarks: the ends of the cigar are the extremes of PC1 (the two extreme points we connected), the middle of the cigar is where the point density peaks. Takeaway: rotate the axes to align with the cigar, and one of the new axes describes the data almost completely.

Worked example: rotating axes.

Four points form a tilted cigar: A = (1, 2), B = (2, 1), C = (7, 6), D = (8, 5). Along the original x-axis the values run 1 to 8 (spread 7); along the original y-axis they run 1 to 6 (spread 5) — both directions vary. Now connect the extremes: A to D is a line with slope 1 (from (1,2) to (8,5)); B to C is nearly the same line. Take that diagonal as X1. Project the points onto it: A lands near one end, D near the other, and the projected positions are spread over almost the whole line — the variation along X1 is roughly 8. Along Y1 (perpendicular, slope −1) the points sit close together: A and B differ from the diagonal by about one unit in each direction, C and D likewise — the variation along Y1 is small. Drop Y1: each point keeps only its position along the diagonal, and the four points remain fully distinguishable. Sense-check: a vertical line drawn through the original cloud would mix the points, but along X1 they separate cleanly — the rotated axis separated the data better than either original axis.

5.3.6 PCA Is a Lossy Transformation

Attribute subset selection and PCA are both lossy transformations. You lose information and you may not be able to recover the original data — you cannot go back — yet they are still useful because the dimensionality drops. The trade is accepted every day in feature reduction.

Scope — when the lossy trade is safe and when it is not. Dropping low-variance directions is safe when those directions genuinely carry little variation: the projected points are nearly the same as the originals, and models built on the projection behave nearly the same. It is not safe when variation was discarded because of bad data rather than small data — see the outlier warning in Section 5.3.8. And note the direction of the trade: PCA tells you how much variance each direction carries, so you choose the loss; the textbooks express this by keeping the strongest principal components and reconstructing an approximation of the original data from them. The approximation is the point: an approximate picture you can compute beats an exact picture you cannot.

5.3.7 The 3D-to-2D Analogy: Seeing, Pictures, and TV

Think about how you see. With your eyes you look at the world in three dimensions: left to right, top to bottom, and depth — put one point in front of you and another behind it and you perceive depth easily. A TV screen is two-dimensional; it projects everything onto two axes. Yet when you watch a good nature image on TV, you still get most of the information. Real versus picture: stand on a hill and you see the scene in 3D with the feel of the moment; take a picture and look at it — the depth is gone, but the picture still holds a lot of information.

The same logic applies to 3D data projected to 2D: we do this all the time and lose surprisingly little. That is why PCA is very relevant these days — it is the mathematical cousin of photography, projecting high-dimensional reality into a lower-dimensional picture while retaining the majority of the information.

Where the analogy holds and where it breaks. A photograph keeps the two axes with the most visible variation — width and height — and discards depth, the third axis, whose loss your brain barely notices. PCA keeps the directions with the most variance and discards the rest, which is why it is often described as "photographing" the data. The analogy breaks in scale: a photo discards one of three axes, while PCA routinely drops hundreds out of thousands — but the principle is identical, and the surprise is the same: we lose surprisingly little, because most of the information lives in a few directions.

5.3.8 Warnings Before Running PCA

Outliers corrupt PCA. If you run PCA on data with outliers, the principal components may go bad and give you wrong directions. The workflow is: do outlier analysis first, remove the outliers during preprocessing, and only then run PCA on the cleaned data. Outlier handling is a separate concern; PCA is not a tool for removing outliers.

Why one outlier can tilt the answer. Five points sit near the origin, and one stray point sits at (100, 99). The variance along the diagonal pointing at the stray point is enormous — the squared distance to that point dominates the sum. PCA maximizes variance, so the first principal component tilts toward the outlier, and the component that should describe the bulk of the data instead points at one bad row. Remove the outlier and the component snaps back to the true cigar direction. Sense-check: variance is a sum of squared distances, and one large distance can outweigh many small ones — that is the mathematical reason outliers must be cleaned before PCA.

5.3.9 Student Questions and Answers

Q: Does normalization also affect attribute subset selection? A: Yes. Normalization changes the absolute values of the attributes, and since attribute selection methods work on those values, a change in scale can change which attributes get selected. This matters even more for PCA: the textbooks normalize first so that attributes with large domains (say, income in thousands) do not dominate attributes with small domains (say, age in years). Without normalization, a large-domain attribute gets treated as high-variance for the wrong reason — because its units are big, not because its information is big.

Q: If we convert 3D data to 2D data, is there data loss? For example, when a 3D picture becomes a 2D picture we no longer see the depth. A: Yes, there is data loss, but think about it: when you watch a 2D movie in a theater you still get a good experience — not as good as a 3D movie, but acceptable. You do this all the time. PCA works the same way: we keep the maximum-variance features, drop the low-variance ones, and we can still build a model. We lose information, and we manage without it. That is the whole point of feature reduction: dropping attributes always loses some information, and that is a lossy transformation you accept.

Recap: PCA finds, without a picture, the directions in which the data varies most. The first principal component is the direction of maximum variance, the second is the perpendicular direction with the next-highest variance, and so on; dropping the weak directions is a lossy compression whose everyday version is photography — 3D scenes become 2D pictures and nearly everything important survives. Clean the outliers first, normalize before you start, and you can reduce hundreds of columns to a handful of new ones. The next section closes preprocessing with discretization: turning continuous values into a few representative ones.

5.4 Discretization

5.4.1 Converting Continuous Attributes into Ordinal Attributes

Discretization is the last preprocessing step. The idea is simple: convert a continuous attribute into an ordinal attribute. Instead of keeping every one of a stream of distinct values, you map them onto a small set of representative values.

The one-sentence hook: a continuous column can hold infinitely many distinct values, but most mining algorithms work with a handful of categories — so discretization asks the data to speak in categories instead of decimals.

The visual version: a continuous value can be written as 1.00000000 with infinitely many decimals. Round it to two decimal places and you get 1.00; round to one decimal place and you get 1.0; round to no decimals and you get 1. That rounding-off is discretization: a continuous value moved into a discrete value.

Why bother? Discretization saves a lot of computation. Continuous data with many variations is hard to handle, and an ordinal version of the same attribute is cheap to process.

Worked example: rounding as discretization.

Take the value $1.00000000$ (eight decimals).

Round to two decimal places: $1.00$ .
Round to one decimal place: $1.0$ .
Round to no decimals: $1$ .

The continuous stream of possible values collapsed into three levels — 1.00, 1.0, 1 — and at the last step every value in the interval $[0.5, 1.5)$ becomes the single category $1$ . A data set of a thousand distinct values becomes a data set of a few categories, and every operation on it gets faster. Sense-check: the rounded version is a faithful but coarser picture — you traded precision for speed, exactly the discretization trade.

5.4.2 Strategies: Equal Interval Width, Equal Frequency, Histograms

Two named strategies exist: equal interval width and equal frequency. A histogram is one form of discretization — binning the values into intervals is exactly the rounding-off idea, applied at scale. In some cases the histogram route works fine for a given variable.

Equal interval width: divide the attribute's range into intervals of identical width, like slicing a ruler into equal pieces. If ages run from 0 to 90 and you want three intervals, they are 0–30, 30–60, 60–90 — each 30 wide. Simple to compute, but a few extreme values can spread the intervals so thinly that most data lands in one bucket.

Equal frequency (equal depth): divide the sorted values so that each interval holds roughly the same number of data points. If 100 ages are sorted and you want four intervals, each holds about 25 points. The intervals adapt to where the data actually is — dense regions get narrow intervals, empty regions get wide ones — which makes this strategy more robust when the distribution is skewed.

Histograms: a histogram is the same idea drawn: buckets on the x-axis, counts on the y-axis. Building a histogram with equal-width buckets is equal-interval discretization, and with equal-frequency buckets it is equal-frequency discretization. The textbooks also use histograms with singleton buckets (one value per bucket) to isolate high-frequency outliers.

Worked example: the two strategies on the same data.

Twelve measurements: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 90, 91.

Equal interval width with 3 intervals over the range 1 to 91: 1–31, 31–61, 61–91. Bucket 1 swallows ten of the twelve points; buckets 2 and 3 hold one point each. The huge gap between 10 and 90 means the width strategy wastes two buckets on two points.

Equal frequency with 3 intervals: sorted values split into three groups of four — {1,2,3,4}, {5,6,7,8}, {9,10,90,91}. Every bucket now holds the same number of points, and the outlier pair (90, 91) is isolated instead of stealing half the range. Sense-check: equal width is defined by the ruler, equal frequency by the data — on skewed data the frequency version uses the buckets where the points are.

5.4.3 Student Questions and Answers

Q: I did not get what discretization means. A: It is just rounding. Take a value like 1.0000000...; round it to two decimals (1.00), or one decimal (1.0), or none (1). A continuous value becomes a discrete value. A histogram is one kind of discretization, and if you look at a variable rounded to two decimal places, that is discretization in action.

Exam note: discretization is a covered topic in the quiz syllabus. Know the two named strategies — equal interval width and equal frequency — and the histogram as a discretization tool, plus the rounding picture that defines the whole idea: continuous in, a few representative levels out.

Recap: discretization converts a continuous attribute into an ordinal attribute by mapping many distinct values onto a few representative ones — rounding is the smallest case, histograms are the large-scale version, and equal-width versus equal-frequency decides how the intervals are cut. This closes preprocessing; the lecture now turns from preparing the data to the fourth module: classification and prediction.

5.5 Supervised versus Unsupervised Learning

5.5.1 Unsupervised Learning: Only X

We now start the fourth module, classification and prediction. First, a recap of supervised versus unsupervised learning.

Unsupervised learning gives you only the data, X: a table of tuples T1 to Tn described by attributes A1 to Am. There is no target column. The goal is to find patterns and structure in the data — not to predict anything. The canonical example is clustering: you run a clustering algorithm and the data splits into clusters, where points inside one cluster are very similar to each other compared with points in other clusters. The pattern you extracted is precisely that: point P1 is similar to point P2 (same cluster) and very different from point P3 (different cluster). You could state that only after building the clustering model; the model is what turned raw X into this statement.

Unsupervised learning answers "what is here?" before anyone tells it "what to predict." The classic picture: a supermarket lays out thousands of customer purchase records (rows) with no labels at all, runs clustering, and discovers that customers split into groups — budget shoppers, premium shoppers, weekend shoppers. The groups were not named in the data; the algorithm found that they exist. The lecture's phrasing captures the same idea: unsupervised learning finds structure; it does not predict.

5.5.2 Cluster Boundaries and Tiebreakers

A point can land on the border of two clusters, and then you need a tiebreaker. Two typical tiebreakers were suggested. Distance from the cluster center: if the border point is much closer to the center of the smaller cluster, assign it there. Number of points in the cluster: adding the point to the bigger cluster gives it one more data point, and that extra point brings more information, so size can win. Any tiebreaker you define is legitimate; the design choice is yours.

Scope — tiebreakers are an edge-case policy, not the main algorithm. Clusters are discovered by similarity, and most points belong to one cluster unambiguously; only points on the boundary need a policy. The lecture offers two legitimate ones: distance to the cluster center (assign to whichever center is nearer — the smaller cluster wins if it is much closer), and cluster size (assign to the larger cluster, because one more point is more useful there — richer data for the bigger group). Both are defensible, which is the real lesson: the tiebreaker is a design choice, and any consistent rule you define is legitimate. The trap is forgetting that the rule exists and letting border points be assigned by accident.

5.5.3 Supervised Learning: X and Y

Supervised learning gives you two things: X and Y. X is the same table — tuples T1 to Tn, attributes A1 to Am — and Y is an extra column of class labels. The idea is to learn a model that predicts Y for new, unseen rows.

Unsupervised learning only finds structure; supervised learning performs prediction. In the geometric picture, supervised learning builds a line, a plane, or a curve that separates the classes, and every new point is classified by which side of that boundary it falls on.

The two boxes side by side:

	Unsupervised	Supervised
What you get	Only X — tuples and attributes	X plus Y — a column of class labels
Goal	Find structure and patterns	Learn a model that predicts Y for new rows
Example	Clustering splits data into clusters	Classification draws a boundary between classes
Output statement	"P1 is similar to P2, different from P3"	"This new point is class dot, not class cross"
Prediction?	No	Yes

When to pick which: use unsupervised when you want to discover what is in the data; use supervised when you have labels and want to predict them for unseen data.

Recap: the supervised/unsupervised split is about what the algorithm receives. Only X — find structure (clustering); X and Y — learn to predict (classification). The next section formalizes the supervised branch: what classification is, how a boundary is drawn, and how a new point gets its class.

5.6 Classification

5.6.1 What Classification Is

Definition: given a collection of records — call it training data — where each record consists of X, the input, along with Y, the class label, the task is to learn a model, a border, that predicts the class label for a new X.

A binary classification problem has two classes. Picture a graph with two classes, dots and crosses, already scattered over it. Building a classification model means drawing a line that separates them. A test point arrives — a circle, say — and its predicted class is whatever side of the line it falls on. In the example, the test point on the left side of the separating line is predicted as dot.

Classification is a two-stage process: model training and model testing.

Training: the algorithm sees records whose labels are known — dot or cross — and learns the boundary that separates them.
Testing: new records, whose labels are unknown, are classified using the trained model — the boundary assigns each one by the side it falls on.

Classification predicts a discrete, nominal value — a class label from a fixed set (dot/cross, pass/fail, spam/not-spam). This is the property that distinguishes it from regression, covered in Section 5.6.4.

The professor's one-line summary, worth memorizing: classification is always about building a line, plane, or curve that separates the classes. If you can separate the classes properly, you have built a classification model. Two classes give a line; three classes in a plane give a set of boundary lines; more classes in more dimensions give a surface — but the picture is always the same: a boundary, and sides.

5.6.2 Worked Example: Pass or Fail with Two Subjects

Binary classification, classes pass and fail. The x-axis holds marks in subject S1, the y-axis holds marks in subject S2, and every point is a student. Students who failed sit in the low-low corner, students who passed sit in the high-high corner, and the classes visibly separate.

We draw a boundary: a vertical line at marks M1 on the S1 axis and a horizontal line at marks M2 on the S2 axis. The classification model is one rule:

$class (S_{1}, S_{2}) = {pass, fail, if S_{1} > M_{1} and S_{2} > M_{2} otherwise$

Here $S_{1}$ is the student's marks in subject S1, $S_{2}$ is the marks in subject S2, $M_{1}$ is the threshold on the S1 axis, and $M_{2}$ is the threshold on the S2 axis. In words: if a student's marks in S1 are greater than M1, and marks in S2 are greater than M2, the student passes; in any other case, the student fails.

Worked example: the rule in action.

Suppose the thresholds are $M_{1} = 40$ and $M_{2} = 40$ , and two students arrive.

Test point one: marks in S1 above M1 and marks in S2 above M2 — say (55, 60). Check the rule: $55 > 40$ is true and $60 > 40$ is true, so both conditions hold — the student passes.

Test point two: marks in S1 below M1 — say (30, 95). Check the rule: $30 > 40$ is false, and the rule demands both conditions, so the student fails — fails, before we even check S2. Even a perfect score in the second subject cannot rescue the first.

The boundary itself is the two lines $S_{1} = 40$ and $S_{2} = 40$ ; the pass region is the rectangle they cut off in the top-right corner. Sense-check: every point in the top-right rectangle passes, every point outside it fails — the rule and the picture agree.

5.6.3 Rule-Based Classification

The pass/fail model is an example of rule-based classification. Sometimes we see the boundary visually and write the rule directly, as above; sometimes we compute the rule with mathematics. Rule-based classification gets its own treatment later in the course.

5.6.4 Classification versus Regression

Both classification and regression are supervised learning; both predict something. The difference is the target column.

In classification, Y holds discrete values: a fixed set of class labels. Weather prediction — will it be hot or cold tomorrow — has two labels, hot and cold. Rainfall prediction — will it rain or not — has two labels, yes and no.

In regression, Y holds continuous values. What will the price of petrol be tomorrow — a continuous number like 100.2 or 100.02 — and what amount of rainfall will occur — 1 cm, 5 cm, 50 cm — are regression problems. You predict a continuous value, not a class label.

Worked example: regression — car price against mileage.

The x-axis is mileage, the y-axis is the cost of the car. Known cars C1, C2, C3 give three points: each mileage value maps to a cost. Say C1 = 20,000 km at 18,000; C2 = 60,000 km at 12,000; C3 = 100,000 km at 7,000. To predict the price of a car with a new mileage, fit a line (or curve or plane) through the points so that the error is minimum for the majority of them — the line overlaps the points with minimum total error. A candidate line with slope about −0.1375 and intercept near 20,750 passes close to all three points, and no other line is closer overall to them. Then read the predicted price off the fitted line at the new mileage: at 80,000 km the line gives about 9,750. Regression means connecting the points with a fitted curve so that you can predict another point on the same curve. Sense-check: the prediction is plausible — more mileage, lower price, and the new point sits between the observed ones.

Q: Can we add an error estimate to the predicted car price? A: Yes, you can add an estimate on top of the prediction. The rule is that the regression line gives the single best prediction, and attaching an estimate (for example, a range or an uncertainty interval around the predicted price) is allowed — the prediction does not have to be a bare number. The response details were garbled in the source; the accepted answer is that attaching an estimate is allowed.

5.6.5 Hypothesis Space and Performance Measures

The supervised setup: input X, class label Y, and we predict Y-hat, the model's output. To build the separating line we have a huge space of options, called the hypothesis space — a large collection of classification algorithms, each able to draw the line: decision tree algorithms, rule-based methods, neural networks, LSTM models, and so on. They all solve the same task; they differ in how they draw the boundary.

Model selection works in three dimensions: the input vector, the hypothesis space, and performance. On a given data set, algorithm C1 gives performance P1, algorithm C2 gives P2, algorithm C3 gives P3; you compare P1, P2, and P3 and choose the algorithm with the best performance for your data. In practice you apply four or five algorithms to a data set and pick the winner.

The hypothesis space is not flat. It contains subspaces: machine learning algorithms, bagging-based algorithms, boosting-based algorithms, deep learning-based algorithms, each a subspace of the bigger space. All can build classification models; you measure each one's performance, compare, and choose the best model. One more thing to note: each category of algorithm suits a specific category of data — that is a topic for later. The consequence today: do not ask "which algorithm is best?" in the abstract; ask "which algorithm performs best on this data set?" and let the measured performance P1, P2, P3 decide.

5.6.6 Real-World Classification Tasks

Email categorization: a classifier checks each incoming email and moves it to the spam or advertisement folder or to the proper inbox. Two classes: spam and non-spam.
Malware detection: antivirus software examines each file, finds features that separate malware from benign files, and labels the file malware or good.
Tumor cell identification: looking at an image, the classifier says whether it contains tumor cells or benign cells.

5.6.7 Student Questions and Answers

Q: Do different clusters follow different models? A: The question needs rephrasing, but the core distinction is this: supervised learning gives you both X and Y, and you can predict for test data — you build a line, plane, or curve that separates classes. Unsupervised learning gives you only X, and you only find structure in the data. Classification is supervised; clustering is unsupervised.

Common pitfalls:

Confusing the two problem types: classification outputs a label from a fixed set (hot/cold, yes/no); regression outputs a continuous number (100.2, 50 cm). The same weather task can be either: "will it rain?" is classification, "how much rain?" is regression.
Forgetting the two-stage process: the model is built on labeled training data and applied to new test data; judging a model on the data that trained it overstates its quality (test/train splitting returns in detail later).
Misreading the pass/fail rule: the condition uses and — both marks must exceed their thresholds. A single mark below its threshold fails the student regardless of the other subject.
Treating the hypothesis space as one algorithm: it is a collection of algorithm families; selection means measuring each on your data, not picking by reputation.

Recap: classification learns a separating boundary from labeled training data and assigns classes to new points by the side they fall on. The pass/fail rule shows the whole idea in one formula; the contrast with regression is the shape of Y (discrete labels versus continuous values); and the hypothesis space is where the many candidate boundaries live, with performance measures deciding the winner. This closes the lecture: preprocessing gave us reduced, discretized data, and classification gave us the first prediction task to run on it.

Exam Guidance Summary

Quiz 1 runs from 13 February to 23 February (2023). It is an objective-type quiz — multiple-choice questions — and must be finished within the given time window on those dates. No extension of quiz dates is possible.
Exam note: the quiz syllabus is everything covered up to and including today's class, so attribute subset selection, attribute creation, PCA intuition, discretization, and the classification introduction are all inside the quiz syllabus.
Exam note: the quiz platform is the course's learning portal (Takshila), not the video-conferencing tool. All quizzes and assignments run there.
Exam note: quiz duration is not fixed — you may take 10 minutes, 50 minutes, or 60 minutes. The number of questions is not disclosed.
Exam note: ideally you complete the quiz in one go rather than in several sittings.
Tutorials are pre-recorded and live on Microsoft Teams. Tutorial 1 covers Python, pandas, and NumPy basics; tutorial 2, on data preprocessing, appears at the start of the next week. Assignments assume you worked through the tutorials.
Data mining textbooks are available for download on the learning portal; reference books are listed at the end of every module for deeper reading.
Research papers are being uploaded continuously; reading the original papers end to end, even though they are hard, gives insight into why each algorithm was designed the way it was.
Exam note: information gain, entropy, and tree construction are covered in the next class (decision trees); expect the full treatment there.
Homework: search Google Scholar for "forward selection feature selection" to see the improved, non-random variants.
Read about the curse of dimensionality; it is the motivation behind every feature reduction method in this lecture.

Key Industry Applications

Real-world: spam filtering in email — a two-class classifier decides inbox versus spam for every message.
Real-world: antivirus and malware detection — file features decide malware versus benign.
Real-world: medical imaging — image classifiers identify tumor cells versus benign cells.
Real-world: weather and rainfall prediction — hot/cold and yes/no are classification problems; rainfall amount is a regression problem.
Real-world: fuel pricing and used-car pricing — petrol price tomorrow and car price from mileage are regression problems.
Real-world: retail and tax — purchase price and tax paid are nearly redundant features, because tax is a fixed percentage of price.
Real-world: image processing — feature extraction from images (edges, masking) replaces thousands of pixels with a few informative features.
Real-world: photography and television — 3D scenes are projected to 2D with acceptable loss, the everyday version of what PCA does to data.
Real-world: PCA is widely used in industry today to compress high-dimensional data before modeling, because the maximum-variance directions retain most of the information.

DM Lecture 5 notes · Data Reduction, Discretization, and Classification

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

1Attribute Subset Selection

Redundant and irrelevant features, the cost of exhaustive search, and the three greedy methods: forward selection, backward elimination, and decision tree induction

2Attribute Creation

Feature extraction, feature construction, Fourier and wavelet transforms, averaging, and PCA as an attribute creation method

3Principal Component Analysis: Intuition and Visualization

Distributions and correlation, flattening low-variance axes, rotating to principal components, the lossy trade, and the 3D-to-2D analogy

4Discretization

Converting continuous attributes into ordinal attributes by rounding, equal interval width versus equal frequency, and histograms

5Supervised versus Unsupervised Learning

Only X versus X and Y, what clustering finds, and cluster-boundary tiebreakers

6Classification

The separating-boundary model, the pass/fail rule, classification versus regression, and the hypothesis space

7Exam Guidance Summary

Quiz logistics, syllabus coverage, tutorials, textbooks, and homework pointers

8Key Industry Applications

Spam filtering, malware detection, medical imaging, pricing and weather prediction, and PCA in industry

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Attribute Subset Selection

Must-know: Attribute subset selection removes redundant (same info twice, e.g. price/tax) and irrelevant (no info for task, e.g. student ID) attributes; all practical methods are greedy because exhaustive search costs 2^n - 1 subsets.

$2^{n} - 1$

⚠️ Top pitfall: Assuming greedy selection finds the globally optimal subset; greedy gives no guarantee of global optimality.

Self-check: With 3 attributes, how many non-empty subsets must an exhaustive search evaluate? (7 = 2^3 - 1)

Connects to: Attribute Creation; Principal Component Analysis: Intuition and Visualization

Attribute Creation

Must-know: Attribute creation builds new columns from old ones: feature construction (density = m/V, area = height x width), feature extraction (edges from pixels), transforms; PCA reduces N attributes to K orthogonal new vectors, K << N.

$ρ = \frac{m}{V}$

⚠️ Top pitfall: Confusing subset selection (keeps original columns) with attribute creation (surviving columns are combinations of originals).

Self-check: Which method keeps original columns: attribute subset selection or PCA? (subset selection)

Connects to: Attribute Subset Selection; Principal Component Analysis: Intuition and Visualization

Principal Component Analysis: Intuition and Visualization

Must-know: PC1 is the direction of maximum variance (primary PC), PC2 is the perpendicular direction of second-highest variance (secondary PC); PCA is lossy, needs normalization, and outliers must be removed before running it.

⚠️ Top pitfall: Running PCA on data with outliers - one extreme point tilts the first principal component toward it.

Self-check: What must be done to outliers before running PCA? (outlier analysis and removal during preprocessing)

Connects to: Attribute Subset Selection; Attribute Creation

Discretization

Must-know: Discretization = rounding a continuous value into a discrete one; two named strategies: equal interval width (fixed-size intervals) and equal frequency (roughly equal counts per interval); histograms are discretization.

⚠️ Top pitfall: Using equal-width intervals on skewed data - a few extreme values spread the intervals so thinly that most points land in one bucket.

Self-check: What are the two named discretization strategies? (equal interval width and equal frequency)

Connects to: Attribute Subset Selection

Supervised versus Unsupervised Learning

Must-know: Unsupervised: only X, finds structure (clustering, no prediction). Supervised: X and Y, learns a model that predicts Y for new rows (classification builds a separating boundary). Border points need a tiebreaker (distance to center, or cluster size).

⚠️ Top pitfall: Forgetting that a tiebreaker rule must be defined for border points - assignment cannot be left to chance.

Self-check: Which kind of learning gets both X and Y? (supervised)

Connects to: Classification

Classification

Must-know: Classification predicts a discrete class label with a separating boundary built from training data; pass iff S1 > M1 AND S2 > M2; regression predicts continuous values; hypothesis space = collection of algorithm families compared by measured performance.

$class (S_{1}, S_{2}) = {pass, fail, if S_{1} > M_{1} and S_{2} > M_{2} otherwise$

⚠️ Top pitfall: Misreading the AND in the pass/fail rule: one mark below its threshold fails the student regardless of the other subject.

Self-check: Is 'how much rain will fall?' classification or regression? (regression - a continuous value)

Connects to: Supervised versus Unsupervised Learning

Exam Guidance Summary

Must-know: Quiz 1 is MCQ on Takshila 13-23 Feb, no fixed duration, no extension; syllabus = everything through today (subset selection, attribute creation, PCA intuition, discretization, classification intro); complete it in one go.

⚠️ Top pitfall: Missing the quiz window - no extension of quiz dates is possible.

Self-check: Where do quizzes and assignments run? (the course learning portal, Takshila)

Connects to: Attribute Subset Selection; Attribute Creation; Principal Component Analysis: Intuition and Visualization; Discretization; Classification

Key Industry Applications

Must-know: Named applications: email spam filtering, antivirus malware detection, tumor cell identification (classification); weather/rainfall and fuel/car pricing (regression); price/tax redundant features; image edge extraction; PCA compression in industry.

Self-check: Is predicting petrol price tomorrow classification or regression? (regression)

Connects to: Classification

Previous LectureLecture 04 · Data Preprocessing: Noise, Integration, Transformation, and Reduction

Next LectureLecture 06 · Classification, Performance Measures, and Overfitting

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

5.1 Attribute Subset Selection

5.1.1 The Two Ways to Reduce Data: Volume versus Features

5.1.2 Redundant and Irrelevant Features

5.1.3 The Cost of Exhaustive Search

5.1.4 Greedy Selection: the Shared Idea

5.1.5 Forward Selection

5.1.6 Backward Elimination

5.1.7 Decision Tree Induction

5.1.8 Key Ideas to Take Away

5.2 Attribute Creation

5.2.1 The Idea

5.2.2 Feature Extraction

5.2.3 Feature Construction

5.2.4 Fourier and Wavelet Transforms, and Averaging

5.2.5 PCA as an Attribute Creation Method

5.3 Principal Component Analysis: Intuition and Visualization

5.3.1 Distributions in One Dimension

5.3.2 Correlation in Two Dimensions

5.3.3 Why Visualization Fails in Higher Dimensions

5.3.4 Flattening a Low-Variance Axis

5.3.5 Rotating the Axes: Principal Components

5.3.6 PCA Is a Lossy Transformation

5.3.7 The 3D-to-2D Analogy: Seeing, Pictures, and TV

5.3.8 Warnings Before Running PCA

5.3.9 Student Questions and Answers

5.4 Discretization

5.4.1 Converting Continuous Attributes into Ordinal Attributes

5.4.2 Strategies: Equal Interval Width, Equal Frequency, Histograms

5.4.3 Student Questions and Answers

5.5 Supervised versus Unsupervised Learning

5.5.1 Unsupervised Learning: Only X

5.5.2 Cluster Boundaries and Tiebreakers

5.5.3 Supervised Learning: X and Y

5.6 Classification

5.6.1 What Classification Is

5.6.2 Worked Example: Pass or Fail with Two Subjects

5.6.3 Rule-Based Classification

5.6.4 Classification versus Regression

5.6.5 Hypothesis Space and Performance Measures

5.6.6 Real-World Classification Tasks

5.6.7 Student Questions and Answers

Exam Guidance Summary

Key Industry Applications

DM Lecture 5 notes · Data Reduction, Discretization, and Classification

Sections Breakdown

Exam Revision Notes

Attribute Subset Selection

Attribute Creation

Principal Component Analysis: Intuition and Visualization

Discretization

Supervised versus Unsupervised Learning

Classification

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat