Data Mining Exam Preparation: 8 Essential Practice Questions

Data Mining and Warehousing

Data mining is the art and science of discovering hidden patterns, extracting meaningful insights, and making data-driven decisions from massive datasets. Whether you are preparing for a university examination, a technical interview, or simply aiming to solidify your understanding, mastering the core concepts of data mining is non-negotiable.

This guide is not just a list of questions, it is a strategic weapon. Each of the eight comprehensive questions has been carefully curated to test not only your recall but your ability to reason, calculate, compare, and apply data mining techniques in real-world scenarios. The content is structured to mirror the depth and rigor expected in advanced data mining courses and professional certifications.

By the end of this guide, you will be able to:

• Explain the core principles behind data preprocessing, data warehousing, classification, and clustering

• Perform calculations for information gain, Bayesian probabilities, and distance metrics

• Identify the strengths and weaknesses of each data mining technique

• Navigate the trade-offs between accuracy, interpretability, scalability, and computational cost

• Confidently answer any exam question thrown your way

Question 1: Multiple Choice (10 items, 1 mark each)

1.1 Which of the following is NOT a characteristic of a data warehouse as defined by Inmon? a) Subject-oriented b) Integrated c) Volatile d) Time-variant

1.2 What is the primary difference between classification and clustering? a) Classification is supervised; clustering is unsupervised b) Clustering is supervised; classification is unsupervised c) Both are supervised learning methods d) Both are unsupervised learning methods

1.3 In the KDD process, which step comes immediately before Data Mining? a) Data Cleaning b) Data Selection c) Pattern Evaluation d) Data Transformation

1.4 Which OLAP operation involves summarizing data by climbing up a concept hierarchy? a) Drill down b) Roll up c) Slice d) Dice

1.5 What is the main advantage of using Gain Ratio over Information Gain as an attribute selection measure? a) It's computationally faster b) It handles continuous attributes better c) It reduces bias toward attributes with many values d) It always produces smaller trees

1.6 In the Naive Bayes classifier, what assumption is made about attributes? a) They are all numerical b) They are conditionally independent given the class c) They follow a normal distribution d) They are all categorical

1.7 Which of the following is NOT a type of data reduction technique? a) Dimensionality reduction b) Numerosity reduction c) Data integration d) Data compression

1.8 What are support vectors in SVM? a) All training examples b) Training examples that lie closest to the decision boundary c) Examples that are misclassified d) The mean of each class

1.9 Which data warehouse model normalizes dimensional hierarchies into smaller dimension tables? a) Star schema b) Snowflake schema c) Fact constellation d) Galaxy schema

1.10 What does the Jaccard coefficient measure? a) Correlation between numerical variables b) Similarity between asymmetric binary variables c) Distance between categorical variables d) Entropy of a dataset

Question 1

1.1 c) Volatile. Data warehouses are non-volatile: data is not updated but only loaded and accessed. Operational databases are volatile (frequently updated), but data warehouses maintain historical data that is read-only. This characteristic ensures that data warehouses provide a stable, consistent view of historical data for decision-making, unlike operational systems where data changes constantly.

1.2 a) Classification is supervised; clustering is unsupervised. Classification uses labeled training data (the class labels are known) to build a model that predicts class labels for new data. Clustering discovers patterns without predefined labels, grouping similar data objects together based on inherent similarities. Example: classification predicts whether a customer will buy a product (Yes/No) based on historical purchase data with known outcomes; clustering automatically groups customers into segments based on purchasing behavior without knowing the segments beforehand.

1.3 d) Data Transformation. The KDD process follows this sequence: Data Cleaning, Data Integration, Data Selection, Data Transformation, Data Mining, Pattern Evaluation, Knowledge Presentation. Data transformation prepares the data for mining by normalizing, aggregating, or constructing new attributes, ensuring the mining algorithms can work effectively with the data.

1.4 b) Roll up. Roll up (also called drill-up) summarizes data by moving up the concept hierarchy, for example aggregating sales from City to Region to Country to All. Drill down (roll down) is the reverse, moving from summary to detailed data. Slice selects a single dimension value. Dice selects a subcube by specifying ranges on multiple dimensions. Pivot (rotate) reorients the cube visualization.

1.5 c) It reduces bias toward attributes with many values. Information Gain tends to favor attributes with many distinct values (like ID attributes) even if they're not actually useful for classification. Gain Ratio normalizes Information Gain by SplitInfo, reducing this bias. Formula: GainRatio(A) = Gain(A) / SplitInfo(A). If an attribute has a unique value for each tuple, Information Gain would be high (implying it's important), but Gain Ratio would reveal it's actually not useful.

