Introduction to Data Mining

Introduction – Need for Data Mining – What Kinds of Data: Kinds of

Patterns, Technologies, Applications and Issues
Data Mining
Data Mining or Knowledge Discovery in Databases (KDD) : The
nontrivial extraction of implicit, previously unknown and potentially
useful information from data in databases.
Data mining is about tools, methodologies and theories for revealing
patterns in data — which is a critical step in knowledge discovery.
• Data mining refers to extracting or “mining” of knowledge from large
amounts of data.
• The term is actually a misnomer.
• Remember that the mining of gold from rocks or sand is referred to as
gold mining rather than rock or sand mining.
• Thus, data mining should have been more appropriately named
“knowledge/Information mining from data”.
 # Need for Data Mining
The fast-growing, tremendous amount of
data, collected and stored in large and
numerous data repositories, - without
powerful tools.

Data collected in large data repositories

become “data tombs”—data archives.

The decision maker does not have the

tools to extract the valuable knowledge
embedded in the vast amounts of data
Decision Support
Data Mining helps companies/organizations in Decision Support.
• Typical procedure
– Data -> Knowledge -> Action/Decision -> Goal
• Examples
– Netflix collects user ratings of movies (data) => What types of movies you will
like (knowledge) => Recommend new movies to you (action) => Users stay with
Netflix (goal)
– Road traffic (data) => Which road is likely to be congested? (knowledge) =>
Suggest better routes to drivers (action) => Save time and energy (goal)

4
Knowledge discovery process or Data Mining Process

1. Data cleaning - to remove noise and inconsistent data.

2. Data integration - where multiple data sources may be combined.
3. Data selection - where data relevant to the analysis task are retrieved from the database.
4. Data transformation - where data are transformed or consolidated into forms appropriate for mining by
performing summary or aggregation operations.
5. Data mining - An essential process where intelligent methods are applied in order to extract data
patterns.
6. Pattern evaluation - To identify the truly interesting patterns representing knowledge based on some
interestingness measure.
7. Knowledge presentation - where visualization and knowledge representation techniques are used to
present the mined knowledge to the user.
Architecture components of a typical data mining system
The major components of data mining system
a) Data source
✓ Database, data warehouse, World Wide Web (WWW), text files and other
documents are the actual sources of data.
✓ We need large volumes of historical data for data mining to be successful.
✓ Organizations usually store data in databases or data warehouses.
✓ Data warehouses may contain one or more databases, text files,
spreadsheets or other kinds of information repositories.
✓ Sometimes, data may reside even in plain text files or spreadsheets.
✓ World Wide Web or the Internet is another big source of data.
Different Processes
• The data needs to be cleaned, integrated and selected before passing
it to the database or data warehouse server.
• As the data is from different sources and in different formats, it
cannot be used directly for the data mining process because the data
might not be complete and reliable.
• Only the data of interest needs to be selected and passed to the
server.
b) Database or Data Warehouse Server
✓contains the actual data that is ready to be processed.
✓Hence, the server is responsible for retrieving the relevant data
based on the data mining request of the user.

c) Data Mining Engine

✓The core component of any data mining system.
✓Consists of a number of modules for performing data mining tasks -
characterization, association and correlation analysis, classification,
prediction, cluster analysis, outlier analysis, and evolution analysis.
d) Pattern Evaluation Modules
✓Mainly responsible for the measure of interestingness of the pattern by using
a threshold value.
✓ It interacts with the data mining engine to focus the search towards
interesting patterns.
✓Thresholds to filter out discovered patterns.
✓Alternatively, the pattern evaluation module may be integrated with the
mining module, depending on the implementation of the data mining
method used.

e) Graphical User Interface

✓Communicates between the user and the data mining system.
✓ When the user specifies a query or a task, this module interacts with the
data mining system and displays the result in an easily understandable
manner.
f) Knowledge Base:
• The knowledge base is helpful in the entire process of data mining. It might be
helpful to guide the search or evaluate the stake of the result patterns.
• The knowledge base may even contain user views and data from user
experiences that might be helpful in the data mining process.
• The data mining engine may receive inputs from the knowledge base to make
the result more accurate and reliable.
• The pattern assessment module regularly interacts with the knowledge base to
get inputs, and also update it.
#Data Mining – On what kind of data
Relational Databases
The software programs involve mechanisms for the definition of database
structures; for data storage; for concurrent, shared, or distributed data
access.
Relational Databases is a collection of Tables, which
contains a set of attributes as Fields and
Tuples/Records as rows. Also has relational query language.
Data mining is applied to relational databases for finding Trends & Patterns.
• For example, data mining systems can analyse customer data to predict
the credit risk of new customers based on their income, age, and previous
credit information.
• Also detect deviations, such as items whose sales are far from those
expected in comparison with the previous year.
Data warehouses
Data warehouse: is a repository of information collected from multiple sources, stored under a unified
schema.
They are constructed via the process of Data cleaning, Data Integration, Data Transformation, Data
Loading, Periodic data refreshing etc.
It is electronic storage of a large amount of information by a business which is designed for query and
analysis. It is a process of transforming data into information and making it available to users in a
timely manner to make a difference.

Typical framework of a DW
Data source
in Chicago
Client
Data source Clean
in New York Integrate Query &
Transform Data
Warehouse
analysis
Data source Load
in Toronto Refresh tools
Client
Data source
in
Vancouver
 DW
• Historical information.
• Usually modelled by a Multidimensional database structure.
• A multidimensional model views data in the form of a data-cube.
• A data cube enables data to be modeled and viewed in multiple dimensions in which
each dimension corresponds to an attribute or a set of attributes in the schema, and
each cell stores the value of some aggregate measure such as count or sum.
• For example, a shop may create a sales data warehouse to keep records of the
store's sales for the dimension time, item, and location. These dimensions allow the
save to keep track of things, for example, monthly sales of items and the locations at
which the items were sold. Each dimension has a table related to it, called a
dimensional table, which describes the dimension further.
For example, a dimensional table for an item may contain the attributes item name,
brand, and type.
Multidimensional Data Cube: OLAP operations
• DW systems are well suited for on-line analytical processing (OLAP)
• OLAP is an acronym for Online Analytical Processing. OLAP performs multidimensional
analysis of business data and provides the capability for complex calculations, trend
analysis, and sophisticated data modeling.
• OLAP operations allow the user to view the data at differing degrees of
summarization

• Drill –down – Also known as Consolidation/Aggregation.

• Roll –up
• Dice
• Slice
• Pivot (Rotate)
3. Transactional databases
• A transactional database consists of a file where each record
represents a transaction.

• A transaction typically includes a unique transaction identity

number (trans ID) and a list of the items making up the
transaction (such as items purchased in a store)

• The transactional database may have additional tables

associated with it, - regarding the sale, the date of the
transaction, the customer ID number, the ID number of the
salesperson and of the branch at which the sale occurred etc

• Each record represents a transaction

• Unique transaction number and a list of items making up the
transaction
• Data mining systems for transactional data can identify frequent
itemsets, that is, sets of items that are frequently sold together.
Data Mining Functionalities—
What Kinds of Patterns can Be Mined?
Data Mining Functionalities

Data mining functionalities are used to specify the kind of patterns to

be found in data mining tasks.
Data mining tasks can be classified into two categories:
• Descriptive mining tasks characterize the general properties of the
data in the database.
• Predictive mining tasks perform inference on the current data in
order to make predictions.
• Users may have no idea regarding the kinds of patterns.
• Can search several kinds of patterns in parallel.
• Should find patterns at various granularity.
Descriptive functions

