Classification with Spark (LogisticRegression, RandomForest) in Apache Spark - Time & Space Complexity

Time Complexity: Classification with Spark (LogisticRegression, RandomForest)

O(n * m)

Understanding Time Complexity

When using Spark for classification, it is important to know how the time needed grows as data gets bigger.

We want to understand how training Logistic Regression and Random Forest models scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from pyspark.ml.classification import LogisticRegression, RandomForestClassifier

# Prepare training data
trainingData = spark.read.format("libsvm").load("data/mllib/sample_libsvm_data.txt")

# Logistic Regression model
lr = LogisticRegression(maxIter=10, regParam=0.3, elasticNetParam=0.8)
lrModel = lr.fit(trainingData)

# Random Forest model
rf = RandomForestClassifier(numTrees=20, maxDepth=5)
rfModel = rf.fit(trainingData)

This code trains two classifiers on the same data: Logistic Regression and Random Forest.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterations over data rows during model training.
• How many times: Logistic Regression runs multiple iterations (maxIter) over all data; Random Forest builds multiple trees (numTrees), each traversing data multiple times depending on tree depth.

How Execution Grows With Input

As the number of data points grows, the time to train increases roughly in proportion to the number of data points and the number of iterations or trees.

Input Size (n)	Approx. Operations
10	Small number of passes over 10 rows
100	About 10 times more work than 10 rows
1000	About 100 times more work than 10 rows

Pattern observation: Training time grows roughly linearly with data size multiplied by number of iterations or trees.

Final Time Complexity

Time Complexity: O(n * m)

This means training time grows roughly in proportion to the number of data points (n) times the number of iterations or trees (m).

Common Mistake

[X] Wrong: "Training time depends only on the number of data points, not on iterations or trees."

[OK] Correct: Each iteration or tree requires a full pass over the data, so more iterations or trees multiply the work.

Interview Connect

Understanding how training time grows helps you explain model choices and resource needs clearly in real projects.

Self-Check

"What if we increase the maxDepth of the Random Forest trees? How would the time complexity change?"

Practice

1. What is the main purpose of Logistic Regression in Spark MLlib classification?

easy

A. To predict the probability of a binary outcome

B. To cluster data into groups without labels

C. To reduce the number of features in the dataset

D. To generate random decision trees

Solution

1. Step 1: Understand Logistic Regression's goal

   Logistic Regression predicts the probability that an input belongs to a class, usually binary (yes/no).

2. Step 2: Compare with other options

   Clustering is unsupervised, feature reduction is different, and random trees relate to Random Forest, not Logistic Regression.

3. Final Answer:

   To predict the probability of a binary outcome -> Option A

4. Quick Check:

   Logistic Regression = Binary probability prediction [OK]

Hint: Logistic Regression predicts yes/no probabilities [OK]

Common Mistakes:

• Confusing classification with clustering
• Thinking Logistic Regression reduces features
• Mixing Logistic Regression with Random Forest

2. Which of the following is the correct way to import LogisticRegression from Spark MLlib in Python?

easy

A. import LogisticRegression from pyspark.ml

B. from pyspark.ml.classification import LogisticRegression

C. from pyspark.ml import LogisticRegression

D. from pyspark.ml.classification import logisticregression

Solution

1. Step 1: Recall correct import syntax

   The correct import uses 'from pyspark.ml.classification import LogisticRegression' with exact casing.

2. Step 2: Check other options for errors

   import LogisticRegression from pyspark.ml has wrong import order, C misses classification submodule, D uses wrong case for class name.

3. Final Answer:

   from pyspark.ml.classification import LogisticRegression -> Option B

4. Quick Check:

   Correct import syntax = from pyspark.ml.classification import LogisticRegression [OK]

Hint: Use exact module and class names with correct case [OK]

Common Mistakes:

• Wrong import order or missing submodule
• Incorrect capitalization of class names
• Assuming all classes are in pyspark.ml directly

3. Given the following Spark code snippet, what will be the output of predictions.select('prediction').show()?

from pyspark.ml.classification import LogisticRegression
from pyspark.ml.feature import VectorAssembler

# Sample data
data = spark.createDataFrame([
  (0, 1.0, 3.0),
  (1, 2.0, 1.0),
  (0, 1.5, 2.5)
], ['label', 'feature1', 'feature2'])

assembler = VectorAssembler(inputCols=['feature1', 'feature2'], outputCol='features')
data = assembler.transform(data)

lr = LogisticRegression(featuresCol='features', labelCol='label')
model = lr.fit(data)
predictions = model.transform(data)

medium

A. Shows predicted labels as 0.0 or 1.0 for each row

B. Shows raw feature vectors for each row

C. Throws an error because 'prediction' column is missing

D. Shows only the label column values

Solution

1. Step 1: Understand model.transform output

   LogisticRegression's transform adds a 'prediction' column with predicted labels (0.0 or 1.0).

2. Step 2: Check what predictions.select('prediction').show() does

   This command displays the predicted labels for each row, not features or original labels.

3. Final Answer:

   Shows predicted labels as 0.0 or 1.0 for each row -> Option A

4. Quick Check:

   Prediction column = predicted labels [OK]

Hint: Model.transform adds 'prediction' column with labels [OK]

Common Mistakes:

• Expecting raw features instead of predictions
• Assuming 'prediction' column is missing
• Confusing label column with prediction column

4. Identify the error in this Spark RandomForest classification code snippet:

from pyspark.ml.classification import RandomForestClassifier

rf = RandomForestClassifier(labelCol='label', featuresCol='features')
model = rf.fit(data)
predictions = model.transform(data)
predictions.select('prediction').show()

Assuming data has columns 'label' and 'features'.

medium

A. RandomForestClassifier requires setting numTrees parameter

B. Missing import for VectorAssembler

C. Features column must be assembled before fitting

D. No error; code runs correctly

Solution

1. Step 1: Check if data has required columns

   The question states data already has 'label' and 'features' columns, so no need to assemble features here.

2. Step 2: Verify RandomForestClassifier usage

   RandomForestClassifier can run with default parameters; numTrees is optional. The code fits and predicts correctly.

3. Final Answer:

   No error; code runs correctly -> Option D

4. Quick Check:

   Data with 'features' and 'label' = code runs [OK]

Hint: Check if data has features before assuming errors [OK]

Common Mistakes:

• Assuming numTrees is mandatory
• Forgetting features must be assembled before fitting
• Confusing import errors with runtime errors

5. You want to improve classification accuracy on a Spark dataset with many features and possible overfitting. Which approach is best to try first?

hard

A. Train LogisticRegression with only one feature

B. Use LogisticRegression without feature scaling

C. Use RandomForest with more trees and limit tree depth

D. Remove the label column before training

Solution

1. Step 1: Understand overfitting and feature impact

   Overfitting happens when model is too complex; limiting tree depth in RandomForest helps reduce it.

2. Step 2: Evaluate options for improving accuracy

   Increasing trees and limiting depth balances bias and variance. LogisticRegression without scaling or removing label harms model. Using one feature loses information.

3. Final Answer:

   Use RandomForest with more trees and limit tree depth -> Option C

4. Quick Check:

   Control complexity to reduce overfitting [OK]

Hint: Limit tree depth in RandomForest to reduce overfitting [OK]

Common Mistakes:

• Ignoring feature scaling when needed
• Removing label column by mistake
• Using too few features reduces accuracy