Chapter 1.1 What is data mining?

Data mining is the process of automatically discovering useful information in large repositories.

Knowledge discovery in databases (KDD) is the overall process of converting raw data into useful information. Data mining is an integral part of KDD.

Preprosessing in advance of processing do feature selection, dimensionality reduction, normalization data subsetting. Make the data into an appropriate format, reduce noise etc. Postprocessing filtering patterns, visualization, pattern interpretation. Only useful and valid results are incorporated into an decision support system (DSS).

Chapter 1.2 Motivating challenges

Scalability Algorithms must support growing data sets.

High dimensionality The algorithms must support the complexity that increases when the high dimensionality (number of features) increases.

Heterogeneous and complex data We need techniques for heterogeneous attributes and complex data models.

Data ownership and distribution sometimes the data needed is not owned or stored in one location/organization. Requires distributed data mining techniques. The chalenge is to find out how to reduce communication in distribution, and how to effectively consolidate the result. There are also of course data security issues.

Non-traditional analysis non traditional methods, types of data and data distribution.

Chapter 1.3 The origins of data mining

Data mining draws upon ideas from sampling, estimation hypothesis testing from Statistics. and search algorithms, modeling techniques and learning theories from AI, pattern recognition, machine learning. Other areas: optimization, evolutionary computing, information theory, signal processing, visualization, information retrieval. Others: database systems, (parallell) computing (for massive data sets), distributed techniques.

Chapter 1.4 Data mining tasks

Two categories: _Predictive tasks _objective is to predict the value of a particular attribute (target/dependent variable) based on the values of other attributes (explanatory/independent variables).

Descriptive tasks objective is to derive patterns (correlations, trends, clusters, trajectories, anomalies) that summarize underlying relationships in data.

Predictive modeling building a model for target variable as a function of the explanatory variables. Two types of predictive modeling tasks: classification for discrete target variables. Regression for continuous target variables. The model should minimize the error between the predicted and the true values of the target variable.

Association analysis used to discover patterns that describe strongly associated features in the data. Patterns represented as implication rules or feature subsets. Extract the most interesting patterns in an efficient manner.

Anomaly detection the task of identifying observations whose characteristics are significantly different from the rest of the data. The observations are called anomalies/outliers. The goal is to find them and not label normal objects as anomalous.

Chapter 2.1 Types of data

Data set collection of data objects (records).

Data objects described by a number of attributes (variables).

Definition Attribute: is a property or characteristic of an object that may vary, either from one object to another (eye color) or from one time to another (temperature).

Definition Measurement scale: is a rule (function) that associates a numerical or symbolic value with an attribute of an object.

The values used to represent an attribute may have properties that are not properties of the attribute itself, and vice versa.

Attribute types (see table 2.2 p.26): nominal and ordinal (categorical/qualitative), interval and ratio (quantitative, numeric).

Permissible transformations are transformations that do not change the meaning of the attribute (table 2.3 p.27).

Number of values Describing attributes by the number of values - Discrete attribute has a finite/countable infinite set of values. - Special case: binary attributes - Continuous attributes have real number values (temperate, height, weight). represented in floating-point variables.

The number of values can be combined with attribute types, but all do not make sense. Example: Count attributes. Are both discrete(number of values) and ratio(attribute type).

Asymmetric attributes Only presence (non-zero attributes) are regarded as important. As a student who takes a course (1) or not (0) on a university. There are fewer 1´s than 0’s, so it is smarter to focus on the 1’s. Special case: asymmetric binary attributes. important for association analysis. special case: asymmetric discrete, asymmetric continuous attributes.

Data sets general characteristics - Dimensionality - the number of attributes that the object in the data set possess. Curse of dimensionality is issues with high dimensionality. Need reduction in preprocessing phase. - Sparsity - only process and store the non-zero values. - Resolution - capture data at different resolutions to avoid that patterns disappear because of noise etc.

Transaction (market basket) data a special type of record data. each record (transaction) involves a set of items. Like a super market basket.

