Classification vs Regression and ID3 Decision Tree

Part 1: Classification vs Regression

Classification predicts a discrete categorical label; regression predicts a continuous ordered value.

Part 2: ID3 Classifier

Given data

9 tuples: Class Up = 5, Down = 4.

Step 1: Entropy of dataset

$$E(D) = -\tfrac{5}{9}\log_2\tfrac{5}{9} - \tfrac{4}{9}\log_2\tfrac{4}{9} = 0.4711 + 0.5200 = 0.9911$$

Step 2: Information Gain

Age: old(3): 0Up,3Down; mid(3): 2Up,1Down; new(3): 3Up,0Down

$$E(\text{old})=0,\quad E(\text{new})=0$$ $$E(\text{mid}) = -\tfrac{2}{3}\log_2\tfrac{2}{3}-\tfrac{1}{3}\log_2\tfrac{1}{3}=0.9183$$ $$E_{\text{Age}} = \tfrac{3}{9}(0)+\tfrac{3}{9}(0.9183)+\tfrac{3}{9}(0)=0.3061$$ $$\text{Gain(Age)} = 0.9911 - 0.3061 = 0.6850$$

Competition: Yes(4): 2Up,2Down; No(5): 3Up,2Down

$$E(\text{Yes})=1.0,\quad E(\text{No})=0.9710$$ $$E_{\text{Comp}} = \tfrac{4}{9}(1.0)+\tfrac{5}{9}(0.9710)=0.9838$$ $$\text{Gain(Competition)} = 0.9911-0.9838 = 0.0073$$

Type: SW(5): 2Up,3Down; HW(4): 3Up,1Down

$$E(\text{SW})=0.9710,\quad E(\text{HW})=0.8113$$ $$E_{\text{Type}} = \tfrac{5}{9}(0.9710)+\tfrac{4}{9}(0.8113)=0.5394+0.3606=0.9000$$ $$\text{Gain(Type)} = 0.9911-0.9000 = 0.0911$$

Root = Age (highest gain 0.6850).

Step 3: Split on Age

• Age = old → all Down → leaf Down
• Age = new → all Up → leaf Up
• Age = mid → mixed, needs further split.

Step 4: Subtree for Age = mid

Subset: 3 tuples (2 Up, 1 Down). $$E(D_{mid}) = -\tfrac{2}{3}\log_2\tfrac{2}{3}-\tfrac{1}{3}\log_2\tfrac{1}{3}=0.9183$$

Competition: Yes(2): 1Up,1Down → E=1.0; No(1): 1Up → E=0 $$E_{\text{Comp}} = \tfrac{2}{3}(1.0)+\tfrac{1}{3}(0)=0.6667$$ $$\text{Gain} = 0.9183-0.6667 = 0.2516$$

Type: SW(1): 0Up,1Down → E=0; HW(2): 2Up → E=0 $$E_{\text{Type}} = 0 \Rightarrow \text{Gain} = 0.9183 ;(\text{maximum})$$

Split on Type:

• Type = SW → Down
• Type = HW → Up

Final Decision Tree

Age?
├── old  → Down
├── new  → Up
└── mid  → Type?
            ├── SW → Down
            └── HW → Up

Step 5: Prediction for [Age = Mid, Competition = Yes, Type = HW]

Age = mid → check Type → Type = HW → Up

$$\boxed{\text{Predicted Profit = Up}}$$

KDD vs Data Mining and Stages of KDD

How KDD Differs from Data Mining

KDD (Knowledge Discovery from Data) is the overall process of discovering useful knowledge from raw data. It is a complete, iterative, multi-step process.

Data Mining is just one step within the larger KDD process, where intelligent methods (algorithms) are applied to extract patterns from prepared data.

As stated in the notes: "Data mining can be viewed as a step within a larger process called KDD."

Stages of KDD

The KDD process is an iterative sequence of the following steps:

Block Diagram

+------------------+
|   Raw Data       |
|  (Databases,     |
|   Files, etc.)   |
+--------+---------+
         |
         v
+------------------+
|  1. Data         |
|     Cleaning     |
+--------+---------+
         |
         v
+------------------+
|  2. Data         |
|     Integration  |
+--------+---------+
         |
         v
+------------------+
|  3. Data         |
|     Selection    |
+--------+---------+
         |
         v
+------------------+
|  4. Data         |
|     Transformation|
+--------+---------+
         |
         v
+------------------+
|  5. Data Mining  |  <--- Core Step
+--------+---------+
         |
         v
+------------------+
|  6. Pattern      |
|     Evaluation   |
+--------+---------+
         |
         v
+------------------+
|  7. Knowledge    |
|     Presentation |
+------------------+
         |
         v
+------------------+
|   Knowledge      |
+------------------+

(The process is iterative: feedback can go back to any earlier stage.)

Explanation of Each Stage

1. Data Cleaning

• Process of removing noise and inconsistent data from the dataset.
• Example: Filling missing values, removing duplicate records.

2. Data Integration

• Process of combining multiple data sources into a coherent data store.
• Example: Merging data from different databases or files.

3. Data Selection

• Data relevant to the analysis task are retrieved from the database.
• Only the useful subset of data is selected for further processing.

4. Data Transformation