1.6 b) They are conditionally independent given the class. This is the "naive" assumption: that the effect of each attribute on the class label is independent of all other attributes. This simplifies the probability calculation from a complex joint probability P(X|C) = P(x1, x2, ..., xn|C) to a product P(X|C) = P(x1|C) × P(x2|C) × ... × P(xn|C). While this assumption is often violated in real data, Naive Bayes still performs surprisingly well in many applications like spam filtering and document classification.

1.7 c) Data integration. Data integration is a preprocessing step, not a data reduction technique. Data reduction strategies include dimensionality reduction (PCA, attribute subset selection), numerosity reduction (regression, histograms, clustering, sampling), and data compression (lossless and lossy). Data integration combines multiple sources, while data reduction reduces the volume of data while preserving analytical results.

1.8 b) Training examples that lie closest to the decision boundary. Support vectors are the critical training examples that define the margin of the separating hyperplane. They "support" the hyperplane: if all other training examples are removed, the same separating hyperplane would be found. The number of support vectors determines the complexity of the classifier and is used to compute the upper bound on the expected error rate.

1.9 b) Snowflake schema. A snowflake schema is a refinement of the star schema where dimension tables are normalized into a set of smaller, interconnected dimension tables, forming a shape similar to a snowflake. Compared to a star schema, it is more normalized, uses less redundant storage, has slower query performance due to more joins, and is harder to understand.

1.10 b) Similarity between asymmetric binary variables. The Jaccard coefficient measures similarity between asymmetric binary attributes where the presence of a feature is more important than its absence. Formula: Jaccard(A, B) = M11 / (M10 + M01 + M11). In market basket analysis, this measures similarity between customers based on purchased items, ignoring items neither purchased, which makes it suitable for binary data where presence matters more than absence.

Question 2: True or False (10 items, 1 mark each)

2.1 Data mining and Knowledge Discovery in Databases (KDD) are identical processes.

2.2 In a decision tree, the root node represents the most important attribute for classification.

2.3 Euclidean distance and Manhattan distance produce identical results for all data points.

2.4 In data warehousing, the apex cuboid represents the most detailed level of data.

2.5 The Naive Bayes classifier assumes attributes are conditionally independent given the class.

2.6 Overfitting occurs when a model performs well on training data but poorly on unseen data.

2.7 The holdout method for model evaluation partitions data into training and test sets.

2.8 In SVM, the margin is the distance between the separating hyperplane and the support vectors.

2.9 A data mart is always dependent on an enterprise data warehouse.

2.10 Bagging and Boosting are both ensemble methods that combine multiple classifiers.

Question 2

2.1 False. KDD is the overall process that includes data mining as one step. Data mining is the core analysis step within KDD. The KDD process is: Data Cleaning, Data Integration, Data Selection, Data Transformation, Data Mining, Pattern Evaluation, Knowledge Presentation. Think of KDD as building a house (the whole process) and data mining as laying the bricks (one crucial step).

2.2 True. The root node is selected using an attribute selection measure, like Information Gain or Gain Ratio, that identifies the attribute providing the highest discriminatory power at the top level. It provides the highest information gain, best separates the training examples, and creates the purest child nodes.

2.3 False. They are different metrics that produce different results except in special cases. Euclidean distance (√Σ(xi-yi)²) is the straight-line distance and is sensitive to outliers; Manhattan distance (Σ|xi-yi|) is the sum of absolute differences and is more robust. For points (0,0) and (1,1): Euclidean = √(1²+1²) = 1.414, Manhattan = 1+1 = 2. They are equal only when points differ in exactly one dimension.

2.4 False. The apex cuboid represents the highest level of summarization (the 0-D cuboid with a single cell), the most summarized data. The base cuboid represents the most detailed level of data. In a sales cube with dimensions (Product, Time, Location), the apex is total sales as one number, while the base is sales per product per day per store.

2.5 True. This is the fundamental assumption of the Naive Bayes classifier: P(X|C) = P(x1|C) × P(x2|C) × ... × P(xn|C). In real data, attributes are often correlated (for example age and income), and the independence assumption is rarely true, but despite this it works well in practice for tasks like spam filtering, document classification, and medical diagnosis with conditionally independent symptoms.

