University:
California State University, Northridge
Course:
ME 209 | Programming for Mechanical Engineers
Academic year:

2011
Views:

463

Pages:

19
Author:

Maxwell Davies

Data Discretization • R Reduce d th number the b off values l ffor a given i continuous attribute by dividing the range of the attribute into intervals • Interval labels can then be used to replace actual t ld data t values l • Split (top‐down) vs. merge (bottom‐up) • Discretization can be performed recursively on an attribute 49/51 Why Discretization is Used? • Reduce data size. • Transforming quantitative data to qualitative data. 50 Interval Merge by χ2 Analysis • Merging‐based (bottom‐up) • Merge: Find the best neighboring intervals and merge them to form larger intervals recursively • ChiMerge [Kerber AAAI 1992, See also Liu et al. DMKD 2002] 51/51 • Initially, each distinct value of a numerical attribute A is considered to be one interval • χ 2 tests are performed for every pair of adjacent intervals • Adjacent intervals with the least χ 2 values are merged together, since low χ 2 values for a pair indicate similar class distributions • This merge process proceeds recursively until a predefined stopping criterion is met 52 Entropy-Based Entropy Based Discretization • The goal of this algorithm is to find the split with the maximum information gain. • The boundary that minimizes the entropy over all possible boundaries is selected • The process is recursively applied to partitions obtained until some stopping criterion is met • Such h a boundary b d may reduce d d data size and d improve classification accuracy 53/51 What is Entropy? • The entropy is a measure of the uncertainty associated with ith a random d variable i bl • As uncertainty and or randomness increases for a result set so does the entropy • Values range from 0 – 1 to represent the entropy of information 54 Entropy Example 55 Entropy py Example p 56 Entropy py Example p (cont’d) ( ) 57 Calculatingg Entropy py For m classes: m Entropy ( S ) = − ∑ pi log 2 pi For 2 classes: i =1 Entropy ( S ) = − p1 log 2 p1 − p2 log 2 p2 • Calculated based on the class distribution of the samples in set S. • pi is the probability of class i in S • m is the number of classes (class values) 58 Calculatingg Entropy py From Split p • Entropy of subsets S1 and S2 are calculated. calculated • The calculations are weighted by their probability of being in set S and summed. • In formula below, – S is the set – T is the value used to split S into S1 and S2 E (S , T ) = S1 S Entropy ( S1 ) + S2 S Entropy ( S 2 ) 59 Calculatingg Information Gain • IInformation f ti Gain G i = Difference Diff iin entropy t b between t original set (S) and weighted split (S1 + S2) Gain( S , T ) = Entopy ( S ) − E ( S , T ) Gain( S ,56) = 0.991076 − 0.766289 Gain( S ,56) = 0.224788 0 224788 compare to Gain( S ,46) = 0.091091 60 Numeric Concept Hierarchy • A concept hierarchy for a given numerical attribute defines a discretization of the attribute • Recursively reduce the data by collecting and replacing low level concepts by higher level concepts 61 A Concept Hierarchy for the Attribute Price Figure 2.22. A concept hierarchy for the attribute price. 62/51 Segmentation by Natural Partitioning • A simply 3‐4‐5 rule can be used to segment numeric data into relatively l l uniform, f “natural” “ l” intervals l – – – If an interval covers 3, 6, 7 or 9 distinct values at the most significant digit, partition the range into 3 equi‐width intervals If it covers 2, 4, or 8 distinct values at the most significant digit, partition the range into 4 intervals If it covers 1,, 5,, or 10 distinct values at the most significant g digit, g , partition the range into 5 intervals 63/51 Fig gure 2.23. Automattic generation of a concep pt Hie erarchy fo or profit based b on 3-4-5 rule e. 64 Concept Hierarchy Generation for C t Categorical i l Data D t • Specification of a partial ordering of attributes explicitly at the schema level by users or experts • Specification of a portion of a hierarchy by explicit data grouping • Specification of a set of attributes, but not of their partial ordering 65 Automatic Concept Hierarchy Generation country 15 distinct valules province or state 365 distinct values city 3,567 distinct values street 674,339 distinct values Based on the number of distinct values per attributes attributes, p p.95 95 66 Data preprocessing Data cleaning Missing values Use the most probable value to fill in the missing value (and five other methods) Noisy data Binning; Regression; Clusttering Data integration Entity ID problem Metadata Redundancy Correlation analysis (Correlation coefficient, coefficient chi‐square chi square test) Data trasnformation Smoothing Data cleaning Aggregation Data reduction Generailization Data reduction Normalization Min‐max; z‐score; decimal scaling Attribute Construction Data reduction Data cube aggregation Data cube store multidimensional aggregated information Attribute subset selection Stepwise forward selection; stepwise backward selection; combination; decision tree induction Dimensionality reduction Discrete wavelet trasnforms (DWT); Principle components analysis (PCA); Numerosity Reduction Regression and log‐linear models; histograms; clustering; sampling Data discretization Binning; Bi i historgram hi t analysis; l i entropy‐based t b d discretization; di ti ti Interval merging by chi‐square analysis; cluster analysis; intuitive partitioning Concept hierarchy Concept hierarchy generation 67

Data Discretization

of 19

Description

Free up your schedule!

Take 5 seconds to unlock