Data Warehousing and Data Mining

MOLAP versus ROLAP

MOLAP (multidimensional OLAP) stores the data in multidimensional arrays (cubes); ROLAP (relational OLAP) keeps it in relational tables and builds the multidimensional view with SQL.

• Advantage of MOLAP over ROLAP: Query response is much faster, because aggregates are pre-computed and the cube is accessed directly by array indexing, with no joins or run-time aggregation.
• Disadvantage of MOLAP over ROLAP: It scales poorly. The cube becomes sparse and very large as the number of dimensions and the cardinality of the dimensions grow, and it cannot handle very large volumes of detailed data as ROLAP (which uses the relational database) can. It also needs a separate proprietary storage engine and a loading step.

Signed network and balance

A signed network is a graph $G=(V,E)$ in which every edge carries a sign, $+$ (friendship, trust, agreement) or $-$ (enmity, distrust, disagreement). Examples are social networks with friends and foes, or user ratings that trust or distrust other users.

Structural balance. A signed network is balanced if the following equivalent conditions hold (Harary's theorem):

1. Every cycle contains an even number of negative edges (the product of the signs on every cycle is $+$).
2. The vertices can be divided into two groups (one possibly empty) such that all edges inside a group are positive and all edges between the groups are negative.

This reflects the rules "a friend of my friend is my friend" and "an enemy of my enemy is my friend".

How to check:

1. Delete the negative edges and find the connected components using only the positive edges. Contract each component to one super-node (all the nodes inside it must be on the same side).
2. If any negative edge has both its end points inside the same component, the network is not balanced.
3. Otherwise, build the graph of components joined by the negative edges and try to two-colour it using BFS or DFS. If it is two-colourable, the network is balanced; if an odd cycle is found, it is not balanced.

Example: nodes $A,B,C$ with $A$-$B$ positive, $B$-$C$ positive, $A$-$C$ negative. The positive edges put $A,B,C$ in one component, and the negative edge $A$-$C$ lies inside it, so the triangle has one negative edge (odd) and is unbalanced. If $A$-$C$ were positive, or if two edges were negative, the triangle would be balanced.

Beam search and space complexity

Beam search is a heuristic search that expands the search tree level by level like breadth-first search, but at each level keeps only the best $k$ candidates (the beam width) according to a scoring function, and discards the rest. Best-first or breadth-first search keeps all the nodes of a level, which grows as $O(b^d)$ for branching factor $b$ and depth $d$. Beam search keeps at most $k$ nodes per level, so the memory is $O(k\cdot d)$ (or $O(k\cdot b)$ if only the current frontier is stored), which is linear in the depth instead of exponential. The price is that it is not complete or optimal, because the best path may be pruned.

In data mining it is used in rule learning such as the CN2 algorithm, and in decision-tree or sequence decoding, where it avoids evaluating all possible conditions.

Example. Learn a rule for the class "Yes" with beam width $k=2$ from candidate conditions, each scored by accuracy on the training data.

• Level 1: conditions A (score 0.6), B (0.8), C (0.5), D (0.7). Keep the best 2: B (0.8) and D (0.7). A and C are discarded.
• Level 2: only extend B and D with the other conditions: B&A (0.85), B&C (0.9), D&A (0.75), D&C (0.7), and so on. Keep the best 2: B&C (0.9) and B&A (0.85).
• Continue until no improvement is possible.

With full breadth-first search, all the $4\times 3 = 12$ pairs and later all triples would be kept in memory; with the beam, at most 2 partial rules are carried to the next level, so memory is bounded by $k$ at each level.

Concept hierarchy in extracting information

A concept hierarchy is a sequence of mappings from low-level (specific) concepts to higher-level (more general) concepts for an attribute or dimension. For example, for location: $street < city < province < country$; for time: $day < month < quarter < year$; for age: $0\text{-}12 \to$ child, $13\text{-}19 \to$ teen, and so on.

It is used in extracting information in these ways:

• Roll-up and drill-down in OLAP: Rolling up moves up the hierarchy (city to country) to summarise data; drilling down moves to finer detail.
• Data generalisation and summarisation: Attribute-oriented induction replaces low-level values by higher-level concepts and merges identical tuples, giving a compact summary (a characteristic rule).
• Multilevel association rule mining: Rules can be mined at several levels of abstraction, e.g. "milk $\Rightarrow$ bread" at a higher level when "Dairy Gold milk $\Rightarrow$ Brown bread" is too rare to reach the minimum support. Support thresholds can be reduced at lower levels.
• Discretisation of numeric attributes into intervals, and handling of data at the level the user needs, hiding unnecessary detail.

FP-growth with minimum support = 3

The data set of the question is not printed in the text, so the standard transaction set of this exercise is used:

Step 1: Count the items (first scan). $f:4,\ c:4,\ a:3,\ b:3,\ m:3,\ p:3$. All the others (d, g, i, l, o, h, j, k, s, e, n) have count less than 3 and are dropped.

Step 2: Order each transaction by descending support ($f, c, a, b, m, p$):

Step 3: Build the FP-tree.

root
 +-- f:4
 |    +-- c:3
 |    |    +-- a:3
 |    |         +-- m:2
 |    |         |    +-- p:2
 |    |         +-- b:1
 |    |              +-- m:1
 |    +-- b:1
 +-- c:1
      +-- b:1
           +-- p:1

Step 4: Conditional pattern bases and mining (from the least frequent item upward):

Frequent patterns (18): f, c, a, b, m, p, {c,p}, {f,m}, {c,m}, {a,m}, {f,c,m}, {f,a,m}, {c,a,m}, {f,c,a,m}, {f,a}, {c,a}, {f,c,a}, {f,c}.

The largest frequent itemset is {f, c, a, m} with support 3.

Comparing two classifiers

Two classifiers $M_1$ and $M_2$ are compared on the same data, by estimating their performance in a reliable way and by checking whether the difference is real or due to chance.

1. Estimate the accuracy (or error) with a proper evaluation method. Use a hold-out test set, $k$-fold cross-validation (e.g. 10-fold, with both models tested on the same folds), or bootstrap, so that the evaluation is not on the training data.
2. Use several measures, not only accuracy: the confusion matrix, precision, recall, F-measure, specificity, and especially for imbalanced data. Also compare speed, scalability, robustness to noise and interpretability.
3. Test statistical significance. With 10-fold cross-validation, take the error rates $err(M_1)_i$ and $err(M_2)_i$ of each fold and use a paired $t$-test with $k-1$ degrees of freedom:

$t=\frac{\overline{err}(M_1)-\overline{err}(M_2)}{\sqrt{\operatorname{var}(M_1-M_2)/k}}$

If $|t|$ is greater than the critical value for the chosen significance level (for example 5 %), the difference is statistically significant; otherwise the two models are not significantly different. 4. ROC curves. Plot the true positive rate against the false positive rate for each classifier; the model whose curve is closer to the top left, i.e. with the larger area under the curve (AUC), is better.

DBSCAN with Eps = 2.5 and MinPts = 3

Rule: a point is a core point if its Eps-neighbourhood (including the point itself) has at least 3 points; a border point is not a core but lies within Eps of a core point; a point that is neither is an outlier (noise).

Points: A(3,7), B(4,6), C(5,5), D(6,4), E(7,3), F(6,2), G(7,2), H(8,4).

Distances $\le 2.5$ (Euclidean), using $d=\sqrt{\Delta x^2+\Delta y^2}$:

• A-B: $\sqrt{1+1}=1.41$; A-C: $\sqrt{4+4}=2.83$; A to all others is larger.
• B-C: $1.41$; B-D: $\sqrt{4+4}=2.83$.
• C-D: $1.41$; C-E: $\sqrt{4+4}=2.83$.
• D-E: $1.41$; D-F: $2$; D-G: $\sqrt{1+4}=2.24$; D-H: $2$.
• E-F: $1.41$; E-G: $1$; E-H: $1.41$.
• F-G: $1$; F-H: $\sqrt{4+4}=2.83$.
• G-H: $\sqrt{1+4}=2.24$.

Neighbourhoods (within 2.5, including the point itself):

Result

• Core points: B, C, D, E, F, G, H.
• Border points: A (it has fewer than 3 points in its neighbourhood, but it lies within Eps of the core point B).
• Outliers (noise): none.

All the core points are density-connected through B-C-D-E, so they form a single cluster {A, B, C, D, E, F, G, H}.

Interesting pattern. A pattern is said to be interesting if it is (1) easily understood by humans, (2) valid on new or test data with some degree of certainty, (3) potentially useful, and (4) novel (or it validates a hypothesis the user wanted to confirm). Interestingness can be measured objectively (support, confidence, lift, accuracy) or subjectively (unexpectedness, actionability). A pattern is also interesting when it represents knowledge, that is, it is not trivially known already.

Issues in data mining

1. Mining methodology issues
   • Mining different kinds of knowledge (characterization, association, classification, clustering, outlier analysis) in the same database.
   • Interactive mining at multiple levels of abstraction (drill-down, roll-up).
   • Incorporation of background knowledge and domain constraints.
   • Handling noisy, incomplete and uncertain data, and pattern evaluation (interestingness).
2. Performance issues
   • Efficiency and scalability of algorithms for very large databases.
   • Parallel, distributed and incremental mining algorithms.
3. User interaction issues
   • Data mining query languages and ad hoc mining.
   • Effective presentation and visualization of results.
4. Diversity of data types
   • Handling relational, complex (spatial, multimedia, text, time-series) data.
   • Mining from heterogeneous databases and the web.
5. Social issues
   • Privacy protection, data security and misuse of discovered knowledge.

Data discretization. Discretization is a data reduction/transformation technique that divides the range of a continuous attribute into intervals and replaces the raw values by interval labels (e.g. age 0-18, 19-60, 60+) or concept labels (young, adult, senior). It reduces the number of distinct values, makes data easier to interpret and is needed by algorithms that accept only categorical input. Methods include binning (equal-width, equal-frequency), histogram analysis, clustering, decision-tree (entropy-based) and correlation ($\chi^2$) based discretization.

Tasks of data preprocessing

1. Data cleaning - fill in missing values (ignore tuple, global constant, mean/median, most probable value), smooth noisy data (binning, regression, clustering), identify outliers and resolve inconsistencies.
2. Data integration - combine data from multiple sources; handle schema integration, entity identification and redundancy (detected by correlation analysis), and conflicts in attribute values.
3. Data transformation - normalization (min-max, z-score, decimal scaling), smoothing, aggregation, generalization, attribute construction and discretization.
4. Data reduction - obtain a smaller representation giving similar results: dimensionality reduction (PCA, wavelets), numerosity reduction (sampling, histograms, clustering), data cube aggregation and data compression.

Spatial data mining. Spatial data mining is the discovery of interesting, implicit and previously unknown patterns from spatial data, i.e. data related to space such as maps, satellite images, GIS layers, road networks and geographic coordinates. It finds spatial relationships (topological, distance, direction), spatial clusters, spatial association rules (e.g. "houses near a river are expensive"), spatial classification and spatial outliers.

Challenges of multimedia mining

• Heterogeneous, unstructured data: images, audio, video and text have very different formats and must be combined.
• High dimensionality and huge volume: feature vectors from images and video are large, which makes storage and processing costly.
• Semantic gap: low-level features (colour, texture, shape, pitch) do not map easily to high-level human concepts.
• Feature extraction and representation: choosing features that are robust to scale, rotation, noise and lighting.
• Similarity search and indexing: content-based retrieval needs suitable similarity measures and index structures.
• Temporal and spatial relations: video and audio have time ordering that must be modelled.
• Noise, missing data and subjectivity of interpretation, and privacy/copyright issues.

Example. In content-based image retrieval, a user supplies a photo of a sunset. The system extracts colour histograms and texture features, compares them with those of stored images by a distance measure and returns the similar images. Because the colour histogram of a red flower can look like a sunset, the semantic gap causes wrong matches, and millions of high-dimensional feature vectors make the search slow without indexing.

Use the naive Bayes classifier: choose the class $C$ maximizing $P(C)\,\prod_i P(x_i\mid C)$.

Let $X$ = (Confident = Yes, Sick = No). There are 5 tuples: Fail = 2, Pass = 3.

$P(\text{Fail}) = \tfrac25,\qquad P(\text{Pass}) = \tfrac35$

Class Fail (tuples 1 and 3):

• $P(\text{Confident=Yes}\mid\text{Fail}) = 1/2$
• $P(\text{Sick=No}\mid\text{Fail}) = 1/2$

$P(X\mid\text{Fail})P(\text{Fail}) = \tfrac12\cdot\tfrac12\cdot\tfrac25 = 0.1$

Class Pass (tuples 2, 4, 5):

• $P(\text{Confident=Yes}\mid\text{Pass}) = 2/3$
• $P(\text{Sick=No}\mid\text{Pass}) = 1/3$

$P(X\mid\text{Pass})P(\text{Pass}) = \tfrac23\cdot\tfrac13\cdot\tfrac35 = 0.1333$

Since $0.1333 > 0.1$ (normalized: Pass = 57.1%, Fail = 42.9%), the object is classified as Pass.

Choices for data cube materialization. For a cube with $n$ dimensions there are $2^n$ cuboids (more with hierarchies). There are three choices:

1. No materialization - compute no non-base cuboid; every query is computed on the fly from the base cuboid. Storage is minimal but query response is extremely slow.
2. Full materialization - precompute all cuboids. Queries are fastest, but the storage and computation cost is huge (the cube may explode in size, especially for sparse data).
3. Partial materialization - materialize only a selected subset of cuboids (e.g. those most frequently used, chosen by a benefit/cost heuristic such as greedy view selection), or only cells above a minimum support (iceberg cube). This balances storage, build time and query speed and is the practical choice.

Strategies for cube computation

• Sorting, hashing and grouping: sort or hash tuples on the dimension attributes so aggregates for a group are computed together.
• Simultaneous aggregation and caching intermediate results: compute several cuboids at once while the data is in memory; a lower-dimensional cuboid is computed from an already computed parent (e.g. from $ABC$ get $AB$) rather than from the base table.
• Aggregation from the smallest child: compute a cuboid from the smallest already computed parent to reduce I/O.
• Multiway array aggregation (MOLAP): partition the array into chunks and compute all cuboids in one scan, ordering the dimensions by size to minimize memory.
• BUC (bottom-up construction): build an iceberg cube from the apex downward, partitioning on dimensions and pruning partitions below the minimum support (Apriori-style pruning).
• Star-Cubing / Shell fragments: use a star-tree for iceberg cubes, or precompute only small groups of dimensions for high-dimensional data.

Balance and status theory (social network analysis). Structural balance theory (Heider) states that a signed triangle of relations is stable (balanced) if the product of the three signs is positive: "a friend of my friend is my friend" and "an enemy of my enemy is my friend". The triangle (+,+,+) or (+,-,-) is balanced, while (+,+,-) and (-,-,-) are unbalanced and tend to change. It treats the signs as symmetric and undirected.

Status theory (Leskovec et al.) treats a directed link as a statement of status: a positive link $A\to B$ means B has higher status than A, and a negative link means B has lower status. A triangle is consistent if the statuses can be ordered without contradiction.

Conflict. Take three users with directed links $A\to B$ negative, $B\to C$ negative and $A\to C$ negative (triangle $-,-,-$).

• Balance theory: the product of signs is negative, so the triangle is unbalanced and expected to change (two of the three enemies should become friends).
• Status theory: $A\to B$ negative means B has lower status than A; $B\to C$ negative means C is lower than B; so C is lower than A, and a negative link $A\to C$ is exactly what is expected. The triangle is consistent.

So the same triangle is unstable under balance theory but stable under status theory. Empirically, balance explains undirected, symmetric relations (friendship) while status explains directed ones (endorsement, voting).

Improving Apriori

• Hash-based itemset counting: hash candidate $k$-itemsets into buckets while scanning; buckets with count below minimum support are discarded, shrinking the candidate set (especially $C_2$).
• Transaction reduction: a transaction with no frequent $k$-itemset cannot contain frequent $(k+1)$-itemsets, so it is removed from later scans.
• Partitioning: divide the database into partitions; any globally frequent itemset must be frequent in at least one partition, so only two scans are needed.
• Sampling: mine a random sample with a lowered support threshold, then verify in the full database.
• Dynamic itemset counting: add new candidate itemsets at checkpoints during a scan.
• Alternatives that avoid candidate generation: FP-growth and Eclat (vertical format).

Star schema vs snowflake schema

Two methods of data normalization

1. Min-max normalization: maps a value $v$ of attribute $A$ to a new range $[new\_min, new\_max]$: $v' = \frac{v-\min_A}{\max_A-\min_A}(new\_max-new\_min)+new\_min$
2. Z-score normalization: uses the mean $\bar A$ and standard deviation $\sigma_A$: $v' = \frac{v-\bar A}{\sigma_A}$

(Decimal scaling, $v' = v/10^j$ with the smallest $j$ giving $\max|v'|<1$, is another.)

Evaluating classifier accuracy. Accuracy is the fraction of test tuples correctly classified, measured on data not used for training (otherwise the estimate is over-optimistic): $\text{Accuracy} = \frac{TP+TN}{P+N}$ Other measures from the confusion matrix are error rate, precision, recall (sensitivity), specificity and F-measure. Methods for estimating accuracy:

• Holdout: randomly split the data, typically 2/3 for training and 1/3 for testing. Random subsampling repeats this and averages the accuracy.
• Cross-validation: described below.
• Bootstrap: sample $n$ tuples with replacement for training; the tuples not selected (about 36.8%) form the test set. The .632 bootstrap combines the results.
• Also ROC curves and the area under the curve for comparing classifiers.

K-fold cross-validation. The data are partitioned into $k$ mutually exclusive folds of about equal size. In iteration $i$ the $i$-th fold is the test set and the remaining $k-1$ folds are the training set. The accuracy is the average over the $k$ runs (total correct classifications over all folds divided by the number of tuples). Usually $k=10$.

Advantages

• Every tuple is used for both training and testing, with each tuple tested exactly once, so no data are wasted (useful for small data sets).
• The estimate has lower variance and less bias than a single holdout split and is less dependent on how the data are divided.
• It gives a more reliable basis for model selection and parameter tuning, and for comparing classifiers.
• Stratified folds keep the class distribution the same in each fold.

Points: $A(185,72)$, $B(170,56)$, $C(168,60)$, $D(179,68)$, $E(182,72)$, $F(188,77)$. Initial centroids: $c_1=A=(185,72)$, $c_2=B=(170,56)$. Distance is Euclidean.

Iteration 1

Cluster 1 = {A, D, E, F}, Cluster 2 = {B, C}.

New centroids: $c_1=\left(\tfrac{185+179+182+188}{4},\tfrac{72+68+72+77}{4}\right)=(183.5,\,72.25)$ $c_2=\left(\tfrac{170+168}{2},\tfrac{56+60}{2}\right)=(169,\,58)$

Iteration 2

No point changes cluster, and the centroids stay $(183.5,72.25)$ and $(169,58)$, so the algorithm has converged.

Final clusters: Cluster 1 = {(185,72), (179,68), (182,72), (188,77)}; Cluster 2 = {(170,56), (168,60)}.

Drawbacks of Apriori

1. It generates a huge number of candidate itemsets (e.g. $10^4$ frequent 1-itemsets give more than $10^7$ candidate 2-itemsets), which costs memory and time.
2. It scans the database repeatedly, once for every itemset length $k$, so I/O cost is high, especially for long patterns.

FP-growth. Number of transactions = 6, so minimum support count = $0.5\times6=3$. Let S = Sausage, P = Peanut, B = Beer, A = Apple, M = Milk.

Item counts: P = 5, S = 4, B = 4, A = 4, M = 2. Milk is infrequent and is dropped. Order of items (descending count): P, S, B, A.

Ordered transactions:

1. P, S, B
2. P, B, A
3. A
4. P, S, A
5. P, S, B
6. P, S, B, A

FP-tree (item:count)

• root
  • P:5
    • S:4
      • B:3
        • A:1 (from T6)
      • A:1 (from T4)
    • B:1
      • A:1 (from T2)
  • A:1 (from T3)

Conditional pattern bases and frequent patterns (processing from the least frequent item)

Frequent itemsets: {P}:5, {S}:4, {B}:4, {A}:4, {P,S}:4, {P,B}:4, {S,B}:3, {P,A}:3, {P,S,B}:3.

Association rules (minimum confidence 60%)

All the rules listed meet the 60% threshold.

When an MLP is the better choice. A multilayer perceptron (with hidden layers and non-linear activation) is preferred when the classes are not linearly separable (e.g. XOR), when the relationship between inputs and output is complex and non-linear, when there are many inputs and plenty of training data, when the data are noisy (it tolerates noise and can classify unseen patterns), when no explicit rules or probability model are known, and when long training time and low interpretability are acceptable. It handles continuous and multi-class outputs and can approximate any continuous function.

Back-propagation. Network: inputs 1, 2; hidden units 3, 4; output unit 5. Learning rate $\eta=0.5$, sigmoid $O=1/(1+e^{-net})$.

Formulas: output error $\delta_5=O_5(1-O_5)(T-O_5)$; hidden error $\delta_j=O_j(1-O_j)\,\delta_5\,w_{j5}$; $w_{ij}\leftarrow w_{ij}+\eta\,\delta_j O_i$; $b_j\leftarrow b_j+\eta\,\delta_j$.

Tuple 1: $(x_1,x_2,T)=(1,1,0)$

Forward pass: $net_3=0.5(1)-0.3(1)+0.6=0.8\Rightarrow O_3=0.6900$ $net_4=0.2(1)+0.5(1)-0.4=0.3\Rightarrow O_4=0.5744$ $net_5=0.1(0.6900)+0.3(0.5744)+0.8=1.0413\Rightarrow O_5=0.7391$

Errors: $\delta_5=0.7391(0.2609)(0-0.7391)=-0.1425$ $\delta_3=0.6900(0.3100)(-0.1425)(0.1)=-0.00305$ $\delta_4=0.5744(0.4256)(-0.1425)(0.3)=-0.01045$

Updates:

Tuple 2: $(x_1,x_2,T)=(0,1,1)$ using the updated weights

Forward pass: $net_3=0(0.4985)+1(-0.3015)+0.5985=0.2970\Rightarrow O_3=0.5737$ $net_4=0(0.1948)+1(0.4948)-0.4052=0.0896\Rightarrow O_4=0.5224$ $net_5=0.0508(0.5737)+0.2591(0.5224)+0.7287=0.8932\Rightarrow O_5=0.7096$

Errors: $\delta_5=0.7096(0.2904)(1-0.7096)=0.0599$ $\delta_3=0.5737(0.4263)(0.0599)(0.0508)=0.00074$ $\delta_4=0.5224(0.4776)(0.0599)(0.2591)=0.00387$

Updates:

Final weights after both tuples: $w_{13}=0.4985$, $w_{14}=0.1948$, $w_{23}=-0.3012$, $w_{24}=0.4967$, $w_{35}=0.0680$, $w_{45}=0.2747$, $b_3=0.5988$, $b_4=-0.4033$, $b_5=0.7587$.

Why OLAP operations are used. OLAP (Online Analytical Processing) operations let decision makers view and analyse multidimensional data interactively and from different perspectives. They support fast, flexible exploration of summarized data in a data warehouse (trends, comparisons, drill into exceptions) without writing complex queries, so they help in reporting, forecasting and decision support.

Consider a sales cube with dimensions Time (day < month < quarter < year), Location (city < country) and Item (item < category), with measure sales.

1. Roll-up (drill-up) - aggregate data by climbing a concept hierarchy or by dimension reduction. Example: move from city to country, so sales of Kathmandu and Pokhara are summed to give sales of Nepal; or aggregate quarters into years.
2. Drill-down - the reverse; go from summarized to more detailed data by stepping down a hierarchy or adding a dimension. Example: from quarterly sales to monthly sales, or from country to city.
3. Slice - select one value of one dimension, giving a sub-cube of one lower dimension. Example: Time = "Q1" gives a Location x Item table for the first quarter.
4. Dice - select values on two or more dimensions, giving a sub-cube. Example: (Location = Kathmandu or Pokhara) and (Time = Q1 or Q2) and (Item = Mobile or Laptop).
5. Pivot (rotate) - rotate the axes of the display to give an alternative view. Example: swap rows (Item) and columns (Location) of a 2-D table.
6. Other operations: drill-across (query involving more than one fact table) and drill-through (go down to the back-end relational tables), and ranking/top-N or difference operations.

Without concept hierarchies. For an $n$-dimensional data cube, every subset of the dimensions forms one cuboid (including the base cuboid with all dimensions and the apex cuboid with none), so the number of cuboids is $2^n = 2^5 = 32.$

With hierarchies. If dimension $i$ has $L_i$ levels, the total number of cuboids is $T=\prod_{i=1}^{n}(L_i+1)$ where the extra 1 is for the virtual top level "all". With $n=5$ and $L_i=5$ for every dimension: $T=(5+1)^5=6^5=7776.$

An attribute is a data field representing a characteristic of an object. Attribute types:

1. Nominal - categories or names with no meaningful order; only equality can be tested (mode is the central tendency). Examples: hair colour (black, brown), marital status, district name.
2. Binary - a nominal attribute with only two states, 0 and 1. It is symmetric if both outcomes are equally important (gender: male/female) and asymmetric if not (medical test: positive/negative, where positive is the rarer, more important outcome).
3. Ordinal - values have a meaningful order or rank but the magnitude of difference between values is unknown. Examples: grade (A, B, C), size (small, medium, large), rating 1-5. Median and mode apply.
4. Numeric - quantitative values.
   • Interval-scaled: measured on a scale with equal units but no true zero; differences are meaningful but ratios are not. Examples: temperature in Celsius, calendar year, dates.
   • Ratio-scaled: has an inherent zero point, so ratios make sense. Examples: weight, height, income, age, temperature in Kelvin.

Attributes can also be classified as discrete (finite or countably infinite values, e.g. number of students, zip code) or continuous (real numbers, e.g. height, temperature).

Importance of normalization. Attributes in a data set often have different units and ranges (e.g. income in thousands, age in tens). Distance-based methods such as k-NN and k-means, and neural networks and gradient-based methods, would let large-valued attributes dominate. Normalization scales attributes to a common range so that every attribute contributes equally, speeds up convergence of training, improves accuracy and makes distance and similarity measures meaningful.

Min-max normalization. A linear transformation of the original range $[\min_A,\max_A]$ to $[new\_min_A,new\_max_A]$: $v'=\frac{v-\min_A}{\max_A-\min_A}\,(new\_max_A-new\_min_A)+new\_min_A$ It preserves the relationships among the original values. It fails if a future value falls outside the original range, and is sensitive to outliers.

Example: income range Rs 12,000 to Rs 98,000 mapped to $[0,1]$; Rs 73,600 becomes $\frac{73600-12000}{98000-12000}=\frac{61600}{86000}=0.716$.

Z-score (zero-mean) normalization. The values are based on the mean $\bar A$ and standard deviation $\sigma_A$: $v'=\frac{v-\bar A}{\sigma_A}$ The result has mean 0 and standard deviation 1. It is useful when the true minimum and maximum are unknown or outliers dominate.

Example: with $\bar A=54{,}000$ and $\sigma_A=16{,}000$, Rs 73,600 becomes $\frac{73600-54000}{16000}=1.225$.

Two categories of hierarchical clustering

1. Agglomerative (bottom-up): start with each object as its own cluster and repeatedly merge the two closest clusters until one cluster (or the required number $k$) remains.
2. Divisive (top-down): start with all objects in one cluster and repeatedly split a cluster until each object is separate (or $k$ clusters are obtained).

Agglomerative clustering (Euclidean distance, complete linkage; cluster distance = maximum pairwise distance). Points: $A(2,10)$, $B(2,5)$, $C(8,4)$, $D(5,8)$, $E(7,5)$, $F(6,4)$.

Pairwise distances:

• Step 1: smallest distance is 1.41 (C,E; E,F also 1.41). Merge C and E into {C,E}.
• Step 2: distance {C,E} to F = max(2.24, 1.41) = 2.24, the smallest. Merge to {C,E,F}.
• Step 3: next smallest is A-D = 3.61. Merge to {A,D}.
• Step 4: remaining distances are {A,D}-B = max(5.00, 4.24) = 5.00, B-{C,E,F} = max(6.08, 5.00, 4.12) = 6.08 and {A,D}-{C,E,F} = 8.49. Merge {A,D} and B into {A,B,D}.

Now two clusters remain, so stop:

Cluster 1 = {(2,10), (2,5), (5,8)}, Cluster 2 = {(8,4), (7,5), (6,4)}.

(The dendrogram merges: C+E at 1.41, +F at 2.24, A+D at 3.61, +B at 5.00, and the last merge at 8.49.)

Problem with K-means. Standard K-means picks the initial centroids at random, so a poor choice (e.g. two centroids in the same natural cluster) can give a bad local minimum and slow convergence. Also each iteration passes over the entire data set, which is expensive for large data.

K-means++. An initialization method that spreads out the initial centroids:

1. Choose the first centroid $c_1$ uniformly at random from the data points.
2. For each point $x$, compute $D(x)$, the distance to the nearest centroid already chosen.
3. Choose the next centroid from the data points with probability proportional to $D(x)^2$ (far points are more likely).
4. Repeat steps 2-3 until $k$ centroids are chosen, then run normal K-means.

Result: better and more stable clusterings, faster convergence, and an expected cost within $O(\log k)$ of the optimum.

Mini-batch K-means. A variant for very large data sets. Instead of using all points in each iteration, it uses small random subsets (mini-batches):

1. Initialize $k$ centroids (e.g. by K-means++).
2. Draw a random mini-batch of $b$ points and assign each to its nearest centroid.
3. Update each centroid as a running average of the points assigned to it, using a per-centroid learning rate $1/n_c$ ($n_c$ = number of points seen so far by that centroid): $c \leftarrow (1-\tfrac1{n_c})c+\tfrac1{n_c}x$.
4. Repeat until convergence or a fixed number of iterations.

Result: much lower computation time and memory (suits streaming/online data), at the cost of slightly worse cluster quality than full K-means.

Confusion matrix. A table that summarizes the performance of a classifier by comparing the predicted classes with the actual classes. For two classes (positive/negative):

Here $P=TP+FN$ and $N=FP+TN$ are the numbers of actual positive and negative tuples.

Classification measures

• Accuracy (recognition rate): $\dfrac{TP+TN}{TP+TN+FP+FN}$
• Error rate: $\dfrac{FP+FN}{TP+TN+FP+FN}=1-\text{Accuracy}$
• Precision: $\dfrac{TP}{TP+FP}$ - fraction of predicted positives that are really positive.
• Recall (sensitivity, true positive rate): $\dfrac{TP}{TP+FN}$ - fraction of actual positives that are found.
• Specificity (true negative rate): $\dfrac{TN}{TN+FP}$
• F1-score: $\dfrac{2\cdot\text{Precision}\cdot\text{Recall}}{\text{Precision}+\text{Recall}}$ - harmonic mean of precision and recall.
• F-beta: $\dfrac{(1+\beta^2)\,\text{Precision}\cdot\text{Recall}}{\beta^2\,\text{Precision}+\text{Recall}}$

Accuracy is misleading when classes are imbalanced (e.g. 99% negative), where precision, recall and F1 are better.

Application areas of graph mining

• Chemical informatics: finding frequent substructures in molecules, predicting toxicity or activity of compounds, drug discovery.
• Bioinformatics: protein-interaction networks, gene regulatory and metabolic networks.
• Social network analysis: community detection, influence analysis, link prediction, spam/fraud detection.
• Web and text mining: web link structure, page ranking, document and citation graphs.
• Computer vision and pattern recognition: matching and indexing of image graphs.
• Network traffic and cyber security, transport networks and software engineering (program flow graphs, bug detection).

Inductive logic programming (ILP). ILP is a branch of machine learning that learns logic programs (first-order rules, e.g. Prolog clauses) from examples and background knowledge. Given

• positive examples $E^+$, negative examples $E^-$ and background knowledge $B$,

it induces a hypothesis $H$ (a set of rules) such that $B\wedge H\models E^+$ (covers all positive examples) and $B\wedge H\not\models E^-$ (covers no negative example). Because it uses relational logic, it can learn from multi-relational and graph data without flattening them into a single table.

Demonstration (family relation). Background knowledge: parent(ann, mary), parent(mary, tom), parent(ann, joe), female(ann), female(mary), male(tom), male(joe). Positive examples: grandparent(ann, tom). Negative examples: grandparent(ann, mary), grandparent(tom, ann).

The learner starts from the most general clause grandparent(X,Y) :- true, which covers the negatives, and specializes it by adding literals chosen by a coverage score. Adding parent(X,Z) and parent(Z,Y) gives $\text{grandparent}(X,Y) \leftarrow \text{parent}(X,Z),\ \text{parent}(Z,Y)$ This covers the positive example (Z = mary) and no negative example, so it is accepted as the learned rule.

Concept. Text mining (text analytics) is the process of extracting useful, previously unknown patterns and knowledge from unstructured or semi-structured text such as documents, emails, web pages, reviews and social media. Because text has no fixed schema, it first has to be converted to a structured form, then analysed with data mining methods.

Typical process

1. Collect documents.
2. Preprocessing: tokenization, stop-word removal, stemming/lemmatization, part-of-speech tagging.
3. Representation: bag of words, TF-IDF vectors (term weight $tf\cdot\log\frac{N}{df}$), n-grams or word embeddings.
4. Feature selection and dimensionality reduction (e.g. LSA).
5. Apply mining: classification, clustering, association, information extraction, summarization, topic modelling.
6. Evaluate and interpret the results.

Practical implications / applications

• Spam filtering and email categorization (classification).
• Sentiment analysis and opinion mining of product reviews and tweets for business and politics.
• Information retrieval and search engines, document clustering and topic detection.
• Customer support: automatic routing of complaints, chatbots.
• Healthcare and legal: extraction of facts from clinical notes and case documents.
• Plagiarism detection, news summarization, fraud detection.

Challenges include ambiguity of natural language, multiple languages (including Nepali), sarcasm, and the high dimensionality and sparsity of text data.

1. Data Mart

A data mart is a small, subject-oriented subset of a data warehouse focused on one department or business function, such as sales, marketing or finance. It gives a particular group of users quick access to the data they need.

• Dependent data marts are built from the enterprise data warehouse; independent data marts are built directly from operational sources or external data.
• Advantages: smaller size, faster queries, lower cost and shorter implementation time, easier to manage and secure, and tailored to a user group.
• Disadvantages: if independent marts are built separately, data may be inconsistent and difficult to integrate.

2. Market Basket Analysis

Market basket analysis finds associations between items that customers buy together in the same transaction, using association rule mining (Apriori, FP-growth). A rule $X\Rightarrow Y$ is measured by $\text{support}=\frac{\#(X\cup Y)}{N},\qquad \text{confidence}=\frac{\text{support}(X\cup Y)}{\text{support}(X)}$ and lift $=\dfrac{\text{confidence}(X\Rightarrow Y)}{\text{support}(Y)}$.

Example: {bread, butter} => {milk} with support 20% and confidence 70% means 20% of all baskets contain all three, and 70% of the baskets with bread and butter also contain milk. Uses: shelf arrangement and cross-selling, promotions and bundling, catalogue design and inventory planning.

Apriori property. All non-empty subsets of a frequent itemset must also be frequent; equivalently, if an itemset is infrequent, all its supersets are infrequent. This anti-monotone property is used to prune candidates.

There are 5 transactions, so minimum support count $=0.5\times5=2.5\Rightarrow 3$. Minimum confidence = 75%.

Pass 1: $C_1$ and $L_1$

Egg and Yogurt are removed. $L_1=\{$Bread:4, Cheese:3, Juice:4, Milk:3$\}$.

Pass 2: $C_2$ and $L_2$

$L_2=\{$Bread-Juice:3, Cheese-Juice:3$\}$.

Pass 3: the only join of $L_2$ gives {Bread, Cheese, Juice}, whose subset {Bread, Cheese} is infrequent, so it is pruned (actual count is 2 anyway). $C_3=\emptyset$.

Frequent itemsets: Bread, Cheese, Juice, Milk, {Bread, Juice}, {Cheese, Juice}.

Association rules (from the 2-itemsets)

All four rules are strong association rules.

Importance of the data mart. A data mart is a department-level subset of a data warehouse (e.g. sales, finance, marketing). It is important because it:

• gives a particular user group fast, focused access to relevant data;
• is smaller, cheaper and quicker to build than an enterprise warehouse (weeks instead of months);
• improves query performance and reduces load on the central warehouse;
• is easier to manage, secure and customize for the department's needs;
• can be built first and later integrated into the enterprise warehouse (bottom-up approach).

Data warehouse schemas

A schema defines the fact and dimension tables and how they are linked.

1. Star schema - a central fact table (measures and foreign keys) connected directly to a single denormalized table for each dimension; the diagram looks like a star. Example: fact table Sales(time_key, item_key, branch_key, location_key, units_sold, dollars_sold) with dimension tables Time(day, month, quarter, year), Item(name, brand, type, supplier), Branch, Location(street, city, province, country). It is simple and gives fast queries with few joins, but has redundancy.

2. Snowflake schema - a variant of the star schema in which dimension tables are normalized into additional tables. Example: Item is split into Item(item_key, name, brand, type, supplier_key) and Supplier(supplier_key, type); Location is split into Location and City(city_key, city, province, country). It saves space and is easier to maintain, but needs more joins and so is slower.

3. Fact constellation (galaxy) schema - several fact tables share dimension tables. Example: Sales and Shipping fact tables share the Time, Item and Location dimensions, with Shipping also linking a Shipper dimension. It suits enterprise-wide warehouses; data marts normally use star or snowflake schemas.

KDD vs data mining. Knowledge Discovery in Databases (KDD) is the whole process of obtaining useful knowledge from raw data: selection, preprocessing, transformation, data mining, and interpretation/evaluation. Data mining is just one step of KDD, the step in which algorithms are applied to extract patterns. So KDD is the overall process, and data mining is its core step; the other steps are needed to prepare the data and to make sense of the patterns.

Stages of KDD

Databases / Data sources
        |  (cleaning, integration)
        v
Data warehouse
        |  (selection)
        v
Task-relevant data
        |  (preprocessing, transformation)
        v
Transformed data
        |  (DATA MINING)
        v
Patterns
        |  (evaluation, presentation)
        v
Knowledge

1. Data cleaning - remove noise and inconsistent data, handle missing values.
2. Data integration - combine data from multiple sources into one store (a data warehouse).
3. Data selection - retrieve the data relevant to the analysis task from the database.
4. Data transformation - consolidate the data into forms suitable for mining by summary or aggregation operations, normalization and so on.
5. Data mining - apply intelligent methods (classification, clustering, association, etc.) to extract data patterns.
6. Pattern evaluation - identify the truly interesting patterns using interestingness measures.
7. Knowledge presentation - present the mined knowledge to users using visualization and reporting techniques.

The process is iterative: results of later steps may require going back to earlier steps.

Noisy data is random error or variance in a measured variable (e.g. a wrong age of 250). Smoothing methods:

1. Binning. Sort the data, distribute it into equal-frequency (or equal-width) bins, and smooth each bin using its neighbours.

Example: sorted prices 4, 8, 15, 21, 21, 24, 25, 28, 34 divided into three equal-frequency bins:

• Bin 1: 4, 8, 15; Bin 2: 21, 21, 24; Bin 3: 25, 28, 34.
• Smoothing by bin means: Bin 1: 9, 9, 9; Bin 2: 22, 22, 22; Bin 3: 29, 29, 29.
• Smoothing by bin boundaries (each value replaced by the closest boundary): Bin 1: 4, 4, 15; Bin 2: 21, 21, 24; Bin 3: 25, 25, 34.
• Smoothing by bin medians: Bin 1: 8, 8, 8; and so on.

2. Regression. Fit the data to a function (linear regression for one predictor, multiple regression for several) and replace the values by the fitted values. Example: fit $y=a+bx$ to (advertising, sales) data and replace noisy sales values with the line's predictions.

3. Clustering / outlier analysis. Group similar values into clusters; values that fall outside all clusters are outliers and can be removed or corrected. Example: in a set of ages mostly between 18 and 60, an entry of 250 lies far from every cluster and is treated as noise.

4. Combined computer and human inspection. The computer flags suspicious values (e.g. surprising to the expected pattern), and a human checks whether they are real or errors.

(a) Number of cuboids

For an $n$-dimensional data cube (no concept hierarchies), every dimension is either present or aggregated away (replaced by "all"), so the number of cuboids is

$2^n = 2^5 = 32$

These range from the 5-D base cuboid (all five dimensions), through the 4-D, 3-D, 2-D and 1-D cuboids, down to the 0-D apex cuboid (the grand total). Counting by size: $\binom{5}{5}+\binom{5}{4}+\binom{5}{3}+\binom{5}{2}+\binom{5}{1}+\binom{5}{0}=1+5+10+10+5+1=32$.

(b) Full cube

A full cube materializes all $2^n$ cuboids and all their cells. It answers any group-by query directly, but it needs huge storage and long computation, because the number of cells grows exponentially with the number of dimensions, and most cells in a sparse cube have very small aggregate values.

Iceberg cube

An iceberg cube materializes only the cells whose aggregate value satisfies a threshold given in a HAVING condition, for example

SELECT item, city, year, COUNT(*)
FROM sales
CUBE BY item, city, year
HAVING COUNT(*) >= 100

Only the "tip of the iceberg" (cells with count $\ge 100$) is stored. This saves space and time, and it keeps just the cells that are interesting to analysts. Algorithms such as BUC (Bottom-Up Computation) exploit the Apriori-style pruning property: if a cell fails the minimum support, none of its descendants can satisfy it, so they are pruned. Star-Cubing and similar methods also compute iceberg cubes efficiently.

Difference between K-medoids and K-means

K-medoids on the given data ($k=2$, Manhattan distance $|x_1-x_2|+|y_1-y_2|$)

Points: P1(70,85), P2(65,80), P3(72,88), P4(75,90), P5(60,50), P6(64,55), P7(62,52), P8(63,58).

Iteration 1. Choose initial medoids $M_1=$ P2(65,80) and $M_2=$ P5(60,50).

Cost $=(10+0+15+20)+(0+9+4+11)=45+24=69$.

Now try replacing $M_1$ by a non-medoid. Taking P1(70,85) as the new medoid gives cluster 1 cost $10+5+10+0=25$, so the total is $25+24=49<69$. This swap is the best one (swapping with P3 gives the same 49, and the others are worse), so it is accepted: $M_1=$ P1(70,85).

Iteration 2. Medoids P1(70,85) and P5(60,50). The assignment is the same: cluster 1 $=\{$P1, P2, P3, P4$\}$ with cost 25, and cluster 2 $=\{$P5, P6, P7, P8$\}$ with cost 24, total 49.

Try swapping $M_2$: with P7(62,52) the cost of cluster 2 is $4+5+0+7=16$ (distances to P5, P6, P7, P8), so the total is $25+16=41<49$. Using P6 instead gives 18 and P8 gives 22 for cluster 2, both worse than 16. Accept $M_2=$ P7(62,52). Swapping $M_1$ gives no reduction (P3 as medoid costs 25, the same).

Iteration 3. Medoids P1(70,85) and P7(62,52). Re-assignment gives the same clusters; total cost $=25+16=41$. Every possible swap gives cost $\ge 41$ (P6 gives 18, P8 gives 22, P5 gives 24 for cluster 2), so there is no improvement and the algorithm stops.

Final result

• Cluster 1: (70,85), (65,80), (72,88), (75,90), with medoid (70,85)
• Cluster 2: (60,50), (64,55), (62,52), (63,58), with medoid (62,52)

Total cost $=41$.

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

DBSCAN groups together points that are densely packed and marks points lying alone in low-density regions as noise. It needs two parameters:

• $\varepsilon$ (Eps): the radius of the neighbourhood around a point.
• MinPts: the minimum number of points required within the $\varepsilon$-neighbourhood for a point to be dense.

Point types

• Core point: has at least MinPts points (counting itself) within $\varepsilon$.
• Border point: has fewer than MinPts points in its neighbourhood but lies within $\varepsilon$ of a core point.
• Noise (outlier): neither a core point nor a border point.

Key concepts

• A point $q$ is directly density-reachable from a core point $p$ if $q$ is within $\varepsilon$ of $p$.
• $q$ is density-reachable from $p$ if there is a chain of points $p=p_1,\dots,p_n=q$ where each $p_{i+1}$ is directly density-reachable from $p_i$.
• Two points are density-connected if both are density-reachable from some third point. A cluster is a maximal set of density-connected points.

Algorithm

1. Mark all points as unvisited.
2. Pick an unvisited point $p$ and mark it visited.
3. Find its $\varepsilon$-neighbourhood $N_\varepsilon(p)$. If $|N_\varepsilon(p)|<$ MinPts, label $p$ as noise (it may later turn out to be a border point of some cluster).
4. Otherwise $p$ is a core point: create a new cluster $C$ and add $p$. For every point $q$ in $N_\varepsilon(p)$, add $q$ to $C$ if it is not yet in any cluster; if $q$ is unvisited, mark it visited and find its neighbourhood, and if $q$ is also a core point, add its neighbours to the set being expanded.
5. Continue expanding until no more points can be added to $C$.
6. Repeat from step 2 until all points are visited.

Features: it needs no number of clusters in advance, finds clusters of arbitrary shape, identifies outliers, and runs in $O(n\log n)$ with a spatial index (otherwise $O(n^2)$). Its weaknesses are sensitivity to the choice of $\varepsilon$ and MinPts, and poor handling of clusters with widely varying density.

A multi-layer perceptron (multilayer feed-forward neural network) is trained with the backpropagation algorithm, which uses gradient descent to minimize the squared error between the network output and the target.

Network structure: an input layer, one or more hidden layers and an output layer. Each unit $j$ computes a weighted sum of its inputs plus a bias and applies an activation function, usually the sigmoid:

$I_j=\sum_i w_{ij}O_i+\theta_j,\qquad O_j=\frac{1}{1+e^{-I_j}}$

Algorithm

1. Initialize all weights and biases to small random numbers. Choose a learning rate $l$.
2. Forward pass. For each training tuple, feed the inputs to the input layer ($O_j=x_j$). Then, layer by layer, compute $I_j$ and $O_j$ for every hidden and output unit.
3. Backward pass (error propagation).
   • For an output unit $j$ with target $T_j$: $Err_j=O_j(1-O_j)(T_j-O_j)$
   • For a hidden unit $j$, with $k$ ranging over the units of the next layer: $Err_j=O_j(1-O_j)\sum_k Err_k\,w_{jk}$
4. Update weights and biases: $\Delta w_{ij}=l\cdot Err_j\cdot O_i,\qquad w_{ij}\leftarrow w_{ij}+\Delta w_{ij}$ $\Delta\theta_j=l\cdot Err_j,\qquad \theta_j\leftarrow\theta_j+\Delta\theta_j$
5. Terminate when the change in weights in the previous epoch is below a threshold, or the misclassification rate falls below a threshold, or a maximum number of epochs is reached. Otherwise repeat for the next tuple (case updating) or after a whole epoch (batch updating).

Remarks: the error surface may have local minima, so training can be repeated with different initial weights. A momentum term can speed up convergence. Training is slow, but the trained network is fast to use and tolerates noisy data and can model non-linear decision boundaries.

OLAP (Online Analytical Processing) operations let users view and analyze multidimensional data from different angles. Consider a sales cube with dimensions Time (day, month, quarter, year), Location (city, country) and Item (type), and measure sales amount.

1. Roll-up (drill-up). Aggregates data by climbing up a concept hierarchy or by removing a dimension. Example: rolling up Location from city to country gives sales per country instead of per city.

2. Drill-down. The reverse of roll-up: moves from summarized to more detailed data by stepping down a hierarchy or adding a dimension. Example: drilling down Time from quarter to month gives monthly sales.

3. Slice. Selects one value of one dimension, giving a sub-cube with one fewer dimension. Example: slice for Time = Q1 gives a 2-D view of Location by Item for Q1.

4. Dice. Selects values on two or more dimensions, giving a smaller sub-cube. Example: dice for (Time = Q1 or Q2) and (Location = Kathmandu or Pokhara) and (Item = Mobile or Laptop).

5. Pivot (rotate). Rotates the axes of the data view to give another presentation, for example swapping the Item and Location axes of a 2-D table so that locations form rows and items form columns.

Other operations include drill-across (querying several fact tables) and drill-through (going down to the back-end relational tables).

Multimedia data mining

Multimedia data mining is the discovery of interesting patterns and knowledge from multimedia databases that hold images, audio, video, graphics and text. It combines techniques from image processing, computer vision, information retrieval and data mining. Typical tasks are content-based retrieval, classification and clustering of images, video summarization, audio and speech mining, and association discovery between visual and textual features (for example, finding that images with a large blue top region are often labelled "sky").

Main challenges are the high dimensionality of the feature vectors, the large volume of data, the semantic gap between low-level features (colour, texture, shape) and human concepts, and the difficulty of annotating data.

Similarity search in multimedia data

Similarity search finds the objects in a database that are similar to a query object, without needing an exact match. There are two main types:

1. Description-based retrieval: uses keywords, captions and tags attached to the objects.
2. Content-based retrieval: uses features extracted from the content itself.

Steps in content-based similarity search:

• Feature extraction: each object is converted into a feature vector, for example colour histograms, texture descriptors, shape descriptors, or Fourier/wavelet coefficients (sequence data are reduced to a few coefficients).
• Indexing: the vectors are stored in a multidimensional index such as an R-tree or a KD-tree, to avoid scanning all objects.
• Similarity measure: a distance such as Euclidean distance $d(x,y)=\sqrt{\sum_i (x_i-y_i)^2}$ is computed between the query vector and the stored vectors.
• Query types: range (threshold) query, which returns all objects within distance $\varepsilon$ of the query, and nearest-neighbour query, which returns the $k$ closest objects.

Example: for a query image, the system computes its colour histogram, finds the stored images whose histograms are within a threshold distance, and returns them ranked by similarity.

1. Support Vector Machine (SVM)

An SVM is a supervised classification method that finds the hyperplane separating the classes with the maximum margin. The margin is the distance between the hyperplane and the nearest training tuples of each class; those nearest tuples are the support vectors, and only they determine the hyperplane.

A separating hyperplane is written $\mathbf{w}\cdot\mathbf{x}+b=0$. For two classes labelled $y_i=\pm1$, the constraints are $y_i(\mathbf{w}\cdot\mathbf{x}_i+b)\ge 1$, and the margin width is $2/\lVert\mathbf{w}\rVert$. Maximizing the margin means

$\min_{\mathbf{w},b}\ \tfrac12\lVert\mathbf{w}\rVert^2\quad\text{subject to}\quad y_i(\mathbf{w}\cdot\mathbf{x}_i+b)\ge1 .$

For data that are not linearly separable, a soft margin (slack variables with penalty $C$) is used, or a kernel function (polynomial, RBF, sigmoid) maps the data into a higher-dimensional space where a linear separator exists. SVMs are accurate and resist overfitting because the model depends only on the support vectors, but training on very large data is slow and the kernel and parameters need tuning.

2. Multi-dimensional Data Model

Data warehouses are based on a multidimensional model, in which data are viewed as a data cube. A cube is defined by:

• Dimensions: the perspectives or entities about which records are kept, such as time, item, branch, location. Each dimension has a dimension table and often a concept hierarchy (day, month, quarter, year).
• Facts: the numeric measures of interest (dollars sold, units sold), held in a fact table with keys to the dimension tables.

An $n$-D cube is a lattice of cuboids, from the base cuboid to the apex cuboid. The model is implemented using a star schema (one fact table with a single dimension table per dimension), a snowflake schema (normalized dimension tables), or a fact constellation (several fact tables sharing dimensions). It supports OLAP operations such as roll-up, drill-down, slice, dice and pivot.

Trimmed mean

The trimmed mean is the mean computed after discarding a fixed percentage (for example the top and bottom 2% to 25%) of the sorted values. We prefer it when the data contain outliers or are skewed, because the ordinary mean is very sensitive to extreme values, while the median ignores most of the data. The trimmed mean is a compromise: it keeps most of the information and is robust.

Example: salaries (in Rs thousands) of 10 employees: 20, 22, 25, 25, 27, 28, 30, 31, 33, 400.

Ordinary mean $=641/10=64.1$, which is not representative because of 400. Trimming 10% at each end (dropping 20 and 400) leaves 22, 25, 25, 27, 28, 30, 31, 33, whose sum is 221, so the trimmed mean $=221/8=27.6$, which reflects the typical salary.

Multi-dimensional data model

A data warehouse views data as a data cube defined by dimensions and facts.

• Dimensions are the perspectives for analysis (time, item, branch, location). Each has a dimension table and may have a concept hierarchy, for example day < month < quarter < year.
• Facts are numeric measures (units sold, amount) stored in a fact table that references dimension tables by keys.
• An $n$-dimensional cube is a lattice of cuboids; the base cuboid holds the lowest level of detail and the apex cuboid holds the grand total. With no hierarchies there are $2^n$ cuboids.

This model supports fast aggregation and OLAP operations (roll-up, drill-down, slice, dice, pivot).

Conceptual modelling of a data warehouse

The multidimensional model is expressed through three schemas.

1. Star schema: a central fact table connected to one denormalized dimension table per dimension. It is simple and fast for queries, with some redundancy.
2. Snowflake schema: a refinement in which dimension tables are normalized into further tables (for example city and country split from a location table). It saves space but needs more joins.
3. Fact constellation (galaxy) schema: several fact tables share dimension tables; it models multiple related subjects such as sales and shipping.

Example star schema: fact table Sales(time_key, item_key, branch_key, location_key, units_sold, dollars_sold) with dimension tables Time, Item, Branch and Location.

Generating strong association rules

Strong association rules are produced in two steps:

1. Find all frequent itemsets: itemsets whose support count is at least the minimum support (min_sup).
2. Generate rules from each frequent itemset $l$: for every non-empty proper subset $s$ of $l$, output the rule $s\Rightarrow(l-s)$ if $\text{confidence}=\frac{\text{support\_count}(l)}{\text{support\_count}(s)}\ \ge\ \text{min\_conf}.$ A rule that satisfies both minimum support and minimum confidence is strong.

FP-growth with minimum support count 3

Item counts: K = 5, E = 4, M = 3, O = 3, Y = 3 (all frequent). Order by descending count: K, E, M, O, Y.

Ordered transactions:

FP-tree (node:count):

null
 └─ K:5
     ├─ E:4
     │   ├─ M:2
     │   │   └─ O:1
     │   │       └─ Y:1
     │   └─ O:2
     │       └─ Y:1
     └─ M:1
         └─ Y:1

Conditional pattern bases and frequent patterns (from the least frequent item upward):

For Y, E and M have count 2 in the base, below 3, so they are dropped. For M, E has count 2 and is dropped. For O, M has count 1 and is dropped.

Frequent itemsets (support count $\ge3$):

{K}:5, {E}:4, {M}:3, {O}:3, {Y}:3, {K,E}:4, {K,M}:3, {K,O}:3, {K,Y}:3, {E,O}:3, {K,E,O}:3.

Overfitting and underfitting

• Overfitting: the model fits the training data too closely, including its noise and accidental patterns. It has very high training accuracy but poor accuracy on unseen data. It happens with overly complex models (for example a very deep tree) or too little data. Remedies are pruning, more data, cross-validation and regularization.
• Underfitting: the model is too simple to capture the structure of the data, so both training and test accuracy are poor. Remedies are a more complex model, better features and longer training.

ID3 decision tree

ID3 chooses at each node the attribute with the highest information gain.

Class counts: High = 4 (TID 1, 2, 3, 6), Low = 2 (TID 4, 5).

$Info(D)=-\tfrac46\log_2\tfrac46-\tfrac26\log_2\tfrac26=0.9183$

Attribute Age

• $\le30$: TID 1, 2, 6, all High, so $Info=0$.
• $>30$: TID 3 (High), 4, 5 (Low): $Info=-\tfrac13\log_2\tfrac13-\tfrac23\log_2\tfrac23=0.9183$.

$Info_{Age}(D)=\tfrac36(0)+\tfrac36(0.9183)=0.4591,\qquad Gain(Age)=0.9183-0.4591=0.4591$

Attribute Car Type

• Family: TID 1, 4, 6 with High 2 and Low 1, so $Info=0.9183$.
• Sports: TID 2, 3, both High, so $Info=0$.
• Truck: TID 5, Low, so $Info=0$.

$Info_{Car}(D)=\tfrac36(0.9183)=0.4591,\qquad Gain(Car\ Type)=0.4591$

The two gains are equal, so either can be the root. Choose Age.

• Age $\le30$ is pure, so it becomes a leaf: High.
• For Age $>30$ (TID 3, 4, 5), split on Car Type: Sports (TID 3) gives High; Family (TID 4) gives Low; Truck (TID 5) gives Low.

Resulting tree

Age
├─ <=30 : High
└─ >30  : Car Type
           ├─ Sports : High
           ├─ Family : Low
           └─ Truck  : Low

(Choosing Car Type as the root gives an equally valid tree: Sports gives High, Truck gives Low, and Family is split by Age, with $\le30$ giving High and $>30$ giving Low.)

Noise is a random error or variance in a measured variable. Two common methods of smoothing noisy data are binning and regression.

1. Binning

The sorted data are distributed into bins (equal-frequency or equal-width), and each value is replaced by a value derived from its neighbourhood (bin).

Example: sorted prices 4, 8, 15, 21, 21, 24, 25, 28, 34, partitioned into equal-frequency bins of size 3:

• Bin 1: 4, 8, 15; Bin 2: 21, 21, 24; Bin 3: 25, 28, 34.
• Smoothing by bin means: Bin 1: 9, 9, 9; Bin 2: 22, 22, 22; Bin 3: 29, 29, 29.
• Smoothing by bin boundaries: each value is replaced by the closest boundary. Bin 1: 4, 4, 15; Bin 2: 21, 21, 24; Bin 3: 25, 25, 34.
• Smoothing by bin medians is also possible.

2. Regression

Data are fitted to a function, for example a linear regression line $y=a+bx$, and the fitted values replace the observed ones. Values far from the line are treated as noise. Multiple linear regression is used when there are several attributes.

(Clustering, which treats values outside the clusters as outliers, and combined computer and human inspection are other methods.)

k-means++ initialization

The first centroid is chosen (here given). Each next centroid is chosen from the remaining points with probability proportional to $D(x)^2$, the squared distance to the nearest centroid already chosen. To obtain a definite answer we take the point with the largest $D^2$ (the farthest point), which is the choice with the highest probability.

Points: A1 (3,11), A2 (3,6), A3 (9,5), A4 (6,9), A6 (7,5), A7 (2,3), A8 (5,10).

Step 1. First centroid $c_1=A1(3,11)$. Squared distances to $c_1$:

Total $=232$. The largest is A3 (72), with selection probability $72/232=0.31$. So $c_2=A3(9,5)$.

Step 2. $D^2$ to the nearest of $c_1, c_2$:

Total $=100$. The largest is A7 (53), with probability $0.53$. So $c_3=A7(2,3)$.

Initial centroids: (3,11), (9,5) and (2,3).

Computing a data cube means computing aggregates (such as sum or count) for all group-by combinations. The general strategies are as follows.

1. Sorting, hashing and grouping. Dimension attributes are sorted, hashed or grouped so that tuples with the same dimension values are brought together and aggregated. Sorting and grouping techniques of relational query processing are applied to cuboids.

2. Simultaneous aggregation and caching of intermediate results. Higher-level aggregates are computed from already computed lower-level ones rather than from the base fact table. For example, cuboid (item, city) can be derived from (item, city, year) by aggregating away year. Caching the intermediate cuboid in memory reduces disk I/O.

3. Aggregation from the smallest child. When a cuboid can be computed from several child cuboids, the smallest child is used, which reduces the amount of data scanned.

4. Apriori (pruning) for iceberg cubes. If a cell does not satisfy the minimum support (for example count $\ge$ threshold), none of its descendant (more specific) cells can, so they are pruned. BUC uses this idea.

Well-known algorithms

• MultiWay array aggregation: a chunk-based array method for MOLAP that computes many cuboids at the same time in an efficient order, reading each chunk once.
• BUC (Bottom-Up Computation): works from the apex cuboid downward, partitioning on one dimension at a time and pruning with the iceberg condition.
• Star-Cubing: combines top-down and bottom-up computation using a star-tree structure with shared dimensions.

Data characterization vs. data discrimination

Challenges of multimedia mining

1. High dimensionality and large volume: images, audio and video create very large feature vectors and huge databases.
2. Semantic gap: the gap between low-level features (colour, texture, shape, pitch) and high-level human concepts.
3. Heterogeneity: several data types (text, image, audio, video) that must be combined.
4. Feature extraction and representation: choosing features that describe the content well, and indexing them for fast search.
5. Similarity measurement: defining a similarity measure that matches human judgement.
6. Lack of labelled data: manual annotation is costly and subjective.
7. Temporal and spatial relationships in video, and noise and quality variations (lighting, resolution, compression).
8. Storage, processing time and privacy.

Graph mining

Graph mining is the process of discovering interesting and useful patterns, structures and relationships from data that are represented as graphs, where nodes are objects and edges are links between them. Examples are social networks, web graphs, chemical compounds and biological networks. Tasks include frequent subgraph mining, graph classification and clustering, link prediction, and community detection.

Theory of balance and theory of status (signed networks)

In a signed network, edges carry a positive sign (friend, trust) or a negative sign (enemy, distrust). Two theories explain the structure of triangles.

Theory of balance. Based on the ideas "the friend of my friend is my friend", "the enemy of my friend is my enemy", "the friend of my enemy is my enemy" and "the enemy of my enemy is my friend". A triangle is balanced if the product of its edge signs is positive, which means 3 positive edges, or 1 positive and 2 negative edges. A triangle with 2 positive and 1 negative edge, or with 3 negative edges, is unbalanced. The theory works on undirected edges.

Theory of status. Edges are directed; a positive edge $A\to B$ means "A regards B as having higher status", and a negative edge means "A regards B as having lower status". A triangle is consistent if the implied status ordering has no cycle.

The conflict. The two theories give opposite verdicts on some triangles.

• Triangle with two positive and one negative edge: A $\xrightarrow{+}$ B, B $\xrightarrow{+}$ C, C $\xrightarrow{-}$ A. Balance theory calls it unbalanced (product of signs is negative). Status theory finds it consistent: B has higher status than A, C has higher status than B, and C regards A as lower, so the order A < B < C holds with no contradiction.
• Triangle with three positive edges in a cycle: A $\xrightarrow{+}$ B, B $\xrightarrow{+}$ C, C $\xrightarrow{+}$ A. Balance theory calls it balanced (all friends). Status theory finds it inconsistent: A < B < C < A is a cycle of status.

So a triangle can be unbalanced yet status-consistent, or balanced yet status-inconsistent. Real networks (for example Epinions and Slashdot) are explained better by balance for undirected relations and by status for directed ones.

Support vector

In a support vector machine (SVM), the support vectors are the training tuples that lie closest to the separating hyperplane, exactly on the margin boundaries $\mathbf{w}\cdot\mathbf{x}+b=\pm1$. They alone determine the position and orientation of the maximum-margin hyperplane; removing any other tuple does not change the model.

Evaluating the accuracy of a classifier

Accuracy is the percentage of test tuples correctly classified. It must be measured on data not used for training, otherwise the estimate is optimistic.

1. Confusion matrix and measures. With TP, TN, FP, FN:

$Accuracy=\frac{TP+TN}{TP+TN+FP+FN},\qquad Error\ rate=1-Accuracy$

$Precision=\frac{TP}{TP+FP},\qquad Recall\ (Sensitivity)=\frac{TP}{TP+FN},\qquad Specificity=\frac{TN}{TN+FP}$

$F_1=\frac{2\cdot Precision\cdot Recall}{Precision+Recall}$

Precision, recall and $F_1$ matter when classes are imbalanced.

2. Holdout method. The data are randomly split (for example 2/3 training and 1/3 test). The model is built on the training part and its accuracy is estimated on the test part. Random subsampling repeats this and averages the accuracy.

3. k-fold cross-validation. The data are divided into $k$ equal folds. In each round one fold is the test set and the other $k-1$ folds are used for training. The accuracy is the average over all $k$ rounds. Every tuple is used for testing exactly once. Leave-one-out is the special case $k=n$. Stratified 10-fold cross-validation is commonly recommended.

4. Bootstrap. Tuples are sampled with replacement to form a training set of the same size; the tuples not chosen (about 36.8%) form the test set. This is repeated and the results are averaged (.632 bootstrap).

5. ROC curve. Plots true positive rate against false positive rate at different thresholds; the area under the curve (AUC) measures how well the classifier separates the classes.