a) Concept/Class Description
b) Mining of Frequent Patterns
c) Mining of Associations
d) Mining of Correlations
e) Mining of Clusters
a) Concept/Class Description: Characterization and Discrimination

• Data can be associated with classes or concepts

• Eg: In a company
❑ Classes of items for sales - computer and printers
❑Concepts of customers - big spenders and budget spenders.
Such descriptions of a class or a concept are called class/concept
descriptions.

These descriptions can be derived using:-

• Data Characterization - This refers to summarizing data of a class under
study. This class under study is called as the Target Class.
• Data Discrimination - It refers to the mapping or comparison of a Target
class with some predefined group or class.
• Or by both data characterization and discrimination.
Data characterization is a summarization of the general characteristics or
features of a target class of data.
• Eg:
1) To study the characteristics of software product whose sales increased by 10%
in the last year, the data related to such products can be collected by executing
an SQL query.
2) The characteristics of customers who spend more than $1,000 a year at
AllElectronics.
▪ Result - profile of the customers, - they are 40–50 years old, employed, and
have excellent credit ratings.

▪ The system should allow users to drill down on any dimension, such as on
occupation in order to view these customers according to their type of
employment

• The output of data characterization - Pie charts, Bar charts, multidimensional

data cubes, multidimensional tables etc.
• Data discrimination is a comparison of the general features of target class data objects with
the general features of objects from one or a set of contrasting classes.

• Example: User- compare the general features of software products whose sales increased by
10% in the last year with those whose sales decreased by at least 30% during the same period.
• Compare two groups of AllElectronics customers :
1) Those who shop for computer products regularly (more than 2 times a month)
2) those who rarely shop for such products (i.e., less than 3 times a year).

• Result –
a) 80% of the customers - frequently purchase computer products are between 20 and 40
years old and have a university education
b) 60% of the customers - infrequently buy such products are either seniors or youths, and
have no university degree.

Drilling down on a dimension, such as occupation, or adding new dimensions, such as income
level, may help in finding even more discriminative features between the two classes.
• The methods and output used for data discrimination are similar to those used for data
characterization.
Frequent patterns are those patterns that occur frequently in data.
Kinds of frequent patterns:
❖Frequent Itemsets - It refers to a set of items that frequently appear
together in a transactional data set.
Eg: milk and bread , bread and jam, cell phone and charger,
❖Frequent Subsequence- A sequence of patterns that occur frequently
such as purchasing laptop, followed by a camera, then a memory card.
❖Frequent Sub Structure - Substructure refers to different structural
forms, such as graphs, trees, or lattices, which may be combined with
item-sets or subsequences . If a substructure occurs frequently in a
graph database, it is called a (frequent) structural pattern.
• Discovery of togetherness or connection of items – Association rule
• This process involves uncovering the relationship between data and
deciding the rules of the association.
• Associations are used in retail sales to identify patterns that are frequently
purchased together.
• For example, a retailer generates an association rule that shows that 70%
of time milk is sold with bread and only 30% of times biscuits are sold with
bread.
• Eg:80% of people buy soft drinks together with potato chips
 Example
Association analysis: Suppose a marketing manager of AllElectronics, would like to
determine which items are frequently purchased together within the same
transactions.????

• A rule, mined from the AllElectronics transactional database, is

buys(X, “computer”)=>buys(X, “software”)=>[support = 1%, confidence = 50%]

where X is a variable representing a customer

• 50% confidence, or certainty means → that if a customer buys a computer, there is a 50% chance that
she will buy software as well.

• 1% support means → that 1% of all of the transactions under analysis showed that computer and
software were purchased together.
Total 1% of transactions in database follow the rule.
• This association rule involves a single attribute or predicate (i.e., buys) that
repeats. Such Asociation rules having a single predicate are referred to as single-
dimensional association rules.
• buys(X, “computer”)=>buys(X, “software”)=>[support = 1%, confidence = 50%]

Consider an association between more than one attribute, or predicate

age(X, “20...29”)^income(X, “20K...29K”)=>buys(X, “CD player”) [support = 2%, confidence = 60%]

• 2% of customers who are 20 to 29 years of age with an income of 20,000 to

29,000 and have purchased a CD player
• There is a 60% probability that a customer in this age and income group will
purchase a CD player.

Association between age,income,buys.

If attribute is referred to as a dimension, the above rule can be referred to as a
multidimensional association rule.
• It is a kind of additional analysis performed to uncover interesting statistical
correlations between associated-attribute-value pairs or between two item sets
to analyze that if they have positive, negative or no effect on each other.
• A value close to 0 in this range indicates a lack of correlation. Values closer to
the boundaries -1 strong negative correlation (one goes down as one goes up),
close to 1 indicate strong positive correlation.
• It is used to study the closeness of the relationship between two or more
variables i.e. the degree to which the variables are associated with each
other.
• Measuring the correlation between the variables "Age" and "Income" or between
the variables "Income" and "TotalPurchase", and so on.
• Suppose in a manufacturing firm, they want the relation between –
• Demand & supply of commodities.
• Production volume & the efficiency of machinery equipment.
• Cluster analysis or clustering is the task of grouping a set of objects in such
a way that objects in the same group (called a cluster) are more similar (in
some sense) to each other than to those in other groups (clusters).
• Data can be grouped into categories on the basis of their similarities or
differences
• In cluster analysis, there is no prior information about the group
or cluster membership for any of the objects.
• The objects are clustered or grouped based on the principle of maximizing the
intraclass similarity and minimizing the interclass similarity.
• The cluster analysis can then identify groups of patients that have similar
symptoms.
• A cluster analysis then may identify what homogeneous groups exist among
students (for example, high achievers in all subjects, or students that excel in
certain subjects but fail in others).
• Classification
• Prediction
• Regression
• Time Series analysis
Classification
✓Classification is the process of finding a Model/Function that describes and
distinguishes data classes.
✓Purpose - able to use this model to predict the class of objects whose class label
is unknown. This derived model is based on the analysis of sets of training data.
• Derivation of a function or model which determines the class of an object based
on its attributes.

“How is the derived model presented or look like?”

The derived model may be represented in various forms, such as
❖Classification (IF-THEN) Rules
❖Decision Trees
❖Mathematical Formulae
❖Neural Networks
IF-THEN Rules based classifier
Rule-based classifier makes use of a set of IF-THEN rules for classification.
We can express a rule in the following form −
IF condition THEN conclusion

Let us consider a rule R1,

R1: IF age = youth AND student = yes THEN buy_computer = yes

• The IF part of the rule is called rule antecedent or precondition.

• The THEN part of the rule is called rule consequent.
• The antecedent part of the condition consist of one or more attribute tests and these tests
are logically ANDed.
• The consequent part consists of class prediction.(here Yes/No)
Decision Tree classifier
A decision tree is a flow-chart-like tree structure, where
Each node denotes a test on an attribute value
Each branch represents an outcome of the test
Tree leaves represent classes.
• Decision trees can easily be converted to classification rules.
Neural network classifier

A neural network, when used for classification, is typically a collection

of neuron-like processing units with weighted connections between the
units.
Supervised & Unsupervised learning
• The learning algorithm of a neural network can either be supervised or
unsupervised.
• A neural net is said to learn supervised, if the desired output is already
known. There will be a input and output pattern.
• While learning, one of the input patterns is given to the net's input layer.
This pattern is propagated through the net to it's output layer. The output
layer generates an output pattern which is then compared to the target
pattern.
• Depending on the difference between output and target, an error value is
computed.
• The greater the computed error value is, the more the weight values will be
changed.
• Neural nets that learn unsupervised have no such target outputs
• Prediction used a combination of other data mining techniques such
as trends, clustering, classification, etc.
• It analyzes past events or instances in the right sequence to predict a
future event.
• The term prediction may refer to both numeric prediction and class
label prediction.