2.6 True. Overfitting happens when a model captures noise and anomalies in the training data rather than general patterns. Signs include high accuracy on training data but low accuracy on test data, and a large gap between training and test performance. Causes include an overly complex model, not enough training data, and no regularization.

2.7 True. The holdout method randomly partitions data into a training set (typically two-thirds of the data) for model construction and a test set (typically one-third) for accuracy estimation. Variations include random sampling (repeat holdout k times and average accuracies) and cross-validation. The test set must be independent of the training set to get an unbiased estimate of accuracy.

2.8 True. The margin is the distance from the separating hyperplane to the support vectors on both sides, and SVM maximizes this margin. A larger margin generally means better generalization, while a smaller margin is more likely to overfit.

2.9 False. Data marts can be independent or dependent. A dependent data mart is created directly from an enterprise data warehouse, giving consistent, governed data and better integration. An independent data mart is created directly from operational data sources, which is faster to build but specific to department needs and may cause data inconsistencies.

2.10 True. Both are ensemble methods that combine multiple base classifiers to create a stronger overall classifier. Bagging trains models in parallel with equal weighting and combines them by majority voting, aiming to reduce variance. Boosting trains models sequentially, focusing on misclassified tuples and combining them by weighted voting, aiming to reduce bias.

Question 3: Matching (10 items, 1 mark each)

Match each term in Column A to its correct description in Column B.

Column A

1. OLAP

2. Entropy

3. Precision

4. K-fold Cross-validation

5. Principal Component Analysis (PCA)

6. Support Vector Machine (SVM)

7. Data Cleaning

8. Apriori Algorithm

9. ROC Curve

10. Backpropagation

Column B A. Measures the impurity or randomness in a dataset B. Neural network learning algorithm that adjusts weights backwards C. Online Analytical Processing for multidimensional data analysis D. Visual comparison tool showing true vs false positive rates E. A classifier that finds the maximum margin separating hyperplane F. Dimensionality reduction technique using eigenvectors G. The percentage of positive predictions that are actually correct H. Model evaluation technique dividing data into k subsets for training and testing I. Algorithm for mining frequent itemsets and association rules J. Process of handling missing values, noise, and inconsistencies

Answer Key Question 3

1–C, 2–A, 3–G, 4–H, 5–F, 6–E, 7–J, 8–I, 9–D, 10–B

Question 4: Bayesian Classification (10 marks)

Part A: Probability Calculation (4 marks)

Given the training data for the "Buys Computer" problem below, classify the new tuple.

Training Data:

New tuple to classify: X = (Age = <=30, Income = Medium, Student = Yes, Credit Rating = Fair)

Solution

Prior probabilities: P(Yes) = 9/14 = 0.643, P(No) = 5/14 = 0.357

Conditional probabilities for class Yes: P(age <=30) = 2/9 = 0.222, P(income medium) = 4/9 = 0.444, P(student yes) = 6/9 = 0.667, P(credit fair) = 6/9 = 0.667

Conditional probabilities for class No: P(age <=30) = 3/5 = 0.600, P(income medium) = 2/5 = 0.400, P(student yes) = 1/5 = 0.200, P(credit fair) = 2/5 = 0.400

P(X|Yes) = 0.222 × 0.444 × 0.667 × 0.667 = 0.044 P(X|No) = 0.600 × 0.400 × 0.200 × 0.400 = 0.019

P(Yes|X) = P(X|Yes) × P(Yes) = 0.044 × 0.643 = 0.028 P(No|X) = P(X|No) × P(No) = 0.019 × 0.357 = 0.007

Since P(Yes|X) > P(No|X), the new tuple is classified as Buys Computer = Yes.

Part B: Laplacian Correction (2 marks)

Using Laplacian correction, calculate the corrected probability for P(Income = Low | Buys Computer = Yes) if this combination never appeared in the training data.

Solution

Without correction: P(Income = Low | Yes) = 0/9 = 0

With Laplacian correction (k = 1), where the number of possible values for Income is 3 (High, Medium, Low) and the total count for class Yes is 9:

P(Income = Low | Yes) = (0 + 1) / (9 + 3) = 1/12 = 0.083

This avoids zero probabilities that would make the entire product zero, maintains reasonable estimates close to the original proportions, and adds a small pseudo-count to each possible value. Even though we've never seen a low-income person buy a computer in the training data, we estimate a small probability (8.3%) based on the assumption that it's possible.

Part C: Short Answer (4 marks)

