2023 question paper

Data Mining

29 questions

1. Q1(a). Data about data is called (i) table (ii) database (iii) metadata (iv) integration20232m

   Module 1: Data Warehousing and Business Analysis

   Data about data is called

   (i) table
   (ii) database
   (iii) metadata
   (iv) integration

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) metadata

   Metadata is 'data about data': it describes the structure, origin, format, quality and other attributes of the actual data — for example a schema or table definition in a data dictionary, the data type and length of a column, a file's author and creation date, or the number of rows in a relation.

   A table is only the physical structure that stores the data, and a database is an organised collection of that data — neither of them describes the data. Integration is a preprocessing step that merges data from several sources, so it is a process rather than descriptive information about data. Hence only (iii) fits.

2. Q1(b). Which of the following frequent pattern mining technique generates the minimum number of candidate item sets? (i) Partitioning (ii) Apriori (iii) FP-growth (iv) Dynamic itemset counting20232m

   Module 2: Data Mining Fundamentals and Association Rule Mining

   Which of the following frequent pattern mining technique generates the minimum number of candidate item sets?

   (i) Partitioning
   (ii) Apriori
   (iii) FP-growth
   (iv) Dynamic itemset counting

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) FP-growth

   FP-growth mines frequent patterns by first compressing the transaction database into a compact FP-tree (frequent-pattern tree) and then mining that tree with a divide-and-conquer strategy. It never materialises any candidate itemsets at all, so the number of candidate itemsets generated is zero — the minimum possible for any frequent-pattern technique.

   Apriori is the natural comparison: at each level it joins the frequent (k-1)-itemsets to generate candidate k-itemsets and then prunes them, and this candidate generation is exactly the bottleneck FP-growth was designed to remove. Partitioning and dynamic itemset counting both follow the same Apriori-style generate-and-test paradigm, so they do generate candidate itemsets. Hence (iii) is correct.

3. Q1(c). If no hierarchy is associated with an n-dimensional data cube, how many cuboids would there be? (i) n³ (ii) n (iii) 2ⁿ (iv) n²20232m

   Module 1: Data Warehousing and Business Analysis

   If no hierarchy is associated with an n-dimensional data cube, how many cuboids would there be?

   (i) n³
   (ii) n
   (iii) 2ⁿ
   (iv) n²

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) 2ⁿ

   With no hierarchy associated with any dimension, each of the n dimensions can appear either in its base level or be fully aggregated away. The cuboids of the cube therefore correspond one-to-one with the subsets of the n dimensions, and the number of subsets of an n-element set is $2^n$. This includes the base cuboid (all n dimensions present) and the apex cuboid (no dimensions, i.e. the empty subset), with $\binom{n}{k}$ cuboids containing exactly k dimensions.

   The options n³, n and n² are not powers of two and cannot count $2^n$ subsets, so they are incorrect.

4. Q1(d). CLARANS stands for (i) Clustering Large Application based on RANdomized Search (ii) Clustering Least Application based on RANdomized Sorting (iii) Clustering Labelled Application based on RANdomized Search (iv) None of the above20232m

   Module 4: Cluster Analysis

   CLARANS stands for

   (i) Clustering Large Application based on RANdomized Search
   (ii) Clustering Least Application based on RANdomized Sorting
   (iii) Clustering Labelled Application based on RANdomized Search
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Clustering Large Application based on RANdomized Search

   CLARANS is a medoid-based clustering algorithm for large datasets. Instead of exhaustively scanning all neighbours of a medoid (as PAM does) or drawing random samples once (as CLARA does), it searches the neighbourhood graph of potential medoid sets using a randomised search, jumping to a random neighbour each time a better one is found. The name is the direct expansion of that idea: CLustering Large Applications based on RANdomized Search.

   Options (ii) and (iii) substitute incorrect words — 'Least ... Sorting' and 'Labelled ... Search' — neither of which belongs to the actual acronym. Because a correct expansion is given, 'None of the above' is also wrong.

5. Q1(e). Which of the following is required by K-means clustering? (i) Define distance metric (ii) Number of clusters (iii) Initial guess as to cluster centroids (iv) All of the above20232m

   Module 4: Cluster Analysis

   Which of the following is required by K-means clustering?

   (i) Define distance metric
   (ii) Number of clusters
   (iii) Initial guess as to cluster centroids
   (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) All of the above

   K-means requires all three inputs before it can run: (i) a distance metric (usually Euclidean) to decide which centroid a point is closest to and to compute within-cluster error; (ii) the number of clusters k, which must be supplied by the user because the algorithm has no way of discovering it; and (iii) an initial guess of the cluster centroids (seed points), which the algorithm then refines by alternating the assignment and update steps.

   Since (i), (ii) and (iii) are each genuinely required, no single one of them is the answer — 'All of the above' is correct.

6. Q1(f). DENCLUE clustering method is of type (i) Partitioning (ii) Hierarchical (iii) Density based (iv) Grid based20232m

   Module 4: Cluster Analysis

   DENCLUE clustering method is of type

   (i) Partitioning
   (ii) Hierarchical
   (iii) Density based
   (iv) Grid based

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Density based

   DENCLUE (DEnsity-based CLUstEring) models the overall density of a dataset as a superposition of kernel density functions ('influence functions') contributed by every data point, and then climbs the gradient of this density surface to reach density attractors. Points sharing an attractor form a cluster, so clusters are simply high-density regions separated by low-density regions — the defining property of density-based clustering.

   It is not partitioning (it does not split data into k given groups), not hierarchical (it builds no dendrogram), and not grid-based (it does not quantise the space into grid cells). Hence (iii).

7. Q1(g). Cluster is (i) Group of similar objects that differ significantly from other objects (ii) Operations on a database to transform or simplify data in order to prepare it for a machine learning algorithm (iii) Symbolic representation of facts or ideas from which information can potentially be extracted (iv) None of the above20232m

   Module 4: Cluster Analysis

   Cluster is

   (i) Group of similar objects that differ significantly from other objects
   (ii) Operations on a database to transform or simplify data in order to prepare it for a machine learning algorithm
   (iii) Symbolic representation of facts or ideas from which information can potentially be extracted
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Group of similar objects that differ significantly from other objects

   A cluster is defined by intra-cluster similarity and inter-cluster dissimilarity: its members are alike with respect to the attributes of interest, while being distinctly different from objects belonging to other clusters. This is the standard working definition used in cluster analysis.

   Option (ii) describes data preprocessing (transforming or simplifying data before learning), and option (iii) describes a knowledge or idea representation from which information is extracted — neither is a cluster. Since (i) is a correct definition, 'None of the above' is wrong as well.

8. Q1(h). An oblique tree is relevant when (i) The attributes are correlated (ii) The attributes are independent (iii) There are only two attributes (iv) All attributes are categorical20232m

   Module 3: Classification and Prediction

   An oblique tree is relevant when

   (i) The attributes are correlated
   (ii) The attributes are independent
   (iii) There are only two attributes
   (iv) All attributes are categorical

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) The attributes are correlated

   An ordinary decision tree can only make axis-parallel splits of the form $A \le v$ on a single attribute. An oblique tree instead splits a node on a linear combination of several attributes, e.g. $w_1A_1 + w_2A_2 + \dots + w_nA_n \le c$, which produces an oblique (non-axis-parallel) decision boundary in attribute space.

   Such a split is useful precisely when the attributes are correlated, because the classes then cannot be separated cleanly by one axis-aligned cut; a linear combination captures the joint effect. If attributes are independent, a simple single-attribute split already works. Two attributes or all-categorical attributes are handled perfectly well by ordinary trees, so (iii) and (iv) are not the reason for using an oblique tree.

9. Q1(i). ________ is an example of predictive type of data mining whereas ________ is an example of descriptive type of data mining. (i) Association Rule, Clustering (ii) Association Rule, Classification (iii) Classification, Clustering (iv) Clustering, Classification20232m

   Module 3: Classification and Prediction

   ________ is an example of predictive type of data mining whereas ________ is an example of descriptive type of data mining.

   (i) Association Rule, Clustering
   (ii) Association Rule, Classification
   (iii) Classification, Clustering
   (iv) Clustering, Classification

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Classification, Clustering

   Predictive data mining builds a model that predicts a target (labelled) attribute for new or unseen cases, and classification does exactly that: it learns a model from labelled training data and assigns class labels to future records. Descriptive data mining discovers patterns with no target variable to predict; clustering groups objects purely by their inherent similarity in unlabelled data, so it is descriptive.

   Association rule mining (e.g. Apriori over market-basket data) is also a descriptive technique, not a predictive one, so options (i) and (ii) are wrong; option (iv) simply reverses the two roles.