Regression analysis
• Regression analysis is a statistical methodology that is most often
used for numeric prediction.
• Primarily it gives the exact relationship between two or more
variables in the given data set.
• For example, we might use it to project certain costs, depending on
other factors such as availability, consumer demand, and competition.
Outliers are data objects that do not comply with
the general behaviour or model of the data available.
• Outliers are data elements that cannot be grouped in a given class or
cluster
• Sometimes outliers can be considered noise and discarded in some
applications. An outlier can cause serious problems in statistical
analyses.

Evolution Analysis(Time series) - refers to the description and model

regularities or trends for objects whose behavior changes over time.
• Ie, the study of time related data that changes with time.
Data Mining Technologies
 DM Technologies
• Data mining is the process of extracting the useful information, which is
stored in the large database.
• It is a powerful tool, which is useful for organizations to retrieve the useful
information from available data warehouses.
• Several technologies that strongly influence the development of data
mining are statistics, machine learning, pattern recognition, database and
data warehouse systems, information retrieval, visualization, algorithms,
high-performance computing, and many application domains
1. Statistics
• It uses the mathematical analysis to express
representations, model and summarize empirical data or real
world observations.
• Statistical analysis involves the collection of methods,
applicable to large amount of data to conclude and report
the trend.
2. Machine learning
• Machine Learning is the science of getting computers to learn
and act like humans do, and improve their learning over time
in autonomous fashion, by feeding them data and information.
• In machine learning, an algorithm is constructed to predict the
data from the available database (Predictive analysis).
The four types of machine learning are:

1. Supervised learning .
It is based on the classification. In this method, the desired
outputs are included in the training dataset.
2. Unsupervised learning
Unsupervised learning is based on clustering. Clusters are
formed on the basis of similarity measures and desired outputs
are not included in the training dataset.

3. Semi-supervised learning
Semi-supervised learning includes some desired outputs to the
training dataset to generate the appropriate functions. This method
generally avoids the large number of labeled examples (i.e. desired outputs).

4. Active learning :
Active learning is a powerful approach in analyzing the data efficiently.
Active learning is the subset of machine learning in which a learning algorithm can query a user
interactively to label data with the desired outputs.
ie, selects the subset of examples to be labeled next from the pool of unlabeled data
3. Information retrieval
• Science of searching for documents or information in documents.
• Retrieving Information from text or images with the help of the semantics
of objects (text, images).
For example: Finding relevant information from a large document.
4. Database systems and data warehouse
• Databases are used for the purpose of recording the data.
• Online Transactional Processing (OLTP) uses databases for day to day
transaction
purpose.
• Data warehouses are used to store historical data which helps to take
strategical decision for business.
• It is used for online analytical processing (OALP), which helps to analyze
the data.
Applications of Data mining
 DM Applications
• Data mining is used in diverse applications such as banking, marketing,
healthcare, telecom industries, and many other areas.
• Data mining techniques help companies to gain knowledgeable
information, increase their profitability by making adjustments in processes
and operations. It is a fast process which helps business in decision making
through analysis of hidden patterns and trends.
• AMAZON: Amazon uses Text Mining to find the lowest price of the product.
• MC Donald’s: McDonald’s uses big data mining to enhance its customer
experience. It studies the ordering pattern of customers, waiting times, size
of orders, etc.
• NETFLIX: Netflix finds out how to make a movie or a series popular among
the customers using its data mining insights.
1. Financial Analysis
• The banking and finance industry relies on high-quality, reliable data. In loan markets,
financial and user data can be used for a variety of purposes, like predicting loan
payments and determining credit ratings. Banks are the first users of data mining
technology as it helps them with credit assessment. Data mining analyzes what
services offered by banks are used by customers, what type of customers use
ATM cards and what do they generally buy using their cards (for cross-selling).
• Banks use data mining to analyze the transactions which the customer do
before they decide to change the bank to reduce customer attrition. Also, some
outliers in transactions are analyzed for fraud detection.

2. Telecommunication Industry
• Expanding and growing at a fast pace, especially with the advent of the internet. Data
mining can enable key industry players to improve their service quality to stay ahead in
the game.
• Cellular Phone Companies use data mining techniques to avoid churning.
Churning is a measure showing the number of customers leaving the services.
It detects patterns that show how customers can benefit from the services to
retain customers.
3. Intrusion Detection
• Global connectivity in today’s technology-driven economy has presented security
challenges for network administration. Network resources can face threats and actions
that intrude on their confidentiality or integrity. Therefore, detection of intrusion has
emerged as a crucial data mining practice. Association and correlation analysis,
aggregation techniques, visualization, and query tools can effectively detect any
anomalies or deviations from normal behavior.

4. Retail Industry
• The organized retail sector holds sizable quantities of data points covering sales,
purchasing history, delivery of goods, consumption, and customer service. The databases
have become even larger with the arrival of e-commerce marketplaces.
• In modern-day retail, data warehouses are being designed and constructed to get the full
benefits of data mining. Multidimensional data analysis helps deal with data related to
different types of customers, products, regions, and time zones. Online retailers can also
recommend products to drive more sales revenue and analyze the effectiveness of their
promotional campaigns. So, from noticing buying patterns to improving customer service
and satisfaction, data mining opens many doors in this sector.
5. Spatial Data Mining
• Geographic Information Systems (GIS) and several other navigation applications
make use of data mining to secure vital information and understand its
implications. This new trend includes extraction of geographical, environment,
and astronomical data, including images from outer space. Typically, spatial data
mining can reveal aspects like topology and distance.
6. Biological Data Analysis
• Biological data mining practices are common in genomics, proteomics, and
biomedical research. From characterizing patients’ behaviour and predicting
office visits to identifying medical therapies for their illnesses, data science
techniques provide multiple advantages.
7. Criminal Investigation
• Data mining activities are also used in Criminology, which is a study of crime
characteristics. First, text-based crime reports need to be converted into word
processing files. Then, the identification and crime-machining process would
take place by discovering patterns in massive stores of data
8. Healthcare Management
• The data mining method is used to identify chronic diseases,
track high-risk regions prone to the spread of disease, design
programs to reduce the spread of disease. Healthcare
professionals will analyze the diseases, regions of patients
with maximum admissions to the hospital.
• With this data, they will design the campaigns for the region
to make people aware of the disease and see how to avoid
it. This will reduce the number of patients admitted to
hospitals.
9. Customer Relationship Management can be reinforced with
data mining. Good customer Relations can be built by
attracting more suitable customers, better cross-selling and
up-selling, better retention.
Major Issues in Data mining
• Major data mining issues can be partitioned into five groups:

1. Mining methodology.
2. User Interaction.
3. Efficiency and scalability.
4. Diversity of data types.
5. Data mining and society.
1. 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 uncertainty, noise or incompleteness of data
- Pattern evaluation and pattern- or constraint-guided mining.

2. User Interaction
- Interactive mining
- Incorporation of background knowledge
- Ad hoc data mining and data mining query languages
- Presentation and visualization of data mining results
3. Efficiency and Scalability
- Efficiency and scalability of data mining algorithms
- Parallel, distributed, and incremental mining algorithms

4. Diversity of Database Types

-Handling complex types of data
-Mining dynamic, networked, and global data repositories

5. Data Mining and Society

-Social impacts of data mining
-Privacy-preserving data mining
-Invisible data mining
 Module1
