Spark MLlib: Regression, Classification, Clustering, and Collaborative Filtering

This lecture is an entry point into machine learning with PySpark's MLlib library. Four techniques are covered — regression, classification, clustering, and collaborative filtering — with hands-on code snippets for the first three. The treatment is deliberately introductory: the audience has not seen machine learning before, so the first part of the session builds the vocabulary (what learning means, what supervised and unsupervised learning are), and the rest applies that vocabulary to real PySpark code running against a Spark cluster.

Along the way the session works a complete path: it defines machine learning, splits the field into supervised and unsupervised learning, separates regression from classification, derives the error metrics used to fit a straight line, then shows each idea running as a real program — linear regression on the Boston housing data, a decision tree on wine-quality data, and k-means on a tiny synthetic file. The session closes with the two recommendation approaches. Everything in the session is examinable, and the practical rules (maximum information gain, minimum gini, follow the L1 or L2 instruction given in the problem) are the ones that recur in exam questions.

8.1 What Machine Learning Is

8.1.1 The 1959 definition and why it stayed theoretical

Machine learning is an old term — almost six decades old by now. The first author to define it was Arthur Samuel, who coined the definition in 1959: it is a field of study that gives computers the ability to learn without being explicitly programmed.

To see how different that is from ordinary programming: in a conventional program we feed instructions to the computer — rules that say exactly how to perform the task. We give it input, it applies the rules, and it generates output. That is how a computer typically works. Samuel's definition flips the emphasis: instead of writing the rules ourselves, the computer discovers them from data.

8.1.2 Why machine learning could not take off in 1959

The definition existed, but the field could not be leveraged at that moment, for two practical reasons:

1. Machine learning needs high computing power. The data being processed is large in volume, and learning algorithms over that data are computationally heavy.
2. Machine learning needs large datasets. More data is required to achieve more accuracy.

In 1959 neither abundant computing power nor abundant data existed. Neither was available in abundance, so the benefit of the concept could not be taken.

8.1.3 Mitchell's task–performance–experience definition (late 90s)

Moving forward to the late 90s, Tom Mitchell defined machine learning more operationally: machine learning is a field of study of algorithms that improve their performance \(P\) at some task \(T\) with experience \(E\).

Break that down:

• \(T\) — the task you give the algorithm.
• \(P\) — the performance measure: how well it is performing, how well it is learning.
• \(E\) — the experience: the data you feed it.

It is a three-variable tuple: performance, task, and experience. Given a task and given a certain experience, you evaluate the performance. The central idea: give the algorithm more experience and its performance should improve.

8.1.4 The canonical example: email spam filtering

The classic example used to make this concrete is email spam filtering — classifying emails as spam or not spam.

• Task \(T\): classify each email as spam or not spam.
• Experience \(E\): historical emails that already carry certain attributes and a label saying whether each one is spam or not spam. This is what is called labeled data (labeling is discussed later under the two categories of machine learning algorithms).
• What the system does: it learns something out of those labeled emails and applies the same rules it has learned to unseen emails, classifying each as spam or not spam.
• Performance \(P\): how many emails it is able to correctly classify as spam or not spam. Give the model more emails to learn from and performance should improve.

Real-world & domain connection. The spam filter is not just a classroom example — it is the canonical first machine learning application in the industry, and it still runs on every major email service. The same T-P-E pattern generalizes everywhere: recommend a product (\(T\)), the user's past purchases (\(E\)), fraction of recommendations accepted (\(P\)); or predict the next day's traffic (\(T\)), historical sensor readings (\(E\)), mean prediction error (\(P\)). In the broader field, this definition is the entry point to the whole machine learning course: once you can name the task, the experience, and the performance measure for any problem, you have already done the first step of modelling it.

8.2 Supervised vs Unsupervised Learning

Whenever machine learning is introduced, these two terms come up immediately, because the whole field divides along this line. The division depends on one thing: does the training data come with the desired output or not?

8.2.1 Supervised learning

In supervised learning you have a dataset, called the training data, from which the model learns. The training data includes the desired output — the answer for each training instance. In the spam example, the model is told "this is a spam email" and "these are the rules of a spam email" and "these are the rules of a genuine email". Because the desired output is given to the system, this kind of data is called labeled data.

The house-price example makes the structure explicit. Suppose a real estate agency hands over the records of past house purchases in a city. The attributes available are:

• plot size
• number of bedrooms
• covered area
• whether there is granite flooring
• whether the kitchen is upgraded
• distance from the city, in kilometers
• age of the flat, in years
• price, as the final attribute

The first seven attributes are the input attributes to the system; the price is the output attribute. Because both inputs and outputs are present — these are historical sales that have already happened — the data is labeled. This kind of data, presented as input attributes plus the desired output, is called training data with desired output, and it is what supervised learning problems use. The model learns from these attributes how to predict the price; later, given a new instance with the same seven attributes, it should predict the price of that house.

8.2.2 Unsupervised learning

In unsupervised learning we have only the training data — only the input attributes — and no desired output; the data is unlabeled. Take the same house dataset and remove the price column: without the price of historical sales, it becomes very difficult to predict a price, because the desired output is simply not there.

But something else can be done with such data: grouping. The houses can be grouped by number of bedrooms — a buyer interested only in a 3 BHK flat should be shown only the 3 BHK flats — or by plot size, or by distance from the city. Creating groups out of the data without any desired output is exactly the shape of an unsupervised learning problem.

8.2.3 Student question: is a model the same as an algorithm?

8.2.4 Uses of unsupervised learning

Examples or use cases of unsupervised learning:

• Market segmentation — you have customer details and want to categorize them under different heads: high-income, low-income, middle-income, or high-spend vs low-spend customers. This is done for better targeting, for example to decide whom to market a new product to.
• Recommendation systems — almost every website has one today: any electronic store, any e-commerce website, and OTT platforms all build recommendations.
• Social network analysis — again an unsupervised learning task.

