Riassunti Data mining and text mining

Data Mining and Text Mining Notes

Giacomo Varini 2019/2020

Lezione 2 - Data Mining

Machine Learning

“A computer program is said to learn from experience E with respect to some class of task T and a performance measure P, if its performance at tasks in T, as measured by P, improves because of experience E.”

Suppose we have the experience E encoded as a dataset D = x1, x2, x3, ..., xN:

• Supervised learning: Given the desired outputs, learns to produce the correct output given a new set of input.
• Unsupervised learning: Exploits regularities in D to build a representation to be used for prediction.
• Reinforcement learning: Producing actions which affect the environment, and receiving rewards, learn to act in order to maximize rewards in the long term.

Data Mining

The non-trivial process of identifying (1) valid, (2) novel, (3) potentially useful, and (4) understandable patterns in data.

Patterns

An example of possible pattern:

if astigmatism = yes and tear production rate = normal and spectacle prescription = myope then recommendation = hard

Idea: Build computer programs that navigate through databases automatically, seeking regularities or patterns. Attention: most patterns are uninteresting, most are coincidences, real data is imperfect!

Interestingness Measures

A pattern is interesting if it is easily understood by humans, valid with some degree of certainty, potentially useful, novel, or validates some hypothesis that a user seeks to confirm.

Objective vs. Subjective Interestingness Measures

• Objective measures are based on statistics and structures of patterns.
• Subjective measures are based on user’s belief in the data.

It is often unrealistic and inefficient for data mining systems to generate all possible patterns. Instead, user-provided constraints and interestingness measures should be used to focus the search. Association rule mining is an example where the use of constraints and interestingness measures can ensure the completeness of mining. Completeness: the model finds ALL the interesting patterns. Optimization: the model finds ONLY interesting patterns.

Data mining can be descriptive (about what already happened) or predictive (about what might happen).

What Are the Main Steps?

• Selection: What data we actually need to answer the posed question?
• Cleaning: Are there any errors or inconsistencies in the data?
• Transformation: Some variables might be eliminated because equivalent to others, others might be elaborated to create new variables.
• Mining: Select the mining approach: classification, regression, association, etc., and apply the mining algorithm(s).
• Validation: Are the patterns we discovered sound? According to what criteria? Are the criteria sound? Can we explain the result?

Data Mining Main Tasks

• Prediction & Regression
• Classification
• Clustering
• Associations

Other Tasks

• Outlier analysis (data that can be considered as noise or exception)
• Trend and evolution analysis (periodicity)

Lezione 3 - Data Representation

Describing Data

Instances (aka observations): each row corresponds to an instance.

Attributes (aka independent variables): each column contains values of an attribute, each instance is composed of a certain number of attributes.

Concept (aka class, target/dependent variable): kind of things that can be learned.

Attribute Types

Numeric Attributes

• Real-valued or integer-valued domain (can be divided into “discrete” and “continuous”)
• Interval-scaled when only differences are meaningful (e.g., temperature)
• Ratio-scaled when differences and ratios are meaningful (e.g., age, money, and weight) -> zero point is defined

Categorical Attributes

• Set-valued domain composed of a set of symbols
• Nominal when only equality is meaningful (e.g., domain(Sex) = {M, F})
• Ordinal: categorical attributes with an imposed order on values (e.g., “hot” > “mild” > “cool”)

Characteristics:

• No relation among nominal values
• No ordering
• No distance measure
• Only equality tests can be performed

Binary Attributes

Ordering Directions

• Sequential: age, height, weight;
• Diverging: temperature, altitude;
• Cyclic: hour, week;

Why Specifying Attribute Types?

Some algorithms fit some specific data types best. Make the most adequate comparisons.

Dataset Types

• Tables
• Networks
• Spatial Data:

• Fields (e.g., grid of positions, like seats in a theatre)
• Geometry (e.g., positions per coordinates)

Missing Values

Why Missing Values Exist? Faulty equipment, incorrect measurements, missing cells in manual data entry, censored/anonymous data. They are frequently indicated by out-of-range entries (e.g., max/min float), NaN or special values (e.g., zero).

Does absence of value have some significance?

• If it does, “missing” is a separate value
• If it does not, “missing” must be treated in a special way

Types of Missing Values

• Missing not at random (MNAR): Distribution of missing values depends on missing value, e.g., respondents with high income less likely to report it
• Missing at random (MAR): Distribution of missing values depends on observed attributes, but not missing value e.g., men less likely than women to respond to question about mental health
• Missing completely at random (MCAR): Distribution of missing values does not depend on observed attributes or missing value

Dealing with Missing Values

Decide on the best strategy to yield the least biased estimates:

• Deletion Methods (listwise deletion, pairwise deletion)
• Single Imputation Methods (mean/mode substitution, dummy variable control, single regression)
• Model-Based Methods (maximum likelihood)

List-wise Deletion

