Data Warehousing & Data Mining exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Data Warehousing & Data Mining
- Practise Apriori and FP-Growth by hand on a small transaction table of about eight to ten transactions: write each candidate itemset with its support count, prune against the minimum support, and then derive rules with their confidence so every step is visible on paper.
- For classification, work through decision tree construction by computing entropy, information gain and Gini index to three or four decimal places, and solve at least one Naive Bayes problem where you multiply each class prior P(C) by the conditional probabilities P(xᵢ|C) and pick the class with the highest result.
- Redraw the three-tier data warehouse architecture, the star, snowflake and fact constellation schemas, and an OLAP cube showing roll-up, drill-down, slice and dice until you can sketch each one neatly from memory and label every component.
- For clustering and preprocessing, trace k-means iterations with Euclidean distances on a few 2-D points, and practise min-max normalization, z-score normalization and equal-width or equal-depth binning, checking that min-max results fall inside the new target range and that smoothed bin values stay within the original data range.
Data Warehousing and Online Analytical Processing
Syllabus: Basic concepts of data warehousing; Data warehouse modeling: data cube and OLAP; Data warehouse design and usage; Data warehouse implementation; Cloud data warehouse; Data mining and pattern mining; Technologies and applications; Major issues in data mining; Data objects and attribute types; Basic statistical descriptions of data; Data visualization; Measuring data similarity and dissimilarity
One-page revision summary
- A data warehouse is a subject-oriented, integrated, time-variant and nonvolatile collection of data that supports management decisions.
- The three-tier architecture has a warehouse database server (bottom), an OLAP server (middle) and front-end query, reporting and mining tools (top).
- OLTP handles current day-to-day transactions, while OLAP analyses historical, summarised data for decision making.
- The multidimensional model views data as a cube of facts (measures) and dimensions, organised as star, snowflake or fact constellation schemas.
- OLAP operations include roll-up, drill-down, slice, dice and pivot, which move along concept hierarchies.
- Warehouse design takes four views: top-down (the information the business needs), data source (what operational systems capture), data warehouse (fact and dimension tables) and business query (what end users see); building can go top-down, bottom-up or both.
- The design process picks a business process to model, its grain, its dimensions and its measures; the warehouse then serves information processing, analytical processing and data mining, and OLAP leads naturally to multidimensional data mining.
- Implementation relies on partial materialization of cuboids, bitmap and join indexes, and ROLAP, MOLAP or HOLAP servers.
- Cloud data warehouses separate storage and compute, scale elastically, use columnar storage with parallel processing and charge per use.
- Data mining is the core step of the KDD process: cleaning, integration, selection, transformation, mining, evaluation and presentation.
- Patterns mined include characterization, discrimination, frequent patterns, associations, classification, regression, clusters and outliers.
- Data mining draws on statistics, machine learning, database and warehouse technology, information retrieval, visualization and high-performance computing.
- Applications include business intelligence, web search, fraud detection, recommendation and bioinformatics.
- Major issues cover mining methodology, user interaction, efficiency and scalability, diverse data types, and privacy and social impact.
- Attributes may be nominal, binary (symmetric or asymmetric), ordinal or numeric (interval-scaled or ratio-scaled), and discrete or continuous.
- Mean, median, mode and midrange describe central tendency; range, quartiles, IQR, variance and standard deviation describe dispersion.
- Visualization techniques: pixel-oriented methods colour one pixel per value in a window per attribute; geometric projection uses scatter-plot matrices or parallel coordinates; icon-based methods map attributes to Chernoff faces or stick figures; hierarchical methods such as treemaps nest subspaces; graph-based methods show relationships.
- Proximity measures differ by attribute type, and Minkowski distance generalises Manhattan, Euclidean and supremum distances.
Learn these by heart
- Number of cuboids: 2^n for n dimensions without hierarchies; Π(Li + 1) with hierarchies of Li levels.
- Outlier rule: a value is an outlier if it is below Q1 − 1.5 × IQR or above Q3 + 1.5 × IQR, where IQR = Q3 − Q1.
- Five-number summary: Minimum, Q1, Median, Q3, Maximum (the basis of a boxplot).
- Minkowski distance d = (Σ |xi − yi|^h)^(1/h); h = 1 Manhattan, h = 2 Euclidean, h → ∞ supremum.
- Asymmetric binary dissimilarity d = (r + s)/(q + r + s); Jaccard similarity = q/(q + r + s).
- Cosine similarity cos(x, y) = (x · y)/(||x|| × ||y||).
- Ordinal mapping z = (r − 1)/(M − 1), where r is the rank and M the number of states.
2-mark questions
1 Define a data warehouse and state its four key characteristics. 2 marks
A data warehouse is a database for decision support that is kept separate from the operational databases. It is subject-oriented (organised around topics such as sales), integrated (combines heterogeneous sources consistently), time-variant (stores historical data over long periods) and nonvolatile (loaded and read, rarely updated).
2 What is a cloud data warehouse? Give two of its advantages. 2 marks
A cloud data warehouse is a warehouse service hosted and managed by a cloud provider and accessed over the internet. Storage and compute are usually separate and elastic. Advantages: pay-per-use pricing with no hardware to buy, and automatic scaling, backup and maintenance handled by the provider.
3 A data cube has three dimensions with concept hierarchies of 3, 2 and 4 levels (excluding 'all'). How many cuboids does the full cube contain? 2 marks
The total number of cuboids is the product of (Li + 1), where Li is the number of levels of dimension i and the extra 1 stands for the virtual top level 'all'. Total = (3+1) × (2+1) × (4+1) = 4 × 3 × 5 = 60 cuboids.
4 Distinguish between nominal, ordinal and ratio-scaled attributes with one example each. 2 marks
A nominal attribute holds names or categories with no order, for example hair colour. An ordinal attribute has a meaningful order but unknown gaps between values, for example grade (A, B, C). A ratio-scaled attribute is numeric with a true zero, so ratios make sense, for example weight in kg.
5 Name the main categories of data visualization techniques. 2 marks
The main categories are: pixel-oriented techniques (one coloured pixel per value), geometric projection techniques (scatter-plot matrices, parallel coordinates), icon-based techniques (Chernoff faces, stick figures), hierarchical techniques (worlds-within-worlds, treemaps), and techniques for complex data and relations such as tag clouds and graphs.
6 For two objects described by asymmetric binary attributes, q = 2 (both 1), r = 1, s = 1 and t = 4 (both 0). Find the dissimilarity and the Jaccard coefficient. 2 marks
For asymmetric binary attributes the negative matches t are ignored. Dissimilarity d = (r + s)/(q + r + s) = (1 + 1)/(2 + 1 + 1) = 2/4 = 0.5. Jaccard coefficient = q/(q + r + s) = 2/4 = 0.5, which equals 1 − d.
10-mark questions
1 Explain the three-tier architecture of a data warehouse with a neat diagram. Also compare OLTP and OLAP systems. 10 marks
A data warehouse supports analysis and decision making, so it is built as a layered system that separates data storage, analytical processing and user presentation. The usual design is a three-tier architecture.
1. Bottom tier (warehouse database server): This is normally a relational database. Back-end tools extract data from operational databases and external sources, clean it (remove errors and inconsistencies), transform it into a common format, load it and periodically refresh it. A metadata repository stores the warehouse structure, source mappings, summarisation rules and refresh history. Small departmental subsets called data marts may also live here.
2. Middle tier (OLAP server): This tier presents the stored data as multidimensional cubes. It may be a ROLAP server, which maps cube operations onto relational tables, or a MOLAP server, which stores data in special multidimensional arrays.
3. Top tier (front-end client): Query and reporting tools, analysis tools and data mining tools that business users work with.
OLTP versus OLAP:
- Users: OLTP serves clerks and IT staff; OLAP serves managers and analysts.
- Function: OLTP runs day-to-day operations; OLAP supports decision making.
- Data: OLTP holds current, detailed data; OLAP holds historical, summarised and consolidated data.
- Database design: OLTP uses an entity-relationship, application-oriented design; OLAP uses star or snowflake, subject-oriented schemas.
- Access: OLTP does many short read/write transactions; OLAP mostly runs complex read-only queries.
- Records accessed: tens for OLTP; millions for OLAP.
- Size: megabytes to gigabytes for OLTP; gigabytes to terabytes and more for OLAP.
- Main metric: transaction throughput for OLTP; query response time for OLAP.
Design and usage: a warehouse may be built top-down (enterprise-wide plan first) or bottom-up (data marts first), often combined. It is used for information processing (queries, reports), analytical processing (OLAP operations) and data mining (finding hidden patterns).
In conclusion, the three-tier structure keeps heavy analytical work away from operational systems, and the clear OLTP/OLAP differences explain why a separate warehouse is needed.
2 What is data mining? Explain the steps of knowledge discovery, the kinds of patterns that can be mined, the technologies used and the major issues in data mining. 10 marks
Data mining is the process of discovering interesting, useful and previously unknown patterns from large amounts of data. It is the central step of the wider knowledge discovery in databases (KDD) process.
Steps of knowledge discovery:
1. Data cleaning: remove noise and inconsistent data. 2. Data integration: combine several data sources. 3. Data selection: retrieve the data relevant to the task. 4. Data transformation: summarise or aggregate data into forms suitable for mining. 5. Data mining: apply intelligent methods to extract patterns. 6. Pattern evaluation: identify the truly interesting patterns using interestingness measures. 7. Knowledge presentation: show the results with visualization and reports.
Kinds of patterns:
- Class/concept description: characterization (general features of a class) and discrimination (comparing classes).
- Frequent patterns and associations, for example items often bought together.
- Classification and regression: build models that predict a class label or a numeric value.
- Cluster analysis: group objects so that similar ones fall in the same cluster.
- Outlier analysis: find objects that do not fit the general behaviour, useful in fraud detection.
Technologies used: statistics, machine learning, database systems and data warehouses, information retrieval, pattern recognition, visualization, and high-performance or distributed computing.
Applications: business intelligence, web search engines, market basket analysis, fraud detection, bioinformatics and healthcare.
Major issues:
- Mining methodology: mining many kinds of knowledge in multidimensional space, handling noisy, uncertain or incomplete data, and evaluating patterns for interestingness.
- User interaction: interactive mining, incorporating background knowledge, data mining query languages, and presenting and visualizing results.
- Efficiency and scalability: algorithms must handle very large and growing data; parallel, distributed and incremental mining are needed.
- Diversity of data types: relational, text, multimedia, spatial, stream and network data each need suitable methods.
- Data mining and society: social impact, privacy-preserving mining and invisible mining.
In conclusion, data mining turns raw data into knowledge through a structured KDD process, draws on several disciplines, and must address issues of method, scale, data variety and privacy.
3 Explain star, snowflake and fact constellation schemas for multidimensional data with suitable examples. Describe the typical OLAP operations on a data cube. 10 marks
A data warehouse uses a multidimensional model in which data is viewed as a cube. Numeric measures (such as dollars sold) are stored in a fact table, and the descriptive perspectives (time, item, location) are stored in dimension tables. Three schemas are common.
1. Star schema: one central fact table connected directly to one table per dimension. Example: fact table Sales(time_key, item_key, branch_key, location_key, dollars_sold, units_sold) with dimension tables Time, Item, Branch and Location. Each dimension is a single, denormalised table.
2. Snowflake schema: a variant where some dimension tables are normalised into extra tables. For example, Item(item_key, item_name, brand, supplier_key) links to a separate Supplier table, and Location links to a City table. It saves space and reduces redundancy, but needs more joins, so queries can be slower.
3. Fact constellation (galaxy schema): several fact tables share dimension tables. Example: Sales and Shipping fact tables both use Time, Item and Location dimensions. It suits enterprise warehouses covering several related subjects.
Concept hierarchies organise dimension values into levels, for example street < city < state < country, or day < month < quarter < year. OLAP operations move along these hierarchies.
OLAP operations:
- Roll-up: aggregate to a higher level, by climbing a hierarchy (city to country) or by removing a dimension.
- Drill-down: the reverse, moving to more detail (quarter to month) or adding a dimension.
- Slice: select one value on one dimension to get a sub-cube, for example time = Q1.
- Dice: select ranges on two or more dimensions, for example location in (Delhi, Chennai) and time in (Q1, Q2) and item in (phone, laptop).
- Pivot (rotate): change the orientation of axes, for example swap item and location in a 2-D view.
- Others: drill-across (over several fact tables) and drill-through (down to the underlying relational data).
These operations are how analysts use a warehouse for analytical processing: a manager may roll up sales to yearly totals, notice a weak year, then drill down to months and slice by region to locate the cause.
In conclusion, the star schema is simple and fast, the snowflake schema saves space, the fact constellation handles multiple subjects, and OLAP operations let users explore the cube interactively.
4 Discuss data warehouse implementation: efficient data cube computation, indexing of OLAP data, OLAP query processing and types of OLAP servers. Add a note on cloud data warehouses. 10 marks
OLAP queries must answer quickly over huge data, so implementing a warehouse focuses on precomputing aggregates, indexing and choosing a suitable server architecture.
1. Data cube computation: a cube is a lattice of cuboids, one for each group-by. With n dimensions and no hierarchies there are 2^n cuboids. Example for dimensions (city, item, year): 2^3 = 8 cuboids, namely the apex () ; (city), (item), (year); (city, item), (city, year), (item, year); and the base cuboid (city, item, year). With hierarchies the total is the product of (Li + 1). The compute cube operator in SQL-like form computes group-by over all these subsets.
2. Materialization choices:
- No materialization: compute on the fly; slow.
- Full materialization: precompute every cuboid; fast but needs huge storage.
- Partial materialization: precompute a chosen subset, for example an iceberg cube that stores only cells whose count exceeds a minimum support threshold.
3. Indexing OLAP data:
- Bitmap index: for each value of an attribute, keep a bit vector with one bit per row. Example: a column 'region' with values North, South gives two bit vectors; a selection becomes a fast bitwise AND/OR. Good for low-cardinality attributes.
- Join index: stores pairs of row identifiers from the fact table and a dimension table that join, avoiding costly joins at query time. In a star schema, bitmapped join indices are widely used.
4. OLAP query processing: first, determine which operations (roll-up, slice, dice) are needed on which cuboids; second, choose the materialized cuboid that can answer the query at the lowest cost, i.e. the smallest cuboid that is at least as detailed as the query requires.
5. OLAP server types:
- ROLAP: stores data in relational tables, scales well to large data.
- MOLAP: stores data in multidimensional arrays, giving fast indexing to summarised data, but sparse data wastes space.
- HOLAP: hybrid; detailed data in relational form, aggregates in arrays.
6. Cloud data warehouse: a managed service in the cloud that separates storage from compute, uses columnar storage and massively parallel processing, scales elastically and charges per use. It removes hardware management but raises concerns about data transfer cost, security and vendor dependence.
In conclusion, good implementation balances precomputation, storage and indexing, and today often runs on elastic cloud platforms.
5 The marks of 12 students are: 4, 8, 10, 12, 15, 18, 20, 22, 25, 28, 30, 70. Compute the mean, median, mode, midrange, quartiles, IQR and five-number summary. Identify outliers and describe the boxplot and other graphic displays of such data. 10 marks
Basic statistical descriptions summarise the central tendency and spread of data, and graphic displays help us see its shape and outliers quickly. The data is already sorted (n = 12).
1. Mean: sum = 4+8+10+12+15+18+20+22+25+28+30+70 = 262. Mean = 262/12 = 21.83.
2. Median: n is even, so median = average of 6th and 7th values = (18 + 20)/2 = 19.
3. Mode: every value appears once, so the data has no mode.
4. Midrange: (min + max)/2 = (4 + 70)/2 = 37.
5. Quartiles (using the medians of the two halves):
- Lower half 4, 8, 10, 12, 15, 18 gives Q1 = (10 + 12)/2 = 11.
- Upper half 20, 22, 25, 28, 30, 70 gives Q3 = (25 + 28)/2 = 26.5.
6. IQR = Q3 − Q1 = 26.5 − 11 = 15.5.
7. Outlier test: 1.5 × IQR = 23.25. Lower fence = 11 − 23.25 = −12.25. Upper fence = 26.5 + 23.25 = 49.75. The value 70 > 49.75, so 70 is an outlier; no low outliers.
8. Five-number summary: Minimum = 4, Q1 = 11, Median = 19, Q3 = 26.5, Maximum = 70.
The mean (21.83) is greater than the median (19) and the midrange is far higher, which shows the data is positively skewed, pulled up by the outlier 70. The median is the more robust measure of centre here.
Dispersion: variance σ² = (1/n) Σ (xi − mean)² and standard deviation σ = √σ²; a large σ indicates widely spread values.
Boxplot description: a horizontal axis from 0 to 75. A box is drawn from 11 to 26.5 with a vertical line inside at 19. The left whisker extends to 4. The right whisker extends only to 30, the largest value within the upper fence. The point 70 is plotted separately as an individual dot marking the outlier.
Other graphic displays:
- Histogram: bars over equal-width ranges show the frequency distribution.
- Quantile plot: each value plotted against its f-value, (i − 0.5)/n, showing the overall distribution.
- Quantile-quantile plot: quantiles of one distribution against another to compare them.
- Scatter plot: pairs of numeric attributes plotted to reveal correlation, clusters and outliers.
In conclusion: mean 21.83, median 19, no mode, midrange 37, Q1 11, Q3 26.5, IQR 15.5, and 70 is an outlier; the boxplot makes the skew and outlier visible at a glance.
6 Explain proximity measures for different attribute types. For x = (2, 5, 1, 4) and y = (6, 2, 3, 4), compute the Manhattan, Euclidean, Minkowski (h = 3) and supremum distances and the cosine similarity. 10 marks
Similarity and dissimilarity (proximity) measures tell how alike two data objects are. They are central to clustering, classification and outlier detection. The right measure depends on the attribute type.
1. Nominal attributes: d(i, j) = (p − m)/p, where p is the number of attributes and m is the number of matches.
2. Binary attributes: let q = number of attributes that are 1 in both objects, r = 1 in i and 0 in j, s = 0 in i and 1 in j, t = 0 in both. For symmetric binary attributes, d = (r + s)/(q + r + s + t). For asymmetric binary attributes the negative matches t are ignored, so d = (r + s)/(q + r + s), and Jaccard similarity = q/(q + r + s).
3. Ordinal attributes: replace each value by its rank r in 1..M, map it to z = (r − 1)/(M − 1) in [0, 1], then treat it as numeric.
4. Numeric attributes: use the Minkowski family, d = (Σ |xi − yi|^h)^(1/h) with h ≥ 1. h = 1 gives Manhattan, h = 2 gives Euclidean, h → ∞ gives supremum (maximum difference). Attributes are usually normalised first.
5. Mixed attributes: compute a weighted average of per-attribute dissimilarities, each scaled to [0, 1].
6. Document-like vectors: cosine similarity, cos(x, y) = (x · y)/(||x|| ||y||).
Calculation for x = (2, 5, 1, 4), y = (6, 2, 3, 4):
Absolute differences: |2−6| = 4, |5−2| = 3, |1−3| = 2, |4−4| = 0.
- Manhattan (h = 1): 4 + 3 + 2 + 0 = 9.
- Euclidean (h = 2): √(16 + 9 + 4 + 0) = √29 ≈ 5.385.
- Minkowski (h = 3): (64 + 27 + 8 + 0)^(1/3) = 99^(1/3) ≈ 4.626.
- Supremum (h → ∞): max(4, 3, 2, 0) = 4.
The distance decreases as h increases (9 > 5.385 > 4.626 > 4), as expected.
Cosine similarity:
- Dot product x · y = 2×6 + 5×2 + 1×3 + 4×4 = 12 + 10 + 3 + 16 = 41.
- ||x|| = √(4 + 25 + 1 + 16) = √46 ≈ 6.782.
- ||y|| = √(36 + 4 + 9 + 16) = √65 ≈ 8.062.
- ||x|| × ||y|| = √2990 ≈ 54.68.
- cos(x, y) = 41/54.68 ≈ 0.75.
A cosine of 0.75 means the vectors point in fairly similar directions (angle about 41°), even though their Euclidean distance is noticeably large.
Metric properties: a distance is a metric if it satisfies non-negativity, d(i, i) = 0, symmetry and the triangle inequality d(i, j) ≤ d(i, k) + d(k, j). The Minkowski distance is a metric only when h ≥ 1, so the Manhattan, Euclidean, h = 3 and supremum distances above all qualify. For 0 < h < 1 the triangle inequality can fail. For example, with h = 0.5: d((0,0),(1,1)) = (1 + 1)^2 = 4, but d((0,0),(1,0)) + d((1,0),(1,1)) = 1 + 1 = 2, and 4 > 2.
In conclusion: Manhattan = 9, Euclidean ≈ 5.385, Minkowski (h = 3) ≈ 4.626, supremum = 4 and cosine similarity ≈ 0.75. Choosing the measure to match the attribute type is essential for meaningful mining results.
Data Preprocessing
Syllabus: Overview of data preprocessing; Data cleaning; Data integration; Data reduction; Data transformation and data discretization
One-page revision summary
- Real-world data can be incomplete, noisy and inconsistent, so it must be preprocessed before mining.
- Data quality is judged by accuracy, completeness, consistency, timeliness, believability and interpretability.
- The four major preprocessing tasks are data cleaning, data integration, data reduction, and data transformation with discretization.
- Missing values can be handled by ignoring the tuple, manual filling, a global constant, the mean or median, the class-wise mean, or a value inferred by a model such as regression or a decision tree.
- Noise is smoothed by binning, regression or clustering-based outlier analysis.
- Data cleaning is an iterative two-step process: discrepancy detection, aided by metadata, rules, data scrubbing and data auditing tools, followed by data transformation using data migration and ETL tools.
- Data integration must handle entity identification, redundancy, tuple duplication and data value conflicts such as differing units or scales.
- Redundancy is detected with the chi-square test for nominal attributes, and with the correlation coefficient or covariance for numeric attributes.
- Dimensionality reduction uses wavelet transforms, PCA and attribute subset selection (forward selection, backward elimination, decision tree induction).
- Numerosity reduction uses parametric models (regression, log-linear) or non-parametric forms (histograms, clustering, sampling, data cube aggregation).
- Data compression is lossless if the original data can be rebuilt exactly, and lossy if only an approximation can be recovered.
- Transformation strategies include smoothing, attribute construction, aggregation, normalization, discretization and concept hierarchy generation.
- Discretization methods include binning, histogram analysis, clustering, entropy-based decision-tree splitting and ChiMerge.
- For nominal data, concept hierarchies can be generated automatically: the attribute with the most distinct values is placed at the lowest level.
Learn these by heart
- Min-max: v' = ((v − min)/(max − min)) × (new_max − new_min) + new_min
- Z-score: v' = (v − mean)/σ
- Decimal scaling: v' = v/10^j, where j is the smallest integer with max(|v'|) < 1
- Chi-square: χ² = Σ (o − e)²/e, with e = (row total × column total)/N and df = (r − 1)(c − 1)
- Correlation coefficient: r = Σ(a_i − Ā)(b_i − B̄)/(n σA σB); r > 0 positive, r < 0 negative, r = 0 no linear correlation
- Covariance: Cov(A,B) = E(A·B) − Ā·B̄
- Smoothing by bin boundaries: each value is replaced by the nearer of its bin's minimum or maximum
2-mark questions
1 What is data preprocessing and why is it needed before data mining? 2 marks
Data preprocessing is the set of operations applied to raw data before mining to make it accurate, complete, consistent and suitable for analysis. Real-world data is often incomplete, noisy and inconsistent. Mining results depend on the quality of the input data, so preprocessing improves both the accuracy and the efficiency of mining.
2 Define noisy data. Name the techniques used to smooth it. 2 marks
Noise is random error or variance in a measured variable. Examples are wrongly recorded values caused by faulty sensors or data-entry mistakes. Noise can be smoothed in three ways:
- Binning: replace values by bin means, medians or boundaries.
- Regression: fit the values to a function.
- Outlier analysis: use clustering to detect and treat unusual values.
3 What is the entity identification problem in data integration? 2 marks
When data from several sources is combined, the same real-world attribute or object may be represented differently. For example, cust_id in one database may be customer_no in another. Entity identification is the problem of deciding which attributes and records actually match. It is solved using metadata such as attribute name, meaning, data type, value range and null rules.
4 Differentiate between parametric and non-parametric numerosity reduction. 2 marks
Numerosity reduction replaces the original data with a smaller representation.
- Parametric methods assume a model, such as regression or a log-linear model, and store only the model parameters, discarding the actual data.
- Non-parametric methods store a reduced form of the data itself, such as histograms, cluster representatives, samples or data cube aggregates.
5 Using min-max normalization, map the value 70 of an attribute whose minimum is 20 and maximum is 120 to the range [0, 1]. 2 marks
Formula: v' = ((v − min)/(max − min)) × (new_max − new_min) + new_min.
Substituting: v' = ((70 − 20)/(120 − 20)) × (1 − 0) + 0 = 50/100 = 0.5.
The normalized value is 0.5.
6 What is data discretization? Give an example of a concept hierarchy. 2 marks
Discretization divides the range of a continuous attribute into intervals and replaces raw values with interval labels or higher-level concepts. This reduces data size and makes results easier to interpret.
Example: age values can be mapped to youth (0–25), middle-aged (26–55) and senior (56 and above). Location forms the hierarchy street < city < state < country.
10-mark questions
1 Explain the need for data preprocessing. Discuss the factors that determine data quality and describe the major tasks of data preprocessing with a neat diagram. 10 marks
Introduction: Data collected from operational systems, sensors, web logs and surveys is rarely ready for mining. It contains gaps, errors and contradictions, and it is often far too large. Poor-quality input produces poor-quality patterns, so preprocessing is an essential first stage of the knowledge discovery process.
There are three main reasons why real data is dirty:
- Incomplete: attribute values are missing, for example a customer did not fill in income.
- Noisy: values contain errors or outliers, for example age = 250.
- Inconsistent: codes or names conflict, for example rating stored as 1,2,3 in one table and A,B,C in another.
Factors of data quality:
1. Accuracy: values correctly reflect the real world. 2. Completeness: all required values and records are present. 3. Consistency: the same fact is recorded the same way everywhere. 4. Timeliness: data is updated soon enough to be useful. 5. Believability: users trust the data. 6. Interpretability: users can easily understand the data.
Major tasks of data preprocessing:
1. Data cleaning: fill in missing values, smooth noisy data, identify or remove outliers and resolve inconsistencies. 2. Data integration: merge data from multiple databases, files or cubes. This involves resolving schema conflicts, entity identification, redundancy and value conflicts. 3. Data reduction: obtain a smaller representation that gives nearly the same analytical results. Methods include dimensionality reduction (PCA, wavelets, attribute subset selection), numerosity reduction (regression, histograms, clustering, sampling) and compression. 4. Data transformation and discretization: convert data into forms suited to mining. Examples are normalization (min-max, z-score, decimal scaling), aggregation, attribute construction, discretization and concept hierarchy generation.
These tasks are not strictly sequential. Cleaning may be repeated after integration, and reduction may follow transformation.
Conclusion: Preprocessing improves data quality on all six dimensions. It reduces mining time and directly raises the accuracy and usefulness of the discovered knowledge. In many projects it takes the major share of the total effort.
2 What is data cleaning? Explain the methods for handling missing values and noisy data, and describe data cleaning as a process. 10 marks
Introduction: Data cleaning (or cleansing) detects and corrects errors in data. It fills missing values, smooths noise, identifies outliers and removes inconsistencies, so that mining algorithms work on reliable input.
A. Handling missing values:
1. Ignore the tuple. This is usually done when the class label is missing. It wastes data when many attributes are missing. 2. Fill in the value manually. This is accurate but time-consuming and impractical for large data. 3. Use a global constant such as "Unknown". This is simple, but the miner may treat "Unknown" as a meaningful concept. 4. Use a measure of central tendency: the attribute mean for symmetric data, or the median for skewed data. 5. Use the mean or median of all samples of the same class. This is more accurate in classification tasks. 6. Use a value inferred by a model such as regression, Bayesian inference or decision-tree induction. This is a strong approach because it uses information from the other attributes.
A missing value is not always an error. For example, "driving licence number" is legitimately blank for a person without a licence.
B. Handling noisy data:
1. Binning: sort the values and partition them into bins of equal frequency or equal width. Then smooth by bin means, bin medians or bin boundaries, so each value is adjusted using its neighbourhood. 2. Regression: fit the data to a function, such as a straight line y = wx + b. Replace values by fitted values, or use one attribute to estimate another. 3. Outlier analysis: use clustering to group similar values. Values falling outside all clusters are treated as outliers. 4. Combined computer and human inspection: suspicious values flagged by programs are verified manually.
C. Data cleaning as a process:
1. Discrepancy detection: find problems using metadata (data type, domain, acceptable range), basic statistics such as mean, median and standard deviation, and data rules. Three kinds of rules are useful:
- Unique rules: each value of an attribute must be distinct.
- Consecutive rules: no missing values between the lowest and highest, for example cheque numbers.
- Null rules: specify how blanks, question marks or special characters are to be read.
2. Tools help with detection:
- Data scrubbing tools use domain knowledge such as postal codes and spell-checking.
- Data auditing tools discover rules and find violators.
3. Data transformation: correct the discrepancies using data migration tools and ETL tools. 4. Iteration: correcting one error may expose others. Interactive tools such as Potter's Wheel integrate detection and transformation so that users can repeat the cycle quickly.
Conclusion: Data cleaning is an iterative, partly automated process. Missing values are filled sensibly, noise is smoothed by binning, regression or clustering, and discrepancies are detected and corrected repeatedly until the data is trustworthy.
3 Explain the issues in data integration. A survey of 200 people records gender and preferred shopping mode: Male–Online 60, Male–Offline 40, Female–Online 30, Female–Offline 70. Use the chi-square test to check whether gender and shopping mode are correlated (critical value for 1 degree of freedom at 0.001 significance is 10.828). 10 marks
Introduction: Data integration merges data from multiple sources into a coherent store such as a data warehouse. Careful integration reduces redundancy and inconsistency, which improves later mining.
Issues in data integration:
1. Entity identification problem: matching equivalent attributes and objects across sources, for example emp_id versus employee_number. Metadata (name, meaning, type, range, null rules) is used to match them. 2. Redundancy: an attribute is redundant if it can be derived from others, for example annual salary from monthly salary. Correlation analysis detects redundancy:
- Chi-square test for nominal data.
- Correlation coefficient r = Σ(a_i − Ā)(b_i − B̄)/(n σA σB) for numeric data. Here r > 0 means positive correlation, r < 0 negative, and r = 0 no linear correlation.
- Covariance Cov(A,B) = E(A·B) − Ā·B̄, also for numeric data.
3. Tuple duplication: the same record appears twice, often because of denormalised tables or inconsistent updates. 4. Data value conflicts: the same fact has different representations, such as weight in kg versus pounds, price in rupees versus dollars, or different grading scales.
Chi-square calculation:
Step 1: Contingency table with totals.
- Male: Online 60, Offline 40, total 100.
- Female: Online 30, Offline 70, total 100.
- Column totals: Online 90, Offline 110. N = 200.
Step 2: Expected frequencies, e = (row total × column total)/N.
- Male–Online = 100 × 90/200 = 45.
- Male–Offline = 100 × 110/200 = 55.
- Female–Online = 45.
- Female–Offline = 55.
Step 3: χ² = Σ (o − e)²/e.
- Male–Online: (60 − 45)²/45 = 225/45 = 5.0000.
- Male–Offline: (40 − 55)²/55 = 225/55 = 4.0909.
- Female–Online: (30 − 45)²/45 = 5.0000.
- Female–Offline: (70 − 55)²/55 = 4.0909.
- χ² = 5 + 4.0909 + 5 + 4.0909 = 18.18 (approx.).
Step 4: Degrees of freedom = (rows − 1)(columns − 1) = (2 − 1)(2 − 1) = 1.
Step 5: Decision. Since 18.18 > 10.828, the hypothesis that gender and shopping mode are independent is rejected.
Result: Gender and preferred shopping mode are strongly correlated in this group. Men favour online shopping and women favour offline shopping.
Conclusion: Integration must resolve entity matching, redundancy, duplication and value conflicts. Statistical tools such as the chi-square test and the correlation coefficient help decide whether two attributes carry overlapping information.
4 What is data reduction? Explain dimensionality reduction, numerosity reduction and data compression techniques in detail. 10 marks
Introduction: Mining a huge data set takes a long time. Data reduction produces a much smaller representation that keeps the integrity of the original data, so mining on it gives almost the same results more efficiently. The time spent on reduction must not exceed the time saved.
A. Dimensionality reduction (fewer attributes):
1. Wavelet transforms: the discrete wavelet transform converts a data vector into wavelet coefficients. Only the strongest coefficients are kept and the rest are set to zero, giving a sparse approximation. It works well for noisy, skewed and multidimensional data. 2. Principal Component Analysis (PCA):
- Normalize the attributes.
- Compute k orthonormal vectors (principal components).
- Sort them by decreasing variance.
- Keep only the strongest components.
The data is projected onto a smaller set of new axes. 3. Attribute subset selection removes irrelevant or redundant attributes using greedy heuristics:
- Stepwise forward selection: start empty and add the best attribute each step.
- Stepwise backward elimination: start with all attributes and remove the worst each step.
- Combined forward and backward.
- Decision tree induction: attributes not appearing in the tree are dropped.
B. Numerosity reduction (fewer values or tuples):
1. Parametric methods:
- Linear regression y = wx + b.
- Multiple regression.
- Log-linear models, which approximate discrete multidimensional distributions.
Only the parameters are stored. 2. Histograms: partition the values into buckets and store bucket ranges with counts. Buckets may be equal-width or equal-frequency. 3. Clustering: replace the data by cluster representatives (centroid, diameter). 4. Sampling: take a sample of n tuples from N.
- SRSWOR: simple random sample without replacement.
- SRSWR: simple random sample with replacement.
- Cluster sample.
- Stratified sample, which keeps the proportions of strata and suits skewed data.
The cost of sampling is proportional to n, not N. 5. Data cube aggregation: store summarised values. For example, keep yearly totals instead of quarterly sales, at the lowest level that still answers the queries.
C. Data compression:
- Lossless: the original data can be reconstructed exactly, for example string compression.
- Lossy: only an approximation can be recovered, as with wavelets and PCA.
Conclusion: Dimensionality reduction cuts the number of attributes, numerosity reduction cuts the volume of values, and compression encodes the data compactly. Together they make large-scale mining feasible with little loss of quality.
5 Explain data transformation strategies. For an attribute marks with minimum 20, maximum 100, mean 60 and standard deviation 16, normalize the value 84 using (a) min-max normalization to [0,1] and to [−1,1], (b) z-score normalization, and (c) decimal scaling. 10 marks
Introduction: Data transformation converts or consolidates data into forms suited for mining. Normalization matters for distance-based methods such as k-nearest neighbour and clustering, and for neural networks. Without it, attributes with large ranges dominate those with small ranges.
Transformation strategies:
1. Smoothing: remove noise by binning, regression or clustering. 2. Attribute construction: build new attributes from existing ones, for example area = length × width. 3. Aggregation: summarise data, for example daily sales into monthly totals. 4. Normalization: scale values into a small range such as [0,1] or [−1,1]. 5. Discretization: replace numeric values by intervals or conceptual labels. 6. Concept hierarchy generation for nominal data: for example street → city → state → country.
Normalization methods with the given data (min = 20, max = 100, mean = 60, σ = 16, v = 84):
(a) Min-max normalization: v' = ((v − min)/(max − min)) × (new_max − new_min) + new_min.
To [0,1]:
- v' = ((84 − 20)/(100 − 20)) × (1 − 0) + 0
- = 64/80
- = 0.8
To [−1,1]:
- v' = (64/80) × (1 − (−1)) + (−1)
- = 0.8 × 2 − 1
- = 1.6 − 1
- = 0.6
Min-max keeps the relationships among the original values. However, a future value outside [min, max] gives an "out of bounds" error.
(b) Z-score normalization: v' = (v − mean)/σ.
- v' = (84 − 60)/16
- = 24/16
- = 1.5
The value lies 1.5 standard deviations above the mean. This method is useful when the actual min and max are unknown or when outliers exist. A variant uses the mean absolute deviation instead of σ, which is more robust to outliers.
(c) Decimal scaling: v' = v/10^j, where j is the smallest integer such that max(|v'|) < 1.
- The maximum absolute value is 100.
- With j = 2: 100/100 = 1, which is not less than 1.
- With j = 3: 100/1000 = 0.1 < 1, so j = 3.
- v' = 84/1000 = 0.084
Summary of results:
- Min-max [0,1]: 0.8
- Min-max [−1,1]: 0.6
- Z-score: 1.5
- Decimal scaling: 0.084
Conclusion: Each normalization method suits a different situation. Min-max needs known bounds, z-score relies on the mean and spread, and decimal scaling simply moves the decimal point. The parameters (min, max, mean, σ, j) must be stored so that future data is normalized the same way.
6 The sorted values of an attribute are: 4, 9, 11, 15, 18, 24, 25, 32, 36. Partition them into equal-frequency bins of size 3 and smooth by bin means, bin medians and bin boundaries. Then explain the main data discretization techniques. 10 marks
Introduction: Binning is a local smoothing technique. It sorts the values and replaces each value using its neighbours in the same bin. The same idea is also a simple, unsupervised way to discretize a numeric attribute.
Step 1: Equal-frequency (equi-depth) partitioning, 9 values into 3 bins of 3.
- Bin 1: 4, 9, 11
- Bin 2: 15, 18, 24
- Bin 3: 25, 32, 36
Step 2: Smoothing by bin means.
- Bin 1 mean = (4 + 9 + 11)/3 = 24/3 = 8, giving 8, 8, 8.
- Bin 2 mean = (15 + 18 + 24)/3 = 57/3 = 19, giving 19, 19, 19.
- Bin 3 mean = (25 + 32 + 36)/3 = 93/3 = 31, giving 31, 31, 31.
Step 3: Smoothing by bin medians.
- Bin 1: 9, 9, 9
- Bin 2: 18, 18, 18
- Bin 3: 32, 32, 32
Step 4: Smoothing by bin boundaries. The minimum and maximum of each bin are the boundaries, and every other value moves to the closer boundary.
- Bin 1 (boundaries 4, 11): 9 is 5 from 4 and 2 from 11, so it becomes 11. Result: 4, 11, 11.
- Bin 2 (boundaries 15, 24): 18 is 3 from 15 and 6 from 24, so it becomes 15. Result: 15, 15, 24.
- Bin 3 (boundaries 25, 36): 32 is 7 from 25 and 4 from 36, so it becomes 36. Result: 25, 36, 36.
For comparison, equal-width binning would use width (36 − 4)/3 ≈ 10.67, giving intervals [4, 14.67), [14.67, 25.33) and [25.33, 36].
Data discretization techniques:
1. Binning: top-down splitting into equal-width or equal-frequency bins, with values replaced by the bin mean or median. It is unsupervised. 2. Histogram analysis: partition the values into buckets (equal-width or equal-frequency), applied recursively to build multilevel concept hierarchies. 3. Cluster analysis: group close values into clusters, each forming one interval. This follows the natural distribution of the data. 4. Decision-tree analysis: a supervised, top-down method. Split points are chosen to minimise entropy (maximise information gain) with respect to the class label. 5. Correlation analysis (ChiMerge): a supervised, bottom-up method. Adjacent intervals with the lowest χ² values, meaning similar class distributions, are merged repeatedly until a stopping criterion is met. 6. Concept hierarchy generation for nominal data: specify an ordering of attributes, for example street < city < state < country. A hierarchy can also be generated automatically, since the attribute with the most distinct values goes to the lowest level.
Conclusion: Binning smooths noise and doubles as discretization. Supervised methods such as entropy-based splitting and ChiMerge use class information to choose better interval boundaries, which helps classification.
Classification
Syllabus: Classification: basic concepts; General approach to solving a classification problem; Decision tree induction; Attribute selection measures; Tree pruning; Scalability of decision tree induction; Visual mining for decision tree induction; Bayesian classification: Bayes theorem; Naive Bayes classification; Rule-based classification; Model evaluation and selection
One-page revision summary
- Classification learns a model from labelled training tuples (supervised learning) and predicts discrete class labels; numeric prediction predicts continuous values.
- The general approach has two steps: a learning step that builds the classifier, and a classification step that first measures accuracy on an independent test set and then labels new data.
- A decision tree has attribute tests at internal nodes, test outcomes on branches and class labels at leaves; it is grown greedily top-down by recursive partitioning, which stops when a node is pure, when no attributes remain (majority voting), or when a partition is empty (leaf labelled with the parent's majority class).
- Information gain (ID3) is biased towards many-valued attributes, gain ratio (C4.5) normalises gain by SplitInfo, and the Gini index (CART) evaluates binary splits by impurity reduction.
- Pre-pruning stops splitting using a threshold, while post-pruning removes subtrees from a full tree using cost-complexity pruning (with a pruning set) or pessimistic pruning (training error plus a penalty).
- Scalable tree algorithms handle disk-resident data: SLIQ and SPRINT use attribute lists, RainForest uses AVC-sets per node, and BOAT builds a tree from bootstrap samples and refines it in about two scans.
- Perception-based classification draws each attribute as a circle segment of class-coloured pixels so the user can choose split points interactively, giving smaller and more understandable trees.
- Bayes' theorem gives the posterior P(H|X) from the prior P(H), the likelihood P(X|H) and the evidence P(X); naive Bayes assumes class-conditional independence, uses the Laplacian correction to avoid zero probabilities, and models continuous attributes with a Gaussian distribution.
- A rule-based classifier uses IF-THEN rules whose IF part (antecedent or precondition) is a conjunction of attribute tests and whose THEN part (consequent) is the class prediction; a rule covers a tuple when its antecedent holds, and each rule is judged by its coverage and accuracy.
- When more than one rule fires for a tuple, a conflict resolution strategy is needed, and size ordering gives priority to the triggering rule with the toughest requirement, meaning the most attribute tests in its antecedent.
- Rule ordering fixes priorities in advance, either class-based (classes ranked by decreasing importance such as prevalence or misclassification cost, with rules inside a class unordered) or rule-based (all rules ranked by a quality measure into a decision list, where the first rule that fires assigns the class).
- A default rule with an empty antecedent is evaluated last and labels any tuple that no other rule covers, usually with the overall majority class or the majority class of the training tuples left uncovered by the rules.
- Rule extraction from a decision tree creates one rule per root-to-leaf path, joining the tests along the path with AND to form the antecedent and taking the leaf's class as the consequent, so the extracted rules are mutually exclusive and exhaustive.
- Extracted rules can be simplified by removing any conjunct that does not reduce the rule's estimated accuracy, but the pruned rules may then overlap or leave tuples uncovered, so a class-based ordering and a default rule are added.
- Sequential covering algorithms such as AQ, CN2 and RIPPER learn rules directly from the data, one rule and usually one class at a time, removing the tuples each new rule covers and repeating until no tuples of the class remain or rule quality falls below a threshold.
- Learn_One_Rule grows each rule greedily from general to specific, starting with an empty antecedent and adding the attribute test that gives the largest FOIL_Gain, which rewards rules that are more accurate while still covering many positive tuples.
- Each grown rule is pruned on an independent pruning set using FOIL_Prune, removing a conjunct when the shorter rule scores higher, and this one-rule-at-a-time learning differs from a decision tree, which effectively learns all its rules simultaneously.
- The confusion matrix gives accuracy, error rate, precision, recall (sensitivity), specificity and F-measure, and recall and specificity are preferred over accuracy for imbalanced classes.
- Accuracy can be estimated by holdout, random subsampling, stratified k-fold cross-validation, leave-one-out or the .632 bootstrap.
- Models are compared with a paired t-test over the same folds, with ROC curves (higher area under the curve is better, 0.5 means random guessing), or with cost-benefit analysis.
Learn these by heart
- Info(D) = −Σ pi log2 pi; Info_A(D) = Σ (|Dj|/|D|) Info(Dj); Gain(A) = Info(D) − Info_A(D)
- SplitInfo_A(D) = −Σ (|Dj|/|D|) log2(|Dj|/|D|); GainRatio(A) = Gain(A) / SplitInfo_A(D)
- Gini(D) = 1 − Σ pi²; ΔGini(A) = Gini(D) − Gini_A(D), and the split with the largest reduction is chosen
- Bayes: P(H|X) = P(X|H) P(H) / P(X); naive Bayes picks the class Ci that maximises P(Ci) × Π P(xk|Ci)
- Rule coverage = n_covers / |D|; rule accuracy = n_correct / n_covers
- Accuracy = (TP + TN)/(P + N); Precision = TP/(TP + FP); Recall = TP/P; Specificity = TN/N; F = 2 × Precision × Recall/(Precision + Recall)
- .632 bootstrap: Acc(M) = (1/k) Σ (0.632 × Acc_test + 0.368 × Acc_train), because (1 − 1/d)^d ≈ e^−1 = 0.368
- FOIL_Gain = pos' × (log2(pos'/(pos' + neg')) − log2(pos/(pos + neg))), where pos and neg are the positive and negative tuples covered by rule R, and pos', neg' those covered by the extended rule R'
- FOIL_Prune(R) = (pos − neg)/(pos + neg), computed on the pruning set; drop a conjunct if the pruned rule's FOIL_Prune value is higher
- Conflict resolution: size ordering picks the fired rule with the most tests; rule ordering uses class-based priority or a decision list; the default rule applies only when no rule fires
2-mark questions
1 Define classification and state how it differs from numeric prediction. 2 marks
Classification is a supervised data analysis task. It learns a model, called a classifier, from training tuples whose class labels are known. The model then assigns discrete, unordered class labels (for example safe or risky) to new tuples. Numeric prediction instead forecasts a continuous value, such as a loan amount, usually by regression.
2 A node of a decision tree contains 8 training tuples: 6 of class Yes and 2 of class No. Compute its entropy Info(D). 2 marks
Info(D) = −(6/8)log2(6/8) − (2/8)log2(2/8) = −0.75 × (−0.415) − 0.25 × (−2) = 0.311 + 0.5 = 0.811 bits.
The node is impure, but less impure than a 50/50 node, whose entropy would be 1 bit.
3 Distinguish between pre-pruning and post-pruning of a decision tree. 2 marks
Pre-pruning stops tree growth early. A node is not split further when a measure such as information gain or Gini reduction falls below a threshold, and it becomes a leaf labelled with the majority class.
Post-pruning first grows the full tree. It then removes subtrees and replaces them by leaves, for example by cost-complexity or pessimistic pruning.
4 State Bayes' theorem as used in classification and name each term. 2 marks
Let X be a data tuple and H the hypothesis that X belongs to class C. Then P(H|X) = P(X|H) P(H) / P(X).
- P(H|X) is the posterior probability.
- P(H) is the prior probability.
- P(X|H) is the likelihood of X given H.
- P(X) is the evidence, which is the same for every class.
5 A rule R: IF income = high AND credit = good THEN loan = approve covers 40 tuples of a 200-tuple data set and correctly classifies 30 of them. Find the coverage and accuracy of R. 2 marks
coverage(R) = n_covers / |D| = 40/200 = 0.20, i.e. 20%.
accuracy(R) = n_correct / n_covers = 30/40 = 0.75, i.e. 75%.
So R fires for one-fifth of the data and is correct three times out of four when it fires.
6 What is an AVC-set in the RainForest framework? 2 marks
For a node and an attribute A, the AVC-set (Attribute-Value, Class label) stores, for each distinct value of A, the number of training tuples in each class. It summarises the data, so attribute selection can be done in memory without holding all the tuples. The AVC-group is the set of AVC-sets of all attributes at that node.
10-mark questions
1 Explain the basic concepts of classification and the general two-step approach to solving a classification problem. Support your answer with a diagram described in words. 10 marks
Classification is a form of data analysis that extracts a model describing important data classes. The model, called a classifier, predicts categorical (discrete, unordered) class labels. For example, a bank may label loan applications as safe or risky, and a hospital may label patients as needing treatment A, B or C. When the value to be predicted is continuous, the task is called numeric prediction (regression) instead.
Basic concepts:
- A data tuple X = (x1, x2, ..., xn) is described by n attributes A1, ..., An.
- One extra attribute, the class label attribute, gives the class of each tuple.
- The tuples used to build the model form the training set. They are drawn randomly from the database.
- The class of every training tuple is supplied, so classification is supervised learning. Clustering, by contrast, is unsupervised because the labels are not known.
- The learned model can be viewed as a mapping y = f(X). It may be represented as a decision tree, IF-THEN rules, probability tables or mathematical formulae.
General two-step approach: 1. Learning step (training phase): a classification algorithm analyses the training tuples and their labels and builds the classifier. On loan data it might learn a rule such as IF income = high AND credit_rating = good THEN decision = safe. 2. Classification step: the model is used to predict labels. Before deployment, its accuracy is estimated on a separate test set whose tuples were not used in training. Accuracy is the percentage of test tuples whose predicted label matches the known label. Training tuples are not used for this estimate, because the model tends to overfit them and would give an optimistic figure. 3. If the accuracy is acceptable, the classifier is applied to new tuples whose class label is unknown.
Data preparation before classification:
- Data cleaning to reduce noise and handle missing values.
- Relevance analysis to remove irrelevant or redundant attributes.
- Transformation, such as normalisation or generalisation to higher-level concepts.
Criteria for comparing classifiers:
- Accuracy.
- Speed of training and prediction.
- Robustness to noise and missing values.
- Scalability to large data.
- Interpretability of the model.
In conclusion, classification is a learn-then-predict process. A model is built from labelled data, validated on independent test data, and then used to label unseen data.
2 Discuss the methods used for model evaluation and selection. A classifier tested on 200 tuples gives TP = 80, FN = 20, FP = 10 and TN = 90. Compute its accuracy, error rate, precision, recall, specificity and F-measure. 10 marks
After a classifier is built, we must estimate how well it will perform on unseen data and choose the best of several competing models. This requires evaluation metrics and reliable estimation methods.
1. Confusion matrix and metrics. For positive class P and negative class N, the counts are TP, TN, FP and FN.
- Accuracy = (TP + TN)/(P + N)
- Error rate = (FP + FN)/(P + N)
- Recall (sensitivity) = TP/P
- Specificity = TN/N
- Precision = TP/(TP + FP)
- F-measure = 2 × precision × recall/(precision + recall)
2. Worked example. P = TP + FN = 80 + 20 = 100, N = FP + TN = 10 + 90 = 100, total = 200.
- Accuracy = (80 + 90)/200 = 170/200 = 0.85
- Error rate = (10 + 20)/200 = 30/200 = 0.15
- Precision = 80/(80 + 10) = 80/90 = 0.889
- Recall = 80/100 = 0.80
- Specificity = 90/100 = 0.90
- F-measure = 2 × 0.889 × 0.80/(0.889 + 0.80) = 1.422/1.689 = 0.842
Result: accuracy 85%, error rate 15%, precision 0.889, recall 0.80, specificity 0.90, F = 0.842.
3. Estimation methods.
- Holdout: the data is split randomly, typically two-thirds for training and one-third for testing. Random subsampling repeats the holdout k times and averages the accuracies.
- k-fold cross-validation: the data is divided into k nearly equal folds. In iteration i, fold i is the test set and the other folds train the model. Accuracy = total correct predictions over all iterations / total tuples. Stratified 10-fold cross-validation, which keeps class proportions in every fold, is a common choice. Leave-one-out is the special case where k equals the number of tuples.
- Bootstrap: d tuples are sampled with replacement to form the training set, and the tuples never chosen form the test set. A tuple is missed with probability (1 − 1/d)^d ≈ e^−1 = 0.368, so about 63.2% of distinct tuples are used for training. The .632 bootstrap estimate is Acc(M) = (1/k) Σ (0.632 × Acc_test + 0.368 × Acc_train).
4. Model selection.
- Paired t-test: both models are run on the same k folds and their error rates are compared. If t exceeds the critical value at the chosen significance level, the difference is not due to chance.
- ROC curve: plots the true positive rate against the false positive rate as the decision threshold varies. An area under the curve close to 1 indicates a strong model. The diagonal, with area 0.5, corresponds to random guessing.
- Cost-benefit analysis: when errors have unequal costs (FN versus FP), the model with the lowest total cost is preferred.
5. Class imbalance. When positive tuples are rare, accuracy can look high even if the positives are missed. Recall, specificity, precision and F-measure are more informative in that case.
Conclusion: sound evaluation combines suitable metrics with resampling methods such as cross-validation or the bootstrap. Model selection then relies on significance tests, ROC analysis or cost considerations.
3 Describe the basic algorithm for decision tree induction. Explain the attribute selection measures information gain, gain ratio and Gini index, with their merits and drawbacks. 10 marks
A decision tree is a flowchart-like structure. Each internal node tests an attribute, each branch is an outcome of the test, and each leaf holds a class label. To classify a tuple, we follow a path from the root to a leaf. Algorithms such as ID3, C4.5 and CART build the tree greedily, top-down, by recursive divide-and-conquer without backtracking.
1. Basic algorithm
Generate_Decision_Tree(D, attribute_list)
create node N
if all tuples in D belong to the same class C then
return N as a leaf labelled C
if attribute_list is empty then
return N as a leaf labelled with the majority class of D
criterion = Attribute_Selection_Method(D, attribute_list)
label N with criterion
if splitting attribute is discrete and multiway splits are allowed then
remove it from attribute_list
for each outcome j of criterion
Dj = tuples of D satisfying outcome j
if Dj is empty then
attach a leaf labelled with the majority class of D
else
attach Generate_Decision_Tree(Dj, attribute_list)
return N2. Splitting cases for an attribute A
- Discrete-valued A: one branch for each known value.
- Continuous-valued A: a binary test A ≤ split_point. Candidate split points are the midpoints of adjacent sorted values.
- Discrete A in a binary tree: a test of the form A ∈ S_A, where S_A is a subset of the values of A.
3. Attribute selection measures. Each measure chooses the split that produces the purest partitions.
Information gain (ID3):
- Info(D) = −Σ pi log2 pi
- Info_A(D) = Σ (|Dj|/|D|) × Info(Dj)
- Gain(A) = Info(D) − Info_A(D)
- The attribute with the highest gain is chosen.
- Drawback: it is biased towards attributes with many values. A unique ID attribute gives pure partitions and maximum gain, yet it is useless for prediction.
Gain ratio (C4.5):
- SplitInfo_A(D) = −Σ (|Dj|/|D|) log2(|Dj|/|D|)
- GainRatio(A) = Gain(A)/SplitInfo_A(D)
- Dividing by SplitInfo penalises splits into many small partitions.
- Drawback: the ratio becomes unstable when SplitInfo is near 0. To avoid this, only attributes whose gain is at least average are considered.
Gini index (CART):
- Gini(D) = 1 − Σ pi²
- For a binary split into D1 and D2: Gini_A(D) = (|D1|/|D|)Gini(D1) + (|D2|/|D|)Gini(D2)
- ΔGini(A) = Gini(D) − Gini_A(D). The split with the largest reduction is chosen.
- Strength: it is efficient and naturally suits binary trees.
- Drawbacks: it still favours multivalued attributes, struggles when there are many classes, and tends to prefer equal-sized partitions.
Example: a node with 6 Yes and 4 No tuples has Gini = 1 − (0.36 + 0.16) = 0.48 and entropy = 0.971 bits.
Conclusion: tree induction is simple recursive partitioning. Its quality depends largely on the attribute selection measure, and each measure trades bias against stability.
4 What is tree pruning? Explain pre-pruning and post-pruning. Also discuss how decision tree induction is made scalable for very large databases, and how visual mining supports interactive tree construction. 10 marks
A fully grown decision tree often overfits the training data, because many branches reflect noise or outliers. Pruning removes the least reliable branches. The result is a smaller tree that is easier to understand and usually more accurate on unseen data.
1. Pre-pruning
- Tree construction is halted early: a node is not split when a goodness measure falls below a threshold. Suitable measures are information gain, Gini reduction or a chi-square significance test.
- The node becomes a leaf labelled with the majority class, or it stores the class distribution.
- Difficulty: choosing the threshold. A high threshold gives oversimplified trees, while a low one gives very little pruning.
2. Post-pruning The complete tree is grown first. Subtrees are then removed bottom-up and replaced by leaves labelled with the majority class.
- Cost-complexity pruning (CART): cost complexity is a function of the number of leaves and the error rate. For each internal node, the cost of keeping the subtree is compared with the cost of replacing it by a leaf, and the subtree is pruned if the leaf is cheaper. A separate pruning set is used, and the smallest tree with minimum error is kept.
- Pessimistic pruning (C4.5): uses the training error with a penalty added, so no separate pruning set is needed.
- Post-pruning is usually more reliable than pre-pruning but costs more computation. Even after pruning, trees may suffer from repetition and replication of subtrees.
3. Scalability of decision tree induction ID3, C4.5 and CART assume the training data fits in memory. With millions of tuples, swapping data between disk and memory makes them very slow. Scalable methods address this:
- SLIQ and SPRINT keep disk-resident attribute lists indexed by tuple identifiers. SLIQ also keeps a memory-resident class list, while SPRINT stores class labels inside the attribute lists, which makes it easy to parallelise.
- RainForest keeps an AVC-set (attribute value with class counts) for each attribute at each node. The AVC-group of a node is usually small enough to fit in memory, because its size depends on the number of distinct values and classes, not on the number of tuples.
- BOAT draws in-memory samples and builds several trees on bootstrap samples. It combines them into an initial tree close to the final one, then corrects it with about two scans of the data. It also supports incremental updates.
4. Visual mining for decision tree induction Perception-based classification (PBC) is an interactive, pixel-oriented approach.
- Each attribute is drawn as a circle segment.
- Each tuple's value is shown as a pixel coloured by its class label, with values sorted within the segment.
- The user sees where class colours separate and picks one or more split points directly.
- A tree view displays the tree built so far, and the algorithm can also suggest splits.
- The resulting trees tend to be smaller with comparable accuracy, and the user understands and trusts the model better.
Conclusion: pruning controls overfitting, scalable algorithms handle disk-resident data, and visual mining brings the user into the tree-building loop.
5 Consider the following training data for predicting whether a student passes (class Pass). Each line gives Attendance, Study, Pass. T1: High, Regular, Yes T2: High, Regular, Yes T3: High, Regular, Yes T4: High, Irregular, Yes T5: Medium, Regular, Yes T6: Medium, Irregular, No T7: Medium, Irregular, No T8: Low, Regular, Yes T9: Low, Irregular, No T10: Low, Irregular, No Using information gain, select the root attribute, construct the complete decision tree and classify X = (Attendance = Medium, Study = Irregular). 10 marks
ID3-style induction chooses, at every node, the attribute with the highest information gain. Splitting continues until each partition is pure.
Step 1: Entropy of the whole data set. There are 6 Yes and 4 No tuples. Info(D) = −0.6 log2 0.6 − 0.4 log2 0.4 = 0.6 × 0.737 + 0.4 × 1.322 = 0.442 + 0.529 = 0.971 bits
Step 2: Attribute Attendance.
- High: 4 tuples (4 Yes, 0 No), so Info = 0.
- Medium: 3 tuples (1 Yes, 2 No), so Info = −(1/3)log2(1/3) − (2/3)log2(2/3) = 0.528 + 0.390 = 0.918.
- Low: 3 tuples (1 Yes, 2 No), so Info = 0.918.
Info_Attendance(D) = (4/10)(0) + (3/10)(0.918) + (3/10)(0.918) = 0.551 Gain(Attendance) = 0.971 − 0.551 = 0.420
Step 3: Attribute Study.
- Regular: 5 tuples (5 Yes, 0 No), so Info = 0.
- Irregular: 5 tuples (1 Yes, 4 No), so Info = −0.2 log2 0.2 − 0.8 log2 0.8 = 0.464 + 0.258 = 0.722.
Info_Study(D) = (5/10)(0) + (5/10)(0.722) = 0.361 Gain(Study) = 0.971 − 0.361 = 0.610
Step 4: Root selection. Gain(Study) = 0.610 is greater than Gain(Attendance) = 0.420, so Study becomes the root.
Step 5: Expanding the branches.
- Study = Regular: all 5 tuples are Yes, so this branch is a leaf labelled Yes.
- Study = Irregular: the partition D' = {T4, T6, T7, T9, T10} has 1 Yes and 4 No, so Info(D') = 0.722.
- Only Attendance remains. High gives {T4} = Yes, Medium gives {T6, T7} = No, and Low gives {T9, T10} = No.
- Every partition is pure, so Info_Attendance(D') = 0 and Gain = 0.722 − 0 = 0.722. D' is split on Attendance.
Step 6: Final tree, described in words. The root node tests Study.
- Regular → leaf Pass = Yes
- Irregular → node testing Attendance:
- High → leaf Yes
- Medium → leaf No
- Low → leaf No
Equivalent IF-THEN rules, one for each root-to-leaf path:
- IF Study = Regular THEN Pass = Yes
- IF Study = Irregular AND Attendance = High THEN Pass = Yes
- IF Study = Irregular AND Attendance = Medium THEN Pass = No
- IF Study = Irregular AND Attendance = Low THEN Pass = No
These rules are mutually exclusive and exhaustive, because every tuple follows exactly one root-to-leaf path, so no conflict resolution or default rule is needed.
Step 7: Classifying X = (Medium, Irregular). Study = Irregular leads to the Attendance node, and Attendance = Medium leads to the leaf No.
Final result: the root is Study (gain 0.610), and X is classified as Pass = No.
6 State Bayes' theorem and explain how the naive Bayesian classifier uses it. Using the training data below, classify X = (Weather = Rainy, Traffic = Heavy, Day = Weekday). Each line gives Weather, Traffic, Day, Late. T1: Rainy, Heavy, Weekday, Yes T2: Rainy, Heavy, Weekday, Yes T3: Rainy, Light, Weekend, Yes T4: Sunny, Heavy, Weekday, Yes T5: Sunny, Light, Weekday, No T6: Sunny, Light, Weekend, No T7: Rainy, Light, Weekday, No T8: Sunny, Heavy, Weekend, No T9: Sunny, Light, Weekday, No T10: Rainy, Light, Weekend, No 10 marks
Bayesian classifiers are statistical classifiers that predict the probability of class membership.
Bayes' theorem: P(Ci|X) = P(X|Ci) P(Ci) / P(X)
- P(Ci|X) is the posterior probability.
- P(Ci) is the prior probability.
- P(X|Ci) is the likelihood.
- P(X) is the evidence.
The naive Bayesian classifier assigns X to the class with the maximum posterior probability. P(X) is the same for every class, so it only needs to maximise P(X|Ci) P(Ci). It also assumes class-conditional independence: the attribute values are independent of one another given the class. Hence P(X|Ci) = P(x1|Ci) × P(x2|Ci) × ... × P(xn|Ci).
Step 1: Prior probabilities. P(Yes) = 4/10 = 0.4 and P(No) = 6/10 = 0.6
Step 2: Conditional probabilities for the values in X. Class Yes (T1 to T4):
- P(Rainy|Yes) = 3/4
- P(Heavy|Yes) = 3/4
- P(Weekday|Yes) = 3/4
Class No (T5 to T10):
- P(Rainy|No) = 2/6
- P(Heavy|No) = 1/6
- P(Weekday|No) = 3/6
Step 3: Likelihoods. P(X|Yes) = 0.75 × 0.75 × 0.75 = 0.421875 P(X|No) = (2/6) × (1/6) × (3/6) = 6/216 = 0.02778
Step 4: Products with the priors. P(X|Yes) P(Yes) = 0.421875 × 0.4 = 0.16875 P(X|No) P(No) = 0.02778 × 0.6 = 0.01667
Step 5: Decision. 0.16875 > 0.01667, so X is classified as Late = Yes. Normalising the two products: P(Yes|X) = 0.16875 / (0.16875 + 0.01667) = 0.16875 / 0.18542 = 0.910 P(No|X) = 0.090
Practical points:
- Zero-probability problem: if an attribute value never occurs with a class, the whole product becomes 0. The Laplacian correction adds 1 to each count, and the number of attribute values to the denominator, so no probability is ever zero.
- Continuous attributes: these are usually modelled with a Gaussian distribution, using the mean and standard deviation of the attribute within each class.
- Strengths: the classifier is fast, needs only one pass over the data to collect counts, and performs well in practice even when the independence assumption is only approximately true.
- Weakness: dependencies among attributes are ignored. Bayesian belief networks address this limitation.
Conclusion: by combining the prior with the product of the conditional probabilities, the naive Bayesian classifier predicts Late = Yes for X, with a posterior probability of about 0.91.
Association Analysis
Syllabus: Problem definition of association analysis; Frequent itemset generation; Rule generation: confidence-based pruning; Rule generation in the Apriori algorithm; Compact representation of frequent itemsets; FP-growth algorithm
One-page revision summary
- Association analysis finds rules X → Y with X ∩ Y = ∅ from transaction data, using support and confidence thresholds.
- Support count σ(X) is the number of transactions containing X; support is σ(X ∪ Y)/N and confidence is σ(X ∪ Y)/σ(X).
- For d items there are 2^d − 1 candidate itemsets and 3^d − 2^(d+1) + 1 possible rules, so brute force is infeasible.
- The task is split into frequent itemset generation (expensive) and rule generation, because all rules from the same itemset share the same support.
- Apriori principle: subsets of frequent itemsets are frequent and supersets of infrequent itemsets are infrequent, which allows support-based pruning.
- Apriori works level by level: generate Ck by the F(k−1) × F(k−1) merge, prune candidates with an infrequent (k−1)-subset, count support, and keep Fk.
- A hash tree reduces the number of comparisons between transaction subsets and candidates during support counting.
- A frequent k-itemset yields 2^k − 2 rules, and their confidence needs only stored support counts, so no extra database scan is required.
- Confidence-based pruning: within one itemset, if X → Y−X fails minconf, every rule whose antecedent is a subset of X fails too.
- In Apriori rule generation, consequents grow level-wise, and an (m+1)-item consequent is formed only from m-item consequents that gave strong rules.
- Maximal frequent itemsets have no frequent immediate superset; they are the most compact representation but lose support values.
- Closed frequent itemsets have no immediate superset with equal support; they are lossless, and maximal ⊆ closed ⊆ frequent.
- FP-growth builds an FP-tree in two scans, with items sorted by descending support and shared prefixes merged with counts.
- FP-growth mines each item through its conditional pattern base and conditional FP-tree, working bottom-up with no candidate generation.
Learn these by heart
- s(X → Y) = σ(X ∪ Y)/N and c(X → Y) = σ(X ∪ Y)/σ(X)
- Number of possible rules R = 3^d − 2^(d+1) + 1 (for d = 6, R = 602)
- Anti-monotone support: X ⊆ Y → s(X) ≥ s(Y)
- Confidence pruning: X' ⊂ X ⊂ Y → c(X' → Y−X') ≤ c(X → Y−X)
- Maximal ⊆ Closed ⊆ Frequent; sup(X) = max support of the closed supersets of X
- A frequent k-itemset gives 2^k − 2 candidate rules
2-mark questions
1 A database has 10 transactions. The itemset {bread} appears in 5 of them and {bread, milk} appears in 4. Find the support and confidence of the rule {bread} → {milk}. 2 marks
Support = σ({bread, milk}) / N = 4/10 = 0.4, that is 40%.
Confidence = σ({bread, milk}) / σ({bread}) = 4/5 = 0.8, that is 80%.
So the rule covers 40% of all transactions, and 80% of the transactions that contain bread also contain milk.
2 State the Apriori principle and the property of support on which it rests. 2 marks
Apriori principle: if an itemset is frequent, then every subset of it is also frequent. Equivalently, if an itemset is infrequent, then all of its supersets are infrequent. It rests on the anti-monotone property of support: X ⊆ Y → s(X) ≥ s(Y). This lets the algorithm prune candidates without counting their support.
3 What is confidence-based pruning in rule generation? 2 marks
Consider rules generated from the same frequent itemset Y. If the rule X → Y−X fails minconf, then every rule X' → Y−X' with X' ⊂ X also fails. The reason is that σ(X') ≥ σ(X), so σ(Y)/σ(X') ≤ σ(Y)/σ(X). Any rule whose consequent is a superset of a failed consequent can therefore be skipped.
4 Define a maximal frequent itemset and state one advantage and one limitation of it. 2 marks
A maximal frequent itemset is a frequent itemset none of whose immediate supersets is frequent. Advantage: every frequent itemset is a subset of some maximal itemset, so the set of maximal itemsets is a very compact representation. Limitation: the support counts of the subsets cannot be recovered from it.
5 Define a closed frequent itemset. How is it related to a maximal frequent itemset? 2 marks
An itemset X is closed if none of its immediate supersets has the same support count as X. It is a closed frequent itemset if it is also frequent (support ≥ minsup). Every maximal frequent itemset is closed, so maximal ⊆ closed ⊆ frequent. Unlike maximal itemsets, closed itemsets preserve exact support information.
6 Define an FP-tree and a conditional pattern base. 2 marks
An FP-tree is a compressed prefix tree of the database. Transactions are inserted with their frequent items sorted in descending order of support, and shared prefixes are merged into paths with counts. The conditional pattern base of an item x is the set of prefix paths that end at x's nodes, each path carrying x's node count.
10-mark questions
1 Formally define the association analysis problem. Explain itemset, support count, support and confidence with an example. Derive the number of possible rules for d items and explain why the problem is split into two subtasks. 10 marks
Association analysis discovers interesting relationships hidden in large transaction data. A typical example is a set of items that are often bought together in a supermarket. These relationships are expressed as frequent itemsets or association rules.
1. Data model. Let I = {i1, i2, ..., id} be the set of items and T = {t1, ..., tN} the set of transactions, where each ti ⊆ I. The data can be stored as a binary table: rows are transactions, columns are items, and a cell is 1 if the item is present. Quantity and price are ignored.
2. Itemset and support count. An itemset is any subset of I, and an itemset with k items is called a k-itemset. The support count of X is σ(X) = |{ti ∈ T | X ⊆ ti}|, the number of transactions that contain X.
3. Association rule. A rule is an implication X → Y where X ∩ Y = ∅.
- Support s(X → Y) = σ(X ∪ Y) / N
- Confidence c(X → Y) = σ(X ∪ Y) / σ(X)
Low support means the pattern may be a chance occurrence. Confidence measures how reliably Y follows X; it estimates P(Y | X).
4. Example. Take T1 = {milk, bread}, T2 = {bread, eggs}, T3 = {milk, bread, eggs}, T4 = {milk}, T5 = {bread, eggs}. For the rule {milk} → {bread}, σ(milk, bread) = 2 and σ(milk) = 3. So s = 2/5 = 0.4 and c = 2/3 ≈ 0.67.
5. Problem statement. Given T, minsup and minconf, find all rules with s ≥ minsup and c ≥ minconf.
6. Brute-force count of rules. Each item can go into the antecedent X, into the consequent Y, or into neither, giving 3^d assignments. We must remove the assignments where X is empty (2^d of them) and those where Y is empty (2^d). The case where both are empty was removed twice, so we add 1 back.
R = 3^d − 2^(d+1) + 1.
For d = 6: R = 729 − 128 + 1 = 602 rules. Most of these fail the thresholds, so evaluating all of them wastes effort.
7. Decomposition. The support of X → Y depends only on X ∪ Y. For example, {milk, bread} → {eggs}, {eggs} → {milk, bread} and {milk} → {bread, eggs} all have the same support. If an itemset is infrequent, all its rules can be discarded at once. The task is therefore split into two steps:
- Frequent itemset generation: find all itemsets with support ≥ minsup. This is the expensive step.
- Rule generation: from each frequent itemset, extract the rules that satisfy minconf (strong rules).
Conclusion: support and confidence give a precise formulation of the problem, and the two-step split avoids the exponential brute-force search. Note that a rule shows co-occurrence, not causality.
2 Explain frequent itemset generation. Discuss the itemset lattice, the brute-force cost, the Apriori principle with support-based pruning, and the steps of the Apriori algorithm. 10 marks
Frequent itemset generation finds every itemset whose support is at least minsup. It is the most expensive part of association analysis.
1. Itemset lattice. With d items there are 2^d − 1 non-empty itemsets. Picture a lattice with the null set at the top, the 1-itemsets on the next level, then the 2-itemsets, and so on, ending with the full itemset at the bottom. Each edge joins an itemset to one of its immediate supersets.
2. Brute-force cost. Every candidate is compared with every transaction, costing O(N × M × w). Here N is the number of transactions, M = 2^d − 1 is the number of candidates, and w is the maximum transaction width. The cost can be reduced in three ways:
- reduce M by pruning candidates
- reduce N
- reduce the number of comparisons using a hash tree
3. Apriori principle. If an itemset is frequent, all its subsets are frequent. This holds because support is anti-monotone: ∀X, Y: (X ⊆ Y) → s(X) ≥ s(Y). In the other direction, if {a, b} is infrequent, then every superset such as {a, b, c} or {a, b, c, d} is infrequent. The whole sub-lattice below {a, b} can be removed without counting; this is called support-based pruning.
4. Apriori algorithm (level-wise, generate-and-test):
k = 1
F1 = { i ∈ I | σ(i) ≥ N × minsup }
repeat
k = k + 1
Ck = candidate_gen(F(k-1))
Ck = candidate_prune(Ck, F(k-1))
for each transaction t in T
for each c in Ck with c ⊆ t
σ(c) = σ(c) + 1
Fk = { c ∈ Ck | σ(c) ≥ N × minsup }
until Fk is empty
answer = union of all Fk5. Candidate generation (F(k−1) × F(k−1) method). Keep the items of each itemset sorted. Two frequent (k−1)-itemsets are merged only if their first k−2 items are identical. For example, {bread, diaper} and {bread, milk} merge into {bread, diaper, milk}. This method is complete and creates no duplicate candidates.
6. Candidate pruning. A candidate is deleted if any of its (k−1)-subsets is not in F(k−1).
7. Support counting. The algorithm enumerates the k-subsets of each transaction; a 5-item transaction has C(5,3) = 10 subsets of size 3. These subsets are matched against candidates stored in a hash tree. The tree hashes items into buckets, so each subset is compared only with the candidates in the matching leaf.
8. Factors affecting cost: a lower minsup, more items, more transactions and wider transactions all increase the work.
Conclusion: by combining the Apriori principle with careful candidate generation and hash-tree counting, the algorithm examines only a small fraction of the 2^d − 1 itemsets.
3 Explain rule generation in the Apriori algorithm. State and prove the theorem used for confidence-based pruning, and illustrate the pruning on the rule lattice of a frequent 4-itemset. 10 marks
Once the frequent itemsets are known, strong rules are extracted from each of them. A frequent k-itemset Y can produce 2^k − 2 rules of the form X → Y − X, leaving out the cases with an empty antecedent or consequent. Every such rule has support s(Y), which already meets minsup, so only confidence needs to be checked. The confidence is σ(Y)/σ(X), and both counts were stored during itemset generation, so no extra database scan is needed.
1. Theorem. Let Y be a frequent itemset and X' ⊂ X ⊂ Y. If X → Y − X does not satisfy minconf, then X' → Y − X' also fails.
2. Proof. We have c(X → Y−X) = σ(Y)/σ(X) and c(X' → Y−X') = σ(Y)/σ(X'). Every transaction containing X also contains X', so σ(X') ≥ σ(X). The numerators are equal, so c(X' → Y−X') ≤ c(X → Y−X) < minconf. ∎
In words, moving items from the antecedent to the consequent can never raise confidence. Confidence is not anti-monotone across rules from different itemsets; the property holds only within one itemset.
3. Rule lattice for Y = {a, b, c, d}. It contains 14 rules arranged by the size of the consequent:
- Level 1: bcd→a, acd→b, abd→c, abc→d
- Level 2: cd→ab, bd→ac, bc→ad, ad→bc, ac→bd, ab→cd
- Level 3: d→abc, c→abd, b→acd, a→bcd
Suppose bcd→a has low confidence. Then every rule whose consequent contains a is pruned without being evaluated: cd→ab, bd→ac, bc→ad, d→abc, c→abd and b→acd. That is six rules removed by one failure.
4. Level-wise procedure:
for each frequent itemset f with |f| = k ≥ 2
H1 = { {i} | i ∈ f } // 1-item consequents
gen_rules(f, H1, 1)
gen_rules(f, Hm, m)
for each h in Hm
conf = σ(f) / σ(f − h)
if conf ≥ minconf then output (f − h) → h
else remove h from Hm
if m + 1 < k and Hm has at least two members
H(m+1) = candidate_gen(Hm) // merge consequents
H(m+1) = candidate_prune(H(m+1), Hm)
gen_rules(f, H(m+1), m + 1)Consequents are grown with the same candidate generation used for itemsets. A consequent is created only if all its smaller consequents produced strong rules.
Conclusion: the theorem allows the Apriori algorithm to generate rules level by level and discard whole branches of the rule lattice. This saves many confidence computations without missing any strong rule.
4 Why is a compact representation of frequent itemsets needed? Explain maximal and closed frequent itemsets. For the transactions T1 = {A,B,C}, T2 = {A,C,D}, T3 = {B,C,E}, T4 = {A,B,C,E}, T5 = {B,E} with minimum support count 2, the frequent itemsets are A:3, B:4, C:4, E:3, AB:2, AC:3, BC:3, BE:3, CE:2, ABC:2, BCE:2. Identify the maximal and closed frequent itemsets. 10 marks
The number of frequent itemsets can grow very large. A single frequent 10-itemset implies 2^10 − 1 = 1023 frequent subsets. Storing and reporting all of them is wasteful, so smaller sets that represent all frequent itemsets are used.
1. Maximal frequent itemset. A frequent itemset none of whose immediate supersets is frequent. In the lattice, these itemsets lie on the border between frequent and infrequent itemsets. Every frequent itemset is a subset of some maximal one, so the frequent itemsets can be regenerated from them. Their supports, however, are lost.
2. Closed frequent itemset. An itemset X is closed if no immediate superset has the same support count. It is a closed frequent itemset if it is also frequent. This representation is lossless: sup(X) = max{ sup(Y) | Y closed frequent, X ⊆ Y }.
3. Relationship. Maximal ⊆ Closed ⊆ Frequent. A maximal itemset has no frequent superset, so no superset can share its support, which makes it closed.
4. Finding the maximal itemsets.
- The immediate supersets of ABC are ABCD (support 0) and ABCE (support 1, T4 only). Both are infrequent, so ABC is maximal.
- The immediate supersets of BCE are ABCE (support 1) and BCDE (support 0). Both are infrequent, so BCE is maximal.
- Every other frequent itemset is contained in ABC or BCE.
Maximal = {ABC, BCE}.
5. Testing closure, item by item.
- A:3 has superset AC:3 with the same count, so it is not closed.
- B:4 has supersets AB:2, BC:3, BE:3, all smaller, so it is closed.
- C:4 has supersets AC:3, BC:3, CE:2, so it is closed.
- E:3 has superset BE:3, so it is not closed.
- AB:2 has superset ABC:2, so it is not closed.
- AC:3 has superset ABC:2, so it is closed.
- BC:3 has supersets ABC:2 and BCE:2, so it is closed.
- BE:3 has superset BCE:2, so it is closed.
- CE:2 has superset BCE:2, so it is not closed.
- ABC:2 and BCE:2 have superset ABCE:1, so both are closed.
Closed frequent = {B:4, C:4, AC:3, BC:3, BE:3, ABC:2, BCE:2}, which is 7 itemsets. So 2 maximal ⊆ 7 closed ⊆ 11 frequent.
6. Recovering the support of non-closed itemsets.
- sup(A) = max(AC:3, ABC:2) = 3
- sup(E) = max(BE:3, BCE:2) = 3
- sup(AB) = ABC:2 = 2
- sup(CE) = BCE:2 = 2
All of these match the given counts.
Conclusion: maximal itemsets give the smallest representation but lose supports. Closed itemsets are slightly larger but keep every support count, so rules can still be generated from them.
5 Apply the Apriori algorithm to the transactions T1 = {A,B,C}, T2 = {A,C,D}, T3 = {B,C,E}, T4 = {A,B,C,E}, T5 = {B,E} with a minimum support count of 2 to find all frequent itemsets. Then generate association rules from the frequent 3-itemsets with a minimum confidence of 70%, showing confidence-based pruning. 10 marks
Apriori finds frequent itemsets level by level and uses the Apriori principle to prune candidates. Rules are then produced from each frequent itemset, with confidence-based pruning. Here N = 5 and the minimum support count is 2.
1. Level 1 (C1 and F1). Counts: A = 3, B = 4, C = 4, D = 1, E = 3. D is below 2 and is removed. F1 = {A:3, B:4, C:4, E:3}.
2. Level 2. C2 is formed from all pairs of F1.
- AB = 2 (T1, T4)
- AC = 3 (T1, T2, T4)
- AE = 1 (T4)
- BC = 3 (T1, T3, T4)
- BE = 3 (T3, T4, T5)
- CE = 2 (T3, T4)
AE is removed. F2 = {AB:2, AC:3, BC:3, BE:3, CE:2}.
3. Level 3. Merge pairs from F2 that share their first item.
- AB + AC gives ABC.
- BC + BE gives BCE.
Pruning check: the subsets of ABC (AB, AC, BC) are all frequent, and so are the subsets of BCE (BC, BE, CE).
Counting: ABC = 2 (T1, T4) and BCE = 2 (T3, T4). F3 = {ABC:2, BCE:2}.
4. Level 4. ABC and BCE do not share their first two items, so C4 is empty and the algorithm stops. ABCE would be pruned anyway because AE is infrequent.
All frequent itemsets (11): A3, B4, C4, E3, AB2, AC3, BC3, BE3, CE2, ABC2, BCE2.
5. Rules from ABC, with σ = 2. Start with 1-item consequents:
- AB → C: 2/2 = 100%, kept
- AC → B: 2/3 = 66.7%, rejected
- BC → A: 2/3 = 66.7%, rejected
Only the consequent {C} survives. Two survivors are needed to build a 2-item consequent, so A → BC, B → AC and C → AB are pruned without evaluation. Check: their confidences are 2/3, 2/4 and 2/4, all below 70%, so the pruning was safe.
6. Rules from BCE, with σ = 2.
- BC → E: 2/3 = 66.7%, rejected
- BE → C: 2/3 = 66.7%, rejected
- CE → B: 2/2 = 100%, kept
The rules B → CE (2/4), C → BE (2/4) and E → BC (2/3) are pruned, and they would indeed fail.
7. Strong rules:
- {A, B} → {C}: support 2/5 = 40%, confidence 100%
- {C, E} → {B}: support 40%, confidence 100%
Conclusion: Apriori counted only 6 two-item and 2 three-item candidates instead of every subset. Confidence-based pruning removed six of the twelve possible 3-itemset rules without computing them.
6 Explain the FP-growth algorithm. Construct the FP-tree for the transactions T1 = {P,Q,R}, T2 = {Q,R,S}, T3 = {P,Q,S}, T4 = {P,R}, T5 = {P,Q,R,S} with a minimum support count of 3, and mine all frequent itemsets. 10 marks
FP-growth finds frequent itemsets without generating candidates. It compresses the database into an FP-tree using two scans. It then mines the tree recursively through conditional pattern bases and conditional FP-trees, using a divide-and-conquer approach.
1. First scan: item counts. P = 4, Q = 4, R = 4, S = 3. All counts are at least 3, so all items are frequent. Items are ordered by descending support, with ties broken alphabetically: P, Q, R, S.
2. Ordered transactions:
- T1: P Q R
- T2: Q R S
- T3: P Q S
- T4: P R
- T5: P Q R S
3. Second scan: inserting each transaction.
- T1 creates the path null → P:1 → Q:1 → R:1.
- T2 starts with Q, so a new branch null → Q:1 → R:1 → S:1 is created.
- T3 shares the prefix PQ: P becomes 2 and Q becomes 2, and a new child S:1 is added under that Q.
- T4 shares P, which becomes 3, and a new child R:1 is added under P.
- T5 follows P → Q → R: P becomes 4, Q becomes 3, R becomes 2, and a new child S:1 is added under that R.
Final tree:
null
├─ P:4
│ ├─ Q:3
│ │ ├─ R:2
│ │ │ └─ S:1
│ │ └─ S:1
│ └─ R:1
└─ Q:1
└─ R:1
└─ S:1A header table holds a node-link chain for each item. Check: the S nodes sum to 1+1+1 = 3, the R nodes to 2+1+1 = 4, and the Q nodes to 3+1 = 4, matching the first scan.
4. Mining, from the least frequent item upward.
S (support 3).
- Conditional pattern base: {P,Q,R}:1, {P,Q}:1, {Q,R}:1.
- Counts within the base: P = 2, Q = 3, R = 2. Only Q reaches 3.
- Conditional FP-tree: Q:3. Output {Q,S}:3.
R (support 4).
- Conditional pattern base: {P,Q}:2, {P}:1, {Q}:1.
- Counts: P = 3, Q = 3. Output {P,R}:3 and {Q,R}:3.
- Inside the R-conditional tree, Q's prefix path is {P}:2. Since 2 < 3, {P,Q,R} is not frequent.
Q (support 4).
- Conditional pattern base: {P}:3, so P = 3. Output {P,Q}:3.
P. It has no prefix path; output {P}:4.
5. Result: {P}:4, {Q}:4, {R}:4, {S}:3, {P,Q}:3, {P,R}:3, {Q,R}:3, {Q,S}:3. These match direct counts; for example, PQR occurs only in T1 and T5, which is 2.
6. Merits:
- only two database scans
- no candidate generation
- shared prefixes give strong compression when transactions overlap
The tree can be large when the data is sparse.
Conclusion: FP-growth found the same frequent itemsets that Apriori would find, but it worked on a compact tree and small conditional sub-problems instead of repeatedly scanning the database.
Cluster Analysis
Syllabus: Overview, basics and importance of cluster analysis; Clustering techniques; Different types of clusters; The basic K-means algorithm; K-means additional issues; Bisecting K-means; Agglomerative hierarchical clustering: the basic algorithm; DBSCAN: the traditional density-based approach; The DBSCAN algorithm; Strengths and weaknesses of DBSCAN
One-page revision summary
- Cluster analysis groups objects using only the data, maximising similarity within groups and difference between groups, without class labels.
- Clustering serves understanding (taxonomy, customer segmentation) and utility (summarization, compression, nearest-neighbour search).
- Clusterings may be partitional or hierarchical, exclusive, overlapping or fuzzy, and complete or partial.
- Cluster types include well-separated, prototype-based, graph-based (contiguity), density-based and shared-property (conceptual).
- Basic K-means picks K initial centroids, assigns points to the nearest centroid, recomputes centroids as means, and repeats until the centroids stop changing.
- K-means minimises SSE, converges to a local minimum, and needs K in advance.
- Poor initial centroids give high SSE; remedies are multiple runs, choosing farthest points, using hierarchical clustering on a sample, or bisecting K-means.
- Empty clusters are fixed by choosing the point farthest from all centroids, or a point from the cluster with the highest SSE.
- Outliers distort centroids and should be removed before or after clustering.
- Post-processing reduces SSE by splitting high-SSE clusters, adding centroids, dispersing clusters or merging close clusters.
- K-means struggles with non-globular clusters and with clusters of different sizes or densities.
- Bisecting K-means repeatedly splits the largest or highest-SSE cluster using several 2-means trials, keeping the lowest-SSE split; it yields a divisive hierarchy.
- Agglomerative clustering starts from singletons and merges the closest pair of clusters each step, producing a dendrogram.
- Inter-cluster proximity can be MIN (single link), MAX (complete link), group average, Ward's method or centroid distance.
- Agglomerative clustering merges are irreversible and it has no global objective; it needs O(m²) space and O(m³) time in the basic form.
- DBSCAN labels points as core, border or noise using Eps and MinPts, links core points within Eps into clusters, and attaches border points to them.
- Eps can be chosen from the sorted k-dist plot at the point where the curve rises sharply.
- DBSCAN handles noise and arbitrary shapes and finds the number of clusters itself, but fails with varying densities and high-dimensional data.
Learn these by heart
- SSE = Σ_{i=1..K} Σ_{x∈Ci} dist(ci, x)²
- Centroid ci = (1/mi) Σ_{x∈Ci} x, the mean of the mi points in cluster Ci
- K-means: time O(I·K·m·n), space O((m+K)·n)
- Single link d(Ci,Cj) = min distance between their points; complete link = max distance; group average = mean of all pairwise distances
- Agglomerative clustering: O(m²) space and O(m³) time (O(m² log m) with heaps)
- DBSCAN: core point if |N_Eps(p)| ≥ MinPts (counting p itself); border point if not core but within Eps of a core point; otherwise noise
2-mark questions
1 What is cluster analysis? State why it is important. 2 marks
Cluster analysis is the unsupervised grouping of data objects into clusters, using only the data itself, so that objects in the same cluster are similar and objects in different clusters are dissimilar. It helps in understanding data, for example customer segments or gene groups. It is also useful for summarization, compression and fast nearest-neighbour search.
2 Distinguish between partitional and hierarchical clustering. 2 marks
A partitional clustering divides the objects into non-overlapping subsets, so each object belongs to exactly one cluster. K-means is an example. A hierarchical clustering produces nested clusters organised as a tree called a dendrogram. Each internal node is the union of the clusters below it, and each leaf is a single object. Agglomerative clustering is an example.
3 What are prototype-based and density-based clusters? 2 marks
In a prototype-based cluster, each object is closer to the prototype (centroid or medoid) of its own cluster than to the prototype of any other cluster, so such clusters tend to be globular. A density-based cluster is a dense region of objects surrounded by a region of low density. This allows irregular shapes and leaves noise outside.
4 Define SSE as used in K-means clustering. 2 marks
Sum of Squared Error measures the quality of a clustering: SSE = Σ_{i=1..K} Σ_{x∈Ci} dist(ci, x)², where ci is the centroid of cluster Ci. K-means tries to minimise SSE. Among several runs, the clustering with the lowest SSE is preferred because its centroids represent their points better.
5 Define core, border and noise points in DBSCAN. 2 marks
DBSCAN uses a radius Eps and a threshold MinPts.
- A core point has at least MinPts points, counting itself, within distance Eps.
- A border point is not a core point but lies within the Eps-neighbourhood of some core point.
- A noise point is neither core nor border and is discarded.
6 State any two weaknesses of DBSCAN. 2 marks
- It struggles when clusters have widely varying densities, because a single pair of Eps and MinPts values cannot suit all clusters.
- It performs poorly on high-dimensional data, where density is hard to define. Neighbourhood computation also becomes expensive, and choosing suitable Eps and MinPts values needs care.
10-mark questions
1 Explain the basics and importance of cluster analysis. Describe the different types of clusterings (clustering techniques) and the different types of clusters. 10 marks
Cluster analysis divides data objects into groups (clusters) using only information found in the data. Objects within a group should be similar to each other and different from objects in other groups. It is unsupervised learning, because no class labels are used. The greater the similarity within groups and the difference between groups, the better the clustering.
1. Importance of cluster analysis
- Understanding: discovering taxonomies in biology, grouping web search results, finding climate patterns and segmenting customers for marketing.
- Utility: summarization (a cluster prototype stands for many objects), compression (vector quantization) and faster nearest-neighbour search.
- Preprocessing: it supports classification, outlier detection and data reduction.
2. Types of clusterings (clustering techniques)
- Partitional versus hierarchical: a partitional clustering splits objects into non-overlapping subsets, each object in exactly one subset. A hierarchical clustering gives nested clusters organised as a tree (dendrogram), where each internal node is the union of its children.
- Exclusive, overlapping and fuzzy: exclusive assigns each object to one cluster. Overlapping lets an object belong to several clusters at once. Fuzzy gives every object a membership weight between 0 and 1 for every cluster, and the weights of an object sum to 1.
- Complete versus partial: a complete clustering assigns every object. A partial clustering may leave noise or uninteresting objects unassigned.
3. Types of clusters
- Well-separated: each object is closer to every object in its own cluster than to any object outside it.
- Prototype-based (centre-based): each object is closer to its own cluster's prototype (centroid or medoid) than to any other prototype. Such clusters are usually globular.
- Graph-based (contiguity-based): objects are nodes and a cluster is a connected component. An object is closer to at least one member of its cluster than to any non-member, so clusters can form chains.
- Density-based: a dense region of objects surrounded by low density. This handles irregular shapes and noise.
- Shared-property (conceptual): objects that share some property. This is the most general notion.
Conclusion: the type of clustering and the notion of cluster chosen decide which algorithm suits a problem. K-means targets prototype-based clusters, agglomerative methods build hierarchies, and DBSCAN finds density-based clusters.
2 Explain the basic K-means algorithm along with its additional issues such as choosing initial centroids, empty clusters, outliers and post-processing. 10 marks
K-means is a partitional, prototype-based technique. It divides data into a user-specified number K of clusters, each represented by its centroid (the mean of its points).
1. Basic algorithm
1. Select K points as initial centroids.
2. repeat
3. Form K clusters by assigning every point to its closest centroid.
4. Recompute the centroid of each cluster.
5. until the centroids do not change2. Key ideas
- Proximity: Euclidean distance for points in space, cosine similarity for documents.
- Objective: minimise SSE = Σ_{i=1..K} Σ_{x∈Ci} dist(ci, x)². The mean is the centroid that minimises SSE for a cluster.
- Convergence: most changes happen in early iterations, so a weaker stopping rule (for example, fewer than 1% of points change) is often used.
- Complexity: time O(I·K·m·n) and space O((m+K)·n), for m points, n attributes and I iterations.
3. Choosing initial centroids Random initial centroids may lead to a poor local minimum with high SSE. Remedies:
- Run K-means several times and keep the result with the lowest SSE.
- Pick the first centroid at random, then pick each next centroid as the point farthest from the centroids already chosen.
- Cluster a sample with hierarchical clustering and use those centroids.
- Use bisecting K-means.
4. Handling empty clusters If no point is assigned to a centroid, replace that centroid with one of these:
- the point farthest from all current centroids, or
- a point from the cluster with the highest SSE, which also splits that cluster.
5. Outliers Outliers pull centroids away from the true centre and inflate SSE. They can be removed before clustering, or points that add unusually large SSE can be removed afterwards.
6. Reducing SSE with post-processing
- Split the cluster with the largest SSE.
- Introduce a new centroid, for example at the point farthest from any centroid.
- Disperse a cluster by removing its centroid and reassigning its points.
- Merge two clusters whose union gives the smallest increase in SSE.
7. Incremental update Centroids can be updated after each single assignment instead of after all assignments. This avoids empty clusters but depends on the order of points.
Conclusion: K-means is simple and efficient. It needs K in advance and works best for globular clusters of similar size and density. Good initialization and post-processing greatly improve its results.
3 Apply the K-means algorithm with K = 2 to the points P1(1,1), P2(2,1), P3(1,2), P4(6,5), P5(7,6) and P6(6,7). Take P1 and P2 as the initial centroids and use Euclidean distance. Show every iteration, the final clusters and the final SSE. 10 marks
K-means assigns each point to its nearest centroid and recomputes centroids as cluster means until no point moves. The square root does not change which centroid is nearer, so squared Euclidean distances (d²) are compared below.
Initial centroids: c1 = (1,1), c2 = (2,1).
Step 1: Iteration 1 assignment (d² to c1, d² to c2)
- P1(1,1): 0, 1 → C1
- P2(2,1): 1, 0 → C2
- P3(1,2): 1, 2 → C1
- P4(6,5): 25+16 = 41, 16+16 = 32 → C2
- P5(7,6): 36+25 = 61, 25+25 = 50 → C2
- P6(6,7): 25+36 = 61, 16+36 = 52 → C2
C1 = {P1, P3}, C2 = {P2, P4, P5, P6}
Step 2: Update centroids
- c1 = ((1+1)/2, (1+2)/2) = (1, 1.5)
- c2 = ((2+6+7+6)/4, (1+5+6+7)/4) = (21/4, 19/4) = (5.25, 4.75)
Step 3: Iteration 2 assignment (d² to c1, d² to c2)
- P1: 0+0.25 = 0.25; 18.0625+14.0625 = 32.125 → C1
- P2: 1+0.25 = 1.25; 10.5625+14.0625 = 24.625 → C1
- P3: 0+0.25 = 0.25; 18.0625+7.5625 = 25.625 → C1
- P4: 25+12.25 = 37.25; 0.5625+0.0625 = 0.625 → C2
- P5: 36+20.25 = 56.25; 3.0625+1.5625 = 4.625 → C2
- P6: 25+30.25 = 55.25; 0.5625+5.0625 = 5.625 → C2
P2 has moved to C1. Now C1 = {P1, P2, P3} and C2 = {P4, P5, P6}.
Step 4: Update centroids
- c1 = ((1+2+1)/3, (1+1+2)/3) = (4/3, 4/3) ≈ (1.33, 1.33)
- c2 = ((6+7+6)/3, (5+6+7)/3) = (19/3, 6) ≈ (6.33, 6)
Step 5: Iteration 3 assignment P1, P2 and P3 are each at most 5/9 ≈ 0.56 (squared) from c1 and more than 28 from c2. For example, P2 to c1 = (2/3)² + (1/3)² = 5/9.
P4, P5 and P6 are each at most 10/9 ≈ 1.11 from c2 and more than 34 from c1. For example, P4 to c2 = (1/3)² + 1² = 10/9.
No point changes cluster, so the centroids stay the same and the algorithm stops.
Step 6: Final SSE
- C1 about (4/3, 4/3): P1 = 1/9+1/9 = 2/9; P2 = 4/9+1/9 = 5/9; P3 = 1/9+4/9 = 5/9. Total = 12/9 = 4/3.
- C2 about (19/3, 6): P4 = 1/9+1 = 10/9; P5 = 4/9+0 = 4/9; P6 = 1/9+1 = 10/9. Total = 24/9 = 8/3.
- SSE = 4/3 + 8/3 = 4.
Conclusion: K-means converged in three iterations to C1 = {P1, P2, P3} with centroid (1.33, 1.33) and C2 = {P4, P5, P6} with centroid (6.33, 6). The total SSE is 4. Although both initial centroids lay in the same natural group, the algorithm recovered the two natural groups here.
4 Explain the bisecting K-means algorithm. How does it overcome the initialization problem of basic K-means, and how is it related to hierarchical clustering? 10 marks
Bisecting K-means extends basic K-means. To get K clusters, it starts with all points in one cluster and repeatedly splits one chosen cluster into two using K-means with K = 2, until K clusters exist.
1. Algorithm
1. Initialise the list of clusters with one cluster containing all points.
2. repeat
3. Remove a cluster from the list of clusters.
4. for i = 1 to number_of_trials do
5. Bisect the selected cluster using basic K-means (K = 2).
6. end for
7. Select the pair of clusters from the bisection with the lowest total SSE.
8. Add these two clusters to the list of clusters.
9. until the list contains K clusters2. Choosing which cluster to split
- Split the largest cluster.
- Split the cluster with the largest SSE.
- Use a rule that combines size and SSE.
Different choices give different final clusters.
3. Illustration Take the points (1,1), (2,1), (1,2), (6,5), (7,6), (6,7) with K = 3.
- First bisection: {(1,1), (2,1), (1,2)} with SSE 4/3, and {(6,5), (7,6), (6,7)} with SSE 8/3.
- The second cluster has the larger SSE, so it is bisected next.
- Splitting off (6,5) leaves {(7,6), (6,7)}. Its centroid is (6.5, 6.5) and its SSE is 0.5 + 0.5 = 1, so the split has total SSE 1.
- Splitting off (6,7) leaves {(6,5), (7,6)}, which also gives total SSE 1.
- Splitting off (7,6) leaves {(6,5), (6,7)}, which gives SSE 2.
- One of the two splits with SSE 1 is kept, and the result has three clusters.
4. Why it is less sensitive to initialization
- Each step solves only a two-cluster problem, and several trial bisections are tried, keeping the one with the lowest SSE.
- So a poor random start affects only one split, not the whole clustering.
- Because many trials run on smaller subsets, it is also efficient.
5. Refinement Each bisection is locally optimal, but the final set of K clusters need not be a local minimum of total SSE. A common step is to use the bisecting centroids as initial centroids for one run of basic K-means.
6. Relation to hierarchical clustering Recording the sequence of splits gives a hierarchy: the full data set at the root, and each bisection creating two children. This is a divisive hierarchical clustering. Any level of the tree can be cut to obtain a desired number of clusters.
Conclusion: bisecting K-means keeps the efficiency of K-means and reduces its dependence on initial centroids. It also gives a divisive hierarchy as a by-product.
5 Explain the basic agglomerative hierarchical clustering algorithm. Apply single-link (MIN) clustering to the five points A, B, C, D, E with distances d(A,B)=2, d(A,C)=6, d(A,D)=10, d(A,E)=9, d(B,C)=5, d(B,D)=9, d(B,E)=8, d(C,D)=4, d(C,E)=5, d(D,E)=3, and describe the dendrogram. 10 marks
Agglomerative hierarchical clustering starts with every point as a singleton cluster. At each step it merges the two closest clusters, until one cluster remains. The result is a dendrogram showing the merge order and merge distances.
1. Basic algorithm
1. Compute the proximity matrix, if necessary.
2. repeat
3. Merge the closest two clusters.
4. Update the proximity matrix for the new cluster.
5. until only one cluster remains2. Defining proximity between clusters
- MIN (single link): the smallest distance between points of the two clusters.
- MAX (complete link): the largest distance between points of the two clusters.
- Group average: the average of all pairwise distances.
- Ward's method: the increase in SSE caused by merging.
- Centroid distance: the distance between cluster centroids.
3. Single-link worked example
Step 1: The smallest distance is d(A,B) = 2, so A and B merge.
- d(AB,C) = min(6,5) = 5
- d(AB,D) = min(10,9) = 9
- d(AB,E) = min(9,8) = 8
- Unchanged: d(C,D) = 4, d(C,E) = 5, d(D,E) = 3
Step 2: The smallest distance is d(D,E) = 3, so D and E merge.
- d(DE,AB) = min(9,8) = 8
- d(DE,C) = min(4,5) = 4
- d(AB,C) = 5
Step 3: The smallest distance is d(DE,C) = 4, giving {C,D,E}.
- d(CDE,AB) = min(5,8) = 5
Step 4: {A,B} and {C,D,E} merge at distance 5, giving one cluster.
Merge sequence: {A,B} at 2, {D,E} at 3, {C,D,E} at 4, all points at 5.
4. Dendrogram in words Place the leaves A, B, C, D, E on the horizontal axis and distance on the vertical axis.
- A and B join at height 2.
- D and E join at height 3.
- C joins the D–E branch at height 4.
- The two branches join at height 5.
Cutting the tree between heights 4 and 5 gives two clusters, {A,B} and {C,D,E}.
5. Key issues
- Complexity: O(m²) space for the proximity matrix and O(m³) time in the basic version, or O(m² log m) with sorted lists or heaps.
- Merges are final: a wrong early merge can never be undone.
- There is no global objective function. Each merge is a local decision.
- Single link handles non-elliptical shapes but is sensitive to noise and chaining. Complete link is less sensitive to noise but tends to break large clusters.
Conclusion: agglomerative clustering gives a full hierarchy without fixing K in advance. Its cost and its irreversible merges limit it to moderate-sized data.
6 Explain the density-based approach of DBSCAN. Write the DBSCAN algorithm, illustrate it with an example, and discuss its strengths and weaknesses. 10 marks
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) finds clusters as dense regions separated by sparse regions. It uses the centre-based notion of density: the density of a point is the number of points within radius Eps of it, counting the point itself.
1. Classification of points (parameters Eps and MinPts)
- Core point: has at least MinPts points within Eps. These points lie in the interior of a cluster.
- Border point: not a core point, but within Eps of some core point.
- Noise point: neither core nor border.
2. Algorithm
1. Label every point as core, border or noise.
2. Eliminate noise points.
3. Put an edge between all core points within Eps of each other.
4. Make each connected group of core points a separate cluster.
5. Assign each border point to the cluster of one of its associated core points.The number of clusters is found automatically. Time is O(m²) in general, or about O(m log m) with spatial indexes in low dimensions. Space is O(m).
3. Example Take the one-dimensional points 1, 2, 3, 4, 10, 11, 12, 25 with Eps = 1 and MinPts = 3.
Neighbourhood counts:
- Point 1: {1,2} = 2 points
- Point 2: {1,2,3} = 3 points, so core
- Point 3: {2,3,4} = 3 points, so core
- Point 4: {3,4} = 2 points
- Point 10: {10,11} = 2 points
- Point 11: {10,11,12} = 3 points, so core
- Point 12: {11,12} = 2 points
- Point 25: {25} = 1 point
Labels:
- Points 1 and 4 are border points, near cores 2 and 3.
- Points 10 and 12 are border points of core 11.
- Point 25 is noise.
Result: Cluster 1 = {1,2,3,4}, Cluster 2 = {10,11,12}, and point 25 is discarded as noise.
4. Choosing Eps and MinPts For each point, compute the distance to its k-th nearest neighbour (k-dist), sort these values and plot them. Choose Eps at the sharp rise in the curve, with MinPts = k (often 4 for two-dimensional data).
5. Strengths
- Resistant to noise, which it labels explicitly.
- Finds clusters of arbitrary shape and size that K-means cannot.
- Does not need the number of clusters in advance.
6. Weaknesses
- Has trouble when cluster densities vary widely, because one Eps cannot suit all clusters.
- Struggles with high-dimensional data, where density is hard to define.
- Neighbourhood computation can be expensive.
- Results are sensitive to Eps and MinPts.
Conclusion: DBSCAN is a simple and effective density-based method for irregularly shaped clusters with noise. Its parameters must be chosen carefully, and it suits data of roughly uniform cluster density.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Data Mining: Concepts and Techniques · Jiawei Han, Micheline Kamber
- Introduction to Data Mining · Pang-Ning Tan, Michael Steinbach and Vipin Kumar
- Data Mining · Vikram Pudi and P. Radha Krishna
- Data Mining Techniques · Arun K. Pujari