The data matrix if the data objects in a collection of data all have the same fixed set of numeric attributes. Then the data objects can be thought of as points (vectors in a multidimensional space, where each dimension represents a distinct attribute describing the object. Matrix m,n where m rows for each object and n columns for each attribute. Special case: sparse data matrix, only non-zero attributes are important. Document-term matrix, is a sparse data matrix of a document where each word is an attribute and the order of the words are not important.

Group-based data A graph is a powerful and convenient representation of data.

data with relationships among objects Data often represented as a graph. Data objects are mapped to nodes of the graph, and relationships are paths between objects (with direction and weight). Example, The internet with web pages that links to other pages.

data with objects that are graphs If objects have structure (the object contains sub-objects with relationships) they are frequently represented as graphs. Example molecules. Substructure mining is a branch of data mining.

Ordered data Attributes have relationships that involve time or space.

Sequential data (temporal data) extension of record data where each record has a time associated with it. Example a transaction of groceries with timestamp.

Sequence data consists of a data set that is a sequence of individual entities (sequence of words, letters, etc.). Not timestamps but a position in an ordered sequence. Example DNA sequences (ATGC).

Time series data Special case of sequential data, but each record is a time series (series of measurements over time). Example average monthly tempratures of Minneapolis. temporal autocorrelation is important to consider: if two measurements are close in time, then their values are often similar.

Spatial data Positions, areas, etc. Example: weather data (several attributes for each geographical location). spatial autocorrelation (close points have same values).

Handling non-record data Most data mining algorithms are designed for record data. For non-record data, extract features from data objects and create records for each object. Does not capture all relationships (example time etc.)

Chapter 2.2 Data Quality

Because preventing data quality problems is typically not an option, data mining focuses on the detection and correction of data quality problems the use of algorithms that can tolerate poor data quality. First step of correction: data cleaning.

Measurement and data collection issues Data are not perfect: - Human error - Limitations of measuring devices - Flaws in data collection process - Missing data/data sets - Spurious or duplicate objects

Measurement and data collection error common problem: recorded value differs from true value. Numeric difference = error. Data collection error = omitting data objects/attribute values, inappropriately including a data object.

noise, artifacts: distortion of value, spurious object techniques from signal processing to discover patterns lost in the noise elimination of noise is difficult. Data mining algorithms must be robust, to produce good result even when noise is present. Artifacts are deterministic disortions of data, such as a streak in the same place on a set of photographs.

Precision, bias, accuracy: In statistics, quality of measurement process and resulting data is measured by precision and bias. precision: the closeness of repeated measurements (of the same quantity) to one another. Bias: a systematic variation of measurements from the quantity being measured. Accuracy: the closeness of measurements to the true value of the quantity being measured. depends on precision and bias. Significant digits, use only the number of digits specified in the data.

Outliers: data objects that, in some sense, have characteristics that are different from most of the other data objects in the data set values of an attribute that are unusual with respect to the typical values for that attribute “anomalous” objects noise and outliers are not the same outliers can be legitimate outliers can be of interest (fraud, network intrusion detection)

Missing values: - not collected, refused to be entered (age, weight), conditional parts of forms. - should be taken into account in data analysis. - strategies for dealing with missing data - eliminate data objects or attributes with missing values - (-) lose important information. - (+) simple and effective. - can be done with care (if the data set has only a few objects missing data, it can be expedient). - estimate missing values (reliably) - interpolation with remaining values - ignore the missing values during analysis - if the total number of attributes is high enough - if the number of missing values is low

Inconsistent values: Detect and, if possible, correct. It can be necessary to consult with an external source of information.

Duplicate data: or almost duplicates. To detect and eliminate, two main issues must be addressed: if there are two objects that actually represent a single object, then the values of corresponding attributes may differ, and these inconsistent values must be resolved. care needs to be taken to avoid accidentally combining data objects that are similar, but not duplicates. Such as two distinct people with identical names. Can cause problems for algorithms. Deduplication = dealing with the two issues.

Issues related to applications - Timeliness - some data age as soon as they are collected (snapshots of ongoing processes) - Relevance - Make sure that objects in data set are relevant. common problem: sampling bias - occurs when a samples does not contain different types of objects in proportion to their actual occurrence in the population. - example: survey data only describes only respondents. - Knowledge about the data - data that have documentation. - type of feature (nominal, ordinal, interval, ratio) - scale of measurement (meters, feet, etc.) - origin of data

Chapter 2.3 Data preprocessing

To make data more suitable for data mining. - aggregation - sampling - dimensionality reduction - feature subset selection - feature creation - discretization and binarization - variable transformation

Aggregation “less is more”. Combine two or more objects into one object. example: reduce transactions in a store one day to one common transaction. Issue: how are the data combined? Behaviour of groups of object is more stable than individual objects Lose information about interesting details.

Sampling Sampling is a commonly used approach for selecting a subset of the data objects to be analyzed. Statistics use sampling because entire data sets are expensive and time consuming to obtain. Data mining use sampling because the entire data set are expensive and time consuming to process. If sampling is representative, then it is almost as well as using the entire data set. representative if has approximately the same property of interest sampling is a statistically process

Sampling approaches simple random sampling - variation 1: sampling without replacement - variation 2: sampling with replacement - same object can be picked more than once - easier to analyse since the size of the data set is constant - can fail if population consists of different types of objects, with widely different numbers of objects. Might not get representation of all object types.

Stratified sampling - starts with prespecified groups of objects. - simple version: extract equal number of objects from each group - complex version: extract the number of objects from a group that is proportional to the size of the group

progressive sampling - size can be difficult to determine. sometimes adaptive or progressive sampling is therefore used. - start with small sample, increase til sufficient size has been obtained.

Dimensionality reduction Benefits: - many data mining algorithms work better if the dimensionality is lower - reduce noise - eliminate irrelevant features - more understandable model - more easily visualized - amount of time and memory required by an algorithm is reduced

Reduction often consists of techniques that replace attributes with a new attribute that is a combination of the old attributes (feature subset selection).

Two important topics: 1)the curse of dimensionality data is more complex to analyse as the dimensionality increases. - classification: - not enough data objects to allow the creation of a model that reliably assigns a class to all possible objects - clustering: - the definitions of density and the distance between points become less meaningful. Therefore a lot of algorithms have trouble with high-dimensional data. 2)Linear algebra techniques for dimensionality reduction Principal component analysis (PCA) - technique that for continuous attributes finds new attributes that - are linear combinations of the original attributes - are orthogonal to each other - capture the maximum amount of variation in the data - Singular Value Decomoposition (SVD) - related to PCA

Feature Subset Selection Use only a subset of the features. If redundant and irrelevant features are present, one does not lose information. - redundant features - duplicate much/all information contained in one or more other attributes. - irrelevant features - contain almost no useful information for the task at hand will reflect bias, objective at final algorithm. For n attributes there are 2n subsets. Impractical in most situations. Three standard approaches: 1. embedded 1. occurs naturally as part of the data mining algorithm. the algorithm decides what attributes to use, and what to ignore. 2. filter 1. features are selected before the algorithm runs. 3. wrapper 1. use the target algorithm as a black box to find best subset, but does not enumerate all possible subsets.

architecture for feature subset selection (filter/wrapper) feature selection process consists of: - measure for evaluating a subset - search strategy that controls the generation of a new subset of features - stopping criterion - validation procedure Filter (uses target algorithm) and wrapper (distinct from target algorithm) differs in the way they evaluate a subset.

flowchart of a feature subset selection process (figur i boken)

Stopping criterion is often based on 1+ conditions: - number of iterations - optimal value of the subset, or exceeds a threshold - certain size of subset - evaluation criteria has been achieved evaluation approach - run algorithm with both full data set and featured subset and compare results - run algorithm with different subsets and compare results

feature weighting more important features are assigned a higher weight. Sometimes based on domain knowledge, or can be determined automatically. Features with higher weighting plays a more important role in a model.

Feature extraction Creation of new set of features from the original raw data. Highly domain-specific. example image processing. Features and techniques to extract features are specific to fields.

mapping the data to a new space in example time series of data and if there is a number of periodic patterns and noise present, patterns are hard to detect. Fourier transform applied to the time series patterns can be detected. Underlying frequency information is explicit.

