王大玲数据挖掘课件--3

1、,Chapter 3,Data Preprocessing,Data Preprocessing,Data Preprocessing: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Transformation Data Reduction Summary,Data in the real world is dirty incomplete lacking attribute value, lacking certain attributes of interest, con

2、taining only aggregate data noisy containing errors or outliers inconsistent containing discrepancies in codes or names,How about real world data?,mainly from data collection attributes of interest may not always be available e.g. age of a female customer relevant data may have been considered unimp

3、ortant at the time of entry e.g. height of a customer malfunctions of data entry equipment inconsistent data may have been removed ,Why incomplete?,mainly from data collection data collection instruments may not be accurate e.g. measuring wind speed with stopwatch human or computer errors occurring

4、at data entry errors in data transmission e.g. network error resulting from inconsistencies ,Why noisy?,mainly from data integration a concept may have different names in different databases e.g. customer, cust, and cust_id an attribute may have different names in different databases e.g. family nam

5、e and surname a value of an attribute may have different measures in different databases e.g. 1.75m and 175cm data integration may also encounter redundancy some attributes may be derived or inferred from others,Why inconsistent?,Why data preprocessing?,no quality data, no quality mining results How

6、 about mining those data directly? although most mining routines have some ability of dealing with incomplete or noisy data, they are not always robust most mining routines cannot deal with inconsistency even without incompleteness, noise, and inconsistency, the size of the data may be too large to

7、mine,Data Preprocessing,Data Preprocessing: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Transformation Data Reduction Summary,Major tasks of data preprocessing (I),Data cleaning （数据净化） filling in missing values, smoothing noisy data, identifying or removing outl

8、iers, and resolving inconsistencies,Water clean dirty-looking data cleanlooking data,Data integration （数据集成） integrating multiple databases, data cubes, files, etc.,Data transformation （数据转换） normalization and aggregation (-2, 32, 100, 59, 48) (-0.02, 0.32, 1.00, 0.59, 0.48),Major tasks of data prep

9、rocessing (II),Data reduction （数据约简） obtains reduced representation in volume which could produce the same or similar analytical results,Major tasks of data preprocessing (III),Data Preprocessing,Data Preprocessing: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Tr

10、ansformation Data Reduction Summary,Data cleaning attempts to do: filling in missing values smoothing out noisy data correcting inconsistent data,Data cleaning,Ignore the tuple usually done when class label is missing (assuming the tasks involving classification or description) poor when the percent

11、age of missing values per attribute varies considerably Fill in the missing value manually Tedious may be infeasible Use a global constant e.g. “unknown” mining routines may mistakenly think the filled value form an interesting concept,Filling in missing data (I),Filling in missing data (II),Use the

12、 attribute mean use the mean of the attribute across all the samples to fill in the missing value Use the attribute mean of the same class use the mean of the attribute across the samples belonging to the same class to fill in the missing value Use the most probable value model the attribute with ot

13、her available attributes smarter strategy, which uses the most information contained in the present data,Smoothing out noisy data (I),Binning smooth a sorted data value by consulting its “neighborhood”,data: 21, 120, 28, 30, 2, 25, 32, 108, 26,Binning smooth a sorted data value by consulting its “ne

14、ighborhood”,sorted data: 2, 21, 25, 26, 28, 30, 32, 108, 120,Smoothing out noisy data (II),Binning smooth a sorted data value by consulting its “neighborhood”,by bin means: 16, 16, 16, 28, 28, 28, 87, 87, 87,by bin medians: 21, 21, 21, 28, 28, 28, 108, 108, 108,by bin boundaries: 2, 25, 25, 26, 26,

15、30, 32, 120, 120,data: 4, 34, 15, 25, 28, 21, 8, 21, 24,Smoothing out noisy data (III),Clustering organize similar values into groups or clusters values falling out of the set of clusters may be regarded as outliers,Smoothing out noisy data (IV),Clustering organize similar values into groups or clus

16、ters values falling out of the set of clusters may be regarded as outliers,Smoothing out noisy data (V),Regression fit the data to a mathematical function values deviate from the expected values for some distance may be regarded as outliers,x,y,y = x + 1,x1,y1,y1,Smoothing out noisy data (VI),Combin

17、ed computer and human inspection use some measures to detect suspect values and then resort to and human to identify the actual errors or outliers better than manually searching through the entire database tedious may be infeasible,many data smoothing methods are also methods of data reduction invol

18、ving discretization concept hierarchy is a tool of data discretization which can be used for data smoothing some methods of classification have built-in data smoothing mechanisms,Smoothing out noisy data (VII),Some data inconsistencies may be corrected manually using external references e.g. errors

19、made at data entry may be corrected by performing a paper trace Knowledge engineering tools may also be used to detect the violation of known data constraints In general, correcting inconsistent data require great intervention of users,Correcting inconsistent data,Data Preprocessing,Data Preprocessi

20、ng: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Transformation Data Reduction Summary,Combine data from multiple sources into a coherent data store Schema integration entity identification problem: How can entities from multiple data sources be “matched up”? met

