数据挖掘课件：chap2-data.ppt

1、 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 1 Data Mining: DataLecture Notes for Chapter 2Introduction to Data MiningbyTan, Steinbach, Kumar Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 2 What is Data?lCollection of data objects and their attributeslAn attribute is a pr

2、operty or characteristic of an objectExamples: eye color of a person, temperature, etc.Attribute is also known as variable, field, characteristic, or featurelA collection of attributes describe an objectObject is also known as record, point, case, sample, entity, or instanceTid Refund Marital Status

3、 Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 AttributesObjects Tan,Steinbach, Kumar Introduction to Data Mining

4、 4/18/2004 3 Attribute ValueslAttribute values are numbers or symbols assigned to an attributelDistinction between attributes and attribute values Same attribute can be mapped to different attribute valuesu Example: height can be measured in feet or meters Different attributes can be mapped to the s

5、ame set of valuesu Example: Attribute values for ID and age are integersu But properties of attribute values can be different ID has no limit but age has a maximum and minimum value Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 4 Measurement of Length lThe way you measure an attribute i

6、s somewhat may not match the attributes properties.123557815104ABCDE Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 5 Types of Attributes l There are different types of attributes NominaluExamples: ID numbers, eye color, zip codes OrdinaluExamples: rankings (e.g., taste of potato chips o

7、n a scale from 1-10), grades, height in tall, medium, short IntervaluExamples: calendar dates, temperatures in Celsius or Fahrenheit. RatiouExamples: temperature in Kelvin, length, time, counts Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 6 Properties of Attribute Values lThe type of a

8、n attribute depends on which of the following properties it possesses: Distinctness: = Order: Addition: + - Multiplication: * / Nominal attribute: distinctness Ordinal attribute: distinctness & order Interval attribute: distinctness, order & addition Ratio attribute: all 4 propertiesAttribute TypeDe

9、scriptionExamplesOperationsNominalThe values of a nominal attribute are just different names, i.e., nominal attributes provide only enough information to distinguish one object from another. (=, )zip codes, employee ID numbers, eye color, sex: male, femalemode, entropy, contingency correlation, 2 te

10、stOrdinalThe values of an ordinal attribute provide enough information to order objects. ()hardness of minerals, good, better, best, grades, street numbersmedian, percentiles, rank correlation, run tests, sign testsIntervalFor interval attributes, the differences between values are meaningful, i.e.,

11、 a unit of measurement exists. (+, - )calendar dates, temperature in Celsius or Fahrenheitmean, standard deviation, Pearsons correlation, t and F testsRatioFor ratio variables, both differences and ratios are meaningful. (*, /)temperature in Kelvin, monetary quantities, counts, age, mass, length, el

12、ectrical currentgeometric mean, harmonic mean, percent variationAttribute LevelTransformationCommentsNominalAny permutation of valuesIf all employee ID numbers were reassigned, would it make any difference?OrdinalAn order preserving change of values, i.e., new_value = f(old_value) where f is a monot

13、onic function.An attribute encompassing the notion of good, better best can be represented equally well by the values 1, 2, 3 or by 0.5, 1, 10.Intervalnew_value =a * old_value + b where a and b are constantsThus, the Fahrenheit and Celsius temperature scales differ in terms of where their zero value

14、 is and the size of a unit (degree).Rationew_value = a * old_valueLength can be measured in meters or feet. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 9 Discrete and Continuous Attributes lDiscrete Attribute Has only a finite or countably infinite set of values Examples: zip codes, c

15、ounts, or the set of words in a collection of documents Often represented as integer variables. Note: binary attributes are a special case of discrete attributes lContinuous Attribute Has real numbers as attribute values Examples: temperature, height, or weight. Practically, real values can only be

16、measured and represented using a finite number of digits. Continuous attributes are typically represented as floating-point variables. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 10 Types of data sets lRecordData MatrixDocument DataTransaction DatalGraphWorld Wide WebMolecular Structu

