CST 466 exam help data mining mod2.pptx

Data mining is a crucial discipline within the field of data science, focusing on extracting useful patterns, trends, and insights from large datasets. It encompasses various techniques and algorithms aimed at discovering hidden patterns and relationships that can be used to make informed decisions and predictions.

At its core, data mining involves several key steps. Firstly, it begins with data preparation, where raw data is cleaned, transformed, and formatted to ensure its suitability for analysis. This step is critical as the quality of the data directly impacts the effectiveness of mining algorithms.

The next stage involves choosing appropriate data mining techniques. These techniques can broadly be categorized into several types, including classification, clustering, regression, association rule mining, and anomaly detection. Each type serves different purposes: classification predicts categorical labels, clustering groups similar data points, regression models continuous variables, association rule mining discovers relationships between variables, and anomaly detection identifies outliers.

Supporting these techniques are various algorithms. For instance, decision trees, naive Bayes, k-nearest neighbors (k-NN), and support vector machines (SVM) are common in classification tasks, while k-means and hierarchical clustering are prevalent in clustering tasks. These algorithms employ mathematical models and statistical methods to uncover patterns within data.

Furthermore, data mining incorporates advanced concepts like feature selection, which helps in identifying the most relevant variables for analysis, and ensemble methods that combine multiple models to enhance prediction accuracy. Additionally, data mining often intersects with machine learning, utilizing algorithms that iteratively learn from data to improve performance over time.

Ethical considerations are integral to data mining practices, especially concerning privacy, bias mitigation, and transparency. As data mining often involves sensitive information, ensuring compliance with regulations like GDPR and maintaining ethical standards is paramount.

In practical applications, data mining finds diverse uses across industries. In retail, it aids in market basket analysis to understand customer purchasing behavior. In healthcare, it supports clinical decision-making by predicting patient outcomes. Financial institutions employ it for fraud detection, while manufacturing utilizes it for process optimization and quality control.

Looking ahead, the future of data mining lies in handling ever-growing datasets, integrating with artificial intelligence for automated decision-making, and advancing interpretability to enhance trust in model outputs. As technologies evolve, data mining remains pivotal in extracting actionable insights from data to drive innovation and solve complex challenges across various domains.

In conclusion, data mining stands as a cornerstone of data-driven decision-ma

1. 1 Module - 2 (Data Preprocessing) Data Preprocessing-Need of data preprocessing, Data Cleaning- Missing values , Noisy data, Data Integration and Transformation, Data Reduction-Data cube aggregation, Attribute subset selection, Dimensionality reduction, Numerosity reduction, Discretization and concept hierarchy generation.

2. 2 Data Preprocessing It is a datamining technique that involves transforming raw data into understandable format. Need of data preprocessing Data in the real world is dirty incomplete : lacking attribute values, lacking certain attributes of interest, or containing only aggregate data e.g., occupation=“ ” noisy : containing errors or outliers e.g., Salary=“-10” inconsistent : containing discrepancies in codes or names e.g., Age=“42” Birthday=“03/07/1997” e.g., Was rating “1,2,3”, now rating “A, B, C” e.g., discrepancy between duplicate records

3. Major Tasks in Data Preprocessing

4. Why Is Data Preprocessing Important ? No quality data, no quality mining results! Quality decisions must be based on quality data e.g., duplicate or missing data may cause incorrect or even misleading statistics. Data warehouse needs consistent integration of quality data Data extraction, cleaning, and transformation comprises the majority of the work of building a data warehouse 4

5. Explain data cleaning/handling missing data/noisy data Data cleaning tasks Fill in missing values Identify outliers and smooth out noisy data Correct inconsistent data Resolve redundancy caused by data integration 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 Missing data may be due to equipment malfunction inconsistent with other recorded data and thus deleted data not entered due to misunderstanding certain data may not be considered important at the time of entry not register history or changes of the data Missing data may need to be inferred .

