BSc CSIT (TU) Science Data Warehousing and Data Mining (BSc CSIT, CSC410) Question Paper 2082 Nepal

Strong Association Rule

An association rule has the form $X \Rightarrow Y$ where $X, Y$ are itemsets and $X \cap Y = \emptyset$. A rule is called strong if it satisfies both a user-specified minimum support and minimum confidence threshold:

• Support: $\text{supp}(X \Rightarrow Y) = P(X \cup Y)$ — fraction of transactions containing both $X$ and $Y$.
• Confidence: $\text{conf}(X \Rightarrow Y) = \dfrac{\text{supp}(X \cup Y)}{\text{supp}(X)} = P(Y \mid X)$.

Thus a strong rule is one that occurs frequently enough (support $\geq$ min_sup) and is reliable enough (confidence $\geq$ min_conf) to be considered interesting.

Limitations of the Apriori Algorithm

1. Multiple database scans – Apriori rescans the whole database at each level $k$ to count candidate supports, causing heavy I/O for long patterns.
2. Huge number of candidate itemsets – candidate generation explodes combinatorially (e.g., $10^4$ frequent 1-itemsets can generate ~$10^7$ candidate 2-itemsets).
3. High computation and memory cost – counting and holding a massive candidate set is expensive.
4. Poor performance at low support – the number of frequent itemsets grows rapidly, degrading performance on dense/large data.

These limitations led to FP-Growth, which mines patterns from a compact FP-tree without candidate generation using only two scans.

FP-Tree Construction

Dataset:

Step 1 – Count 1-itemset support (min_sup = 1, so all items are kept):

Step 2 – Order frequent items by descending support → C > D > A > B (ties A,B broken alphabetically).

Step 3 – Reorder each transaction by this order:

Step 4 – Insert transactions into the FP-tree (counts after each path):

                    null
                   /    \
              C:5         D:1
            /  |  \          \
         A:1  D:3  (T5 adds A)  B:1   <- from T4 (D,B)
          |    |  \
         B:1  B:1  A:1
              |      |
            (T2)   (T6 A:1)

Drawn more precisely as a header-linked tree:

null
├── C:5
│    ├── A:2
│    │    └── B:1            (path C-A-B  : T1)
│    │    (A:2 also leaf from T5: C-A)
│    └── D:3
│         ├── B:1            (path C-D-B  : T2)
│         └── A:1            (path C-D-A  : T6)
│         (D:3 also leaf from T3: C-D)
└── D:1
     └── B:1                 (path D-B    : T4)

Header (item → node-links) table:

The FP-tree compresses all six transactions; frequent patterns are later mined by building conditional FP-trees from each item's prefix paths, with no candidate generation.

Role of Laplace Smoothing

Laplace (add-one) smoothing is used in probabilistic classifiers such as Naïve Bayes to avoid the zero-probability problem. If an attribute value never co-occurs with a class in the training data, its conditional probability becomes 0, which forces the entire product $P(C)\prod P(x_i \mid C)$ to 0 and wrongly discards otherwise-likely classes.

Laplace smoothing adds a small count (usually 1) to every frequency:

$$P(x_i \mid C) = \frac{count(x_i, C) + 1}{count(C) + m}$$

where $m$ is the number of possible values of the attribute. This guarantees non-zero probabilities, makes the estimates more robust for small or sparse datasets, and keeps the probabilities summing to 1.

Decision Tree using ID3

ID3 selects, at each node, the attribute with the highest information gain:

$$Entropy(S) = -\sum_i p_i \log_2 p_i, \qquad Gain(S,A) = Entropy(S) - \sum_{v} \frac{|S_v|}{|S|} Entropy(S_v)$$

Dataset:

Class counts: C1 = 3, C2 = 3 (total 6).

Entropy of S:

$$Entropy(S) = -\tfrac{3}{6}\log_2\tfrac{3}{6} - \tfrac{3}{6}\log_2\tfrac{3}{6} = 1.0$$

Gain(A1)

• A1 = T (objects 1,2,3): classes {C1, C1, C2} → $-\tfrac{2}{3}\log_2\tfrac{2}{3} - \tfrac{1}{3}\log_2\tfrac{1}{3} = 0.918$
• A1 = F (objects 4,5,6): classes {C1, C2, C2} → $0.918$

$$Gain(A1) = 1.0 - \left(\tfrac{3}{6}(0.918) + \tfrac{3}{6}(0.918)\right) = 1.0 - 0.918 = 0.082$$

Gain(A2)

• A2 = T (objects 1,2,5,6): classes {C1, C1, C2, C2} → $-\tfrac{2}{4}\log_2\tfrac{2}{4} - \tfrac{2}{4}\log_2\tfrac{2}{4} = 1.0$
• A2 = F (objects 3,4): classes {C2, C1} → $1.0$

