Chapters 1,2

Extraction of interesting informations or patterns from data in large databases

• Statistics

• Machine Learning

• Database Systems

• Information Visualization

1. Descriptive Learning

   • Better understanding - data mining

   • e.g pattern recognition, clustering, outlier detection

2. Predictive Learning

   • Better forecasts - regression

   • e.g. traffic prediction, labeling, fraud detection

3. Prescriptive Learning

   • Better actions - artificial intelligence

   • e.g. predictive maintenance, autonomous driving, medical therapies

• Tremendous amounts of data caused bt

  • Automated data collection

  • Mature database technology

• Solution:

  • Data Warehousing and on-line analytical processing (OLAP)

  • Data Mining (give definition)

• Database analysis and decision support

  • Market analysis and management

  • Risk analysis and management

  • Fraud detection and management

• Other applications:

  • Text mining

  • Intelligent query answering

• Frequent Pattern Mining

• Clustering

• Classification

• Regression

• Process Mining

• may take 60% of the effort

• Integration of data from different sources

  • Mapping of attribute names

  • Joining different tables

• Elimination of inconsistencies

• Elimination of noise

• Computation of missing values e.g default value, average value

Task:

• Find useful features

• Dimensionality/variable reduction

• Invariant Representation

• Creating a target data set

• Selections

  • Selecting the relevant tuples/rows from the database table

• Projections

  • Selecting the relevant attributes/columns from the database tables

• Transformations

  • Discretization of numerical attributes

  • Computation of derived tuples/rows

    • e.g. aggregation (2+ -> 1), making new attributes (1+ -> 1++)

Goal:

• Find patterns of interest

Task:

• Are there labels (in the training data)?

  • Many -> Supervised learning

  • Some few -> Semi-supervised learning

  • None -> Unsupervised learning

• Choose fitting mining algorithms

Setting:

• Given a database of transactions e.g.

Motivation:

• Find the frequently co-occurring items in the set of transactions which indicate correlations or causalities

Applications:

• Market-based analysis

• Cross-marketing

• Catalogue design

• As a basis for clustering, classification

• Association rule mining: determining correlations between different itemsets

Setting:

• Database of objects O

• Unknown class labels

• Similarity model for objects, oft as function sim: O x O -> R

Task:

• Group objects into clusters while maximising intra-cluster similarity (cohesion) and minimising inter-clustering similarity (separation)

Applications:

• Customer profiling/segmentation

• Document or image collections

• Web access patterns

Setting:

• Class labels are known for a set of training data

Task:

• Find models/functions/rules that

  • describe and distinguish the classes

  • predict class membership for new objects

Applications:

• Classify disease type for samples based on gene expression values

• Automatic assignment of categories

• Predict unknown or missing values

Setting:

• Numerical output values are known for a training set

Task:

• Find models/functions/rules that

  • describe the numerical output values of the training data

  • predict the numerical value for new objects

Applications:

• Building a model of the housing values, which can be used to predict the price of a house in a certain area

• Building a model of an engineering process as a basis to control a technical system

• Generalise, summarise, and contrast data characteristics

• Based on attribute aggregation along concept hierarchies

  • Data cube approach (OLAP)

  • Attribute-oriented induction approach

• Finding objects which do not comply with the general behaviour of the data

• e.g. fraud detection, rare events analysis

• Sequential patterns (finding reoccurring sequences of events)

• Process mining

• Spatial data mining

• Graphs

• …

• Pattern evaluation and knowledge presentation

• Representation of real objects, situations, processes

• Measured by physical sensors

• Recorded from digital systems

• Generated by simulations

• Stored and provided by computers

• Numerical and categorical data types

• Similarity models -> allow for pattern mining

• Data reduction -> to increase efficiency

• identifiers (int, long, float)

• domains ({1,2,…},{true,false},{‘hello’,’hi’})

• operations (+,and,concat)

• Single values need 1 byte, 1 Byte = 8 bit, 4 Byte = 32 bits

• Big data sets allocated Kilobytes,…,Zettabytes

• Data compression helps (partially)

1. O(d)

2. O(nd)

3. O(nd^2)

• Simple, basic data types (numbers, symbols)

• Composed data types (vectors, sets)

• Complex data types (multimedia, spatial, structural data)

A metric space (O,d) consists of object set O and metric distance function d: O x O -> R which fulfills:

• Symmetry: ∀p,q ∈ O : d(p,q) = d(q,p)

