Data Mining and BI

Topic three
Data and data warehousing
Topics
 Fundamental concepts and the need for business intelligence,
data mining and its flavors , big data analysis
 BI/DM/BDA applications, DA models and frameworks
 Data and data warehousing
 Data mining techniques ;Association rule mining, Classification
and Cluster analysis
 Including web/text, opinion mining, Big data and BI technologies,
applications, and case studies
 Web Mining/ opinion mining basics and Current trends in (big)
data analytics and BI
Sub - Topics
 The nature of real world data and data formats
 Data quality issues
 Preparing data for analysis/preprocessing
 Data warehouse

3
The nature of real world data and data
formats
The Data Set (input to DM process)
 Components of the input:
 Concepts: kinds of things that can be learned
 Aim: intelligible and operational concept description
 Instances: (data objects) the individual, independent
examples of a concept
 Attributes: measuring aspects of an instance
 We apply data analytics (DM, Web Mining, Opinion Mining,
Big data analytics) on this input data

5
Cont…
Attributes
 Thus dataset can be seen as collection of data
objects/examples and their attributes, representing
Tid Refund Marital Taxable
a concept Status Income Cheat

1 Yes Single 125K No

 An attribute is a property or characteristic of an 2 No Married 100K No

object 3 No Single 70K No

4 Yes Married 120K No
 Examples: eye color of a person, temperature, 5 No Divorced 95K Yes
etc. Objects 6 No Married 60K No

 Attribute is also known as variable, field, 7 Yes Divorced 220K No

characteristic, or feature 8 No Single 85K Yes
9 No Married 75K No
 A collection of attributes to describe an object
10 No Single 90K Yes
 Object is also known as record, point, case,
10

sample, entity, or instance

Data objects
 Instance: specific type of example
 Thing/opinions/ to be classified, associated, or clustered
 Individual, independent example of target concept
 Characterized by a predetermined set of attributes
 Input to learning scheme: set of instances/dataset
 Represented as a single relation/flat file
 Rather restricted form of input
 No relationships between objects
 Most common form in practical data mining/web mining

7
What‘s an attribute?
 Each instance is described by a fixed predefined set of
features, its ―attributes‖
 But: number of attributes may vary in practice
 Possible solution: ―irrelevant value‖ flag
 Related problem: existence of an attribute may depend
of value of another one
 Possible attribute types (―levels of measurement‖):
 Nominal, ordinal, interval and ratio

8
Attribute types used in practice
 Most schemes accommodate just two levels of measurement: nominal and ordinal
 Nominal attributes are also called ―categorical‖, ‖enumerated‖, or ―discrete‖
 e.g. eye color=brown, blue, …
 only equality tests
 important special case: boolean (True/False)

 Ordinal attributes could be ―numeric‖, or ―continuous‖

 But: ―continuous‖ implies mathematical continuity
 Ordinal, e.g. grade=k,1,2,..,12
 Continuous (numeric), e.g. year
 interval quantities – integer
 ratio quantities -- real

9
Types of data sets formats
 Record
 Relational, Data Matrix, Document Data,
Transaction Data

 Graph and networks

 World Wide Web, Social networks, Molecular
Structures

 Ordered
 SpatialData, Temporal Data, Sequential Data,
