Data Mining and Data Warehousing

1.1 What is data mining?

The name is slightly wrong, and examiners love this remark: we do not mine data, we mine knowledge from data, just as gold mining is named after gold, not after sand. A more accurate name is Knowledge Discovery from Data (KDD). Data mining is one step of KDD, though in industry the two words are used interchangeably.

Why did data mining appear?

• Data explosion. Cheap storage, bar-code scanners, ATMs, e-commerce, sensors and the Web created terabytes of data. We are "data rich but information poor". Write this exact phrase, it is from the textbook.
• Queries are not enough. SQL answers "how many TVs did we sell in Pokhara in Ashad?" It cannot answer "which customers are about to leave us and why?"
• Competition. Business needs decision support, not just record keeping.

1.2 The KDD process near-certain question

KDD is the complete pipeline from raw database to usable knowledge. Data mining sits in the middle of it. Learn the seven steps in order, because this figure alone is often a full 5-mark answer.

1. Data cleaning: remove noise and inconsistent records, fill in missing values.
2. Data integration: combine multiple heterogeneous sources into one store.
3. Data selection: retrieve only the data relevant to the analysis task.
4. Data transformation: normalise, aggregate, summarise into forms fit for mining.
5. Data mining: apply intelligent algorithms to extract patterns.
6. Pattern evaluation: keep only truly interesting patterns using interestingness measures.
7. Knowledge presentation: visualise with charts, trees, rules and tables.

1.3 Architecture of a typical data mining system

Knowledge base holds domain knowledge such as concept hierarchies, user beliefs and thresholds, and guides the search and evaluates interestingness. Tight coupling of the mining engine with the database (mining primitives pushed into the DB engine) gives the best performance; no coupling is the worst.

1.4 Classification of data mining systems frequent

A DM system can be categorised along four criteria. Remember the mnemonic D-K-T-A: Database, Knowledge, Technique, Application.

1.5 Data mining functionalities (techniques) write with examples

Split them into two families first, since this framing earns a mark by itself.

• Descriptive mining: characterises general properties of the data (characterisation, discrimination, association, clustering).
• Predictive mining: infers on current data to make predictions (classification, prediction/regression, outlier & evolution analysis).

1.6 Major issues and challenges in data mining very frequent

Group them under five headings and give two sub-points each. Never write a plain list.

(a) Mining methodology issues

• Mining different kinds of knowledge in the same database, since users want many functionalities.
• Mining knowledge at multiple levels of abstraction (roll-up / drill-down of patterns).
• Incorporating background knowledge (concept hierarchies, user beliefs).
• Handling noise and incomplete data: otherwise overfitting occurs.
• Pattern evaluation, the interestingness problem: algorithms generate thousands of patterns, most of them useless.

(b) User interaction issues

• Interactive mining: the user must be able to refine the search dynamically.
• Data mining query languages and ad-hoc mining (DMQL, integration with SQL).
• Presentation and visualisation of results (trees, rules, cubes, charts).

(c) Performance issues

• Efficiency and scalability: runtime must be predictable and acceptable on huge data.
• Parallel, distributed and incremental mining algorithms: data is partitioned, results merged; incremental updating avoids mining from scratch.

(d) Diversity of data types

• Handling relational and complex types: spatial, multimedia, time-series, text, graphs.
• Mining heterogeneous, global information systems (the Web); Web mining is a whole research area.

(e) Social issues

• Privacy and data security: mining personal records raises legal/ethical problems; privacy-preserving data mining is the response.
• Misuse and misinterpretation of discovered patterns (correlation ≠ causation).

1.7 DBMS vs data mining, and KDD vs data mining short question

1.8 Applications of data mining

• Market basket / retail analysis: product placement, catalogue design, cross-selling, loyalty analysis.
• Finance and banking: credit scoring, loan default prediction, risk analysis, money laundering detection.
• Telecommunication: fraudulent call pattern detection, churn prediction, network fault isolation.
• Healthcare and bioinformatics: disease diagnosis, DNA sequence and gene expression analysis, drug discovery.
• Intrusion detection and cyber security: anomaly and misuse detection.
• Science and engineering: remote sensing, astronomy sky surveys, weather.
• Web and social media: recommendation systems, search engine ranking, personalisation, sentiment analysis.
• Government: census analysis, tax fraud, policy planning.

1.9 Likely exam questions from this unit

1. Define data mining. Explain the KDD process with a neat diagram. 10
2. Explain the architecture of a typical data mining system. 5-10
3. On what criteria are data mining systems classified? Explain each. 5
4. Explain data mining functionalities with suitable examples. 10
5. Discuss the major issues and challenges in data mining. 10
6. Differentiate DBMS and data mining / OLTP and data mining. 5
7. What makes a pattern interesting? List the applications of data mining. 5

2.1 What is a data warehouse? definition + 4 features = guaranteed

Then explain the four keywords. Each one is worth a mark.

Data warehouse vs data mart vs virtual warehouse

• Enterprise warehouse: the whole organisation; large, months/years to build.
• Data mart: a subset for a specific group/department (e.g. marketing data mart). Independent data mart = sourced directly from operational systems; dependent data mart = sourced from the enterprise warehouse.
• Virtual warehouse: only a set of views over operational databases; easy to build, but it puts extra load on operational servers.

ETL is the loading machinery: Extract from sources, Transform (clean, standardise, aggregate), Load into the warehouse. Add refresh as the fourth ongoing operation.

2.2 OLTP vs OLAP asked almost every year

2.3 Multi-dimensional data model

The warehouse is modelled as a data cube which allows data to be viewed in multiple dimensions.

• Dimension: a perspective or entity with respect to which the organisation keeps records: time, item, branch, location. Each has a dimension table describing it.
• Fact table: contains the numeric measures (dollars_sold, units_sold, average_sales) plus foreign keys to the dimension tables.
• Measure: a numeric function evaluated at each point of the cube space. Three types: distributive (count, sum, min, max, which can be computed by partitioning), algebraic (avg, standard deviation, obtained from distributive functions), holistic (median, mode, rank, for which no constant-size sub-aggregate exists).
• Cuboid: the cube for a given set of dimensions. The base cuboid is the lowest level (all n dimensions); the apex cuboid (denoted all) is the total summary. The lattice of all cuboids is the data cube.

2.4 Schemas: star, snowflake, fact constellation draw all three

2.5 Data cubes and OLAP operations guaranteed question

OLAP server types short question