Only analyze cases with available data on each variable (simple, but reduces the data). Attention: estimates may be biased if data not MCAR.

Pairwise Deletion

Analysis with all cases in which the variables of interest are present. Advantage: keeps as many cases as possible for each analysis. Disadvantage: can’t compare analyses because sample different each time.

Imputation Methods

Extract a model from the dataset to perform the imputation (suitable for MCAR and for MAR, not suitable for MNAR).

Single Imputation Methods

• Mean/mode substitution (most common)
  • Advantage: can use complete case analysis methods
  • Disadvantage: reduces variability
• Dummy variable control: create an indicator for missing value
  • Advantage: uses all available information about missing observations
  • Disadvantage: results in biased estimates
• Regression Imputation

Inaccurate Values

• Typographical errors in nominal attributes -> values need to be checked for consistency
• Typographical and measurement errors in numeric attributes -> outliers need to be identified

Geometrical View

When the data contains only numerical values - Every row can be viewed as a point in a d-dimensional space - Every column as a point in an n-dimensional space.

Lezione 4 - Data Exploration and Visualization

What is Data Exploration?

Preliminary exploration of the data aimed at identifying their most relevant characteristics (and summarize them).

What the Key Motivations?

Help to select the right tool for preprocessing and data mining. We focus on data exploration using:

• Summary statistics
• Visualization

Summary Statistics

• Frequency: percentage of time the value occurs in the data set
• Mode: the most frequent attribute value
• Mean and Median: they are measures of location; mean is very sensitive to outliers
• Percentiles (for continuous data): p-th percentile is a value x_p of x such that p% of the observed values of x are less than x_p
• Trimean: the weighted mean of the first, second and third quartile
• Truncated Mean: discards data above and below a certain percentile (Interquartile truncate data at 25th and 75th percentile)
• Range and Variance: they are measures of spread; range is the difference between the max and min; they are sensitive to outliers. Solutions: ADD (media delle distanze dalla media), MAD (mediana delle distanze dalla media), IQR.

Correlation Analysis

Given two attributes it measures how strongly one attribute implies the other.

• Numerical Variables: For two numerical variables, compute the correlation coefficient, Pearson’s coefficient
• Ordinal Variables: Compute Spearman coefficient
• Categorical Variables: For two categorical variables, compute chi-square statistic test to test the hypothesis that they are independent
• Binary Variables: Compute Point-biserial correlation

Attention:

• Correlation does not imply causation!
• Causality has a direction, while correlation typically doesn’t e.g. High income may cause Ferrari, but giving someone a Ferrari does not generate high income
• Confounding variables can cause attributes to be correlated e.g. high heart rate and sweating are correlated with each other since they tend to both happen during exercise (confounder)

Outliers

Data objects that do not comply with the general behavior of the data (anomalous data). Outliers may be detected using:

• Manual inspection
• Statistical tests
• Distance measures
• Deviation-based methods

How Do We Manage Outliers?

• Trimming: Eliminate the outlier data values
• Winsorizing: Example (10% Winsorizing):
  • Consider the 5th and 95th percentiles
  • Set the values below the 5th percentile to the 5th percentile itself
  • Set the values above the 95th percentile to the 95th percentile itself

Normalization

When attributes have vastly different scales (e.g., age vs income), it is necessary to normalize them with:

• Range normalization: (x - min) / (max - min)
• Standard Score Normalization: (x - mu) / sigma

Visualization

Conversion of data into a visual or tabular format - Can detect general patterns and trends - Can detect outliers and unusual patterns.

Bar Plots

• They use horizontal or vertical bars to compare categories

Histograms

• They are a graphical representation of the distribution of data
• They estimate the probability distribution of a continuous variable

Kernel Density Estimates

• Smoothed lines calculated using kernel-density estimation (usually plotted over histograms)
• Bandwidth h of the kernel determines how smooth the estimate is
  • Large h -> smooth function -> loss of information
  • Small h -> bumpy function -> possible overfitting
• Bandwidth selection via cross-validation

Box Plots

Another way of displaying the distribution of data

Violin Plots

Kernel density estimates + box plot

Scatter Plots

Used to compare two (or more) attributes (two-dimensional scatter plots most common, but three-dimensional plots also used) - Often additional attributes can be displayed by using size, shape, and color of the markers that represent the objects

Visualizing Spatial Data

—> see slides 48-65

• Geometry:
  • Dot Maps
  • Bubble Maps
  • Choropleth Map
  • Surprise Maps
  • Connection Maps

—> NB: using absolute values is dangerous! Any map would show population distribution

Scalar Fields

• Isocontour Maps
• Isocontour Plots
• Isosurface Plots

Vector Fields

• Glyph Flow
• Geometric Flow
• Texture Flow
• Feature Flow

More than Two Dimensions at Once

Two main approaches:

• Visualize all the dimensions at once (e.g., Heatmaps, Spider Plots, Radar Plots, Star Plots and Chernoff Faces)
• Project the data into a smaller space and visualize the projected data
  • Find a linear projection (e.g., use Principal Component Analysis PCA)
  • Find a non-linear projection (e.g., use t-distributed Stochastic Neighbor Embedding t-SNE)

PCA

The goal of PCA is to find a projection that captures the largest amount of variation in data. Given n-dimensional data, find k<n orthogonal vectors (the principal components) that can be used to represent data.

How?

—> Each input data point can be written as a linear combination of the k principal component vectors. Attention: data usually need to be rescaled before applying PCA. The principal components are sorted in order of decreasing “significance” or strength. Using the strongest principal components, it is possible to reconstruct a good approximation of the original data.

t-SNE

Unlike PCA, the mapped points are not a linear combination of original attribute values and the axes of mapped space are not a linear combination (rotation) of original axes. Unlike PCA, t-SNE tries to preserve local distances to nearby points —> similar data points are modeled by nearby map points while dissimilar data points are modeled by distant map points.

Algorithm

1. Define a probability distribution over pairs of high-dimensional data points so that:
   • Similar data points have a high probability of being picked
   • Dissimilar points have an extremely small probability of being picked
2. Define a similar distribution over the points in the map space

Kullback–Leibler - Minimize the divergence between the two distributions w.r.t. the locations of the map points (gradient descent).

Observations

• Different initializations will lead to different results
• Should be applied to data with a “reasonable” number of dimensions (e.g., 30-50)
• If data have more dimensions, another dimensionality reduction algorithm should be applied

Force-directed Layout

We can map any graph of data points into 2D provided we have some (dis)similarity value between pairs of nodes:

• Euclidean distance between them in higher dimensional space
• Joint probability under a Gaussian kernel (in case of t-SNE)
• Pearson’s correlation, Spearman’s Rank correlation, chi-squared, etc.

It works by moving points around in the mapped 2D space until convergence.

Lezione 5 - Association Rules

What is Association Rule Mining?

Finding frequent patterns, associations, correlations, or causal structures among sets of items in transaction databases, relational databases or other information repositories. Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction.

Examples

• {Bread} —> {Milk}
• {Soda} —> {Chips}
• {Bread} —> {Jam}

Set of items like {Milk, Bread} or {Bread} are called “itemsets”. Support = #itemset / #transazioni totali.

What is An Association Rule?

Implication of the form X —> Y, where X and Y are itemsets. Confidence = #itemset /(#itemset \ item considered).

Two Rule Evaluation Metrics

• Support: fraction of transactions that contain both X and Y
• Confidence: measures how often items in Y appear in transactions that contain X. Obviously, rules originating from the same itemset have identical support but can have different confidence!

Given a Set of Transactions T

The goal of association rule mining is to find all rules having - support >= minsup threshold - confidence >= minconf threshold.

Brute-force Approach

(Computationally prohibitive!):

• List all possible association rules
• Compute the support and confidence for each rule
• Prune rules that fail the minsup and minconf thresholds

Two Step Approach

• Frequent Itemset Generation: find the itemsets with support >= minsup;
• Rule Generation: generate high confidence rules from frequent itemset (each binary partitioning of a frequent itemset is a rule)

Attention: frequent itemset generation is computationally expensive!

Frequent Itemset Generation

Complexity = N * M * w where:

• N = |D|,
• M = 2^|I| (all candidates)
• w = # of elements in the transaction

Strategies

• Reduce the number of candidates (M) with pruning techniques
• Reduce the number of transactions (N) as the size of itemset increases
• Reduce the number of comparisons (NM) (no need to match every candidate against every transaction)

The Apriori Principle

If an itemset is frequent, then all of its subsets must also be frequent, since: This is known as the anti-monotone property of supports. If X is frequent, any subset Y of X is frequent; if X is not frequent, any superset Y of X is not frequent.

The Apriori Algorithm

Let k=1 Generate frequent itemsets of level 1 Repeat until no new frequent itemsets are identified:

• Generate level (k+1) candidate itemsets from level k frequent itemsets
• Count the support of each candidate by scanning the database
• Prune candidates that are infrequent, leaving only those that are frequent

Example

Given the following database and a min support of 3, generate all the frequent itemsets.

The support counting step can be improved significantly if we index the database in such a way that it allows fast frequent computations.

ECLAT tidsets

Idea: given t(X) and t(Y) for any two frequent itemsets X and Y, then t(XY)=t(X) ∧ t(Y) and sup(XY) = |t(XY)|. Eclat intersects the tidsets only if the frequent itemsets share a common prefix. NB: t(X) is the set of transactions to which itemset X belongs.

Algorithm

Example: Frequent Patterns Mining WITHOUT Candidate Generation. Why? 10^4 frequent 1-itemset will generate 10^7 candidate 2-itemsets! To discover a frequent pattern, the process is required.