8.3 Regression vs Classification

Regression and classification are both supervised learning problems — in both cases you have labeled data — so the difference is not in the data. The difference is in the kind of output being predicted.

8.3.1 Continuous vs discrete output

• Regression predicts a continuous variable — a real number that can take an infinite number of values. Predicting house price is the running example.
• Classification predicts a discrete variable — a value chosen from a finite set of categories. Handwritten digit recognition is the running example: digits 0 through 9 are only ten possible values, so any digit gets classified under one of these ten discrete, finite labels.

So the little difference is: regression → continuous output; classification → discrete output.

When to pick which: if the label column contains numbers you could split infinitely, regress; if it names a fixed set of buckets, classify.

8.3.2 Classification examples

• Image recognition: certain features are extracted from training images, and each image is given a label — "this is an apple", "this is a tomato", "this is an animal". The model learns "if these are the set of features, classify as ...". In testing you give an image that is different from the training images; it extracts features, passes them to the learned model, and the model predicts which class it belongs to.
• Employability prediction: four input attributes — CGPA, communication skills, aptitude, and programming skills — with historical data from a university covering the past three to four years, including whether the job was offered to each candidate. This labeled data trains a classification model; then, given the four attributes of a new student, the model predicts whether the job will be offered.
• Disease prediction: predicting whether a patient has a particular disease — yes or no — or is likely to get it.
• Email spam detection: the spam/not-spam problem already discussed; only two categories exist here.

8.3.3 Regression examples

• Property price prediction.
• Stock price prediction.
• Sales prediction: organizations such as Amazon and Flipkart predict the sales of their products, or overall sales during events like the Big Billion Days; they need such models to prepare the inventory and the workforce needed to fulfill those many orders.

8.4 Simple Linear Regression

8.4.1 The problem, simplified to one attribute

The house-price problem is simplified for study: suppose the price depends only on plot size. Price is plotted on one axis (in lakhs) against plot size on the other (in square feet), producing a two-dimensional scatter plot of training points. One attribute is independent — size can vary freely — and the attribute being predicted is dependent: given a size, the price is to be predicted.

From school days, the equation of a straight line is \(y = mx + c\), where \(m\) is the slope and \(c\) is the intercept. Relating it to this problem, and assuming the relationship between size and price is linear:

\[ \text{price} = m \cdot x + c \]

where \(x\) is the plot size. Given the training data, the objective is to come up with the line that fits these points. The assumption of linearity is important: if the relation were quadratic, the fit would not be a straight line.

8.4.2 The algorithm vs the model

A line becomes the model only after its parameters are learned. There is a real difference between an algorithm and a model: once \(m\) and \(c\) have been identified, these are the model parameters — \(m\) is the slope and \(c\) is the intercept. The procedure that finds them is the algorithm; the resulting line is the model.

8.4.3 Which line is best? The error, point by point

Looking at the scatter plot, infinitely many lines can be drawn through the cloud of blue points — this line, that line, \(n\) number of lines. Which one best fits the points? That is the objective, and it is important to understand how to decide.

Focus on a single fitted line. Some points fall below the line, some fall above it. For each point, the vertical distance between the point and the line is the error between the model being selected and the original point. For a point below the line the error is negative in sign, but the magnitude of the error is still there; other points show small errors. So: we can fit a number of lines, but we choose the one that minimizes this error across different points. The definition of "error across all training data" needs a term; wherever that term is minimum, that line is chosen as the model.

Visual intuition. Draw the scatter plot with plot size (square feet) on the horizontal axis and price (lakhs) on the vertical axis. The training points form a rising cloud — bigger plots, higher prices, with scatter around the general trend. Overlay any candidate line: some blue points sit above it, some below. The vertical gap between each point and the line is the error for that point — not the diagonal distance, because prediction happens along the price axis. The line with the smallest total vertical gap — the one that threads the middle of the cloud — is the fit we want. The cloud is never threaded exactly; every point has some residual error, and that fact survives into section 8.6: 100% accuracy cannot be achieved.

8.4.4 Worked notation change: from \(m, c\) to \(\theta_0, \theta_1\)

To follow the books, the notation changes. With \(y = mx + c\):

• \(\theta_0 = c\) — the intercept
• \(\theta_1 = m\) — the slope

so the model becomes:

\[ y = \theta_0 + \theta_1 x \]

The task is to find \(\theta_0\) and \(\theta_1\). Once they are found, for any given value of \(x\) the model can predict \(y\).

8.4.5 Worked prediction with \(y = 2 + 5x\)

Suppose the learned parameters are \(\theta_0 = 2\) and \(\theta_1 = 5\), giving:

\[ y = 2 + 5x \]

Given a plot size of 750 (square feet), the predicted price is:

\[ \hat{y} = 5 \times 750 + 2 = 3752 \]

That is the predicted value. For each training record, this predicted value is compared with the actual value we already know, and the difference is computed.

8.4.6 Root mean squared error (RMSE)

Let \(y_j\) be the actual value of the \(j\)-th training point and \(\hat{y}_j\) (read "y-j hat"; some people say "y-j cap") the predicted value. The error per point is the difference \(y_j - \hat{y}_j\). To build one number out of all training points:

\[ \text{RMSE} = \sqrt{\frac{1}{n}\sum_{j=1}^{n} \left( y_j - \hat{y}_j \right)^2} \]

where \(n\) is the number of training data points. Each difference is squared, the squares are summed over all \(n\) points, the sum is divided by \(n\), and a square root is taken at the end "to balance out" the squaring. That is why the term is root mean squared error — the mean (average over \(n\)) of squared errors, then rooted.

8.4.7 Mean absolute error (MAE)

A variant metric replaces the square with the absolute value (mod):

\[ \text{MAE} = \frac{1}{n}\sum_{j=1}^{n} \left| y_j - \hat{y}_j \right| \]