feature construction If the original feature is in a form not suitable for the data mining algorithm. One or more new features are constructed out of the original feature.

Discretization and binarization Some algorithms require data to be categorical attributes (classification) or binary attributes (association patterns). Continuous to categorical = discretization Continuous/discrete to binary = binarization If some categorical attribute has a large number of values, or if some values occur infrequently, it can be beneficial to reduce number of categories by combining values.

Binarization Simple techniques: - if there are m categorical values, then uniquely assign each original value to an integer in the interval [0, m-1]. If the attribute is ordinal, the order must be maintained by the assignment. - convert each of the m integers to a binary number. - If only the presence of an attribute is important, use asymmetric binary attributes. For n attribute there is n*x binary attribute values. - Some attributes needs to be divided into two or more binary attributes. Example gender with one attribute that has value 1 if female, and one attribute that has value 1 if male.

discretization of continuous attributes: Discretization for attributes used for classification or association analysis. Transformation from continuous attribute to categorical attribute: 1. deciding how many categories, and how to map attribute-values to these categories - after the values of the continuous attribute are sorted, divide them into n intervals by specifying n-1 split points. - all the values in one interval are mapped to the same categorical value. 2. problem: - how many split points? - where to place them? 3. result represented as a set of intervals, or as a series of inequalities (xo < x < x1, etc.)

Unsupervised discretization: distinct between discr. methods by whether class information is used (supervised) or not (unsupervised). Unsupervised has relatively simple approaches. As equal width (divide the range of the attribute into a user-specified number of intervals each having same width), can be badly affected by outliers. Equal frequency (puts the same number of objects into each interval) is preferred, handles outliers better. K-means and visually inspecting is also examples. Usually better than no discretization.

Supervised discretization Use the end purpose in mind and use class labels. Produce better result than unsupervised. Things to consider: purity and minimum size of an interval. entropy: (formel i boka) where k is number of class labels, mi is the number of values in the ith interval, mij is the values of class j in the ith interval, pij=mij/mi is the probability of clas j in the ith interval. total entropy: (formel i boka) where w is mi/m (the fraction of values in the ith interval) and m is the number of values.

Entropy is a measure of the purity of an interval. If an interval contains only objects of the same class (pure), the entropy equals 0. If the classes of values in an interval occur equally often, the interval is as impure as possible, and the entropy is maximum.

Simple approach for partitioning is by starting with bisecting the initial values so the resulting two intervals give minimum entropy. assumes ordered set of values. Repeat with the interval with highest entropy, until stopping criterion is reached.

problem: categorical attributes sometimes have too many values can join together based on domain knowledge, or if it does not improve or exist, use a more empirical method such as group together only if grouping improves the classification accuracy or similar.

Variable transformation A transformation that is applied to all the values of a variable. For each object, the transformation is applied to the value of the variable for that object.

Simple functions A simple mathematical function is applied to each value individually. Variable transformaiton should be done with causion since it change the nature of the data. Should be fully appreciated. Example 1/x, increases magnitude for <0,1>, but decreases for <1,n>.

Normalization or standardization Common type of variable transformation. The goal is to make an entire set of values have a particular property. Example: difference of two people based on income and age. Income varies more than age, income can dominate. Mean and standard deviation is often affected by outliers. Mean is therefore replaced by median (middle value), standard deviation is replaced by absolute standard deviation.

Chapter 2.4 Measures of similarity and dissimilarity

Used by a number of data mining techniques; clustering, nearest neighbour classification, anomaly detection. In many cases initial data set is not needed after similarities or dissimilarities have been computed.

Proximity Refers to similarity or dissimilarity.

Similarity between two objects is a numerical measure of the degree to which the two objects are alike. 0 = no similarity 1 = complete similarity.

Dissimilarity between two objects is a numerical measure of the degree to which two objects are different. Distance is a synonym. [0,1] or [0, infinity].

transformations often applied to convert a similarity to a dissimilarity (or vice versa) - d = 1-s and s= 1-d. - s > 0, d<0 and s = -d, and d=-s transform a measure to fall within a specific range. example [0,1] - s’ = (s-min_s)/(max_s-min_s). example: s’ = s-1/9 where min_s = 1 and max_s = 10.

Similarity and dissimilarity between simple attributes objects having a simple attribute. S = 1 if match, s = 0 if dont match. d = 1 if dont match, d = 1 if match. single ordinal attribute. If poor = 0, fair = 1, ok = 2, good = 3, wonderful = 4, then d(good, ok) = 3-2 = 1. downside: assumes equal distance between the values. table 2.7 s.69!!!!

Dissimilarities between data objects

distance Euclidean distance d between x and y is given by following formula: (formel i boka)

n is the number of dimensions. xk and yk is the kth attributes of x and y.

Euclidean distance is generalized by Minkowski distance metric: (formel i boka)

r is a parameter. Three most common examples: 1. r = 1. City block (Manhattan, taxicab, L1 norm) distance. 2. r = 2. Euclidean distance (L2 norm). 3. r = Supremum (Lmax norm) distance. The maximum difference between any attribute of the objects. (formel i boka)

Properties of distances: positivity d(x,y) is positive for all x, y. d(x,y) = 0 only if x = y symmetry d(x,y) = d(y,x) for all x, y triangle inequality d(x,z) d(x,y) + d(y,z) for all points x,y,z. Measures that satisfy all = metrics

Similarities between data objects For similarities the triangle inequality often does not hold.

Examples of proximity measures Simple matching coefficient SMC = number of matching attribute valuesnumber of attributes=f(11)+f(00)f(01)+f(10)+f(00)+f(11) treats presences and absences equally.

Jaccard coefficient handles objects consisting of asymmetric binary attributes. Example if number of true is very little combined with false. J = number of matching presencesnumber of attributes not involved in 00 matches=f(11)/f(01)+f(10)+f(11) Example: Jaccard and SMC x = (1,0,0,0,0,0,0,0,0,0) y = (0,0,0,0,0,0,1,0,0,1) f01 = 2, f10 = 1, f00 = 7, f11 = 1

SMC = (0+7)/(2+1+0+7) = 0,7 J = 0/(2+1+0) = 0