6. How to Handle Missing Data? Ignore the tuple: usually done when class label is missing (assuming the tasks in classification—not effective when the percentage of missing values per attribute varies considerably. Fill in the missing value manually: tedious + infeasible Use a global constant to fill in the missing value: e.g., “unknown”, NULL,a new class?! Use the attribute mean to fill in the missing value: For example, suppose that the average income of AllElectronics shop is $56,000. Use this value to replace the missing value for income 6 5. Use the attribute mean or median for all samples belonging to the same class as the given tuple: For example, if classifying customers according to credit risk, we may replace the missing value with the mean income value for customers in the same credit risk category as that of the given tuple. 6. Use the most probable value to fill in the missing value: This may be determined with regression, inference-based tools using a Bayesian formalism, or decision tree induction. For example, using the other customer attributes in your data set, you may construct a decision tree to predict the missing values for income. Methods 3 through 6 bias the data—the filled-in value may not be correct. Method 6, however, is a popular strategy.

7. Noisy Data Noise: random error or variance in a measured variable Incorrect attribute values may due to faulty data collection instruments data entry problems data transmission problems technology limitation inconsistency in naming convention Other data problems which requires data cleaning duplicate records incomplete data inconsistent data 7

8. How to Handle Noisy Data? Binning First sort data and partition into (equal-frequency) bins then one can smooth by bin means, smooth by bin median, smooth by bin boundaries, etc. Regression Smooth by fitting the data into regression functions Clustering Detect and remove outliers Combined computer and human inspection Detect suspicious values and check by human (e.g., deal with possible outliers) 8

9. Binning Methods: Bin depth =3 First sort data and partition into (equal-frequency) bins then one can smooth by bin means, smooth by bin median, smooth by bin boundaries, etc.

10. 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34,bin =4 Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34 * Partition into equal-frequency ( equi -depth) bins: - Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bin 3: 26, 28, 29, 34 * Smoothing by bin means: - Bin 1: 9, 9, 9, 9 - Bin 2: 23, 23, 23, 23 - Bin 3: 29, 29, 29, 29 * Smoothing by bin boundaries: - Bin 1: 4, 4, 4, 15 - Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 34

11. 8,16,9,15,21,21,24,30,26,27,30,34 bin depth=4

12. 13 Data Integration and Transformation Data integration: Data mining often requires data integration—the merging of data from multiple data stores/ combines data from multiple sources Careful integration can help reduce and avoid redundancies and inconsistencies in the resulting data set This can help improve the accuracy and speed of subsequent data mining process

13. Issues in data integration : Entity identification problem: identify real world entities from multiple data sources, Schema integration and object matching can be tricky. How can equivalent real-world entities from multiple data sources be matched up? This is referred to as the entity identification problem. e.g., A.Empno  B.Empid Examples of metadata for each attribute include the name, meaning, data type, and range of values permitted for the attribute, and null rules for handling blank, zero, or null values. Such metadata can be used to help avoid errors in schema integration .

14. 2. Data Value Conflict Detection and Resolution Data integration also involves the detection and resolution of data value conflicts. For example, for the same real-world entity, attribute values from different sources may differ. This may be due to differences in representation, scaling, or encoding eg1:a weight attribute may be stored in metric units in one system and British imperial units in another. Eg 2: One university may adopt a quarter system, offer three courses on database systems, and assign grades from A+ to F, whereas another may adopt a semester system, offer two courses on databases, and assign grades from 1 to 10.

15. 3. Tuple Duplication In addition to detecting redundancies between attributes, duplication should also be detected at the tuple level (e.g., where there are two or more identical tuples for a given unique data entry case). 4 . Redundancy and Correlation Analysis Redundancy is another important issue in data integration. An attribute (such as annual revenue, for instance) may be redundant if it can be “derived” from another attribute or set of attributes. Inconsistencies in attribute or dimension naming can also cause redundancies in the resulting data set. Some redundancies can be detected by correlation analysis. Handling Redundancy: correlation coefficient(check 2 attribute are related ) covariance(check 2 attribute are different) Redundancy check / correlation test for nominal data is done by χ 2 (chi- square) test 16

16. 17

17. 18 Q:Suppose that a group of 1500 people was surveyed. The gender of each person was noted. Each person was polled as to whether his or her preferred type of reading material was fiction or nonfiction. Thus, we have two attributes, gender and preferred reading. The observed frequency (or count) of each possible joint event is summarized in the contingency table, where the numbers in parentheses are the expected frequencies, the expected frequency for the cell (male, fiction) is,

18. 19

19. 20 For this 2 × 2 table, the degrees of freedom are : (r-1)(c-1)= (2 – 1)/(2 – 1)=1. For 1 degree of freedom, the χ2 value needed to reject the hypothesis at the 0.001 significance level is 10.827. Since our computed value is above this, we can reject the hypothesis that gender and preferred reading are independent and conclude that the two attributes are (strongly) correlated for the given group of people.

20. Since our computed value is above this, we can reject the hypothesis ,so they are independent and conclude that the two attributes are (strongly) correlated.

21. Correlation Coefficient for Numeric Data For numeric 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 ). This is,   where n is the number of tuples, ai and bi are the respective values of A and B in tuple i , A’ and B’ are the respective mean values of A and B, σA and σB are the respective standard deviations of A and B. Value of r=0 (no relation, they are independent) Value of r<0(- vely correlated) Value of r>0(+ vely correlated) 23