10. Q1(j). Classification is an example of ______ learning whereas clustering is an example of ______ learning. (i) Supervised, Unsupervised (ii) Unsupervised, Supervised (iii) Machine, Supervised (iv) Supervised, Machine20232m

    Module 3: Classification and Prediction

    Classification is an example of ______ learning whereas clustering is an example of ______ learning.

    (i) Supervised, Unsupervised
    (ii) Unsupervised, Supervised
    (iii) Machine, Supervised
    (iv) Supervised, Machine

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (i) Supervised, Unsupervised

    Classification learns from data in which the class label of every example is already known — a 'supervisor' supplies the correct output that the model is trained to reproduce — so it is supervised learning. Clustering receives unlabelled data and must discover the group structure on its own, with no target output to guide it, so it is unsupervised learning.

    Option (ii) swaps the two. Options (iii) and (iv) are wrong because machine learning is the umbrella category that contains both supervised and unsupervised learning, not the counterpart of supervised learning.

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2(a). Introduce the idea of Data Mining with example(s). What are the steps involved in Knowledge discovery in Database (KDD) process?20237m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Introduce the idea of Data Mining with example(s). What are the steps involved in Knowledge discovery in Database (KDD) process?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Data Mining and the KDD Process

    Definition. Data mining is the task of discovering valid, novel, potentially useful and ultimately understandable patterns — models, rules, clusters, associations — from large volumes of data. It sits at the intersection of database systems, statistics and machine learning, turning stored data into knowledge that supports decision making. A pattern counts as knowledge only if it is previously unknown, holds on new data, and is useful to the user; mining is not a random hunt for anything unusual.

    Examples

    • A supermarket mines point-of-sale baskets and finds the rule {bread, butter} -> milk with, say, support 8% and confidence 70%, which guides shelf placement and bundle offers.
    • A bank mines card transaction histories to flag fraud by matching each transaction against the customer's normal spending profile.
    • A telecom operator clusters customers by usage patterns to design targeted tariff plans.

    Steps in the KDD Process

    Knowledge Discovery in Databases (KDD) is the overall, iterative procedure for converting raw data into usable knowledge; data mining is the single step inside it that extracts the patterns. The standard steps are:

    1. Data cleaning — remove noise and inconsistent records (missing values, duplicates, wrong entries).
    2. Data integration — combine data from multiple databases, files or schemas into a coherent store.
    3. Data selection — retrieve only the data relevant to the analysis task.
    4. Data transformation — normalise, aggregate, summarise and discretise into forms suitable for mining.
    5. Data mining — apply intelligent methods (classification, clustering, association rule mining, regression, etc.) to extract patterns.
    6. Pattern evaluation — identify genuinely interesting, valid and useful patterns using objective measures (support, confidence, accuracy) together with domain knowledge.
    7. Knowledge presentation — present the mined knowledge through visualisation, graphs, reports, queries or rules.

    Raw data -> Cleaning -> Integration -> Selection -> Transformation
                                                            |
    Knowledge <- Evaluation <- Data mining <----------------+
    

    Because any step may expose problems that send the process back to an earlier step, KDD is a loop rather than a one-pass pipeline.

13. Q2(b). Explain the process of mining the world wide web. Compare Web mining with data mining.20237m

    Module 5: Mining Object, Spatial, Multimedia, Text and Web Data

    Explain the process of mining the world wide web. Compare Web mining with data mining.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Mining the World Wide Web

    Definition. Web mining is the automatic discovery of useful patterns and knowledge from web documents, from the link structure of the web, and from the records of how users interact with web sites. Because the web is a huge, distributed, semi-structured and constantly changing hypertext repository, ordinary data mining techniques are adapted to work on HTML/XML text, hyperlink graphs and server or clickstream data.

    Types / Process of Web Mining

    1. Web content mining — mines the actual content of pages: text, images, audio, metadata and embedded tables. It uses text categorisation, information extraction, wrapper induction and document clustering, and can work either on the raw pages or on the result sets returned by search engines.
    2. Web structure mining — mines the hyperlink structure to evaluate importance and relatedness of pages. PageRank, the hub-and-authority (HITS) model and discovery of web communities are the standard examples.
    3. Web usage mining — mines user-interaction data such as server/access logs, clickstreams, cookies and registration data. The process is:
       • Data collection — gather server logs, proxy logs, client-side records.
       • Data preprocessing — clean the logs, identify users and sessions, reconstruct visit sequences.
       • Pattern discovery — apply clustering, association rules and sequential pattern mining.
       • Pattern analysis — extract actionable knowledge for personalisation, recommendation and site redesign.

    Web Mining vs Data Mining

    Basis	Data mining	Web mining
    Source	Centralised databases / data warehouses	Distributed web pages, links and logs
    Data type	Mostly structured tuples and attributes	Semi-structured / unstructured HTML, XML, text, images, clickstreams
    Data quality	Curated, consistent, pre-processed	Noisy, redundant, inconsistent formats, missing values
    Schema	Fixed and known in advance	No global schema; structure must be extracted
    Scale and change	Relatively static	Extremely large and continuously updated
    Relationships	Foreign keys and explicit relations	Hyperlinks, page hierarchy, user sessions
    Goal	Hidden patterns, rules, clusters, models	Page relevance, site structure, user behaviour, personalisation

    In short, web mining is data mining applied to web-derived data, but it must additionally cope with hyperlink structure, unstructured text and highly dynamic, noisy content.

14. Q3(a). Explain DBSCAN briefly.20237m

    Module 4: Cluster Analysis

    Explain DBSCAN briefly.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

    Definition. DBSCAN is a density-based clustering algorithm that groups together points lying in densely populated regions of the data space and marks points lying in sparse regions as noise. Unlike K-means it does not require the number of clusters, it can discover clusters of arbitrary shape, and it handles outliers explicitly.

    Key concepts

    The algorithm takes two parameters:

    • ε (eps) — the radius of a point's neighbourhood, $N_\varepsilon(p) = \{q \mid d(p,q) \le \varepsilon\}$.
    • MinPts — the minimum number of points required inside that neighbourhood.

    Every point is then classified as:

    1. Core point if $|N_\varepsilon(p)| \ge MinPts$.
    2. Border point if it lies within ε of a core point but has fewer than MinPts points in its own neighbourhood.
    3. Noise point if it is neither core nor border.

    A point is density-reachable from a core point if it falls inside that core point's ε-neighbourhood (directly or through a chain of core points). Two points are density-connected if both are density-reachable from some common core point. A cluster is a maximal set of density-connected points.

    Algorithm

    1. Label every point as unvisited.
    2. Pick an unvisited point p and compute $N_\varepsilon(p)$.
    3. If $|N_\varepsilon(p)| < MinPts$, label p as noise (it may be relabelled as a border point of a cluster formed later).
    4. Otherwise p is a core point: create a new cluster and grow it — insert every point of $N_\varepsilon(p)$; for each newly added point that is itself a core point, expand its neighbourhood too, continuing through the queue until no more core points are reachable.
    5. Mark all points added to a cluster as visited and repeat from step 2 until no unvisited points remain.

    repeat until no unvisited point is left:
        pick unvisited p, compute N_eps(p)
        |N_eps(p)| <  MinPts --> label p noise (may become border later)
        |N_eps(p)| >= MinPts --> p is a core point: open a new cluster,
                                 absorb N_eps(p), then expand through every
                                 density-reachable core point
    result: set of clusters + noise points
    

    Properties

    • Strengths: no need to pre-specify the number of clusters; finds arbitrarily shaped (non-convex) clusters; outliers are reported as noise instead of being forced into a cluster; with a spatial index the neighbourhood search costs about $O(n \log n)$.
    • Limitations: one global (ε, MinPts) pair must suit every cluster, so clusters of strongly differing densities are handled poorly; the result is sensitive to the choice of ε and MinPts; effectiveness drops on high-dimensional data, where distances become less meaningful.