Data & Attribute types
Data Objects and Attribute Types
Data - Basic Statistical Descriptions of Data
Data Visualization
Measuring Data Similarity and Dissimilarity
Data Objects and Attribute Types
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.
Data objects are typically described by attributes.
If the data objects are stored in a database, they are data
tuples/Records.
Database rows -> data objects; columns ->attributes.
Attributes/ Data
Attributes
• Attribute (or dimensions, features, variables): a data field,
representing a characteristic or feature of a data object.
Example:
Customer Object: customer _ID, name, address, designation, salary etc.
Flower object: color, no_Petals, petal_length, type etc.
Eye: eyecolor, eyeshape, eyelength etc.
• Attribute Types:
• Nominal
• Binary
• Ordinal
• Numeric: quantitative
• Interval-scaled
• Ratio-scaled
4
Attribute Types
Nominal:”relating to names”
The values of nominal attributes are symbols or “names of things”.
Nominal Attributes only provide enough information to differentiate between one object and another.
• Hair_color = { black, blond, brown, grey, red, white}
• marital status, occupation,petal_length, eyecolor
Binary
Nominal attributes are with only 2 states (0 and 1)
Where 0 is the absence of any features and 1 is the inclusion of any characteristics.(Boolean)
• Symmetric binary: both outcomes equally important
e.g., gender (male and female)
• Asymmetric binary: outcomes not equally important.
e.g., medical test (positive vs. negative)
• Convention: assign 1 to most important outcome (e.g., Covid positive)
Ordinal
The ordinal attribute with possible values provides meaningful order. Such as Rankings, Grades, Height
• Values have a meaningful order (ranking) but magnitude between successive values is not known.
• Size = {small, medium, large}, grades, army rankings
 Numeric Attribute Types
• Numeric attribute: It is quantitative, such that quantity can be measured and
represented in integer or real values are of two types - Interval Scaled attribute &
Ratio scaled attributes
• Interval
• It is measured on a scale of equal size units, these attributes allows us to compare such as
temperature in C or F.
• A Celsius and Fahrenheit scales, calendar date.
• Ratio
• Numeric attribute with an inherent zero-point.
• A Kelvin scale is an ideal example of a ratio scale.
• Along with all the other values, in a Kelvin scale, the zero point has a
relevant meaning.

6
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
• Continuous attributes are typically represented as floating-
point variables

8
Basic Statistical Descriptions of Data
Measures of
1. Central Tendency
2. Distribution
3. Dispersion
4. Association
Basic Statistical Descriptions of Data
• For data preprocessing to be successful, it is essential to have an overall
picture of your data.
• Basic statistical descriptions can be used to identify properties of the data
and highlight which data values should be treated as noise or outliers.
• To better understand the data: central tendency, variation and spread
Describe data using measures of central tendency and dispersion:
• for a set of individual data values, and
• for a set of grouped data.
• Use the computer to visually represent data.
• The basic statistical descriptions of data help us to measure some
very special properties of the data.
• One of these properties is the central tendency. Measuring the
central tendency helps us know, where does most of the data lie
taking into account the whole set of data.
• Let us take a use case. Suppose that we have a set of values and we
want to find a value that has the capability of replacing the whole
dataset and still achieve a relevant result.
• Finding the central tendency helps us achieve this use case.
 Descriptive Statistics: Shape – Center - Spread
When we gather data, we want to uncover the “information” in it. One easy way
to do that is to think of: “Shape –Center- Spread”

• Shape – What is the shape of the histogram?

• Center – What is the mean or median?
• Spread – What is the range or standard deviation?

• Measures of Central Tendency : The Center: Mean, Median, Mode, Midrange

• Measures of Shapes : Distributions
• Measures of Dispersion : The Spread: Range, Variance, Standard deviation
• Measures of Association : Coefficient of correlation r, Coefficient of
determination r^2
1. Measures of Central tendency
( A single number that can represent entire dataset)

Mean, Median, Mode, Midrange

 Mean- Most effective central measure
Suppose that we have a dataset, in which, we have an attribute “age” of supposing 100
people. Let the corresponding ages be a1, a2, a3…..an.
The mean of the ages of these 100 people means the mean-age of the people, which is
equivalent to answering, “what age do most of the people belong to?”
Mathematically, the mean of n values can be defined as:
•

• Disadvantages: When extreme values are in data

Suppose that out of 100 people in a company.
95 have a salary in the range 2 Lakhs to 5 Lakhs, but 5 people have above 100 Lakhs. In
this case, the mean salary will be around 8 Lakhs. But as we can see that most of the
people have salaries between 2 Lakhs and 5 Lakhs, so this result did have much
significance and was not at all useful. We cannot replace the whole dataset with the
mean in this scenario. In such cases, we have another measure of central tendency
which is the Median of the data.
• Weighted Arithmetic Mean – If X values are associated with weights.
 Weighted Mean
When what you have weighted data, compute the mean using
µ = (Swixi)/Swi

Eg: Camera rating. Suppose rating be like

Image Quality 50%
Battery Life 30%
Zoom Range 20%
Camera A gets 8 (out of 10) for Image Quality, 6 for Battery Life and 7 for Zoom Range
Camera B gets 9 for Image Quality, 4 for Battery Life and 6 for Zoom Range

Camera A : 0.5 × 8 + 0.3 × 6 + 0.2 × 7 = 4 + 1.8 + 1.4 = 7.2

Camera B : 0.5 × 9 + 0.3 × 4 + 0.2 × 6 = 4.5 + 1.2 + 1.2 = 6.9

Which camera is best??? (Camera A)

 Median
• When our dataset has skewness (data is asymmetric), calculating the
Median could prove to be more beneficial than Mean.
• Median is defined as the centermost value of an ordered numerical
dataset.
• For calculating the Median, it is important for the dataset to be in
some order, i.e. it should be sorted.
• To find the median:
1. Put the data in an array.
If the data set has an ODD number of numbers, the median is the middle value.
If the data set has an EVEN number of numbers, the median is the AVERAGE of the
middle two values.
(Note that the median of an even set of data values is not necessarily a member of the
set of values.)

The median is particularly useful if there are outliers in the data set.
 Mode
This is another measure of central tendency.
The mode is the most frequent value.
Bimodal, Trimodal, Multimodal datasets
• There is an equal possibility that a dataset might have two modes. Such
datasets are known as Bimodal.
• Trimodal- Data set with three modes. Ie, there are three data values that
are having highest frequencies.
• Ex: A={2,2,2,3,4,4,5,6,5,4,7,5,8} is 2,4 and 5
• In general, a dataset with two or more modes is known as Multimodal.
• While there is just one value for the mean and one value for the median,
there may be more than one value for the mode of a data set.
 Bimodal dataset

One major implication of a bimodal data set is that it can

reveal to us that there are two different types of
individuals represented in a data set.
A histogram of a bimodal data set will exhibit two peaks
or humps.
• For example, a histogram of test scores that are
bimodal will have two peaks.
These peaks will correspond to where the highest
frequency of students scored.
If there are two modes, then this could show that there
are two types of students: those who were prepared for
the test and those who were not prepared.
Midrange
This is defined as the average of the largest and smallest values in the set of
values.
It is a measure of central tendency which is the arithmetic mean of the
maximum and minimum values in a data set.(Max() and Min())
Midrange is useful for finding a quick average or midpoint of certain data sets.
Note that in the presence of outliers, or data points that differ significantly
from the other points in a data set, the midrange would alter significantly.
While outliers can cause difficulties in any statistical analysis, it is particularly
damaging for the midrange that depends only on the maximum and minimum
values in its calculation.
 2. Measures of Shape
