Riassunti Data Mining and Text Mining

Data exploration and visualization

Data mining can be descriptive (about what already happened, Ex: I want to analyze who are the customers that shop at my store more than twice a week) or predictive (about what might happen, Ex: I need a model to help me investing in the stock market). Prescriptive: use descriptive and predictive mining to recommend a course of action.

Descriptive analytics

Descriptive analytics is focused solely on historical data. You can think of predictive analytics as using this historical data to develop statistical models that will then forecast about future possibilities. Prescriptive analytics takes predictive analytics a step further and takes the possible forecasted outcomes and predicts consequences for these outcomes. (Ex: Whenever you go to Amazon, the site recommends dozens and dozens of products to you. These are based not only on your previous shopping history (reactive), but also based on what you’ve searched for online, what other people who’ve shopped for the same things have purchased, and about a million other factors (proactive).)

Interesting patterns and completeness

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. Completeness: the model finds ALL the interesting patterns (ex: greedy algorithm). Optimization: the model finds ONLY interesting patterns. (Ex: FP-growth)

Handling missing values

Missing values: If we apply imputation without any knowledge about the meaning of what a missing value represents, we would end up with attributes set almost completely to the same value. So they would be almost useless. We need to ask the domain expert whether some missing values have a special meaning.

Distribution and correlation analysis

Distribution of numerical variables: we can apply the log1p function to all the skewed numerical variables.

Correlation analysis: measure how strongly one attribute implies the other. (Using heatmap or clustermap)

Managing outliers

Outliers: Data objects that do not comply with the general behavior of the data. Outliers may be detected using: Manual inspection, Statistical tests, Distance measures, or 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, finally set the values above the 95th percentile to the 95th percentile itself.

Normalization and visualization

Normalization: when attributes have vastly different scales, it is necessary to normalize them with: Range normalization or Standard score normalization.

Visualization: conversion of data into a visual or tabular format to detect general patterns and trends and to detect outliers or unusual patterns: Bar plots to compare categories, histograms that represent the distribution of continuous variables from the data set, box plots to display visualization of data, scatter plots to compare two or more attributes.

Visualizing more than two dimensions

• Visualize all the dimensions at once (e.g. heat maps).
• Project the data into a smaller space and visualized projected data (linear projection: PCA, non-linear projection: t-SNE).

Association rules

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. 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.

Brute-force approach (computationally prohibitive!)

• 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).
• The Apriori principle: if X is frequent, any subset Y of X is frequent; if X is not frequent, any superset Y of X is not frequent.
• ECLAT: intersects the tidsets only if the frequent itemsets share a common prefix.

Frequent patterns mining without candidate generation

• The FP-Growth algorithm: Construct the frequent pattern tree. For each frequent item, i compute the projected FP-tree. Recursively mine conditional FP-trees and grow frequent patterns obtained so far. If the conditional FP-tree contains a single path, simply enumerate all the patterns.
• Rule Generation: Given a frequent itemset L, find all non-empty subsets f L such that f → (L \ f) satisfies the minimum confidence requirement. Lift: lift(X → Y) = sup(X U Y) / (sup(X) * sup(Y)) = conf(X → Y) / sup(Y). It says how much is surprising to find a rule given the distribution of the single element (the higher the most surprising).
• A frequent itemset X is called maximal if it has no frequent supersets.
• An itemset X is closed if all supersets of X have strictly less support.
• A frequent itemset X is a minimal generator if all subsets of X have strictly higher support.

Clustering

Searches for “natural” grouping/structure in un-labeled data. Euclidean distance, Jaccard distance (d(x,y) = 1 – SIM(x,y), SIM is the percentage of identical attributes).

Requisites for clustering algorithms: Scalability, ability to deal with different types of attributes, ability to handle dynamic data, able to deal with noise and outliers, high dimensionality, incorporation of user-specified constraints, interpretability, and usability.

Hierarchical clustering

Time complexity O(N² log N). Single linkage: d(Ci, Cj) = min(ti,p, tj,q). Complete linkage: d(Ci, Cj) = max(ti,p, tj,q). Mean distance: d(Ci, Cj) = d(µi, µj) where µi and µj are the cluster means. Average distance: d(Ci, Cj) = avg(d(ti,p, tj,q)).

Determining the number of clusters

• Internal Validation Measures: employ criteria that are derived from the data itself. For instance, intracluster and inter-cluster distances to measure cluster cohesion (WSS, evaluates how similar are the points in the same cluster) and separation (BSS evaluates how far apart are the points in different clusters). WSS = sum (i=1:K) sum (x_j in C_i) { dist(x_j , mu_i )² } BSS = sum (i=1:K) { |C_i| dist(mu, mu_i )² }. Then also the Silhouette coefficient which is both a measure of cohesion and separation of clusters. It is based on the difference between the average distance to points in the closest cluster and to points in the same cluster. For each point xi we calculate its silhouette coefficient si as: s(xi) =b(xi)−a(xi)/ (max{a(xi ),b(xi )}, Where a(xi) is the average distance between item xi and all other data within the same cluster; b(xi) is the mean distances from x_i to points in the closest cluster. The silhouette plot shows that the n_clusters value of 3, 5, and 6 are a bad pick for the given data due to the presence of clusters with below-average silhouette scores and also due to wide fluctuations in the size of the silhouette plots. Silhouette analysis is more ambivalent in deciding between 2 and 4. Also, from the thickness of the silhouette plot, the cluster size can be visualized. The silhouette plot for cluster 0 when n_clusters is equal to 2, is bigger in size owing to the grouping of the 3 sub-clusters into one big cluster. However, when the n_clusters is equal to 4, all the plots are more or less of similar thickness and hence are of similar sizes as can be also verified from the labeled scatter plot on the right.
• External Measures: Employs criteria that are not inherent to the dataset. Use prior knowledge about the clusters (e.g.: we cluster iris dataset using the 4 input variables then we evaluate the cluster using known class labels).
• Relative Validation Measure: aim to directly compare different solutions, usually those obtained via different parameter settings for the same algorithm. Major weakness of agglomerative clustering methods: they do not scale well (time complexity O(n²) and they can never undo what was done previously).

Connectivity constraints

In agglomerative clustering, we can restrict which clusters to join by adding connectivity constraints. These constraints specify which examples are considered connected and only clusters with connected examples, from one cluster to the other, can be joined into larger clusters. Without connectivity, hierarchical clustering with average and complete clustering cannot correctly separate the donuts and the half-moons. When a connectivity constraint that restricts the connection of each example only to the 10 nearest neighbors (by calling the k-neighbors_graph function), creates a graph of connections that respects the structure of the data and prevents these inadequate clusters from forming.

Representative-based clustering

K-means algorithm

Greedy iterative approach to find a clustering that minimizes: SSE(C) = sum(i=1:k) sum (x_j in c_i) { dist(x_j, mu_i)² } find C*=argmin(C) SSE(C). Being a greedy iterative algorithm, it can converge to a local optima instead of a globally optimal clustering. Initial centroids matter.