Cosine similarity word documents often does not contain zero entries. Cosine similarities does not depend on (and ignores) 0-0matches, as jaccard measure also does. Cosine similarity also must be able to handle non-binary vectors. If x and y are two documents vectors then cos(x,y) = x * y/||x||||y|| x*y = the vector dot product.

(s.75 for regneeksempel)

if cos = 0, the angle is 90 degrees, and x and y do not share any terms.

Extended jaccard coefficient (tanimoto coefficient) useful for document data. reduces to jaccard in case of binary attributes. EJ(x,y) , formel i boka..

Chapter 3.2 Summary statistics

Summary statistics are quantities that capture various characteristics of a potentially large set of values with a single number or a small set of numbers. Mean, standard deviation etc.

Frequency For unordered categorical values, frequency is almost the only useful thing to compute. frequency (vi) = number of objects with attribute value vim m is the number of objects.

Mode the mode of a categorical attribute is the value that has the highest frequency. May contain information about the presence of missing values (heights in cm and not in mm, or if a value is used to indicate a missing value).

Percentiles Ordered data. Given an ordinal/continuous attribute x and a number p (0,100), the pth percentile xp is a value of x such that p% of the observed values of x are less than xp. Eksempel s.101.

Measures of location Mean x= 1mi = 1mxi The middle of a set of values, if the values are distributed in a symmetric manner. If not, use median. Sensitive to outliers. Trimmed mean, when a percentage p of the top and bottom are trimmed, and mean is calculated as usual. (median is trimmed mean where p=100%).

Median median (x) = x( r + 1 ) if m is odd (the middle value) = ½ (x(r) + x( r + 1 )) if m is even (the average of the two middle values) Not so sensitive to outliers.

Measures of spread Measures if widely spread or relatively concentrated around a single point.

range Simplest measure of spread. range(x) = max(x)-min(x)=x(m)-x(1) in the set {x1, x2, …, xm}. Not good if most of the values are concentrated, but there are some extreme min and max outliers.

variance variance = sx2 = 1m-11 = 1m(xi-x)2 Standard deviation (sx) is the square root of the variance. Variance is computed with mean, and is therefore also sensitive to outliers. More robust measures: ADD: absoulte average deviation ADD = 1m1 = 1m|xi-x | MAD: median absolute deviation MAD(x) = median({|x1 - x|, … ,|xm - x|}) IQR: interquaratile range IQR = x75% - x25%

Multivariate summary statistics measures of location can be obtained by computing mean and median separately for each attribute. For multivariate data, it can be computed independent of each other. For continuous variables, the spread is most commonly captured with covariance matrix S.

si j = covariance(xi,yi) covariance(xi , yi) = 1m-11 = 1m(xki-xi)(xkj-xj)

The variances lies along the diagonal. Covariance is the measure of how two attributes vary together and depends on the magnitudes of the variables. Near 0, not have a relationship.

Correlation measure how strong two attributes are linearly related. Preferred for data exploration. correlation (xi,yi) = covariance(xi, yi)s(i)s(j)

Diagonal = 1, other varies between (-1, 1).

Other ways to summarize data Skewness The degree to which the values are symmetrically distributed around a mean.

Chapter 3.3 Visualization

the display of information in a graphic or tabular format. Visual data mining.

Motivation for visualization use information that is “locked up in people’s heads”. Maps of world and temperature. eliminate patterns and focus on the important ones.

General concepts Representation: Mapping data to graphical elements First step. Objects usually represented as: if only a single categorical attribute is being considered categories based on values of the attribute are displayed as an entry in a table or an area on a screen. if an object has multiple attributes objects can be represented as a row (/column) in a table or as a line in a graph if an object is a point in a 2- or 3-dimensional space points can be represented as a geometric figure circle, cross, box…

Techniques based on number or type of attributes involved, or if the data has some special characteristics.

visualizing small numbers of attributes Stem and leaf plots one-dimensional integer or continuous data. Split the values into groups, where each group contains those values that are the same except for the last digit each group becomes a stem last value in a group is a leaf example: 35, 36, 42, 51. stems: 3, 4, 5 leaves: 5, 6, 2, 1.

Histogram Stem and leaf plots are a type of histogram where values are divided into bins.
For categorical data, each value is a bin. If too many bins, combine. for continuous attributes, the range of values is divided into bins of (often) equally width. Representation: Each bin is represented by a bar. Bar plot. Variations: relative (frequency) histogram - change in scale in y axis. pareto histogram - categories are sorted by count. Decreases from left to right. two-dimensional histograms - each attribute is divided into intervals ,and the two sets of intervals define two-dimensional rectangles of values. can show how to values of an attribute co-occur. (figur på s.114)

Box plots figur s. 115. outliers = “+”. Compact and many can be shown in same plot.

Pie chart typically used with categorical attributes with relatively small number of values. not popular in technical publications because the size of relative areas can be hard to judge.

Cumative distribution function (CDF) - Percentile plots For each value in a statistical distribution a CDF shows the probability that a point is less than that value. For each observed value an Empirical CDF shows a fraction of points that are less than this value. (figur s.117)

Scatter plots each data object is plotted as a point in the plane using the values of the two attribute as x and y coordinates. main uses for scatter plots: graphically show the relationship between two attributes. scatter plots can also be used to detect non-linear relationships, either directly or using a scatter plot of the transformed attributes. when class labels are available, they can be used to investigate the degree to which two attributes separate the classes.

visualizing spatio-temporal data when data has spatial or temporal attributes. The earth is a spatial grid. various points in time. Data may have only a temporal component, such as time series data that give the daily prices of stocks.

contour plots if a three-dimensional data where the third dimension has a continuous value (temperature, elevation). Visualized as contour plot, which breaks the plane (the first two dimensions) into separate regions where the third dimension is roughly the same. surface plot the third attribute is the height above the plane (x, y). Require the z to be defined for all combinations of x,y.

Vector field plot characteristics may have both a magnitude and a direction. Display both. (figur s. 123).

Lower-dimensional slices When a spatio-temporal data set is recorded over time = 4 dimensions. Not easily displayed. Separate slices can be displayed (example one for each month).