21、adata can be used to help avoid errors in schema integration Detection and resolution of data value conflicts semantic heterogeneity: for the same real world entity, attribute values from different sources may be different this may be due to differences in representation, scaling, or encoding e.g. k

22、ilometers vs. miles,Data integration (I),Handling redundancy Redundancy often occurs in the integration of multiple databases the same attribute may have different names in different databases an attribute may be redundant if it can be derived from other attributes some tuples may be duplicated some

23、 redundancies can be detected by correlation analysis the correlation between attributes A and B can be measured by,cor = 1 A and B are independent e.g. A: rain B: good TV program cor 1 A and B are positively correlated e.g. A: rain B: cloudy cor 1 A and B are negatively correlated e.g. A: rain B: s

24、unshine the higher the value of cor, the more each attribute implies the other,Data integration (II),Correlation Analysis (Nominal Data),2 (chi-square) test The larger the 2 value, the more likely the variables are related The cells that contribute the most to the 2 value are those whose actual coun

25、t 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,Chi-Square Calculation: An Example,2 (chi-square) calculation (numbers in parenthesis are expected co

26、unts calculated based on the data distribution in the two categories) It shows that like_science_fiction and play_chess are correlated in the group,450*300/1500=90,450*1200/1500=360,1050*300/1500=210,1050*1200/1500=840,Correlation Analysis (Numeric Data),Correlation coefficient (also called Pearsons

27、 product moment coefficient) where n is the number of tuples, and are the respective means of A and B, A and B are the respective standard deviation of A and B, and (aibi) is the sum of the AB cross-product. If rA,B0, A and B are positively correlated (As values increase as Bs). The higher, the stro

28、nger correlation. rA,B=0: independent; rA,B0: negatively correlated,Data integration (III),Visually Evaluating Correlation,Scatter plots showing the similarity from 1 to 1.,Correlation (viewed as linear relationship),Correlation measures the linear relationship between objects To compute correlation

29、, we standardize data objects, A and B, and then take their dot product,Covariance (Numeric Data),Covariance is similar to correlation,Correlation coefficient:,where n is the number of tuples, and are the respective mean or expected values of A and B, A and B are the respective standard deviation of

30、 A and B.,Covariance (Numeric Data),Positive covariance: If CovA,B0, then A and B both tend to be larger than their expected values. Negative covariance: If CovA,B0 then if A is larger than its expected value, B is likely to be smaller than its expected value. Independence: CovA,B=0 but the converse

31、 is not true: Some pairs of random variables may have a covariance of 0 but are not independent. Only under some additional assumptions (e.g., the data follow multivariate normal distributions) does a covariance of 0 imply independence,Covariance: An Example,Suppose two stocks A and B have the follo

32、wing values in one week: (2, 5), (3, 8), (5, 10), (4, 11), (6, 14). Question: If the stocks are affected by the same industry trends, will their prices rise or fall together? E(A) = (2 + 3 + 5 + 4 + 6)/ 5 = 20/5 = 4 E(B) = (5 + 8 + 10 + 11 + 14) /5 = 48/5 = 9.6 Cov(A, B) = (25+38+510+411+614)/549.6=

33、4 Thus, A and B rise together since Cov(A, B)0.,It can be simplified in computation as,Data Preprocessing,Data Preprocessing: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Transformation Data Reduction Summary,Normalization scale the attribute values to a small sp

34、ecified range Smoothing remove noise from the data Aggregation summarize the data or construct data cube from the data Generalization climb concept hierarchy,Data transformation,min-max normalization,comes from,preserves the relationship among the original data values may encounter “out of bounds” e

35、rror,Normalization (I),z-score normalization,particularly useful when the actual min and max of the attribute value are unknown, or when there are outliers dominating the min-max normalization change the original data,decimal scaling normalization,where j is the smallest integer such that max (|v|)

36、1 e.g. 986 0.986 very simple change the original data,Normalization (II),Data Preprocessing,Data Preprocessing: An Overview Major Tasks of Data Preprocessing Data Cleaning Data Integration Data Transformation Data Reduction Summary,Obtain a reduced representation of the data set that is much smaller

37、 in volume, yet produce the same (or almost same) analytical results Data reduction strategies: data cube aggregation dimension reduction data compression numerosity reduction discretization concept hierarchy generalization,Data reduction,Data cube aggregation (I),Aggregation operations are applied

38、to the data in the construction of a data cube Data cube is a lattice of cuboids the lowest level of a data cube store the aggregation for an individual entity of interest there are multiple levels of aggregation in a data cube each higher level of aggregation further reduces the data size use the s

39、mallest representation which is enough to solve the problem,Data cube aggregation (II),Data cube aggregation (III),D1, D2, D3,D1, D2,D1, D3,D2, D3,D2,ALL,Data cube aggregation (IV),D1,D3,Dimensionality reduction,Remove irrelevant attributes (or dimensions) from the data leaving out relevant attribut

40、es or keeping irrelevant attributes may be harmful to the mining routines the inclusion of irrelevant or redundant attributes may slow down the mining process attribute subset selection to find a minimum set of attributes such that the resulting probability distribution of the data classes is as clo

