Module 4: Data normalization, discretization

and reduction techniques

• Data Normalization, Min-Max normalization, z-score
normalization, Decimal scaling
• Data discretization, Binning, Histogram, discretization
using data clustering techniques, discretization using
classification techniques
• Data reduction, filtering techniques, sampling
techniques, attribute subset selection techniques,
detecting outliers
Preprocessing in Data Mining
Data preprocessing is a data mining technique which is used to
transform the raw data in a useful and efficient format
 Tasks in data preprocessing

1. Data cleaning: fill in missing values, smooth noisy data, identify or remove
outliers, and resolve inconsistencies.
2. Data integration: using multiple databases, data cubes, or files.
3. Data transformation: normalization and aggregation.
4. Data reduction: reducing the volume but producing the same or similar
analytical results.
 Data cleaning

1. Fill in missing values (attribute or class value):

• Ignore the tuple: usually done when class label is missing.
• Use the attribute mean (or majority nominal value) to fill in the missing value.
• Use the attribute mean (or majority nominal value) for all samples belonging to the same class.
• Predict the missing value by using a learning algorithm: consider the attribute with the missing
value as a dependent (class) variable and run a learning algorithm (usually Bayes or decision tree)
to predict the missing value.
2. Identify outliers and smooth out noisy data:
• Binning
• Sort the attribute values and partition them into bins
• Then smooth by bin means, bin median, or bin boundaries.
• Clustering: group values in clusters and then detect and remove outliers (automatic or manual)
• Regression: smooth by fitting the data into regression functions.
3. Correct inconsistent data: use domain knowledge or expert decision.
Data Integration
• Data integration is the process of combining data from different sources into a single, unified
view.
• Integration begins with the ingestion process, and includes steps such as cleansing, ETL
mapping, and transformation
• Data integration ultimately enables analytics tools to produce effective, actionable business
intelligence.
• There is no universal approach to data integration.
• However, data integration solutions typically involve a few common elements, including a
network of data sources, a master server, and clients accessing data from the master server.
• In a typical data integration process, the client sends a request to the master server for data.
• The master server then intakes the needed data from internal and external sources.
• The data is extracted from the sources, then consolidated into a single, cohesive data set.
• This is served back to the client for use.
 Handling Redundancy in Data Integration

• Redundant data occur often when integration of multiple

databases
• Object identification: The same attribute or object may
have different names in different databases
• Derivable data: One attribute may be a “derived” attribute
in another table, e.g., annual revenue
• Redundant attributes may be able to be detected by correlation
analysis and covariance analysis
• Careful integration of the data from multiple sources may help
reduce/avoid redundancies and inconsistencies and improve
mining speed and quality
6
6
Chi square Test
• The Chi Square statistic is commonly used for testing
relationships between categorical variables. The null
hypothesis of the Chi-Square test is that no relationship exists
on the categorical variables in the population; they are
independent. An example research question that could be
answered using a Chi-Square analysis would be:
• Is there a significant relationship between voter intent and
political party membership?
How does the Chi-Square statistic work?
• The Chi-Square statistic is most commonly used to evaluate
Tests of Independence when using a crosstabulation (also
known as a bivariate table).
• Crosstabulation presents the distributions of two categorical
variables simultaneously, with the intersections of the
categories of the variables appearing in the cells of the table.
• The Test of Independence assesses whether an association exists
between the two variables by comparing the observed pattern of
responses in the cells to the pattern that would be expected if
the variables were truly independent of each other.
• Calculating the Chi-Square statistic and comparing it against a
critical value from the Chi-Square distribution allows the
researcher to assess whether the observed cell counts are
significantly different from the expected cell counts.
Correlation Analysis (Nominal Data)

• Χ2 (chi-square) test
(Observed − Expected ) 2
2 = 
Expected
• The larger the Χ2 value, the more likely the variables are related
• The cells that contribute the most to the Χ2 value are those
whose actual count is very different from the expected count
• Correlation does not imply causality
• # of hospitals and # of car-theft in a city are correlated
• Both are causally linked to the third variable: population

9
 Chi-Square Calculation: An Example

Play chess Not play chess Sum (row)

Like science fiction 250(90) 200(360) 450

Not like science fiction 50(210) 1000(840) 1050

Sum(col.) 300 1200 1500

• Χ2 (chi-square) calculation (numbers in parenthesis are expected

counts calculated based on the data distribution in the two
categories)
(250 − 90) 2 (50 − 210) 2 (200 − 360) 2 (1000 − 840) 2
 =
2
+ + + = 507.93
90 210 360 840
• It shows that like_science_fiction and play_chess are correlated
in the group
10
DATA TRANSFORMATION
 DATATRANSFORMATION
• Data must be transformed( or consolidated) to make patterns more
understandable for mining.
• Data transformation is a function that maps the entire set of values of a given
attribute to a new set of replacement values such that each old value can be
identified with one of the new values
• The different data transformation Methods are:
1. Smoothing: Remove noise from data using binning, regression, and
clustering.
2. Attribute/feature construction: New attributes constructed from the
given ones
3. Aggregation: Summarization, data cube construction. transforms a large
set of data to a smaller volume by implementing aggregation operation
on the data set.
4. Normalization: Scaled to fall within a smaller, specified range Eg: min-
max normalization, z-score normalization, normalization by decimal
scaling
5. Discretization: the raw values of a numeric attribute are replaced by
interval label or conceptual label. Concept hierarchy climbing
6. Concept hierarchy generation for nominal data: Here, attributes can be
generalized to higher level concepts
Data Normalization
Data Normalization
• The data normalization (also referred to as data pre-
processing) is a basic element of data mining.
• It means transforming the data, namely converting the
source data in to another format that allows processing data
effectively.
• The main purpose of data normalization is to minimize or
even exclude duplicated data.
• This is a very essential and important issue because it is
increasingly problematic to keep in data in relational
databases, which store identical data in more than one
place.
 Data Normalization
• Measurement unit used can affect the data analysis. Hence data are scaled to fall within a smaller range
like 0.0 to 1.0. Such transformation or mapping the data to a smaller or common range will help all
attributes to gain equal weight. This is known as Normalization.
• Methods: min-max normalization, z-score normalization, and normalization by decimal scaling.
• The normalization parameters such as mean, standard deviation, the maximum absolute value must be
preserved in order to normalize the future data uniformly.
Need of Normalization of Data

• Normalization is generally required when we are dealing with

attributes on a different scale, otherwise, it may lead to a dilution in
effectiveness of an important equally important attribute(on lower
scale) because of other attribute having values on larger scale.
• In simple words, when multiple attributes are there but attributes
have values on different scales, this may lead to poor data models
while performing data mining operations.
• So they are normalized to bring all the attributes on the same scale.
Why Normalization?
• If not normalized, one feature might completely dominate the others.
• make every datapoint have the same scale so each feature is
equally important.
• It will help to speed up the learning phase while dealing
with attributes on a different scale
• Avoid dependence on the choice of measurement units
• Comparison made easily
• The application of data mining algorithms becomes easier, effective
and efficient
• Once the data is normalized, the extraction of data from databases
becomes a lot faster.
• More specific data analyzing methods can be applied to
normalized data.
• It prevent attributes with initially large ranges (e.g., income) from
outweighing attributes with initially smaller ranges (e.g., binary
attributes)
Advantages of Normalization
• The use of data mining normalization has a number of
advantages:
1. the application of data mining algorithms becomes easier
2. the data mining algorithms get more effective and efficient
3. the data is converted in to the format that everyone can get their
heads around
4. the data can be extracted from databases faster
5. it is possible to analyze the data in a specific manner
Min-Max normalization
• Min-max normalization performs a linear transformation on the original data in
range [0, 1] or [−1, 1]. Selecting the target range depends on the nature of data.
• If 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:

• Min-max normalization preserves the relationships among the original data values.
• It encounter an “out-of-bounds” error ifa future input case for normalization
falls outside of the original data range for A.
 • It does not center the mean at 0.
• It makes the variance vary across variables.
• It may not maintain the shape of the original distribution.
• The minimum and maximum values are in the range
FEATURES of [ 0 , 1 ] .
• This method is very sensitive to outliers.
 Min-Max normalization Example
1. Let income range be from $12,000 to $98,000. Map income to the range
[0.0, 1.0](ie normalized to). By min-max normalization, a value of
$73,600 for income is transformed to

2. Given Data Employee Name Years of Experience

A 8
B 20
C 10
D 15
z-score normalization/ Feature Standardisation
• This method normalizes the value for attribute A using the mean and standard
deviation. The formula for the same is:

• Ᾱ and σA are the mean and standard deviation for attribute A respectively.
• Data can include multiple dimensions.
• Feature standardization makes the values of each feature in the data have zero-
mean (when subtracting the mean in the numerator) and unit-variance but not
normal distribution it can be still skewed.
• This method is widely used for normalization in many machine learning algorithms
(e.g., support vector machines, logistic regression, and artificial neural networks
FEATURES
• It scales the variance at 1.
• It centers the mean at 0.
• It preserves the shape of the
original distribution.
• It preserves outliers if they
exist.
• Minimum and maximum
values vary.
COMPARISON

Min-max normalization Z-score normalization

Not very well efficient in Handles the outliers in a

handling the outliers good way.

Helpful in the
Min-max Guarantees that
normalization of the data
all the features will have
but not with
the exact same scale.
the exact same scale.
Decimal scaling
• This method normalizes the value of attribute A by moving the decimal point in
the value. This movement of a decimal point depends on the maximum
absolute value of A.
The formula for the decimal scaling is:

• J is the The smallest integer j such that Max(| vi/10j|) < 1

• Number of digits in data value with largest absolute value.
 z-score normalization Example
1. Given mean and standard deviation for attribute A as $54,000 and
$16,000 respectively. Normalize the value $73,600 using z-score
normalization.
 Decimal scaling Example
1. The observed values for attribute A lie in the range from -986 to 917
and the maximum absolute value for attribute A is 986. Here,
to normalize each value of attribute A using decimal scaling, we have
to divide each value of attribute A by 1000 i.e. j=3. So, the value -
986 would get normalized to -0.986 and 917 would get normalized to
0.917.
2. The Data is: -10, 201, 301, -401, 501, 601, 701. Normalize the given data
3. GIven Data:
Employee Name Salary
A 10,000
B 25,000
C 8,000
D 15,000
 EXERCISE
• Use these methods to normalize the following group of data: 200, 300,
400, 600,1000
(a) min-max normalization by setting min D 0 and max D 1
(b) z-score normalization
(c)z-score normalization using the mean absolute deviation instead of
standard deviation
(d) normalization by decimal scaling
Data Discretization
What is data discretization?

• In data discretization we transform numeric data by mapping values to

interval concept labels.
• Such methods can be used to automatically generate concept hierarchies
for the data, which allows forming at multiple levels of granularity.
• Discretization techniques include binning, histogram analysis, cluster
analysis, decision tree analysis, and correlation analysis.
• For nominal data concept hierarchies may be generated based on schema
definitions as well as the number of distinct values per attribute.
• We can think of discretization as reducing the number of values for given
continuous attributes.
 Data discretization
• Data discretization is defined as a process of converting continuous data attribute values into a finite set of
intervals with minimal loss of information and associating with each interval some specific data value. (e.g., 0–
10, 11–20, etc.) or conceptual labels (e.g., youth, adult, senior)
• The goal of discretization is to reduce the number of values a continuous variable assumes by grouping them
into a number, b, of intervals or bins.
• Interval labels can then be used to replace actual data values. Discretization reduce data size.
• Why Discretization?
• Improves the quality of discovered knowledge
• Easy maintainability of the data
• There is a necessity to use discretized data by many DM algorithms which can only deal with discrete attributes.
• Reduces the running time of various data mining tasks such as association rule discovery, classification, and prediction
• Prepare for further analysis, e.g., classification
• Discretization is considered a data reduction mechanism because it diminishes data from a large domain of numeric values to a
subset of categorical values.
• Nature of good discretization:
• minimize information loss.
• how to select the number of intervals or bins
• how to decide on their width
 Discretization Process Table: Before discretization

• Assuming a dataset S consisting of N examples, M Age 10,11,13,14,17,19,30, 31, 32, 38, 40, 42,70 , 72, 73, 75

attributes, and c class labels, a discretization scheme.

• DAwould exist on the continuous attribute A ЄM,
which partitions this attribute into k discrete and
disjoint intervals, where d0 and dkA are, respectively, Table: After discretization
the minimum and maximal value, and represents the
set of cut points of A in ascending
order.{|d0d1|,|d1d2|,|d3d4|,….|dka-1 dkA|} Attribute Age Age Age
STEPS OF DISCRETIZATION 10,11,13,14,17, 30, 31, 32, 38, 40,
70 , 72, 73, 75
19, 42
1. Sorting the continuous values of the feature to be
discretized, After
Discretizati Young Mature Old
2. Evaluating a cut point for splitting or adjacent on
intervals for merging,
3. Splitting or merging intervals of continuous values
according to some defined criterion.
4. Stopping at some point.
DATA
DISCRETI
ZATION
TYPES
 Data discretization Types
• Discretization can be performed with or without taking class information, if available, into account. These are
the supervised and unsupervised ways
• Unsupervised discretization methods are not provided with class label informatio. Eg: Equal-width
discretization, Equal-frequency discretization, K-means discretization supervised discretization methods are
supplied with a class label for each data item value. Eg: Entropy based, Decision Trees
• Both unsupervised and supervised discretization methods can be further subdivided into top-down(split) and
bottom-up(merge) methods.
• A top-down method starts with a single interval that includes all data attribute values and then generates a set
of intervals by splitting the initial interval into two or more intervals. Splitting Algorithm consists of 4 steps. 1)
Sort the feature values. 2)Search for a suitable cut point 3) split the range of continuous values according to cut
point 4) Stop when criteria is satisfied
• A bottom-up method initially considers each data point as a separate interval. It then selects one or more
adjacent data points merging them into a new interval. If the process starts by considering all of the continuous
values as potential split-points, removes some by merging neighborhood values to form intervals, then it is
called bottom-up discretization or merging.
• Discretization can be performed rapidly on an attribute to provide a hierarchical partitioning of the attribute
values, known as a concept hierarchy.
• Concept hierarchies can be used to reduce the data by collecting and replacing low-level concepts with higher-
level concepts. Data mining on a reduced data set means fewer input/output operations and is more efficient
than mining on a larger data set.
• discretization techniques and concept hierarchies are typically applied before data mining, rather than during
mining.
Data discretization Types
Equal-width Discretization
• The most simple form of discretization that
divides the range of possible values into N bins
of the same width.
• The width of intervals is determined by the
following formula:
• where N is the number of bins or intervals, this
parameter is something to determine
experimentally—there’s no rule of thumb here.
Example: if the variable interval is [100, 200], and
we want to create 5 bins, that means 200-100 / 5 =
20, so each bin’s width is 20, and the intervals will
be [100, 120], [120, 140],…,[180,200]
• Equal-width discretization does not improve the
values spread.
• This method handles outliers.
Data discretization Types
Equal-Frequency Discretization
• Equal-frequency discretization divides the scope
of possible values of the variable into N bins,
where each bin holds the same number (or
approximately the same number) of
observations..
• the interval boundaries correspond to the
quantiles.
• This method improves the value spread.
• Equal-frequency handles outliers.
Methods of Data Discretization
 Data Discretization Typical Methods
• All the methods can be applied recursively.
1. Binning
• Binning is a top-down splitting technique based on a specified number of bins. Binning is an
unsupervised discretization technique. Main challenge in discretization is to choose the
number of intervals or bins and how to decide on their width.
2. Histogram Analysis
• It is a Top-down split. Since histogram analysis does not use class information so it is an
unsupervised discretization technique. Histograms partition the values for an attribute into
disjoint ranges called buckets.
3. Cluster Analysis
• Cluster analysis is a unsupervised method which can be top-down split or bottom-up merge. A
clustering algorithm can be applied to discrete a numerical attribute of A by partitioning the
values of A into clusters or groups. Each initial cluster or partition may be further decomposed
into several subcultures, forming a lower level of the hierarchy. Detect and remove outliers
4. Decision-tree analysis (supervised, top-down split)
5. Correlation (e.g. chi merge) analysis (unsupervised, bottom-up merge)
 Binning

• Binning methods smooth a sorted data value by consulting

its “neighborhood,” that is, the values around it. The sorted values
are distributed into a number of “buckets,” or bins. Because binning
methods consult the neighborhood of values, they perform
local smoothing
• Attribute values can be discretized by applying equal-width or equal-
frequency binning, and then replacing each bin value by the bin mean or
median, as in smoothing by bin means or smoothing by bin medians,
respectively.
• Binning does not use class information and is therefore an unsupervised
discretization technique. It is sensitive to the user-specified number of
bins, as well as the presence of outliers.
 Binning Methods for DataSmoothing
• Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
1. Partition into equal-frequency (equi-depth) bins: of size 4
• Bin 1: 4, 8, 9, 15
• Bin 2: 21, 21, 24, 25
• Bin 3: 26, 28, 29, 34
2. Smoothing by bin means: each value in a bin is replaced by the mean value of the bin.
• Bin 1: 9, 9, 9, 9
• Bin 2: 23, 23, 23, 23
• Bin 3: 29, 29, 29, 29
3. Smoothing by bin boundaries: The minimum and maximum values in a given bin are
identified as the bin boundaries. Each bin value is then replaced by the closest
boundary value. In general, the larger the width, the greater the effect of the
smoothing.
• Bin 1: 4, 4, 4, 15
• Bin 2: 21, 21, 25, 25
• Bin 3: 26, 26, 26, 34
4. Smoothing by bin medians : each bin value is replaced by the bin median.
Entropy Based Binning

•Given Data. Discretize the

temperature variable using
entropy-based
binning algorithm
ENTROPY BASED BINNING
O-Ring Failure
Y N
• Calculate "Entropy" for the target. 7 17

• E (Failure) = E(7, 17) = E(0.29, .71) = -0.29 x log2(0.29) - 0.71 x log2(0.71)

= 0.871
O-Ring Failure
• Calculate "Entropy" for the target given a bin Y N
<= 60 3 0
Temperature
> 60 4 17
• E (Failure,Temperature) = P(<=60) x E(3,0) + P(>60) x E(4,17) = 3/24 x 0 +
21/24 x 0.7= 0.615
• Calculate "Information Gain" given a bin.
• Information Gain (Failure, Temperature) =0.871-0.615= 0.256
FINAL

The information gains for

all three bins show that the
best interval for
"Temperature" is (<=60,
>60) because it returns the
highest gain.
Data discretization using Histogram Analysis
Histogram
• Meaning
• Histos- Pole or Mast
• Gram- chart
• Chart of Pole
• Graphical Method to summarize distribution of given attributes X
• X nominal attributes ex model, item_type etc.
• Pole or vertical bar is drawn on each value of X
• Height of the bar → frequency of that X value.
• The range of value of X → Disjoint consecutive subranges
• Subrange →Bins/Buckets.
• Buckets→Width
• Resulting graph is known as a bar chart
• Example: Range of Marks → 0-100. Subranges: 0-40,40-45,45-60,60-75,75-100
 Histogram Analysis
• Divide data into buckets and store
40
35
average (sum) for each bucket
30

• Partitioning rules: 25
20
• Equal-width: equal bucket
15
range 10

• Equal-frequency (or equal- 5

0
depth) 10000 30000 50000 70000 90000

46
Discretization using Histogram Analysis
• Similar to Binning
• Unsupervised Discretization Technique because does not use class
information
• Partition the value of attributes into disjoint range called buckets/bins
• Partitioning Rules:
• Equal Width
• Equal Frequency
• Concept of Hierarchy
Partitioning Rules
• How bucket determined and the attribute value partitioned?
• Equal width: Width of each bucket is uniform
• Equal Frequency: the buckets are created , keep in mind the
frequency of each bucket is constant. ([Link] bucket contains roughly
same number of contiguous data samples).
Hierarchy Representation
• organizational structure or mapping in which items are ranked
according to their levels of importance
OR ,
• hierarchy concept refers to a sequence of mappings with a set of
more general concepts to complex concepts.

• mapping is done from low-level concepts to high-level concepts.

Example- Computer Model
• Computer science, there are different types of hierarchical systems
• A document is placed in a folder in windows at a specific place in the
tree structure is the best example of a computer hierarchical tree
model.
Example - City
• New Delhi can be mapped to India, and India can be mapped to Asia.
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.

52
 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}
53
 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

54
Hierarchical Representation
Types of Mapping
• Top Down
• Bottom Up
Top-down mapping

• Top-down mapping generally starts with the top with some general
information and ends with the bottom to the specialized information.
Bottom-up mapping

• Bottom-up mapping generally starts with the bottom with some

specialized information and ends with the top to the generalized
information.
Data discretization and binarization in data mining

• Data discretization is a method of converting attributes values of

continuous data into a finite set of intervals with minimum data loss.
In contrast, data binarization is used to transform the continuous and
discrete attributes into binary attributes.
Discretization using data clustering techniques
Discretization using data clustering techniques

• Cluster analysis is a popular data discretization method.

• A clustering algorithm can be applied to discretize a numeric
attribute, A, by partitioning the values of A into clusters or
groups based on similarity, and store cluster representation
(e.g., centroid and diameter) only
• Partition data set into clusters
• There are many choices of clustering definitions and
clustering algorithms. Eg: K-Means and K-Medoid algorithm
• properties of clusters
• All the data points in a cluster should be similar to each other.
• The data points from different clusters should be as different as
possible
Different Evaluation Metrics for Clustering
• Property 1-inertia calculates the sum of distances of
all the points within a cluster from the centroid of that
cluster. This distance within the clusters is known
as intracluster distance. So, inertia gives us the sum of
intracluster distances. the lesser the inertia value, the
better our clusters are.
• Property 2-Dunn index. The distance between the
centroids of two different clusters is known as inter-
cluster distance. Dunn index is the ratio of the
minimum of inter-cluster distances and maximum of
intracluster [Link] the Dunn index. The
more the value of the Dunn index, the better will be the
clusters
K-Means
Clustering
Algorithm

• A cluster refers to a collection of data points aggregated together because of certain similarities.
• K-mean algorithm is one of the centroid based technique. it is also referred to as Lloyd's algorithm.
• K means algorithm takes the unlabeled dataset as input, divides the dataset into k-number of clusters,
and repeats the process until it does not find the best clusters without the need for any training.
• K refers to the number of pre-defined clusters that need to be created in the process, as if K=2, there
will be two clusters, and for K=3, there will be three clusters.
• Each cluster is associated with a centroid and algorithm aims to minimize the sum of distances
between the data point and their corresponding cluster centroids.
K-Means Algorithm Steps
1. Select the number K to decide the number of
clusters. K can be determined using some
techniques like Elbow Method using WCSS(Within
Cluster Sum of Squares), Silhouette Method.
2. Compute random seed points as the centroids or
K points of the clusters of the current partitioning
( A centroid is the imaginary or real location
representing the center of the cluster or mean
point of the cluster .)
3. Assign each object to the cluster with the nearest
seed point based on eulidean distance. Using a
different distance function other than (squared)
Euclidean distance may prevent the algorithm
from converging. Partition objects
into k nonempty subsets by seeing
the closest centroids for each data points.
4. Calculate the variance and place a new centroid of
each cluster based on mean value of the cluster.
Better choice is to place them as much as possible
far away from each other
5. Go back to Step 3, stop when the assignment does
choose the value of "K number of clusters" inK-
means Clustering
• WCSS=∑Pi in Cluster1 distance(Pi C1)2 +∑Piin Cluster2distance(Pi C2)2+∑Pi in
CLuster3 distance(Pi C3)
2

• ∑Pi in Cluster1 distance(Pi C1)2: It is the sum of the square of the distances
between each data point and its centroid within a cluster1 and the
same for the other two terms.
• To find the optimal value of clusters, the elbow method follows the
below steps:
• It executes the K-means clustering on a given dataset for different K
values (ranges from 1-10).
• For each value of K, calculates the WCSS value.
• Plots a curve between calculated WCSS values and the number of
clusters K.
• The sharp point of bend or a point of the plot looks like an arm, then
that point is considered as the best value of K.
 Stopping Criteria for
K-Means Clustering

• There are essentially three stopping criteria that can

be adopted to stop the K-means algorithm:
1. Centroids of newly formed clusters do not change
2. Points remain in the same cluster
3. Maximum number of iterations are reached
 EXAMPLE

• Apply k-means clustering algorithm

and euclidean distance to cluster the
following 1 dimensional data set {2, 4,
10, 12, 3, 20, 30, 11, 25} into 2
clusters with initial means as M1= 4,
M2=11
EXAMPLE
• Apply k-means clustering algorithm and euclidean
distance to cluster the following 1 dimensional data
set {2, 4, 10, 12, 3, 20, 30, 11, 25} into 2 clusters
Iteration 1
• M1, M2 are the two randomly selected centroids/means
where M1= 4, M2=11
• Calculate the Euclidean distance as D=[x,a]=√(x-a)²
• D1 is the distance from M1 andD2 is the distance from
M2
• initial clusters are C1= {2, 4, 3} C2= {10, 12, 20, 30, 11, 25}
 EXAMPLE
Iteration 2
• Calculate new mean of datapoints in C1 and C2. M1=
(2+3+4)/3= 3 and M2= (10+12+20+30+11+25)/6= 18. New
Clusters C1= {2, 3, 4, 10} and C2= {12, 20, 30, 11, 25}
Iteration 3
• Calculate new mean of datapoints in C1 and C2.
• M1= (2+3+4+10)/4= 4.75 and M2= (12+20+30+11+25)/5= 19.6
• New Clusters C1= {2, 3, 4, 10, 12, 11} and C2= {20, 30, 25}
Iteration 4
• Calculate new mean of datapoints in C1 and C2.
• M1= (2+3+4+10+12+11)/6=7 and M2= (20+30+25)/3= 25
• New Clusters C1= {2, 3, 4, 10, 12, 11} and C2= {20, 30, 25}
 • Use the k-means algorithm and Euclidean