Draw the Bayesian network structure for the Buys Computer problem and explain why the Naive Bayes assumption simplifies computation but may sacrifice accuracy in some scenarios.

Solution

Bayesian network structure:

                        [Buys Computer]
                        /      |      |      \
                       /       |      |       \
                      /        |      |        \
                   [Age]   [Income] [Student] [Credit Rating]

Naive Bayes assumes all attributes are conditionally independent given the class, simplifying P(X|C) from a joint probability to a product: P(X|C) = P(x1|C) × P(x2|C) × ... × P(xn|C).

Advantages of this assumption: computational efficiency (much faster to calculate), data efficiency (requires less training data), simple implementation, and it works well in practice, often performing competitively with more complex models.

Limitations: real attributes are frequently correlated. Age and Income are often correlated in real data. In medical diagnosis, symptoms like fever and cough are not independent. In text classification, words in a document are correlated (for example "machine" and "learning"). In spatial data, nearby locations share similar properties. In the Buys Computer problem specifically, younger people tend to have lower incomes, students typically have lower incomes, and higher income often leads to better credit ratings, all of which are dependencies Naive Bayes ignores.

It still works well when dependencies are weak or cancel out, when the goal is classification rather than probability estimation, and when data is high-dimensional.

Questions 5–8: Extended Answer Section (20 marks each)

Question 5 Data Preprocessing (20 marks)

Part A: Handling Missing Data (6 marks)

You have a dataset of 1,000 customer records with income information. 150 records have missing income values.

a) Describe four methods for handling missing data, explaining when each is appropriate. (4 marks)

Solution

Ignore the tuple: remove any record with missing values. Appropriate when the class label is missing or missing values are under 5%. Limitation: can lose valuable data if missing values are common. Example: dropping a customer record entirely.

Fill with global constant: replace with "unknown" or 0. Appropriate as a simple fallback when domain knowledge is limited. Limitation: may introduce bias if the constant is not representative. Example: replacing missing income with "unknown".

Fill with attribute mean: replace with the average of all available values. Appropriate when data is relatively uniform and missing values are random. Limitation: reduces variance and may underestimate spread. Example: replacing missing income with $50,000, the mean.

Fill with most probable value: use inference, such as a Bayesian formula or decision tree, to predict the value. Appropriate when strong correlations with other attributes exist. Advantage: most sophisticated, maintains data patterns. Example: predicting income from education and occupation.

b) Calculate the mean absolute deviation and standardized z-score for the income attribute with the following values: [45,000, 52,000, 48,000, 55,000, 50,000]. (2 marks)

Solution

Mean = (45,000 + 52,000 + 48,000 + 55,000 + 50,000) / 5 = 250,000 / 5 = 50,000

Absolute deviations: |45,000-50,000| = 5,000; |52,000-50,000| = 2,000; |48,000-50,000| = 2,000; |55,000-50,000| = 5,000; |50,000-50,000| = 0

Mean Absolute Deviation (MAD) = (5,000 + 2,000 + 2,000 + 5,000 + 0) / 5 = 14,000 / 5 = 2,800

Z-scores (using MAD): z1 = (45,000-50,000)/2,800 = -1.79; z2 = (52,000-50,000)/2,800 = 0.71; z3 = (48,000-50,000)/2,800 = -0.71; z4 = (55,000-50,000)/2,800 = 1.79; z5 = 0

Resulting z-scores: [-1.79, 0.71, -0.71, 1.79, 0]. z-scores show how many MAD units each value is from the mean; negative values are below the mean, positive values are above. Using MAD is more robust than using standard deviation.

Part B: Data Reduction (6 marks)

You have a dataset with 10,000 rows and 50 attributes and want to reduce it for faster analysis.

a) Explain Principal Component Analysis (PCA) and list its steps. (4 marks)

Solution

PCA is a dimensionality reduction technique that transforms the original attributes into a new set of uncorrelated variables called principal components, ordered by the amount of variance they capture. The key idea is to find the projection that captures the largest amount of variation in the data.

The six steps: standardize the data so each attribute has mean 0 and variance 1, ensuring all attributes contribute equally regardless of scale; compute the covariance matrix between all pairs of attributes; compute the eigenvalues and eigenvectors of that covariance matrix, where each eigenvector represents a principal component and each eigenvalue indicates the variance explained by it; sort the eigenvalues and eigenvectors in decreasing order so the first component captures the most variance; select the top k principal components that capture most of the variance, for example 95%, which determines the new dimensionality; and transform the data by projecting the original data onto the selected eigenvectors, producing a reduced dataset with k dimensions.