22. Covariance of Numeric Data How much two attribute change together 24

23. Data Transformation: Smoothing : remove noise from data Attribute/feature construction New attributes constructed from the given ones Aggregation: summarization help in constructing data cube(so helpful in OLAP operation) Sales data may be aggregated to compute monthly and annual total amount Generalization : concept hierarchy climbing Low level concept are replaced with higher-level Street citycountry Normalization : attributes are normalized or scaled to fall within a small, specified range 25 binning regression clustering

24. Data Transformation: Normalization min-max normalization: transform original data linearly z-score normalization normalization by decimal scaling   26 Where j is the smallest integer such that Max(| |)<1

25. Min-max normalization Example Suppose that the minimum and maximum values for the attribute income are $12,000 and $98,000, respectively. We would like to map income to the range [0.0;1.0]. By min-max normalization, a value of $73,600 for income is transformed to   27 Q:normalize the following group of data: 1000,2000,3000,5000,9000 min-max normalization by setting min=0 and max=1 Ans: 0, 0.125, 0.25, 0.5, 1

26. z-score normalization Example Suppose that the mean and standard deviation of the values for the attribute income are $54,000 and $16,000, respectively. With z-score normalization, a value of $73,600 for income is transformed to Q:normalize the following group of data: 1000,2000,3000,5000,9000 using z-score normalization Mean =1000+2000+3000+5000+9000/5=4000 Standard deviation=   28

27. Decimal scaling example Suppose that the recorded values of A range from -986 to 917. The maximum absolute value of A is 986. To normalize by decimal scaling, we therefore divide each value by 1,000 (i.e., j = 3) so that -986 normalizes to -0.986 and 917 normalizes to 0.917. Q: normalize by decimal scaling{-99,9} Here J=2 so divide each value by 10 2 So it will{-0.99,0.09} Q: normalize by decimal scaling{-273,4866} 30

28. Data Reduction Strategies Why data reduction? A database/data warehouse may store terabytes of data Complex data analysis/mining may take a very long time to run on the complete data set Data reduction Obtain a reduced representation of the data set that is much smaller in volume but yet produce the same (or almost the same) analytical results 32

29. Data Reduction Strategies Data cube aggregation It is a process in which information is gathered and expressed in a summary form. Data cube Stores multi-dimensional aggregated information. Attribute subset selection irrelevant, weakly relevant, or redundant attributes or dimensions may be detected and removed. Data Compression- Data encoding or transformations are applied so as to obtain a reduced or compressed representation of original data 1.Lossless – with out any loss of information 2.Lossy – approximation of original data Dimensionality reduction - e.g., remove unimportant attributes Numerosity reduction - e.g., fit data into models Discretization and concept hierarchy generation

30. 2. Attribute subset selection techniques Step-wise forward selection Step-wise backward elimination Combining forward selection and backward elimination Decision-tree induction

31. Combining forward selection and backward elimination(bi-directional selection and elimination)

32. 3.Data Compression Data encoding or transformations are applied so as to obtain a reduced or compressed representation of original data 1.Lossless – with out any loss of information eg : string compression using Huffman encoding 2.Lossy – approximation of original data . Eg : audio or video compression Original data Original data approximated COMPRESSED DATA lossless lossy