• ROLAP: relational OLAP. Data stays in relational tables; uses star schema plus bitmap/join indexes. Scalable to huge data, slower queries.
• MOLAP: multidimensional OLAP. Data stored in a multidimensional array; fast indexing to precomputed summaries, but sparse cubes waste space (needs two-level sparse compression).
• HOLAP: hybrid. Detailed data in relational store, aggregations in multidimensional store. Best of both, e.g. Microsoft SQL Server Analysis Services.
• Specialised SQL servers: SQL engines optimised for star queries.

2.6 Data warehouse architecture draw the 3-tier

Design approaches

• Top-down: build the enterprise warehouse first, then dependent data marts. Consistent, but expensive and slow.
• Bottom-up: build data marts first and integrate later. Fast, low cost, but risks inconsistency.
• Recommended (incremental/hybrid): define a high-level enterprise model, implement independent marts in parallel, then integrate.

The four warehouse design views

Top-down view (what information the enterprise needs) · data source view (what the operational systems hold) · data warehouse view (fact and dimension tables) · business query view (what the end user sees).

Metadata repository: list its contents

• Warehouse structure: schema, view, dimension, hierarchy, derived-data definitions, mart location.
• Operational metadata: data lineage (history of migrated data), currency (active/archived/purged), monitoring information.
• Algorithms for summarisation and mapping from operational environment to warehouse.
• Business metadata: business terms, ownership, charging policies.

2.7 Data warehouse implementation

(a) Efficient cube computation: the materialisation question

• No materialisation: compute every cuboid on the fly. Slow queries.
• Full materialisation: precompute all 2ⁿ cuboids. Fastest queries but explosive storage.
• Partial materialisation: precompute a selected subset. This is the practical choice. Selection uses query frequency, cost, and storage constraints; iceberg cubes store only cells above a minimum-support threshold.

The compute cube operator generates the lattice; algorithms include multiway array aggregation (MOLAP, bottom-up), BUC (bottom-up computation for iceberg cubes, top-down order) and Star-Cubing.

(b) Indexing OLAP data

• Bitmap index: for each distinct value of a low-cardinality attribute, a bit vector of length = number of rows. Comparison, join and aggregation become fast bit operations (AND/OR). Inefficient for high-cardinality attributes.
• Join index: pre-computes the join between the fact table and a dimension table by registering the joinable rows. A bitmapped join index combines both.

(c) Efficient query processing: three steps

1. Determine which operations should be performed on the available cuboids (transform the selection, roll-up, drill-down into corresponding SQL/OLAP operations).
2. Determine to which materialised cuboid(s) the relevant operations should be applied.
3. Choose the cuboid with the least cost: prefer one with fewer, smaller cells, matching dimensions, and available indexes.

(d) From data warehousing to data mining

Three uses of a warehouse: information processing (querying, reporting), analytical processing (OLAP: slice, dice, roll-up), and data mining (knowledge discovery of hidden patterns, rules, models). OLAM (Online Analytical Mining) integrates OLAP with mining so the user can mine interactively at different abstraction levels; it sits between the OLAP engine and the user interface and shares the same cube infrastructure.

2.8 Likely exam questions from this unit

1. Define a data warehouse. Explain its four key features with examples. 5-10
2. Differentiate OLTP and OLAP. Why is a separate data warehouse required? 10
3. Explain the multi-dimensional data model. Draw star, snowflake and fact constellation schemas for a sales warehouse and compare them. 10
4. What is a data cube? Explain OLAP operations with an example each. 10
5. Explain the three-tier data warehouse architecture with a diagram. 10
6. Discuss data cube materialisation and OLAP indexing (bitmap, join index). 5-10
7. Differentiate ROLAP, MOLAP and HOLAP. 5
8. How many cuboids does a 5-dimensional cube with 3-level hierarchies contain? 2-5

3.1 Data cleaning

(a) Missing values: six methods, in increasing order of quality

1. Ignore the tuple: usually done when the class label is missing; poor when the percentage of missing values per attribute is large.
2. Fill in manually: accurate but tedious and infeasible for large data.
3. Use a global constant such as "Unknown" or −∞: simple, but the mining program may mistakenly treat "Unknown" as an interesting concept.
4. Use the attribute mean for all samples.
5. Use the attribute mean for samples of the same class: better.
6. Use the most probable value: inferred by regression, Bayesian inference or a decision tree. This is the most popular and most accurate strategy, so say so.

(b) Noisy data: smoothing techniques

Noise = random error or variance in a measured variable.

• Binning: sort values, partition into equal-frequency (equi-depth) bins, then smooth by bin means, bin medians or bin boundaries (each value is replaced by the nearer boundary).
• Regression: fit the data to a function (linear/multiple) and use fitted values.
• Clustering: values falling outside every cluster are detected as outliers.
• Combined computer-and-human inspection: the computer flags suspicious values, a human confirms.

3.2 Data integration

Combining data from multiple sources into a coherent store. Three problems to write about:

1. Entity identification problem: is cust_id in one database the same as customer_number in another? Solved using metadata (name, meaning, data type, range, null rules).
2. Redundancy: an attribute derivable from another (annual revenue from monthly sales). Detected by correlation analysis.
3. Duplication and conflict detection: the same real-world entity with different attribute values, e.g. price in NPR vs USD, weight in kg vs pounds.

Correlation analysis: two formulas to remember

3.3 Data transformation

• Smoothing: remove noise (binning, regression, clustering).
• Aggregation: summarise; e.g. daily sales aggregated to monthly, building a cube.
• Generalisation: replace low-level data with higher-level concepts using a concept hierarchy (street → city → country).
• Normalisation: scale into a small specified range.
• Attribute/feature construction: add new attributes derived from existing ones (area from height × width).

Three normalisation methods numerical: learn all three

3.4 Data reduction

Obtain a reduced representation that produces (almost) the same analytical results in far less volume. Five strategies:

1. Data cube aggregation: aggregate to the smallest cuboid that still answers the task.
2. Attribute subset selection: remove irrelevant/redundant attributes. Heuristic methods since 2ⁿ subsets exist:
   • Stepwise forward selection: start empty, add the best attribute each round.
   • Stepwise backward elimination: start full, remove the worst each round.
   • Combination of forward and backward.
   • Decision-tree induction: attributes appearing in the tree are the relevant ones.
3. Dimensionality reduction: encode data to a compressed form. Wavelet transform (DWT: keeps a small fraction of the strongest coefficients, lossy but good for sparse/skewed data) and Principal Component Analysis (finds k orthonormal vectors, the principal components, that best represent the data; the components are sorted by variance and the weak ones are dropped).
4. Numerosity reduction: replace data by smaller representations: parametric (regression, log-linear models, which store only the parameters) and non-parametric (histograms, clustering, sampling).
5. Discretisation and concept hierarchy generation: see next section.