$$Gain(A2) = 1.0 - \left(\tfrac{4}{6}(1.0) + \tfrac{2}{6}(1.0)\right) = 1.0 - 1.0 = 0.0$$

Root selection

Since $Gain(A1) = 0.082 > Gain(A2) = 0.0$, the root is A1.

Splitting on A1

• A1 = T subset {1,2,3} = {C1, C1, C2}, entropy 0.918 → split further on the only remaining attribute A2:
  • A2 = T → objects 1,2 = {C1, C1} → pure leaf C1
  • A2 = F → object 3 = {C2} → pure leaf C2
• A1 = F subset {4,5,6} = {C1, C2, C2} → split on A2:
  • A2 = T → objects 5,6 = {C2, C2} → pure leaf C2
  • A2 = F → object 4 = {C1} → pure leaf C1

Resulting Tree

               A1
            /      \
          T          F
         /            \
        A2             A2
      /    \         /    \
     T      F       T      F
     |      |       |      |
    C1     C2      C2     C1

The tree classifies all six training objects correctly. To predict a new instance, traverse A1 then A2 to reach a leaf.

K-Means with K-Means++ Initialization

Data points: $P_1(6,3), P_2(7,2), P_3(4,8), P_4(2,2), P_5(0,2), P_6(9,0)$, with k = 3.

Step 1 – Choose initial centroids using k-means++

k-means++ chooses the first centre, then picks each subsequent centre far from existing centres (probability proportional to squared distance $D^2$). Here the first centre is given:

Centre 1: $c_1 = (6,3)$.

Compute squared distance $D^2$ of every other point to the nearest existing centre:

Largest $D^2 = 37$ at (0,2) → Centre 2: $c_2 = (0,2)$.

Now recompute $D^2$ = distance to the nearest of $\{c_1, c_2\}$:

Largest min-$D^2 = 29$ at (4,8) → Centre 3: $c_3 = (4,8)$.

Initial centroids: $c_1=(6,3),\; c_2=(0,2),\; c_3=(4,8)$.

Step 2 – Assign each point to the nearest centroid (squared Euclidean distance)

Cluster assignments:

• C1 (c₁): (6,3), (7,2), (9,0)
• C2 (c₂): (2,2), (0,2)
• C3 (c₃): (4,8)

Step 3 – Recompute centroids (mean of each cluster) → result after first iteration

• New $c_1$ $= \left(\dfrac{6+7+9}{3}, \dfrac{3+2+0}{3}\right) = \left(\dfrac{22}{3}, \dfrac{5}{3}\right) \approx (7.33, 1.67)$
• New $c_2$ $= \left(\dfrac{2+0}{2}, \dfrac{2+2}{2}\right) = (1.0, 2.0)$
• New $c_3$ $= (4, 8)$ (single point)

Result after the first iteration:

Data Mining Primitives

Data mining primitives define a data-mining task and let the user communicate exactly what is to be mined. A data-mining query is built from the following five primitives:

1. Task-relevant data – the portion of the database/data warehouse to be mined: the relevant tables, attributes (dimensions), and selection conditions (the data partition).
2. Kind of knowledge to be mined – the data-mining function to apply, e.g., characterization, discrimination, association, classification, prediction, clustering, or outlier/evolution analysis.
3. Background knowledge – domain knowledge that guides discovery and evaluates patterns, most importantly concept hierarchies (e.g., city → province → country) that allow mining at multiple abstraction levels.
4. Interestingness measures / thresholds – measures used to filter out uninteresting patterns, such as support, confidence, certainty, novelty, and simplicity, each with a threshold.
5. Knowledge presentation / visualization – the form in which discovered patterns are displayed: rules, tables, charts, decision trees, cubes, or graphs, including roll-up/drill-down for the user.

Together these primitives form a data-mining query language (DMQL), giving the user interactive control over the mining process.

Support Vector

In a Support Vector Machine (SVM), the support vectors are the training data points that lie closest to the decision boundary (the separating hyperplane) — i.e., the points lying on the margin. They are the critical examples that define the position and orientation of the maximum-margin hyperplane; if any other point were removed the boundary would not change, but removing a support vector would. The optimal hyperplane maximizes the margin (distance between the two parallel margin planes passing through the support vectors).

Backpropagation Algorithm for Classification

Backpropagation trains a multilayer feed-forward neural network by iteratively adjusting weights to minimize the error between predicted and target outputs using gradient descent.

Input : Training set D, learning rate η, network topology
Output: A trained neural network

