Agenda
 Why Data Mining?
 What Is Data Mining?
 A MultiDimensional View of Data Mining
 What Kinds of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Kinds of Technologies Are Used?
 What Kinds of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
Why Data Mining?
 The Explosive Growth of Data: from terabytes to petabytes
 Data collection and data availability
 Automated data collection tools, database systems, Web, computerized society
 Major sources of abundant data
 Business: Web, ecommerce, transactions, stocks, …
 Science: Remote sensing, bioinformatics, scientific simulation, …
 Society and everyone: news, digital cameras, YouTube
 We are drowning in data, but starving for knowledge!
 “Necessity is the mother of invention”—Data mining—Automated analysis of massive data sets
Evolution of Sciences: New Data Science Era
 Before 1600: Empirical science
 16001950s: Theoretical science
 Each discipline has grown a theoretical component. Theoretical models often motivate experiments and generalize our understanding.
 1950s1990s: Computational science
 Over the last 50 years, most disciplines have grown a third, computational branch (e.g. empirical, theoretical, and computational ecology, or physics, or linguistics.)
 Computational Science traditionally meant simulation. It grew out of our inability to find closedform solutions for complex mathematical models.
 1990now: Data science
 The flood of data from new scientific instruments and simulations
 The ability to economically store and manage petabytes of data online
 The Internet and computing Grid that makes all these archives universally accessible
 Scientific info. management, acquisition, organization, query, and visualization tasks scale almost linearly with data volumes
 Data mining is a major new challenge!
 Jim Gray and Alex Szalay, The World Wide Telescope: An Archetype for Online Science, Comm. ACM, 45(11): 5054, Nov. 2002
What Is Data Mining?
 Data mining (knowledge discovery from data)
 Extraction of interesting (nontrivial, implicit, previously unknown and potentially useful) patterns or knowledge from huge amount of data
 Data mining: a misnomer?
 Alternative names
 Knowledge discovery (mining) in databases (KDD), knowledge extraction, data/pattern analysis, data archeology, data dredging, information harvesting, business intelligence, etc.
 Watch out: Is everything “data mining”?
 Simple search and query processing
 (Deductive) expert systems
Knowledge Discovery (KDD) Process
 This is a view from typical database systems and data warehousing communities
 Data mining plays an essential role in the knowledge discovery process
Example: A Web Mining Framework
 Web mining usually involves
 Data cleaning
 Data integration from multiple sources
 Warehousing the data
 Data cube construction
 Data selection for data mining
 Data mining
 Presentation of the mining results
 Patterns and knowledge to be used or stored into knowledgebase
Data Mining in Business Intelligence
KDD Process: A Typical View from ML and Statistics
 This is a view from typical machine learning and statistics communities
Which View Do You Prefer?
 Which view do you prefer?
 KDD vs. ML/Stat. vs. Business Intelligence
 Depending on the data, applications, and your focus
 Data Mining vs. Data Exploration
 Business intelligence view
 Warehouse, data cube, reporting but not much mining
 Business objects vs. data mining tools
 Supply chain example: mining vs. OLAP vs. presentation tools
 Data presentation vs. data exploration
MultiDimensional View of Data Mining
 Data to be mined
 Database data (extendedrelational, objectoriented, heterogeneous, legacy), data warehouse, transactional data, stream, spatiotemporal, timeseries, sequence, text and web, multimedia, graphs & social and information networks
 Knowledge to be mined (or: Data mining functions)
 Characterization, discrimination, association, classification, clustering, trend/deviation, outlier analysis, etc.
 Descriptive vs. predictive data mining
 Multiple/integrated functions and mining at multiple levels
 Techniques utilized
 Dataintensive, data warehouse (OLAP), machine learning, statistics, pattern recognition, visualization, highperformance, etc.
 Applications adapted
 Retail, telecommunication, banking, fraud analysis, biodata mining, stock market analysis, text mining, Web mining, etc.
Data Mining: On What Kinds of Data?
 Databaseoriented data sets and applications
 Relational database, data warehouse, transactional database
 Advanced data sets and advanced applications
 Data streams and sensor data
 Timeseries data, temporal data, sequence data (incl. biosequences)
 Structure data, graphs, social networks and multilinked data
 Objectrelational databases
 Heterogeneous databases and legacy databases
 Spatial data and spatiotemporal data
 Multimedia database
 Text databases
 The WorldWide Web
Data Mining Function: Generalization
 Information integration and data warehouse construction
 Data cleaning, transformation, integration, and multidimensional data model
 Data cube technology
 Scalable methods for computing (i.e., materializing) multidimensional aggregates
 OLAP (online analytical processing)
 Multidimensional concept description: Characterization and discrimination
 Generalize, summarize, and contrast data characteristics, e.g., dry vs. wet region
Data Mining Function: Association and Correlation Analysis
 Frequent patterns (or frequent itemsets)
 What items are frequently purchased together in your Walmart?
 Association, correlation vs. causality
 A typical association rule
 Diaper → Beer [0.5%, 75%] (support, confidence)
 Are strongly associated items also strongly correlated?
 How to mine such patterns and rules efficiently in large datasets?
 How to use such patterns for classification, clustering, and other applications?
Data Mining Function: Classification
 Classification and label prediction
 Construct models (functions) based on some training examples
 Describe and distinguish classes or concepts for future prediction
 E.g., classify countries based on (climate), or classify cars based on (gas mileage)
 Predict some unknown class labels
 Typical methods
 Decision trees, naïve Bayesian classification, support vector machines, neural networks, rulebased classification, patternbased classification, logistic regression, …
 Typical applications:
 Credit card fraud detection, direct marketing, classifying stars, diseases, webpages, …
Data Mining Function: Cluster Analysis
 Unsupervised learning (i.e., Class label is unknown)
 Group data to form new categories (i.e., clusters), e.g., cluster houses to find distribution patterns
 Principle: Maximizing intraclass similarity & minimizing interclass similarity
 Many methods and applications
Data Mining Function: Outlier Analysis
 Outlier analysis
 Outlier: A data object that does not comply with the general behavior of the data
 Noise or exception? ― One person’s garbage could be another person’s treasure
 Methods: by product of clustering or regression analysis, …
 Useful in fraud detection, rare events analysis
Time and Ordering: Sequential Pattern, Trend and Evolution Analysis
 Sequence, trend and evolution analysis
 Trend, timeseries, and deviation analysis: e.g., regression and value prediction
 Sequential pattern mining
 e.g., first buy digital camera, then buy large SD memory cards
 Periodicity analysis
 Motifs and biological sequence analysis
 Approximate and consecutive motifs
 Similaritybased analysis
 Mining data streams
 Ordered, timevarying, potentially infinite, data streams
Structure and Network Analysis
 Graph mining
 Finding frequent subgraphs (e.g., chemical compounds), trees (XML), substructures (web fragments)
 Information network analysis
 Social networks: actors (objects, nodes) and relationships (edges)
 e.g., author networks in CS, terrorist networks
 Multiple heterogeneous networks
 A person could be multiple information networks: friends, family, classmates, …
 Links carry a lot of semantic information: Link mining
 Web mining
 Web is a big information network: from PageRank to Google
 Analysis of Web information networks
 Web community discovery, opinion mining, usage mining, …
Evaluation of Knowledge
 Are all mined knowledge interesting?
 One can mine tremendous amount of “patterns” and knowledge
 Some may fit only certain dimension space (time, location, …)
 Some may not be representative, may be transient, …
 Evaluation of mined knowledge → directly mine only interesting knowledge?
 Descriptive vs. predictive
 Coverage
 Typicality vs. novelty
 Accuracy
 Timeliness
 …
Data Mining: Confluence of Multiple Disciplines
Why Confluence of Multiple Disciplines?
 Tremendous amount of data
 Algorithms must be highly scalable to handle such as terabytes of data
 Highdimensionality of data
 Microarray may have tens of thousands of dimensions
 High complexity of data
 Data streams and sensor data
 Timeseries data, temporal data, sequence data
 Structure data, graphs, social networks and multilinked data
 Heterogeneous databases and legacy databases
 Spatial, spatiotemporal, multimedia, text and Web data
 Software programs, scientific simulations
 New and sophisticated applications