15. Q3(b). What are the common methods for handling the problem of missing value and noisy data?20237m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    What are the common methods for handling the problem of missing value and noisy data?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Handling Missing Values and Noisy Data

    Both are core data cleaning operations, because models and rules mined from poor-quality input are unreliable. The two problems are distinct: a missing value is an absent attribute value, while noise is a random error or deviation in a measured variable.

    A. Methods for missing values

    1. Ignore the tuple — discard the record entirely. Acceptable only when the missing fraction is very small and records are processed one at a time; otherwise it introduces bias.
    2. Fill in manually — a domain expert supplies the value. Most accurate, but expensive, slow and subjective.
    3. Use a special value — record an explicit marker such as 'unknown' or '?', which is natural for categorical attributes.
    4. Use a central tendency value — substitute the attribute mean, median or mode. A refinement is to fill by class mean (e.g. average salary of the employee's own designation rather than the company-wide average).
    5. Predict the most probable value — infer the missing value from the remaining attributes using decision trees, linear regression or Bayesian reasoning. This is generally the most reliable automatic method.

    B. Methods for noisy data

    1. Binning — sort the values, partition them into equal-frequency bins, then smooth each value by its bin mean, its bin median, or by the bin boundaries (minimum or maximum of the bin). This is local, content-independent smoothing.
    2. Regression — fit a function (linear or multiple regression) to the data and smooth the values by fitting them to the regression line, which also absorbs some of the random variation.
    3. Clustering — detect and remove outliers; points that do not belong to any cluster or lie far from all cluster centroids are treated as noise and either corrected or discarded.
    4. Human inspection — plot the data and let an expert identify and correct obviously wrong values.

    Choosing a method

    Situation	Preferred method
    Very few incomplete records	Ignore the tuple
    Categorical attribute	Special 'unknown' value or the mode
    Numerical attribute, class label known	Class mean
    Other attributes informative about the missing one	Predict most probable value (regression / decision tree)
    Skewed numerical variable to be smoothed	Binning
    Isolate and remove outliers	Clustering
    Small dataset, high cost of error	Manual entry

    Applying these steps before mining substantially improves the accuracy, validity and credibility of the discovered patterns.

16. Q4(a). Build a decision tree using the training data in the table given below. Divide the height attribute into ranges as follows: [0, 1.6], \quad [1.6, 1.7], \quad [1.7, 1.8], \quad [1.8, 1.9], \quad [1.9, 2.0], \quad [2.0, 5.0] | Gender | Height (m) | Class | | :---: | :---: | :---: | | F | 1.6 | Short | | M | 2 | Tall | | F | 1.9 | Medium | | F | 1.88 | Medium | | F | 1.7 | Short | | M | 1.85 | Medium | | F | 1.6 | Short | | M | 1.7 | Short | | M | 2.2 | Tall | | M | 2.1 | Tall | | F | 1.8 | Medium | | M | 1.95 | Medium | | F | 1.9 | Medium | | F | 1.8 | Medium | | F | 1.75 | Medium |20237m

    Module 3: Classification and Prediction

    Build a decision tree using the training data in the table given below. Divide the height attribute into ranges as follows:

    $$[0, 1.6], \quad [1.6, 1.7], \quad [1.7, 1.8], \quad [1.8, 1.9], \quad [1.9, 2.0], \quad [2.0, 5.0]$$

    Gender	Height (m)	Class
    F	1.6	Short
    M	2	Tall
    F	1.9	Medium
    F	1.88	Medium
    F	1.7	Short
    M	1.85	Medium
    F	1.6	Short
    M	1.7	Short
    M	2.2	Tall
    M	2.1	Tall
    F	1.8	Medium
    M	1.95	Medium
    F	1.9	Medium
    F	1.8	Medium
    F	1.75	Medium

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Q4(a) - Building a Decision Tree (ID3, Information Gain)

    Method. At every node we test the attribute that yields the largest information gain, i.e. the largest reduction of entropy (class impurity):

    $$H(S)=-\sum_{i}p_i\log_2 p_i, \qquad Gain(S,A)=H(S)-\sum_{v\in Values(A)}\frac{|S_v|}{|S|}H(S_v)$$

    Height binning. A value lying exactly on a boundary is taken into the higher range, so the given ranges are read as $[0,1.6),[1.6,1.7),[1.7,1.8),[1.8,1.9),[1.9,2.0),[2.0,5.0]$. (With the opposite convention every range comes out pure and the tree is even shallower; the choice of the root attribute does not change.)

    Step 1 - Count tables (15 records)

    Class counts inside each height range:

    Height range	Short	Medium	Tall	Total
    $[0,1.6)$	0	0	0	0
    $[1.6,1.7)$	2	0	0	2
    $[1.7,1.8)$	2	1	0	3
    $[1.8,1.9)$	0	4	0	4
    $[1.9,2.0)$	0	3	0	3
    $[2.0,5.0]$	0	0	3	3
    Total	4	8	3	15

    Class counts by gender:

    Gender	Short	Medium	Tall	Total
    F	3	6	0	9
    M	1	2	3	6
    Total	4	8	3	15

    Step 2 - Entropy of the whole data set

    $$H(S)=-\frac{4}{15}\log_2\frac{4}{15}-\frac{8}{15}\log_2\frac{8}{15}-\frac{3}{15}\log_2\frac{3}{15}=0.5085+0.4837+0.4644=\mathbf{1.4566\ \text{bits}}$$

    Step 3 - Candidate splits

    (a) Height - multi-way split over the given ranges

    Only the range $[1.7,1.8)$ is impure (2 Short + 1 Medium):

    $$H([1.7,1.8))=-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}=0.3900+0.5283=0.9183$$

    All other non-empty ranges are pure, so their entropy is 0. Therefore

    $$Gain(\text{Height})=1.4566-\frac{3}{15}(0.9183)=1.4566-0.1837=\mathbf{1.2729}$$

    (b) Gender - two-way split

    $$H(F)=-\frac{3}{9}\log_2\frac{3}{9}-\frac{6}{9}\log_2\frac{6}{9}=0.5283+0.3900=0.9183$$

    $$H(M)=-\frac{1}{6}\log_2\frac{1}{6}-\frac{2}{6}\log_2\frac{2}{6}-\frac{3}{6}\log_2\frac{3}{6}=0.4308+0.5283+0.5000=1.4591$$

    $$Gain(\text{Gender})=1.4566-\left(\frac{9}{15}\times0.9183+\frac{6}{15}\times1.4591\right)=1.4566-1.1346=\mathbf{0.3219}$$

    (c) Binary threshold splits on height (cross-check)

    Split	Left class counts (S, M, T)	Right class counts (S, M, T)	Gain
    height < 1.7	(2, 0, 0)	(2, 8, 3)	0.300
    height < 1.8	(4, 1, 0)	(0, 7, 3)	0.628
    height < 1.9	(4, 5, 0)	(0, 3, 3)	0.462
    height < 2.0	(4, 8, 0)	(0, 0, 3)	0.722

    Root = Height, because 1.2729 is by far the largest gain (Gender gives only 0.3219).

    Step 4 - Grow each branch

    • $[0,1.6)$ - no records, ignored.
    • $[1.6,1.7)$ - 2 Short, already pure, so leaf = Short.
    • $[1.7,1.8)$ - 2 Short + 1 Medium, so split with the remaining attribute Gender:
      • F gives 1 Short (1.70 m) and 1 Medium (1.75 m): a 1-1 tie, entropy 1.0.
      • M gives one record (1.70 m, Short): pure, leaf = Short.
      • Split gain $=0.9183-\big(\frac{2}{3}\times1+\frac{1}{3}\times0\big)=0.2516>0$, so the split is justified.
    • $[1.8,1.9)$ - 4 Medium, pure, leaf = Medium.
    • $[1.9,2.0)$ - 3 Medium, pure, leaf = Medium.
    • $[2.0,5.0]$ - 3 Tall, pure, leaf = Tall.

    Final decision tree

                              [ Height ]
        +-----------+-----------+-------------+------------+------------+------------+
     [0,1.6)    [1.6,1.7)   [1.7,1.8)     [1.8,1.9)   [1.9,2.0)   [2.0,5.0]
      empty        Short        Gender         Medium      Medium       Tall
                                  |
                     +------------+------------+
                     F                        M
                 Short *                    Short
             (1 Short, 1 Medium)
    

    Resulting classification rules

    1. Height $\in[2.0,5.0]$ gives Tall
    2. Height $\in[1.8,2.0)$ gives Medium
    3. Height $\in[1.6,1.7)$ gives Short
    4. Height $\in[1.7,1.8)$ and Gender = M gives Short; Gender = F is a 1-1 tie broken by any fixed rule (e.g. Short)

    The tree classifies 14 of the 15 training records correctly (93%); the only ambiguity is the female pair inside $[1.7,1.8)$, which no available attribute can separate.

