Data Preprocessing – Normalization

Further to introduction, in this article I am going to discuss “Data Preprocessing” an important step in the knowledge discovery process, can be even considered as a fundamental building block of data mining. People who come from data warehousing background may already be familiar with the term ETL ( Stands for Extraction,Transformation and Loading). Any data mining or data warehousing effort's success is dependent on how good the ETL is performed. DP ( I am going to refer Data preprocessing as DP henceforth) is a part of ETL, its nothing but transforming the data. To be more precise modifying the source data in to a different format which
(i) enables data mining algorithms to be applied easily
(ii) improves the effectiveness and the performance of the mining algorithms
(iii) represents the data in easily understandable format for both humans and machines
(iv) supports faster data retrieval from databases
(v) makes the data suitable for a specific analysis to be performed.




The real world data is mere junk without DP. I am going to explain this through a simple example based on Normalization. For people who come from database background this Normalization is completely different from 1st, 2nd and 3rd form of normalizations used in the relational database design. This is a data preprocessing technique, You are going to say Wow !! to see how a simple DP technique in action can improve the effectiveness of analysis in orders of magnitude. To move on further we should know what is euclidean distance ?


Consider two points in a two-dimensional space (x1,y1) and (x2,y2), the distance between
these 2 points is given by the formula

This is called the Euclidean distance between the points. The same concept can be extended easily to multidimensional space. If the points are (a1,b1,c1,d1...) and (a2,b2,c2,d2,...), the distance between the points is given by

Now, I am going to introduce a sample data set of employee details. The assignment is to find the employees who have similar profiles.

Empid	Salary	Age	Experience
1	25000	24	4
2	40000	27	5
3	55000	32	7
4	27000	25	5
5	53000	30	5

In this data set the first column is an identifier and the rest of the columns contain information. Ignoring the id column if we consider each column as a dimension we can assume that each employee is represented by a point in three dimensional space. The good thing is we can use the euclidean distance formula to calculate the distance between each of these points. The distance between the points 1 and 2, ( the Emp ids 1 and 2 ) can be calculated as below

Look at the data set above, through examination we find that emp id 1 and 4 are employees with almost similar profile. So in the three dimensional space the distance between them should be less, or to put it other way these two points should be very close.


The following table gives the euclidean distance calculation for each employee with the other employee in our example data set.

	1	2	3	4	5
1	0.0000000	15000.0003333	30000.0012167	2000.0005000	28000.0006607
2	15000.0003333	0.0000000	15000.0009667	13000.0001538	13000.0003462
3	30000.0012167	15000.0009667	0.0000000	28000.0009464	2000.0020000
4	2000.0005000	13000.0001538	28000.0009464	0.0000000	26000.0004808
5	28000.0006607	13000.0003462	2000.0020000	26000.0004808	0.0000000

we can see from the above list that the distance between the employee no 1 and 4 is 2000.0004999999376, which is less when compared to distance between Empid 1 and other employees.So our interpretation seems to be correct. An alert reader would have noticed a significant thing here. Wait a minute and observe the above list again, it looks like the euclidean distance values are very close to the differences in salaries.

See this, the difference between the salaries of employees 1 and 4 is
= abs(25000 – 27000) = 2000

And the euclidean distance between one and four is 2000.0004999999376. Oh God !! The approach seems to be flawed. The euclidean distances are dominated by salary amount. So guess you cant rely on euclidean distance to find employees with similar profile.


How do we get ourselves out of this problem? We do not want the salary amount to dominate the euclidean distance calculation. We can achieve this by applying the DP technique, Normalization over the example data set.


What is Normalization?
The attribute data is scaled to fit in a specific range. There are many type of normalization
available, we will see one technique called Min Max Normalization here. Min Max Normalization transforms a value A to B which fits in the range[C,D]. It is given my the below formula

Consider the below example, the salary value is 50000, we want to transform this in to the
range [0.0, 1.0], the maximum value of salary is 55000 and the minimum value of salary is 25000 so the new scaled value for 50000 will be

Now let us apply the this normalization technique to all the three attributes in our example
dataset. Consider the following maximum and minimum values


Max salary = 55001
Min Salary = 24999
Max age = 33
Min age = 23
Max experience = 8
Min experience = 3


The attributes need to scaled to fit in the range [0.0,1.0]. Applying the min max
normalization formula above, we get the normalised example data set as given below

Normalised Example dataset

Empid	Salary	Age	Experience
1	0.0000333	0.1000000	0.2000000
2	0.5000000	0.4000000	0.4000000
3	1.0000000	0.9000000	0.8000000
4	0.0700000	0.2000000	0.4000000
5	0.9300000	0.7000000	0.4000000

Actual Employee data set before normalization ( to make the comparison easier)

Empid	Salary	Age	Experience
1	25000	24	4
2	40000	27	5
3	55000	32	7
4	27000	25	5
5	53000	30	5

We will calculate the euclidean distances for each employee with the other employee now. Its given in the table below.

Euclidean distance after normalization

	1	2	3	4	5
1	0.0000000	0.6164144	1.4141664	0.2333321	1.1273841
2	0.6164144	0.0000000	0.8123833	0.4772345	0.5270225
3	1.4141664	0.8123833	0.0000000	1.2332863	0.4521547
4	0.2333321	0.4772345	1.2332863	0.0000000	1.0005054
5	1.1273841	0.5270225	0.4521547	1.0005054	0.0000000

Euclidean distance before normalization

	1	2	3	4	5
1	0.0000000	15000.0003333	30000.0012167	2000.0005000	28000.0006607
2	15000.0003333	0.0000000	15000.0009667	13000.0001538	13000.0003462
3	30000.0012167	15000.0009667	0.0000000	28000.0009464	2000.0020000
4	2000.0005000	13000.0001538	28000.0009464	0.0000000	26000.0004808
5	28000.0006607	13000.0003462	2000.0020000	26000.0004808	0.0000000

Now compare the euclidean distance calculation pre and post normalization. We can see that the distances are no more dominated by the salary amount and they make more sense now. The age and the experience also contribute to the distance calculation. Its amazing !! Isn't it? I told you, right in the beginning you will get a Wow!! experience to see DP in action.


To conclude there are many measures similar to euclidean distance which can be used to calculate the similarity between two records such as Pearson coefficient, Tanimoto Coefficient, you can try replacing euclidean distance with any of these measures and experiment. You can read more on these measures in the see also section of the link and more on other normalization techniques such as X^2 ( X square) Normalization and decimal scaling are also worth trying. would appreciate your comments and gifts ;)