1. Initialize all weights w_ij and biases θ_j to small random values.
2. Repeat (for each epoch) until termination condition:
     For each training tuple X in D:

     // ---- Forward propagation ----
     3. For each input unit: O_j = input value x_j
     4. For each hidden/output unit j:
            net_j = Σ_i w_ij O_i + θ_j        (weighted sum)
            O_j   = 1 / (1 + e^(-net_j))       (sigmoid activation)

     // ---- Backpropagate the error ----
     5. For each output unit j:
            Err_j = O_j (1 - O_j)(T_j - O_j)
     6. For each hidden unit j (from last hidden layer back):
            Err_j = O_j (1 - O_j) Σ_k Err_k w_jk

     // ---- Update weights and biases ----
     7. For each weight w_ij:
            w_ij = w_ij + η · Err_j · O_i
     8. For each bias θ_j:
            θ_j  = θ_j + η · Err_j

9. Terminate when weights converge / error below threshold /
   max epochs reached.

The trained network then classifies a new instance by a single forward pass, with the output unit having the highest activation giving the predicted class.

Data Mart

A data mart is a subset of a data warehouse that is focused on a single subject area, department, or business function (e.g., sales, finance, or marketing). It contains a smaller, more specialized slice of data tailored to the needs of a particular group of users, which makes it cheaper, faster to build, and easier to query than an enterprise-wide warehouse.

Two design approaches:

• Dependent data mart – sourced from a central enterprise data warehouse.
• Independent data mart – built directly from operational/external sources without a central warehouse.

Why We Need a Multidimensional Data Model

The multidimensional data model organizes data as a data cube with dimensions (e.g., time, item, location) and measures (e.g., sales amount), and is needed because:

1. Natural fit for analysis – it models data the way analysts think ("sales by product by region by quarter").
2. Fast OLAP operations – supports roll-up, drill-down, slice, dice, and pivot efficiently for interactive analysis.
3. Pre-aggregation – summary values can be precomputed along dimensions, giving very fast query response on huge data.
4. Multiple levels of abstraction – concept hierarchies allow viewing data at different granularities (day → month → year).
5. Better decision support – it enables multi-perspective summarization that flat relational/OLTP tables handle poorly.

Data Objects and Attribute Types

Data Object

A data object represents an entity in a dataset — e.g., a customer, a product, or a patient. It is described by a set of attributes (features/variables). In a table, each row is a data object and each column is an attribute.

Attribute Types

An attribute is a data field representing a characteristic of a data object. Attributes are classified by the kind of values they take:

Attributes are also grouped as qualitative (categorical) — nominal, binary, ordinal — and quantitative (numeric) — interval, ratio. Numeric attributes can further be discrete (countable, e.g., number of children) or continuous (real-valued, e.g., height).

Data Cube

A data cube is a multidimensional data structure that models data in terms of dimensions and measures, allowing it to be viewed and analyzed from multiple perspectives. Each dimension (e.g., time, item, location) corresponds to an attribute or set of attributes (a concept hierarchy), and each cell of the cube stores an aggregated measure (e.g., total sales). Although called a "cube," it can have any number of dimensions ($n$-D cube). It is the core structure of OLAP and supports operations such as roll-up, drill-down, slice, and dice.

The complete set of all possible aggregations (subsets of dimensions) is called the cuboid lattice; the base cuboid holds the lowest level of detail and the apex cuboid holds the grand total.

Variations of Cube Materialization

Materialization decides which cuboids/aggregates to precompute and store. The main variations are:

1. No materialization (Full computation on the fly) – compute aggregates only when queried; saves storage but very slow queries.
2. Full materialization – precompute and store all cuboids of the lattice; fastest queries but huge storage and update cost.
3. Partial materialization – precompute and store only a selected subset of cuboids (e.g., the most frequently used or beneficial ones), balancing storage and query speed.
4. Iceberg cube – materialize only those cells whose aggregate value meets a minimum threshold (e.g., count ≥ minimum support), pruning trivial/sparse cells.
5. (Closed/Shell cube) – materialize only closed cells or a small shell fragment of cuboids, further reducing redundant storage.

Concept Behind Beam Search

Beam search is a heuristic search strategy that explores a graph/tree by expanding the most promising nodes at each level, but — unlike best-first search — it keeps only a limited number of best candidates (the beam width, $w$) at each step and discards the rest. This bounds memory and time at the cost of completeness/optimality.

In data mining (e.g., rule induction and feature/subgroup discovery), beam search is used to grow rules: at each step it keeps the top-$w$ partial rules (ranked by a quality measure such as accuracy or information gain), specializes them, and again retains only the best $w$. It thus explores more alternatives than greedy hill-climbing (which keeps only 1) while avoiding the cost of an exhaustive search.

• Beam width $w = 1$ → behaves like greedy/hill-climbing search.
• Larger $w$ → broader search, better solutions, more cost.