17. Q4(b). What is over-fitting and under-fitting of a model? When do they happen?20237m

    Module 3: Classification and Prediction

    What is over-fitting and under-fitting of a model? When do they happen?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Over-fitting and Under-fitting of a Model

    1. Definitions

    • Over-fitting: the model learns the training data too well. Besides the true underlying pattern it also memorises the random noise, outliers and accidental regularities peculiar to that sample. It gives an extremely low (often zero) error on the training data but a large error on unseen data, i.e. it fails to generalise.
    • Under-fitting: the model is too simple to capture the structure present in the data. It does not learn even the training relationship, so it has high error both on the training set and on the test set. Such a model has high bias.

    2. When do they happen?

    Over-fitting occurs when:

    1. The model is far too complex for the amount of data - e.g. a fully grown, unpruned decision tree that creates one leaf per record, a very high-degree polynomial, or a neural network with far more parameters than samples.
    2. Training continues too long, or the same data is reused with constant hyper-parameter tuning (the test data is indirectly used for training).
    3. The training data is small, noisy, unrepresentative or contains outliers that the model tries to explain.
    4. No validation, pruning or regularisation is used.

    Under-fitting occurs when:

    1. The model is too simple to represent the data - e.g. a decision stump, a linear model fitted to clearly non-linear data, a tree with too few levels.
    2. Too few or uninformative features are used, or useful features are discarded.
    3. Training stops too early (premature stopping), or the regularisation strength is set too high.
    4. The learning algorithm itself cannot express the true relationship (a high-bias model).

    3. Bias-variance view

    	Over-fitting	Under-fitting
    Model complexity	Too high	Too low
    Training error	Very low	High
    Test / validation error	High	High
    Bias	Low	High
    Variance	High (sensitive to the data)	Low
    Typical cause	Too much flexibility, too little data	Too little flexibility

    Total prediction error = Bias + Variance + irreducible noise; the goal is the sweet spot where this sum is minimum.

     Error
      |  \___                     __--  training error
      |      \____          ____--
      |           \____--~~     gap between the two curves
      |            ^   ^          = over-fitting
      |            |   validation error
      +------------+--------------------------------> Model complexity
              under-fitted   good fit     over-fitted
    

    4. Detection and control

    • Detect: split the data into training and validation sets (k-fold cross-validation) and compare the two error curves; plot a learning curve (error vs. amount of training data).
    • Cure over-fitting: collect more training data, post-pruning / pre-pruning of the tree, regularisation, dropout and early stopping, feature selection, ensemble methods such as bagging and random forests, or a simpler model.
    • Cure under-fitting: use a richer model, add better features, train longer, reduce regularisation.
18. Q5(a). Define with suitable examples of each of the following data mining functionalities: * data characterization * data association * data discrimination20237m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Define with suitable examples of each of the following data mining functionalities:

    • data characterization
    • data association
    • data discrimination

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Data Mining Functionalities: Characterization, Association and Discrimination

    Data-mining functionalities define the kind of patterns a system can discover. Three important ones are:

    1. Data characterization

    Definition. Data characterization is an automatic summarisation of the general characteristics of a target class of data - the class the user is interested in - drawn from a data set, usually at several abstraction levels.

    How it is done: statistical description (count, mean, median, variance), attribute-oriented induction, OLAP roll-up / drill-down on a data cube, or decision-tree induction in which the tree itself is the profile of the class.

    Example: a supermarket wants to characterize customers who buy a baby product. The result may read: 80% of these buyers are aged 30-45, 70% shop on weekends and their average bill is Rs. 1,200. This profile supports targeted marketing. Only one class is involved.

    2. Data association

    Definition. Data association (association rule mining / correlation analysis) discovers interesting associations, correlations, frequent patterns and causal structures among items or attributes in large data sets, without any class label.

    Measurements: support and confidence, found by algorithms such as Apriori and FP-growth.

    Example - market basket analysis:

    $$\{Bread, Butter\} \Rightarrow \{Milk\} \quad (support = 60\%,\ confidence = 100\%)$$

    Other examples: the classic diapers and beer rule, web click-stream association (users who open page A also open page B), and correlation between hot weather and soft-drink sales.

    3. Data discrimination

    Definition. Data discrimination builds a description (discriminant rules) that distinguishes a target class from a contrasting (background) class. It compares the two rather than describing only one.

    How it is done: comparison of attribute distributions (box plots, histograms), decision-tree induction on both classes, or statistical significance tests.

    Example: in a bank, discriminate good credit-risk customers (target) from bad credit-risk customers (contrast): good-risk customers are usually salaried, aged 30-50, with a debt-to-income ratio below 0.3. Other examples: heavy users vs. light users of a product, buyers vs. non-buyers of a car.

    Quick comparison

    Functionality	Classes involved	Output	Example
    Data characterization	One target class	Profile / summary	Summarize festival shoppers
    Data association	None (item to item)	Frequent patterns / rules	Bread + Butter -> Milk
    Data discrimination	Target vs. contrast	Discriminant rules	Good vs. bad credit risk

19. Q5(b). What do you mean by entropy? Explain it in the light of information gain.20237m

    Module 3: Classification and Prediction

    What do you mean by entropy? Explain it in the light of information gain.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Entropy and Information Gain

    1. Entropy

    Entropy is a measure of impurity, disorder or uncertainty of a data set $S$ with respect to its class labels. For a data set that contains $c$ classes with probabilities $p_1, p_2, \dots, p_c$ (estimated as relative frequencies $p_i = |C_i|/|S|$):

    $$H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i$$

    Units: bits (base 2; base $e$ gives nats).

    Properties:

    1. $0 \le H(S) \le \log_2 c$.
    2. $H(S) = 0$ when the set is pure (all records belong to one class) - no disorder.
    3. $H(S)$ is maximum when all classes are equally likely, i.e. $p_i = 1/c$, giving $H = \log_2 c$ (maximum uncertainty).
    4. Entropy depends only on the class distribution, not on which attribute is tested.

    2. Information gain

    Information gain of a test on attribute $A$ with values $v_1 \dots v_n$ is the reduction in entropy (uncertainty about the class) obtained by splitting $S$ on $A$:

    $$Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$

    The second term is the weighted (expected) entropy after the split - the average impurity of the children, each child weighted by its share of the records. Hence

    $$Gain(S,A) = \text{impurity before the split} - \text{average impurity after the split}$$

    Interpretation. The larger the gain, the better the attribute separates the classes. The learning algorithm (ID3) at every node chooses the attribute with the maximum information gain; a gain of 0 means the attribute does not separate the classes at all, while a gain equal to $H(S)$ means the split produces perfectly pure children.

    3. Worked numeric example

    A set $S$ of 10 records has 6 positives and 4 negatives:

    $$H(S) = -\frac{6}{10}\log_2 0.6 - \frac{4}{10}\log_2 0.4 = 0.6(0.7370) + 0.4(1.3219) = \mathbf{0.9710\ bits}$$

    Attribute $A$ has two values:

    Branch	Records	Class mix	$H$ of branch
    $A = a_1$	5	5 Pos, 0 Neg	0
    $A = a_2$	5	1 Pos, 4 Neg	0.7219

    $$E(S,A) = \frac{5}{10}(0) + \frac{5}{10}(0.7219) = 0.3610$$

    $$Gain(S,A) = 0.9710 - 0.3610 = \mathbf{0.6100\ bits}$$

    So testing $A$ removes about 61% of the initial uncertainty. (For a second candidate attribute with a smaller gain, the algorithm would pick $A$.)

    4. Remarks used in exams

    • In the decision-tree problem of Q4(a), $H(S) = 1.4566$ bits, $Gain(\text{Height}) = 1.2729$ and $Gain(\text{Gender}) = 0.3219$, so Height is chosen at the root.
    • Gain ratio (C4.5) divides gain by the split information $-\sum \frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}$ to remove the bias towards attributes with many values.
    • Gini index (CART), $Gini = 1 - \sum p_i^2$, is an impurity measure equivalent in spirit to entropy.