Applications of Data Mining
 Web page analysis: from web page classification, clustering to PageRank & HITS algorithms
 Collaborative analysis & recommender systems
 Basket data analysis to targeted marketing
 Biological and medical data analysis: classification, cluster analysis (microarray data analysis), biological sequence analysis, biological network analysis
 Data mining and software engineering (e.g., IEEE Computer, Aug. 2009 issue)
 From major dedicated data mining systems/tools (e.g., SAS, MS SQLServer Analysis Manager, Oracle Data Mining Tools) to invisible data mining
Major Issues in Data Mining
 Mining Methodology
 Mining various and new kinds of knowledge
 Mining knowledge in multidimensional space
 Data mining: An interdisciplinary effort
 Boosting the power of discovery in a networked environment
 Handling noise, uncertainty, and incompleteness of data
 Pattern evaluation and pattern or constraintguided mining
 User Interaction
 Interactive mining
 Incorporation of background knowledge
 Presentation and visualization of data mining results
Major Issues in Data Mining (cont')
 Efficiency and Scalability
 Efficiency and scalability of data mining algorithms
 Parallel, distributed, stream, and incremental mining methods
 Diversity of data types
 Handling complex types of data
 Mining dynamic, networked, and global data repositories
 Data mining and society
 Social impacts of data mining
 Privacypreserving data mining
 Invisible data mining
A Brief History of Data Mining Society
 1989 IJCAI Workshop on Knowledge Discovery in Databases
 Knowledge Discovery in Databases (G. PiatetskyShapiro and W. Frawley, 1991)
 19911994 Workshops on Knowledge Discovery in Databases
 Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. PiatetskyShapiro, P. Smyth, and R. Uthurusamy, 1996)
 19951998 International Conferences on Knowledge Discovery in Databases and Data Mining (KDD’9598)
 Journal of Data Mining and Knowledge Discovery (1997)
 ACM SIGKDD conferences since 1998 and SIGKDD Explorations
 More conferences on data mining
 PAKDD (1997), PKDD (1997), SIAMData Mining (2001), (IEEE) ICDM (2001), WSDM (2008), etc.
 ACM Transactions on KDD (2007)
Conferences and Journals on Data Mining
 KDD Conferences
 ACM SIGKDD Int. Conf. on Knowledge Discovery in Databases and Data Mining (KDD)
 SIAM Data Mining Conf. (SDM)
 (IEEE) Int. Conf. on Data Mining (ICDM)
 European Conf. on Machine Learning and Principles and practices of Knowledge Discovery and Data Mining (ECMLPKDD)
 PacificAsia Conf. on Knowledge Discovery and Data Mining (PAKDD)
 Int. Conf. on Web Search and Data Mining (WSDM)
 Other related conferences
 DB conferences: ACM SIGMOD, VLDB, ICDE, EDBT, ICDT, …
 Web and IR conferences: WWW, SIGIR, WSDM
 ML conferences: ICML, NIPS
 PR conferences: CVPR,
 Journals
 Data Mining and Knowledge Discovery (DAMI or DMKD)
 IEEE Trans. On Knowledge and Data Eng. (TKDE)
 KDD Explorations
 ACM Trans. on KDD
Where to Find References? DBLP, CiteSeer, Google
 Data mining and KDD (SIGKDD: CDROM)
 Conferences: ACMSIGKDD, IEEEICDM, SIAMDM, PKDD, PAKDD, etc.
 Journal: Data Mining and Knowledge Discovery, KDD Explorations, ACM TKDD
 Database systems (SIGMOD: ACM SIGMOD Anthology—CD ROM)
 Conferences: ACMSIGMOD, ACMPODS, VLDB, IEEEICDE, EDBT, ICDT, DASFAA
 Journals: IEEETKDE, ACMTODS/TOIS, JIIS, J. ACM, VLDB J., Info. Sys., etc.
 AI & Machine Learning
 Conferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), CVPR, NIPS, etc.
 Journals: Machine Learning, Artificial Intelligence, Knowledge and Information Systems, IEEEPAMI, etc.
 Web and IR
 Conferences: SIGIR, WWW, CIKM, etc.
 Journals: WWW: Internet and Web Information Systems,
 Statistics
 Conferences: Joint Stat. Meeting, etc.
 Journals: Annals of statistics, etc.
 Visualization
 Conference proceedings: CHI, ACMSIGGraph, etc.
 Journals: IEEE Trans. visualization and computer graphics, etc.
Recommended Reference Books
 E. Alpaydin. Introduction to Machine Learning, 2nd ed., MIT Press, 2011
 S. Chakrabarti. Mining the Web: Statistical Analysis of Hypertex and SemiStructured Data. Morgan Kaufmann, 2002
 R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2ed., WileyInterscience, 2000
 T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley & Sons, 2003
 U. M. Fayyad, G. PiatetskyShapiro, P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996
 U. Fayyad, G. Grinstein, and A. Wierse, Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001
 J. Han, M. Kamber, and J. Pei, Data Mining: Concepts and Techniques. Morgan Kaufmann, 3rd ed. , 2011
 T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., Springer, 2009
 B. Liu, Web Data Mining, Springer 2006
 T. M. Mitchell, Machine Learning, McGraw Hill, 1997
 Y. Sun and J. Han, Mining Heterogeneous Information Networks, Morgan & Claypool, 2012
 P.N. Tan, M. Steinbach and V. Kumar, Introduction to Data Mining, Wiley, 2005
 S. M. Weiss and N. Indurkhya, Predictive Data Mining, Morgan Kaufmann, 1998
 I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, 2nd ed. 2005
Summary
 Data mining: Discovering interesting patterns and knowledge from massive amount of data
 A natural evolution of science and information technology, in great demand, with wide applications
 A KDD process includes data cleaning, data integration, data selection, transformation, data mining, pattern evaluation, and knowledge presentation
 Mining can be performed in a variety of data
 Data mining functionalities: characterization, discrimination, association, classification, clustering, trend and outlier analysis, etc.
 Data mining technologies and applications
 Major issues in data mining
Agenda
 Data Objects and Attribute Types
 Basic Statistical Descriptions of Data
 Data Visualization
 Measuring Data Similarity and Dissimilarity
 Summary
Types of Data Sets

Record

Relational records

Data matrix, e.g., numerical matrix, crosstabs

Document data: text documents: termfrequency vector

Transaction data

Graph and network

World Wide Web

Social or information networks

Molecular Structures

Ordered

Video data: sequence of images

Temporal data: timeseries

Sequential Data: transaction sequences

Genetic sequence data

Spatial, image and multimedia:

Spatial data: maps

Image data:

Video data:
Important Characteristics of Structured Data
 Dimensionality
 Sparsity
 Resolution
 Patterns depend on the scale
 Distribution
 Centrality and dispersion
Data Objects
 Data sets are made up of data objects.
 A data object represents an entity.
 Examples:
 sales database: customers, store items, sales
 medical database: patients, treatments
 university database: students, professors, courses
 Also called samples , examples, instances, data points, objects, tuples.
 Data objects are described by attributes.
 Database rows > data objects; columns >attributes.
Attributes
 Attribute (or dimensions, features, variables): a data field, representing a characteristic or feature of a data object.
 E.g., customer _ID, name, address
 Types:
 Nominal
 Binary
 Numeric: quantitative
 Intervalscaled
 Ratioscaled
Attribute Types
 Nominal: categories, states, or “names of things”
 Hair_color = {auburn, black, blond, brown, grey, red, white}
 marital status, occupation, ID numbers, zip codes
 Binary
 Nominal attribute with only 2 states (0 and 1)
 Symmetric binary: both outcomes equally important
 Asymmetric binary: outcomes not equally important.
 e.g., medical test (positive vs. negative)
 Convention: assign 1 to most important outcome (e.g., HIV positive)
 Ordinal
 Values have a meaningful order (ranking) but magnitude between successive values is not known.
 Size = {small, medium, large}, grades, army rankings