Theory of Balance and Status (Social Network Analysis)

Balance theory and status theory explain the structure of signed social networks, where edges between actors are positive (+, friendship/trust) or negative (−, hostility/distrust).

Balance Theory

Based on the principle "the friend of my friend is my friend, the enemy of my enemy is my friend." It treats relations as undirected and looks at triangles:

• A triangle is balanced if it has an odd number of positive edges (i.e., all three +, or exactly one +).
• It is unbalanced/tense if it has an even number of + (two + and one −, or all −). Networks tend to evolve toward balanced configurations, often splitting into two mutually antagonistic groups.

Status Theory

Treats edges as directed and interprets a positive edge $A \rightarrow B$ as "A regards B as having higher status" and a negative edge as "lower status." Relations are consistent if they produce a coherent status ordering (e.g., if A < B and B < C then A < C). Status theory often explains directed sign patterns better than balance theory.

Both theories are used to predict the sign of unknown edges and to understand trust/distrust dynamics in online social networks.

Web Mining

Web mining applies data-mining techniques to discover useful patterns from web data. It has three categories:

1. Web Content Mining

Extracts useful information/knowledge from the actual content of web pages — text, images, audio, video, and structured records. Techniques include text mining, NLP, classification, and clustering of documents. Examples: search-engine indexing, sentiment/opinion mining, extracting product details from pages, topic classification.

2. Web Structure Mining

Analyzes the link (hyperlink) structure of the web — the graph of pages connected by links — to discover relationships and importance of pages. Examples: PageRank and HITS (hubs and authorities) algorithms, identifying communities, and ranking pages by their in-/out-link structure.

3. Web Usage Mining

Mines user interaction/behaviour data captured in web server logs, click-streams, cookies, and sessions to understand how users navigate a site. Examples: discovering navigation/access patterns, personalization and recommendation, improving site design, target advertising.

DBSCAN – Finding Core Points and Outliers

Parameters: Eps = 2.5, MinPts = 3. A point is a core point if its Eps-neighbourhood (distance ≤ 2.5) contains at least MinPts = 3 points, including itself.

Step 1 – Build the symmetric distance matrix

Step 2 – Eps-neighbourhood of each point (distance ≤ 2.5, including itself)

(For A: only B is within 2.5 → 2 points. For D: C=1.41, E=1.41, F=2.00, G=2.24, H=2.00 → all ≤2.5.)

Step 3 – Classify points

• Core points: B, C, D, E, F, G, H (each has ≥ 3 points within Eps).
• A: has only 2 points in its neighbourhood, so it is not a core point. Is it a border point? A is within Eps of a core point only if some core point lists A — only B (a core) has A within 2.5 (d(A,B)=1.41 ≤ 2.5). So A is a border point, not an outlier.

Result

• Core points: B, C, D, E, F, G, H
• Border point: A
• Outliers (noise): None — every point is either a core point or density-reachable from one.

Components of a Data Warehouse

A data warehouse architecture has the following key components:

1. Data Sources – operational/OLTP databases, flat files, and external sources that feed the warehouse.
2. ETL (Extract–Transform–Load) / Back-end Tools – extract data from sources, clean, transform, integrate, and load it into the warehouse.
3. Data Warehouse (Central Repository) – the integrated, subject-oriented, time-variant, non-volatile store, often organized in a star/snowflake schema.
4. Metadata Repository – data about the data: source definitions, transformation rules, schema, and operational information.
5. Data Marts – subject-specific subsets of the warehouse for departments.
6. OLAP Server – (MOLAP/ROLAP/HOLAP) supporting multidimensional analytical queries.
7. Front-end / Analysis Tools – query, reporting, OLAP, data-mining, and visualization tools used by analysts.

Trust Propagation in Social Networks

Trust propagation infers the trust between two users who are not directly connected by propagating trust values along the paths that link them through intermediate users — exploiting the idea that trust is partly transitive ("if A trusts B and B trusts C, then A can partially trust C").

Key ideas:

• Trust is directed and weighted – each edge $A \rightarrow B$ carries a trust score (e.g., 0–1).
• Atomic propagation along a path – trust along a chain is typically combined by multiplication/concatenation (it usually decays with path length, since indirect trust is weaker).
• Aggregation over multiple paths – when several paths connect $A$ and $C$, their inferred trust values are aggregated (e.g., averaged or weighted), giving a more reliable estimate.
• Distrust propagation – negative (distrust) edges can also be propagated, but distrust is generally not transitive in the same way and must be handled carefully.

Algorithms such as TidalTrust and Advogato/EigenTrust use these principles to compute trust scores, which power trust-aware recommendation systems, reputation systems, and spam/fraud resistance in online social networks.