Sampling methods (write all four)

SRSWOR: simple random sample without replacement · SRSWR: with replacement · Cluster sample: the data is grouped into M clusters, a random sample of clusters is taken · Stratified sample: data is divided into strata and a sample is drawn from each, which guarantees representation of rare classes.

3.5 Discretisation and concept hierarchy generation

For numeric attributes: five techniques

• Binning: equal-width or equal-frequency, applied recursively. Unsupervised, top-down, sensitive to outliers.
• Histogram analysis: equal-width or equal-depth histograms, applied recursively until a minimum interval size is reached. Unsupervised.
• Entropy-based discretisation: supervised, top-down. Choose the split point that minimises the expected information requirement; recurse until the information gain is below a threshold. This is the most commonly used and worth naming explicitly.
• χ²-merging (ChiMerge): supervised, bottom-up. Adjacent intervals with the lowest χ² (i.e. most similar class distributions) are merged recursively.
• Cluster analysis / natural partitioning (3-4-5 rule): the 3-4-5 rule partitions a range into 3, 4 or 5 relatively uniform intervals depending on the most significant digit, giving "natural" looking boundaries.

For categorical attributes: four methods of generating hierarchies

1. Explicit specification of a partial/total order by the user at the schema level: street < city < province < country.
2. Explicit data grouping for a small portion of intermediate-level data: {Kathmandu, Lalitpur, Bhaktapur} ⊂ Bagmati.
3. Specification of a set of attributes but not their order: the system generates the order automatically using the heuristic that an attribute with more distinct values is at a lower level of the hierarchy (country 15 values < province 65 < city 3567 < street 674,339).
4. Specification of only a partial set of attributes: the system uses the database schema and semantic ties to fill in the rest.

3.6 Data mining primitives and DMQL

A data mining task is specified in the form of a data mining query, built from five primitives. Memorise them as T-K-B-I-P.

3.7 Concept description: characterisation, discrimination and class comparison

Concept description = characterisation + comparison. It generates descriptions for data classes at a general level.

Attribute-Oriented Induction (AOI): the standard algorithm

1. Collect the task-relevant data with a relational query (the initial working relation).
2. Perform attribute removal: if an attribute has a large number of distinct values and there is no higher-level concept for it (e.g. name, phone), remove it.
3. Perform attribute generalisation: if there is a higher-level concept in the concept hierarchy, replace the values by the generalised value (birth_place: Kathmandu → Nepal).
4. Apply attribute generalisation control: generalise until the number of distinct values of the attribute is under the attribute generalisation threshold (typically 2-8), or until the total number of tuples is under the generalised relation threshold (typically 10-30).
5. Aggregate identical tuples and accumulate a count (and other aggregates like sum), then present the result as a generalised relation, crosstab, chart or a set of quantitative rules.

Class comparison (discrimination): how it differs from characterisation

The procedure is the same as AOI but applied to two or more classes: a target class and one or more contrasting classes. Critically, all classes must be generalised to the same level of abstraction (synchronous generalisation) so they are comparable. The output includes a t-weight (typicality of a tuple within its own class) and a d-weight (discriminating weight: how much a tuple belongs to the target rather than the contrasting class).

3.8 Association rule mining the highest-yield topic in the paper

The two-step process: say this before any algorithm:

1. Find all frequent itemsets (support ≥ min_sup). This is the expensive step.
2. Generate strong association rules from them (confidence ≥ min_conf). This is straightforward.

Classification of association rules: the syllabus asks this directly

3.9 The Apriori algorithm practise this until automatic

The two sub-steps of each iteration

1. Join step: C_k is generated by joining L_k−1 with itself. Two itemsets are joinable only if their first (k−2) items are identical and the last items are in lexicographic order (l₁[k−1] < l₂[k−1]), which avoids duplicates.
2. Prune step: remove any candidate in C_k that has some (k−1)-subset not in L_k−1. Then scan the database once to count the survivors and keep those with count ≥ min_sup.

Improving the efficiency of Apriori: six methods

1. Hash-based technique (DHP): while counting C₁, hash 2-itemsets into buckets; a bucket whose count is below min_sup cannot contain a frequent 2-itemset, so those candidates are removed.
2. Transaction reduction: a transaction that contains no frequent k-itemset cannot contain any frequent (k+1)-itemset, so mark it and skip it in later scans.
3. Partitioning: requires only two database scans. Partition D so each part fits in memory, find local frequent itemsets in each partition (any global frequent itemset must be frequent in at least one partition), then a second scan counts the global support of these candidates.
4. Sampling: mine a random sample with a slightly lowered support threshold, then verify against the full database; trades accuracy for efficiency.
5. Dynamic itemset counting (DIC): new candidates are added at start points during the scan rather than only at the end of a pass, reducing the number of scans.
6. Vertical data format (ECLAT): store item → TID_set; support = length of the TID set, and k-itemsets are obtained by intersecting TID sets.

3.10 FP-Growth: mining without candidate generation compare with Apriori

Two bottlenecks of Apriori that FP-growth removes: (i) it generates a huge number of candidates (10⁴ frequent 1-itemsets produce ~10⁷ candidate 2-itemsets); (ii) it needs to scan the database k+1 times for the longest pattern of length k.

Steps of FP-growth

1. First scan: find frequent 1-itemsets and sort them in descending order of support, the F-list. For our dataset: I2:7, I1:6, I3:6, I4:2, I5:2.
2. Second scan: build the FP-tree. For each transaction, keep only frequent items, sort by the F-list order, and insert as a branch, incrementing counts on shared prefixes. A header table links all nodes of the same item.
3. Mine the tree by starting from the least frequent item and, for each item, collecting its conditional pattern base (the set of prefix paths), constructing its conditional FP-tree, and recursively mining it. Concatenate the suffix to produce the frequent patterns.

3.11 Multilevel and multidimensional association rules

(a) Multilevel association rules

Rules mined at multiple levels of a concept hierarchy (all → computer → laptop computer → IBM laptop). Strong rules are often hard to find at the primitive level because support there is low, so we mine top-down, level by level.

Four support strategies (name them all):