Distributions – Symmetric, Asymmetric (Positively skewed, Negatively skewed) ,
uni-modal, bi-modal, multimodal.
Shape of distribution
• We can characterize the shape of a data set by looking at its histogram.
• First, if the data values seem to pile up into a single "mound", we say
the distribution is unimodal.
• If there appear to be two "mounds", we say the distribution
is bimodal.
• If there are more than two "mounds", we say the distribution
is multimodal.
If mean = median = mode, the shape of the distribution is symmetric.
In a symmetrical distribution the two sides of the distribution are a mirror image of
each other.

In an asymmetrical distribution the two sides will not be mirror images of each other.
Skewness is the tendency for the values to be more frequent around the high or low
ends of the x-axis.

• If mode < median < mean, the shape of the distribution trails to the right, is
positively skewed (Right skewed).
• If mean < median < mode, the shape of the distribution trails to the left, is
negatively skewed(Left skewed).

Distributions of various “shapes” have different properties and names such as the
“normal” distribution, which is also known as the “bell curve” (among
mathematicians it is called the Gaussian Distribution).
 Symmetric Asymmetric Right skewed

Asymmetric Left skewed Symmetric Bimodal

 3. Measures of Dispersion
Tells how spread out the data items are.

Range , Quantiles, Interquartile Ranges, Variance, Standard deviation

 Dispersion/Variance means Spread
The measures of dispersion are important as it helps in
understanding how much a data is spread (i.e. its variation) around a
central value.

The measures of dispersion help to interpret the variability of data.

Helps to know how much homogenous or heterogeneous the data is.
It shows how squeezed or scattered the variable is.
 Range
The range is the simplest measure of spread.
It is simply the difference between the largest and the smallest values
in the data.
Range = largest value – smallest value
This measure of spread does not take into account anything about the
distribution of the data other than the extremes.

Example: 1, 3,5, 6, 7 => Range = 7 -1= 6

 Quartiles
A quartile divides a sorted data set into 4 equal parts, so that each part
represents ¼ of the data set.
Generally divisions are called Quantiles
Example: Height (comparing heights in boys and girls dataset)
TALLEST 25% ( height values> Q3)
• 25% of the girls’ heights are between 150 cm and 160 cm
• 25% of the boys’ heights are between 160 cm and 170 cm
CONCLUSION: all the boys in the top 25% are taller than the girls.

SHORTEST 25% ( height values< Q1)

• 50% of the girls have heights that are less than 140 cm
• 50% of the boys have heights that are less than 148 cm.
CONCLUSION: all the boys in the low 25% are taller than the girls.

Middle 50% (height >Q1 && height <Q3)

• The middle 50% of the girls have heights between 130 cm and 150 cm
• The middle 50% of the boys have heights between 145 cm and 160 cm.
CONCLUSION: all the boys in the middle 50% are taller than the girls.

Final Conclusion : In general the boys are taller than the girls.
: 25% of the boys are taller than the tallest girl.
Interquartile Range - IQR
• Interquartile Range (IQR): The distance between the first and third
quartiles is a simple measure of the spread that gives the range
covered by the middle half of the data.

• This distance is called the Interquartile range.

IQR = Q3 - Q1
 Quantiles
The 2-quantile is the data point dividing the lower and upper halves of the data
distribution. It corresponds to the median of the set of values.
The 4-quantiles are the three data points that split the data distribution into four
equal parts, where each part represents one-fourth of the data distribution.
Also commonly called as quartiles.
 Variance & Standard Deviation
These are the measures of data dispersion. We can measure how spread
out a data distribution is.
• A low standard deviation means that the data observations tend to be
very close to the mean.
• A high standard deviation means that the data are spread out over a large
range of values.
• Mathematically, the standard deviation is defined as the square root of
the variance.
• The variance of N observations, x1, x2, x3….xn, for a numeric attribute X is
Data Visualization
Data Visualization

• Data visualization is the graphical representation of information and

data.
• By using visual elements like charts, graphs, and maps, data
visualization tools provide an accessible way to see and understand
trends, outliers, and patterns to analyze massive data and to make
data driven decisions.
• It helps in analyzing a large amount of data in a simpler way.
• It makes complex data more accessible, understandable, and usable.
• If we can see something, we internalize it quickly. It’s storytelling with
a purpose.
 Pixel-Oriented Visualization Techniques
• A simple way to visualize the value of a dimension is to use a pixel where the colour of
the pixel reflects the dimension’s value.
• 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
• Ex: Sort all customers in income-ascending order

(a) Income (b) Credit Limit (c) transaction volume (d) age
42
Geometric Projection Visualization Techniques
• Visualization of geometric transformations and projections of the
data
• Methods
• Scatterplot

43
Geometric Projection Visualization Techniques

• A drawback of pixel-oriented visualization techniques is that they cannot help us

much in understanding the distribution of data in a multidimensional space.
• For example, they do not show whether there is a dense area in a
multidimensional subspace.
• Geometric visualization techniques help users find interesting projections of
multidimensional data sets.
• A scatter plot displays 2-D data points using Cartesian coordinates.
• A third dimension can be added using different colors or shapes to represent
different data points.
 Scatterplot
• an example, where X and Y are two spatial attributes and the
third dimension is represented by different shapes.

45
Icon-Based 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

46
 Chernoff Faces
• They display multidimensional data of up to 18 variables (or dimensions) as a
cartoon human face.
• Chernoff faces help reveal trends in the data.
• Components of the face, such as the eyes, ears, mouth, and nose, represent
values of the dimensions by their shape, size, placement, and orientation.
• For example, dimensions can be mapped to the following facial
characteristics: eye size, eye spacing, nose length, nose width, mouth
curvature, mouth width, mouth openness, pupil size, eyebrow slant, eye
eccentricity, and head eccentricity.

• A way to display variables on a two-dimensional

surface, e.g., let x be eyebrow slant, y be eye size,
z be nose length, etc.
• The figure shows faces produced using 10
characteristics--head eccentricity, eye size, eye
spacing, eye eccentricity, pupil size, eyebrow
slant, nose size, mouth shape, mouth size, and
mouth opening
47
 Stick Figure
• This technique maps multidimensional data to five-piece stick figure.
• Each figure has four limbs and a body.
• Two dimensions are mapped to the display (x and y) axes and the remaining
dimensions are mapped to the angle or length of the limbs.
• Age and income are mapped to the display axes. Remaining dimensions gender,
education and so on are mapped to stick figures.
• Stick figures having a similar shape, means that they are similar with respect to the
dimensions that are assigned to the limbs of the stick figure icon.
• The resulting visualization shows texture patterns, reflecting data trends.

A census data
figure showing
age, income,
gender,
education, etc.

48
Two attributes mapped to axes, remaining attributes mapped to angle or length of limbs”. Look at texture pattern
Hierarchical Visualization Techniques
• They partition all dimensions into subsets (i.e.,
subspaces). The subspaces are visualized in a hierarchical
manner.
• Methods
• Worlds-within-Worlds
• Tree-Map

49
 Worlds-within-Worlds
• “Worlds-within-Worlds,” also known as n-Vision, is a representative hierarchical
visualization method.
• Suppose we want to visualize a 6-D data set, where the dimensions are F,X1, : : : ,X5.
• We want to observe how dimension F changes with respect to the other dimensions.
We can first fix the values of dimensions X3,X4,X5 to some selected values,say, c3, c4,
c5.
• We can then visualize F,X1,X2 using a 3-D plot, called a world.
• A user can interactively change, in the outer world, the location of the origin of the
inner world. The user then views the resulting changes of the inner world. Moreover,
a user can vary the dimensions used in the inner world and the outer world. Given
more dimensions, more levels of worlds can be used, which is why the method is
called “worlds-within worlds.