17、reslOrderedSpatial DataTemporal DataSequential DataGenetic Sequence Data Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 11 Important Characteristics of Structured Data Dimensionalityu Curse of Dimensionality Sparsityu Only presence counts Resolutionu Patterns depend on the scale Tan,Stei

18、nbach, Kumar Introduction to Data Mining 4/18/2004 12 Record Data lData that consists of a collection of records, each of which consists of a fixed set of attributes Tid Refund Marital Status Taxable Income Cheat 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No 5 No

19、 Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 10 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 13 Data Matrix lIf data objects have the same fixed set of numeric attributes, then the data objects can be thought

20、of as points in a multi-dimensional space, where each dimension represents a distinct attribute lSuch data set can be represented by an m by n matrix, where there are m rows, one for each object, and n columns, one for each attribute1.12.216.226.2512.651.22.715.225.2710.23Thickness LoadDistanceProje

21、ction of y loadProjection of x Load1.12.216.226.2512.651.22.715.225.2710.23Thickness LoadDistanceProjection of y loadProjection of x Load Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 14 Document DatalEach document becomes a term vector, each term is a component (attribute) of the vecto

22、r, the value of each component is the number of times the corresponding term occurs in the document. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 15 Transaction DatalA special type of record data, where each record (transaction) involves a set of items. For example, consider a grocery

23、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 Tan,Steinbach

24、, Kumar Introduction to Data Mining 4/18/2004 16 Graph Data lExamples: Generic graph and HTML Links 521 25Data Mining Graph Partitioning Parallel Solution of Sparse Linear System of Equations N-Body Computation and Dense Linear System Solvers Tan,Steinbach, Kumar Introduction to Data Mining 4/18/200

25、4 17 Chemical Data lBenzene Molecule: C6H6 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 18 Ordered Data lSequences of transactionsAn element of the sequenceItems/Events Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 19 Ordered Data l Genomic sequence dataGGTTCCGCCTTCAGCCCCG

26、CGCCCGCAGGGCCCGCCCCGCGCCGTCGAGAAGGGCCCGCCTGGCGGGCGGGGGGAGGCGGGGCCGCCCGAGCCCAACCGAGTCCGACCAGGTGCCCCCTCTGCTCGGCCTAGACCTGAGCTCATTAGGCGGCAGCGGACAGGCCAAGTAGAACACGCGAAGCGCTGGGCTGCCTGCTGCGACCAGGG Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 20 Ordered DatalSpatio-Temporal DataAverage Monthly

27、Temperature of land and ocean Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 21 Data Quality lWhat kinds of data quality problems?lHow can we detect problems with the data? lWhat can we do about these problems? lExamples of data quality problems: Noise and outliers missing values duplica

28、te data Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 22 NoiselNoise refers to modification of original values Examples: distortion of a persons voice when talking on a poor phone and “snow” on television screenTwo Sine WavesTwo Sine Waves + Noise Tan,Steinbach, Kumar Introduction to Da

29、ta Mining 4/18/2004 23 OutlierslOutliers are data objects with characteristics that are considerably different than most of the other data objects in the data set Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 24 Missing ValueslReasons for missing values Information is not collected (e.g

30、., 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)lHandling missing values Eliminate Data Objects Estimate Missing Values Ignore the Missing Value During Analysis Replace with all possible values (weighted

31、 by their probabilities) Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 25 Duplicate DatalData set may include data objects that are duplicates, or almost duplicates of one another Major issue when merging data from heterogeous sourceslExamples: Same person with multiple email addressesl

32、Data cleaning Process of dealing with duplicate data issues Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 26 Data PreprocessinglAggregationlSamplinglDimensionality ReductionlFeature subset selectionlFeature creationlDiscretization and BinarizationlAttribute Transformation Tan,Steinbach,