20. Q6(a). Define data warehouse. What is the difference between OLAP and OLTP?20235m

    Module 1: Data Warehousing and Business Analysis

    Define data warehouse. What is the difference between OLAP and OLTP?

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Data Warehouse; OLAP vs. OLTP

    1. Definition of a data warehouse

    A data warehouse is a subject-oriented, integrated, time-variant and non-volatile collection of data in support of management's decision-making process.

    • Subject-oriented: organised around major subjects such as customer, product, sales rather than around applications or transactions.
    • Integrated: data from many heterogeneous sources (files, relational DBs, external feeds) are merged under a single schema with consistent naming, units and codes.
    • Time-variant: every attribute records the time period; the data covers a long historical period (years), unlike operational data which holds only the current value.
    • Non-volatile: once loaded, data are not updated or deleted - they are read-only, so historical data remain stable for analysis.

    It is built by ETL (extract, transform, load) from operational systems and organised as a data cube (fact and dimension tables) to support analytical queries.

    2. OLAP vs. OLTP

    Feature	OLTP (On-Line Transaction Processing)	OLAP (On-Line Analytical Processing)
    Purpose	Run day-to-day transactions (insert, update, delete)	Analysis, reporting and decision support
    Users	Clerks, operators, customers	Managers, analysts, executives
    Design	Application-oriented, ER / 3NF normalised schema	Subject-oriented, star / snowflake schema
    Operations	Simple, short read-write queries	Complex queries: roll-up, drill-down, slice, dice, pivot
    Data	Current, detailed, small volume per query	Historical, aggregated, very large volume
    Response time	Very fast (milliseconds), few records touched	Seconds to minutes, large portions of data scanned
    Query volume	Many concurrent short transactions	Fewer, long-running analytical queries
    Indexing	Heavy indexing for fast writes	Bitmap / join indexes for fast aggregation
    Failure impact	Affects business operations immediately	Affects reporting only

    In short: OLTP supports the operations of the organisation (current, fast, transactional), while OLAP supports the analysis of the organisation (historical, aggregated, multidimensional) over a data warehouse.

21. Q6(b). Discuss Star schema with suitable example.20234m

    Module 1: Data Warehousing and Business Analysis

    Discuss Star schema with suitable example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Star Schema (Data Warehouse)

    Definition. A star schema is the simplest dimensional-modelling scheme used to implement a data warehouse. It consists of one central fact table, which stores the business measures (numeric facts) plus foreign keys, and several dimension tables placed around it, which store the descriptive, contextual attributes. Because the fact table sits at the centre with the dimensions radiating out, the resulting ER diagram looks like a star.

    Example - retail sales warehouse

    • Fact table: Sales(Time_key, Product_key, Store_key, Promo_key, Quantity, Amount)
    • Dimensions: Time(Time_key, Date, Month, Quarter, Year), Product(Product_key, Name, Category, Brand), Store(Store_key, City, Region, Manager), Promo(Promo_key, Type, Discount)

                  Time
                   |
      Product --- Sales --- Store
                   |
                  Promo
    

    Key characteristics

    1. The fact table is large and narrow (keys + measures); dimension tables are small and fully denormalised.
    2. Queries need only a few simple joins (star-join optimisation), so performance is high and the structure is easy for business users to understand.
    3. Well suited to OLAP operations such as roll-up, drill-down, slice and dice.
    4. The snowflake schema is the normalised variant in which dimension hierarchies are split into additional tables: it saves storage but adds joins and slows queries. Star schema is therefore preferred for performance and simplicity.
22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q6(c). In data warehouse technology explain ROLAP, MOLAP and HOLAP techniques of implementing a multidimensional view.20235m

    Module 1: Data Warehousing and Business Analysis

    In data warehouse technology explain ROLAP, MOLAP and HOLAP techniques of implementing a multidimensional view.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    ROLAP, MOLAP and HOLAP - Implementing the Multidimensional View

    These are the three techniques used to physically implement the multidimensional (data-cube) view of a data warehouse.

    1. ROLAP - Relational OLAP

    The multidimensional view is implemented on top of a relational database: facts and dimensions are stored as relational tables in a star or snowflake schema, and every OLAP operation (roll-up, drill-down, slice) is translated into SQL queries with GROUP BY.

    • Handles very large and even detail-level data (scales with the RDBMS).
    • Uses aggregate tables, BITMAP indexes and join indexes to speed queries.
    • No fully pre-computed cube, so complex aggregations are slower; dependent on SQL tuning.

    2. MOLAP - Multidimensional OLAP

    Data (including all pre-aggregated summaries) are stored in a specialised multidimensional array / cube structure, not in rows of a table.

    • Queries are extremely fast because aggregates are pre-computed and stored.
    • Sparse cubes waste storage; cube-building (ETL) takes time and the data volume that fits in memory is limited - less scalable than ROLAP.

    3. HOLAP - Hybrid OLAP

    Combines both: detailed (base) data remain in relational tables while the aggregates are stored in a MOLAP cube.

    • Drill-through to detail uses SQL on the relational store; summary queries are answered from the fast cube.
    • Best balance of storage, performance and scalability - a compromise of ROLAP and MOLAP.

    Comparison

    Parameter	ROLAP	MOLAP	HOLAP
    Storage	Relational tables	Multidimensional arrays	Detail in RDBMS, aggregates in cube
    Data volume	Very large, detail-level	Moderate, summaries	Large detail + summaries
    Query speed	Slower for complex aggregation	Fastest (pre-computed)	Fast for summaries, slower for detail
    Pre-aggregation	Limited / none	Full	Aggregates only
    Scalability	Best	Limited by cube size	Good
    Best suited to	Huge detail data, ad-hoc SQL	Small-to-medium data needing speed	Enterprises needing both

24. Q7(a). Describe the principle of Partitioning technique for frequent itemset generation and justify how it improves the efficiency of frequent itemset generation compared to a priori algorithm.20235m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Describe the principle of Partitioning technique for frequent itemset generation and justify how it improves the efficiency of frequent itemset generation compared to a priori algorithm.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Partitioning Technique for Frequent Itemset Generation

    1. Principle

    The partition algorithm (Savasere, Omiecinski and Navathe) avoids the repeated database scans of Apriori by splitting the database into pieces that fit in main memory and scanning the data only twice.

    Phase 1 - local mining (one pass, partition by partition):

    1. Divide the transaction database $D$ into $n$ non-overlapping partitions $D_1, D_2, \dots, D_n$, each small enough to fit in memory.
    2. In each partition $D_i$, find the itemsets whose support in that partition is at least $minsup \times |D_i|$ (using Apriori or a hash tree, entirely in memory).
    3. Take the union of all locally frequent itemsets as the candidate set $C^*$ for Phase 2.

    Why no globally frequent itemset is missed: if an itemset $X$ were infrequent in every partition, then

    $$count_i(X) < minsup \cdot |D_i| \ \ \forall i \ \Longrightarrow \ \sum_i count_i(X) < minsup \cdot \sum_i |D_i| = minsup \cdot |D|$$

    so $X$ would also be globally infrequent. Contrapositively, every globally frequent itemset must be frequent in at least one partition - Phase 1 cannot drop a true frequent itemset (no false negatives).

    Phase 2 - global counting (one single pass over the whole DB): scan $D$ once, count the support of each candidate in $C^*$, and keep only those whose total support is at least $minsup \times |D|$. These are the globally frequent itemsets.

    Partition the database D into D1, D2, ..., Dn
    for each partition Di:
        find locally frequent itemsets (support >= minsup * |Di|)
        C* = union of all locally frequent itemsets
    scan the whole database once:
        count support of every candidate in C*
        L = { X in C* : support(X) >= minsup * |D| }
    

    2. Why it is more efficient than the Apriori algorithm

    1. Only two passes over the data, no matter how long the frequent itemsets are; Apriori needs one full scan per level ($k+1$ scans for itemsets of size $k$) plus candidate generation/pruning at every level.
    2. Phase 1 works in memory on a small partition, so expensive candidate-set handling and repeated disk I/O of the whole database are avoided.
    3. Parallelism and scalability: partitions can be processed simultaneously on different processors, and a database larger than memory can be handled because only one partition is resident at a time.
    4. Candidate set $C^*$ is generally much smaller than the level-wise candidate set of Apriori, so the single counting pass in Phase 2 is cheap.

    Trade-off: the union of local frequent itemsets may contain a few globally infrequent itemsets (false positives), which Phase 2 filters out; this is a small price for cutting the number of full database scans from many to two.