Advantages: works well for numerical data, reduces computational cost, helps visualize high-dimensional data, removes correlated features. Limitations: only works for numerical data, new features are hard to interpret, and it assumes linear relationships.

b) Compare the equal-width and equal-frequency histogram binning methods. (2 marks)

Solution

Equal-width binning divides the data range into equal-sized intervals; all bins have the same width. It is simple to implement and understand but can be skewed if the data is unevenly distributed. It is best used when data is uniformly distributed, for example income bins of 0-50k, 50k-100k, 100k-150k.

Equal-frequency binning divides the data so each bin contains approximately the same number of values; bin widths vary based on the data distribution. It better represents data density, though its boundaries may be less interpretable. It is best used when data has an uneven distribution with outliers, for example bins where each contains 20% of observations.

Part C: Data Transformation (8 marks)

a) A salary attribute has values [45,000, 52,000, 48,000, 55,000, 50,000]. Apply Min-Max normalization to map values to the range [0, 1]. Show your calculations. (4 marks)

Solution

Formula: v' = (v - min) / (max - min) × (new_max - new_min) + new_min, with min = 45,000, max = 55,000, new_min = 0, new_max = 1.

45,000 → 0.00; 52,000 → 7,000/10,000 = 0.70; 48,000 → 3,000/10,000 = 0.30; 55,000 → 10,000/10,000 = 1.00; 50,000 → 5,000/10,000 = 0.50

Result: [0.00, 0.70, 0.30, 1.00, 0.50]. The highest salary maps to 1.00, the lowest to 0.00, all values fall between 0 and 1, and the relative ordering is preserved.

b) Explain the differences between Min-Max normalization, Z-score normalization, and Decimal scaling. When would you use each? (4 marks)

Solution

Min-Max normalization, (v-min)/(max-min) × (new_max-new_min) + new_min, is used when you need bounded values such as [0,1] and know the min and max, for example neural networks with sigmoid activation. It preserves relationships and is simple to understand, but is sensitive to outliers, and new values falling outside the original min/max get clipped.

Z-score normalization, (v-μ)/σ, is used when data is roughly normal and outliers are present, and when you want zero mean and unit variance. It is more robust to outliers when using robust statistics and handles values outside the training range, but it does not bound values and requires the mean and standard deviation.

Decimal scaling, v/10^j where j is the smallest integer such that the maximum absolute scaled value is less than 1, is used for quick, approximate scaling. It is the simplest method and maintains relative distances, but can result in very small values and is not standardized.

As a rough guide: use Min-Max for neural networks with sigmoid or tanh activations and when interpretable results are needed; use Z-score when outliers are present or algorithms assume a normal distribution; use decimal scaling for quick exploration.

Question 6 Data Warehouse and OLAP (20 marks)

Part A: Schema Design (8 marks)

A retail company wants to build a data warehouse to analyze sales performance across stores, products, and time.

a) Design a Star Schema for the sales data warehouse. Identify the fact table and dimension tables, including likely attributes for each. (6 marks)

Solution

Star schema design: a central Sales_Fact table connected to Time_Dim, Product_Dim, Store_Dim, and Customer_Dim.

Fact table Sales_Fact holds: time_key, product_key, store_key, customer_key (all foreign keys), and the measures units_sold, dollars_sold, cost_dollars, and the derived profit_dollars (dollars_sold minus cost_dollars).

Time_Dimension holds: time_key (primary key), date, day_of_week, month, quarter, year, holiday_flag.

Product_Dimension holds: product_key (primary key), product_name, category, sub_category, brand, unit_price.

Store_Dimension holds: store_key (primary key), store_name, city, state, region, store_type.

Customer_Dimension holds: customer_key (primary key), customer_name, age_group, income_level, loyalty_status.

Key design principles: the grain is each fact row representing a sale transaction at the atomic level; measures are additive so they can be summed across dimensions; dimensions hold descriptive attributes for analysis; and surrogate keys are used for performance.

b) Explain how a Snowflake Schema would differ from your Star Schema design and discuss the trade-offs. (2 marks)

Solution

In a snowflake schema, instead of a single Product_Dim table, the hierarchy splits into Product, Category, and Brand tables; instead of a single Store_Dim table, it splits into Store, City, State, and Region tables.