• Uniform support: the same min_sup at every level. Simple; search can be optimised (if an ancestor is infrequent, its descendants are ignored). Problem: a high threshold misses low-level rules, a low threshold generates too many high-level rules.
• Reduced support: each lower level has a smaller min_sup. This is the recommended approach. Search strategies within it: level-by-level independent, level-cross filtering by single item, level-cross filtering by k-itemset, and controlled level-cross filtering using a "level passage threshold".
• Group-based support: the user or expert sets a group-wise threshold per subset of items (e.g. lower threshold for expensive laptops).
• Redundancy filtering: a rule is redundant if its support and confidence are close to the "expected" values based on its ancestor rule. E.g. if computer ⇒ printer [8 %, 70 %] holds and laptops are one quarter of computers, then laptop ⇒ printer [2 %, 72 %] adds nothing new and should be filtered out.

(b) Multidimensional association rules

Rules involving two or more distinct predicates/dimensions, typically mined from a relational table or data warehouse rather than a transaction table.

Since dimensions can be numeric, there are three ways to handle them:

1. Static discretisation using predefined concept hierarchies; the data is transformed into a cube and cells are counted (a cube is well suited because cells already store counts).
2. Dynamic quantitative association rules: numeric attributes are discretised dynamically to maximise the confidence or compactness of the rules; adjacent 2-D cells (a "grid") are clustered/merged into larger rectangular regions.
3. Distance-based association rules: a dynamic discretisation that considers the distance between data points, giving intervals that are semantically more meaningful.

3.12 From association analysis to correlation analysis very likely 5 marks

Other measures worth naming: χ², all_confidence, cosine. Lift and χ² are not null-invariant (they are affected by the number of transactions containing neither item), whereas all_confidence and cosine are. A good sentence to include for full marks.

Also mention constraint-based mining, where the user supplies knowledge, data, dimension, rule or interestingness constraints. Constraints are classified as anti-monotone (if violated, all supersets violate, e.g. sum(price) ≤ 100), monotone, succinct (candidates can be enumerated up-front) and convertible.

3.13 Likely exam questions from this unit

1. Why is data preprocessing needed? Explain the major tasks of data preprocessing. 10
2. Explain the methods of handling missing values and noisy data. Apply binning (means / boundaries) to the given data. 10
3. Explain normalisation. Normalise the given value using min-max, z-score and decimal scaling. 5
4. Explain data reduction strategies. What is attribute subset selection? 10
5. What is discretisation and concept hierarchy generation? Explain the methods for numeric and categorical data. 10
6. Explain the primitives of a data mining task. Write a DMQL query for a given scenario. 10
7. Explain attribute-oriented induction. How is class comparison performed? Define t-weight and d-weight. 10
8. Define support and confidence. Find all frequent itemsets and strong association rules using Apriori for the given transactions. 10-15
9. Explain FP-growth with the FP-tree for the given data and compare it with Apriori. 10
10. Explain multilevel and multidimensional association rules. What is a redundant multilevel rule? 10
11. Show with an example that support and confidence can be misleading. Explain lift/correlation. 5

4.1 Classification vs prediction, and the two-step process

Preparing the data for classification

Data cleaning · relevance analysis (remove redundant/irrelevant attributes, also called feature selection) · data transformation (normalisation, generalisation).

Criteria for comparing classification methods short question

Accuracy (predictive accuracy of the classifier/predictor) · Speed (model construction and usage time) · Robustness (handling noise and missing values) · Scalability (efficiency on disk-resident large databases) · Interpretability (how understandable the model is) · Goodness of rules (tree size, compactness of rules).

4.2 Decision tree induction certain 10-15 marks

Tree construction principle

The tree is built top-down, recursively, in a divide-and-conquer manner. At each node the algorithm selects the attribute that best separates the tuples into individual classes (highest purity) using an attribute selection measure. The classic algorithms are ID3 (Quinlan, 1986, uses information gain), C4.5 (its successor, uses gain ratio) and CART (binary trees, uses the Gini index).

The generic algorithm Generate_decision_tree(D, attribute_list)

1. Create a node N.
2. If all tuples in D belong to the same class C, return N as a leaf labelled C.
3. If attribute_list is empty, return N as a leaf labelled with the majority class in D.
4. Apply the attribute selection method to find the splitting criterion (best attribute, and split point/subset if needed); label N with it.
5. For each outcome j of the splitting criterion, let D_j be the partition of tuples. If D_j is empty, attach a leaf labelled with the majority class of D; otherwise attach the subtree returned by recursively calling the algorithm on D_j.
6. Return N. Terminating conditions: all tuples of one class, no attributes remain, or the partition is empty.

Attribute selection measures

4.3 Tree construction with presorting: scalable decision trees

Classical ID3/C4.5/CART assume the whole training set fits in memory; they thrash when data is disk-resident. Presorting sorts each numeric attribute once at the start so that the best split point can be found in a single linear pass at every node, instead of re-sorting at every node.

4.4 Pruning techniques frequent

Postpruning methods to name

• Cost-complexity pruning (CART): cost = f(number of leaves, error rate). Uses a separate pruning set; a subtree is replaced by a leaf if that reduces the cost.
• Pessimistic pruning (C4.5): uses only the training set but adds a penalty (continuity correction) to the training error to compensate for its optimistic bias, so no separate pruning set is needed.
• MDL, Minimum Description Length: chooses the tree that requires the fewest bits to encode both the tree and the exceptions; needs no test set and is less biased toward large trees.

Integration of pruning and construction syllabus term

Two-phase build-then-prune is wasteful: effort is spent expanding nodes that will be pruned away. PUBLIC (PrUning and BuiLding Integrated in Classification) integrates the two: during building, before a node is expanded, it computes a lower bound on the minimum cost of the subtree rooted at that node. If the node would certainly be pruned later, it is turned into a leaf immediately. The result is identical to the tree produced by build-then-prune, but built faster. The same idea appears in Rainforest + pruning and in the interleaved pruning of MDL-based methods.

Other issues in tree induction

• Repetition: an attribute is repeatedly tested along a path (A < 60, then A < 45).
• Replication: duplicate subtrees exist within the tree. Both are solved by multivariate splits (tests on a combination of attributes) and attribute construction.
• Extracting rules: one IF-THEN rule per root-to-leaf path; rules are mutually exclusive and exhaustive, and can be pruned individually.

4.5 Bayesian classification numerical certain

The naive Bayesian classifier assigns X to the class C_i that maximises P(C_i|X). Since P(X) is constant, we maximise P(X|C_i)·P(C_i). The class-conditional independence assumption ("naive") says the attributes are conditionally independent given the class, so:

Bayesian belief networks syllabus term

Naive Bayes assumes total independence, which is rarely true. A Bayesian belief network (belief network, Bayesian network, probabilistic network) allows conditional independence between subsets of attributes and so is a more realistic model.

It is defined by two components:

1. A directed acyclic graph (DAG): nodes are random variables (discrete or continuous), arcs are causal dependencies. An arc from Y to Z makes Y a parent of Z, and Z is conditionally independent of its non-descendants given its parents.
2. A conditional probability table (CPT) for each variable, giving P(Z | parents(Z)) for every combination of parent values.

Training belief networks: if the structure is known and all variables observable, we simply compute the CPT entries from the data. If the structure is known but some variables are hidden, a gradient descent method (or EM) trains the CPT entries. If the structure is unknown, structure-learning/discrete-optimisation algorithms infer it. Human experts commonly supply the structure using their causal knowledge, which is a major advantage over black-box models.

4.6 Neural networks and backpropagation

Structure of a multilayer feed-forward network: an input layer (one unit per attribute, values usually normalised to [0,1]), one or more hidden layers, and an output layer. It is feed-forward because no weight cycles back; fully connected because every unit feeds every unit of the next layer. A network with two hidden layers is called a three-layer network (input layer is not counted). Given enough hidden units, such a network can approximate any function.

Backpropagation algorithm write the six steps + formulas

1. Initialise the weights and biases to small random numbers (e.g. −1.0 to 1.0).
2. Propagate the inputs forward. For a hidden or output unit j: Ij = Σi wijOi + θj then Oj = 1 / (1 + e−Ij).
3. Backpropagate the error. Output unit: Errj = Oj(1 − Oj)(Tj − Oj). Hidden unit: Errj = Oj(1 − Oj) Σk Errkwjk.
4. Update weights: Δwij = l · Errj · Oi, wij = wij + Δwij, where l is the learning rate (often 1/t for epoch t). Small l = slow learning; large l = oscillation.
5. Update biases: Δθj = l · Errj.
6. Terminate when all Δw are below a threshold, or the misclassified percentage is below a threshold, or the maximum number of epochs is reached. (Updating after each tuple = case updating; after the whole epoch = epoch updating.)

Unsupervised learning in neural nets

Backpropagation is supervised. Unsupervised neural learning has no target output; the network discovers structure by itself:

• Self-Organising Map (SOM / Kohonen map): the winning output unit (whose weight vector is closest to the input) and its neighbours adjust their weights toward the input. Result: a topology-preserving 2-D map where similar inputs land near each other. Used for clustering and visualisation, e.g. web document clustering.
• Competitive / winner-take-all learning: only the winner updates.
• Adaptive Resonance Theory (ART): creates new clusters when an input does not match any existing prototype within a vigilance threshold.

Data mining using a neural net: rule extraction

To beat the black-box criticism, several techniques extract symbolic knowledge:

• Network pruning: remove weighted links that do not change classification accuracy, producing a simpler network.
• Rule extraction: cluster the activation values of hidden units, then derive rules that relate input activations to hidden clusters, and hidden clusters to output classes; finally combine them into IF-THEN rules on the original inputs.
• Sensitivity analysis: vary one input while holding the others fixed and observe the change in output; the result is expressed as a rule such as "IF X decreases 5 % THEN Y increases 8 %".

4.7 Other classification methods

(a) Genetic algorithms

An evolutionary search inspired by biology. Rules are encoded as bit strings: e.g. IF A1 AND NOT A2 THEN C2 is encoded as 100. An initial population of random rules is created; the fitness of a rule is its classification accuracy on a set of training samples. A new population is formed from the fittest rules using selection, crossover (substrings from two rules are swapped) and mutation (randomly flipped bits). The process repeats until the population meets a fitness threshold. GAs are easily parallelised and are also used to evaluate the fitness of other algorithms.

(b) Rough set theory short question

Introduced by Pawlak for imprecise or noisy data; applies to discrete-valued attributes, so continuous ones must be discretised first. A class C that cannot be described exactly is approximated by two sets:

• Lower approximation: the tuples that, based on the attribute values, certainly belong to C.
• Upper approximation: the tuples that cannot be described as not belonging to C (i.e. certainly or possibly belong).

The difference between the two is the boundary region. Rough sets are also used for feature reduction (finding reducts: minimal attribute subsets that describe all concepts) and relevance analysis. Finding all reducts is NP-hard, so a discernibility matrix is used.

(c) Fuzzy set approaches

Classical rules use sharp cut-offs: income > 50K ⇒ high. Then 50,000 is "medium" and 50,001 is "high", which is unnatural. Fuzzy set theory (Zadeh) replaces this with membership functions: a value can belong to "medium income" with degree 0.4 and to "high income" with degree 0.6, and membership values need not sum to 1. In classification, rules from several fuzzy categories are applied, their truth values are combined (usually by summing/averaging), and the class with the highest score wins. Fuzzy logic is valuable in expert systems and data mining because it works at a high level of abstraction and handles vagueness gracefully.

(d) Support Vector Machines (SVM)

An SVM searches for the maximum marginal hyperplane (MMH): the decision boundary with the largest margin between two classes, because that gives the highest expected accuracy on unseen data. The training tuples lying on the margin are the support vectors; they alone define the classifier. For data that is not linearly separable, the input is mapped by a nonlinear kernel function into a higher-dimensional space where a linear separator does exist (polynomial kernel, Gaussian radial basis function kernel, sigmoid kernel). This is the kernel trick: we never compute the mapping explicitly, only the dot products.

(e) Case-based reasoning (CBR)

An instance-based (lazy) learner that stores training tuples as cases: typically complex symbolic descriptions rather than plain points. When a new case arrives, CBR searches for identical cases and returns their solution; if none exists, it finds similar cases (graph/subgraph similarity), combines and adapts their solutions, and may backtrack. Used in customer help desks, legal reasoning and medical diagnosis. Challenges: finding a good similarity metric, efficient indexing of cases, and the trade-off between the size of the case base and the search time.

4.8 Prediction: regression short numerical

Other predictors to name: generalised linear models (logistic regression for categorical outcomes, Poisson regression for counts), log-linear models (approximate discrete multidimensional probability distributions; also used for data compression and smoothing), and regression trees / model trees (CART: leaves hold the mean value, or a linear equation in a model tree).

4.9 Classifier accuracy certain question

Estimating accuracy: four methods

• Holdout: randomly split, typically ²⁄₃ training and ¹⁄₃ testing. Random subsampling repeats holdout k times and averages.
• k-fold cross-validation: partition into k mutually exclusive folds of equal size; in iteration i, fold i is the test set and the rest is training. Each tuple is used once for testing. 10-fold cross-validation is recommended because of its relatively low bias and variance. Leave-one-out is the case k = number of tuples; stratified folds keep the class distribution of the whole data.
• Bootstrap: sample with replacement. In .632 bootstrap, a tuple has probability (1 − 1/d)^d ≈ e⁻¹ = 0.368 of never being chosen, so about 63.2 % of the tuples form the training set and 36.8 % form the test set. Accuracy = Σ (0.632 × acc_test + 0.368 × acc_train) / k. Best for small data sets.
• ROC curve: plots the true-positive rate against the false-positive rate as the threshold varies. The larger the area under the curve (AUC) the more accurate the model; the diagonal represents random guessing.