25. Q7(b). Consider the 5 transactions given below. If minimum support is 30% and minimum confidence is 80% determine the frequent itemsets and association rules using apriori algorithm. | Transaction | Items | | :---: | --- | | T1 | Bread, Jelly, Butter | | T2 | Bread, Butter | | T3 | Bread, Milk, Butter | | T4 | Coke, Bread | | T5 | Coke, Milk |20239m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Consider the 5 transactions given below. If minimum support is 30% and minimum confidence is 80% determine the frequent itemsets and association rules using apriori algorithm.

    Transaction	Items
    T1	Bread, Jelly, Butter
    T2	Bread, Butter
    T3	Bread, Milk, Butter
    T4	Coke, Bread
    T5	Coke, Milk

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Q7(b) - Frequent Itemsets and Association Rules by the Apriori Algorithm

    Given: 5 transactions, minimum support = 30%, minimum confidence = 80%.

    $$minsup\ count = 30\% \ \text{of} \ 5 = 0.30 \times 5 = 1.5 \ \Rightarrow \ an\ itemset\ must\ occur\ in\ \ge 2\ transactions$$

    Abbreviations: Bread = B, Butter = Bu, Milk = M, Coke = C, Jelly = J.

    TID	Items
    T1	Bread, Jelly, Butter
    T2	Bread, Butter
    T3	Bread, Milk, Butter
    T4	Coke, Bread
    T5	Coke, Milk

    Step 1 - Scan 1: 1-itemsets

    Itemset	Transactions	Count	Support	Frequent?
    {Bread}	T1, T2, T3, T4	4	4/5 = 80%	Yes
    {Butter}	T1, T2, T3	3	3/5 = 60%	Yes
    {Milk}	T3, T5	2	2/5 = 40%	Yes
    {Coke}	T4, T5	2	2/5 = 40%	Yes
    {Jelly}	T1	1	1/5 = 20%	No (< 30%)

    $$L_1 = \{\{Bread\}:4,\ \{Butter\}:3,\ \{Milk\}:2,\ \{Coke\}:2\}$$

    Jelly is dropped, so no itemset containing Jelly can ever be frequent (Apriori property / downward closure).

    Step 2 - Scan 2: candidate 2-itemsets from $L_1$

    Candidate	Transactions	Count	Support	Frequent?
    {Bread, Butter}	T1, T2, T3	3	3/5 = 60%	Yes
    {Bread, Milk}	T3, T4	2	2/5 = 40%	Yes
    {Bread, Coke}	T4	1	1/5 = 20%	No
    {Butter, Milk}	T3	1	1/5 = 20%	No
    {Butter, Coke}	-	0	0%	No
    {Milk, Coke}	T5	1	1/5 = 20%	No

    $$L_2 = \{\{Bread, Butter\}:3,\ \{Bread, Milk\}:2\}$$

    Step 3 - Scan 3: 3-itemsets

    The only join candidate is {Bread, Butter, Milk}. Its subset {Butter, Milk} is not in $L_2$, so by the Apriori property the candidate is pruned and no scan is required.

    $$L_3 = \varnothing \quad \Rightarrow \quad \textbf{stop}$$

    All frequent itemsets

    Level	Frequent itemset	Support count	Support %
    1	{Bread}	4	80%
    1	{Butter}	3	60%
    1	{Milk}	2	40%
    1	{Coke}	2	40%
    2	{Bread, Butter}	3	60%
    2	{Bread, Milk}	2	40%

    Step 4 - Association rules (minimum confidence 80%)

    $$confidence(X \Rightarrow Y) = \frac{support(X \cup Y)}{support(X)}$$

    Rules are generated only from itemsets with two or more items:

    Rule	Confidence calculation	Confidence	Passes 80%?
    Bread $\Rightarrow$ Butter	3/4	75%	No
    Butter $\Rightarrow$ Bread	3/3	100%	Yes
    Bread $\Rightarrow$ Milk	2/4	50%	No
    Milk $\Rightarrow$ Bread	2/2	100%	Yes

    Result

    Frequent itemsets: {Bread} 80%, {Butter} 60%, {Milk} 40%, {Coke} 40%, {Bread, Butter} 60%, {Bread, Milk} 40%.

    Strong (valid) association rules with support $\ge$ 30% and confidence $\ge$ 80%:

    1. $\{Butter\} \Rightarrow \{Bread\}$ - support 60%, confidence 100%
    2. $\{Milk\} \Rightarrow \{Bread\}$ - support 40%, confidence 100%

    The other two candidate rules fail the 80% confidence test (75% and 50%), so they are rejected.