Numeric Attribute Types
 Quantity (integer or realvalued)
 Interval
 Measured on a scale of equalsized units
 Values have order
 E.g., temperature in C˚or F˚, calendar dates
 No true zeropoint
 Ratio
 Inherent zeropoint
 We can speak of values as being an order of magnitude larger than the unit of measurement (10 K˚ is twice as high as 5 K˚).
 e.g., temperature in Kelvin, length, counts, monetary quantities
Discrete vs. Continuous Attributes
 Discrete Attribute
 Has only a finite or countably infinite set of values
 E.g., zip codes, profession, or the set of words in a collection of documents
 Sometimes, represented as integer variables
 Note: Binary attributes are a special case of discrete attributes
 Continuous Attribute
 Has real numbers as attribute values
 E.g., temperature, height, or weight
 Practically, real values can only be measured and represented using a finite number of digits
 Continuous attributes are typically represented as floatingpoint variables
Basic Statistical Descriptions of Data
 Motivation
 To better understand the data: central tendency, variation and spread
 Data dispersion characteristics
 median, max, min, quantiles, outliers, variance, etc.
 Numerical dimensions correspond to sorted intervals
 Data dispersion: analyzed with multiple granularities of precision
 Boxplot or quantile analysis on sorted intervals
 Dispersion analysis on computed measures
 Folding measures into numerical dimensions
 Boxplot or quantile analysis on the transformed cube
Measuring the Central Tendency

Mean (algebraic measure) (sample vs. population):
\[ {\bar{x}}=\frac{1}{n} \sum_{i=1}^{n}x_{i} \]
\[ \mu = \frac{\sum x}{N} \]

Note:
n
is sample size and
N
is population size.

Weighted arithmetic mean:

Trimmed mean: chopping extreme values
\[ {\bar{x}}=\frac{\sum_{i=1}^{n}w_{i}x_{i} }{\sum_{i=1}^{n}w_{i}} \]

Median:

Middle value if odd number of values, or average of the middle two values otherwise

Estimated by interpolation (for
grouped data
):
\[ median = {L_{1}} + (\frac{\frac{n}{2}(\sum freq)l)}{freq_{median}}) width \]
Measuring the Central Tendency (cont')
Symmetric vs. Skewed Data
 Median, mean and mode of symmetric, positively and negatively skewed data
Measuring the Dispersion of Data
 Quartiles, outliers and boxplots
 Quartiles: Q1 (25th percentile), Q3 (75th percentile)
 Interquartile range: IQR = Q3 – Q1
 Five number summary: min, Q1, median, Q3, max
 Boxplot: ends of the box are the quartiles; median is marked; add whiskers, and plot outliers individually
 Outlier: usually, a value higher/lower than 1.5 x IQR
 Variance and standard deviation (sample: s, population: σ)
 Variance: (algebraic, scalable computation)
\[
{s^{2}}=\frac{1}{n1}\sum_{i=1}^{n}(x_{i}\bar{x})^2=\frac{1}{n1}[\sum_{i=1}^{n}x_{i}^2\frac{1}{n}(\sum_{i=1}^{n}x_{i})^2]
\]
\[ {\sigma ^{2}}=\frac{1}{N}\sum_{i=1}^{n}(x_{i}\mu)^2=\frac{1}{N}\sum_{i=1}^{n}x_{i}^2\mu ^2 \]
 Standard deviation s (or σ) is the square root of variance s2 (or σ2)
Boxplot Analysis
 Fivenumber summary of a distribution
 Minimum, Q1, Median, Q3, Maximum
 Boxplot
 Data is represented with a box
 The ends of the box are at the first and third quartiles, i.e., the height of the box is IQR
 The median is marked by a line within the box
 Whiskers: two lines outside the box extended to Minimum and Maximum
 Outliers: points beyond a specified outlier threshold, plotted individually
Visualization of Data Dispersion: 3D Boxplots
Properties of Normal Distribution Curve
 The normal (distribution) curve
 From μ–σ to μ+σ: contains about 68% of the measurements (μ: mean, σ: standard deviation)
 From μ–2σ to μ+2σ: contains about 95% of it
 From μ–3σ to μ+3σ: contains about 99.7% of it
Graphic Displays of Basic Statistical Descriptions
 Boxplot: graphic display of fivenumber summary
 Histogram: xaxis are values, yaxis repres. frequencies
 Quantile plot: each value xi is paired with fi indicating that approximately 100 fi % of data are ≤ xi
 Quantilequantile (qq) plot: graphs the quantiles of one univariant distribution against the corresponding quantiles of another
 Scatter plot: each pair of values is a pair of coordinates and plotted as points in the plane
Histogram Analysis
 Histogram: Graph display of tabulated frequencies, shown as bars
 It shows what proportion of cases fall into each of several categories
 Differs from a bar chart in that it is the area of the bar that denotes the value, not the height as in bar charts, a crucial distinction when the categories are not of uniform width
 The categories are usually specified as nonoverlapping intervals of some variable. The categories (bars) must be adjacent
Histograms Often Tell More than Boxplots
  The two histograms shown in the left may have the same boxplot representation
 The same values for: min, Q1, median, Q3, max
 But they have rather different data distributions

Quantile Plot
 Displays all of the data (allowing the user to assess both the overall behavior and unusual occurrences)
 Plots quantile information
 For a data xi data sorted in increasing order, fi indicates that approximately 100 fi% of the data are below or equal to the value xi
QuantileQuantile (QQ) Plot
 Graphs the quantiles of one univariate distribution against the corresponding quantiles of another
 View: Is there is a shift in going from one distribution to another?
 Example shows unit price of items sold at Branch 1 vs. Branch 2 for each quantile. Unit prices of items sold at Branch 1 tend to be lower than those at Branch 2.
Scatter plot
 Provides a first look at bivariate data to see clusters of points, outliers, etc
 Each pair of values is treated as a pair of coordinates and plotted as points in the plane
Positively and Negatively Correlated Data
Uncorrelated Data
Data Visualization
 Why data visualization?
 Gain insight into an information space by mapping data onto graphical primitives
 Provide qualitative overview of large data sets
 Search for patterns, trends, structure, irregularities, relationships among data
 Help find interesting regions and suitable parameters for further quantitative analysis
 Provide a visual proof of computer representations derived
 Categorization of visualization methods:
 Pixeloriented visualization techniques
 Geometric projection visualization techniques
 Iconbased visualization techniques
 Hierarchical visualization techniques
 Visualizing complex data and relations
PixelOriented Visualization Techniques
 For a data set of m dimensions, create m windows on the screen, one for each dimension
 The m dimension values of a record are mapped to m pixels at the corresponding positions in the windows
 The colors of the pixels reflect the corresponding values
Laying Out Pixels in Circle Segments

To save space and show the connections among multiple dimensions, space filling is often done in a circle segment
Geometric Projection Visualization Techniques
 Visualization of geometric transformations and projections of the data
 Methods
 Direct visualization
 Scatterplot and scatterplot matrices
 Landscapes
 Projection pursuit technique: Help users find meaningful projections of multidimensional data
 Prosection views
 Hyperslice
 Parallel coordinates
Direct Data Visualization
 Ribbons with Twists Based on Vorticity
Scatterplot Matrices
 Matrix of scatterplots (xydiagrams) of the kdim. data [total of (k2/2k) scatterplots]
Landscapes
 Visualization of the data as perspective landscape
 The data needs to be transformed into a (possibly artificial) 2D spatial representation which preserves the characteristics of the data
Parallel Coordinates
 n equidistant axes which are parallel to one of the screen axes and correspond to the attributes
 The axes are scaled to the [minimum, maximum]: range of the corresponding attribute
 Every data item corresponds to a polygonal line which intersects each of the axes at the point which corresponds to the value for the attribute
Parallel Coordinates of a Data Set
IconBased Visualization Techniques
 Visualization of the data values as features of icons
 Typical visualization methods
 Chernoff Faces
 Stick Figures
 General techniques
 Shape coding: Use shape to represent certain information encoding
 Color icons: Use color icons to encode more information
 Tile bars: Use small icons to represent the relevant feature vectors in document retrieval
Chernoff Faces
 A way to display variables on a twodimensional surface, e.g., let x be eyebrow slant, y be eye size, z be nose length, etc.
 The figure shows faces produced using 10 characteristicshead eccentricity, eye size, eye spacing, eye eccentricity, pupil size, eyebrow slant, nose size, mouth shape, mouth size, and mouth opening): Each assigned one of 10 possible values, generated using Mathematica (S. Dickson)
 REFERENCE: Gonick, L. and Smith, W. The Cartoon Guide to Statistics. New York: Harper Perennial, p. 212, 1993
 Weisstein, Eric W. "Chernoff Face." From MathWorldA Wolfram Web Resource. mathworld.wolfram.com/ChernoffFace.html