distance to cluster the following 8 examples into
3 clusters: A1=(2,10), A2=(2,5), A3=(8,4),
A4=(5,8), A5=(7,5), A6=(6,4), A7=(1,2),
A8=(4,9). Run the k-means algorithm for 3 epoch/
CHALLENGE iteration. Let seed1=A1=(2,10), seed2=A4=(5,8),
seed3=A7=(1,2)
SOLUTION
• Let seed1=A1=(2,10), seed2=A4=(5,8), seed3=A7=(1,2)
Data Point Value D1(2,10) D2(5,8) D3(1,2) Cluster
A1 (2,10) 0 √13 √65 C1
A2 (2,5) √25 √18 √10 C3
A3 (8,4) √36 √25 √53 C2
A4 (5,8) √13 0 √52 C2
A5 (7,5) √50 √13 √45 C2
A6 (6,4) √52 √17 √29 C2
A7 (1,2) √65 √52 0 C3
A8 (4,9) √5 √2 √58 C2
• new clusters: 1: {A1}, 2: {A3, A4, A5, A6, A8}, 3: {A2, A7}
• Centroid 1=(2,10) Centroid 2 = = ((8+5+7+6+4)/5, (4+8+5+4+9)/5) = (6, 6)
Centroid 3= ((2+1)/2, (5+2)/2) = (1.5, 3.5)
SOLUTION
• Iteration 2

Data Point Value D1 (2,10) D2(6, 6) D3(1.5, 3.5) Cluster

A1 (2,10) 0 √32 √65 C1
A2 (2,5) √25 √18 √10 C3
A3 (8,4) √36 √25 √53 C2
A4 (5,8) √13 0 √52 C2
A5 (7,5) √50 √13 √45 C2
A6 (6,4) √52 √17 √29 C2
A7 (1,2) √65 √52 0 C3
A8 (4,9) √5 √2 √58 C2
• New Clusters : 1: {A1, A8}, 2: {A3, A4, A5, A6}, 3: {A2, A7}
• centroids C1=(3, 9.5), C2=(6.5, 5.25) and C3=(1.5, 3.5). After the 3rd epoch, the results would be: 1: {A1, A4,
A8}, 2: {A3, A5, A6}, 3: {A2, A7} with centers C1=(3.66, 9), C2=(7, 4.33) and C3=(1.5, 3.5).
SOLUTION
• Iteration 3
Data Point Value D1 D2 D3 Cluster
A1 (2,10) 0 √13 √65 C1
A2 (2,5) √25 √18 √10 C3
A3 (8,4) √36 √25 √53 C2
A4 (5,8) √13 0 √52 C2
A5 (7,5) √50 √13 √45 C2
A6 (6,4) √52 √17 √29 C2
A7 (1,2) √65 √52 0 C3
A8 (4,9) √5 √2 √58 C2

• New Clusters : 1 1: {A1, A4, A8}, 2: {A3, A5, A6}, 3: {A2, A7}
• centroids C1=(3.66, 9), C2=(7, 4.33) and C3=(1.5, 3.5).
Advantagesand Disadvantagesof K-
Means Clustering

ADVANTAGES
• It is very simple to implement.
• It is scalable to a huge data set and also faster to large datasets.
• it adapts the new examples very frequently.
• Generalization of clusters for different shapes and sizes.
DISADVANTAGES
• Slow for large number of samples: As this algorithm access each point of the dataset, it becomes slow when the sample size
grows.
• The k-means algorithm is sensitive to outliers ! Since an object with an extremely large value may substantially distort the
distribution of the data
• Value of K need to be specified beforehand. Choosing the k values manually is a tough job.
• As the number of dimensions increases its scalability decreases.
• It is not suitable to identify clusters with non-convex shapes.
 KMedoid
• A medoid can be defined as the point in the cluster, whose dissimilarities with all
the other points in the cluster is minimum. Tthat is, it is a most centrally located
point in the cluster.
• PAM -Partitioning Around Medoids( Kaufmann & Rousseeuw 1987)
• Splits the data set of n objects into k clusters, where the number k of clusters
assumed known a priori (which implies that the programmer must specify)
• Starts from an initial set of medoids and iteratively replaces one of the medoids
by one of the non-medoids if it improves the total distance of the resulting
clustering
• PAM works effectively for small data sets, but does not scale well for large data
sets.
• The dissimilarity of the medoid(Ci) and o b j e c t ( P i ) is calculated by using E =
|Pi - Ci|
• The runtime complexity of the original PAM algorithm per iteration of is O(k(n-
k)2)
ALGORITHM
Build phase:
1. Select k objects to become the medoids, or in
case these objects were provided use them as
the medoids;
2. Calculate the dissimilarity matrix if it was not
provided;
3. Assign every object to its closest medoid;
Swap phase:
4. For each cluster compute the disatnce between
the non-medoid data point o and medoid m.
5. Consider the swap of m and o, and compute the
cost change. See if it decreases the average
dissimilarity coefficient; if it does, select
the entity that decreases this coefficient
6. If the cost change is the current best, remember
this m and o combination
• Medoid process is continued until no any medoid
move
 EXAMPLE X Y
2 6

3 4

3 8
• Cluster the given data set of
ten objects into two clusters 4 7
i.e. k= 2. Let the initial
medoids be (3,4) and (7,4) 6 2

6 4

7 3

7 4

8 5