26. Q8(a). What is cluster analysis? How do we categorize the major clustering methods? Explain each in brief.20235m

    Module 4: Cluster Analysis

    What is cluster analysis? How do we categorize the major clustering methods? Explain each in brief.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cluster Analysis and the Major Clustering Methods

    1. What is cluster analysis?

    Cluster analysis (clustering) is the task of grouping a set of physical or abstract objects into classes (clusters) of similar objects, so that objects within a cluster are highly similar to one another and as dissimilar as possible to objects in other clusters. It is an unsupervised learning task - no class labels are supplied, and the grouping emerges from the data itself. Similarity is usually measured by distance functions such as Euclidean, Manhattan or cosine distance.

    Requirements of a good clustering algorithm: scalability to large data sets, ability to deal with different attribute types, minimal dependence on domain knowledge, discovery of clusters of arbitrary shape, robustness to noise and outliers, and interpretable results.

    2. Categorisation of major clustering methods

    Method	Representative algorithms	Key idea
    Partitioning	k-means, k-medoids (PAM), CLARANS	Build k partitions that minimise a cost function; clusters are spherical and described by prototypes (centroids)
    Hierarchical	AGNES, DIANA, BIRCH, CURE, CHAMELEON	Create a nested hierarchy (tree / dendrogram) of clusters, either bottom-up (agglomerative) or top-down (divisive)
    Density-based	DBSCAN, OPTICS, DenCLUE	A cluster is a continuous region of high point density separated by regions of low density; finds arbitrary shapes and marks noise
    Grid-based	STING, CLIQUE, WaveCluster	Quantise the object space into a finite number of cells on a grid and operate on the grid - very fast, resolution-dependent
    Model-based	EM (Gaussian mixtures), COBWEB, SOM	Assume a statistical or neural model for each cluster and fit the data to it (e.g. maximise likelihood)

    Brief explanation:

    1. Partitioning methods - start with a random or sampled set of k representatives and iteratively reassign points to the nearest representative until convergence (e.g. Lloyd's k-means). Fast and simple, but need k in advance and favour convex clusters.
    2. Hierarchical methods - produce a dendrogram that the analyst can cut at any level; no need to prespecify k, but merges/splits are irreversible and a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory.
    3. Density-based methods - grow clusters from dense seeds, so the number of clusters and the cluster shape are discovered automatically and noise is handled naturally.
    4. Grid-based methods - move the computation from individual objects to cells, giving constant-time complexity with respect to the number of data objects.
    5. Model-based methods - treat clusters as probability distributions or neural units, giving a principled statistical framework (but assuming a particular model form).
27. Q8(b). Suppose that the data mining task is to cluster the following eight points (with (x, y) representing location) into 3 clusters: A_1(2,10), A_2(2,5), A_3(8,4), B_1(5,8), B_2(7,5), B_3(6,4), C_1(1,2), C_2(4,9) The distance function is Euclidian distance. Initially we assign A_1, B_1 and C_1 as the center of each cluster. Use k-means algorithm to determine the three clusters.20239m

    Module 4: Cluster Analysis

    Suppose that the data mining task is to cluster the following eight points (with $(x, y)$ representing location) into 3 clusters:

    $$A_1(2,10), A_2(2,5), A_3(8,4), B_1(5,8), B_2(7,5), B_3(6,4), C_1(1,2), C_2(4,9)$$

    The distance function is Euclidian distance. Initially we assign $A_1$, $B_1$ and $C_1$ as the center of each cluster. Use k-means algorithm to determine the three clusters.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Q8(b) - K-means Clustering of the Eight Points

    Data: $A_1(2,10), A_2(2,5), A_3(8,4), B_1(5,8), B_2(7,5), B_3(6,4), C_1(1,2), C_2(4,9)$; $k = 3$; Euclidean distance $d(P,Q)=\sqrt{(x_P-x_Q)^2+(y_P-y_Q)^2}$; initial centres $A_1, B_1, C_1$.

    Algorithm: (1) assign every point to the nearest centre, (2) recompute each centre as the mean of its cluster, (3) repeat until no membership changes.

    Iteration 1 - centres $A_1(2,10)$, $B_1(5,8)$, $C_1(1,2)$

    Point	$d$ to $(2,10)$	$d$ to $(5,8)$	$d$ to $(1,2)$	Nearest
    $A_1(2,10)$	0.000	3.606	8.062	A
    $A_2(2,5)$	5.000	4.243	3.162	C
    $A_3(8,4)$	8.485	5.000	7.280	B
    $B_1(5,8)$	3.606	0.000	7.211	B
    $B_2(7,5)$	7.071	3.606	6.708	B
    $B_3(6,4)$	7.211	4.123	5.385	B
    $C_1(1,2)$	8.062	7.211	0.000	C
    $C_2(4,9)$	2.236	1.414	7.616	B

    Clusters after iteration 1

    • Cluster A = $\{A_1\}$, centre $= (2,10)$
    • Cluster B = $\{A_3, B_1, B_2, B_3, C_2\}$, centre $= \left(\frac{8+5+7+6+4}{5},\frac{4+8+5+4+9}{5}\right) = (6,6)$
    • Cluster C = $\{A_2, C_1\}$, centre $= \left(\frac{2+1}{2},\frac{5+2}{2}\right) = (1.5,3.5)$

    Iteration 2 - centres $(2,10)$, $(6,6)$, $(1.5,3.5)$

    Point	$d$ to $(2,10)$	$d$ to $(6,6)$	$d$ to $(1.5,3.5)$	Nearest
    $A_1(2,10)$	0.000	5.657	6.519	A
    $A_2(2,5)$	5.000	4.123	1.581	C
    $A_3(8,4)$	8.485	2.828	6.519	B
    $B_1(5,8)$	3.606	2.236	5.701	B
    $B_2(7,5)$	7.071	1.414	5.701	B
    $B_3(6,4)$	7.211	2.000	4.528	B
    $C_1(1,2)$	8.062	6.403	1.581	C
    $C_2(4,9)$	2.236	3.606	6.042	A

    Clusters after iteration 2

    • Cluster A = $\{A_1, C_2\}$, centre $= \left(\frac{2+4}{2},\frac{10+9}{2}\right) = (3,9.5)$
    • Cluster B = $\{A_3, B_1, B_2, B_3\}$, centre $= \left(\frac{8+5+7+6}{4},\frac{4+8+5+4}{4}\right) = (6.5,5.25)$
    • Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$ (unchanged)

    Iteration 3 - centres $(3,9.5)$, $(6.5,5.25)$, $(1.5,3.5)$

    Point	$d$ to $(3,9.5)$	$d$ to $(6.5,5.25)$	$d$ to $(1.5,3.5)$	Nearest
    $A_1(2,10)$	1.118	6.538	6.519	A
    $A_2(2,5)$	4.610	4.507	1.581	C
    $A_3(8,4)$	7.433	1.953	6.519	B
    $B_1(5,8)$	2.500	3.133	5.701	A
    $B_2(7,5)$	6.021	0.559	5.701	B
    $B_3(6,4)$	6.265	1.346	4.528	B
    $C_1(1,2)$	7.762	6.388	1.581	C
    $C_2(4,9)$	1.118	4.507	6.042	A

    Note that $B_1$ moves from cluster B to cluster A. New centres:

    • Cluster A = $\{A_1, B_1, C_2\}$, centre $= \left(\frac{2+5+4}{3},\frac{10+8+9}{3}\right) = (3.67,9)$
    • Cluster B = $\{A_3, B_2, B_3\}$, centre $= \left(\frac{8+7+6}{3},\frac{4+5+4}{3}\right) = (7,4.33)$
    • Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$

    Iteration 4 - centres $(3.67,9)$, $(7,4.33)$, $(1.5,3.5)$

    Point	$d$ to $(3.67,9)$	$d$ to $(7,4.33)$	$d$ to $(1.5,3.5)$	Nearest
    $A_1(2,10)$	1.944	7.557	6.519	A
    $A_2(2,5)$	4.333	5.044	1.581	C
    $A_3(8,4)$	6.616	1.054	6.519	B
    $B_1(5,8)$	1.667	4.177	5.701	A
    $B_2(7,5)$	5.207	0.667	5.701	B
    $B_3(6,4)$	5.518	1.054	4.528	B
    $C_1(1,2)$	7.491	6.438	1.581	C
    $C_2(4,9)$	0.333	5.548	6.042	A

    The memberships are identical to iteration 3, so no point moves, the centres would not change any further, and the algorithm converges.

    Final result

    Cluster	Points	Final centre
    Cluster 1 (A)	$A_1(2,10),\ C_2(4,9),\ B_1(5,8)$	$(3.67,\ 9)$
    Cluster 2 (B)	$A_3(8,4),\ B_2(7,5),\ B_3(6,4)$	$(7,\ 4.33)$
    Cluster 3 (C)	$A_2(2,5),\ C_1(1,2)$	$(1.5,\ 3.5)$

    The three groups are geometrically sensible: a top-left group around $(3.67,9)$, a right-hand group around $(7,4.33)$, and a bottom-left group around $(1.5,3.5)$.

28. Q9(a). Write a short note on Hierarchical Clustering. _(Q.9: short notes on any two of the following)_20237m

    Module 4: Cluster Analysis

    Write a short note on Hierarchical Clustering.

    (Q.9: short notes on any two of the following)

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note on Hierarchical Clustering

    1. Definition

    Hierarchical clustering creates a nested hierarchy (a tree) of clusters in which clusters at one level are merged (or split) to form clusters at the next level. The result is usually displayed as a dendrogram - a tree diagram whose vertical axis shows the distance (or dissimilarity) at which each merge/split occurs. Cutting the dendrogram at any height gives a flat clustering with a chosen number of clusters.

    2. Two approaches

    1. Agglomerative (bottom-up, the most common): start with each object as a singleton cluster ($n$ clusters) and repeatedly merge the two closest clusters until only one cluster remains. $n-1$ merges are needed.
    2. Divisive (top-down): start with one cluster containing all objects and repeatedly split the least homogeneous cluster until every object is a singleton. It is less used because deciding which cluster to split is computationally harder ($2^{n-1}-1$ possible splits for $n$ objects).

    3. How "closest" is measured - linkage criteria

    • Single linkage (minimum distance): distance between the two nearest members of the two clusters. Fast, can find elongated (non-elliptical) clusters, but suffers from the chaining effect - a few noise points can link two large clusters.
    • Complete linkage (maximum distance): distance between the two farthest members. Produces compact, equally sized clusters, but is sensitive to outliers.
    • Average linkage (UPGMA): average of all pairwise distances between the members of the two clusters - a compromise between single and complete linkage.
    • Ward's method: merges the pair whose merge increases the total within-cluster variance the least; tends to give clusters of similar size.
    • Centroid linkage: distance between the centres (means) of the two clusters.

    4. Illustration

     distance
        |                    +--------------------+
     4  |                    |
        |              +-----+-----+
     3  |              |           |
        |        +-----+-----+     |
     2  |        |     |     |     |
        |   +----+--+ +--+ +--+    |
     1  |   |    |  | |  | |  |    |
        +---+----+--+ +--+ +--+----+-----------> objects
            o1   o2   o3  o4  o5   o6
    

    Clusters {o1,o2} and {o3,o4} form first, then merge into one cluster at a higher level, and the whole set joins at the top; cutting at height 2 gives, say, three clusters.

    5. Merits, demerits and variants

    • Merits: no need to prespecify the number of clusters $k$ in advance; the dendrogram is easy to interpret and shows the natural nesting of groups at several abstraction levels.
    • Demerits: merge/split decisions are irreversible (an early wrong merge cannot be undone); a naive implementation costs $O(n^3)$ time and $O(n^2)$ memory to maintain the distance matrix, so it does not scale well to very large data sets; sensitive to noise and to the choice of linkage.
    • Scalable variants: BIRCH (clustering feature tree, incremental), CURE (uses well-scattered representative points), CHAMELEON (uses a $k$-NN graph and dynamic modelling), and ROCK (for categorical data).
29. Q9(b). Write a short note on Text mining. _(Q.9: short notes on any two of the following)_20237m

    Module 5: Mining Object, Spatial, Multimedia, Text and Web Data

    Write a short note on Text mining.

    (Q.9: short notes on any two of the following)

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note on Text Mining

    1. Definition

    Text mining (text data mining) is the process of discovering previously unknown, interesting and useful patterns, associations, concepts and knowledge from large amounts of unstructured or semi-structured text - documents, web pages, e-mails, reports, social-media posts, patents, medical records. It sits at the intersection of information retrieval, natural language processing (NLP), machine learning and statistics. Unlike a keyword search, which only retrieves documents, text mining analyses them to extract knowledge; unlike classical NLP, whose goal is linguistic understanding, its goal is decision-relevant patterns.

    2. General process

    1. Collect the document corpus from the source (database, web, intranet).
    2. Pre-processing / text preparation: tokenisation, sentence segmentation, removal of stop words (the, is, and), noise removal (punctuation, HTML tags), stemming / lemmatisation (running -> run), and sometimes part-of-speech tagging.
    3. Text representation: convert text into a machine-usable form - bag-of-words, term frequency - inverse document frequency (TF-IDF) weighting, n-grams, and the vector space model (each document = a numeric vector).
    4. Analysis / mining:
       • text categorisation and classification (e-mail spam vs. not spam, news by topic),
       • text clustering (grouping similar documents with no labels),
       • information extraction (entities, relations, events from text),
       • association analysis between terms,
       • sentiment / opinion analysis (positive vs. negative reviews),
       • topic modelling (e.g. Latent Dirichlet Allocation),
       • text summarisation and relationship mining.
    5. Evaluation and visualisation of the discovered patterns.

    3. Applications

    Spam filtering, automatic news categorisation, search-engine ranking, sentiment analysis of product reviews and movie ratings, resume screening, legal/medical document discovery (e-discovery), plagiarism detection, chatbots and question-answering systems, patent and scientific literature analysis, and detection of fraudulent insurance claims.

    4. Challenges

    • Data is unstructured, heterogeneous and noisy, so meaning must be reconstructed.
    • Very high dimensionality and sparsity of the term vector (tens of thousands of terms, most zero).
    • Ambiguity: polysemy (one word, many meanings - e.g. bank), synonyms (car = automobile), idioms, sarcasm and domain-dependent language.
    • Mixed languages, abbreviations, spelling variants and evolving slang.
    • Large volume requires scalable algorithms; evaluation is difficult because there is no single correct answer and labelled training corpora are expensive to build.
    • Privacy of the texts being mined.
30. Q9(c). Write a short note on Issues and challenges in data mining. _(Q.9: short notes on any two of the following)_20237m

    Module 2: Data Mining Fundamentals and Association Rule Mining

    Write a short note on Issues and challenges in data mining.

    (Q.9: short notes on any two of the following)

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note on Issues and Challenges in Data Mining

    Data mining offers great benefits but raises a number of technical, methodological and social issues. They are commonly grouped as follows:

    1. Mining methodology issues

    1. Handling noisy, incomplete and inconsistent data - real data contain missing values, errors and outliers; mining a dirty database produces wrong patterns, so data cleaning, integration and preprocessing are mandatory.
    2. Scalability and efficiency - algorithms must handle terabytes of data, high-dimensional data and evolving data streams; frequent pattern mining on dense data can be combinatorially explosive.
    3. Mining diverse data types - relational data, transactions, graphs, spatial, temporal, multimedia, text, web and stream data each need different models, so one technique does not fit all.
    4. Pattern evaluation and interestingness - a huge number of patterns can be produced, most of which are redundant or trivial; the challenge is to measure interestingness (objective measures such as support, confidence, lift; subjective measures such as novelty, usefulness) and to show only significant patterns.
    5. Imbalance and cost-sensitive learning - in domains like fraud or disease detection the positive class is rare and a wrong prediction has a very different cost from another.

    2. Performance-related issues

    • Interactive mining: the user needs multiple rounds with varying minimum-support thresholds, constraints and ad-hoc queries, so results should be produced quickly rather than after long batches.
    • Parallel, distributed and incremental mining to reduce response time on large or streaming data.
    • Incorporation of background knowledge - user beliefs, taxonomy and constraints should guide the search without over-constraining it.

    3. Issues relating to data quality and diversity

    • Data may be heterogeneous, distributed, legacy or schema-less; integration creates redundancy and conflicts.
    • High dimensionality, sparse feature spaces and irrelevant attributes degrade accuracy (the curse of dimensionality).
    • Evolving concepts: models and patterns can become obsolete as data distributions change over time (concept drift).

    4. Social and ethical issues

    1. Data privacy and security - mining can reveal sensitive personal information (e.g. health or financial status) even from seemingly anonymous data; techniques such as k-anonymity, differential privacy and access control are needed.
    2. Data ownership, copyright and access - who owns mined results? Is the use of web content legitimate?
    3. Misuse of results - profiling, discrimination, spam and manipulation; results may be over-trusted because they look precise.
    4. Interpretability - results must be understandable to non-expert decision makers, otherwise they are not used.
    5. Legal and professional responsibility - who is answerable when an automatic decision is wrong (loan rejected, patient misdiagnosed)?

    In short, the main challenges are the quality and scale of data, the correct evaluation of discovered patterns, and the privacy, security and ethical use of the knowledge obtained.

31. Q9(d). Write a short note on Supervised Vs. Unsupervised learning. _(Q.9: short notes on any two of the following)_20237m

    Module 3: Classification and Prediction

    Write a short note on Supervised Vs. Unsupervised learning.

    (Q.9: short notes on any two of the following)

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Note: Supervised vs. Unsupervised Learning

    Both are machine-learning paradigms used in data mining; the fundamental difference is whether the training data carry class labels.

    1. Supervised learning

    Learning from a set of labelled examples - each training record has both the input attributes and the known output (class/target). The learner builds a model (a function $f: X \rightarrow Y$) that predicts the label of unseen records. The problem is described as teaching the machine with a teacher.

    • Algorithms: decision trees (ID3, C4.5, CART), naive Bayes, logistic regression, support vector machines, k-nearest neighbour, neural networks, rule-based learners.
    • Evaluation: a labelled test set gives accuracy, precision, recall, F1-score, ROC-AUC.
    • Applications: spam detection, credit/loan approval, disease diagnosis, price prediction, image classification.
    • Cost: collecting labelled data is expensive and time-consuming.

    2. Unsupervised learning

    Learning from unlabelled data - only the input records are given, and the algorithm must discover the hidden structure, groups or regularities by itself. There is no teacher and no single correct answer.

    • Algorithms: clustering (k-means, k-medoids, hierarchical, DBSCAN), association-rule mining (Apriori, FP-growth), dimensionality reduction (PCA), anomaly/novelty detection.
    • Evaluation: only internal criteria - cohesion, separation, silhouette coefficient, purity, support/confidence - because there is no ground truth.
    • Applications: market-basket segmentation, customer segmentation, document grouping, fraud/anomaly detection, image compression.
    • Advantage: no labelling cost; can find patterns no one had thought to look for.

    3. Comparison table

    Criterion	Supervised learning	Unsupervised learning
    Training data	Labelled (input-output pairs)	Unlabelled (input only)
    Teacher / feedback	Yes - correct answers are given	No - feedback is absent
    Goal	Predict the class/value of new data	Discover hidden structure, groups, rules
    Output	Predictive model (classifier/regressor)	Clusters, associations, projections
    Evaluation	Accuracy, precision, recall, F1	Internal measures (silhouette, support)
    Human effort / cost	High (data labelling)	Low
    Complexity of problem	Well-defined target	Open-ended, exploratory
    Typical errors	Over-fitting / under-fitting	Choosing k, distance measure, thresholds
    Examples	Decision tree, SVM, k-NN, Naive Bayes	k-means, DBSCAN, Apriori, PCA

    4. When is which used?

    • Use supervised learning when labelled historical examples exist and the goal is prediction or decision support.
    • Use unsupervised learning when no labels exist or when the aim is exploration (segmentation, profiling, anomaly hunting).
    • Semi-supervised learning combines a small labelled set with a large unlabelled set and is very practical when labelling is costly; reinforcement learning, where an agent learns by reward and penalty from the environment, is a third distinct paradigm.