Data Mining CA2

main idea of cure

• Stops the creation of a cluster hierarchy if a level consists of k clusters

• Uses multiple representative points to evaluate the distance between clusters, adjusts well to arbitrary shaped clusters and avoids single-link effect

Drawbacks of square-error based clustering method

• Consider only one point as representative of a cluster

• Good only for convex shaped, similar size and density, and if k can be reasonably estimated

Cure: Shrinking Representative Point

• Shrink the multiple representative points towards the gravity centre by a fraction of a.

• Multiple representatives capture the shape of the cluster

ROCK: Robust Clustering using linKs

• Use links to measure similarity/proximity

• Not distance based

• Computational complexity

ROCK Algorithm

• Draw random sample (get a random sample of the data)

• Cluster the data using the link agglomerative approach

• Label data in disk

Density-Based Clustering methods

Clustering based on density (local cluster criterion), such as density-connected points

Major features of Density-Based Clustering methods

• Discover clusters of arbitrary shape

• Handle noise

• One scan

• Need density parameters as termination condition

density reachable clustering

A point p is density-reachable from a point q with regard to Eps, MinPts if there is a chain of points p1, …, pn, p1 =q, pn = p such that pi+1 is directly density-reachable from pi

density-connected clustering

A point p is density-connected to a point q with regard to Eps, MinPts if there is a point o such that both, p and q are density-reachable from o with regard to Eps and MinPts

DBSCAN

• Density Based Spatial Clustering of Applications with Noise

• Relies on a density-based notion of cluster: A cluster is defined as a maximal set of density-connected points

• Discovers clusters of arbitrary shape in spatial datasets with noise

DBSCAN algorithm

1. Arbitrary select a point p

2. Retrieve all points density-reachable from p with regard to Eps and

MinPts.

3. If p is a core point, a cluster is formed.

4. If p is a border point, no points are density-reachable from p and

DBSCAN visits the next point of the dataset.

5. Continue the process until all of the points have been processed.

spatial data

• Generalise detailed geographic points into clustered regions, such as business, residential, industrial, or agricultural areas, according to land usage

• Require the merge of a set of geographic areas by spatial operation

image data

• Extracted by aggregation and/or approximation

• Size, colour, shape, texture, orientation, and relative positions and structures of the contained objects or regions in the image

music data

• Summarise its melody: based on the approximate patterns that repeatedly occur in the segment

• Summarise its style: based on its tone, tempo, or the major musical instruments played

object identifier

Generalise to the lowest level of class in the class/subclass hierarchies

class composition hierarchies

• generalise nested structured data

• generalise only objects closely related in semantics to the current one

Construction and mining of object cubes

• Extend the attribute-oriented induction method: Apply a sequence of class-based generalisation operators on different attributes; Continue until getting a small number of generalised objects that can be summarized as a concise in high-level terms

• For efficient implementation: Examine each attribute, generalise it to simple-valued data; Construct a multidimensional data cube (object cube)

multidimesnsional analysis strategy

• Generalise the plan-base in different directions

• Look for sequential patterns in the generalised plans

• Derive high-level plans

dimension tables

Generalise plan-base in a multidimensional way using dimension table

cardinality

Use the number of distinct values at each level to determine the right level of generalisation (level-“planning”)

operators

Use operators merge “+”, option “[ ]” to further generalise patterns

spatial data warehouse

• Integrated, subject-oriented, time-variant, and non-volatile spatial

• data repository for data analysis and decision making

Why is spatial data integration a big issue

• Structure-specific formats (raster- vs. vector-based, OO vs. relational models, different storage and indexing, etc.)

• Vendor-specific formats (ESRI, MapInfo, Inter-graph, etc.

spatial data cube

• multidimensional spatial database

• Both dimensions and measures may contain spatial componenent

On-line integration

• Collect and store pointers to spatial objects in a spatial data cube

• Expensive and slow, need efficient aggregation technique

Pre-processing

• Pre-compute and store all the possible combinations: huge space overhead

• Pre-compute and store rough approximations in a spatial data cube: accuracy trade-off

selective computation

Only materialise those which will be accessed frequently: a reasonable choice

Two-step mining of spatial association

• Step 1: Rough spatial computation (as a filter) - Use MBR (minimum bounding rectangle) for rough estimation

• Step2: Detailed spatial algorithm (as refinement) - Apply only to those objects which have passed the rough spatial association test (no lessthan min_support)

spatial classification

• Analyse spatial objects to derive classification schemes, such as decision trees in relevance to certain spatial properties (district, highway, river, etc.)

• Example: Classify regions in a province into rich vs. poor according to the average family income

Spatial trend analysis

• Detect changes and trends along a spatial dimension

• Study the trend of non spatial or spatial data changing with space

• Example: Observe the trend of changes of the climate or vegetation with the increasing distance from an ocean

time-series database

• Consists of sequences of values or events changing with time

• Data is recorded at regular intervals

• Characteristic time-series components: Trend, cycle, seasonal, irregula

time-series database applications

• Financial: stock price, inflation

• Biomedical: blood pressure

• Meteorological: precipitation

time series data

can be illustrated as a time-series graph which describes a point moving overtime

categories of time-series movement

• Long-term or trend movements (trend curve)

• Cyclic movements or cycle variations, e.g., business cycles

• Seasonal movements or seasonal variations: almost identical patterns that a time series appears to follow during corresponding months of successive years

• Irregular or random movements

the freehand method

• Fit the curve by looking at the graph

• Costly and barely reliable for large-scaled data mining

the least-square method

Find the curve minimising the sum of the squares of the deviation of points on the curve from the corresponding data point

the moving-average method

• Eliminate cyclic, seasonal and irregular patterns

• Loss of end data

• Sensitive to outliers

estimations of cyclic variations

If (approximate) periodicity of cycles occurs, cyclic index can be constructed in the same manner as seasonal indexe

estimation of irregular variations 

By adjusting the data for trend, seasonal and cyclic variation

prediction

• With systematic analysis of the trend, cyclic, seasonal, and irregular components, it is possible to make long- or short-term predictions with reasonable quality

similarity search

finds data sequences that differ only slightly from the given query sequence

whole matching similarity query

find a set of sequences that are similar to each other (as a whole)

subsequence matching similarity query

find sequences that contain sub-sequences that are similar to a given query sequence

typical applications for similarity search

• Financial market & Market basket data analysis

• Scientific databases

• Medical diagnosis

subsequence matching

• Breaking sequences: into a set of pieces of window with length w

• Extracting the features: For each subsequence inside the window

• Mapping: each sequence to a “trail” in the feature space

• Dividing the trail: of each sequence into “sub-trails” and represent each of them with minimum bounding rectangle

• Multi-piece assembly algorithm: to search for longer sequence matches

full periodicity

Every point in time contributes (precisely or approximately) to the periodicity

partial periodicity

Only some segments contribute to the periodicity