• Identity of Indiscernables: ∀p,q ∈ O : d(p,q) = 0 <=> p = q

• Triangle Inequality: ∀p,q,o∈ O : d(p,q) <= d(p,o) + d(o,q)

e.g. points in 2D space with Euclidean distance

• non-symmetric: one-way roads on the way from p to q

• non-definite: indiscernable equivalent objects are not necessarily identical

• triangles: sometimes detours are preferred

• Symbols/identifiers

• e.g. subjects= {“maths”,”physics”}, occupation = {“butcher”}

• e.g. trivial metric

  • d(p,q) = 0: if p==q, else 1

• e.g. explicit similarity matrix

• e.g. path length in generalization hierarchy

There is a total order ≤ on the set of possible data values O:

• Transitivity: ∀p,q,o∈O : p≤q ∧ q≤o => p≤o

• Antisymmetry: ∀p,q,o∈O : p≤q ∧ q≤p =⇒ p = q

• Totality: ∀p,q∈O : p≤q ∨ q≤p

Examples:

• words, lexicographic ordering: high <= highschool

• (vague) sizes: tiny <= small <= medium <= big

• frequencies: never <= seldom <= rarely <= sometimes

• numbers: 0<=1, 1.78 <= 2.35

• Given a domain D, a sequence s of length n is a mapping I_n -> D of the index set I_n = {1,…,n} into D, s ∈ D^n for short.

• The sequence s concatenates n values from D; the order does not matter

• Unordered collection of individual values

• e.g. skills = {Java, C, Python}, hobbies = {skiing, diving, hiking}

• comparison

• + hamming distance (sep card)

• Given an ordered base set B = (b1,…,bn), for any set S create a binary vector r ∈ {0,1}^n with r_i = 1 <=> b_i ∈ S.

• Hamming distance: Sum of different entries (equal cardinality of symmetric set difference)

• Structure: graphs, networks, trees

• Geometry: shaped, contours, routes, trajectories

• Multimedia: images, audio, text, etc.

• Direct measures: highly data type dependent

• Feature extraction/feature engineering: explicit vector space embedding with hand-crafted features

• Kernel trick: implicit vector space embeddings

• Feature learning: vector space embeddings learned by deep learning methods e.g. neural networks

• Objects from database DB are mapped to feature vectors

• Feature vector space

  • Points represent objects

  • Distance corresponds to (dis)similarity

• Similarity queries are basic operations in databases

• Given: universe O, database DB ⊆ O, distance function d and query object q ∈ O

• Range query

• (k-) Nearest neighbor query

• Ranking query

Range query for range parameter ε ∈ R^+_0:

• range(DB, q, d, ε) = {o ∈ DB | d(o,q) ≤ ε}

Nearest neighbor query:

• NN(DB,q,d) = {o ∈ DB | ∀o′ ∈ DB : d(o,q) ≤ d(o′,q)}

NN(DB,q,d,k) ⊆ DB with |NN(DB,q,d,k)| = k AND ∀o∈NN(DB,q,d,k),

o′∈DB−NN(DB,q,d,k)

:d(o,q)≤d(o′,q)

#

The function works by first calculating the distance between q and each object in DB. Then, it sorts the objects in DB by their distance to q. The k objects with the smallest distances are then returned as the nearest neighbors of q.

The function guarantees that the returned set of nearest neighbors will contain exactly k objects, and that all of the objects in the returned set will be closer to q than any other object in DB that is not in the returned set.

“get next” functionality for picking databse objects in an increasing order w.r.t their distance to q:

• ∀i ≤ j : d(q, rank_{DB,q,d} (i)) ≤ d(q, rank_{DB,q,d (j))}

Using a range query:

• Naive search by sequential scan

  • Fetch database objects from secondary storage (e.g. disk): O(n) time

  • Check distances individually: O(n) time

Using a range query:

• Fast search by applying database techniques

  • Filter-refine architecture

    • Filter: Boil DB down to (small) candidate set C ⊆ DB

    • Refine: Apply exact distance calculations to candidates from C only

  • Indexing structures

    • Avoid sequential scans by (hierarchical or other) index techniques

    • Data access in time O(n), O(log n) or even O(1)

1. Fast filter step produces candidate set C ⊆ DB (by approximating distance function d’)

2. Exact distance function d is calculated on candidate set C only

Example: Dimensionality Reduction

Indexable - Index enabled

Complete - No false dismissals

Efficient - Fast individual calculation

Selective - Small candidate set

