Module 2: Introduction to Data Mining, Data
Exploration and Data Pre-processing
TE – D – DWM
Prof. Smruti Vyavahare
Assistant Professor
Dept. of Computer Engineering,
SIES Graduate School of Technology
1
Prof. Smruti Vyavahare
Contents
• Data Mining Task Primitives
• Architecture
• KDD process
• Issues in Data Mining
• Applications of Data Mining
• Data Exploration: Types of Attributes
• Statistical Description of Data
• Data Visualization
• Data Preprocessing: Descriptive data summarization, Cleaning, Integration &
transformation, Data reduction, Data Discretization and Concept hierarchy generation.
2
Prof. Smruti Vyavahare
Meaning of Data Mining
• Motivation & Concept of Data Mining
1. In 1 second on the Internet: 83,378 Google searches, 84,388 YouTube views,
9,003 tweets, and more.
2. But all this information really important to us?
3. "Necessity is the Mother of all Inventions“
4. Data is doubling every 10 months.
5. Huge growth in digital data, there is need to extract useful knowledge.
6. Since the 1960s, data storage has evolved from basic file systems to advanced
relational database management systems (RDBMS).
3
Prof. Smruti Vyavahare
• Extracting knowledge from large amounts of data called as “ Data Mining”.
• Also called:
“Knowledge mining from data”
“Knowledge Discovery in Databases (KDD)”
4
Prof. Smruti Vyavahare
5
Prof. Smruti Vyavahare
6
Prof. Smruti Vyavahare
Architecture of Data Mining
7
Prof. Smruti Vyavahare
1. Data Sources: Database, World Wide Web(WWW), and data warehouse are parts of data sources.
The data in these sources may be in the form of plain text, spreadsheets, or other forms of media like
photos or videos. WWW is one of the biggest sources of data.
2. Database Server: The database server contains the actual data ready to be processed. It performs
the task of handling data retrieval as per the request of the user.
3. Data Mining Engine: It is one of the core components of the data mining architecture that performs
all kinds of data mining techniques like association, classification, characterization, clustering,
prediction, etc.
4. Pattern Evaluation Modules: They are responsible for finding interesting patterns in the data and
sometimes they also interact with the database servers for producing the result of the user requests.
5. Graphic User Interface: Since the user cannot fully understand the complexity of the data mining
process so graphical user interface helps the user to communicate effectively with the data mining
system.
6. Knowledge Base: Knowledge Base is an important part of the data mining engine that is quite
beneficial in guiding the search for the result patterns. Data mining engines may also sometimes get
inputs from the knowledge base. This knowledge base may contain data from user experiences. The
objective of the knowledge base is to make the result more accurate and reliable.
8
Prof. Smruti Vyavahare
KDD Process
9
Prof. Smruti Vyavahare
Data Mining Task Primitives
•A data mining task can be specified in the form of a data mining query, which is input to
the data mining system.
•A data mining query is defined in terms of data mining task primitives.
•These primitives allow the user to inter- actively communicate with the data mining
system during discovery in order to direct the mining process, or examine the findings
from different angles or depths.
•The data mining primitives specify the following:
1. The set of task-relevant data to be mined
2. The kind of knowledge to be mined
3. The background knowledge to be used in the discovery process
4. The interestingness measures and thresholds for pattern evaluation
5. The expected representation for visualizing the discovered patterns
10
Prof. Smruti Vyavahare
• The set of task-relevant data to be mined
1. This specifies the portions of the database or the set of data in which the user is
interested (Target Data)
2. This includes the database attributes or data warehouse dimensions of interest
• The kind of knowledge to be mined
This specifies the data mining functions to be performed, such as
1. Characterization: Summarization of the general characteristics or features of a target
class of data.
2. Association: It discovers the probability of the co-occurrence of items in a collection.
3. Correlation analysis: It is used to find the association between the variables.
4. Classification: It discovers a model that defines the data classes or concepts.
5. Prediction: It represents the data classes to predict future data/trends.
6. Cluster analysis: To find out the group of objects which are similar to each other
the group but are different from the object in other groups.
7. Outlier analysis: It is a process that involves identifying the anomalous observation in
the dataset.
• The background knowledge to be used in the discovery process:
1. This knowledge about the domain to be mined is useful for guiding the knowledge
discovery process and for evaluating the patterns found.
2. Concept hierarchies (it defines a sequence of mappings from a set of low-level
concepts to higher-level, more general concepts) are a popular form of background
knowledge, which allow data to be mined at multiple levels of abstraction.
11
Prof. Smruti Vyavahare
Types of Data Sets
1. Record
• Relational records
• Data matrix, e.g., numerical matrix, crosstabs
• Document data: text documents: term-frequency vector
• Transaction data
2. Graph and network
• World Wide Web
• Social or information networks
• Molecular Structures
3. Ordered
• Video data: sequence of images
• Temporal data: time-series
• Sequential Data: transaction sequences
• Genetic sequence data
4. Spatial, image and multimedia:
• Spatial data: maps
• Image data
• Video data
12
Prof. Smruti Vyavahare
Important Characteristics of Structured Data
1. Dimensionality
- Curse of dimensionality: Imagine finding a friend in a 2D map vs. a complex 1000D space
—it’s exponentially harder!
2. Sparsity
- Only presence counts: In a user-item recommendation system, most users won’t interact
with most items—those zero entries dominate the dataset.
3. Resolution
- Patterns depend on the scale: Daily sales vs. yearly sales can highlight short-term
promotions vs. long-term growth.
4. Distribution
- Centrality and dispersion: Two datasets can have the same average income but wildly
different levels of inequality.
13
Prof. Smruti Vyavahare
14
Prof. Smruti Vyavahare
Attribute
15
Prof. Smruti Vyavahare
Types of Attributes
• Nominal Attributes: These represent categories or labels without any inherent order—
essentially, names or classifications.
• Example: Hair color could be {auburn, black, blond, brown, grey, red, white}.
• Other examples include marital status, job titles, identification numbers, and postal
codes.
• Binary Attributes: A special case of nominal attributes limited to two possible values,
often represented as 0 and 1.
• Symmetric Binary: Both possible values carry equal significance.
• Example: Gender.
• Asymmetric Binary: One outcome is more critical than the other.
• Example: Medical test results, where a positive result is more important than a
negative one.
• Conventionally, the value 1 is assigned to the more significant outcome (e.g.,
Dengue positive).
• Ordinal Attributes: These have values that follow a meaningful sequence or ranking,
though the intervals between values may not be uniform.
16
Prof. Smruti Vyavahare
17
Prof. Smruti Vyavahare
Discrete vs. Continuous Attributes
•Discrete Attributes
•Consist of a limited or countably infinite set of possible values.
•Examples include zip codes, job titles, or the vocabulary found within a document
collection.
•Often represented using integer data types.
•Note: Binary attributes are a subset of discrete attributes.
•Continuous Attributes
•Characterized by values that are real numbers.
•Examples include measurements like temperature, height, or weight.
•In practice, these real values are recorded with a finite precision due to measurement
and storage limitations.
•Typically stored as floating-point numbers in computing systems.
18
Prof. Smruti Vyavahare
19
Prof. Smruti Vyavahare
20
Prof. Smruti Vyavahare
21
Prof. Smruti Vyavahare
22
Prof. Smruti Vyavahare
23
Prof. Smruti Vyavahare
24
Prof. Smruti Vyavahare
25
Prof. Smruti Vyavahare
26
Prof. Smruti Vyavahare
27
Prof. Smruti Vyavahare
28
Prof. Smruti Vyavahare
29
Prof. Smruti Vyavahare
30
Prof. Smruti Vyavahare
31
Prof. Smruti Vyavahare
32
Prof. Smruti Vyavahare
33
Prof. Smruti Vyavahare
34
Prof. Smruti Vyavahare
35
Prof. Smruti Vyavahare
36
Prof. Smruti Vyavahare
37
Prof. Smruti Vyavahare
38
Prof. Smruti Vyavahare
39
Prof. Smruti Vyavahare
40
Prof. Smruti Vyavahare
41
Prof. Smruti Vyavahare
42
Prof. Smruti Vyavahare
43
Prof. Smruti Vyavahare
In financial data analysis, this technique might be used to spot:
• Customers with high income but low credit limit,
• Clusters of similar transaction volumes,
• Outlier age groups with abnormal behavior
44
Prof. Smruti Vyavahare
45
Prof. Smruti Vyavahare
46
Prof. Smruti Vyavahare
47
Prof. Smruti Vyavahare
48
Prof. Smruti Vyavahare
49
Prof. Smruti Vyavahare
50
Prof. Smruti Vyavahare
51
Prof. Smruti Vyavahare
52
Prof. Smruti Vyavahare
53
Prof. Smruti Vyavahare
54
Prof. Smruti Vyavahare
55
Prof. Smruti Vyavahare
56
Prof. Smruti Vyavahare
57
Prof. Smruti Vyavahare
58
Prof. Smruti Vyavahare
59
Prof. Smruti Vyavahare
60
Prof. Smruti Vyavahare
61
Prof. Smruti Vyavahare
62
Prof. Smruti Vyavahare
63
Prof. Smruti Vyavahare
64
Prof. Smruti Vyavahare
65
Prof. Smruti Vyavahare
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.
If the correlation co-efficient between the attributes A & B are positive then they are
positively correlated.
- That is if A’s value increases, B’s value also increases.
- As the correlation co-efficient value increases, the stronger the correlation.
- If the correlation co-efficient between the attributes A & B is zero then they are
independent attributes. 66
- If the correlation co-efficient value is negative then
Prof. Smruti they are negatively correlated.
Vyavahare
67
Prof. Smruti Vyavahare
68
Prof. Smruti Vyavahare
Correlation Analysis (Nominal Data)
• Χ2 (chi-square) test
• 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 car-theft in a city are correlated
• Both are causally linked to the third variable: population
69
Prof. Smruti Vyavahare
Like Science Fiction Like Science Fiction
Row Total
(Yes) (No)
Play Chess (Yes) O = 250 E = 90 O = 50 E = 210 300
Play Chess (No) O = 200 E = 360 O = 1000 E = 840 1200
Column Total 450 1250 1500
70
Prof. Smruti Vyavahare
Covariance of Numeric Data
Covariance of numeric data is a statistical measure that indicates the direction of the linear relationship
between two numerical variables.
71
Prof. Smruti Vyavahare
72
Prof. Smruti Vyavahare
Data Transformation
• Smoothing:- Removes noise from the data
• Aggregation:- Summarization, Data cube Construction
• Generalization:- Concept Hierarchy climbing
• Attribute / Feature Construction:- New attributes constructed from the given ones
• Normalization:- Data scaled to fall within a specified range
- min-max normalization - z-score normalization
- normalization by decimal scaling
73
Prof. Smruti Vyavahare
Data Reduction
Why Data Reduction?
- A database of data warehouse may store terabytes of data
- Complex data analysis or mining will take long time to run on the complete data set
What is Data Reduction?
- Obtaining a reduced representation of the complete dataset
Produces same result or almost same mining / analytical results as that of original
Data Reduction Strategies
1. Data cube Aggregation
2. Attribute (Subset) Selection
3. Dimensionality reduction – remove unwanted attributes
4. Data Compression
5. Numerosity reduction – Fit data into mathematical models
6. Discretization and Concept Hierarchy Generation
74
Prof. Smruti Vyavahare
1. Data cube Aggregation
• The lowest level of data cube is called as base cuboid.
- Single Level Aggregation - Select a particular entity or attribute and Aggregate based on that particular
attribute.
Eg. Aggregate along ‘Year’ in a Sales data.
-Multiple Level of Aggregation – Aggregates along multiple attributes –Further reduces the size of the data
to analyze.
- When a query is posed by the user, use the appropriate level of Aggregation or data cube to solve the task
- Queries regarding aggregated information should be answered using the data cube whenever possible.
75
Prof. Smruti Vyavahare
2. Attribute (Subset) Selection
Feature Selection: (attribute subset selection)
• The goal of attribute subset selection is to find the minimum set of attributes such that the resulting
probability distribution of data classes is as close as possible to the original distribution obtained using
all attributes.
Heuristic Methods
Due to exponential number of attribute choices
- Step wise forward selection
- Step wise backward elimination
- Combining forward selection and backward elimination
- Decision Tree induction
76
Prof. Smruti Vyavahare
4. Data Compression
- Compressed representation of the original data.
• Lossless Compression
• Lossy Compression
5. Numerosity reduction – Fit data into mathematical models
- Reduces the data volume by choosing smaller forms of data representations.
- Two types – Parametric, Non-Parametric.
- Parametric – Data estimated into a model
– only the data parameters stored and not the actual data.
- Non-Parametric – Do not fits data into models
- Eg. Histograms, Clustering and Sampling
Regression and Log-Linear Models
• Linear Regression - data are modeled to fit in a straight line.
y=ax+b
- That is data can be modeled to the mathematical equation:
- Where y is called the “Response Variable” and x is called “Predictor Variable”.
- a and b are called the regression coefficients.
- b is the Y-intercept and a is the Slope of the equation.
- These regression coefficients can be solved by using “method of least squares”.
- Multiple Regression – Extension of linear regression
– Response variable Y is modeled as a multidimensional vector.
77
Prof. Smruti Vyavahare
Histograms
-Uses binning to distribute the data.
- Histogram for an attribute A;
- Partitions the data of A into disjoint subsets / buckets.
- Buckets are represented in a horizontal line in a histogram.
- Vertical line of histogram represents frequency of values in bucket.
- Singleton Bucket – Has only one attribute value / frequency pair
78
Prof. Smruti Vyavahare
Sampling
- Selects random sample or subset of data.
- Say large dataset D contains N tuples.
1. Simple Random Sample With Out Replacement (SRSWOR) of size n:
- Draw n tuples from the original N tuples in D, where n<N.
- The probability of drawing any tuple in D is 1/N. That is all tuples have equal chance
2. Simple Random Sample With Replacement (SRSWR) of size n:
- Similar to SRSWOR, except that each time when a tuple is drawn from Dit is recorded and replaced.
- After a tuple is drawn it is placed back in D so that it can be drawn again
79
Prof. Smruti Vyavahare
Data Discretization
• Technique that is used to convert a continuous attribute into discrete attributes.
• Some classification algorithms only accept discrete values.
-Supervised- Entropy based discretization is a supervised way of discretization.
Automated Discretization Methods:
o Binning
o Histogram analysis
o Entropy based Discretization Method
o X2 – Merging (Chi-Merging)
o Cluster Analysis
o Discretization by Intuition Partitioning
80
Prof. Smruti Vyavahare
Entropy based Discretization Method
• Top-Down Discretization
• The goal of this algorithm is to find the split with the maximum information gain.
• The boundary that minimizes the entropy over all possible boundaries is selected
• The process is recursively applied to partitionsobtained until some stopping criterion is met
• Such a boundary may reduce data size and improve classification accuracy
81
Prof. Smruti Vyavahare
82
Prof. Smruti Vyavahare
83
Prof. Smruti Vyavahare
84
Prof. Smruti Vyavahare
85
Prof. Smruti Vyavahare
Discretization by Intuition Partitioning
- Users like numerical value intervals to be uniform, easy-to-use, ‘Intuitive’, Natural.
- Clustering analysis produces intervals such as ($53,245.78,$62,311.78].
- But intervals such as ($50,000,$60,000] is better than the above.
- Follows 3-4-5 Rule:
o Partitions the given data range into 3 or 4 or 5 equi-width intervals
o Partitions recursively, level-by-level, based on value range at most significant digit
Segmentation by natural partitioning
• 3-4-5 rule can be used to segment numeric data into relatively uniform, “natural” intervals.
• If an interval covers 3, 6, 7 or 9 distinct values at the most significant digit, partition the range into 3
equi- width intervals
• If it covers 2, 4, or 8 distinct values at the most significant digit, partition the range into 4 intervals
• If it covers 1, 5, or 10 distinct values at the most significant digit, partition the range into 5 intervals
86
Prof. Smruti Vyavahare
87
Prof. Smruti Vyavahare
Hence intervals are: (-$1,000,$0], ($0,$1,000],($1,000,$2,000]
o LOW’ < MIN => Adjust the left boundary to make the interval smaller.
o Most significant digit of MIN is $1000 => MIN’ = -$400
o Hence first interval reduced to (-$400,$0]
o HIGH’ < MAX => Add new interval ($2,000,$5,000]
o Hence the Top tier Hierarchy intervals are:( $400,$0],($0,$1,000],($1,000,$2,000], ($2,000,$5,000]
o These are further subdivided as per 3-4-5 rule to obtain the lower levelhierarchies.
o Interval (-$400,$0] is divided into 4 equi-width intervals
o Intervals ($0,$1,000] & is divided into 5 Equi-width intervals
o Interval ($1,000,$2,000] is divided into 5 Equi-width intervals
o Interval ($2,000,000, $5,000] is divided into 3 Equi-width intervals
88
Prof. Smruti Vyavahare
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.
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
country 15 distinct values
province_or_ state 365 distinct values
city 3567 distinct values
street 674,339 distinct values
89
Prof. Smruti Vyavahare
90
Prof. Smruti Vyavahare
91
Prof. Smruti Vyavahare
92
Prof. Smruti Vyavahare
93
Prof. Smruti Vyavahare
94
Prof. Smruti Vyavahare
Thank You!
(smrutiv@[Link])
95
Prof. Smruti Vyavahare