Hierarchical Visualization Techniques
 Visualization of the data using a hierarchical partitioning into subspaces
 Methods
 Dimensional Stacking
 WorldswithinWorlds
 TreeMap
 Cone Trees
 InfoCube
Dimensional Stacking
 Partitioning of the ndimensional attribute space in 2D subspaces, which are ‘stacked’ into each other
 Partitioning of the attribute value ranges into classes. The important attributes should be used on the outer levels.
 Adequate for data with ordinal attributes of low cardinality
 But, difficult to display more than nine dimensions
 Important to map dimensions appropriately
Dimensional Stacking
Used by permission of M. Ward, Worcester Polytechnic Institute
 Visualization of oil mining data with longitude and latitude mapped to the outer x, yaxes and ore grade and depth mapped to the inner x, yaxes
WorldswithinWorlds
 Assign the function and two most important parameters to innermost world
 Fix all other parameters at constant values  draw other (1 or 2 or 3 dimensional worlds choosing these as the axes)
 Software that uses this paradigm
 N–vision: Dynamic interaction through data glove and stereo displays, including rotation, scaling (inner) and translation (inner/outer)
 Auto Visual: Static interaction by means of queries
TreeMap
 Screenfilling method which uses a hierarchical partitioning of the screen into regions depending on the attribute values
 The x and ydimension of the screen are partitioned alternately according to the attribute values (classes)
InfoCube
 A 3D visualization technique where hierarchical information is displayed as nested semitransparent cubes
 The outermost cubes correspond to the top level data, while the subnodes or the lower level data are represented as smaller cubes inside the outermost cubes, and so on
ThreeD Cone Trees





3D
cone tree
visualization technique works well for up to a thousand nodes or so

First build a
2D
circle tree
that arranges its nodes in concentric circles centered on the root node

Cannot avoid overlaps when projected to 2D

G. Robertson, J. Mackinlay, S. Card. “Cone Trees: Animated 3D Visualizations of Hierarchical Information”,
ACM SIGCHI'91

Graph
from Nadeau Software Consulting website: Visualize a social network
data set that models the way an infection spreads from one person to the
next


Visualizing Complex Data and Relations
 Visualizing nonnumerical data: text and social networks
 Tag cloud: visualizing usergenerated tags
 The importance of tag is represented by font size/color
 Besides text data, there are also methods to visualize relationships, such as visualizing social networks
Newsmap: Google News Stories in 2005
Similarity and Dissimilarity
 Similarity
 Numerical measure of how alike two data objects are
 Value is higher when objects are more alike
 Often falls in the range [0,1]
 Dissimilarity (e.g., distance)
 Numerical measure of how different two data objects are
 Lower when objects are more alike
 Minimum dissimilarity is often 0
 Upper limit varies
 Proximity refers to a similarity or dissimilarity
Data Matrix and Dissimilarity Matrix





Data matrix

n data points with p dimensions

Two modes

Dissimilarity matrix

n data points, but registers only the distance

A triangular matrix

Single mode


Proximity Measure for Nominal Attributes

Can take 2 or more states, e.g., red, yellow, blue, green (generalization of a binary attribute)

Method 1: Simple matching

m
: # of matches,
p
: total # of variables
\[ d(i,j)=\frac{pm}{p} \]

Method 2: Use a large number of binary attributes

creating a new binary attribute for each of the
M
nominal states
Proximity Measure for Binary Attributes
 A contingency table for binary data
 Distance measure for symmetric binary variables:
\[ d(i,j)=\frac{r+s}{q+r+s+t} \]
 Distance measure for asymmetric binary variables:
\[ d(i,j)=\frac{r+s}{q+r+s} \]
 Jaccard coefficient (similarity measure for asymmetric binary variables):
\[ sim_{Jaccard}(i,j)=\frac{q}{q+r+s} \]
 Note: Jaccard coefficient is the same as “coherence”:
\[ coherence(i,j)=\frac{sup(i,j)}{sup(i)+sup(j)sup(i,j)}=\frac{q}{(q+r)(q+s)q} \]
Dissimilarity between Binary Variables
 Gender is a symmetric attribute
 The remaining attributes are asymmetric binary
 Let the values Y and P be 1, and the value N 0
Standardizing Numeric Data
\[ z=\frac{x\mu}{\sigma } \]
 X: raw score to be standardized, μ: mean of the population, σ: standard deviation
 the distance between the raw score and the population mean in units of the standard deviation
 negative when the raw score is below the mean, “+” when above
 An alternative way: Calculate the mean absolute deviation, where
\[ m_{f}= \frac{1}{n}(x_{1f}+x_{2f}+...+x_{nf}) \]
 standardized measure (zscore):
\[ z_{if}=\frac{(x_{if}m_{f})}{S_{f}} \]
 Using mean absolute deviation is more robust than using standard deviation
\[ s_{f}=\frac{1}{n} (x_{1f}m_{f}+x_{2f}m_{f}+...+x_{nf}m_{f}) \]Example: Data Matrix and Dissimilarity Matrix
Distance on Numeric Data: Minkowski Distance
 Minkowski distance: A popular distance measure
where i = (xi1, xi2, …, xip) and j = (xj1, xj2, …, xjp) are two pdimensional data objects, and h is the order (the distance so defined is also called Lh norm)
 Properties
 d(i, j) > 0 if i ≠ j, and d(i, i) = 0 (Positive definiteness)
 d(i, j) = d(j, i) (Symmetry)
 d(i, j) ≤ d(i, k) + d(k, j) (Triangle Inequality)
 A distance that satisfies these properties is a metric
Special Cases of Minkowski Distance
 h = 1: Manhattan (city block, L1 norm) distance
 E.g., the Hamming distance: the number of bits that are different between two binary vectors
\[ d(i,j)=x_{i1}x_{j1}+x_{i2}x_{j2}+...+x_{ip}x_{jp} \]
 h = 2: (L2 norm) Euclidean distance
\[ d(i,j)=\sqrt{(x_{i1}x_{j1}^2+x_{i2}x_{j2}^2+...+x_{ip}x_{jp}^2)} \]
 h →≈ . “supremum” (Lmax norm, L≈ norm) distance.
 This is the maximum difference between any component (attribute) of the vectors
\[ d(i,j)=\lim_{h\rightarrow \infty }(\sum_{f=1}^{p}x_{if}x_{jf}^{h})^\frac{1}{h} =max_{f}^{p}x_{if}x_{jf} \]Example: Minkowski Distance
Ordinal Variables
 An ordinal variable can be discrete or continuous
 Order is important, e.g., rank
 Can be treated like intervalscaled
 replace xif by their rank
\[ r_{if} \epsilon \left \{ 1,...,M_{f} \right \} \]
 map the range of each variable onto [0, 1] by replacing ith object in the fth variable by
 compute the dissimilarity using methods for intervalscaled variables
\[ z_{if} = \frac{r_{if}1}{M_{f}1} \]Attributes of Mixed Type
 A database may contain all attribute types
 Nominal, symmetric binary, asymmetric binary, numeric, ordinal
 One may use a weighted formula to combine their effects