Genetic Sequence Data
10
11
Document Data

 Each document becomes a `term' vector,

 each term is a component (attribute) of the vector,
 the value of each component is the number of times the
corresponding term occurs in the document (or a weight of a
term)

timeout

season
coach

game
score
team

ball

lost
pla

wi
n
y
Document 1 3 0 5 0 2 6 0 2 0 2

Document 2 0 7 0 2 1 0 0 3 0 0

12
Document 3 0 1 0 0 1 2 2 0 3 0
Transaction Data
 A special type of record data, where
 each record (transaction) involves a set of items.
 For example, consider a grocery store. The set of
products purchased by a customer during one shopping
trip constitute a transaction, while the individual
products that were purchased are the items.

TID Items
1 Bread, Coke, Milk
2 Beer, Bread
3 Beer, Coke, Diaper, Milk
4 Beer, Bread, Diaper, Milk
5 Coke, Diaper, Milk
13
14
15
Data Quality
 What kinds of data quality problems?
 How can we detect problems with the data?
 What can we do about these problems?

16
Cont…

 Examples (basic types) of data quality problems:

 Noise and outliers (what is the difference?)
 missing values
 duplicate data
Data Quality Measures
 Before feeding data to DW/DM /DA we have to make sure
the quality of data.
 A well-accepted multidimensional data quality measures
are the following:
 Accuracy
 Completeness
 Consistency
 Timeliness
 Believability
 Interpretability

 Most common issues in DM however are : incomplete,

Inconsistent , Noisy, redundant, …
18
Noise
 Noise refers to modification of original values.
 It may also be used to indicate the problem with dispersed
data
 Examples:
 attribute values that might be invalid or incorrect. E.g.
typographical errors
 distortion of a person‘s voice when talking on a poor
phone line and ―snow‖ on television screen

19
Outliers
 Outliers are data objects with characteristics that are
considerably different than most of the other data objects in
the data set
 misleading data that do not fit to most of the data/facts

20
Missing Values
 attributes values might be absent which needs to be
replaced with estimates
 Reasons for missing values
 Information is not collected
(e.g., people decline to give their age and weight)
 Attributes may not be applicable to all cases
(e.g., annual income is not applicable to children)
(victim age etc… is not appropriate to Property damage
Severity)

21
Duplicate Data
 Data set may include data objects that are duplicates,
or almost duplicates of one another
 Major issue when merging data from heterogeneous
sources
 Examples:
 Date of birth and age at the same time
 Same person with multiple email addresses

22
Why - Data is often of low quality
 Business Analytics/Data mining requires collecting large
amount of data (available in warehouses or databases) to
achieve the intended objective.
 BUT in addition to its heterogeneous & distributed nature of data,
data in the real world is dirty and low quality.
 Why?
 People make mistakes (typos)
 You didn‘t collect it yourself!
 Itprobably was created for some other use, and then you
came along wanting to integrate it
 People are busy (―this is good enough‖) to systematically
organize carefully using structured formats

23
Hot New Data to Play With for BI

 Social network data

 Biometric data
 Images/Video
 Text (Blogs, news, reviews, etc.)
 Google Analytics
 GIS
 Network log data

….who knows what the future holds..

24
Data On web applications-example?
 User
 Installation date, uninstall, Friends, Fan/not-fan
 Where did they come from – ad, message, status
 Requests
 Who was asking for information, For which cities, Who
responded
 Preferences : Who set preferences, What were they set to
 Posts
 Who posted and where, Who commented and where , Who saved
 Who posted pictures, Who tagged pictures, Which cities are
people searching for
 API: Who clicks on the API data
25
From Data To Model: quality data for a better model

 Why are we worried too Data

much about data quality?

 It is because wrong data will

Model
lead to wrong model and
which intern affect busies
decision
Business Solution
(recommendation)

26
What is a model?

 A simplified representation of reality (based on certain

assumptions) created for a specific purpose.
 Simple: Stylized, partial (focused only on certain aspects),
capture the essence.
 Representation: Words, pictures, boxes and arrows,
mathematical expressions
 Specific purpose: What to capture. What to ignore.
 Variables: Entities of interest
 Controllable, uncontrollable, environmental
 Assumptions: Reduce complexity
 In the context of BI & A it includes algorithms + data 27
Solving Business Problems (through Modeling)

REAL WORLD FORMULATION MATH MODEL

PROBLEM DEFINE, SCOPE, SPECIFY

ACQUIRE DATA

TEST
USE

REFINE
COMMUNICATE CALCULATE/DEDUCE
IMPLEMENT

TEST

SENSITIVITY
REAL WORLD INTERPRETATION
SOLUTION MODEL
28
SOLUTION
Case: Business analytics @ Verizon Wireless

About Verizon Wireless

 Largest wireless provider in US
 Customer base: 142 million
 Covering 50% of US population

Challenges
 High customer turnover rate (churn) of 2% per
month (600,000 customers disconnect per month)
 Associated replacement cost in hundreds of
millions per year
 Average cost of new customer acquisition: $320
29
cont…
Possible solutions
 Offer incentives to every customers before contracts
expire
 expensive

 no learning
 Identify
those customers who will not continue with
the company

30
BI & A Solution: Prediction
 Build a predictive model: Before contracts
expire use a predictive model to predict which
customers are likely to leave (i.e., estimating
the probability)
 Then:

 Offer benefits such as a new phone only

to customers most likely to disconnect
 Develop new plans to fit customer
needs

31
Review questions
 What is dataset?
 Discuss any business you know using the nature of
data set around?
 Record , network, ordered ?
 Explain major types of data quality problems?
 Explain what a model is in the context of data
analytics ?

32
 Data Preprocessing
(preparing the data for
experiment/analytics)

33
THE MAGNITUED

34
What is Data Preprocessing?
 "Every data analysis/analytics task starts by gathering,
characterizing, and cleaning a new, unfamiliar data set..."
 More than 80% of researchers working on mining projects
spend 40%-60% of their time on cleaning and preparation of
data.‖ [Kalashnikov+Mehrotra2005]
 Data pre-processing refers to the processing of the various data
elements to prepare for the analytics operation.
 Any activity performed prior to mining the data to get
knowledge out of it is called data pre-processing

35
Selection Example : Data Source Selection
• If for example your mining task is related with customers (profiling,
marketing…)
• Internal Sources
• Customer purchases, Customer billing, Customer complaints,
Supplier orders, deliveries, etc.
• External Sources (this is where we need data preprocessing more
importantly )
• Customer demographics (e.g. age, number of children)
• Customer psychographics (e.g. enjoys fishing, surfing, movies)
• Credit bureau information (e.g. bad debt rating)
• Location information (e.g. average income for suburb, city)
• Competitor information (e.g. prices, promotions, store
36
attributes)

36
Recall the ―why‖ of Data Preprocessing
 Data in the real world is dirty
 Incomplete (missing)
 Noisy: containing errors/Outliers that deviate from the expected
 Duplicate/Inconsistent: containing duplicates/discrepancies in
codes or names
 The data is stored in many formats/different places
 Even the data might not exist as is ready for analysis
 These databases may be heterogeneous
 Variations in schema
 The data may be represented differently across the various datasets
 Data in these DB may simply be inaccurate for the purpose at hand
37
Should we start processing right away?
 Before starting data preprocessing, it will be advisable to have overall
picture of the data we have, so that it tell us high level summary such as;
 General property of the data
 Magnitude of duplicates, missing etc..
 Which data values should be considered as noise or outliers….
 This can be done with the help of descriptive data summarization
 But a minimum requirement is details of the data set in terms of number
of Instances, Features (with their nature), Attribute values especially for
the target class- and explaining them
 Even, Total data size in MB, GB etc..
 Graphic display of basic summaries
38
Descriptive data summarization
 Descriptive summary about data can be generated with the
help of measure of central tendency of the data and
dispersion of the data
 Measureof central tendency includes: mean, median,
mode, mid range.
 Measure of dispersion (Variance) includes: Range, The five
number summary (based on Quartiles), Interquartile range
(IQR), Standard deviation

39
QUESTION
 What are issues related to data that can help you
improve the validity and reliability of research/project
in general?

 Data source/ appropriateness

 Representativeness and enough

 These are also important in data analytics

40
Now then
 You have good understanding of the general nature
of the data
 You can move to selecting and engaging on basic
preprocessing tasks.
 Note that ; all pre processing tasks may not be
applicable to your data at hand
 Even you may not need one

41
FORMS (MAJOR TASKS) OF DATA PREPROCESSING (HIGH LEVEL)

42
Major Tasks in Data Preprocessing
 Data cleaning: to get rid of bad data
– smooth noisy data, fill in missing values,, identify or remove outliers,
and resolve duplication/inconsistencies
 Data integration
– Integration of data from multiple databases, data warehouses, or files
– Mainly handling redundancy
 Data reduction
– Dimensionality reduction/ feature selection
– Numerosity/size reduction
– Data compression (usually for multimedia data mining)
 Data transformation
– Normalization
– Discretization and/or Concept hierarchy generation
43
DATA CLEANING- INCOMPLETE/missing
 Incomplete: lacking attribute values, lacking certain attributes of interest,
or containing only aggregate data
– e.g., Occupation=― ‖ (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
• While the lacking attribute values is the most common, lacking attribute
of interest is the most serious in DM context
• Thus in case of lack of certain ―attribute of interest‖ you may need to
look for other data source or drive one from the existing (feature creation)
• In case of aggregate data you may need to decompose or drill down
searching for details
44
Data Cleaning: How to Handle Missing (incomplete)
Data?- Imputation
 It is the process of replacing missing data with substituted values (Case
Deletion Vs Imputation)
 Case Deletion
 Generally Ignore the tuple: usually done when class label is missing
 By far, the most common means of dealing with missing data is listwise
deletion, which is when all cases with a missing value are deleted
 Pairwise deletion (or "available case analysis") involves deleting a case
when it is missing a variable required for a particular analysis, but
including that case in analyses for which all required variables are
present.

45
Cont…
 Imputation
A few of the well known attempts to deal with missing data include:
hot-deck(last observation carried forward); mean imputation;
regression imputation; global constant imputation;
 Use a global constant to fill in the missing value: e.g., ―unknown‖,
a new class?!
 Note that this constant may form some interesting pattern for the
data mining task which mislead decision process
A hot-deck imputation "last observation carried forward", which
involves sorting a dataset according to any of a number of variables,
thus creating an ordered dataset.
 The technique then finds the first missing value and uses the cell
value immediately prior to the data that are missing
46 to impute
CONT…
 Use the attribute mean to fill in the missing value
 For example, suppose that the average income of AllElectronics customers is
$56,000. Use this value to replace the missing value for income.
 Use the attribute mean for all samples belonging to the same class to
fill in the missing value
 For example, if classifying customers according to credit risk, replace the missing
value with the average income value for customers in the same credit risk category
as that of the given tuple.
 Regression and stochastic imputations are also common in statistics
 Use the most probable value to fill in the missing value (for discrete
and/or categorical data)
 The last three approaches are the most commonly used technique to fill
missing data in data mining projects
47
Data Cleaning: Noisy Data
 Noisy:Generally containing errors, or some times referred as
outliers as shown below, duplication and dispersion of data
 Salary=―−10‖ (an error)
 Let say ‗green‘ is written as ‗rgeen‘

 Note that Incorrect attribute values may be due to

– faulty data collection instruments (e.g.: OCR)
– data entry problems
– data transmission problems
– technology limitation
– inconsistency in naming convention
48
Data Cleaning: How to catch/handle Noisy Data-error
• A technique my not apply to all cases. A case by case approach is appropriate
• Sort data by frequency
 ‗green‘ is more frequent than ‗rgeen‘
 Works well for categorical data
• Use, say Numerical constraints to Catch Corrupt Data
• Weight can‘t be negative
• People can‘t have more than 2 parents
• Salary can‘t be less than Birr 300
 Use other statistical techniques to Catch Corrupt Data
Check for correlated outliers using n-gram (―pregnant males‖), People can
be male, People can be pregnant, People can‘t be male AND pregnant
 Discretization Methods (Binning method)
 Clustering
49
Data Cleaning: Handling Noisy Data by
Discretization Methods (Binning)
 Binning methods smooth a sorted data value by consulting its
―neighborhood,‖ that is, the values around it.
 It helps smooth dispersed data (dispersion is noisy)
 The sorted values are distributed into a number of ―buckets,‖ or bins.
Thus sort data and partition into bins
 Binning (discretization) assigns numeric values to discrete
categories
 The bins can be equal-depth or equal-width bin
 Choose smoothing algorithm and apply the algorithm on each bin
 The algorithm can be; smooth by bin means, smooth by bin median,
smooth by bin boundaries, etc.
50
Data Cleaning: Handling Noisy Data by
Discretization Methods (Binning)
 Equal-width (distance) partitioning:
 Itdivides the range into N intervals of equal size: uniform grid
 ifA and B are the lowest and highest values of the attribute, the width of
intervals will be: W = (B-A)/N.
 Given the data set (say 24, 21, 28, 8, 4, 26, 34, 21, 29, 15, 9, 25)
 Determine the number of bins : N (say 3)
 Determine the range R= Max(B) – Min (A)
 For the above data R= 30,
 W= R/3 = 30/3= 10, X1 = 14, X2 = 24, and X3 = 34
 First sort the data as 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
 Therefore in our case Bin 1 = 4,8,9 Bin 2 = 15, 21, 21 Bin3 = 24, 25,
26, 28, 29, 34
 outliers may dominate presentation
 Skewed data may not be handled well.

51
Data Cleaning: Handling Noisy Data by
Discretization Methods (Binning)
 Equal-depth (frequency) partitioning:
 Itdivides the range into N intervals, each containing
approximately same number of samples
 Given the data set (say 24, 21, 28, 8, 4, 26, 34, 21, 29, 15, 9, 25)
 Determine the number of bins : N (say 3)
 Determine the frequency (F) of the data set (12)
 Determine the number of sample per bin F/N (12/3 = 4)
 Sort the data as 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34 and
place F/N element in order into a bin
 Therefore in our case Bin 1 = 4,8,9 ,15 Bin 2 = 21, 21,24,
25 Bin3 = 26, 28, 29, 34
 Good data scaling

52
Data Cleaning: Handling Noisy Data by Discretization Methods
(Binning)
Smoothing algorithm
 Given the data set in bins as say (using equal depth):
- Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bin 3: 26, 28, 29, 34
 Smoothing by bin means:
 Find the mean in each bin and replace all the element by the bin mean
 Bin 1: 9, 9, 9, 9, Bin 2: 23, 23, 23, 23, Bin 3: 29, 29, 29, 29
 Smoothing by bin median:
 Find the median in each bin and replace all the element by the bin median
 Bin 1: 8.5, 8.5, 8.5, 8.5, Bin 2: 22.5, 22.5, 22.5, 22.5
 Bin 3: 28.5, 28.5, 28.5, 28.5
 Smoothing by bin boundaries:
 Replace each element by the bin min or bin max which ever is the nearest
 Bin 1: 4, 4, 4, 15, Bin 2: 21, 21, 25, 25, Bin 3: 26, 26, 26, 34
53
Data Cleaning: Handling outliers/noisy Data by
Cluster Analysis
Some times some noise and outliers can be
detected using cluster analysis (to be discussed as
a DM function later)

54
Data cleaning – handling duplication

 Usually in terms of attributes not attribute values

 But also possible at a record level

 Needs closer examination of the case in line with

data mining objectives

 More discussion under the next topic ―integration‖

55
Data Integration (merging of Data)- Duplication
 Data mining often requires data integration— the merging of
data from multiple data stores.

 Data integration combines data from multiple sources

(database, data warehouse, files & sometimes from non-
electronic sources) into a coherent store

 Because of the use of different sources, data that is fine on its

own may become problematic when we want to integrate it.

56
 Some of the issues are:
 Different formats and structures
 As data source for data mining differ, the same entity will have
different representation in the different sources
 Schema integration: e.g., [Link]-id  [Link]-#
 Integrate metadata from different sources

 Redundant and Inconsistent data

 Equational theory and Correlation analysis
 Data at different levels
 If it is at a finer level of detail, you can sometimes bin it

57
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, age
 There might also be similar records / items

 Commonly used techniques

 Equational theory for case instance duplication
 Correlation analysis for feature duplication
 Transitive Closure using RS
 Careful integration of the data from multiple sources may help
reduce/avoid redundancies and inconsistencies and improve mining
quality 58

58
Equational Theory and distance functions
 Advanced mechanisms to check record or item similarity
 Uses a declarative rule language to specify an equational theory
 A set of equation rules that defines equivalence. A type of clustering
function (pattern recognition)
 According to Equational Theory; the comparison during the merge
phase is an inferential process
 Compares much more information than simply the key
 The more information there is, the better inferences can be made
 The process of creating a good equational theory is similar to the
process of creating a good knowledge-base for ES/KBS
 In complex problems, an expert‘s assistance is needed to write the
equational theory 59
Cont..
 Example -Two names are spelled nearly identically and have the same address
 It may be inferred that they are the same person
 A simplified rule in English to exemplify one axiom of equational theory

Given two records, r1 and r2

IF the last name of r1 equals the last name of r2,
AND the first names differ slightly,
AND the address of r1 equals the address of r2
THEN r1 is equivalent to r2

 The implementation of ―differ slightly‖ is based on the computation of a distance function

applied on the first name fields of r1 and r2
 Two social security numbers are the same but the names and addresses are totally different: Could
be the same person who moved, or Could be two different
60 people and there is an error in the
social security number
 A ―distance function‖ is used to compare pieces of data
(usually text)
 Apply ―distance function‖ to data that ―differ slightly‖
 Select a threshold to capture obvious typographical errors.
 Impacts number of successful matches and number of
false positives

61
Cont…
 Transitive Closure using RS

 Record similarity (RS) can also be used by employing

distance function computations.

IF (a is similar to b AND b is similar to c) THEN a is similar to c

62
 CONT…
 Correlation analysis (for attributes)
 Some redundancies can be detected by correlation analysis.
 For example given two attributes, such analysis can measure how
strongly one attribute implies the other, based on the available data.
Thus the correlation between two attributes A and B can be
measured by
 For numerical attributes, we can evaluate the correlation between
two attributes, A and B, by computing the correlation
coefficient(also known as Pearson‘s product moment coefficient)

 are the respective mean values of A and B, σA and σB are the

respective standard deviations of A and B , N is total number of
instances. 63
CONT…
 If rA,B is greater than 0, then A and B are positively correlated,
meaning that the values of A increase as the values of B increase.
 The higher the value, the stronger the correlation (i.e., the more
each attribute implies the other).
 Hence, a higher value may indicate that A (or B) may be removed
as a redundancy.
 If the resulting value is equal to 0, then A and B are independent and
there is no correlation between them.
 If the resulting value is less than 0, then A and B are negatively
correlated, where the values of one attribute increase as the values
of the other attribute decrease.
 For categorical (discrete) data, a correlation relationship between two attributes, A
and B, can be discovered by a χ 2 (chi-square) test. 64

 The χ 2 statistic tests the hypothesis that A and B are independent.

DATA REDUCTION
 Why data reduction?
 Warehouse /different data sources may store terabytes of data
 Complex data analysis/mining may take a very long time to run on the
complete data set
 Data reduction tries to obtain a reduced representation of the data set
that is much smaller in volume but yet produces the same (or almost
the same or better) analytical results
Data reduction strategies
 Data Cube Aggregation
 Dimensionality reduction: Select best or remove unwanted attributes
 Numerosity Reduction: Reduce data volume by choosing alternative,
smaller forms of data representation 65
DATA REDUCTION STRATEGIES: DATA CUBE
AGGREGATION
 Data cube aggregation and using it for data mining task reduces the
data set size significantly
 Forexample, one can aggregate sales amount specified at each
month and quarter into the sum of the sales amount per year
 Multiple levels of aggregation in data cubes further reduce the size of
data to deal with
 One should select appropriate levels of aggregation
 Use the smallest representation which is sufficient to solve the task

66
 CONT…

 Aggregation can also be attribute wise

 Combining two or more attributes into a single attribute.
 And it will help to address
 Data reduction
 Reduce the number of attributes or objects
 Change of scale
 Cities aggregated into regions, states, countries, etc
 More ―stable‖ data
 Aggregated data tends to have less variability

67
Data Reduction: Dimensionality Reduction
• Curse of dimensionality: When dimensionality increases, data becomes
increasingly sparse
• Dimensionality reduction:
 Help eliminate irrelevant features and reduce noise
 Reduce time and space required in data mining
 Allow easier visualization
• Method: attribute subset selection: Removes irrelevant attribute by
attribute relevance analysis
 Subject matter /domain experts involvement
 Based on business understanding
 Literature support
 Previous works
 Information gain and Statistical significance
 More detail along with decision tree model 68
Attribute Selection
 Before inducing a model we almost always do input engineering
 The most useful part of this is attribute selection (also called
feature selection)
 Why?
 Helps to focus by avoiding redundant attributes, Irrelevant
attributes
 E.g., is students' ID relevant to predict students' GPA?
 Reduce # of patterns , so that it will be easier to understand
 Irrelevant features contain no information that is useful for the
data mining task at hand
 Example: students' ID is often irrelevant to the task of
predicting students' GPA
 Goal: find a minimum set of attributes such that
resulting probability distribution of the data classes is as
close as possible to the original distribution
 CONT…

 Approaches : (related with feature selection and mining tasks)

 Brute-force approach:
 Try all possible feature subsets as input to mining algorithm
 Embedded/ Wrapper approaches:
 Feature selection occurs naturally as part of the data
mining algorithm
 Use the data mining algorithm as a black box to find best
subset of attributes
 Filter approaches:
 Features are selected before data mining algorithm is run

70
Filters
 Using Information Gain, Gain ration, Correlation
 High correlation with class attribute
 Low correlation with other attributes
 Results in either
 Ranked list of attributes
 Typicalwhen each attribute is evaluated individually
 Must select how many to keep
 A selected subset of attributes
 Best step-wise feature selection
 Step-wise attribute elimination
 Random search such as genetic algorithm
Wrappers

 ―Wrap around‖ the learning

algorithm
 Must therefore always evaluate Select a subset of
subsets attributes
 Return the best subset of attributes
Induce learning
 Apply for each learning algorithm algorithm on this subset
 Use same search methods as before
Evaluate the resulting
model (e.g., accuracy)

No Yes
Stop?
72
Cont…
• Concern
• Smaller attribute sets are simpler to understand, but may
produce an overly simplistic model

• Larger attribute sets may produce an overly complex model

that doesn‘t generalize to new data

• Note that attribute selection techniques can be fruitfully

employed to improve accuracy of any of the mining techniques
we will look at discussions on: decision trees, naïve bayes, etc.

73
Data Reduction: Numerosity Reduction

• Different methods can be used, including Clustering and sampling

• Though it is subjective and varies from case to case it is some how
acceptable to set minimum instance/case to ~ 5000 in data mining
• Clustering
 Partition data set into clusters based on similarity, and store cluster representation
(e.g., centroid and diameter) only.
 Data objects (instance) that are in the same cluster can be treated as the same
instance

• Sampling
 obtaining a small sample s to represent the whole data set N
 Allow a mining algorithm to run in less complexity
 Key principle:
 Choose a representative subset of the data using suitable sampling technique
74
Sampling
 Sampling is the main technique employed for data selection.
 Itis often used for both the preliminary investigation of the
data and the final data analysis.

 Statisticians sample because obtaining the entire set of data of

interest is too expensive or time consuming.

 Sampling is used in data mining because processing the entire set

of data of interest is too expensive or time consuming.

75
SAMPLING …
 The key principle for effective sampling is the following:
 using a sample will work almost as well as using the entire data
sets, if the sample is representative
A sample is representative if it has approximately the same
property (of interest) as the original set of data
 Types of Sampling (common in DM)
 Simple random sampling
 There is an equal probability of selecting any particular item
 Stratified sampling:
 partition the data set, and draw samples from each partition
( usually proportionally, i.e., approximately the same
percentage of the data)
76
DATA TRANSFORMATION (CONVERSION)
 In data transformation, the data are modified into forms more appropriate 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

 Several techniques may be viewed as data transformation techniques:

1. Smoothing – typically introduced to remove noise/outliers from the data. Mainly
through binning, clustering, generalization/aggregation
2. Normalization – involves rescaling of attributes.
 min-max normalization, z-score normalization
 Helps to speed up learning process by creating more manageable ranges

3. Attribute (feature) construction – new attributes are constructed and added to

the existing ones (including binary dummies, concept hierarchies, feature
creations and RFM analysis)

77
Normalization
 Min-max normalization:
 Performs a linear transformation on the original data values.
 Suppose that
 minX and maxX are the minimum and maximum of feature X.
We would like to map interval [minX, maxX] into a new
interval [new_minX, new_maxX].
 Consequently,every value v from the original interval will
be mapped into value new_v.
 Min-max normalization preserves the relationships among
the original data values.

v  minA
v'  .( new _ max A  new _ min A)  new _ min A
maxA  minA
78
 CONT…
 Z-score normalization
 The values of attribute X are normalized using the mean and
standard deviation of X.
 A new value new_v is obtained using the following expression,
where mX or μ and sX or σ are the mean and standard deviation of
attribute X, respectively.

v  A
v' 
 A

Good when
•min and max are unknown
•Outlier affect min/max
79
Normalization example
 Min-max normalization:
v  minA
v'  .( new _ max A  new _ min A)  new _ min A
maxA  minA
– Ex. Let income range $12,000 to $98,000 is normalized to [0.0, 1.0].
Then $73,600 is mapped to

73,600  12,000
(1.0  0)  0  0.716
98,000  12,000
 Z-score normalization (μ: mean, σ: standard deviation):
v  
v' 
A

 A

– Ex. Let μ = 54,000, σ = 16,000. Then,

73,600  54,000
 1.225
16,000 80
Feature Creation (extraction , construction)
 Create new attributes that can capture important information in a data set much more
efficiently than the original attributes
 Two general approach :
 Feature Extraction/Derived Values
 domain-specific

 e.g. derive customer (or product) age from birthdate (or production-date), as age
may be more predictive.
 Feature Construction
 Combining features : Attributes constructed in such a way that they do not add
any new information into the mix.
 New attributes are being constructed from the existing ones. For example,
attribute area may be constructed from height and width.

81
Concept Hierarchy Generation as a means of feature
creation:
 Concept hierarchy organizes concepts (i.e., country
attribute values) hierarchically and is usually
associated with each dimension in a data Region or state
warehouse
 Concept hierarchy formation: Recursively
reduce (and transform) the data by collecting city
and replacing low level concepts (such as
numeric values for age) by higher level
Sub city
concepts (such as youth, adult, or senior)
 Concept hierarchies can be explicitly specified by
domain experts and/or data warehouse designers Street
• Concept hierarchy can be automatically formed by the analysis of the
number of distinct values. E.g., for a set of attributes: {street, city,
state, country}
 For numeric data, use binning discretization methods. 82
RFM ANALYSIS AS A MEANS OF ATTRIBUTE EXTRACTION
• RFM analysis involves producing the following summary statistics for
each record (customer) in your database:
• Recency: time since last purchase
(e.g. categorize into 0-2 months, 3-6 months, 7-12 months, > 12
months)
• Frequency: number of previous purchases over a period
(e.g. categorize into 1 item, 2 item, 3 or more items)
• Monetary value: amount spent over a period
(e.g. categorize into $0-$20, $20-$50, $50-$100, >$100)
• This type of data is rarely available in an organized way
• These summary statistics can then be fed into data mining.
83
 BINARY DUMMIES FOR CATEGORICALS
• Some data mining algorithms predict binary results only in which case
it is helpful to transform categorical variables into binary dummies.
• Start with the categorical variable (1 column) and transform into [n-1]
binary columns where n is the number of categories.
• Many data mining tools will do this automatically for you.

Customer_ID Payment_Type 3 categories (Check / Cash /

1
2
Check
Cash
Credit),
3
4
Cash
Credit
transforms to
[3-1] = 2 binary columns
Customer_ID PaidByCheck PaidByCash
1 1 0
2 0 1
3 0 1
4 0 0

84
Challenges in preprocessing
 Compiling datasets (access to data)
 Including dataset Selection
 Especially those from the web, sensors, social
networks
 Processing task selection
 Ill-defined project/research question (how?)
 Which will affect dimensionality determination
(mainly)
 And last but not least: Procrastination

85
Review questions
 Why descriptive summary before Pre-processing?
 Explain smoothing through binning as a method of transformation and
cleaning?
 Dimensionality reduction Vs Numerosity Reduction. Explain?
 Should feature selection/attribute selection task be part of preprocessing
or actual pattern identification?
 What is dataset?
 Explain what a model is in the context of data analytics ?

86
Review questions
 Will it be necessary to apply all data preprocessing tasks to your data?
 Explain some techniques which you can use for different preprocessing
objectives (tasks)?
 ―More data more pattern‖ vs ― data reduction task‖ – argue for or against?
 Sampling can be applied on both features and instances in a data set. Argue
against or otherwise?
 Explain major types of data quality problems?
 How is document data format different from transactional data format

87
Thank you