Animation To deal with slices of data. Display successive two-dimensional slices of data.

visualizing higher-dimensional data Can show higher dimensions, but show only some aspects of the data.

Matrices array of values. If class labels are known, data should be reordered so similar class labels are grouped together. If different attributes have different ranges, it is standardized to have a mean of 0, and a standard deviation of 1.

If class labels are not known, matrix recording or seriation can be used to rearrange the rows and columns of the similarity matrix, so that groups of highly similar objects and attributes are together and can be visually identified.

parallel coordinates one coordinate axis for each attribute. axes are parallel to one another instead of pendicular (x,y liksom). An object is represented as a line (not a point). - each value represent a point, a line is drawn between points to form the line - figur s.127

star coordinates and chernoff faces encode objects as glyphs or icons. star coordinates - uses one axis for each attribute, and radiate from a center point. - typically, all attribute values are range (0,1). chernoff face - program to map values to features of a face. - figur s.129 they do not scale well, and are of limited use in data mining.

Do’s and Dont’s Guidelines - ACCENT principle for effective pragpical display (d.A. Burn).

Apprehension - ability to correctly perceive relations among variables. Does the graph maximize apprehension of the relations among variables? Clarity - ability to visually distinguish all the elements of a graph. are the most important elements or relations visually most prominent? Consistency - ability to interpret a graph based on similarity to previous graphs. are the elements, symbol shapes, and colors consistent with their use in previous graphs? Efficiency - ability to portray a possibly complex relation in as simple a way as possible. are the elements of the graph economically used? is the graph easy to interpret? Necessity - the need for the graph, and the graphical elements. Is the graph a more useful way to represent the data than alternatives? are all the graph elements necessary to convey the relationships? Truthfulness - ability to determined the true value represented by any graphical element by its magnitude relative to the implicit or explicit scale. are the graph elements accurately positioned and scaled?

Tufte’s guidelines for graphical excellence: - is the well-designed presentation of interesting data - a matter of substance, of statistics and of design. - consists of complex ideas communicated with clarity, precision, and efficiency. is that which gives to the viewer the greatest number of ideas in the shortest time with the least ink in the smallest space. - is nearly always multivariate. - requires telling the truth about the data.

Chapter 3.4 OLAP and multidimensional data analysis

viewing data sets as multidimensional arrays. OLAP = On-Line Analytical Processing. OLAP systems has a strong focus on the interactive analysis of data and typically provide extensive capabilities for visualizing the data and generating summary statistics.

Representing data as a table each row is an object, each column is an attribute. Multidimensional table, s.132.

General case for multidimensional data: starting point: - tabular representation of the data = fact table. step 1: - identification of the dimensions and identification of an attribute that is the focus of the analysis. - The dimensions is categorical attributes, or converted continuous attributes. - The size of the dimension is the number of attribute values. - Content of each cell = target quantity. step 2: - each row is mapped to a cell. The indices of the cell are specified by the values of the attributes (dimensions). The value of the cell is the value of the target attribute. Cells not defined assumes to be 0.

Analyzing multidimensional data - data cubes: computing aggregate quantities - aggregation is important to find a total/summary of data. Also to avoid too many entries when representing/computing. - There are a number of different aggregations (totals) to be computed for a multidim.array, depending on how many attributes we sum over. - For n dimensions, where we sum over k dimensions = nkarrays of totals, each with dimensions n - k (ikke den derre streken midt på. damn g.docs.equations).

data cube a multidimensional representation of the data, together with all possible totals (aggregates). The size of each dimension does not need to be equal. Can have more or less than 3 dimensions. Generalization of cross-tabulation (statistical terminology).

Dimensionality reduction collapses a column into a single cell. If sj is the number of possible values of the jth dimension, the number of cells is reduced by a factor of sj. pivoting is aggregating over all dimensions except 2. result: cross-tabulation with dim= 2.

Slicing and dicing slicing is selecting a group of cells from the entire multidim. array by specifying a specific value for one or more dimensions. dicing is selecting a subset of cells by specifying a range of attribute values. (selecting a subset from the complete array).

Roll-up, drill-down data categories can be viewed as hierarchies. A chair is a furniture, and a chair can be divided into lounge chair, sitting chair, armchair etc. roll-up to roll data up in a single category (from days to one month). drill-down to drill down data from a single category to several categories (from month to days).

Chapter 4.1 Preliminaries

Record The input for a classification task is a collection of records. Each record (instance, example) is characterized by a tuple (x, y). x = attribute set y = special attribute, class label

Definition classification: The task of learning a target function f that maps the attribute set x to one of the predefined class labels y.

f is known as a classification model. Useful for Descriptive modeling serve as tool for distinguish objects of different classes Predictive model predict the class label of unknown records.

Chapter 4.2 General approach to solving a classification problem

Classification technique / classifier To build a classification model from an input data set. Each technique employs a learning algorithm to find the best model for x and y.

Training set a set where labels are known. Is used to build a classification model which is applied to the test set. A test set has unknown labels.

Confusion matrix counts of correct and incorrect results from the test records.

Performing metric One number telling the accuracy shown in the confusion matrix.

Accuracy = number of correct predictions / total number of predictions Error rate = number of wrong predictions / total number of predictions

Chapter 4.3 Decision tree induction

decision tree is a classifier (classification technique).

Root node 0 incoming edges, 0 or more outgoing edges

Internal nodes 1 incoming edges, two or more outgoing edges

Leaf (terminal) nodes 1 incoming edge, 0 outgoing edges

Root and internal nodes contains attribute test conditions.

Algorithms for making decision trees: Hunt’s algorithm basis for: ID3, C4.5, CART grow a tree recursively. - Step 1: - if all records in Dt belongs to the same class yt, then t is a leaf node labeled as yt. - Step 2: - If Dt contains records that belong to more than one class, an attribute test condition is selected to partition the records into smaller subsets. A child node is created for each outcome of the test condition, and Dt is distributed to the children based on the outcomes. - Algorithm is then applied to each child node.

Will work if every combination of attribute values is present in the training data, and each combination has a unique class label.
Additional conditions: - if a child in step 2 can be empty, there are no records associated with the node. In step 2, if all records associated with Dt have identical attribute values, it is not possible to split those records any further.