If you do not square, you do not need the square root. Both RMSE and MAE can be computed, but RMSE is largely the one used; algorithms such as gradient descent typically work with RMSE-style objectives. (Gradient descent itself is not covered here.)

8.4.8 The complete recipe for simple linear regression

Putting the whole section together: price is dependent on plot size; the equation \(\theta_0 + \theta_1 x\) gives predicted values; actual values are already known for each house instance; for each instance take the difference; either take the mod of the difference or the square of it; compute RMSE or MAE; and the objective is to minimize the RMSE (or the MAE) so that the line passes as close as possible through all the points — the line giving the minimum error.

8.5 Multilinear and Polynomial Regression

Simple linear regression is based on a single attribute. Two extensions are introduced, briefly, with the reassurance that in machine learning the libraries handle the complexity — it is a library call and things are done automatically.

8.5.1 Multilinear regression

In multilinear regression, \(y\) depends on multiple features at once — not just plot size, but number of bedrooms, distance from the city, marble or granite flooring, upgraded kitchen, and so on. With each feature there is an associated weight, plus an intercept:

\[ y = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_d x_d \]

where \(x_1, x_2, \dots, x_d\) are the \(d\) input features and \(\theta_1, \dots, \theta_d\) are their weights.

The intuition in machine learning terminology: \(x\) is a set of features — input features. In the simple case \(x\) was the single size of the house; it could be multiple variables: number of bedrooms, distance from the city, granite flooring, upgraded kitchen, and so on. The output is predicted from the input features.

8.5.2 Polynomial regression

In polynomial regression, higher-degree terms are added:

\[ y = \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3 + \cdots \]

Up to the \(x^2\) term it is quadratic; further terms like \(\theta_3 x^3\) take it to higher degrees. Each of these regressions (simple, multilinear, polynomial) would take a full lecture on its own, so the session stays with the simple case — simple linear regression — and the objective of minimizing root mean squared error.

8.6 Hands-On: Linear Regression in PySpark