7 6
EXAMPLE
• Cluster the given data set of ten objects into two clusters i.e. k= 2. Let
the initial medoids be (3,4) and (7,4)
x y D1(3,4) D2(7,4) Cluster Cluster1 = {(3,4) (2,6) (3,8)
2 6 3 7 C1 (4,7
Cluster2 = {(7,4) (6,2) (6,4)
3 4 0 4 C1 (7,3 1]
3 8 4 8 C1
4 7 4 6 C1 Cost (Distance)
=3+0+4+4+3+1+1+0+2+2
6 2 5 3 C2 =20
6 4 3 1 C2
7 3 5 1 C2
7 4 4 0 C2
8 5 6 2 C2
7 6 6 2 C2
EXAMPLE
• Let the new medoid O' be (7,3). So new medoids are (3,4) and (7,3)

x y D1(3,4) D2(7,3) Cluster Cluster1 = {(3,4) (2,6) (3,8)

2 6 3 8 C1 (4,7
Cluster2 = {(7,4) (6,2) (6,4)
3 4 0 5 C1 (7,3 1]
3 8 4 9 C1
4 7 4 7 C1 Cost (Distance)
=3+0+4+4+2+2+0+1+3+4
6 2 5 2 C2 =22
6 4 3 2 C2
7 3 5 0 C2
7 4 4 1 C2
8 5 6 3 C2
7 6 6 4 C2
 EXAMPLE

Let the randomly selected 2 medoids, so select k = 2 and let C1 -(4, 5) and C2 -
(8, 5) are the two medoids.
 EXAMPLE

Let the randomly selected point be (8, 4). The

The points 1, 2, 5 go to cluster C1 and 0, 3, 6, 7, 8 go to
dissimilarity of each non-medoid point with the
cluster [Link] Cost = (3 + 4 + 4) + ( 2 + 2+3 + 1 + 1 ) = 20
medoids – C1 (4, 5) and C2 (8, 4) is calculated
and tabulated.
EXAMPLE
• Each point is assigned to that
cluster whose dissimilarity is less.
So, the points 1 , 2 , 5 go to
cluster C1 and 0 , 3 , 6 , 7 ,
8 go to cluster C2.
The New cost = ( 3 + 4 + 4 )
+ (2 + 2 + 1 + 3 + 3) =
22
Swap Cost = New Cost –
Previous Cost = 22 – 20
and 2 >0
• As the swap cost is not less than
zero, we undo the swap.
Hence ( 3 , 4 ) and ( 7 , 4 ) are
the final medoids.
Advantagesand Disadvantagesof K-
Medoid Clustering

Advantages:
• It is simple to understand and easy to implement.
• K-Medoid Algorithm is fast and converges in a fixed number of steps.
• PAM is less sensitive to outliers than other partitioning algorithms.
Disadvantages:
• The main disadvantage of K-Medoid algorithms is that it is not suitable for clustering non-
spherical (arbitrary shaped) groups of objects. This is because it relies on minimizing the
distances between the non-medoid objects and the medoid (the cluster centre) – briefly, it
uses compactness as clustering criteria instead of connectivity.
• It may obtain different results for different runs on the same dataset because the first k
medoids are chosen randomly.
 Given Datapoints:
{2,4,10,12,3,20,30,11,25}
Challenge and Cluster number : 2.
Apply K-Means and K-
Medoid Algorithm
 k-mean k-medoid
• Datapoints: {2,4,10,12,3,20,30,11,25} • Given data points: {2, 4, 10, 12, 3, 20, 30, 11, 25}
• Cluster number : 2. Initila centroids 2 and 3 • Number of clusters k=2 . Initial medoids 2 and 3
• Step 1: Value of clusters K1{ 2 } K2{ 3 6 8 12 • Step: 1: {2} {3 6 8 12 15 18 22 25} C: 2&3：S=85
15 18 22 25 } • Step: 2: {2 3 } {6 8 12 15 18 22 25} C:2 &6：S=65
•Centroid m1 and m2 : mean values • Step: 3: {2 3} {8 6 12 15 18 22 25} C:2&8：S=55
m1=2.0 m2=13.625 . Distance: • Step: 4: {2 3 6} {12 8 15 18 22 25} C:2&12：S= 41
• Step 2: Value of clusters K1 {2 3 6} K2 {8 12 15 • Step: 5: {2 3 6 8} {15 12 18 22 25} C:2 &18：S=31
• 18 22 25} Value of m m1=3.66 m2=16.66 • Step: 6: {2 3 6 8} {18 12 15 22 25 } C:2 & 15: S=34.
Stop Iteration as cost increases
• Step 3: Value of clusters K1 {2 3 6 8 } K2 {12
15 18 22 25} Value of m m1=4.75 m2=18.4 • Step: 7: The final clusters by K-Medoids are as
• Step 4: Value of clusters K1 {2 3 6 8 } K2 {12 follows: {2 3 6 8} {18 12 15 22 25}
• 15 18 22 25} Value of m m1=4.75 m2=18.4
• Step 5: The final clusters by K-means are as
follows: K1 {2 3 6 8 } K2 {12 15 18 22 25}
 k-mean k-medoid
1. In K-means, the center of a cluster is not 1. In K-medoids chooses actual data points as centers
necessarily one of the input data points . It (medoids or exemplars), which are
is the average/mean between the points in selected randomly and thereby allows for greater
the cluster/data to compute centroid. interpretability of the cluster centers. remaining all
data objects are placed in a cluster having medoid
2. K-means generally requires Euclidean nearest (or most similar) to that data object
distance for efficient solutions.
2. K-medoids can be used with arbitrary dissimilarity
3. Tries to minimize total squared distance or
measures, because k-medoids minimizes a sum of
error pairwise dissimilarities instead of a sum of squared
4. Less robust to noise and outliers Euclidean distances
3. Tries to minimize the absolute distance between
the points and the selected centroid(sum
of dissimilarities between points labeled to be in a
cluster and a point designated as the center of that
cluster)
4. more robust to noise and outliers
Discretization using classification techniques
Discretization using classification techniques
• Classification is one of the important tasks in Data Mining or
Knowledge Discovery with prolific applications.
• Satisfactory classification depends on characteristics of the
dataset too.
• Numerical and nominal attributes are commonly occurred in
the dataset.
• However, classification performance may be aided by
discretization of numerical attributes.
• At present, several discretization methods and numerous
techniques for implementing classifiers exist.
Objective behind Discretization
Classification Technique
• First is to study the effectiveness of discretization of attributes,
• Second is to compare the efficiency of eight discretization methods.
• Methods:
1. ChiMerge
2. Chi2
3. Modified Chi2
4. , Extended Chi2,
5. Class-Attribute Interdependence Maximization (CAIM),
6. Class-Attribute Contingency Coefficient (CACC),
7. Autonomous Discretization Algorithm (Ameva),
8. Minimum Description Length Principle (MDLP).
• Third objective is the study investigates suitability of the eight
discretization methods when applied to the five commonly known
classifiers, Neural Network, K Nearest Neighbour (K-NN), Naive
Bayes, C4.5, and Support Vector machine (SVM).
Data Reduction Techniques
 Data Reduction Strategies

• Data reduction: Obtain a reduced representation of the data set that is much
smaller in volume but yet produces the same (or almost the same) analytical
results
• Why data reduction? — A database/data warehouse may store terabytes of
data. Complex data analysis may take a very long time to run on the complete
data set.
• Data reduction strategies
• Dimensionality reduction, e.g., remove unimportant attributes
• Wavelet transforms
• Principal Components Analysis (PCA)
• Feature subset selection, feature creation
• Numerosity reduction (some simply call it: Data Reduction)
• Regression and Log-Linear Models
• Histograms, clustering, sampling
• Data cube aggregation
91
• Data compression
Data Reduction 1: Dimensionality Reduction
• Curse of dimensionality
• When dimensionality increases, data becomes increasingly sparse
• Density and distance between points, which is critical to clustering, outlier
analysis, becomes less meaningful
• The possible combinations of subspaces will grow exponentially
• Dimensionality reduction
• Avoid the curse of dimensionality
• Help eliminate irrelevant features and reduce noise
• Reduce time and space required in data mining
• Allow easier visualization
• Dimensionality reduction techniques
• Wavelet transforms
• Principal Component Analysis
• Supervised and nonlinear techniques (e.g., feature selection)

92
Mapping Data to a New Space
◼ Fourier transform
◼ Wavelet transform

Two Sine Waves Two Sine Waves + Noise Frequency

93
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

94
Wavelet Transformation
Haar2 Daubechie4
• Discrete wavelet transform (DWT) for linear signal processing,
multi-resolution analysis
• Compressed approximation: store only a small fraction of the
strongest of the wavelet coefficients
• Similar to discrete Fourier transform (DFT), but better lossy
compression, localized in space
• Method:
• Length, L, must be an integer power of 2 (padding with 0’s, when
necessary)
• Each transform has 2 functions: smoothing, difference
• Applies to pairs of data, resulting in two set of data of length L/2
• Applies two functions recursively, until reaches the desired length

95
Wavelet Decomposition
• Wavelets: A math tool for space-efficient hierarchical decomposition of functions
• S = [2, 2, 0, 2, 3, 5, 4, 4] can be transformed to S^ = [23/4, -11/4, 1/2, 0, 0, -1, -1, 0]
• Compression: many small detail coefficients can be replaced by 0’s, and only the
significant coefficients are retained

96
Haar Wavelet Coefficients Coefficient “Supports”
Hierarchical
2.75
2.75 +
decomposition
structure (a.k.a. + -1.25 + -
“error tree”) + -1.25
-
0.5 0
0.5 + -
+ - + - 0 + -
0 -1 -1 0
+
- + - + - + -
0 + -
2 2 0 2 3 5 4 4 -1 + -
-1 + -
Original frequency distribution 0 + -
97
Why Wavelet Transform?
• Use hat-shape filters
• Emphasize region where points cluster
• Suppress weaker information in their boundaries
• Effective removal of outliers
• Insensitive to noise, insensitive to input order
• Multi-resolution
• Detect arbitrary shaped clusters at different scales
• Efficient
• Complexity O(N)
• Only applicable to low dimensional data

98
 Principal Component Analysis (PCA)

• Find a projection that captures the largest amount of variation in data

• The original data are projected onto a much smaller space, resulting in
dimensionality reduction. We find the eigenvectors of the covariance matrix,
and these eigenvectors define the new space

x2

x1
99
 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

100
Data Filtering
Data Filtering
• Data filtering is the process of choosing a smaller part of your data set
and using that subset for viewing or analysis.
• Filtering is generally (but not always) temporary – the complete data
set is kept, but only part of it is used for the calculation.
Data filtering-noise removal
• It is the process of getting rid of noise such as outlier values and error
data from raw data to make the data clean and be proper for further
processing.
• Example , In the process of weather forecast, there will be collecting a
large amount of data as data will be collected every day or every three
hours.
General Used of Filtering
• Look at results for a particular period of time.

• Calculate results for particular groups of interest.

• Exclude erroneous or "bad" observations from an analysis.

• Train and validate statistical models.

Needs of Filtering Data
• In a large size of database, normally there will be incomplete data.
• The incomplete data may be outlier values or error data.
• Hence, data filtering will be needed for the pre-processing of data.
• Additionally, the experimental results will get more accuracy if the
data is clean. Its observed that in different research experiments that
filtered data gave higher accuracy than the non-filtered data.
• Example of using such work is in the breast cancer database, the
pima-indians-diabetes, and the heart disease of the ECG Rhythm
classification using neural network .
Filtering Data Requirements
• Filtering requires you to specify a rule or logic to identify the cases
you want to included in your analysis.

• Filtering can also be referred to as “subsetting” data, or a data “drill-

down”.
Example of filtering

• The table below shows some of the rows of a data set from a survey
about peoples’ preferred Cola.

• The survey data contains demographic information about the

respondents as well as each person’s preferred cola and that person’s
rating (out of 5) for each of six varieties of cola.
 Process of Filtering Data
• Coming up with a rule for the observations needed.

• Selecting the observations that fit the rule.

• Conducting the analysis using only the information contained in those selected
observations.

• For example, the table below show the data filtered for Males only.

• The darker colored rows are kept in the analysis while the remaining rows are
excluded.

• Results computed for Males are then calculated based on the highlighted rows
(ID’s 2, 9, 11, 12, 13, 14).

• If we want to know the average rating for Coca-Cola among males, we would
compute that as (5 + 5 + 4 + 5 + 5 + 3) / 6 = 4.5.
Results for different groups

• A basic need for most research is to obtain results for different groups
in the data.

• One may want to ask about the prevalence of a disease within a

demographic segment of the overall population, understand sales
figures for the past 3 months, or view feedback given by customers
who gave your restaurant 1 star on Yelp.

• In each case, a logical rule defines whether each case in the sample is
excluded or included.
Example Filtering Transform Results
• From the example above, we may wish to compute the average
rating for each beverage within for the Males in the sample.
Such filtering transforms the results like this:
Data Filtering Techniques
• Moving average filtering
• Local regression filtering
• Savitzky- Golay filtering
• Hamming window filtering
Method 1: Moving average filtering
• Moving average filtering is a simple data filtering technique by
calculating the average value of every point in the selected window.

• where (yk)s is the filtered data

(smoothing) at point k,
• yk is the data at point k (before
smoothing),
• n is a number of points in each side
(left side or right side), and –n ≤ i ≤ n.
The window size equals to 2n+1.
Data Filtering: Moving Average
Method 2- Local regression filtering
• It uses the method of regression analysis.

• This filtering technique will specify weight for every data point
• Here window selected by using regression weight function. Given in Eq.
• wi is regression weight of points i,
• x is the predictor value associated with the response value to be smooth,
• xi are the nearest neighbors of x as defined by the selected window, and
• d(x) is the distance along the abscissa from x to the most distant predictor value
within the selected window.
Types of Local regression filtering
1. lowess local regression: uses the method of linear regression
analysis.
2. loess local regression: uses the method of polynomial square
regression analysis
3. rlowess local regression: This method the robust function can be
used to get rid of outlier values. It can be applied with lowess local
regression and
4. rloess local regression: which applied to loess local regression.
additionally , robust function can be used to get rid of outlier
values.
Method 3- Savitzky-Golay filtering
• Data filtering techniques - a characteristic of frequency-wave.
• This technique uses the simple polynomial least–square calculation,
which will not filter too many details out of the data.
• The control parameters are the size of the window and the
polynomial degree.
• Here the size of window has higher value than the polynomial degree.
Formula for calculation of filtered Data
Parameters used for Savitzky-Golay filtering
• (yk)s is the filtered data (smoothing) at point k,
• yk is the data at the point k (before smoothing),
• n is a number of positions of points in each side (left side or right
side), –n ≤ i ≤ n,
• Ai is the value of coefficient weight at position i.
Usage of this Filtering Method
• .This filtering technique has been applied in many fields such as
decreasing noise in ultra sound image, radar image and etc.
Method 4- Hamming window filtering
• It is the data filtering technique that uses signal processing technique.
• It is a method for frequency filtering of finite impulse response .

ˆh k is a new filtered data,

h(k) is an old data, and
w(k) is the window function
 Hamming Window- Window Function
• The window function is used to improve the range of response for
transition as shows in equation:

here w(k) is the window function, k is a value of data at point k, and K is a number
of data points of the window function.
Sampling
 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:
• Note: Sampling may not reduce database I/Os (page at a time)
124
 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

125
Sampling: With or without Replacement

Raw Data
126
Sampling: Cluster or Stratified Sampling

Raw Data Cluster/Stratified Sample

127
Attribute Subset Selection
Techniques
Attribute Subset Selection Techniques
• Attribute subset Selection is a technique which is used for data
reduction in data mining process.
• Data reduction reduces the size of data so that it can be used for
analysis purposes more efficiently.
Need of Attribute Subset Selection
• The data set may have a large number of attributes. But some of
those attributes can be irrelevant or redundant.
• The goal of attribute subset selection is to find a minimum set of
attributes such that dropping of those irrelevant attributes does not
much affect the utility of data and the cost of data analysis could be
reduced.
• Mining on a reduced data set also makes the discovered pattern
easier to understand.
Process of Attribute Subset Selection-
• The brute force approach can be very expensive in which each subset (2^n
possible subsets) of the data having n attributes can be analysed.
• The best way to do the task is to use the statistical significance tests such
that best (or worst) attributes can be recognized.
• Statistical significance test assumes that attributes are independent of one
another.
• This is a kind of greedy approach in which a significance level is decided
(statistically ideal value of significance level is 5%) and the models are
tested again and again until p-value (probability value) of all attributes is
less than or equal to the selected significance level.
• The attributes having p-value higher than significance level are discarded.
• This procedure is repeated again and again until all the attribute in data set
has p-value less than or equal to the significance level.
• This gives us the reduced data set having no irrelevant attributes.
Methods of Attribute Subset Selection-
1. Stepwise Forward Selection.
2. Stepwise Backward Elimination.
3. Combination of Forward Selection and Backward Elimination.
4. Decision Tree Induction.

• All the above methods are greedy approaches for attribute subset
selection.
Features of Methods
• These methods are usually greedy in that while searching
through attribute space, they always create what looks to be the
better choice at the time. Their strategy is to make a locally
optimal choice in the hope that this will lead to a globally optimal
solution. Such greedy approaches are efficient in practice and
can come close to estimating an optimal solution.
• The best and worst attributes are generally determined using
tests of statistical significance, which consider that the attributes
are separate from one another. Some other attribute evaluation
measures can be used, including the information gain measure
used in building decision trees for classification.
Stepwise Forward Selection:
The process starts with a null set of attributes as the reduced set.

The best of the original attributes is determined and added to the

reduced set.

At every subsequent iteration or step, the best of the remaining

original attributes is inserted into the set.
Stepwise Backward Elimination
The procedure starts with the full set of attributes.
At each step, it removes the worst attribute remaining in the set.
Combination of Forward Selection and
Backward Elimination:

• The stepwise forward selection and backward elimination

methods can be connected so that, at each step, the procedure
chooses the best attribute and eliminate the worst from among
the remaining attributes.
Decision Tree Induction:
• Decision tree algorithms including ID3, C4.5, and CART, were
originally designed for classification.
• Decision tree induction constructs a flowchart-like structure
where each internal (non-leaf) 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.
What are Decision Trees?

• In simple words, a decision tree is a structure that contains nodes

(rectangular boxes) and edges(arrows) and is built from a dataset
(table of columns representing features/attributes and rows
corresponds to records). Each node is either used to make a
decision (known as decision node) or represent an outcome (known
as leaf node).
Decision tree Example
The picture above depicts a decision tree that is
used to classify whether a person
is Fit or Unfit.
The decision nodes here are questions like ‘’‘Is
the person less than 30 years of age?’, ‘Does
the person eat junk?’, etc. and the leaves are
one of the two possible outcomes
viz. Fit and Unfit. The initial node is called the root
Looking at the Decision Tree we can say make node (colored in blue), the final nodes
the following decisions: are called the leaf nodes (colored in
if a person is less than 30 years of age and green) and the rest of the nodes are
called intermediate or internal nodes.
doesn’t eat junk food then he is Fit, if a person
The root and intermediate nodes
is less than 30 years of age and eats junk food
represent the decisions while the leaf
then he is Unfit and so on. nodes represent the outcomes.
Another Decision Tree Example
age income student credit_rating buys_computer
<=30 high no fair no
❑ Training data set: Buys_computer <=30 high no excellent no
❑ The data set follows an example of 31…40 high no fair yes
>40 medium no fair yes
Quinlan’s ID3 (Playing Tennis) >40 low yes fair yes
>40 low yes excellent no
❑ Resulting tree:
31…40 low yes excellent yes
age? <=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
<=30 overcast
31..40 >40 31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no

student? yes credit rating?

no yes excellent fair

no yes yes
140
 Algorithm for Decision Tree Induction
• Basic algorithm (a greedy algorithm)
• Tree is constructed in a top-down recursive divide-and-conquer
manner
• At start, all the training examples are at the root
• Attributes are categorical (if continuous-valued, they are
discretized in advance)
• Examples are partitioned recursively based on selected
attributes
• Test attributes are selected on the basis of a heuristic or
statistical measure (e.g., information gain)
• Conditions for stopping partitioning
• All samples for a given node belong to the same class
• There are no remaining attributes for further partitioning –
majority voting is employed for classifying the leaf
• There are no samples left
141
Brief Review of Entropy

m=2
142
ID3 in brief
• D3 stands for Iterative Dichotomiser 3 and is named such because the
algorithm iteratively (repeatedly) dichotomizes(divides) features into
two or more groups at each step.
• Invented by Ross Quinlan, ID3 uses a top-down greedy approach to
build a decision tree. In simple words, the top-down approach means
that we start building the tree from the top and the greedy approach
means that at each iteration we select the best feature at the present
moment to create a node.
• Most generally ID3 is only used for classification problems
with nominal features only.
Metrics in ID3

• Information Gain: Information Gain calculates the reduction in the

entropy and measures how well a given feature separates or classifies
the target classes. The feature with the highest Information Gain is
selected as the best one.
• Entropy : It is the measure of disorder and the Entropy of a dataset is
the measure of disorder in the target feature of the dataset.
• In the case of binary classification (where the target column has only
two types of classes) entropy is 0 if all values in the target column are
homogenous(similar) and will be 1 if the target column has equal
number values for both the classes.
Computation of Entropy
• Entropy(S) = - ∑ pᵢ * log₂(pᵢ) ; i = 1 to n

where,
n is the total number of classes in the target column
(in our case n = 2 i.e YES and NO)
pᵢ is the probability of class ‘i’ or the ratio of “number of rows with class
i in the target column” to the “total number of rows” in the dataset.
Computation of Information Gain
• IG(S, A) = Entropy(S) - ∑((|Sᵥ| / |S|) * Entropy(Sᵥ))
• where Sᵥ is the set of rows in S for which the feature column A has
value v,
• |Sᵥ| is the number of rows in Sᵥ and likewise |S| is the number of rows
in S
• A is the Feature Column(Attribute)
ID3 Steps:
[Link] the Information Gain of each feature.
[Link] that all rows don’t belong to the same class, split the
dataset S into subsets using the feature for which the Information
Gain is maximum.
[Link] a decision tree node using the feature with the maximum
Information gain.
[Link] all rows belong to the same class, make the current node as a leaf
node with the class as its label.
[Link] for the remaining features until we run out of all features, or
the decision tree has all leaf nodes.
 Attribute Selection Measure:
Information Gain (ID3/C4.5)
◼ Select the attribute with the highest information gain
◼ Let pi be the probability that an arbitrary tuple in D belongs to
class Ci, estimated by |Ci, D|/|D|
◼ Expected information (entropy) needed to classify a tuple in D:
m
Info( D ) = − pi log 2 ( pi )
i =1
◼ Information needed (after using A to split D into v partitions) to
classify D: v | D |
Info A ( D) =   Info( D j )
j

j =1 | D |
◼ Information gained by branching on attribute A

Gain(A) = Info(D) − Info A(D)

148
 Attribute Selection: Information Gain
 Class P: buys_computer = “yes” 5 4
Infoage ( D) = I (2,3) + I (4,0)
 Class N: buys_computer = “no” 14 14
9 9 5 5 5
Info( D) = I (9,5) = − log 2 ( ) − log 2 ( ) =0.940 + I (3,2) = 0.694
14 14 14 14 14
age pi ni I(pi, ni) 5
<=30 2 3 0.971 I (2,3)means “age <=30” has 5 out of 14
14 samples, with 2 yes’es and 3 no’s.
31…40 4 0 0 Hence
>40 3 2 0.971
age
<=30
income student credit_rating
high no fair
buys_computer
no
Gain(age) = Info( D) − Infoage ( D) = 0.246
<=30
31…40
high
high
no
no
excellent
fair
no
yes
Similarly,
>40 medium no fair yes
>40 low yes fair yes

Gain(income) = 0.029
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30
>40
low
medium
yes fair
yes fair
yes
yes
Gain( student) = 0.151
<=30
31…40
medium
medium
yes excellent
no excellent
yes
yes Gain(credit _ rating ) = 0.048
149 31…40 high yes fair yes
>40 medium no excellent no
Example Covid 19 data set
• ID | Fever | Cough | Breathing issues | Infected |
+----+-------+-------+------------------+----------+
| 1 | NO | NO | NO | NO |
+----+-------+-------+------------------+----------+
| 2 | YES | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 3 | YES | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 4 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 5 | YES | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 6 | NO | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 7 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 8 | YES | NO | YES | YES |
+----+-------+-------+------------------+----------+
| 9 | NO | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 10 | YES | YES | NO | YES |
+----+-------+-------+------------------+----------+
| 11 | NO | YES | NO | NO |
+----+-------+-------+------------------+----------+
| 12 | NO | YES | YES | YES |
+----+-------+-------+------------------+----------+
| 13 | NO | YES | YES | NO |
+----+-------+-------+------------------+----------+
| 14 | YES | YES | NO | NO |
+----+-------+-------+------------------+----
Computation Entropy
• From the total of 14 rows in our dataset S, there are 8 rows with the
target value YES and 6 rows with the target value NO.

• The entropy of S is calculated as:

• Entropy(S) = — (8/14) * log₂(8/14) — (6/14) * log₂(6/14) = 0.99
IG calculation for Fever: Fever | Cough | Breathing issues | Infected |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
• In this(Fever) feature there +-------+-------+------------------+----------+
are 8 rows having | YES | YES | NO | NO |
+-------+-------+------------------+----------+
value YES and 6 rows | YES | NO | YES | YES |
having value NO. +-------+-------+------------------+----------+
| YES | YES | YES | YES |
As shown below, in +-------+-------+------------------+----------+
the 8 rows with YES | YES | NO | YES | YES |
for Fever, there are 6 rows +-------+-------+------------------+----------+
| YES | NO | YES | YES |
having target +-------+-------+------------------+----------+
value YES and 2 rows | YES | YES | NO | YES |
+-------+-------+------------------+----------+
having target value NO. | YES | YES | NO | NO |
+-------+-------+------------------+----------+
Analysis
• As shown below, in ------+-------+------------------+----------+
| Fever | Cough | Breathing issues | Infected |
the 6 rows with NO, there +-------+-------+------------------+----------+
are 2 rows having target | NO | NO | NO | NO |
+-------+-------+------------------+----------+
value YES and 4 rows having | NO | YES | NO | NO |
target value NO. +-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | NO | NO |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | NO |
+-------+-------+------------------+----------+
calculation of Information Gain for Fever.
• # total rows
• |S| = 14
• For v = YES, |Sᵥ| = 8
• Entropy(Sᵥ) = - (6/8) * log₂(6/8) - (2/8) * log₂(2/8) = 0.81
• For v = NO, |Sᵥ| = 6
• Entropy(Sᵥ) = - (2/6) * log₂(2/6) - (4/6) * log₂(4/6) = 0.91
• # Expanding the summation in the IG formula:
• IG(S, Fever) = Entropy(S) - (|Sʏᴇꜱ| / |S|) * Entropy(Sʏᴇꜱ) -
• (|Sɴᴏ| / |S|) * Entropy(Sɴᴏ)
• ∴ IG(S, Fever) = 0.99 - (8/14) * 0.81 - (6/14) * 0.91 = 0.13
Similarly Calculation for Cough and Breathing
• IG(S, Cough) = 0.04
IG(S, Breathing Issues) = 0.40
• Since the feature Breathing issues have the highest Information Gain
it is used to create the root node.
• Hence, after this initial step our tree looks like this:

• Next, from the remaining two unused features, namely, Fever and
Cough, we decide which one is the best for the left branch of
Breathing Issues.
• Next, from the remaining two unused features,
namely, Fever and Cough, we decide which one is the best for the left
branch of Breathing Issues.
Since the left branch of Breathing Issues denotes YES, we will work
with the subset of the original data i.e the set of rows having YES as
the value in the Breathing Issues column
• Fever | Cough | Breathing issues | Infected |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | YES | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| YES | NO | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | NO |
+-------+-------+------------------+----------+
• Next, we calculate the IG for the features Fever and Cough using the
subset Sʙʏ (Set Breathing Issues Yes) which is shown above :
• Note: For IG calculation the Entropy will be calculated from the subset
Sʙʏ and not the original dataset S.
IG calculation the Entropy will be calculated from
the subset Sʙʏ and not the original dataset S
• IG(Sʙʏ, Fever) = 0.20
IG(Sʙʏ, Cough) = 0.09
• G of Fever is greater than that of Cough, so we select Fever as the left
branch of Breathing Issues:
• Next, we find the feature with the maximum IG for the right branch
of Breathing Issues. But, since there is only one unused feature left
we have no other choice but to make it the right branch of the root
node.
• There are no more unused
------+-------+------------------+----------+
features, so we stop here | Fever | Cough | Breathing issues | Infected
and jump to the final step of |
+-------+-------+------------------+----------+
creating the leaf nodes. | YES | YES | YES | YES |
For the left leaf node of +-------+-------+------------------+----------+
Fever, we see the subset of | YES | NO | YES | YES |
+-------+-------+------------------+----------+
rows from the original data | YES | YES | YES | YES |
set that has Breathing +-------+-------+------------------+----------+
| YES | NO | YES | YES |
Issues and Fever both +-------+-------+------------------+----------+
values as YES. | YES | NO | YES | YES |
+-------+-------+------------------+----------+
• Since all the values in the target column are YES, we label the left leaf node
as YES, but to make it more logical we label it Infected.
• Similarly, for the right node of Fever we see the subset of rows from the
original data set that have Breathing Issues value as YES and Fever as NO.
• -------+-------+------------------+----------+
| Fever | Cough | Breathing issues | Infected |
+-------+-------+------------------+----------+
| NO | YES | YES | YES |
+-------+-------+------------------+----------+
| NO | YES | YES | NO |
+-------+-------+------------------+----------+
| NO | YES | YES | NO |
+-------+-------+------------------+----------+
• Here not all but most of the values are NO, hence NO or Not
Infected becomes our right leaf node
• We repeat the same process for the node Cough, however here both
left and right leaves turn out to be the same i.e. NO or Not
Infected as shown below:
•
• Pruning is a mechanism that reduces the size and complexity of a
Decision tree by removing unnecessary nodes.
• Another drawback of ID3 is overfitting or high variance i.e. it learns
the dataset it used so well that it fails to generalize on new data.
ID3 Algorithms Conclusion
• We covered the process of the ID3 algorithm in detail and saw how
easy it was to create a Decision Tree using this algorithm by using only
two metrics viz. Entropy and Information Gain.
Outlier Analysis
 What Are Outliers?

• Outlier: A data object that deviates significantly from the normal objects as if it were generated
by a different mechanism
• Ex.: Unusual credit card purchase, sports: Michael Jordon, Wayne Gretzky, ...
• Outliers are different from the noise data
• Noise is random error or variance in a measured variable
• Noise should be removed before outlier detection
• Outliers are interesting: It violates the mechanism that generates the normal data
• Outlier detection vs. novelty detection: early stage, outlier; but later merged into the model
• Applications:
• Credit card fraud detection
• Telecom fraud detection
• Customer segmentation
• Medical analysis

170
Types of Outliers (I)
• Three kinds: global, contextual and collective outliers
• Global outlier (or point anomaly) Global Outlier
• Object is Og if it significantly deviates from the rest of the data set
• Ex. Intrusion detection in computer networks
• Issue: Find an appropriate measurement of deviation
• Contextual outlier (or conditional outlier)
• Object is Oc if it deviates significantly based on a selected context
• Ex. 80o F in Urbana: outlier? (depending on summer or winter?)
• Attributes of data objects should be divided into two groups
• Contextual attributes: defines the context, e.g., time & location
• Behavioral attributes: characteristics of the object, used in outlier
evaluation, e.g., temperature
• Can be viewed as a generalization of local outliers—whose density
significantly deviates from its local area
• Issue: How to define or formulate meaningful context?

171
Types of Outliers (II)
• Collective Outliers
• A subset of data objects collectively deviate significantly
from the whole data set, even if the individual data objects
may not be outliers
• Applications: E.g., intrusion detection: Collective Outlier
• When a number of computers keep sending denial-of-
service packages to each other
◼ Detection of collective outliers
◼ Consider not only behavior of individual objects, but also that of

groups of objects
◼ Need to have the background knowledge on the relationship

among data objects, such as a distance or similarity measure

on objects.
◼ A data set may have multiple types of outlier
◼ One object may belong to more than one type of outlier
172
Challenges of Outlier Detection
◼ Modeling normal objects and outliers properly
◼ Hard to enumerate all possible normal behaviors in an application

◼ The border between normal and outlier objects is often a gray area

◼ Application-specific outlier detection

◼ Choice of distance measure among objects and the model of

relationship among objects are often application-dependent

◼ E.g., clinic data: a small deviation could be an outlier; while in

marketing analysis, larger fluctuations

◼ Handling noise in outlier detection
◼ Noise may distort the normal objects and blur the distinction

between normal objects and outliers. It may help hide outliers and
reduce the effectiveness of outlier detection
◼ Understandability
◼ Understand why these are outliers: Justification of the detection

◼ Specify the degree of an outlier: the unlikelihood of the object being

generated by a normal mechanism

173
Outlier Analysis
• Outlier and Outlier Analysis
• Outlier Detection Methods

174
Outlier Detection I: Supervised Methods
• Two ways to categorize outlier detection methods:
• Based on whether user-labeled examples of outliers can be obtained:
• Supervised, semi-supervised vs. unsupervised methods
• Based on assumptions about normal data and outliers:
• Statistical, proximity-based, and clustering-based methods
• Outlier Detection I: Supervised Methods
• Modeling outlier detection as a classification problem
• Samples examined by domain experts used for training & testing
• Methods for Learning a classifier for outlier detection effectively:
• Model normal objects & report those not matching the model as
outliers, or
• Model outliers and treat those not matching the model as normal
• Challenges
• Imbalanced classes, i.e., outliers are rare: Boost the outlier class and
make up some artificial outliers
• Catch as many outliers as possible, i.e., recall is more important than
accuracy (i.e., not mislabeling normal objects as outliers)

175
Outlier Detection II: Unsupervised Methods
• Assume the normal objects are somewhat ``clustered'‘ into multiple groups,
each having some distinct features
• An outlier is expected to be far away from any groups of normal objects
• Weakness: Cannot detect collective outlier effectively
• Normal objects may not share any strong patterns, but the collective
outliers may share high similarity in a small area
• Ex. In some intrusion or virus detection, normal activities are diverse
• Unsupervised methods may have a high false positive rate but still miss
many real outliers.
• Supervised methods can be more effective, e.g., identify attacking some key
resources
• Many clustering methods can be adapted for unsupervised methods
• Find clusters, then outliers: not belonging to any cluster
• Problem 1: Hard to distinguish noise from outliers
• Problem 2: Costly since first clustering: but far less outliers than normal
objects
• Newer methods: tackle outliers directly

176
Outlier Detection III: Semi-Supervised Methods
• Situation: In many applications, the number of labeled data is often small:
Labels could be on outliers only, normal objects only, or both

• Semi-supervised outlier detection: Regarded as applications of semi-supervised

learning

• If some labeled normal objects are available

• Use the labeled examples and the proximate unlabeled objects to train a
model for normal objects
• Those not fitting the model of normal objects are detected as outliers

• If only some labeled outliers are available, a small number of labeled outliers
many not cover the possible outliers well
• To improve the quality of outlier detection, one can get help from models
for normal objects learned from unsupervised methods
177
Outlier Detection (1): Statistical Methods
• Statistical methods (also known as model-based methods) assume that the normal
data follow some statistical model (a stochastic model)
• The data not following the model are outliers.

◼ Example (right figure): First use Gaussian distribution

to model the normal data
◼ For each object y in region R, estimate gD(y), the

probability of y fits the Gaussian distribution

◼ If gD(y) is very low, y is unlikely generated by the

Gaussian model, thus an outlier

◼ Effectiveness of statistical methods: highly depends on whether the

assumption of statistical model holds in the real data
◼ There are rich alternatives to use various statistical models
◼ E.g., parametric vs. non-parametric

178
Outlier Detection (2): Proximity-Based Methods
• An object is an outlier if the nearest neighbors of the object are far away, i.e., the
proximity of the object is significantly deviates from the proximity of most of the
other objects in the same data set

◼ Example (right figure): Model the proximity of an

object using its 3 nearest neighbors
◼ Objects in region R are substantially different
from other objects in the data set.
◼ Thus the objects in R are outliers
◼ The effectiveness of proximity-based methods highly relies on the
proximity measure.
◼ In some applications, proximity or distance measures cannot be
obtained easily.
◼ Often have a difficulty in finding a group of outliers which stay close to
each other
◼ Two major types of proximity-based outlier detection
◼ Distance-based vs. density-based
179
Outlier Detection (3): Clustering-Based Methods

• Normal data belong to large and dense clusters, whereas outliers

belong to small or sparse clusters, or do not belong to any
clusters
◼ Example (right figure): two clusters
◼ All points not in R form a large cluster
◼ The two points in R form a tiny cluster,
thus are outliers
◼ Since there are many clustering methods, there are many
clustering-based outlier detection methods as well
◼ Clustering is expensive: straightforward adaption of a
clustering method for outlier detection can be costly and
does not scale up well for large data sets

180