Increasing accuracy: ensemble methods

• Bagging (bootstrap aggregation): build k models on k bootstrap samples and take a majority vote (average for prediction). Reduces variance and is more robust to noise; often significantly better than a single classifier.
• Boosting (AdaBoost): models are built sequentially and each training tuple carries a weight; after each round, misclassified tuples get higher weights so the next model focuses on them. Final vote is weighted by each model's accuracy. Usually more accurate than bagging but risks overfitting the misclassified data.
• Random forest: bagging of decision trees where each split considers a random subset of attributes; accurate, robust to outliers and fast.

4.10 Likely exam questions from this unit

1. What is classification? Explain the two-step process. How does it differ from prediction? 5-10
2. Construct a decision tree for the given training data using information gain (show all calculations). 15
3. Define entropy, information gain, gain ratio and Gini index. Compare their biases. 10
4. Explain tree construction with presorting (SLIQ / SPRINT / RainForest). 10
5. What is overfitting? Explain prepruning and postpruning; explain integration of pruning and construction. 10
6. Classify the given tuple using the naive Bayesian classifier (show all probabilities). 10
7. What is a Bayesian belief network? Draw one with its CPT and write the joint probability formula. 10
8. Explain the backpropagation algorithm with a neural network diagram. 10-15
9. How is knowledge extracted from a trained neural network? Explain unsupervised learning / SOM. 5-10
10. Write short notes on: genetic algorithm, rough sets, fuzzy sets, SVM, case-based reasoning. 5 each
11. Explain prediction using linear and nonlinear regression with an example. 10
12. Define confusion matrix, accuracy, precision, recall and F-measure. Explain holdout, k-fold cross-validation and bootstrap. 10
13. Differentiate bagging and boosting. 5

Requirements of clustering in data mining easy 5 marks

1. Scalability: must work on millions of objects, not just a few hundred.
2. Ability to deal with different types of attributes: numeric, binary, nominal, ordinal, or mixtures.
3. Discovery of clusters with arbitrary shape: not just spherical clusters.
4. Minimal requirements for domain knowledge to determine input parameters (like k).
5. Ability to deal with noise and outliers.
6. Insensitivity to the order of input records.
7. High dimensionality: data may have hundreds of dimensions (sparse and skewed).
8. Constraint-based clustering: e.g. place ATMs considering rivers and highways.
9. Interpretability and usability of the results.

5.1 Types of data in cluster analysis syllabus point: do not skip

Two common data structures: the data matrix (n objects × p attributes, "two-mode") and the dissimilarity matrix (n × n triangular matrix of d(i,j), "one-mode"). Most clustering algorithms operate on the dissimilarity matrix, so the first job is to convert the data into distances.

5.2 The five major categories of clustering methods always asked

5.3 Partitioning methods

k-means numerical certain

1. Arbitrarily choose k objects as the initial cluster centres (means).
2. Assign each remaining object to the cluster with the nearest mean.
3. Recompute the mean of each cluster.
4. Repeat steps 2-3 until no object changes cluster / the criterion function converges.

k-medoids (PAM), CLARA and CLARANS

k-medoids uses the most centrally located actual object (the medoid) instead of the mean, which makes it far more robust to outliers. PAM (Partitioning Around Medoids) repeatedly tries replacing a medoid o_j by a non-medoid o_random and keeps the swap if the total cost S = E_new − E_old < 0. Cost per iteration is O(k(n−k)²), so PAM is not scalable.

• CLARA (Clustering LARge Applications) draws multiple samples of the data, applies PAM to each and returns the best clustering. Efficient, but the result depends on sample quality (a good medoid may never be sampled).
• CLARANS (Clustering Large Applications based upon RANdomized Search) draws a fresh random sample of neighbours at every step of the search, i.e. it searches a graph where each node is a set of k medoids. More effective than PAM and CLARA; can be improved with spatial index structures (R*-tree).

5.4 Hierarchical methods

• AGNES (AGglomerative NESting): bottom-up. Start with each object as its own cluster and merge the two closest clusters at each step, until all objects are in one cluster or a termination condition holds.
• DIANA (DIvisive ANAlysis): top-down. Start with all objects in one cluster and split at each step, until each object forms its own cluster.

5.5 Density-based methods

DBSCAN algorithm: pick an arbitrary unvisited point p; retrieve all points density-reachable from p using ε and MinPts. If p is a core object, a cluster is formed; if p is a border object with nothing density-reachable, DBSCAN moves on. Repeat until all points are visited. Complexity is O(n log n) with a spatial index (R*-tree), otherwise O(n²).

• Advantages: discovers clusters of arbitrary shape, handles noise explicitly, and does not need k in advance.
• Disadvantages: very sensitive to ε and MinPts, and it fails on data with widely varying density.
• OPTICS (Ordering Points To Identify the Clustering Structure) fixes the parameter problem by producing a cluster ordering with core-distance and reachability-distance, which represents the density-based clustering for a broad range of parameter settings at once (visualised as a reachability plot).
• DENCLUE (DENsity-based CLUstEring) models the overall density as the sum of influence functions (e.g. Gaussian) of each point; clusters are defined by density attractors: local maxima of the density function found by hill climbing. It has a solid mathematical foundation, is good for highly noisy data and is faster than DBSCAN, but needs careful choice of σ and ξ.

5.6 Grid-based methods

The object space is quantised into a finite number of cells forming a grid; all clustering is done on the grid. The main advantage is fast processing time, which depends only on the number of cells, not on the number of data objects.

• STING (STatistical INformation Grid) divides the space into rectangular cells at several levels of resolution, forming a hierarchy. Each cell stores precomputed statistical parameters: count, mean, standard deviation, min, max and the type of distribution. Queries are answered top-down: irrelevant cells are pruned using confidence intervals. Query time is O(g) where g is the number of grid cells at the lowest level, g ≪ n. Weakness: cluster boundaries are horizontal or vertical only, since it uses the axis-parallel grid.
• WaveCluster: imposes a grid, then applies a wavelet transform to the feature space; clusters appear as dense regions in the transformed space. It automatically removes outliers, is multi-resolution (a natural roll-up/drill-down), finds arbitrary shapes, and runs in O(n): but is effective only in low-dimensional space.
• CLIQUE (CLustering In QUEst) is both grid-based and density-based, designed for subspace clustering of high-dimensional data. It partitions each dimension into intervals, finds dense units in 1-D, then uses the Apriori principle (a k-dimensional dense unit must have dense (k−1)-dimensional projections) to build higher-dimensional dense units, and finally generates a minimal description of each cluster as DNF expressions. Insensitive to the input order, scales linearly with n, but accuracy may drop due to the simplicity of the method.