Design issues of Decision tree induction Learning algorithm should address these issues: How should the training records be split? How should the splitting procedure stop?

Methods for expressing attribute test conditions Attribute types: - binary - must generate two potential outcomes - nominal - multiway split (1 to several) - binary split (OR - conditions) - Ordinal - ordered binary, and must keep the order of the values (not small - large and medium - extra large) - continuous - can be expressed as comparison test (A < v) (A > v).

Measures for selecting the best split the measures are often based on the degree of impurity of the child nodes. Smaller degree, more skewed the class distribution. (0,1) = 0 impurity (0.5, 0.5) = highest impurity.

s.158 entropy, gini og classification error som eksempler på impurity measures for binary classification. og graf for å sammenligne.

Gain The difference between impurity of parent node (before splitting) and child node (after splitting). The larger the difference, the better the test condition. Used to decide how good a test condition performs.

Decision trees algorithms often use a test condition that maximize the gain. I(parent) is same for all test conditions, so max the gain means minimize the weighted average impurity measures of the child nodes.

When entropy is used, the difference in entropy is known as information gain.

s. 160 Splitting binary attributes splitting of nominal attributes splitting of continuous atrributes Gain ratio Impurity measures (entropy, Gini index) tend to favor attributes with large number of distinct values.

Strategies to avoid too pure outcome (gender vs car brand vs customer ID): 1. restrict test conditions to binary splits only. - employed by several decision tree alg. 2. modify the splitting criterion to take into account the number of outcomes produced by the attribute test condition. - gain ratio (information gain /split info)

( mangler, s.164.. TreeGrowth algorithm (decision tree induction) og Example: Web robot detection)

Characteristics of decision tree induction 1. nonparametric approach for building classification models. Does not require any prior assumptions. 2. Finding an optimal decision tree is an NP-complete problem. Many alg are heuristic. 3. Inexpensive techniques make it possible to quickly construct models even when training set is large. 4. Easy to interpret. 5. provide an expressive representation for learning discrete-valued functions. 6. D.T.alg are robust to presence of noise (especially overfitting). 7. attribute-redundancy (langt punkt, se s. 169) 8. number of records become smaller when traversing down the tree. Data fragmentation problem is when number at leaf node is too small to make a statistically significant decision. 9. subtree can be replicated multiple times in a D.T. Makes the D.T more complex and more difficult to interpret. 10. border between two regions of different classes is known as decision boundary. 1. Oblique decision tree allow more than one attribute in a test condition. 2. Constructive induction Partition the data into homogeneous non-rectangular regions. crates composite attributes representing existing attributes arithmetic or logical. 11. choice of impurity method has little effect on the performance of the decision tree induction algorithms because the measures are so consistent with each other.

Chapter 4.4 Model overfitting

errors by a classification model divided into 2 types: 1. training errors (resubstitution / apparent error) - number of misclassification errors committed on training records. 2. generalization errors. - the expected error of the model on previously unseen records.

Model overfitting When a model has low training error but higher generalization error than another model with higher training error.

Also when the node number becomes too high, the test error begins to increase even though its training error rate continue to decrease (see p.174).

Model underfitting High error when the tree size is small. The model has yet to learn the true structure of the data.

Handling the overfitting in DT induction strategies: pre-pruning (early stopping rule) alg is halted before generating a fully grown tree that perfectly fits the entire data set. a restrictive stopping condition required. too high threshold = underfitting, too low might cause overfitting. Post-pruning initially grown to full size. then tree-pruning step. trim tree in bottum-up-fashion. replacing subtree with new leaf node or the most frequently used branch of the substree. Terminate when no further improvements can be seen.

chapter 4.5 Evaluating the performance of a classifier

Holdout method two sets: training set, test set. Classification model is induced from the training set. Performance evaluated on test set. Limitations: fewer labels available for training than for testing. the model may be highly dependent on the composition of the training and test sets. smaller training set, larger variance of the model. and the other way around.

Random subsampling Repeating the holdout method. Overall accuarcy: acc(sub) = i = 1kacc(i)/k Problems: not utilize as much data as possible for training. No control for how many times a record is used for training and testing.

Cross-validation each record is used the same number of times for training and 1(once) for testing. divide into sets. K-fold. each run a partition is used for testing, the rest of them are used for training. Runs k times, each partition is used once for testing.

special set. k = N, leave-one-out approach.

bootstrap Does not (as the others) assume that the training records are sampled without replacement → no duplicate records in the training and test sets. In bootstrap, the records are placed back in the pool, and are as likely as the others to be drawn.

Probability of a record to be chosen: 1 - (1- 1/N)N. If N is large, it approaches 1-e-1 = 0.632.

Accuracy = accboot= 1bi = 1b(0.532 x ei+0.368 + accs)

section 6.1 Problem definition

Binary representation market basket represented in a binary format. each transaction is a row, and a present item = 1, non-present = 0. Ignores the quantity, price etc.

Asymmetric binary value an item that is more important when present than absent.

itemset I = {i1,i2,...id} is the set of all itemset. If an itemset contains k items, it is called a k-itemset. {beer, diapers, milk} is a 3-itemset.

Transaction set T = {t1,t2,...,tn} is the set of all transactions. ti contains a subset of items chosen from I.

Support count The number of transactions that contain a particular itemset. (X) = |{ti | X ti, tiT}

association rule implication expression of form X → Y, where X and Y are disjoint itemsets. Strength of rule can be measure with its support and confidence.

support how often a rule is applicable to a given data set. support, s(XY)=(XY)N

Used to eliminate rules with low support (most likely to be random and uninteresting).

Confidence how frequently items in Y appears in transactions that contain X. confidence, c(XY)=(XY)(X) Measures the reliability of the inference made by the rule. Gives the conditional property of Y given X.

Association rule mining problem (definition): given a set of transactions T, find all the rules having support minsup and confidence minconf, where minsup and minconf are the corresponding support and confidence thresholds.