A small program, regression_1.py, is run via spark-submit against a live Spark cluster (already connected to the lab's Spark cluster). The dataset is boston.csv, a standard dataset available on the internet; it has already been downloaded onto the system.

8.6.1 The boston.csv dataset

The file contains input attributes (the classic Boston housing attributes) plus a medv column — the median value, which is the price to predict. The output feature is deliberately kept separate from the input features. The data has 506 records; a statistical description shows, for each attribute, the count, the mean, the standard deviation, and the min and max. For example, crim is basically the crime rate near the area, and for medv (the output) the mean is about 22. This is the training data.

8.6.2 Program structure, step by step

1. Imports: from pyspark, import packages related to Spark configuration, Spark context, and additionally an SQL context, because data frames are used — after RDDs came data frames and datasets, and a data frame is the most structured. The SQL context helps read the CSV file and put it into a data frame.
2. Read the file: create the Spark context, then the SQL context; specify the format to read and the file to read, and load it into a house data frame.
3. Inspect: print the data frame (schema — the columns come out as double, double, integer, double, and so on — and show), and describe, which gives a statistical description of each attribute — count, mean, standard deviation, min, max for every input attribute as well as the output.
4. Vector assembler: from pyspark.ml.feature, import VectorAssembler. It is given the input columns and asked to create a single vector out of them called features — bundling the whole set of input parameters into one vector column. The transform function is applied to the data frame; the medv column is left out of features because it is the output, the thing to predict.
5. Train/test split: randomSplit([0.7, 0.3]) — every machine learning algorithm follows this pattern: use some percentage of the data for training and some for testing. The split is random and the two parts are disjoint: one single record must not appear in both. splits[0] (70% of the data) is the training data frame; splits[1] (30%) is the testing data frame. The data used to train the model must not be used to test it; only then is testing real, because the model must be tested against unseen data (seen data is what it already learned from).
6. Model call: from pyspark.ml.regression, import LinearRegression. Call the constructor with: the feature column (features, built by the vector assembler), the label column (medv), maxIter=10 (10 iterations), and a regularization parameter. (Regularization relates to underfitting/overfitting, not yet discussed; these parameters help avoid overfitting — a one-liner about overfitting follows later. For now they can be skipped.)
7. Fit: lrModel = lr.fit(trainingData) — calling fit on the training data produces the line. That is all: one call and the model is ready.
8. Coefficients and intercept: lrModel.coefficients and lrModel.intercept — recall \(\theta_0, \theta_1, \theta_2, \dots\); the coefficients correspond to the features (how many there are depends on the number of input features), and the intercept is the constant \(\theta_0\).
9. Training errors: trainingSummary = lrModel.summary, then trainingSummary.rootMeanSquaredError and trainingSummary.meanAbsoluteError.
10. Predict on test data: make predictions on the test data frame; print, for each of the top five records, the prediction, the actual value, and the feature set of that record. Then compute RMSE and MAE on the test data. Finally do the same on the whole dataset — show prints 20 rows by default (not the whole file), which is why five rows are printed first and then 20.

8.6.3 What the program prints

• The data frame and its schema.
• The statistical summary (describe) — 506 records per attribute.
• Three rows after the vector assembler (the call was df.show(3)): the feature set, with medv alongside.
• Training errors: RMSE and MAE of about 4.7 and 3.27 respectively.
• Coefficients and intercept: the constant \(\theta_0\) (intercept), then \(\theta_1, \theta_2, \theta_3, \dots\) — as many thetas as input attributes, including one around 3.1 and several 0.0 values. A 0.0 coefficient means that feature is not very important. With 13 input attributes and an intercept this is truly multilinear regression, not the simple case.
• Test predictions (first five rows): record 1 — actual 24, predicted 30.19; record 2 — actual 31.01, predicted 32.2; record 3 — actual 35.4, predicted 30.84; record 4 — actual 18.9, predicted 17.10; record 5 — actual 23.1, predicted 26.12.
• Test errors: RMSE for test data 5.2, MAE for test data 3.4. There is a little difference between the RMSE on training data and on test data.
• The final show prints 20 rows — the first five already seen, plus 15 more.

8.6.4 Reading the output

There is an error with respect to each and every training record, and that will always be there — 100% accuracy cannot be achieved. This is the simple way of doing linear regression: no hyperparameter tuning, which is very deep for this course — this is not a machine learning or data mining course — so just a simple case showing how to do it and how to check the output on Spark.

Real-world & domain connection. The Boston housing dataset (506 records, 13 attributes) is one of the most widely used public benchmarks for teaching regression — the same file appears in countless textbooks and tutorials, which is why the professor picks it for the demo. The workflow shown — assemble features, split, fit, measure RMSE — is the exact skeleton that e-commerce firms (Amazon, Flipkart in section 8.3) scale up to predict sales over events like the Big Billion Days, with the same train/test discipline but far more features and data.

8.7 Classification

Classification is revisited more formally. It is a supervised learning problem: training data is labeled, a classifier learns from it, and the classifier is tested on unseen data.

8.7.1 Classification is a two-step process

1. Model construction: you have training data with associated labels, and the model is represented in some form — classification rules, decision trees, or a mathematical formula (support vector machines and the like). There are many techniques; the major focus of this session is decision trees.
2. Model usage: the built classifier is used on unseen data.

After building the classifier with any of these techniques, the objective is to estimate the accuracy: the rate — the percentage — of test samples correctly classified by the model.

8.7.2 Worked example: tenure prediction

A small labeled dataset has attributes: name, rank (assistant professor), years (3). The output attribute is whether the person is tenured — no or yes. Feeding this to a classification algorithm, it learns rules, e.g.:

\[ \text{if rank} = \text{professor} \quad \text{or} \quad \text{years} > 6 \quad \text{then tenured} = \text{yes} \]

When new, unseen data arrives, the rules trigger and the class (yes or no) is output. Test data: associate professor with number of years greater than 7 — since years > 6, the rule fires and tenured is predicted yes. Training is being done on the labeled data; testing is done on the unseen data.

Real-world & domain connection. The tenure example is a classic HR-decision pattern, and the same construction-usage loop runs in production systems everywhere: banks score loan applications (accept/reject) from historical borrower records; hospitals triage patients (high-risk/low-risk) from historical outcomes; universities and firms screen candidates from past recruitment data — the employability example from section 8.3 is the same shape. Wherever a decision has a yes/no answer and a history of past decisions, a classifier can be built and its accuracy measured.

8.8 Decision Trees and the Buys-Computer Example

The classic buys-computer dataset is the vehicle for decision trees, and decision trees are the major focus of the classification part of the session.

8.8.1 The dataset

Four input attributes:

• age — three values: youth, middle-aged, senior
• income — high, medium, or low
• student — no or yes
• credit rating — fair or excellent

The output attribute is whether the person buys a computer — the class to predict. There are 14 tuples: 9 belong to yes and 5 belong to no.

8.8.2 Building the tree

The tree checks age first, with three branches:

• youth → check student: if not a student → not likely to buy; if a student → yes, likely to buy.
• middle-aged → simply yes: all four middle-aged entries have "yes" output, so a pure yes class is placed there.
• senior → check credit rating: excellent → buys a computer; fair → no. Among the five senior entries there are three yes and two no.

The tree is learned from the data, and it then predicts the class for new records. How the tree is learned — how the attributes are chosen at each level — is the important part.

Visual intuition. Draw a top-down chart. At the top, a root node labelled "age?" with three arrows leaving it: youth → (a node "student?") → no/yes; middle-aged → (a leaf labelled "yes"); senior → (a node "credit rating?") → excellent/yes, fair/no. The path a record takes is a chain of tests: the depth of the tree is the number of tests on the longest chain (this one is depth 2). A new customer enters at the root, answers each question, and exits at a leaf carrying the class. The tree is worth drawing once because every later concept — split attribute, purity, stopping — is a property of this picture.

8.8.3 Pure partitions: the goal of each split

As you move deeper down the tree, each branch should lead to a pure partition: at the next level down, the tuples belonging to a class should maximally belong to one class. The middle-aged branch is the simplest illustration: all tuples at that level belong to one class, so the yes class is placed there — a pure partition. A branch that produces tuples closer to pure partitions is more helpful and guides tree construction.

8.8.4 The two big challenges

1. Which attribute to choose first? Here age was chosen — why age and not income, student, or credit rating at the first stage?
2. What are the stopping conditions? It may not be possible that every split results in pure partitions; partitions may always remain impure, because 100% accuracy cannot be achieved.

8.8.5 Stopping conditions

Any of the following can stop a branch:

1. All samples for a given node belong to the same class (the middle-aged case).
2. There are no remaining attributes for further partitioning — all attributes have been tested and there is no need to test the rest.
3. Majority voting is employed for classifying the leaf — if tuples are still left that cannot be classified, apply majority voting: for example, at a credit-rating leaf, if 70% of the people with that rating buy and 30% do not, then anyone arriving with credit rating excellent is classified as yes.
4. There are no samples left in a branch.

8.8.6 Types of splits

The splitting criterion can take several forms:

• Multiway split on a discrete attribute: color → red / green / blue / purple / orange; income → low / medium / high.
• Binary split on a discrete attribute: color red → go to this branch; not red → go to that branch (still two branches).
• Binary split on a continuous attribute: choose a split point — less than 42,000 → this branch; greater than 42,000 → that branch.

All sorts of splits are possible; what matters is how to decide among them.

8.9 Choosing the Split Attribute: Information Gain and Gini

The metric used to decide the splitting attribute is information gain (referred to in the flow of the session as "information game"). The same example is worked numerically: compute the information gain at the root level, then for a split on each attribute, and the attribute giving the maximum information gain is chosen for the first split. (Gini index is the companion method: maximum information gain, minimum gini.)

8.9.1 Worked computation: information at the root

There are two classes: buys a computer (yes) or does not (no). Out of 14 tuples, 9 belong to yes and 5 to no. The information at the root is:

\[ I(9,5) = -\frac{9}{14}\log_2\frac{9}{14} - \frac{5}{14}\log_2\frac{5}{14} \]

The professor states the value of this as 0.940 — the information at this moment, when 9 tuples belong to one class and 5 to another. Mathematically, information gain is the way to find the partition that takes the tree to a more pure form: the partition whose next level has the maximum tuples belonging to one class.

8.9.2 Worked computation: splitting on age

For the age attribute there are three branches — youth, middle-aged, senior — with the following yes/no counts:

• youth: 5 tuples total — 2 yes, 3 no
• middle-aged: 4 tuples — all 4 yes, 0 no
• senior: 5 tuples — 3 yes, 2 no

The weighted information after splitting on age:

\[ I_{\text{age}} = \frac{5}{14}\,I(2,3) + \frac{4}{14}\,I(4,0) + \frac{5}{14}\,I(3,2) \]

expanding each term:

\[ I(2,3) = -\frac{2}{5}\log_2\frac{2}{5} - \frac{3}{5}\log_2\frac{3}{5} \]

\[ I(4,0) = -\frac{4}{4}\log_2\frac{4}{4} - 0 \cdot \log_2 0 = 0 \]

the middle-aged term cancels out — the \(4/4\) and zero contributions make that term zero — and

\[ I(3,2) = -\frac{3}{5}\log_2\frac{3}{5} - \frac{2}{5}\log_2\frac{2}{5} \]

The total comes to 0.694.

8.9.3 Worked computation: the gain, and the winner

The information gain for age:

\[ \text{Gain}(\text{age}) = 0.940 - 0.694 = 0.246 \]

Similar gains are calculated for income, student, and credit rating, and the values come out lower. The information gain is highest for age, so age is chosen as the splitting attribute at the first stage.

8.9.4 Gini index

A second metric: gini index. At the root level, with 9 yes and 5 no:

\[ \text{Gini}(\text{root}) = 1 - \left(\frac{9}{14}\right)^2 - \left(\frac{5}{14}\right)^2 \]

where the terms are the probability of the yes class and the probability of the no class. Then try it for each attribute. For income, suppose the partition is:

• \(D_1\): low + medium income — 10 tuples out of 14
• \(D_2\): high income — 4 tuples out of 14

so the weights are \(10/14\) and \(4/14\). Within \(D_1\), of the 10 tuples, 7 buy and 3 do not; within \(D_2\), of the 4, 2 buy and 2 do not. The reported gini values for the three possible income splits are:

• low–high split: 0.458
• medium–high split: 0.450
• low–medium split: 0.443

Since the low–medium split has the lowest gini index, low and medium are put in one bucket and high in another — that split gives the more pure partitions.

8.9.5 The one-liner rule

This may seem complex, but there is a one-liner: the partition should lead toward more pure partitions, and the ways to calculate which attribute leads to more pure partitions are information gain and gini — information gain highest, gini lowest, and that attribute is chosen. Different algorithms use different metrics (different algorithms use different stories), but these two methods are enough for this course at this moment.

Real-world & domain connection. Information gain and gini are not classroom-only: gini impurity is the default splitting criterion in scikit-learn's DecisionTreeClassifier and in Spark MLlib's tree, while information gain drives ID3 and C4.5-style learners. Every decision-tree model in production — loan approval, fraud scoring, churn prediction — picks its splits with one of these two rulers, so the 0.246-vs-0.029 comparison above is literally the arithmetic that a bank's credit-scoring tree performs at scale.

8.10 Hands-On: Decision Tree Classifier in PySpark

8.10.1 The wine.csv dataset

The classification demo uses wine.csv. The input features are the wine's chemistry: alcohol content, volatile acidity, citric acid, residual sugar, chlorides, free sulfur (dioxide), total sulfur dioxide, density, pH value, sulphates, alcohol. The output is the quality of the wine, rated on a scale (a quality rating of 6 appears in the printed rows) — so this is a multi-class classification problem.

8.10.2 Program structure, step by step

1. Imports (k-means is imported too in this file but ignored here, since it belongs to the clustering problem).
2. Create the Spark context, read wine.csv, build a data frame, display two records, print the schema — the same pattern as the regression program.
3. Vector assembler: bundle all input features into one vector column called features; transform the data frame. The output — wine quality — stays separate.
4. Show the top three records.
5. Train/test split: randomSplit([0.7, 0.3]), this time with a seed value given. The seed makes the random pick reproducible: 70% of records go to training, 30% to testing, and rerunning the program picks up the same set of records every time (without a seed, the random split differs each run). The seed value can be read about in Python's documentation.
6. Decision tree classifier: from pyspark.ml.classification, import DecisionTreeClassifier. Give it the features column, say the label column is quality, set the maximum depth (depth 3 is used in the demo) — "we don't want to overfit the model" — and call dt.fit(trainingData).
7. Predict: make predictions on the test data (the 30%): for each record print features, quality (the actual label), and prediction (the predicted class).

The whole program is deliberately limited: imports, read the file, build the data frame, vector assembler, train/test split, call the classifier, train the model, predict on test data, and see how many instances it correctly predicts.

8.10.3 Output and interpretation

The output table shows the input vector, the actual quality, and the prediction:

• quality = 3, prediction = 6
• quality = 8, prediction = 7
• quality = 5, prediction = 7

There are many incorrect predictions in the first 20 rows, though some correct instances are also predicted. The likely cause is underfitting: the tree was given maximum depth 3, so perhaps going deeper would increase accuracy. This is the demo's own illustration of the depth/overfitting tradeoff: try more depth and see whether the accuracy increases.

Real-world & domain connection. Winemakers and distributors use exactly this model to grade bottles from chemistry alone, saving expert tasting time. The depth dial is the standing tradeoff of every tree-based model in industry: too shallow underfits (misses patterns), too deep overfits (memorizes noise), and practitioners pick the depth by testing on unseen data — the same loop the demo runs in miniature.

8.11 Clustering

Clustering is introduced as "a little easier", and it is presented as an unsupervised learning method — no labeled data is needed. The session is extended by about 15 minutes to fit clustering in.

8.11.1 What clustering is for

Given unlabeled data, clustering groups it under different heads. Examples: given customer data with certain demographics, categorize customers into different groups — this set belongs to one group, that set to another, that set to a third — to do better target marketing (launching a new product: whom should it be marketed to? find the right segment of customers). There may be no historical purchase data initially available — the customers are very new — but based on certain demographics they can still be grouped. Clustering is also used for market segmentation, spam filters, and fake news detection.

The objective in one sentence: finding groups of objects such that the objects in a group are similar to one another and different from the objects in the other groups.

8.11.2 The objective, in distance terms

Looking at a scatter plot of points, you intuitively see three different groups — three clusters exist. The objective is:

• intra-cluster distance minimized — the distance between two points belonging to the same cluster should be minimized;
• inter-cluster distance maximized — the distance between two points belonging to different clusters should be maximized.

8.11.3 Dissimilarity metrics: Minkowski, Manhattan, Euclidean

When attributes are numeric, dissimilarity can be measured with the Minkowski distance, a general form:

\[ d(i,j) = \left( \sum_{k=1}^{p} \left| x_{ik} - x_{jk} \right|^{q} \right)^{1/q} \]

where the two objects \(i\) and \(j\) each have \(p\) features (the number of features is also called \(n\)), and \(q\) is a parameter.

• \(q = 1\): the Manhattan distance — the sum of absolute differences:

\[ d(i,j) = \sum_{k=1}^{p} \left| x_{ik} - x_{jk} \right| \]

Manhattan distance is called the L1 norm.

• \(q = 2\): the Euclidean distance — square the differences, sum, and take the square root:

\[ d(i,j) = \sqrt{ \sum_{k=1}^{p} \left( x_{ik} - x_{jk} \right)^{2} } \]

Euclidean distance is called the L2 norm.

Based on the dissimilarity values obtained, objects are categorized as similar or different in nature — the threshold for that decision has to be decided.

8.11.4 Binary variables: the \(a, b, c, d\) contingency table

Binary variables take two values — zero or one (or yes/no). For objects \(i\) and \(j\), count the four combinations over all attributes:

• \(a\) = number of attributes where both are 1 (value 1,1)
• \(b\) = number where \(i\) is 1 and \(j\) is 0
• \(c\) = number where \(i\) is 0 and \(j\) is 1
• \(d\) = number where both are 0 (value 0,0)

The dissimilarity — where the values differ, i.e. \(b\) and \(c\):

\[ d(i,j) = \frac{b + c}{a + b + c + d} \]

8.11.5 Asymmetric binary variables and the Jaccard coefficient

Some binary situations are asymmetric: one value is important but the other is not. The medical test example: if a test is positive, it matters a lot; if it is negative, that value can kind of be ignored — the person may still have a problem even when the test says negative, but a positive makes a difference. So wherever the value is zero, it is ignored — the \(d\) term (both zero) is skipped, and the total left is \(a + b + c\):

\[ d_{\text{asym}}(i,j) = \frac{b + c}{a + b + c} \]

For similarity, take one minus the dissimilarity:

\[ s_{\text{asym}}(i,j) = 1 - \frac{b + c}{a + b + c} = \frac{a}{a + b + c} \]

This similarity measure for asymmetric binary variables is termed the Jaccard coefficient.

8.11.6 Nominal variables

A nominal variable can take more than two states — red, yellow, blue, green (the color of an object), anything. The approach is simple matching: count how many attributes are matching. If \(m\) is the number of matches out of \(p\) attributes, then \(p - m\) is the number of unmatched attributes, and:

\[ d(i,j) = \frac{p - m}{p} \]

is the dissimilarity between \(i\) and \(j\).

8.11.7 The notion of a cluster is ambiguous

Even after measuring dissimilarity, the notion of a cluster can be ambiguous: given the same dataset, somebody may say there are two clusters, somebody else four, and at a fine-grain level six. Clusters can be built hierarchically; you can start with a small value, get poor results, and decide to build up more clusters. All of that can be tried. One algorithm — k-means clustering — is covered, a distance-based approach.

Real-world & domain connection. Clustering's name comes from the field's flagship use case — cluster analysis in market research: an insurer profiling 2,000 households found five segments (non-traditionals, direct buyers, budget-conscious, agent-loyal, hassle-free) and aimed targeted campaigns at each — the exact "target marketing" use the professor names. The same toolbox drives fake-news detection (grouping similar claims), spam filtering (grouping similar messages), and social network community detection.

8.12 K-Means Clustering

8.12.1 The algorithm

K-means is a partition-based clustering approach: a single point belongs to exactly one cluster, each cluster is associated with a centroid, and each point is assigned to the cluster with the closest centroid. Given a set of points:

1. Choose \(k\) initial centroids — that is why it is called \(k\)-means.
2. Compute the distance of every point from each centroid.
3. Assign each point to the cluster whose centroid it is closest to.
4. Recompute the centroids: take the average of all the points of each feature for the points in the cluster.
5. Iterate — recompute distances, reassign points, recompute centroids — until the centroids converge: when points stop shuffling between clusters, the centroids are fixed, and the algorithm stops.

8.12.2 Worked illustration: centroids moving over iterations

The illustration uses three centroids (red, blue, green plus-marks) over a scatter of data points:

• Initial: three centroids are chosen; each point is assigned by proximity — the red cluster has very few points, blue and green have more.
• After recomputing distances, some points that were in green and blue should have been in the red cluster, so points move from blue and green to red.
• Centroids are recomputed as the average of the points in each cluster; the centroids shift a little.
• The next iteration moves the centroids a little further down; the green and blue ones move further down still.
• By the sixth iteration the final clusters are settled.

This is how clusters are built with k-means: a simple distance-based approach using the L1 or L2 norm — if the exam (or some problem) says use L1, go with L1; if it says L2, go with L2.

Visual intuition. Picture the scatter: three roughly circular clouds of points, plus-marks sitting on top of them as the initial centroids (the professor's diagram shows red, blue, green). The first assignment draws boundaries mid-way between the plus-marks, so boundary points land in the wrong cloud; the first recompute drags each plus-mark toward the true middle of its assigned points; each subsequent pass re-draws the boundaries, migrating a few more points, until the plus-marks stop moving — by the sixth iteration the three clusters are settled. Each frame is the same two moves — assign by nearest centroid, then average the members — repeated until nothing changes.

8.12.3 What k-means minimizes

Another way to view the clusters: k-means minimizes the sum of squared error — compute the distance of each point from its centroid, square it, and sum:

\[ \text{SSE} = \sum_{i=1}^{k} \sum_{x \in C_i} \| x - \mu_i \|^2 \]

where \(C_i\) is the \(i\)-th cluster, \(x\) is a point in it, and \(\mu_i\) is its centroid.

8.12.4 Limitations of k-means

Three limitations are illustrated with diagrams:

1. Clusters of different sizes: the original data has three clusters of different sizes, but depending on the chosen initial centroids, k-means may end up with wrong groupings — not good quality clusters.
2. Clusters of different densities: the data shows three clusters where some are more dense than others; with k-means, certain centroid choices can merge two of them into one — again not good quality. For density differences there is a density-based clustering algorithm: DBSCAN.
3. Non-globular shapes: the original clusters have elongated, non-globular shapes; k-means may cut them into the wrong pieces. K-means cannot be used in this case.

Other algorithms exist to find these kinds of clusters, covered in more depth in the machine learning course, with some things also covered in the data mining course.

Real-world & domain connection. K-means is the workhorse unsupervised algorithm in industry — customer segmentation for targeted marketing (the professor's exact motivation), image compression (each pixel assigned to one of \(k\) color centroids), fraud and anomaly detection, and healthcare sub-population characterization (diabetic vs non-diabetic group structure from patient attributes). Its strength is speed — the reference analysis gives time cost \(O(n k I d)\) with \(n\) points, \(k\) clusters, \(I\) iterations, \(d\) attributes — which is why it survives at Big Data scale even though it inherits all three shape limitations.

8.13 Hands-On: K-Means in PySpark

8.13.1 The program

The clustering program, kmeans_clustering_1.py, is very simple because the input file is very simple:

1. Import the Spark context; import k-means (from the MLlib library, e.g. KMeans).
2. Define a function that splits the input file — each line is split on spaces (a parseVector-style helper used with map; recall the map transformation on RDDs).
3. Set k = 2 — build two clusters.
4. The whole dataset is the training data (there is no train/test split in clustering).
5. At the end, print the cluster centers and the compute cost.
6. Stop the Spark context.

Similar examples ship with the Spark ML libraries; this one was picked up to show the context.

8.13.2 The data file

The input file is kmeans_data.txt (the file listing first shows kmeans.txt absent — the actual file is kmeans_data.txt). It contains only five or six samples, three-dimensional points near the origin — \(0.0, 0.0, 0.0\); \(0.0, 0.1, 0.1\); \(0.1, 0.1, 0.1\); and similar — with the data well separated into two natural groups (points near the origin and a point near \(9.1, 9.1, 9.1\)). The goal is to cluster these samples into two clusters: the program picks initial centroids and comes up with final centroids.

0.0 0.0 0.0
0.1 0.1 0.1
0.2 0.2 0.2
9.0 9.0 9.0
9.1 9.1 9.1
9.2 9.2 9.2

8.13.3 Output

Running spark-submit kmeans_clustering_1.py:

• Total cost: 0.12 — the computed cost of the final clustering.
• Two centroids: \(0.1, 0.1, 0.1\) — the first centroid — and \(9.1, 9.1, 9.1\) — the second centroid.
• K-means converged in two iterations — within just two iterations the algorithm figured it out.

No in-depth discussion of cluster quality metrics (like the silhouette coefficient) is attempted — explaining clustering properly needs three to four lectures — so the session covers simple k-means: what it does, and how to write a small sample and run it on PySpark. The same was done for regression and for classification; three hands-on demos are enough at this moment. (A recommendation-system code snippet may be shared separately, easy to run on your own.)

Real-world & domain connection. This six-line toy is the archetype of every production k-means job: the same KMeans class in MLlib segments millions of customers by spending behavior, retrieves similar images by feature similarity, and flags anomalous credit-card transactions — the exact use cases the reference text lists for k-means. The cost number printed here is the same SSE that, at scale, guides choosing \(k\) (smaller is tighter, but over-splits).

8.14 Recommendation Systems

A brief, roughly five-minute close on recommendation systems — what the two approaches to recommending items are.

8.14.1 The recommendation problem

Almost every website that sells anything has a recommendation system: any e-commerce website recommends products to you; movie websites recommend movies; reading platforms recommend books. The core idea: predict the preference of a user based on past behavior. There is a set of items \(Y\) and a set of users \(X\), and the system tries to learn a function from past interactions that predicts the likeliness of \(x\) (a user) to \(y\) (an item). On an OTT platform like Netflix, the items are movies or shows; users are end users, each with attributes like age and likes and dislikes.

8.14.2 Content-based filtering

Content-based filtering uses only the attributes of the items and does not study the attributes of the users coming in. For items (movies, songs) to be usable this way, items must have attributes: for a movie — its genre, the actor, the director. If a person has been liking thriller movies, recommend more thrillers; if they have previously watched a movie of a certain actor, recommend another movie by the same actor. In the course of the session the professor describes this with an audience-behavior example as well: if someone has heard songs A, B, C and a large number of the audience who listened to A, B, C have also heard X and "we next" (the next track), that next song appears in the playlists of a large number of that audience — and that is how it gets recommended. The distinguishing claim is that content-based studies the attributes of the items they have but not the attributes of the users.

8.14.3 Collaborative filtering

Collaborative filtering utilizes the user interaction behavior in addition to the item attributes — the specific user interactions that have happened with the system matter. With songs, the system understands who are the similar users and what else those users listen to, so that the next song recommendation can be generated; item attributes are less important here. New users are matched to categories: if a new user fits into a particular category (as the system recorded the attributes of existing users), whatever the users in that category have watched gets recommended — not on a one-person basis, of course; there should be sufficient data, a certain number of users in the category who have watched that content.

The everyday analogy: you want to watch a movie and you ask your friend circle — specifically the people of a similar nature of taste, not each and every friend. Out of a friend list of 25, you know that five of you share very common taste in movies; you ask those five, and their recommendation tells you whether to go. Most collaborative filtering systems use a similarity index with respect to the active user — a set of similar user preferences is aggregated. What matters is the relationship of the users to the items, rather than only among the items (which is content-based). The similarity in items is determined by the similarity of the preferences of those items by the users who have rated both items. This is an unsupervised technique; techniques like nearest neighbor are used.

8.14.4 User-based vs item-based approaches

Two diagrams illustrate the two collaborative approaches:

• User-based approach: if a particular user has bought two DVDs/CDs of a digital content and another user has bought three, and the two users are similar, then the third one can be recommended to the first user.
• Item-based approach: two items are similar because the same user has given similar ratings to both; so if another user buys one of these items, since the two items are similar (two users gave similar ratings), that item is recommended back to this person.

Sources are mentioned for reading more about these approaches.

When to pick which: with many users and few items per user, item-based is more stable (item similarities change slowly); with a dense user-item matrix, user-based works well. Both are memory-based collaborative filtering — the reference text's two branches of CF are exactly user-based and item-based.

8.14.5 Matrix factorization, and how much depth is intended

The matrix factorization approach is not covered ("max factorization" in the flow of the session is the matrix factorization method). It is something you can read about for detail. The simple things about recommendation systems have been covered; covering all these four techniques in detail would need 12–13 sessions, but that is not the objective here — the basics are the objective.

8.14.6 Student question and closing notes

For finding a session's topic, the answer is to match the recording's date with the dates on the slide deck. Exam note: everything in this session — regression, classification, clustering, and collaborative filtering — is part of the end-semester exam; consolidated guidance on what to study is gathered at the end. The next session covers a little bit of spark streaming.

Real-world & domain connection. Recommenders are the most visible machine learning product in the world: Netflix's home screen, Amazon's "customers also bought", Spotify's weekly playlist, YouTube's next video. The friend-circle logic scales to billions of interactions — Netflix's items are movies and shows, users carry attributes like age and preferences, and the top-N list is the interface everyone sees. Item-based similarity is why Amazon shows you the chocolate and gift box next to the greeting card in your cart — the same co-purchase inference the professor's audience example describes.

Exam Guidance Summary

• Exam note: The end-semester exam covers regression, classification, clustering, and collaborative filtering — everything discussed in this session. Pay careful attention to all of these topics.
• Exam note: Questions may be asked from code snippets and conceptual things out of these topics; the professor will not go too deep, and whatever is in the slides is enough — but the topics should be explored a little more in detail.
• Exam note: For distance choices in k-means-style problems, if the exam says use the L1 norm, go with L1; if it says L2, go with L2.
• Exam note: Two methods suffice for the attribute-selection question in classification: information gain (choose the maximum) and gini index (choose the minimum). Different algorithms use different metrics, but these two are the ones to learn for this course.
• Study advice: The three code files used in the session (regression, decision tree classifier, k-means) will be uploaded; a working recommendation-system snippet may also be uploaded if it works.
• Study advice: Recordings are organized by date in the slide deck; to find which recording covers which topic, match the recording's date with the dates mentioned on the slide deck.
• Course scope: Hyperparameter tuning, gradient descent, cluster-quality metrics (silhouette coefficient), matrix factorization, and other clustering algorithms (DBSCAN and the like) are explicitly out of scope for this course — they belong to machine learning or data mining courses.

Key Industry Applications

• Real-world: Spam filtering is the canonical first machine learning application: classify emails as spam or not spam using labeled historical emails.
• Real-world: Machine learning has touched almost every area — image recognition, speech recognition, medical diagnosis, traffic prediction, stock price trading, self-driving cars, product recommendations, and fraud detection.
• Real-world: Amazon and Flipkart predict product sales, and overall sales during events like the Big Billion Days, to prepare inventory and the workforce needed to fulfill those orders.
• Real-world: OTT platforms such as Netflix run recommendation systems whose items are movies and shows, recommending based on a user's attributes and past behavior.
• Real-world: E-commerce websites and book/movie platforms all carry recommendation systems; most use either content-based or collaborative filtering.
• Real-world: Market segmentation for target marketing — grouping new customers by demographics to decide whom to market a new product to — is an unsupervised learning use case.
• Real-world: Social network analysis is an unsupervised learning task.
• Real-world: The medical-test asymmetry example — positive results matter, negatives can be ignored — is why asymmetric binary dissimilarity drops the both-zero term.
• Real-world: The Boston housing dataset (boston.csv, 506 records) and the wine-quality dataset (wine.csv) are standard public benchmark datasets used to teach regression and classification.