5.7 Model-based clustering

Each cluster is assumed to be generated by an underlying probability distribution or concept, and the algorithm finds the best fit between the data and the model. It gives a robust way of automatically determining the number of clusters, using statistics and noise/outlier tolerance.

• Expectation-Maximisation (EM): a generalisation of k-means in which each object is assigned to a cluster with a probability of membership (soft/fuzzy assignment) rather than exclusively. The data is modelled as a mixture of Gaussian distributions. Two steps iterate: E-step: compute the probability that each object belongs to each cluster; M-step: re-estimate the model parameters (mean, covariance, mixture weight) to maximise the expected likelihood. It converges to a local maximum; complexity is linear in the data size.
• COBWEB: an incremental conceptual clustering method for categorical data. It builds a classification tree whose nodes hold probabilistic descriptions of a concept, guided by the category utility measure, using operators insert, create, merge and split. Weaknesses: it assumes attributes are independent, the tree can be expensive in space and time, and it is not suited to skewed data. CLASSIT is its extension for continuous data; AutoClass is a Bayesian variant.
• SOM (Self-Organising Map): the neural-network approach described in Unit 4. Objects are mapped onto a 2-D grid of neurons that preserves the topology of the input space, so it is useful for clustering and visualisation of high-dimensional data (e.g. WEBSOM for web documents).

Outlier analysis often bundled with this unit

An outlier is a data object that is grossly different from or inconsistent with the remaining data. Four detection approaches:

1. Statistical (distribution-based): assume a distribution and use a discordancy test; objects with low probability are outliers. Requires knowing the distribution in advance and works mostly in single dimensions.
2. Distance-based: an object o is a DB(p, d)-outlier if at least a fraction p of the objects lie further than distance d from o. Algorithms: index-based, nested-loop, cell-based.
3. Density-based (local outlier): uses the local outlier factor (LOF), which compares the local density of an object with that of its neighbours, so it can find outliers within clusters of different densities.
4. Deviation-based: identifies outliers by examining the main characteristics of a group; the sequential exception technique uses a dissimilarity function and smoothing factor; the OLAP data cube approach flags deviating cells for drill-down.

5.8 Likely exam questions from this unit

1. What is cluster analysis? How does it differ from classification? List the requirements of clustering. 10
2. Explain the types of data in cluster analysis and how dissimilarity is computed for each. 10
3. Explain the k-means algorithm. Apply it to the given data set and show all iterations. 10-15
4. Differentiate k-means and k-medoids. Explain PAM, CLARA and CLARANS. 10
5. Explain agglomerative and divisive hierarchical clustering with a dendrogram. Explain BIRCH / CURE. 10
6. Explain DBSCAN with definitions of core object, density-reachable and density-connected. 10
7. Explain grid-based clustering: STING, WaveCluster and CLIQUE. 10
8. Explain model-based clustering: EM, COBWEB and SOM. 10
9. What are outliers? Explain the approaches to outlier detection. 5-10

6.1 Mining spatial databases

A spatial database stores data with spatial (geographic) attributes: points, lines, polygons, satellite images, maps, medical images. Spatial data mining is the extraction of knowledge, spatial relationships and other interesting patterns not explicitly stored in spatial databases.

Why is it harder than relational mining? Spatial data is huge, has complex data types, and carries implicit spatial relationships (adjacent, inside, close_to, intersects) that must be computed rather than looked up. Neighbours also influence each other, so objects are autocorrelated, violating the independence assumption of ordinary mining.

Techniques and tasks

• Spatial data cube and spatial OLAP: dimensions can be non-spatial (temperature = hot), spatial-to-non-spatial (a region generalised to "Nepal"), or spatial-to-spatial. Measures may be numerical or spatial (a collection of merged regions). Precomputing merged regions is costly, so on-line merging with pointers is used.
• Spatial association rules: of the form A ⇒ B [s %, c %] where the predicates are spatial, e.g. is_a(X, "school") ∧ close_to(X, "sports_centre") ⇒ close_to(X, "park") [0.5 %, 80 %]. Mining uses a progressive refinement approach: apply a rough, cheap spatial predicate (g_close_to, using MBR or R-tree approximation) first, then apply the expensive precise test only to the surviving candidates.
• Spatial classification and trend analysis: classify spatial objects using relevant neighbourhood attributes; spatial trend analysis detects changes of a non-spatial attribute as one moves away from a reference point (e.g. economic level decreasing with distance from Kathmandu).
• Spatial clustering: CLARANS, DBSCAN, STING and WaveCluster all originated in this area.
• Mining raster/image databases: generalisation-based mining of remote sensing images.

Applications: GIS, urban planning, environmental studies, epidemiology (mapping disease outbreaks), navigation and traffic, and marketing by geography.

6.2 Mining multimedia databases

A multimedia database stores images, audio, video and sequence data. Multimedia mining extracts patterns from such data, which is unstructured and very high-dimensional.

Main topics to write

• Similarity search: two families: description-based retrieval (using keywords, captions, size, creation time, which is labour intensive and subjective) and content-based retrieval (using the actual image content: colour histogram, texture, shape, edges). Content-based systems support image-sample-based queries (find images similar to a given one) and image feature specification queries (specify colour, texture, shape). Indexing uses the colour histogram, multi-feature composite signatures, and wavelet-based signatures, usually inside an R-tree or a similarity index.
• Multidimensional analysis: a MultiMediaMiner-style image data cube with dimensions such as size, width, height, Internet domain, colours, keywords, edge-orientation.
• Classification and prediction: e.g. classifying sky images or detecting tumours; decision trees are commonly used on extracted features.
• Mining associations in multimedia data: three categories: associations between image content and non-image content features; associations among image contents not related to spatial relationships; and associations among image contents related to spatial relationships (e.g. "if two circles are touching and of similar size, they are likely to be balls"). Progressive resolution refinement is used: mine at a coarse resolution first, then refine only the frequent candidates at higher resolution.
• Audio and video data mining: indexing motion, scene change detection, speech transcription; audio can also be used to present mined patterns (audio data mining).

