Multidimensional Analysis and Descriptive Mining of Complex Data Objects

Q: What is attribute-oriented induction (AOI)?

AOI is a set-oriented, generalization-based technique that summarises a data set by replacing low-level attribute values with higher-level concepts from concept hierarchies. It produces a compact generalized relation (with counts) that characterises the target class.

Q: Write the steps of the AOI algorithm.

1. Collect the task-relevant data. 2. Remove attributes with many distinct values and no hierarchy. 3. Generalize each attribute while its distinct values exceed the threshold t. 4. Merge identical tuples and accumulate counts. 5. Simplify and present the result as a table, chart or rule.

Q: What is the generalization threshold?

It is a user-set limit t (usually 2 to 8) on the number of distinct values an attribute may keep. If an attribute has more than t distinct values, it is generalized one level up. A small t gives a more abstract summary; a large t keeps more detail.

Q: What is a concept hierarchy? Give an example.

A concept hierarchy is a sequence of mappings from low-level to higher-level concepts. Example: street < city < state < country, or day < month < quarter < year.

Q: Differentiate data characterization and data discrimination.

Characterization summarises the general features of a single target class (for example high-GPA students). Discrimination compares the target class against contrasting classes to highlight what makes them different, using d-weights.

Q: What are t-weight and d-weight?

t-weight is the share of a generalized tuple among all tuples of the target class (how typical it is). d-weight is the share of that tuple's count that belongs to the target class compared with all classes (how discriminating it is).

Q: How many cuboids does a data cube with $d$ dimensions have?

2^{d} cuboids when no concept hierarchies are used (one per subset of dimensions, from the base cuboid to the apex cuboid).

Q: Compare AOI with the data cube approach.

AOI generalizes on demand and needs little storage but is slower per query. The data cube approach pre-computes all cuboids so answers are fast, at the cost of large storage and a costly build step.

Classical data mining assumes structured tuples in a relational table. Real systems also store complex objects: maps, images, audio/video, documents, web pages, graphs, time-series and biological structures. This topic shows how to summarise and describe such data using generalization and data cubes.

Important

Attribute-Oriented Induction (AOI) is the star of this topic. Be ready to write its algorithm, show a generalization example, and explain the generalization threshold. It is asked almost every year (10 marks).

1. Why Complex Data Objects?

Complex objects come from object-relational, object-oriented, spatial and temporal databases. An object is more than a row: it bundles identity, structure and behaviour.

Part of an object	Meaning	Example
OID	Unique object identity	`STU-1042`
Attributes	Atomic, set-valued, composite, multivalued or multimedia	`hobbies = {chess, music}`
Methods	Operations defined on the object	`computeGPA()`
Links	Inheritance, aggregation, composition	`Student` is-a `Person`

MermaidDiagram

Rendering diagram…

2. Generalization-Based Descriptive Mining

Data generalization summarises data by replacing low-level values with higher-level concepts taken from a concept hierarchy. The output is a small generalized relation that characterises the target class.

Typical hierarchies:

street < city < province_or_state < country
date < month < quarter < year < decade

Example: Big-University student database

name	major	birth_date	address	gpa
Amy	CS	1999	1212 Richmond Ave., Victoria, BC, Canada	3.9
Bob	Physics	2001	12 Main St., Vancouver, BC, Canada	3.7

After generalization (name removed, address rolled up to country, birth year to age range, gpa to a label):

major	birth_region	age_range	gpa	count
CS	Canada	20-24	very_good	1
Physics	Canada	20-24	good	1

Pro TipSame data, different level

Stopping one level lower gives (CS, British Columbia) and (Physics, British Columbia). A lower level means more detail and more rows; a higher level means a smaller, more abstract summary.

3. Attribute-Oriented Induction (AOI)

Collect task-relevant data

Run a query (or pick a data cube) to fetch only the data needed for the mining task, for example all graduate students.

Generalization threshold $t$

$t$ controls how aggressively data is generalized. Typical values are 2 to 8.

Threshold $t$	Effect	Result
Small (about 2)	Generalizes strongly	Few rows, very abstract summary
Large (about 8)	Generalizes gently	More rows, more detail

Note

Generalization stops for an attribute as soon as its number of distinct values is $\le t$ . That is why the same data can give different summaries for different $t$ .

4. Cube-Oriented Approach

Instead of generalizing step by step, the data cube approach pre-computes all cuboids (one per combination of aggregation levels). The user's request is then answered by selecting the matching cuboid, which is much faster.

N_{cuboids} = 2^{d} \quad \text{for } d \text{ dimensions (ignoring hierarchies)}

MermaidDiagram