• To organize data in a way for fast access to relevant objects, e.g. by heavy pruning.

• R-Tree as an example for spatial index structure:

  • Hierarchy of minimum bounding rectangles

  • Disregard subtrees which are not relevant for the current query region

• Data visualization transforms data in visually perceivable representations

• Combines the capabilities:

  • Computers are good in number crunching

  • Humans are good in visual pattern recognition

• Geometric

• Icon-based

• Pixel-oriented

• Other

• Visualization of geometric transformations and projections of the data

• e.g. Scatterplots, Parallel Coordinates

  
  

• Visualization of data as icons

• e.g. Chernoff Faces, Stick Figures

• Visualize each attribute value of each data object by one coloured pixel

• e.g. recursive patterns

• Hierarchical techniques, graph-based techniques, hybrid techniques

• Designed for 2D data, two axes span the drawing area

• 2D objects are depicted as points in the diagram

• Orthogonal projections of points to axes indicate coordinate values

• Provides a first look at bivariate data to see clusters of points, outliers, etc.

• Matrix of scatterplots for pairs of dimensions

• Ordering of dimensions is important:

  • reordering improves understanding of structures and reduces clutter

  • Interestingness of orderings can be evaluated with quality metrics

• Scatterplots work well for 2 dimensions only

• Only depict pairwise correlations

• Projections get ambiguous for 3 or more dimensions

• Depict objects by curves rather than by points

• Coordinates are not indicated by orthogonal projections but by explicit intersections of polygons with axes

• e.g. spiderweb - axes remain connected at origin

• e.g. parallel coordinates - axes are aligned in parallel

• Illustrate any single object by a polygonal line

• Contract origins of all axes to a global origin point

• Works well for few objects only

• e.g. monthly average temperature

• d-dimensional data space is visualised by d parallel axes

• each axis is scaled to min-max range

• object = polygonal line intersecting axis at value in this dimension

• ordering important to reveal correlations

• Each data value is mapped onto a colored pixel

• Each dimension is showin in a separate window

• Arrangement strategies: recursive patterns iterated line and column-based arrangements

• Map d-dimensional space to facial expression, e.g. length of nose = dim 6; curvature of mouth = dim 8

• Humans can evaluate similarity between faces much more intuitively than between high-dimensional vectors

• Without dimensionality reduction only applicable to data spaces with up to 18 dimensions

• Which dimension represents what part?

• Better perception of patterns

  • Raw data is hard to understand

  • Visualization is limited to thousand of objects

  • Reduction of data may help to identify patterns

• Computational complexity

  • Big data sets cause prohibitively long runtime for data mining algorithms

  • Reduced data sets are useful the more the algorithms produce the same analytical results

Numerosity reduction

• Data aggregation (basic statistics)

• Data generalization (abstraction to higher levels)

Dimensionality reduction (reduction of attributes):

• Linear methods: (PCA)

• Non-linear methods: (Multidimensional scaling)

Quantization, discretization (reduce number of values per domain):

• Binning (histograms)

• Generalization along hierarchies (OLAP)

• Aggregation is numerosity reduction (less tuples/rows)

• Generalisation yields duplicates -> add counting attribute and merge duplicate tuple

• Central tendency: Where is the data located/ where is it centred?

• Variation, spread: How much do the data deviate from the centre

The value of a distributive measure d on D can be calculated by combining the results of distributed calculations on partitions D_i ⊂ D , D = D1 ∪ D2 ∪ . . . Dn

e.g.

• count(D1 ∪ D2) = count(D1) + count(D2)

• sum(D1 ∪ D2) = sum(D1) + sum(D2)

• min(D1 ∪ D2) = min(min(D1), min(D2))

• max(D1 ∪ D2) = max(max(D1), max(D2))

An algebraic measure on D can be computed by an algebraic function with M arguments, each of which is obtained by applying a distributive aggregate function to the partitions D_i ⊂ D , D = D1 ∪ D2 ∪ . . . Dn

There is no constant bound on the storage size that is needed to calculate and represent sub-aggregates.

• Mean - (weighted) arithmetic mean

• Mid-range

• Median

• Mode

• (Weighted) arithmetic mean is calculated by:

• Mid-range is calculated by the average of the largest and the smallest values in a data set

• Both are algebraic measures

• Applicable to numerical data only (sum, scalar multiplication)

• Applicable to ordinal data only (data that can be ordered), as total order is required

• Median is a holistic measure (considers all values equally)