6.3 Mining time-series and sequence data

(a) Trend analysis: the four components of a time series

1. Trend (long-term) movement: the general direction over a long period, found with the moving average, weighted moving average, or the least-squares/freehand method. A moving average of order n smooths the series and eliminates cyclic/seasonal variation, but it loses data at the ends and may be affected by outliers.
2. Cyclic movements: long-term oscillations about a trend line, which may or may not be periodic (business cycles).
3. Seasonal variations: nearly identical patterns that a series follows during corresponding months/seasons (sales rising during Dashain-Tihar). Quantified as a seasonal index; dividing by it gives deseasonalised data.
4. Irregular / random movements: sporadic motion due to chance events (strikes, earthquakes).

(b) Similarity search in time-series data

Unlike normal queries, similarity search looks for sequences that differ only slightly. Subsequence matching finds the sequences containing a short query pattern; whole sequence matching compares entire sequences. Typical steps: apply a transform to reduce dimensionality, using DFT (discrete Fourier transform) keeping only the first few coefficients, or DWT, then index the result in an R*-tree, and search. Preprocessing needed before comparison: offset translation, amplitude scaling, noise removal, time warping (DTW, dynamic time warping, handles sequences that run at different speeds).

(c) Sequential pattern mining name the algorithms

Finds frequent subsequences in a sequence database, e.g. customers who buy a laptop tend to buy a printer within 3 months. Given min_sup, a sequence is frequent if it occurs in at least that fraction of sequences. Algorithms: GSP (Apriori-based, candidate generate-and-test), SPADE (vertical format, ID-list joins) and PrefixSpan (pattern-growth, projected databases, generally the fastest). Constraint-based versions add duration, gap and event-folding window constraints. Periodicity analysis mines full, partial and cyclic periodic patterns.

Biological sequence analysis is a major application: alignment of DNA/protein sequences using BLAST and dynamic programming, plus hidden Markov models (HMM) with the forward, Viterbi and Baum-Welch algorithms.

6.4 Web mining draw the taxonomy

(a) Web content mining

Extracts useful information from page content. Includes automatic classification and clustering of documents, extraction of structured data from pages using wrappers, and building multilayered web information bases where layer 0 is the raw Web and higher layers hold progressively more generalised, structured descriptions.

(b) Web structure mining: PageRank and HITS

The insight: a hyperlink from page A to page B is an implicit endorsement of B by A, so the link graph encodes human judgement about page quality.

HITS (Hyperlink-Induced Topic Search) defines two mutually reinforcing scores: an authority is a page with many in-links from good hubs; a hub is a page that points to many good authorities. The scores are computed iteratively: a(p) = Σ h(q) over pages q linking to p, and h(p) = Σ a(q) over pages q that p links to, normalised each round until convergence (this is the principal eigenvector of the adjacency matrix). HITS is query-dependent; PageRank is query-independent and computed offline.

(c) Web usage mining

Mines web server logs, browser logs, proxy logs, cookies and click streams to discover user access patterns. The process has three phases:

1. Preprocessing: data cleaning (remove image/script requests, robots), user identification, session identification (usually a 30-minute timeout), path completion because of browser caching.
2. Pattern discovery: association rules ("70 % who visit /laptops also visit /printers"), sequential patterns of page visits, clustering of users or pages, classification of user profiles.
3. Pattern analysis: filter out uninteresting rules and present them via visualisation or an OLAP weblog cube.

Applications: personalisation and recommender systems, improving site structure and navigation, targeted advertising, prefetching and caching, e-commerce customer profiling, and fraud detection.

6.5 Text mining

The text mining pipeline

1. Text preprocessing: tokenisation, removal of stop words (the, is, of), stemming (computing/computer/computed → comput), case folding, and part-of-speech tagging.
2. Feature/term extraction and representation: build the vector space model: each document becomes a vector of term weights in a term-frequency matrix (bag of words).
3. Dimensionality reduction: remove terms with low discriminating power; Latent Semantic Indexing (LSI) using SVD, Locality Preserving Indexing (LPI), or probabilistic LSI.
4. Mining: document classification (naive Bayes, SVM, k-NN, association-based), document clustering (spectral, mixture model, k-means on the vectors), keyword-based association analysis, document summarisation, topic detection, sentiment analysis, and information extraction.
5. Evaluation and visualisation: precision, recall, F-score of the retrieved/labelled set.

Keyword-based, tagging-based and information-extraction-based approaches form a spectrum from simple to sophisticated. Modern systems also build document concept hierarchies so that text can be placed in a text cube and analysed with OLAP operations. Applications: spam filtering, plagiarism detection, sentiment/opinion mining, resume screening, biomedical literature mining, legal e-discovery and customer feedback analysis.

6.6 Likely exam questions from this unit

1. What is spatial data mining? Explain spatial data cubes, spatial association rules and progressive refinement. 10
2. Explain multimedia data mining. What is content-based retrieval? Explain multimedia association rules. 10
3. What is time-series data? Explain trend analysis and its four components. 10
4. Explain similarity search and sequential pattern mining in sequence databases. 10
5. What is web mining? Explain its three categories with examples. 10
6. Explain PageRank and HITS (hubs and authorities). 5-10
7. Explain the phases of web usage mining and its applications. 10
8. What is text mining? Explain the text mining process and the vector space model / TF-IDF. 10

The structure that scores

For a 10-mark question, plan roughly one and a half to two pages, in this order:

1. Definition (2-3 lines, underlined). Use the textbook wording.
2. Why / context (2 lines): the problem this concept solves.
3. Diagram, drawn with a pencil and ruler, fully labelled, with a caption "Fig: KDD process".
4. Main body in numbered points: each point starts with a bold keyword, then one or two sentences. Aim for 5-8 points.
5. Example or numerical: one small worked instance.
6. Advantages / limitations / comparison: two or three lines. This is where most students stop early and lose the last 2 marks.

Time budgeting for a 3-hour, 80-mark paper

• First 5 minutes: read all questions and mark the ones you know cold. Attempt those first, because momentum matters.
• Roughly 1.5 minutes per mark. A 10-mark question = 15 minutes, no more.
• Do the numericals early (Apriori, decision tree, naive Bayes, k-means) while you are fresh; they carry the most guaranteed marks.
• Leave 10 minutes at the end to add diagrams or headings to any answer that looks thin.
• Never leave a question blank; a definition plus a diagram still earns 3-4 out of 10.

Revise only this on the morning of the exam.

You have attended one class. This is the order that gets you from nothing to confident, spending about three focused hours a day.