Trade-offs: the snowflake schema uses less redundant, more efficient storage, but has more joins and therefore slower queries; it offers better data integrity but is more complex to maintain and understand than a star schema. For most data warehouses, star schema is preferred for its query performance and simplicity; snowflake is used mainly when storage is expensive or dimension tables are very large and need normalizing.

Part B: OLAP Operations (6 marks)

A manager is analyzing sales data for the year 2024.

a) Describe roll up, drill down, slice, and dice using this data. (4 marks)

Solution

Roll up (summarization) moves up the hierarchy to get a more summarized view. Instead of Q1 through Q4, show the total per product: Laptop = 6.6M, Tablet = 3.8M, Smartphone = 11.5M.

Drill down (detail) moves down the hierarchy to see more detailed data, for example expanding Q1 sales into January, February, and March figures, allowing more detailed trend analysis.

Slice selects a single dimension value to create a 2D view, for example viewing only Smartphone sales across all quarters: Q1=2.5M, Q2=2.8M, Q3=3.0M, Q4=3.2M.

Dice selects a subcube by specifying ranges on multiple dimensions, for example Product in {Laptop, Smartphone} and Time in {Q1, Q2}, giving Laptop Q1=1.2M, Q2=1.5M and Smartphone Q1=2.5M, Q2=2.8M.

b) Explain Pivot (Rotate) with an example from the data. (2 marks)

Solution

Pivot reorients the cube visualization, changing which dimensions appear in rows versus columns to provide different perspectives on the same data. Before pivoting, products are in rows and quarters in columns. After pivoting, quarters are in rows and products in columns, for example Q1 showing Laptop=1.2M, Tablet=0.8M, Smartphone=2.5M. This gives a different perspective on the same data and can reveal patterns not visible in the original orientation.

Part C: OLAP vs OLTP (6 marks)

a) Compare OLTP and OLAP systems based on purpose, data characteristics, query types, and performance requirements. (4 marks)

Solution

OLTP records day-to-day business transactions using current, detailed data, with simple SELECT, INSERT, UPDATE, and DELETE queries, and needs high throughput with fast response time. Its data model is normalized (3NF) for efficiency, its users are operational staff and clerks, and it involves frequent updates.

OLAP supports decision-making and analysis using historical, summarized data, with complex analytical queries involving aggregations. It needs fast response to complex queries and is less concerned with updates. Its data model is denormalized (star or snowflake) for analysis, its users are decision-makers, analysts, and managers, and it typically holds five to ten years of historical data loaded in periodic batches.

b) Why is it beneficial to maintain a separate data warehouse rather than performing analytical queries directly on the operational database? (2 marks)

Solution

Performance: OLTP databases are tuned for fast transaction processing, and complex analytical queries would slow down daily operations, so a separate warehouse can be optimized specifically for analysis.

Data integration: warehouses combine data from multiple sources (for example sales, marketing, and customer service), while operational databases typically hold only one system's data.

Historical data: operational databases often purge old data, while warehouses maintain years of history, which is essential for trend analysis and seasonality detection.

Data quality: data can be cleaned, transformed, and standardized in the warehouse, correcting inconsistencies like different date formats, currency values, or product codes found in operational data.

Security and resource isolation: analysts don't need direct access to operational systems, which reduces risk to production, and OLAP queries won't compete with OLTP transactions for resources.

Question 7 Classification Methods (20 marks)

Part A: Decision Tree Construction (8 marks)

Build a decision tree for the "Buy Computer" dataset from Question 4. The attributes are Age, Income, Student, and Credit Rating, with class label Buys Computer.

a) Calculate the Information Gain for the attribute "Age" to determine if it should be the root node. Show all calculations. (4 marks)

Solution

Given 14 total tuples, 9 Yes and 5 No:

Entropy(D) = -(9/14)log2(9/14) - (5/14)log2(5/14) = -(0.643 × -0.637) - (0.357 × -1.486) = 0.410 + 0.531 = 0.941 bits

Age <=30: 5 tuples (2 Yes, 3 No). Entropy = -(2/5)log2(2/5) - (3/5)log2(3/5) = 0.529 + 0.442 = 0.971

Age 31-40: 4 tuples (4 Yes, 0 No). Entropy = 0

Age >40: 5 tuples (3 Yes, 2 No). Entropy = -(3/5)log2(3/5) - (2/5)log2(2/5) = 0.442 + 0.529 = 0.971

Weighted average entropy: Info_Age(D) = (5/14)(0.971) + (4/14)(0) + (5/14)(0.971) = 0.347 + 0 + 0.347 = 0.694 bits