33. Curse of dimensionality When dimensionality increases, data becomes increasingly sparse Density and distance between points, which is critical to clustering, outlier analysis, becomes less meaningful The possible combinations of subspaces will grow exponentially 4. Dimensionality reduction

34. Dimensionality reduction Avoid the curse of dimensionality Help eliminate irrelevant features and reduce noise Reduce time and space required in data mining Allow easier visualization

35. Dimensionality reduction techniques: 1. Wavelet transforms : is a linear signal processing technique.When applied to a data vector D, transforms it into a numerically different vector, D’, of wavelets coefficients 2. Principal Component Analysis(PCA) Suppose that the data to be reduced consist of tuples or data vectors described by n attributes or dimensions. Principal components analysis, or PCA searches for k n-dimensional orthogonal vectors that can best be used to represent the data, where k ≤ n. The original data are thus projected onto a much smaller space, resulting in dimensionality reduction. Unlike attribute subset selection, which reduces the attribute set size by retaining a subset of the initial set of attributes, PCA “combines” the essence of attributes by creating an alternative, smaller set of variables. 39

36. Wavelet transforms The Discrete Wavelet Transform (DWT) is a linear signal processing technique. When applied to a data vector D, transforms it into a numerically different vector, D’, of wavelets coefficients [Fourier Transformation] These two vectors are of same length. removes noise by the help of Fourier Transformation ,without smoothing out the main features of the data, making it effective for data cleaning as well. All wavelet coefficients larger than some user defined threshold can be retained . The remaining coefficients set to zero. A compressed approximation of the data can be retained by storing only a small fraction of the strongest of the wavelet coefficients.

37. HAAR Wavelet Transformation Given input S=[2,2,0,2,3,5,4,4] reduce the input vector using HAAR Wavelet Transformation. check whether length is power of 2 else add 0. Forward transform vector: [ 2 3/4 , -1 1/4 , 1/2,0, 0,-1,-1,0] Resolution Average ( a+b )/2 Detail Coefficient (a-b)/2 8 [2,2,0,2,3,5,4,4] 4 [2,1,4,4] [0,-1,-1,0] 2 [1 1/2 , 4] [1/2,0] 1 [2 3/4 ] [-1 1/4 ]

38. 5.numerosity reduction techniques Replaces the original data with small form of data representation 2 methods: Parametric and Non parametric method Parametric : For parametric methods,its assumes a data model, model is used to estimate the data, so that typically only the data parameters need to be stored, instead of the actual data. Regression and log-linear models are examples . Non parametric method: Nonparametric methods , it doenot assumes a data model, Used for storing reduced representations of the data include histograms, clustering, sampling 43

39. Regression and Log-Linear Models In linear regression , the data are modeled to fit a straight line Y = α + β x, y (called a response variable) and x is predictor variable α and β (called regression coefficients) These coefficients can be solved for by the method of least squares. Multiple linear regression is an extension of (simple) linear regression, which allows a response variable, y, to be modelled as a linear function of two or more predictor variables. Log-linear models is a technique used in statistics to examine the relationship between more than two categorical variables. This allows a higher-dimensional data space to be constructed from lower-dimensional spaces. Log-linear models are therefore also useful for dimensionality reduction (since the lower dimensional points together typically occupy less space than the original data points) and data smoothing (since aggregate estimates in the lower-dimensional space are less subject to sampling variations than the estimates in the higher-dimensional space). . 44

40. Histograms: The following data are a list of prices of commonly sold items at AllElectronics (rounded to the nearest dollar). The numbers have been sorted: 1, 1, 5, 5, 5, 5, 5, 8, 8, 10, 10, 10, 10, 12, 14, 14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 30. 45 Histograms use binning to approximate data distributions and are a popular form of data reduction. A histogram for an attribute, A, partitions the data distribution of A into disjoint subsets, or buckets. If each bucket represents only a single attribute-value/frequency pair, the buckets are called singleton buckets

41. Histograms How are the buckets determined and the attribute values partitioned?” There are several partitioning rules, including the following: Equal-width : In an equal-width histogram, the width of each bucket range is uniform Equal-frequency (or equidepth ): In an equal-frequency histogram, the buckets are created so that, roughly, the frequency of each bucket is constant 46