50
 Tree-Map
• Tree-maps display hierarchical data as a set of nested rectangles
• Screen-filling method which uses a hierarchical partitioning of the
screen into regions depending on the attribute values

51
Newsmap: Google News Stories in 2005
Measuring Data Similarity and Dissimilarity

• In data mining applications, such as clustering, outlier analysis, and

nearest-neighbour classification, we need ways to assess how alike or
unalike objects are in comparison to one another.
• A cluster is a collection of data objects such that the objects within a
cluster are similar to one another and dissimilar to the objects in other
clusters. For example, a store may want to search for clusters of
customer objects, resulting in groups of customers with similar
characteristics (e.g., similar income, area of residence, and age).
• Outlier analysis also employs clustering-based techniques to identify
potential outliers as objects that are highly dissimilar to others.
• Knowledge of object similarities can also be used in nearest-
neighbour classification schemes where a given object (e.g., a patient)
is assigned a class label (relating to, say, a diagnosis) based on its
similarity toward other objects in the model.
Similarity and Dissimilarity
• Similarity
• Numerical measure of how alike two data objects are
• Often falls in the range [0,1]
• Value is higher when objects are more alike. Value of 1
indicates the objects are identical.
• Dissimilarity (e.g., distance)
• Numerical measure of how different two data objects are
• Lower when objects are more alike
• Minimum dissimilarity is often 0. It returns a value of 0 if the
objects are the same
• Upper limit varies
• Proximity refers to a similarity or dissimilarity

53
 Data Matrix and Dissimilarity Matrix
• Data matrix(object-by-attribute structure)
• used to store the data objects  x11 ... x1f ... x1p 
having multiple attributes.  
• n data objects with p  ... ... ... ... ... 
x ... xif ... xip 
attributes.  i1 
 ... ... ... ... ... 
x ... xnf ... xnp 
• Dissimilarity matrix(object-by-object  n1 
structure)
• used to store dissimilarity  0 
values for pairs of objects  d(2,1) 
 0 
• n data objects, but registers
only the distance  d(3,1) d ( 3,2) 0 
 
• A triangular matrix  : : : 
• Single mode d ( n,1) d ( n,2) ... ... 0

54
 Proximity Measure for Nominal Attributes
• Nominal attribute can take on two or more states ( e.g., red,
yellow, blue, green)
• The dissimilarity between two objects i and j can be computed
based on the ratio of mismatches:

d (i, j) = p −
p
m

• where m is the number of matches (i.e., the number of

attributes for which i and j are in the same state), and p is the
total number of attributes describing the objects

55
Proximity Measure for Binary Attributes
• Binary attribute has only one of two states: 0 and 1, where 0
means that the attribute is absent, and 1 means that it is present

56
 Dissimilarity of Numeric Data: Minkowski Distance
• First the data are normalized before applying distance calculations. This involves
transforming the data to fall within a smaller or common range, such as [-1, 1] or
[0.0, 1.0]. Normalizing the data attempts to give all attributes an equal weight.
 Distance on Numeric Data: Minkowski Distance
• Minkowski distance: is a generalization of the Euclidean and Manhattan
distances