33、 Kumar Introduction to Data Mining 4/18/2004 27 AggregationlCombining two or more attributes (or objects) into a single attribute (or object)lPurpose Data reductionu Reduce the number of attributes or objects Change of scaleu Cities aggregated into regions, states, countries, etc More “stable” datau

34、 Aggregated data tends to have less variability Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 28 AggregationStandard Deviation of Average Monthly PrecipitationStandard Deviation of Average Yearly PrecipitationVariation of Precipitation in Australia Tan,Steinbach, Kumar Introduction to D

35、ata Mining 4/18/2004 29 Sampling lSampling is the main technique employed for data selection. It is often used for both the preliminary investigation of the data and the final data analysis. lStatisticians sample because obtaining the entire set of data of interest is too expensive or time consuming

36、. lSampling is used in data mining because processing the entire set of data of interest is too expensive or time consuming. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 30 Sampling lThe key principle for effective sampling is the following: using a sample will work almost as well as u

37、sing 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 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 31 Types of SamplinglSimple Random Sampling There is an equal probabili

38、ty of selecting any particular itemlSampling without replacement As each item is selected, it is removed from the populationlSampling with replacement Objects are not removed from the population as they are selected for the sample. u In sampling with replacement, the same object can be picked up mor

39、e than oncelStratified sampling Split the data into several partitions; then draw random samples from each partition Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 32 Sample Size 8000 points 2000 Points500 Points Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 33 Sample SizelW

40、hat sample size is necessary to get at least one object from each of 10 groups. Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 34 Curse of DimensionalitylWhen dimensionality increases, data becomes increasingly sparse in the space that it occupieslDefinitions of density and distance betw

41、een points, which is critical for clustering and outlier detection, become less meaningful Randomly generate 500 points Compute difference between max and min distance between any pair of points Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 35 Dimensionality ReductionlPurpose: Avoid cur

42、se of dimensionality Reduce amount of time and memory required by data mining algorithms Allow data to be more easily visualized May help to eliminate irrelevant features or reduce noiselTechniques Principle Component Analysis Singular Value Decomposition Others: supervised and non-linear techniques

43、 Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 36 Dimensionality Reduction: PCAlGoal is to find a projection that captures the largest amount of variation in datax2x1e Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 37 Dimensionality Reduction: PCAlFind the eigenvectors of th

44、e covariance matrixlThe eigenvectors define the new spacex2x1e Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 38 Dimensionality Reduction: ISOMAPlConstruct a neighbourhood graphlFor each pair of points in the graph, compute the shortest path distances geodesic distancesBy: Tenenbaum, de

45、Silva, Langford (2000) Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 39 Dimensions = 10Dimensions = 40Dimensions = 80Dimensions = 120Dimensions = 160Dimensions = 206Dimensionality Reduction: PCA Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 40 Feature Subset SelectionlAnoth

46、er way to reduce dimensionality of datalRedundant features duplicate much or all of the information contained in one or more other attributes Example: purchase price of a product and the amount of sales tax paidlIrrelevant features contain no information that is useful for the data mining task at ha

47、nd Example: students ID is often irrelevant to the task of predicting students GPA Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 41 Feature Subset SelectionlTechniques: Brute-force approch:uTry all possible feature subsets as input to data mining algorithm Embedded approaches:u Feature

48、selection occurs naturally as part of the data mining algorithm Filter approaches:u Features are selected before data mining algorithm is run Wrapper approaches:u Use the data mining algorithm as a black box to find best subset of attributes Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004

49、 42 Feature CreationlCreate new attributes that can capture the important information in a data set much more efficiently than the original attributeslThree general methodologies: Feature Extractionu domain-specific Mapping Data to New Space Feature Constructionu combining features Tan,Steinbach, Ku

50、mar Introduction to Data Mining 4/18/2004 43 Mapping Data to a New SpaceTwo Sine WavesTwo Sine Waves + NoiseFrequencylFourier transformlWavelet transform Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 44 Discretization Using Class LabelslEntropy based approach3 categories for both x and