• To categorical (non-numerical) data

• The variance measures the spread around the mean of numerical data

• The single pass calculation (sum of squares and square of sum in parallel) is faster than the two-pass method

• Variance is zero iff. all the values are equal

• Standard deviation is equal to the square root of the variance

  • These are both algebraic measures

• Mapping a continuous range of values into a discrete set of values

• It may use generalization

• e.g. group age (7 bits -> 128 values) to age_range (4 bits -> 16 values only)

  
  

• e.g. dropping age corresponds to reduction zero bits (10,14 -> teen, 25,29 -> twen)

• corresponds to generalization of age to ‘all’ = ‘any age’ = no information

• Use overall data (= single partition)

  • Overall mean, overall variance are too coarse)

• Different techniques to form groups for aggregation

  • binning - histograms

  • generalization - abstraction based on hierarchies

  • clustering - based on object similarity

• Histograms use binning to approximate data distributions

• Divide data into bins are store a representative for each bin

• To make equi-width histograms:

  • divide the range into N intervals of equal size (uniform grid)

  • If A and B are the lowest and highest values of the attribute, the width of the intervals will be (B-A)/N

Benefits:

• Most straightforward

• Easy to understand

Limitations:

• Outliers may dominate presentation

• Skewed data is not handled well

Benefits:

• Good data scaling

• Less prone to outliers

• Four-bin example is strongly related to boxplot

Limitations:

• Key information in bin boundaries (somehow subtle)

• If any value occurs often, the equal frequency criterion might not be met

• Flat groups (no serious hierarchies e.g. name, gender, phone no)

• Hierarchies by subgrouping (age -> 15-19, 20-24, 25-30)

• Hierarchies from schema information (major -> science/business/engineering)

• Concept hierarchies can be specified by (expert) users

• Heuristically generate a hierarchy for a set of (related) attributes

  • based on the number of distinct values in the attribute set

  • The attribute with the most distinct values is placed at the lowest level of the hierarchy (e.g. in adress hierarchy, street is the lowest)

• Counter-example: 20+ years, 12 months, 7 days of week

A process which abstracts a large set of task-relevant data in a database from low conceptual levels to higher ones

• Data-cube approach (OLAP / Roll-up) - manual

• Attribute-oriented induction (AOI) - automated

• Roll up

  • Summarize data by climbing up hierarchy or by dimension reduction

• Drill down

  • Reverse of roll up. From higher level summary to lower level summary or detailed data, or introducing new dimensions

• Slice and dice

  • Selection on one (slice) or more (dice) dimensions.

• Pivot (rotate)

  • Reorient the cube, visualization, 3D to series of 2D planes

• Drill across

  • involving more than one fact table

• Drill through

  • through the bottom level of the cube to its back-end relational tables (SQL)

• Each circle is called a footprint

• Footprints represent the granularities available for OLAP operations

• Efficient implementation of data generalizations

• Computation of various kinds of measures e.g. count, sum

• Generalization can be performed on a data cube by roll-up (or drill down)

• Handles only dimensions of simple non-numeric data and measures of simple aggregated numeric values

• Lack of intelligent analysis, does not suggest which dimensions should be used and what levels the generalization should aim at

• More automated approach than OLAP

• Apply aggregation by mergin identical, generalized tuples and accumulating their respective fcounts

• Builds on data focusing: task-relevant data, including dimensions, resulting in their initial relation

• Generates a generalization plan: decide for either attribute removal or attribute generalization

• Keep it

• Attribute Removal, for the following cases

  • There is a large set of distinct values for A but no generalization operator (concept hierarchy) on A

  • A’s higher level concepts are expressed in terms of other attributes (street is covered by city,state, country)

• Attribute Generalization

  • If there is a large set of distinct values for A, and there exists a set of generalization operators (concept hierarchy) on A, then select an operator and generalize A

• Attribute-threshold control: default or user-specified, typically 2-8 values

• Generalized relational threshold control: control the size of the final relation/rule e.g. 10-30 tuples

• Overgeneralization: values are too high-level

• Undergeneralization: level not sufficiently high

• Both yield tuples of poor usefulness

• Aiming at minimal degree of generalization

  • choose attribute that reduces the numer of tuples the most

  • useful heuristic: choose attributes with highest number of distinct values

• Aiming at similar degree of generalization for all attributes

  • choose the attribute currently with least degree of generalization

• User-controlled

  • domain experts may specifiy priorities for selection