Information Gain: Gain(Age) = Entropy(D) - Info_Age(D) = 0.941 - 0.694 = 0.247 bits

Age provides an information gain of 0.247 bits.

b) Draw the complete decision tree, with the root splitting on the attribute with the highest gain. Clearly label all nodes, branches, and leaf nodes. (4 marks)

Solution

                        [Age]
                      /    |    \
                  <=30   31-40   >40
                   /        |       \
                 Age     [Yes]    Credit Rating
                /   \              /           \
            Student Yes         Excellent      Fair
             /    \                |             |
          No     Yes            [No]          [Yes]
           |       |
         [No]    [Yes]

Rules in IF-THEN format: R1: IF Age = 31-40 THEN Buys_Computer = Yes R2: IF Age > 40 AND Credit_Rating = Excellent THEN Buys_Computer = No R3: IF Age > 40 AND Credit_Rating = Fair THEN Buys_Computer = Yes R4: IF Age <= 30 AND Student = No THEN Buys_Computer = No R5: IF Age <= 30 AND Student = Yes THEN Buys_Computer = Yes

The tree is three levels deep with five pure leaves, and is easy to understand and explain.

Part B: Model Evaluation (6 marks)

A classifier was tested on 2,000 instances with the following confusion matrix:

a) Calculate accuracy, error rate, precision, and recall. (4 marks)

Solution

TP = 900, FP = 80, FN = 100, TN = 920, Total = 2,000

Accuracy = (TP+TN)/Total = (900+920)/2000 = 1820/2000 = 0.91 = 91%

Error Rate = 1 - Accuracy = 0.09 = 9% (equivalently (FP+FN)/Total = 180/2000)

Precision = TP/(TP+FP) = 900/980 = 0.918 = 91.8%

Recall = TP/(TP+FN) = 900/1000 = 0.90 = 90%

b) Calculate the F1-score and interpret what it means. (2 marks)

Solution

F1 = 2 × (Precision × Recall) / (Precision + Recall) = 2 × (0.918 × 0.900) / (0.918 + 0.900) = 1.6524/1.818 = 0.909 = 90.9%

The F1-score of 90.9% indicates excellent classifier performance that balances precision and recall: very few false positives (91.8% precision) and very few false negatives (90% recall). F1-score is most useful when class distribution is uneven, when a single comparison metric is needed, or when both false positives and false negatives matter.

Part C: Ensemble Methods (6 marks)

Three classifiers have the following accuracies on validation data: Classifier A 75%, Classifier B 80%, Classifier C 82%.

a) Explain the Bagging ensemble method and how you would use these three classifiers. (3 marks)

Solution

Bagging (Bootstrap Aggregating) creates multiple training datasets by sampling with replacement from the original data (each bootstrap sample is the same size as the original, and about 63% of the original data appears in each sample), trains a separate classifier on each bootstrap sample independently and in parallel, then aggregates: majority voting for classification, averaging for regression.

Applied to the three classifiers: each is trained on its own bootstrap sample. For a new instance, if Classifier A predicts Yes, Classifier B predicts Yes, and Classifier C predicts No, the final prediction by majority vote is Yes. Bagging reduces variance in high-variance classifiers and usually improves accuracy compared to single models; Random Forest is a popular bagging algorithm built on decision trees.

b) Explain the Boosting ensemble method and compare it with Bagging. (3 marks)

Solution

Boosting (for example AdaBoost) assigns weights to each training tuple, initially equal, and trains classifiers sequentially: after each classifier, the weights of misclassified tuples increase so the next classifier focuses more on the hard examples. Each classifier's vote is weighted by its accuracy (αt = ½ × ln((1-error)/error)), and the final prediction is a weighted vote across all classifiers.

Comparison: Bagging trains in parallel with equal tuple weighting and equal voting, aiming to reduce variance, with lower overfitting risk; Random Forest is a typical example. Boosting trains sequentially, gives misclassified tuples higher weight, and votes are weighted by accuracy, aiming to reduce bias, with higher overfitting risk; AdaBoost and XGBoost are typical examples. Bagging is preferable when interpretability matters or data is noisy; Boosting is preferable when maximum accuracy is the goal and data is relatively clean.

Question 8 Clustering Analysis (20 marks)

Part A: Distance Measures (8 marks)

Consider two data points X = (2, 5, 8) and Y = (4, 7, 3).

a) Calculate the Euclidean distance, Manhattan distance, and Minkowski distance (q = 3) between X and Y. (6 marks)