where i = (xi1, xi2, …, xip) and j = (xj1, xj2, …, xjp) are two p-
dimensional data objects, and h is the order (the distance so
defined is also called L-h 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

58
 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.

• Applications: information retrieval, biologic taxonomy, gene feature mapping, ...

• Cosine measure: If x and y are two vectors (e.g., term-frequency vectors), then

59
 Summary
• Data attribute types: nominal, binary, ordinal, interval-scaled, ratio-scaled
• 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.

60
 Chapter 3: Data Preprocessing

◼ Data Preprocessing: An Overview

◼ Data Quality

◼ Major Tasks in Data Preprocessing

◼ Data Cleaning

◼ Data Integration

◼ Data Reduction

◼ Data Transformation and Data Discretization

◼ Summary
1
 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 transformation and data discretization
◼ Normalization
◼ Concept hierarchy generation

2
3
 Chapter 3: Data Preprocessing

◼ Data Preprocessing: An Overview

◼ Data Quality

◼ Major Tasks in Data Preprocessing

◼ Data Cleaning

◼ Data Integration

◼ Data Reduction

◼ Data Transformation and Data Discretization

◼ Summary
4
 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.,
◼ Birthday=“03/07/2010”, Age=“42”
◼ 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?
5
 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

6
 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?!
◼ Use a measure of central tendency : the attribute mean
◼ Use the attribute mean for all samples belonging to
the same class: smarter way
◼ the most probable value: inference-based such as
Bayesian formula or decision tree
7
 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

8
 How to Handle Noisy Data?

◼ Binning
◼ first sort data and partition into (equal-frequency) bins

◼ then one can smooth by bin means, smooth by bin

median, smooth by bin boundaries, etc.

each bin contains three values

value in a bin is replaced by the mean value of the bin.

Each bin value is then replaced by the closest

boundary value.
9
 How to Handle Noisy Data?

◼ Regression
◼ smooth by fitting the data into regression functions.
Linear regression involves finding the “best” line to fit two attributes (or
variables) so that one attribute can be used to predict the other. Multiple linear
regression- more than two attributes are involved and the data are fit to a
multidimensional surface.
◼ Clustering -Outlier analysis
◼ detect and remove outliers.

◼ Combined computer and human inspection

◼ detect suspicious values and check by human (e.g.,

deal with possible outliers)

10
 Data Cleaning as a Process
◼ Data discrepancy detection
◼ Use metadata

◼ Check uniqueness rule, consecutive rule and null rule

◼ Use commercial tools

◼ Data scrubbing: use simple domain knowledge (e.g., postal

code, spell-check) to detect errors and make corrections

◼ Data auditing: find discrepancy 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.

◼ Ex: simple transformations to be specified such as to replace

the string “gender” by “sex.”
◼ ETL (Extraction/Transformation/Loading) tools: allow users to
specify transformations through a graphical user interface
11
 Chapter 3: Data Preprocessing

◼ Data Preprocessing: An Overview

◼ Data Quality

◼ Major Tasks in Data Preprocessing

◼ Data Cleaning

◼ Data Integration

◼ Data Reduction

◼ Data Transformation and Data Discretization

◼ Summary
12
 Data Integration
◼ Data integration:
◼ Combines data from multiple sources into a coherent store. The sources
may include multiple databases, data cubes, or flat files
◼ Schema integration: e.g., [Link]-id  [Link]-#
◼ 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 13
 Handling Redundancy in Data Integration

◼ Redundant data occur often when integration of multiple

databases. To resolve this,
◼ 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
◼ Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality
14
 Correlation Analysis (Nominal Data)
◼ Correlation analysis is a statistical method used to
measure the strength of the linear relationship
between two variables and compute their association.
◼ For nominal data, we use the Χ2 (chi-square) test to identify a
correlation relationship between two attributes.

◼ The larger the Χ2 value, the more likely the variables are
related
15
 ◼ The cells that contribute the most to the Χ2 value are
those whose actual count is very different from the
expected count

6/6/2024 Data Mining: Concepts and Techniques 16

 Correlation Analysis (Numeric Data)

◼ Correlation coefficient (also called Pearson’s product moment

coefficient)

i=1 (ai − A)(bi − B) 

n n
(ai bi ) − n AB
rA, B = = i =1
(n − 1) A B (n − 1) A B

where n is the number of tuples, A and B 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 cross-product.
◼ 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
◼ Correlation measures the linear relationship between objects
17
Visually Evaluating Correlation

Scatter plots
showing the
similarity from
–1 to 1.

18
 Covariance (Numeric Data)
◼ Covariance is similar to correlation

Correlation coefficient:

where n is the number of tuples, A and B 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:

19
 Tuple Duplication
◼ In addition to detecting redundancies between attributes,
duplication should also be detected at the tuple level.
[denormalized tables, duplicates]

Data Value Conflict Detection and Resolution

◼ Data integration also involves the detection and resolution of
data value conflicts.
◼ For example, for the same real-world entity, attribute values
from different sources may differ.
◼ This may be due to differences in representation, scaling, or
encoding.

20
21

Chapter 3: Data Preprocessing

◼ Data Preprocessing: An Overview

◼ Data Quality

◼ Major Tasks in Data Preprocessing

◼ Data Cleaning

◼ Data Integration

◼ Data Reduction

◼ Data Transformation and Data Discretization

◼ Summary
21
 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

◼ Numerosity reduction (some simply call it: Data Reduction)

◼ Regression and Log-Linear Models

◼ Histograms, clustering, sampling

◼ Data cube aggregation

◼ Data compression

22
23

What Is Wavelet Transform?

◼ Decomposes a signal into
different frequency subbands
◼ Applicable to n-
dimensional 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
24

Discrete wavelet transform (DWT)

◼ The discrete wavelet transform (DWT) is a linear signal processing
technique. It transforms a vector into a numerically different vector (D to
D’) of wavelet coefficients. The two vectors are of the same length.
However it is useful for compression in the sense that wavelet-transformed
data can be truncated. [D=x1,x2, : : : ,xn]
◼ A small compressed approximation of the data can be retained by storing
only a small fraction of the strongest wavelet coefficient e.g., retain all
wavelet coefficients larger than some particular threshold and the
remaining coefficients are set to zero.
◼ The resulting data representation is very sparse, so that operations take
advantage of data sparsity are computationally very fast if performed in
wavelet space
◼ Given a set of coefficients, an approximation of the original data can be got
by applying the inverse DWT.
◼ The DWT is closely related to the discrete Fourier transform (DFT) a signal
processing technique involving sine’s and cosines.
25

Wavelet Transformation
◼ Wavelet transforms can be applied to multidimensional
data such as data cubes.
◼ Wavelet transforms have many real world applications,
including the compression of fingerprint images,
computer vision, and analysis of time-series data and
data cleaning.
 Principal Component Analysis (PCA)
◼ Principal components analysis (PCA; also called
the K-L, method searches for k n-dimensional Principal
orthogonal vectors that can best be used to components
represent the data, where k <=n. analysis. Y and
1

Y are the first

2

◼ The original data are thus projected onto a much two principal
smaller space, resulting in dimensionality components for
the
reduction. given data.
◼ PCA “combines” the essence of attributes by
creating an alternative, smaller set of variables.
◼ The initial data can then be projected onto this
smaller set. PCA often reveals relationships that
were not previously suspected and thereby
allows interpretations that would not ordinarily
result.
26
 Principal Component Analysis (Steps)
◼ Given N data vectors from n-dimensions, 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
27
 Attribute Subset Selection[feature subset selection]
◼ Attribute subset selection reduces the data set size by removing
irrelevant or redundant attributes (or dimensions).
◼ The goal of attribute subset selection is to find a minimum set of
attributes such that the resulting probability distribution of the data
classes is as close as possible to the original distribution obtained using
all attributes.
◼ Redundant attributes
◼ Duplicate much or all of the information contained in one or more

other attributes
◼ 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
28
 Attribute Selection methods
1. Stepwise forward selection: The procedure starts with an empty set of attributes
as the reduced set. The best of the original attributes is determined and added to
the reduced set. At each subsequent iteration or step, the best of the remaining
original attributes is added to the set.
2. Stepwise backward elimination: The procedure starts with the full set of
attributes. At each step, it removes the worst attribute remaining in the set.
3. Combination of forward selection and backward elimination: The stepwise
forward selection and backward elimination methods can be combined so that, at
each step, the procedure selects the best attribute and removes the worst from
among the remaining attributes.
4. Decision tree induction: Decision tree induction constructs a flowchart like
structure where each internal (nonleaf) node denotes a test on an attribute, each
branch corresponds to an outcome of the test, and each external (leaf) node denotes
a class prediction. At each node, the algorithm chooses the “best” attribute to
partition the data into individual classes.

29
30
Attribute Creation (Feature construction)
◼ Create new attributes (features) that can capture the
important information in a data set more effectively than
the original ones
◼ Such attribute construction can help improve
accuracy and understanding of structure in high
dimensional data.
◼ For example, we may wish to add the attribute area
based on the attributes height and width.

31
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.: Log-linear models—estimate discrete multidimensional
probability distributions
◼ Non-parametric methods
◼ Do not assume models

◼ Major families: histograms, clustering, sampling, …

32
 y
Regression Analysis Y1
◼ Regression analysis: A collective name for
techniques for the modeling and analysis of
Y1’
numerical data consisting of values of a y=x+1
dependent variable (also called response
variable or measurement) and of one or
more independent variables ( explanatory x
X1
variables or predictors)
◼ For example, a random variable, y (called a
◼ Used for prediction
response variable), can be modeled as a
(including forecasting
linear function of another random variable, of time-series data),
x (called a predictor variable), with the inference, hypothesis
equation y = wx + b, testing, and modeling
◼ The parameters are estimated so as to give of causal relationships
a "best fit" of the data.
33
 Regress Analysis and Log-Linear Models
◼ Linear regression: Y = w X + b
◼ Two regression coefficients, slope w and intercept 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 = b0 + b1 X1 + b2 X2
◼ Many nonlinear functions can be transformed into the above
◼ Log-linear models:
◼ Approximate discrete multidimensional probability distributions
◼ Given a set of tuples in n dimensions (e.g., described by n attributes),
consider each tuple as a point in an n-dimensional space and estimate the
probability of each point in a multi-dimensional space for a set of
discretized attributes, based on a smaller subset of dimensional
combinations . Useful for dimensionality reduction and data smoothing
34
 Histogram Analysis

◼ Divide data into buckets and

store the count for each bucket
◼ Partitioning rules:
◼ Equal-width: equal bucket
range
◼ Equal-frequency (or equal-
depth) roughly, the frequency
of each bucket is constant.
35
 Clustering
◼ Partition data set into clusters based on similarity, and
store cluster representation (e.g., centroid and diameter)
only
◼ The “quality” of a cluster may be represented by its
diameter, the maximum distance between any two
objects in the cluster.
◼ Centroid distance is an alternative measure of cluster
quality and is defined as the average distance of each
cluster object from the cluster centroid
◼ Clustering can be very effective if data is clustered but
not if data is “smeared”

36
 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 sub-linear 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:

37
 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

38
39

Sampling: With or without Replacement

Raw Data
Sampling: Cluster or Stratified Sampling

Raw Data Cluster/Stratified Sample

40
6/6/2024 Data Mining: Concepts and Techniques 41
42

Data Cube Aggregation

◼ Data cubes store multidimensional aggregated information
◼ Data cubes provide fast access to pre-computed, summarized data.
◼ The cube created at the lowest abstraction level is referred to as the base
cuboid [ex: sales, customer]
◼ A cube at the highest level of abstraction is the apex cuboid.
◼ Multiple levels of aggregation in data cubes[Cuboids]
◼ Further reduce the size of data to deal with
◼ Reference appropriate levels
◼ Use the smallest representation which is enough to solve the task
◼ Ex: data cube for multidimensional analysis of sales data with respect to
annual sales per item type for each AllElectronics branch. Each cell holds an
aggregate data value, corresponding to the data point in multidimensional
space.
Data Cube Aggregation
44

Chapter 3: Data Preprocessing

◼ Data Preprocessing: An Overview

◼ Data Quality

◼ Major Tasks in Data Preprocessing

◼ Data Cleaning

◼ Data Integration

◼ Data Reduction

◼ Data Transformation and Data Discretization

◼ Summary
45

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. Techniques include binning, regression,
and clustering
◼ Attribute/feature construction
◼ New attributes constructed from the given ones
◼ Aggregation: Summarization, data cube construction
◼ Normalization: Attribute data are scaled to fall within a smaller, specified range
such as -1.0 to 1.0, or 0.0 to 1.0
◼ Discretization: Concept hierarchy for numeric data, where the raw values of a
numeric attribute (e.g., age) are replaced by interval labels (e.g., 0–10, 11–20,
etc.) or conceptual labels (e.g., youth, adult, senior).
◼ Concept hierarchy generation for nominal data, where attributes such as street
can be generalized to higher-level concepts, like city or country.
 Data Transformation -overlap between the
major data preprocessing tasks.
• There is much Smoothing is a form of data cleaning task
• Attribute construction and aggregation are data reduction
techniques.
• Data discretization and concept hierarchy generation are also
forms of data reduction.
• If the discretization process uses class information, then we say
it is supervised discretization. Otherwise, unsupervised.
• If the process starts by first finding one or a few points (called
split points or cut points) to split the entire attribute range, and
then repeats this recursively on the resulting intervals, it is called
top-down discretization or splitting.
• bottom-up discretization or merging, which starts by considering
all of the continuous values as potential split-points, removes
some by merging neighborhood values to form intervals, and
then recursively applies this process to the resulting intervals.
 Normalization
Purpose
• The measurement unit used can affect the data analysis.
Expressing an attribute in smaller units will lead to a larger
range for that attribute, and thus tend to give such an
attribute greater effect or “weight.”
• Normalization helps prevent attributes with initially large
ranges (e.g., income) from outweighing attributes with
initially smaller ranges (e.g., binary attributes).
• Normalizing the data give all attributes an equal weight.
• Normalization is particularly useful for classification
algorithms involving neural networks or distance
measurements such as nearest-neighbour classification and
clustering.
 Normalization
◼ Min-max normalization: performs a linear transformation on
the original data.
◼ Suppose that minA and maxA are the minimum and maximum
values of an attribute, A.
◼ Min-max normalization maps a value, vi of A to vi’ in the range
[new minA,new maxA] by computing
v − minA
v' = (new _ maxA − new _ minA) + new _ minA
maxA − minA

◼ Ex. Let income range $12,000 to $98,000 normalized to

[0.0, 1.0]. Then $73,000 is mapped to
73,600 − 12,000
(1.0 − 0) + 0 = 0.716
98,000 − 12,000

48
 Normalization
◼ In z-score normalization (or zero-mean normalization), the values for an
attribute, A, are normalized based on the mean (i.e., average) and standard
deviation of A. A value, vi , of A is normalized to vi ‘ by computing
v − A
v' =
 A

(μ: mean, σ: standard deviation):

73,600 − 54,000
◼ Ex. Let μ = 54,000, σ = 16,000. Then = 1.225
16,000
◼ This method of normalization is useful when the actual minimum and
maximum of attribute A are unknown, or when there are outliers that
dominate the min-max normalization.
◼ Thus, z-score normalization using the mean absolute deviation is

◼ The mean absolute deviation, sA, is more robust to outliers than the standard
deviation. When computing the mean absolute deviation, the deviations from the
mean (i.e., |xi- xj| are not squared; hence, the effect of outliers is somewhat
reduced.
49
 Normalization
◼ Normalization by decimal scaling : normalizes by moving the
decimal point of values of attribute A.
◼ The number of decimal points moved depends on the maximum
absolute value of A. A value, vi , of A is normalized to vi’ by
computing
v
v' = j
10
Where j is the smallest integer such that Max(|ν’|) < 1

◼ Suppose that the recorded values of A range from -986 to 917. The
maximum absolute value of A is 986.
◼ To normalize by decimal scaling, we therefore divide each value by
1000 (i.e., j D 3) so that -986 normalizes to -0.986 and 917
normalizes to 0.917

50
 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 (top-down) vs. merge (bottom-up)

51
 Data Discretization Methods
◼ Typical methods: All the methods can be applied recursively
◼ Binning
◼ Top-down split, unsupervised
◼ Histogram analysis
◼ Top-down split, unsupervised
◼ Clustering analysis (unsupervised, top-down split or
bottom-up merge)
◼ Decision-tree analysis (supervised, top-down split)
◼ Correlation (e.g., 2) analysis (unsupervised, bottom-up
merge)

52
 Simple Discretization: Binning

◼ Equal-width (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

◼ Equal-depth (frequency) partitioning

◼ Divides the range into N intervals, each containing approximately
same number of samples
◼ Good data scaling
◼ Managing categorical attributes can be tricky
53
 Histogram

◼ A histogram partitions the values of an attribute, A, into

disjoint ranges called buckets or bins.
◼ In an equal-width histogram, for example, the values are
partitioned into equal-size partitions or ranges.
◼ With an equal-frequency histogram, the values are
partitioned so that, ideally, each partition contains the same
number of data tuples.

54
 Discretization by Cluster, Decision Tree,
and Correlation Analyses
◼ Clustering, decision tree analysis, and correlation analysis
can be used for data discretization.
◼ Clustering can be used to generate a concept hierarchy
for A by following either a top-down splitting strategy or a
bottom-up merging strategy, where each cluster forms a
node of the concept hierarchy.
◼ In the former, each initial cluster or partition may be
further decomposed into several subclusters, forming a
lower level of the hierarchy.
◼ In the latter, clusters are formed by repeatedly grouping
neighbouring clusters in order to form higher-level
concepts

55
 Discretization by Classification &
Correlation Analysis
◼ Classification (e.g., decision tree analysis)
◼ Supervised: Given class labels, e.g. diagnosis class, cancerous vs. benign
◼ select split-points so that a given resulting partition contains as many
tuples of the same class as possible.
◼ Top-down, recursive split
◼ Correlation analysis (e.g., Chi-merge: χ2-based discretization)
◼ Supervised: use class information
◼ Bottom-up 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

56
 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 can be explicitly specified by domain experts
and/or data warehouse designers
◼ Nominal attributes have a finite (but possibly large) number of distinct
values, with no ordering among the values. Examples include
geographic location, job category, and item type.
◼ Four methods for the generation of concept hierarchies for nominal
data

57
 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}
58
 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

country 15 distinct values

province_or_ state 365 distinct values

city 3567 distinct values

street 674,339 distinct values

59
 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

60
 OLTP vs. OLAP
OLTP OLAP
users clerk, IT professional knowledge worker
function day to day operations decision support
DB design application-oriented subject-oriented
data current, up-to-date historical,
detailed, flat relational summarized, multidimensional
isolated integrated, consolidated
usage repetitive ad-hoc
access read/write lots of scans
index/hash on prim. key
unit of work short, simple transaction complex query
# records accessed tens millions
#users thousands hundreds
DB size 100MB-GB 100GB-TB
metric transaction throughput query throughput, response

61