• Data are transformed into forms appropriate for mining.
• Example: Normalization, aggregation, or encoding of attributes.

5. Data Mining

• The core step where intelligent methods are applied to extract data patterns.
• Tasks include: association analysis, classification, clustering, evolution analysis, etc.

6. Pattern Evaluation

• Identify the truly interesting patterns representing knowledge based on interestingness measures (e.g., support, confidence).
• Filters out trivial or redundant patterns.

7. Knowledge Presentation

• Visualization and knowledge representation techniques are used to present mined knowledge to users.
• Example: Charts, graphs, decision trees, rules displayed to the end user.

Summary

KDD is the complete pipeline from raw data to actionable knowledge. Data mining is only step 5 in this pipeline. The entire KDD process is iterative, meaning results at any stage may require going back to a previous step to refine the outcome.

Cuboids from 5-Dimensional Data, Full Cube, and Iceberg Cube

Step 1 - Given Data

• Number of dimensions: $n = 5$
• (No concept hierarchies specified, so we assume one level per dimension.)

Step 2 - Solve

Number of Cuboids

A data cube of $n$ dimensions (without concept hierarchies) contains $2^n$ cuboids, because each dimension can either be included or excluded from a given group-by.

$$\text{Number of cuboids} = 2^n = 2^5 = 32$$

Breakdown by level (using dimensions A, B, C, D, E):

• The base cuboid (ABCDE) is the least generalized and holds the most detailed data.
• The apex cuboid (0-D) is the most generalized, holding a single aggregate value.

Note: If each dimension had an associated concept hierarchy with $L_i$ levels, the total would instead be $\prod_{i=1}^{n}(L_i + 1)$. With no hierarchy given, the answer is $2^5 = 32$.

Full Cube

A full cube is a data cube in which all cuboids (all $2^n$ group-by combinations) and all their cells are precomputed and materialized in advance.

• For 5 dimensions, all 32 cuboids are precomputed.
• Advantage: Queries are answered very fast, since every aggregation is already available.
• Disadvantage: Requires very large storage and computation; grows explosively with dimensions and concept hierarchies, making it impractical for high-dimensional or sparse data.

Iceberg Cube

An iceberg cube is a partially materialized cube that stores only those cells whose aggregate measure value satisfies a specified minimum threshold (the iceberg condition / minimum support).

• Only cells meeting a condition such as count >= min_sup or sum(sales) > threshold are stored.
• Cells below the threshold (typically the vast majority in sparse data) are discarded.
• The name "iceberg" reflects that only the significant "tip" is materialized, while the large insignificant bulk stays hidden.
• Benefit: Greatly reduced storage and computation while retaining the useful (frequent/significant) aggregates.

Comparison

Summary

For 5-dimensional data there are $2^5 = 32$ possible cuboids. A full cube precomputes all 32 cuboids (high storage cost), whereas an iceberg cube materializes only cells whose measure exceeds a minimum threshold, saving substantial space and computation.

OLAP Operations in Multidimensional Data Model

OLAP (Online Analytical Processing) is a technology used to perform multidimensional analysis on large volumes of data stored in a data warehouse. OLAP operations are performed on a data cube, which organizes data along multiple dimensions (e.g., time, location, product).

The key OLAP operations are described below:

1. Roll-Up (Drill-Up)

Roll-up is also known as consolidation or aggregation. It generates a summary by moving from a lower level to a higher level in a concept hierarchy, or by reducing dimensions.

Concept Hierarchy is a system of grouping things based on their order level.

Two ways to perform Roll-up:

• Reducing dimensions
• Climbing up the concept hierarchy

Example:

• In the time dimension: Daily summary → Weekly summary → Monthly summary → Yearly summary
• In the location dimension: City level data is aggregated (rolled up) to Country level data.

Rolling up on location means sales data for individual cities (e.g., Kathmandu, Pokhara) is aggregated to give total sales for Nepal (country level).

2. Drill-Down (Roll-Down)

Drill-down is the reverse of roll-up. It navigates from a higher level of summary to a lower level of detail by descending a concept hierarchy or adding new dimensions.

Example:

• Moving from yearly sales data → quarterly sales → monthly sales → daily sales.
• From country-level sales → city-level sales.

3. Slice

The slice operation selects one particular dimension from a data cube and provides a new sub-cube by fixing a single value for one dimension.

Example:

• From a 3D cube with dimensions (Time, Location, Product), fixing Time = "Q1 2024" produces a 2D slice showing sales by Location and Product for Q1 2024 only.

4. Dice

The dice operation selects two or more dimensions from a data cube and provides a sub-cube by specifying a range or list of values for multiple dimensions.

Example:

• Selecting: Location = {Kathmandu, Pokhara}, Time = {Q1, Q2}, Product = {Laptop}
• This produces a smaller sub-cube from the original data cube.

5. Pivot (Rotate)

The pivot operation rotates the data axes of the cube to provide an alternative presentation of the data. It does not change the data but changes the orientation/view of the cube.

Example:

• Swapping the Time axis with the Location axis to view data from a different angle, such as viewing sales by product across time instead of by location across time.

Summary Table

These operations allow analysts and decision-makers to view data from multiple perspectives, enabling effective business intelligence and decision support.