Solution

Euclidean (q=2): d = √[(2-4)² + (5-7)² + (8-3)²] = √[4+4+25] = √33 = 5.745

Manhattan (q=1): d = |2-4| + |5-7| + |8-3| = 2+2+5 = 9

Minkowski (q=3): d = (|2-4|³ + |5-7|³ + |8-3|³)^(1/3) = (8+8+125)^(1/3) = (141)^(1/3) = 5.204

Manhattan distance is largest at 9.0, Euclidean is intermediate at 5.745, and Minkowski with q=3 sits closest to Euclidean at 5.204; as q increases, Minkowski approaches Chebyshev distance.

b) Explain the relationship between Minkowski distance and the other distance measures. (2 marks)

Solution

Minkowski distance, d = (Σ|xi-yi|^q)^(1/q), is a generalization: at q=1 it is Manhattan distance, at q=2 it is Euclidean distance, and as q approaches infinity it becomes Chebyshev distance (the maximum coordinate-wise difference). Lower q values, such as Manhattan, are more robust to outliers, while q=2 gives the familiar geometric straight-line distance. All q ≥ 1 satisfy the triangle inequality.

Part B: Clustering Methods (8 marks)

a) Describe the K-means clustering algorithm, including its steps and when it should be used. (4 marks)

Solution

K-means partitions n objects into k clusters where each object belongs to the cluster with the nearest mean (centroid). Steps: choose k and select k initial centroids; assign each object to its closest centroid, usually by Euclidean distance; recompute each centroid as the mean of the objects currently assigned to it; repeat the assignment and update steps until cluster assignments no longer change, a maximum number of iterations is reached, or centroid movement falls below a threshold.

K-means works well on large, numerical datasets with spherical, compact clusters when k is known in advance. It performs poorly on non-spherical clusters, clusters of very different sizes or densities, data with many outliers, or when k is unknown. Evaluation methods include within-cluster sum of squares (to minimize), the elbow method (plotting WCSS against k), and the silhouette score.

b) Compare Partitioning methods (like K-means) with Hierarchical clustering methods. (4 marks)

Solution

Partitioning methods like K-means divide data into k flat clusters, require specifying k beforehand, run in roughly O(n×k×i) time, scale well to large datasets, but can be non-deterministic depending on initialization, and are easy to interpret.

Hierarchical methods build a tree of clusters (a dendrogram) with no need to specify k in advance, since the dendrogram can be cut at any level. They typically run in O(n²) or O(n²logn) time, scale less well to large datasets, are deterministic, and are more informative since they show relationships between clusters, though the dendrogram itself takes more work to interpret.

Agglomerative (bottom-up) hierarchical clustering starts with each object as its own cluster and merges the closest clusters iteratively, and is the more common approach; divisive (top-down) starts with one cluster and splits it iteratively, and is less common because it is computationally expensive. Common linkage methods for hierarchical clustering are single linkage (minimum distance between clusters), complete linkage (maximum distance), average linkage, and Ward's method (minimizing within-cluster variance).

Partitioning is preferable for large datasets, when k is known, or when fast results are needed. Hierarchical is preferable when exploring different cluster granularities, when the data has a natural hierarchy, when k is unknown, or for small to medium datasets.

Part C: Data Types in Clustering (4 marks)

Consider the following mixed-type data:

a) Explain how you would handle mixed-type attributes for clustering. (2 marks)

Solution

First standardize interval and ratio attributes (using z-score or min-max normalization) so that attributes with larger scales, like income, don't dominate attributes with smaller scales, like age. Then treat each attribute type appropriately: scale interval attributes like Age to [0,1]; use Jaccard coefficient or simple matching for binary attributes like Gender; convert categorical attributes like City to binary dummy variables or use matching; apply a log transformation to skewed ratio attributes like Income before normalizing. The overall dissimilarity is then computed as a weighted combination across all attributes, for example using Gower's distance, which handles mixed types and missing values by having each attribute contribute a 0 to 1 similarity score to the overall combined distance.

b) For the City attribute, calculate the Simple Matching distance between each pair of cities. (2 marks)

Solution

Simple matching distance for a single categorical attribute is 0 if the values match and 1 if they differ. Since New York, London, and Tokyo are all different from one another, the distance is 1 for every pair: (1,2) = 1, (1,3) = 1, (2,3) = 1. Simple matching is appropriate for nominal categorical data where only sameness or difference matters, not degree of difference.

Goodluck!