41、se as possible to the original distribution obtained using all the attributes heuristic methods which explore a reduced search space are commonly used the attributes are typically selected using evaluation measures such as statistical significance, information gain, etc.,Dimensionality reduction,Ste

42、p-wise forward selection select the best of the original attributes select the best of the remaining original attributes initial attribute set: A1, A2, A3, A4, A5, A6 initial reduced set: step 1: A1 step 2: A1, A4 step 3: A1, A4, A6,Attribute subset selection (I),Step-wise backward elimination elimi

43、nate the worst of the original attributes eliminate the worst of the remaining original attributes initial attribute set: A1, A2, A3, A4, A5, A6 initial reduced set: A1, A2, A3, A4, A5, A6 step 1: A1, A3, A4, A5, A6 step 2: A1, A4, A5, A6 step 3: A1, A4, A6,Attribute subset selection (II),Combined f

44、orward selection and backward elimination select the best of the original attributes and eliminate the worst of the remaining original attributes initial attribute set: A1, A2, A3, A4, A5, A6 initial reduced set: A1, A2, A3, A4, A5, A6 step 1: A1, A3, A4, A5, A6 step 2: A1, A4, A5, A6 step 3: A1, A4

45、, A6,Attribute subset selection (III),Decision tree induction train a decision tree remove the attributes that have not appeared in the tree initial attribute set: A1, A2, A3, A4, A5, A6,reduced set: A1, A4, A6,A4?,A1?,Class1,Class1,Class2,Class2,A6?,y,n,y,y,n,n,Attribute subset selection (IV),Origi

46、nal Data,Data compression (I),Data encoding or transformations are applied so as to obtain a reduced or compressed representation of the original data lossless compression（无损压缩）: if original data can be reconstructed from the compressed data without any loss of information lossy compression（有损压缩）: i

47、f only an approximation of the original data can be reconstructed from the compressed data e.g. wavelet, PCA although there are several well-tuned lossless string compression algorithms, they allow only limited manipulation of the data popular and effective compression algorithms are often lossy,Dat

48、a compression (II),Discrete Wavelet Transform (DWT): linear signal processing technique 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,general algorithm l

49、ength, L, must be an integer power of 2 (padding with 0s, when necessary) each transform involves two functions: smoothing and difference applies to pairs of data, resulting in two sets of data of length L/2 applies two functions recursively, until reaches the desired length,Wavelet transformation (

50、I),DWT for Image Compression,Wavelet transformation (II),Image,search for c best k-dimensional principal components, i.e. orthogonal vectors create a new coordinates based on the principal components each original data is a linear combination of the c principal components general algorithm normalize

51、 original data compute N principal components, i.e. orthogonal vectors that provide a basis for the normalized data sort the principal components according to decreasing order of “significance” eliminate the weaker principal components,Principal component analysis,Numerosity reduction,Reduce the dat

52、a volume by choosing alternative, “smaller” form of data representation parametric use a mathematical model to fit the data, so that only the parameters of the data need to be stored non-parametric histogram, clustering, sampling, etc.,Numerosity reduction,linear regression data are modeled to fit a

53、 straight line,log-linear model approximate discrete multidimensional probability distribution,multiple regression a response variable Y is modeled as a linear function of multiple features,Regression and Log-linear models,Partition the data distribution into disjoint buckets equi-depth each bucket

54、contains roughly same frequency of values equi-width each bucket contains roughly same range of values v-optimal the histogram with the least variance histogram variance is the weighted sum of the variance of the original values that each bucket contains maxdiff bucket boundary is established betwee

55、n each pair for pairs having the -1 largest differences determines the number of buckets,Histograms (I),an example: partition 1, 5, 8, 10 into 3 buckets,equi-depth 1 5 8, 10 or 1 5, 8 10 or 1, 5 8 10,equi-width 1 5 8, 10 in fact: 1, 3.3), 3.3, 6.6), 6.6, 10,maxdiff 1 5 8, 10,v-optimal 1 5 8, 10 beca

56、use,for 1, 5, 8, 10 v = 0 + 0 + 1/2 2 = 1 for 1, 5, 8, 10 v = 0+1/24.5+ 0 = 2.25 for 1, 5, 8, 10 v = 1/28 + 0 + 0 = 4,in general, v-optimal and maxdiff histograms are more accurate histograms for single attributes can be generalized to multidimensional histograms,Histograms (II),Partition the object

57、s into clusters, so that objects within a cluster are similar to each other while dissimilar to objects in other clusters,the quality of a cluster may be measured by: diameter: the maximum distance between any two objects in the cluster centroid distance: the average distance of each cluster object

58、from the cluster centroid,Clustering,Use a much smaller random sample to represent a large data set,simple random sampling without replacement (SRSWOR),simple random sampling with replacement (SRSWR),Sampling (I),cluster sampling,stratified sampling,Sampling (II),Reduce the number of values for a gi

59、ven continuous attribute by dividing the range of the attribute into intervals. Interval labels can then be used to replace actual data values Types of attributes: categorical (nominal) continuous (numerical) or unordered ordered,Discretization,Concept hierarchies can be used to reduce the data by replacing low level concepts with higher level concepts,Concept hierarchies can be automatically gener