Brute-force (1) compute support and confidence for all possible rules. Expensive, exponentially many rules that can be extracted from a data set: R = 3d - 2d+1 + 1, where d is the number of items in the data set.

section 6.2 Frequent itemset generation

itemset of k items can generate 2k -1 frequent itemsets. Ways to reduce computational complexity: reduce the number of candidate itemsets (M) apriori principle, does not count support values reduce the number of comparisons instead of matching each candidate itemset against every transaction. Uses advanced data structures to store the candidate itemsets or to compress the data sets.

Apriori principle if an itemset is frequent, then all of its subsets must also be frequent. and if an itemset is infrequent, then all its supersets is infrequent too. Can prune based on this = support-based pruning.

Anti-monotone property: the support of an itemset never exceeds the support for its subsets. X is subset of Y, f(Y) must not exceed f(X). Anti-monotone (Downward closed).

Monotone property: Monotone (upward closed) = if X is a subset of Y, f(X) must not exceed f(Y).

Apriori algorithm (s.337) initially makes a single pass over the data set to determine the support of each item. Upon completion of this step, the set of all frequent 1-itemset F1 will be known. next, the algorithm iteratively generate new candidate k-itemsets using the frequent (k-1)-itemsets found in the previous iteration. The algorithm passes once more to count the support. Then the algorithm eliminates all candidate itemsets whose support counts are less than minsup. The algorithm terminates when there are no new frequent itemsets generated.

The frequent-itemset-generation part of the Apriori algorithm is a level-wise algorithm it traverses the itemset lattice one level at a time (k = 1 til k = n) generate-and-test first generate candidate itemsets from frequent sets, and then test each candidate. total number of iterations is kmax + 1 (kmax is the max size of the frequent itemsets).

List of requirements for an effective candidate generation procedure: avoid generating too many unnecessary candidates. unnecessary: at least one of its subsets is infrequent. Anti-monotone property! the candidate set is complete (no frequent itemsets are left out by the procedure). a candidate itemset should not be generated more than once.