Rendering diagram…

	AOI (generalization-based)	Cube-oriented
Idea	Generalize attribute by attribute, on demand	Pre-compute all aggregations, then look up
Speed	Slower per query	Very fast per query
Storage	Small	Large (many cuboids)
Best for	Ad-hoc, one-off descriptions	Repeated OLAP-style questions

5. Characterization vs Discrimination

Characterization describes one class (the target class).
Discrimination (class comparison) compares the target class with one or more contrasting classes.

t-weight (how typical a generalized tuple is within the target class):

t\text{-weight} = \frac{count(q_a)}{\sum_{i=1}^{n} count(q_i)}

d-weight (how well a tuple separates the target class from the others):

d\text{-weight} = \frac{count(q_a \in C_{target})}{\sum_{j=1}^{m} count(q_a \in C_j)}

A characteristic rule reported as a quantitative rule looks like:

major(X) \in \{CS, Physics\} \wedge birth\_region(X) = Canada \Rightarrow gpa(X) = very\_good \quad [t\text{-weight} = 60\%]

Operation	Example question
Characterization	"Describe the students with GPA of at least 3.8."
Discrimination	"Compare graduate and undergraduate students."

Mining class comparisons

Collect data for each class

Split the data into the target class and the contrasting class(es).

6. Mining Complex Types of Data: Overview

Data type	How it is generalized or described	Key methods
Spatial	Spatial and non-spatial attributes along spatial hierarchies	Spatial data cube, spatial OLAP, clustering
Multimedia	Colour, texture, shape, keywords	Feature-space cube, similarity search
Time-series / sequence	Aggregation over time, periodicity	Similarity search, trend analysis
Text	Keyword and term hierarchies (document cube)	Keyword hierarchies, topic models
Web	Page content, structure and links	Content, structure and usage mining
Object / graph	Set-valued and composite attributes	Graph and sub-structure pattern mining

Exam TrapTypical questions

Explain attribute-oriented induction with the algorithm and an example (10 marks).
Explain the generalization threshold and the attribute removal / generalization rules (5-7 marks).
Differentiate characterization and discrimination, with t-weight and d-weight (5-7 marks).
Compare AOI with the cube-oriented approach (5 marks).

Frequently Asked Questions

QWhat is attribute-oriented induction (AOI)?

AOI is a set-oriented, generalization-based technique that summarises a data set by replacing low-level attribute values with higher-level concepts from concept hierarchies. It produces a compact generalized relation (with counts) that characterises the target class.

QWrite the steps of the AOI algorithm.

Collect the task-relevant data. 2. Remove attributes with many distinct values and no hierarchy. 3. Generalize each attribute while its distinct values exceed the threshold $t$ . 4. Merge identical tuples and accumulate counts. 5. Simplify and present the result as a table, chart or rule.

QWhat is the generalization threshold?

It is a user-set limit $t$ (usually 2 to 8) on the number of distinct values an attribute may keep. If an attribute has more than $t$ distinct values, it is generalized one level up. A small $t$ gives a more abstract summary; a large $t$ keeps more detail.

QWhat is a concept hierarchy? Give an example.

A concept hierarchy is a sequence of mappings from low-level to higher-level concepts. Example: street < city < state < country, or day < month < quarter < year.

QDifferentiate data characterization and data discrimination.

Characterization summarises the general features of a single target class (for example high-GPA students). Discrimination compares the target class against contrasting classes to highlight what makes them different, using d-weights.

QWhat are t-weight and d-weight?

t-weight is the share of a generalized tuple among all tuples of the target class (how typical it is). d-weight is the share of that tuple's count that belongs to the target class compared with all classes (how discriminating it is).

QHow many cuboids does a data cube with $d$ dimensions have?

$2^{d}$ cuboids when no concept hierarchies are used (one per subset of dimensions, from the base cuboid to the apex cuboid).

QCompare AOI with the data cube approach.

AOI generalizes on demand and needs little storage but is slower per query. The data cube approach pre-computes all cuboids so answers are fast, at the cost of large storage and a costly build step.

Multidimensional Analysis and Descriptive Mining of Complex Data Objects

Multidimensional Analysis and Descriptive Mining of Complex Data Objects

1. Why Complex Data Objects?

2. Generalization-Based Descriptive Mining

3. Attribute-Oriented Induction (AOI)

Collect task-relevant data

Generalization threshold ttt

4. Cube-Oriented Approach

5. Characterization vs Discrimination

Mining class comparisons

Collect data for each class

6. Mining Complex Types of Data: Overview

Frequently Asked Questions

Pocketly on Android

Generalization threshold $t$