\[ d(i,j) = \frac{\sum_{f=1}^{p} \delta _{ij}^{(f)} d_{ij}^{(f)}}{\sum_{f=1}^{p} \delta _{ij}^{(f)}} \]
 f is binary or nominal:
 dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise
 f is numeric: use the normalized distance
 f is ordinal
 Compute ranks rif and
 Treat zif as intervalscaled
\[ z_{if} = \frac{r_{if}1}{M_{f}1} \]Cosine Similarity
 A document can be represented by thousands of attributes, each recording the frequency of a particular word (such as keywords) or phrase in the document.
 Other vector objects: gene features in microarrays, …
 Applications: information retrieval, biologic taxonomy, gene feature mapping, ...
 Cosine measure: If d1 and d2 are two vectors (e.g., termfrequency vectors), then
cos(d1, d2) = (d1 ⋅ d2) /d1 d2 ,
where ⋅ indicates vector dot product, d: the length of vector d
Example: Cosine Similarity
 cos(d1, d2) = (d1 ⋅ d2) / d1 d2 ,
where ⋅ indicates vector dot product, d: the length of vector d  Ex: Find the similarity between documents 1 and 2.
d1 = (5, 0, 3, 0, 2, 0, 0, 2, 0, 0)
d2 = (3, 0, 2, 0, 1, 1, 0, 1, 0, 1)
d1 ⋅ d2 = 5*3+0*0+3*2+0*0+2*1+0*1+0*1+2*1+0*0+0*1 = 25
d1 = (5*5+0*0+3*3+0*0+2*2+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481
d2 = (3*3+0*0+2*2+0*0+1*1+1*1+0*0+1*1+0*0+1*1)0.5 = (17) 0.5 = 4.12
cos(d1, d2 ) = 0.94
Summary
 Data attribute types: nominal, binary, ordinal, intervalscaled, ratioscaled
 Many types of data sets, e.g., numerical, text, graph, Web, image.
 Gain insight into the data by:
 Basic statistical data description: central tendency, dispersion, graphical displays
 Data visualization: map data onto graphical primitives
 Measure data similarity
 Above steps are the beginning of data preprocessing.
 Many methods have been developed but still an active area of research.
References
 W. Cleveland, Visualizing Data, Hobart Press, 1993
 T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley, 2003
 U. Fayyad, G. Grinstein, and A. Wierse. Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001
 L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.
 H. V. Jagadish et al., Special Issue on Data Reduction Techniques. Bulletin of the Tech. Committee on Data Eng., 20(4), Dec. 1997
 D. A. Keim. Information visualization and visual data mining, IEEE trans. on Visualization and Computer Graphics, 8(1), 2002
 D. Pyle. Data Preparation for Data Mining. Morgan Kaufmann, 1999
 S. Santini and R. Jain,” Similarity measures”, IEEE Trans. on Pattern Analysis and Machine Intelligence, 21(9), 1999
 E. R. Tufte. The Visual Display of Quantitative Information, 2nd ed., Graphics Press, 2001
 C. Yu et al., Visual data mining of multimedia data for social and behavioral studies, Information Visualization, 8(1), 2009
Agenda
 Data Preprocessing: An Overview
 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary
Data Quality: Why Preprocess the Data?
 Measures for data quality: A multidimensional view
 Accuracy: correct or wrong, accurate or not
 Completeness: not recorded, unavailable, …
 Consistency: some modified but some not, dangling, …
 Timeliness: timely update?
 Believability: how trustable the data are correct?
 Interpretability: how easily the data can be understood?
Major Tasks in Data Preprocessing
 Data cleaning
 Fill in missing values, smooth noisy data, identify or remove outliers, and resolve inconsistencies
 Data integration
 Integration of multiple databases, data cubes, or files
 Data reduction
 Dimensionality reduction
 Numerosity reduction
 Data compression
 Data transformation and data discretization
 Normalization
 Concept hierarchy generation
Data Cleaning
 Data in the Real World Is Dirty: Lots of potentially incorrect data, e.g., instrument faulty, human or computer error, transmission error
 incomplete: lacking attribute values, lacking certain attributes of interest, or containing only aggregate data
 e.g., Occupation=“ ” (missing data)
 noisy: containing noise, errors, or outliers
 e.g., Salary=“−10” (an error)
 inconsistent: containing discrepancies in codes or names, e.g.,
 Age=“42”, Birthday=“03/07/2010”
 Was rating “1, 2, 3”, now rating “A, B, C”
 discrepancy between duplicate records
 Intentional (e.g., disguised missing data)
 Jan. 1 as everyone’s birthday?
Incomplete (Missing) Data
 Data is not always available
 E.g., many tuples have no recorded value for several attributes, such as customer income in sales data
 Missing data may be due to
 equipment malfunction
 inconsistent with other recorded data and thus deleted
 data not entered due to misunderstanding
 certain data may not be considered important at the time of entry
 not register history or changes of the data
 Missing data may need to be inferred
How to Handle Missing Data?
 Ignore the tuple: usually done when class label is missing (when doing classification)—not effective when the % of missing values per attribute varies considerably
 Fill in the missing value manually: tedious + infeasible?
 Fill in it automatically with
 a global constant : e.g., “unknown”, a new class?!
 the attribute mean
 the attribute mean for all samples belonging to the same class: smarter
 the most probable value: inferencebased such as Bayesian formula or decision tree
Noisy Data
 Noise: random error or variance in a measured variable
 Incorrect attribute values may be due to
 faulty data collection instruments
 data entry problems
 data transmission problems
 technology limitation
 inconsistency in naming convention
 Other data problems which require data cleaning
 duplicate records
 incomplete data
 inconsistent data
How to Handle Noisy Data?
 Binning
 first sort data and partition into (equalfrequency) bins
 then one can smooth by bin means, smooth by bin median, smooth by bin boundaries, etc.
 Regression
 smooth by fitting the data into regression functions
 Clustering
 detect and remove outliers
 Combined computer and human inspection
 detect suspicious values and check by human (e.g., deal with possible outliers)
Data Cleaning as a Process
 Data discrepancy detection
 Use metadata (e.g., domain, range, dependency, distribution)
 Check field overloading
 Check uniqueness rule, consecutive rule and null rule
 Use commercial tools
 Data scrubbing: use simple domain knowledge (e.g., postal code, spellcheck) to detect errors and make corrections
 Data auditing: by analyzing data to discover rules and relationship to detect violators (e.g., correlation and clustering to find outliers)
 Data migration and integration
 Data migration tools: allow transformations to be specified
 ETL (Extraction/Transformation/Loading) tools: allow users to specify transformations through a graphical user interface
 Integration of the two processes
 Iterative and interactive (e.g., Potter’s Wheels)
Data Integration
 Combines data from multiple sources into a coherent store
 Schema integration: e.g., A.custid ≡ B.cust#
 Integrate metadata from different sources
 Entity identification problem:
 Identify real world entities from multiple data sources, e.g., Bill Clinton = William Clinton
 Detecting and resolving data value conflicts
 For the same real world entity, attribute values from different sources are different
 Possible reasons: different representations, different scales, e.g., metric vs. British units
Handling Redundancy in Data Integration
 Redundant data occur often when integration of multiple databases
 Object identification: The same attribute or object may have different names in different databases
 Derivable data: One attribute may be a “derived” attribute in another table, e.g., annual revenue
 Redundant attributes may be able to be detected by correlation analysis and covariance analysis
 Careful integration of the data from multiple sources may help reduce/avoid redundancies and inconsistencies and improve mining speed and quality
Correlation Analysis (Nominal Data)
\[ X^{2}=\sum \frac{(ObservedExpected)^2}{Expected} \]
 The larger the Χ^2 value, the more likely the variables are related
 The cells that contribute the most to the Χ2 value are those whose actual count is very different from the expected count
 Correlation does not imply causality
 # of hospitals and # of cartheft in a city are correlated
 Both are causally linked to the third variable: population
ChiSquare Calculation: An Example
 X^2 (chisquare) calculation (numbers in parenthesis are expected counts calculated based on the data distribution in the two categories)
\[ X^{2}=\frac{(25090)^2}{90} + \frac{(50210)^2}{210} + \frac{(200360)^2}{360} + \frac{(1000840)^2} {840} = 507.93 \]

It shows that like_science_fiction and play_chess are correlated in the group
Correlation Analysis (Numeric Data)
 Correlation coefficient (also called Pearson’s product moment coefficient)
\[ {r_{A,B}}=\frac{\sum_{i=1}^{n} (a_{i}\bar{A})
(b_{i}\bar{B})}{(n1)\sigma_{A} \sigma_{B}}=\frac{\sum_{i=1}^{n}
(a_{i}b_{i})n \bar{A}\bar{B}}{(n1)\sigma_{A} \sigma_{B}} \]
where n is the number of tuples, and are the respective means of A and B, σA and σB are the respective standard deviation of A and B, and Σ(aibi) is the sum of the AB crossproduct.  If rA,B > 0, A and B are positively correlated (A’s values increase as B’s). The higher, the stronger correlation.
 rA,B = 0: independent; rAB < 0: negatively correlated
Visually Evaluating Correlation
Correlation (viewed as linear relationship)
 Correlation measures the linear relationship between objects
 To compute correlation, we standardize data objects, A and B, and then take their dot product
\[ a^{'}_{k} = (a_{k}mean(A))/std(A) \]
\[ b^{'}_{k} = (b_{k}mean(B))/std(B) \]
\[ correlation (A,B)=A^{'}.B^{'} \]
Covariance (Numeric Data)
 Covariance is similar to correlation
Correlation coefficient:
where n is the number of tuples, and are the respective mean or expected values of A and B, σA and σB are the respective standard deviation of A and B.
 Positive covariance: If CovA,B > 0, then A and B both tend to be larger than their expected values.
 Negative covariance: If CovA,B < 0 then if A is larger than its expected value, B is likely to be smaller than its expected value.
 Independence: CovA,B = 0 but the converse is not true:
 Some pairs of random variables may have a covariance of 0 but are not independent. Only under some additional assumptions (e.g., the data follow multivariate normal distributions) does a covariance of 0 imply independence
CoVariance: An Example
 It can be simplified in computation as
 Suppose two stocks A and B have the following values in one week: (2, 5), (3, 8), (5, 10), (4, 11), (6, 14).
 Question: If the stocks are affected by the same industry trends, will their prices rise or fall together?
 E(A) = (2 + 3 + 5 + 4 + 6)/ 5 = 20/5 = 4
 E(B) = (5 + 8 + 10 + 11 + 14) /5 = 48/5 = 9.6
 Cov(A,B) = (2×5+3×8+5×10+4×11+6×14)/5 − 4 × 9.6 = 4
 Thus, A and B rise together since Cov(A, B) > 0.
Data Reduction Strategies
 Data reduction: Obtain a reduced representation of the data set that is much smaller in volume but yet produces the same (or almost the same) analytical results
 Why data reduction? — A database/data warehouse may store terabytes of data. Complex data analysis may take a very long time to run on the complete data set.
 Data reduction strategies
 Dimensionality reduction, e.g., remove unimportant attributes
 Wavelet transforms
 Principal Components Analysis (PCA)
 Feature subset selection, feature creation
 Numerosity reduction (some simply call it: Data Reduction)
 Regression and LogLinear Models
 Histograms, clustering, sampling
 Data cube aggregation
 Data compression
Data Reduction 1: Dimensionality Reduction
 Curse of dimensionality
 When dimensionality increases, data becomes increasingly sparse
 Density and distance between points, which is critical to clustering, outlier analysis, becomes less meaningful
 The possible combinations of subspaces will grow exponentially
 Dimensionality reduction
 Avoid the curse of dimensionality
 Help eliminate irrelevant features and reduce noise
 Reduce time and space required in data mining
 Allow easier visualization
 Dimensionality reduction techniques
 Wavelet transforms
 Principal Component Analysis
 Supervised and nonlinear techniques (e.g., feature selection)
Mapping Data to a New Space
 Fourier transform
 Wavelet transform
What Is Wavelet Transform?
 Decomposes a signal into different frequency subbands
 Applicable to ndimensional signals
 Data are transformed to preserve relative distance between objects at different levels of resolution
 Allow natural clusters to become more distinguishable
 Used for image compression
Wavelet Transformation
 Discrete wavelet transform (DWT) for linear signal processing, multiresolution analysis
 Compressed approximation: store only a small fraction of the strongest of the wavelet coefficients
 Similar to discrete Fourier transform (DFT), but better lossy compression, localized in space
 Method:
 Length, L, must be an integer power of 2 (padding with 0’s, when necessary)
 Each transform has 2 functions: smoothing, difference
 Applies to pairs of data, resulting in two set of data of length L/2
 Applies two functions recursively, until reaches the desired length
Wavelet Decomposition
 Wavelets: A math tool for spaceefficient hierarchical decomposition of functions
 S = [2, 2, 0, 2, 3, 5, 4, 4] can be transformed to
\[ S^ = [2\frac{3}{4}, 1\frac{1}{4}, \frac{1}{2}, 0, 0, 1, 1, 0] \]
 Compression: many small detail coefficients can be replaced by 0’s, and only the significant coefficients are retained
Why Wavelet Transform?
 Use hatshape filters
 Emphasize region where points cluster
 Suppress weaker information in their boundaries
 Effective removal of outliers
 Insensitive to noise, insensitive to input order
 Multiresolution
 Detect arbitrary shaped clusters at different scales
 Efficient
 Only applicable to low dimensional data
Principal Component Analysis (PCA)
 Find a projection that captures the largest amount of variation in data
 The original data are projected onto a much smaller space, resulting in dimensionality reduction. We find the eigenvectors of the covariance matrix, and these eigenvectors define the new space
 Given N data vectors from ndimensions, find k ≤ n orthogonal vectors (principal components) that can be best used to represent data
 Normalize input data: Each attribute falls within the same range
 Compute k orthonormal (unit) vectors, i.e., principal components
 Each input data (vector) is a linear combination of the k principal component vectors
 The principal components are sorted in order of decreasing “significance” or strength
 Since the components are sorted, the size of the data can be reduced by eliminating the weak components, i.e., those with low variance (i.e., using the strongest principal components, it is possible to reconstruct a good approximation of the original data)
 Works for numeric data only
Principal Component Analysis (Steps)
Attribute Subset Selection
 Another way to reduce dimensionality of data
 Redundant attributes
 Duplicate much or all of the information contained in one or more other attributes
 E.g., purchase price of a product and the amount of sales tax paid
 Irrelevant attributes
 Contain no information that is useful for the data mining task at hand
 E.g., students' ID is often irrelevant to the task of predicting students' GPA
Heuristic Search in Attribute Selection
 There are 2d possible attribute combinations of d attributes
 Typical heuristic attribute selection methods:
 Best single attribute under the attribute independence assumption: choose by significance tests
 Best stepwise feature selection:
 The best singleattribute is picked first
 Then next best attribute condition to the first, ...
 Stepwise attribute elimination:
 Repeatedly eliminate the worst attribute
 Best combined attribute selection and elimination
 Optimal branch and bound:
 Use attribute elimination and backtracking
Attribute Creation (Feature Generation)
 Create new attributes (features) that can capture the important information in a data set more effectively than the original ones
 Three general methodologies
 Attribute extraction
 Mapping data to new space (see: data reduction)
 E.g., Fourier transformation, wavelet transformation, manifold approaches (not covered)
 Attribute construction
 Combining features (see: discriminative frequent patterns in Chapter 7)
 Data discretization
Data Reduction 2: Numerosity Reduction
 Reduce data volume by choosing alternative, smaller forms of data representation
 Parametric methods (e.g., regression)
 Assume the data fits some model, estimate model parameters, store only the parameters, and discard the data (except possible outliers)
 Ex.: Loglinear models—obtain value at a point in mD space as the product on appropriate marginal subspaces
 Nonparametric methods
 Do not assume models
 Major families: histograms, clustering, sampling, …
Parametric Data Reduction: Regression and LogLinear Models
 Linear regression
 Data modeled to fit a straight line
 Often uses the leastsquare method to fit the line
 Multiple regression
 Allows a response variable Y to be modeled as a linear function of multidimensional feature vector
 Loglinear model
 Approximates discrete multidimensional probability distributions
Regression Analysis
 Regression analysis: A collective name for techniques for the modeling and analysis of numerical data consisting of values of a dependent variable (also called response variable or measurement) and of one or more independent variables (aka. explanatory variables or predictors)
 The parameters are estimated so as to give a "best fit" of the data
 Most commonly the best fit is evaluated by using the least squares method, but other criteria have also been used
 Used for prediction (including forecasting of timeseries data), inference, hypothesis testing, and modeling of causal relationships
 Linear regression: Y = w X + b
 Two regression coefficients, w and b, specify the line and are to be estimated by using the data at hand
 Using the least squares criterion to the known values of Y1, Y2, …, X1, X2, ….
 Multiple regression: Y = b + b1 X1 + b2 X2
 Many nonlinear functions can be transformed into the above
 Loglinear models:
 Approximate discrete multidimensional probability distributions
 Estimate the probability of each point (tuple) in a multidimensional space for a set of discretized attributes, based on a smaller subset of dimensional combinations
 Useful for dimensionality reduction and data smoothing
Regress Analysis and LogLinear Models
Histogram Analysis
 Divide data into buckets and store average (sum) for each bucket
 Partitioning rules:
 Equalwidth: equal bucket range
 Equalfrequency (or equaldepth)
Clustering
 Partition data set into clusters based on similarity, and store cluster representation (e.g., centroid and diameter) only
 Can be very effective if data is clustered but not if data is “smeared”
 Can have hierarchical clustering and be stored in multidimensional index tree structures
 There are many choices of clustering definitions and clustering algorithms
 Cluster analysis will be studied in depth in Chapter 10
Sampling
 Sampling: obtaining a small sample s to represent the whole data set N
 Allow a mining algorithm to run in complexity that is potentially sublinear to the size of the data
 Key principle: Choose a representative subset of the data
 Simple random sampling may have very poor performance in the presence of skew
 Develop adaptive sampling methods, e.g., stratified sampling:
 Note: Sampling may not reduce database I/Os (page at a time)
Types of Sampling
 Simple random sampling
 There is an equal probability of selecting any particular item
 Sampling without replacement
 Once an object is selected, it is removed from the population
 Sampling with replacement
 A selected object is not removed from the population
 Stratified sampling:
 Partition the data set, and draw samples from each partition (proportionally, i.e., approximately the same percentage of the data)
 Used in conjunction with skewed data
Sampling: With or without Replacement
Sampling: Cluster or Stratified Sampling
Data Cube Aggregation
 The lowest level of a data cube (base cuboid)
 The aggregated data for an individual entity of interest
 E.g., a customer in a phone calling data warehouse
 Multiple levels of aggregation in data cubes
 Further reduce the size of data to deal with
 Reference appropriate levels
 Use the smallest representation which is enough to solve the task
 Queries regarding aggregated information should be answered using data cube, when possible
Data Reduction 3: Data Compression
 String compression
 There are extensive theories and welltuned algorithms
 Typically lossless, but only limited manipulation is possible without expansion
 Audio/video compression
 Typically lossy compression, with progressive refinement
 Sometimes small fragments of signal can be reconstructed without reconstructing the whole
 Time sequence is not audio
 Typically short and vary slowly with time
 Dimensionality and numerosity reduction may also be considered as forms of data compression
Data Compression
Data Transformation
 A function that maps the entire set of values of a given attribute to a new set of replacement values s.t. each old value can be identified with one of the new values
 Methods
 Smoothing: Remove noise from data
 Attribute/feature construction
 New attributes constructed from the given ones
 Aggregation: Summarization, data cube construction
 Normalization: Scaled to fall within a smaller, specified range
 minmax normalization
 zscore normalization
 normalization by decimal scaling
 Discretization: Concept hierarchy climbing
Normalization
 Minmax normalization: to [new_minA, new_maxA]
\[ v^{'}=\frac{vmin_{A}}{max_{A}min_{A}}(newmax_{A}  newmin_{A})+ newmin_{A} \]
 Ex. Let income range $12,000 to $98,000 normalized to [0.0, 1.0]. Then $73,000 is mapped to
\[ \frac{73,60012,000}{98,00012,000}(1.0  0)+ 0 = 0.716 \]
 Zscore normalization (μ: mean, σ: standard deviation):
\[ v^{'} = \frac{v\mu_{A}}{\sigma _{A}} \]
 Ex. Let μ = 54,000, σ = 16,000. Then
\[ \frac{73,60054,000}{16,000} = 1.225 \]
 Normalization by decimal scaling
\[ v^{'} = \frac{v}{10^{j}} \]
Where j is the smallest integer such that Max(ν’) < 1
Discretization
 Three types of attributes
 Nominal—values from an unordered set, e.g., color, profession
 Ordinal—values from an ordered set, e.g., military or academic rank
 Numeric—real numbers, e.g., integer or real numbers
 Discretization: Divide the range of a continuous attribute into intervals
 Interval labels can then be used to replace actual data values
 Reduce data size by discretization
 Supervised vs. unsupervised
 Split (topdown) vs. merge (bottomup)
 Discretization can be performed recursively on an attribute
 Prepare for further analysis, e.g., classification
Data Discretization Methods
 Typical methods: All the methods can be applied recursively
 Binning
 Topdown split, unsupervised
 Histogram analysis
 Topdown split, unsupervised
 Clustering analysis (unsupervised, topdown split or bottomup merge)
 Decisiontree analysis (supervised, topdown split)
 Correlation (e.g., X^2) analysis (unsupervised, bottomup merge)
Simple Discretization: Binning
 Equalwidth (distance) partitioning
 Divides 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 intervals will be: W = (B –A)/N.
 The most straightforward, but outliers may dominate presentation
 Skewed data is not handled well
 Equaldepth (frequency) partitioning
 Divides the range into N intervals, each containing approximately same number of samples
 Good data scaling
 Managing categorical attributes can be tricky
Binning Methods for Data Smoothing
 Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
 * Partition into equalfrequency (equidepth) bins:
  Bin 1: 4, 8, 9, 15
  Bin 2: 21, 21, 24, 25
  Bin 3: 26, 28, 29, 34
 * Smoothing by bin means:
  Bin 1: 9, 9, 9, 9
  Bin 2: 23, 23, 23, 23
  Bin 3: 29, 29, 29, 29
 * Smoothing by bin boundaries:
  Bin 1: 4, 4, 4, 15
  Bin 2: 21, 21, 25, 25
  Bin 3: 26, 26, 26, 34
Discretization Without Using Class Labels(Binning vs. Clustering)
Discretization by Classification & Correlation Analysis
 Classification (e.g., decision tree analysis)
 Supervised: Given class labels, e.g., cancerous vs. benign
 Using entropy to determine split point (discretization point)
 Topdown, recursive split
 Details to be covered in Chapter 7
 Correlation analysis (e.g., Chimerge: χ2based discretization)
 Supervised: use class information
 Bottomup merge: find the best neighboring intervals (those having similar distributions of classes, i.e., low χ2 values) to merge
 Merge performed recursively, until a predefined stopping condition
Concept Hierarchy Generation
 Concept hierarchy organizes concepts (i.e., attribute values) hierarchically and is usually associated with each dimension in a data warehouse
 Concept hierarchies facilitate drilling and rolling in data warehouses to view data in multiple granularity
 Concept hierarchy formation: Recursively reduce the data by collecting and replacing low level concepts (such as numeric values for age) by higher level concepts (such as youth, adult, or senior)
 Concept hierarchies can be explicitly specified by domain experts and/or data warehouse designers
 Concept hierarchy can be automatically formed for both numeric and nominal data. For numeric data, use discretization methods shown.
Concept Hierarchy Generation for Nominal Data
 Specification of a partial/total ordering of attributes explicitly at the schema level by users or experts
 street < city < state < country
 Specification of a hierarchy for a set of values by explicit data grouping
 {Urbana, Champaign, Chicago} < Illinois
 Specification of only a partial set of attributes
 E.g., only street < city, not others
 Automatic generation of hierarchies (or attribute levels) by the analysis of the number of distinct values
 E.g., for a set of attributes: {street, city, state, country}
Automatic Concept Hierarchy Generation
 Some hierarchies can be automatically generated based on the analysis of the number of distinct values per attribute in the data set
 The attribute with the most distinct values is placed at the lowest level of the hierarchy
 Exceptions, e.g., weekday, month, quarter, year
Summary
 Data quality: accuracy, completeness, consistency, timeliness, believability, interpretability
 Data cleaning: e.g. missing/noisy values, outliers
 Data integration from multiple sources:
 Entity identification problem
 Remove redundancies
 Detect inconsistencies
 Data reduction
 Dimensionality reduction
 Numerosity reduction
 Data compression
 Data transformation and data discretization
 Normalization
 Concept hierarchy generation
References
 D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehouse environments. Comm. of ACM, 42:7378, 1999
 T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley, 2003
 T. Dasu, T. Johnson, S. Muthukrishnan, V. Shkapenyuk. Mining Database Structure; Or, How to Build a Data Quality Browser. SIGMOD’02
 H. V. Jagadish et al., Special Issue on Data Reduction Techniques. Bulletin of the Technical Committee on Data Engineering, 20(4), Dec. 1997
 D. Pyle. Data Preparation for Data Mining. Morgan Kaufmann, 1999
 E. Rahm and H. H. Do. Data Cleaning: Problems and Current Approaches. IEEE Bulletin of the Technical Committee on Data Engineering. Vol.23, No.4
 V. Raman and J. Hellerstein. Potters Wheel: An Interactive Framework for Data Cleaning and Transformation, VLDB’2001
 T. Redman. Data Quality: Management and Technology. Bantam Books, 1992
 R. Wang, V. Storey, and C. Firth. A framework for analysis of data quality research. IEEE Trans. Knowledge and Data Engineering, 7:623640, 1995
Agenda
 Data Warehouse: Basic Concepts
 Data Warehouse Modeling: Data Cube and OLAP
 Data Warehouse Design and Usage
 Data Warehouse Implementation
 Data Generalization by AttributeOriented Induction
 Summary
What is a Data Warehouse?
 Defined in many different ways, but not rigorously.
 A decision support database that is maintained separately from the organization’s operational database
 Support information processing by providing a solid platform of consolidated, historical data for analysis.
 “A data warehouse is a subjectoriented, integrated, timevariant, and nonvolatile collection of data in support of management’s decisionmaking process.”—W. H. Inmon
 Data warehousing:
 The process of constructing and using data warehouses
Data Warehouse—SubjectOriented
 Organized around major subjects, such as customer, product, sales
 Focusing on the modeling and analysis of data for decision makers, not on daily operations or transaction processing
 Provide a simple and concise view around particular subject issues by excluding data that are not useful in the decision support process
Data Warehouse—Integrated
 Constructed by integrating multiple, heterogeneous data sources
 relational databases, flat files, online transaction records
 Data cleaning and data integration techniques are applied.
 Ensure consistency in naming conventions, encoding structures, attribute measures, etc. among different data sources
 E.g., Hotel price: currency, tax, breakfast covered, etc.
 When data is moved to the warehouse, it is converted.
Data Warehouse—Time Variant
 The time horizon for the data warehouse is significantly longer than that of operational systems
 Operational database: current value data
 Data warehouse data: provide information from a historical perspective (e.g., past 510 years)
 Every key structure in the data warehouse
 Contains an element of time, explicitly or implicitly
 But the key of operational data may or may not contain “time element”
Data Warehouse—Nonvolatile
 A physically separate store of data transformed from the operational environment
 Operational update of data does not occur in the data warehouse environment
 Does not require transaction processing, recovery, and concurrency control mechanisms
 Requires only two operations in data accessing:
 initial loading of data and access of data
OLTP vs. OLAP
 OLTP  OLAP 
users  clerk, IT professional
 knowledge worker

function DB design
 day to day operations applicationoriented
 decision support subjectoriented

data  surrent, uptodate detailed, flat relational isolated
 historical, summarized, multidimensional integrated, sonsolidated

usage access
 repetetive read/write index/hash on prim key  adhoc lots of scans

unit of work #records accessed
 short, simple transaction tens  complex query millions

#users DB size metric
 thousands 100MBGB transaction throughput
 hundreds 100GBTB query throughput, response

Why a Separate Data Warehouse?
 High performance for both systems
 DBMS— tuned for OLTP: access methods, indexing, concurrency control, recovery
 Warehouse—tuned for OLAP: complex OLAP queries, multidimensional view, consolidation
 Different functions and different data:
 missing data: Decision support requires historical data which operational DBs do not typically maintain
 data consolidation: DS requires consolidation (aggregation, summarization) of data from heterogeneous sources
 data quality: different sources typically use inconsistent data representations, codes and formats which have to be reconciled
 Note: There are more and more systems which perform OLAP analysis directly on relational databases
Data Warehouse: A MultiTiered ArchitectureUntitled
Three Data Warehouse Models
 Enterprise warehouse
 collects all of the information about subjects spanning the entire organization
 Data Mart
 a subset of corporatewide data that is of value to a specific groups of users. Its scope is confined to specific, selected groups, such as marketing data mart
 Independent vs. dependent (directly from warehouse) data mart
 Virtual warehouse
 A set of views over operational databases
 Only some of the possible summary views may be materialized
Extraction, Transformation, and Loading (ETL)
 Data extraction
 get data from multiple, heterogeneous, and external sources
 Data cleaning
 detect errors in the data and rectify them when possible
 Data transformation
 convert data from legacy or host format to warehouse format
 Load
 sort, summarize, consolidate, compute views, check integrity, and build indicies and partitions
 Refresh
 propagate the updates from the data sources to the warehouse
Metadata Repository
 Meta data is the data defining warehouse objects. It stores:
 Description of the structure of the data warehouse
 schema, view, dimensions, hierarchies, derived data defn, data mart locations and contents
 Operational metadata
 data lineage (history of migrated data and transformation path), currency of data (active, archived, or purged), monitoring information (warehouse usage statistics, error reports, audit trails)
 The algorithms used for summarization
 The mapping from operational environment to the data warehouse
 Data related to system performance
 warehouse schema, view and derived data definitions
 Business data
 business terms and definitions, ownership of data, charging policies
From Tables and Spreadsheets to Data Cubes
 A data warehouse is based on a multidimensional data model which views data in the form of a data cube
 A data cube, such as sales, allows data to be modeled and viewed in multiple dimensions
 Dimension tables, such as item (item_name, brand, type), or time(day, week, month, quarter, year)
 Fact table contains measures (such as dollars_sold) and keys to each of the related dimension tables
 In data warehousing literature, an nD base cube is called a base cuboid. The top most 0D cuboid, which holds the highestlevel of summarization, is called the apex cuboid. The lattice of cuboids forms a data cube.
Cube: A Lattice of Cuboids
Conceptual Modeling of Data Warehouses
 Modeling data warehouses: dimensions & measures
 Star schema: A fact table in the middle connected to a set of dimension tables
 Snowflake schema: A refinement of star schema where some dimensional hierarchy is normalized into a set of smaller dimension tables, forming a shape similar to snowflake
 Fact constellations: Multiple fact tables share dimension tables, viewed as a collection of stars, therefore called galaxy schema or fact constellation
Example of Star Schema
Example of Snowflake Schema
Example of Fact Constellation