Brute-force method (2) computations needed for each candidate is O(k). The overall complexity is O(k =1dkd over k= O(d*2d-1)

Fk-1 x F1 method (figur s.340) A frequent itemset is extended with another frequent items. If k=3, a k-1-itemset is extended with a k=1-itemset. Produces O(|Fk-1| x |F1|) candidate k-itemsets, where |Fj| is the number of frequent j-itemsets. Overall complexity: O(kk|Fk-1| |F1|) The method is complete. The method does not prevent that an itemset is generated more than once. can be prevented with sorted items in lexical order, and each itemset(k-1) is extended with an item that is lexically larger. {bread, diapers} with {milk} not {diapers, milk} with {bread} Better than brute-force, but still produce a lot of unnecessary candidates. heuristics available to improve every k-itemset survived pruning step, should be present in k-1 candidates. Otherwise, it is infrequent.

Fk-1 x Fk-1 method (figur s.342) The procedure merges a pair of frequent (k-1)itemsets only if their first k-2 items are identical. Lexical ordering to prevent duplicate candidates. Additional candidate pruning is needed to ensure that the remaining k-2 subsets of the candidate is frequent.

Support counting one approach: compare each transaction against every candidate itemset, and to update the support counts of candidates contained in the transaction. expensive (computationally) another approach: enumerate the itemsets contained in each transaction and use them to update the support counts of their respective candidate itemsets. figur s.343 som forklarer fremgangsmåten. first enumerate, then increment support if it is a match between a k-2(?) itemset and a candidate. Hash tree function (figur s.344) sort both candidate itemsets into buckets, and transaction itemsets (of similar size) into same buckets. Match needs only to be done inside each bucket. les på dette… (s.344)

Computational complexity can be affected by following factors: support threshold lowering threshold → more itemsets is frequent. More complex. number of items (dimensionality) more space needed to store the support counts of items. number of transactions run time increases since it repeatedly passes over the data set average transaction width the maximum size of frequent itemsets tend to increase. Complexity increases. more itemsets are contained in the transaction, number of hash tree traversals increases during counting.

Time complexity: generation of frequent 1-itemsets for each transaction, need to update the support count for every item present in the transaction. w is average transaction width N is total number of transactions O(Nw) is the time the operation requires. candidate generation blæ (se s 349). support counting cost for support counting: O(Nk(W over k)k) W is the maximum transaction width, k is the cost for updating the support count of a candidate k-itemset in the hash tree.

section 6.3 Rule generation

Each itemset of size k can produce max 2k - 2 association rules. Partition an itemset Y into non-empty subset X and Y-X, such that X→ Y-X satisfies the confidence threshold. (all subsets are infrequent due to anti-monotone property).

confidence for rule X → Y-X = (Y)(X)

Confidence-based pruning No anti-monotone property for confidence.

Theorem: If a rule X → Y-X does not satisfy the confidence threshold, then any rule X’ → Y - X’ where X’ is a subset of X, must not satisfy the confidence threshold as well.

Rule generation in apriori algorithm (tegn inn fra s. 350)

algoritme:

les også eksempel s. 353.

section 6.4 Compact representation of frequent itemsets

in practice, the number of frequent itemsets produced from a transaction data set can be very large. identify a small representative set of itemsets from which all other frequent itemsets can be derived.

Maximal frequent itemsets Definition: A maximal frequent itemset is defined as a frequent itemset for which none of its immediate supersets are frequent.

figur 6.16:  Itemsets are divided into frequent/infrequent itemsets. {a,d} is maximal frequent because all of its immediate supersets ({a,b,d},{a,c,d},{a,d,e}) are infrequent. Non-maximal = non of its immediate subsets are frequent.

Maximal frequent itemsets provide a compact representation because they form the smallest set of itemsets from which all frequent itemsets can be derived.

In figure 6.16 the maximal frequent itemsets are {a,c,e}, {a,d} and {b,c,d,e}.

Maximal frequent itemsets do not contain info about support of their subsets. Additional pass over data set is needed to determine support counts of the non-maximal frequent itemsets.

Closed frequent itemsets minimal representation without losing support information.

definition closed itemset: an itemset X is closed if none of its immediate supersets has exactly the same support count as X.

or: X is not closed if at least one of its immediate supersets has the same support count as X.

figur 6.17

definition closed frequent itemset: an itemset is a closed frequent itemset if it is closed and its support is greater than or equal to minsup.

The closed frequent itemsets to determine the support counts for the non-closed frequent itemsets. {a,d} must have the same support as {a,c,d} since it has larger support count than {a,b,d} and {a,d,e}.

figur 6.18

closed frequent itemset remove some of the redundant association rules. All maximum frequent itemsets are closed because none of the maximal frequent itemsets can have the same support count as their immediate supersets.

section 6.5 Alternative methods for generating frequent itemsets

Apriori - earliest, significant performance improvement, but still incurs considerable I/O overhead since it requires several passes. If transaction width is too high, it can also decrease.

Traversal of itemset lattice (tre fra {} på topp til {a,b,c,d,e} på bunn).

General-to-specific, specific-to-general, bidirectional: apriori uses this search strategy. Merging of k-1-itemsets to obtain candidate k-itemsets. Alternatively can look at most specific first and then more general.

Bidirectional combine. Can find frequent itemset border.

figur 6.19

Equivalance classes: Partition the lattice into disjoint groups of nodes (equivalence classes). A frequent itemset generation algorithm is used within each class. Equivalence classes can also be defined according to its prefix or suffix label of an itemset. First search for frequent itemset with prefix a, then b,c, d, etc. Suffix starts from the back.

figur 6.20

Breadth-first, depth-first: Apriori is a breadth-first. Starts with 1-itemsets, then 2-etc.

Depth first is often used by algorithms designed to find maximal frequent itemsets. Finds the border more quickly.

figur 6.21

figur 6.22

Representation of transaction data set choice of representation can affect the I/O cost.

Horizontal: adopted by apriori etc.

vertical: TID list may be too large to fit into memory, and need more sophisticated methods to compress TID-list.

section 6.6 FP-growth algorithm

Not generate-and-test. Instead it encodes the data set using a compact data structure called an FP-tree and extracts frequent itemsets directly from this structure.

FP-tree representation Compressed representation of the input data. Read the transactions one at a time, and map each transaction onto a path in the tree. Paths may overlap due to similar items. More overlap is more compression. If tree can fit in main memory, frequent data sets can be extracted directly without passes over data stored on disk.

figur 6.24 -- les beskrivelse 1-5 under  Best-case scenario. All transactions contains the same items and there is only one branch in the tree. Worst case: none of the branches overlap. The pointers requires space, so the tree requires more space in memory than original data set.

Pointers (between nodes that have the same items) help to facilitate the rapid access of individual items in the tree.

If ordering by decreasing support, it will result in this tree: figur 6.25

section 6.7 Evaluation of association patterns

Need to have evaluation criterias to decide the quality of the association patterns made by the algorithms.

First set of criteria derived from statistical arguments. Patterns that involve a set of mutually independent items or cover very few transactions are considered uninteresting because they may capture spurious relationships in the data. Patterns can be eliminated by applying an: objective interestingness measure uses statistics derived from data to determine if a pattern is interesting. support, confidence, correlation.

Second set: subjective arguments. A pattern is considered subjectively uninteresting unless it reveals unexpected information about the data or provides useful knowledge that can lead to profitable actions. {Butter} → {Bread} vs {Diapers} → {Beer}. Requires a lot of domain knowledge. Approaches for incorporating subjective knowledge into pattern discovery: visualization - interpreting and verifying the discovered patterns. template-based approach - only rules that satisfy a user-specified template are returned to the user. subjective interestingness measure - ?? a subjective measure can be defined based on domain info such as concept hierarchy or profit margin of items. the measure can then be used to filter patterns that are obvious and non-actionable.

Objective measures of interestingness A data driven approach for evaluating the quality of association patterns. Domain-independent, requires minimal input from the users, other than a threshold.

An objectibe measure is usually computed based on the frequency counts tabulated in a contingency table: (figur 6.7)

Limitations of the support-confidence framework Support eliminates low support items, even though they might be of interest. Limitation of confidence: A tea-drinker that drinks coffee is 75% chance, and seems like a good rule, but when 80% drinks coffee regardless of tea or not. Therefore the rule is not good.

(skjønte ikke helt det som står på s. 373)

Interest factor tea-coffee example show that high-confidence rules can be misleading because they ignores the support. Can solve by applying a metric; lift: Lift =c(AB) s(B) Which computes the ratio between the rule’s confidence and the support of the imteset in the rule consequent.

Binary values, it is called interest factor I(A,B)=s(A,B)s(A) x s(B)=Nf11f1+ f+1 ….????....

section 8.1 Overview

Cluster analysis groups data objects based only on information found in the data that describes the objects and their relationships. The goal is similar objects in a group, that is different from objects outside the group. The greater the similarity, the greater the difference between groups = better clustering.

The definition of a cluster is imprecise, and it should depend on the nature of the data and the desired result.

Clustering could be regarded as a form of classification in that it creates a labeling of objects with class (cluster) labels. Cluster analysis is sometimes referred to as unsupervised classification (supervised is as in chapter 4).

Different types of clustering

Hierarchical versus partitional Nested (hierarchical) clustering allowed with subclusters, one get a set of nested clusters organized as a tree. often (but not always) the leaf nodes are singleton clusters of individual data objects. Can be viewed as a sequence of partitional clusterings. unnested (partitional) clustering each object is in exactly one cluster(subset).

Exclusive versus overlapping versus fuzzy exclusive clustering assign each object to a single cluster. If it is reasonable to place an object in several clusters, it is addressed as non-exclusive clustering. overlapping (non-exclusive) clustering can simultaneously belong to more than one group (class). a student can both be enrolled and an employee at an university. rather than making an arbitrary assignment with placing an object in only one cluster, one can place the object in all of the “equally good” clusters. fuzzy clustering every object belongs to every cluster with a membership weight that is between 0 and 1 (absolutely belongs). often impose that the weights should sum up to 1 for each object. good to avoid assigning an object to only one when it may (but not certain as the student/employee) be close to several.

Complete versus partial complete clustering assigns every object to a cluster. May be desired if clustering is to organize documents, th