42. Plot an equal-width histogram, the width of each bucket the width of $10 The numbers have been sorted: 1, 1, 5, 5, 5, 5, 5, 8, 8, 10, 10, 10, 10, 12, 14, 14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 30.

43. V-optimal: If we consider all of the possible histograms for a given number of buckets, the V-optimal histogram is the one with least variance. Histogram is a weighted sum of the all original values that each bucket represents, where bucket weight is equal to the number of values in the bucket. MaxDiff : In a MaxDiff histogram , we consider the difference between each pair of adjacent values. A bucket boundary is established between pair for pairs having k-1 largest differences, where k is user specified V-optimal and MaxDiff are most accurate and practical histograms.

44. Clustering Clustering techniques consider data tuples as objects. They partition the objects into groups or clusters, so that objects within a cluster are “similar” to one another and “dissimilar” to objects in other clusters. The “quality” of a cluster may be represented by its diameter , the maximum distance between any two objects in the cluster. Centroid distance is an alternative measure of cluster quality and is defined as the average distance of each cluster object from the cluster centroid In data reduction, the cluster representations of the data are used to replace the actual data. The effectiveness of this technique depends on the nature of the data. 51

45. Sampling Sampling can be used as a data reduction technique because it allows a large data set to be represented by a much smaller random sample (or subset) of the data. Simple random sample without replacement (SRSWOR) Simple random sample with replacement (SRSWR) Cluster sample Stratified sample 52

46. SRSWOR Simple random sample without replacement This is created by drawing s of the N tuples from D (s < N), where the probability of drawing any tuple in D is 1/N, that is, all tuples are equally likely to be sampled. SRSWR Simple random sample with replacement This is similar to SRSWOR, except that each time a tuple is drawn from D, it is recorded and then replaced. That is, after a tuple is drawn, it is placed back in D so that it may be drawn again. 53

47. Cluster sample If the tuples in D are grouped into M mutually disjoint “clusters,” then an SRS of s clusters can be obtained, where s < M. 54 Stratified sample If D is divided into mutually disjoint parts called strata, a stratified sample of D is generated by obtaining an SRS at each stratum

48. Data Discretization and Concept Hierarchy Generation Data discretization techniques can be used to reduce the number of values for a given continuous attribute by dividing the range of the attribute into intervals. AGE GROUP NUMBER OF PEOPLE(2020) % OF GLOBAL POPULATION <20 YEARS 2.6 billion 33.2% 20 -39YEARS 2.3 billion 29.9% 40 -59YEARS 1.8 billion 23.1% 60-79 YEARS 918 million 11.8% 80-99 YEARS 147 million 1.9% 100+ 0.6 million 0.01%

49. Data Discretization TYPES top-down discretization or splitting : If the process starts by first finding one or a few points (called split points or cut points) to split the entire attribute range, and then repeats this recursively on the resulting intervals, it is called top-down discretization or splitting. Bottom-up discretization or merging, which starts by considering all of the continuous values as potential split-points, removes some by merging neighborhood values to form intervals, and then recursively applies this process to the resulting intervals

50. Discretization for Numerical Data: Binning Histogram analysis Entropy-based discretization, Chi-square merging cluster analysis Decision tree analysis- discretization by intuitive partitioning.

51. Entropy is one of the most commonly used discretization measures. Entropy-based discretization is a supervised, top-down splitting technique. It explores class distribution information in its calculation and determination of split-points and recursively partitions the resulting intervals to arrive at a hierarchical discretization. The process is recursively applied to partition until stopping criteria is met It will reduce the data size and improve the classification accuracy Entropy-Based Discretization

52. Chi-square merging

53. Discretization by Intuitive Partitioning Although the above discretization methods are useful in the generation of numerical hierarchies, many users would like to see numerical ranges partitioned into relatively uniform, easy-to-read intervals that appear intuitive or “natural.” For example, annual salaries broken into ranges like ($50,000, $60,000] are often more desirable than ranges like ($51,263.98, $60,872.34], obtained by, say, some sophisticated clustering analysis. 60