CS Education

Frequent itemset discovery – how to find frequently co-occurring items in an unordered “itemset”

To be considered frequent, a pattern must appear in the dataset with some minimum frequency – called “minimum support“.
Take advantage of the closure/”Apriori” property – every subset of a frequent n-itemset must be frequent.

Want to know prediction value of certain set of items on the presence of another item or set of items

Assess using “confidence” – the conditional probability of the target set’s appearance when the “base” set is there. When the pattern {x, y} appears, how confident can we be that {z} will appear too?

Just because you have high support and confidence doesn’t mean that {x,y}→{z} is a positive correlation. Even if {z} appears in 80% of the cases where {x,y} does, if in the global population, {z}’s appearance rate is 90%, then it is actually negatively correlated w/ {x,y}. Need a way to assess the impact {x,y}’s appearance has on the probability of {z} co-occurring.

Use correlation measures. Many exist – lift, chi-squared, cosine, Jaccard. Most have drawbacks – most are not null-invariant (thrown off by null tuples – portion of population that lack both {x,y} and {z}), and others provide a measure of correlation in one direction only.
Kulczynski is null-invariant and can be used with imbalance ratio to assess both {x,y}→{z} and {x,y}←{z} simultaneously.

Frequent sequential patterns

Like frequent itemset mining but respecting order
Gapped vs. non-gapped – choice is different for different types of data.

Frequent subgraphs

Data and pattern constraints and pruning methods can be used to reduce computational burden.

Most take advantage of monotonic or antimonotonic properties of the data or pattern.
Some constraints are convertible, requiring the dataset be sorted before application.

Partitioning-based

k-means/medoids/medians/modes
Based on some measure of distance or dissimilarity (depending on data type)
Progressive-refinement technique
Greedy; can be sensitive to initial cluster selection. Methods for better-than-random initialization exist – some use probabilistic initialization to spread out starting cluster centers, others just repeat algo w/ different random initializations and keep best outcome.
Different methods exist to automatically determine optimal number of clusters for a given data, attempting to automate assignment of k value.

Hierarchical

Create entire hierarchy instead of just the given partitioning of the data with a set number of clusters (k).
More deterministic; no iterative refinement. Still greedy though.
Dendrogram (tree) used to represent a clustering hierarchy
Agglomerative vs. divisive (bottom-up vs. top-down)
Have to choose a “linkage criterion” – how will data-point/cluster proximity “closeness” be measured to split or merge?

Density-based

Can discover clusters of arbitrary shape (e.g. non-convex)
Don’t specify #clusters k; instead, specify the minimum number of points a cluster requires, and the max distance a point can be away (ε) and still be part of a cluster.
DBSCAN
OPTICS – produces reachability plot showing cluster count vs. density
Can discretize data space and apply a grid-based algo like CLIQUE. CLIQUE can find subspace clusters in high-dimensional data, iteratively applying apriori principle while increasing dimensionality of search space.

Probabilistic and generative models

Perform MLE using expectation-maximization iterative algo to derive model of most-likely generative function (e.g., Gaussian(s))that could have produced data.
Allows for a data point to contribute to mulitiple clusters, with a probability of membership in each.

How to handle non-convex/linearly-inseparable clusters

Kernel methods (e.g., kernel k-means)
Density-based clustering
Probabilistic clustering (MLE via expectation-maximization)

Different evaluation metrics exist to determine how well an algo finds clusters, compared to the “ground truth” provided for a given dataset.

Curse of dimensionality

High-dimensional data is very sparse; distance metrics become less useful
Subspace-clustering methods like CLIQUE can be used.
Dimensionality-reduction methods like PCA can be used.

Decision trees

Different ways of determining how to split dataset at each node

Information Gain
Gain Ratio
Gini impurity

Random forest – ensemble of trees w/ bagging

Bayes classifier

Naïve Bayes classifier that assumes class-conditional independence
Bayesian network w/ conditional probability table for each node

Metrics to assess performance

Accuracy, Error Rate
Sensitivity, Specificity
Precision, Recall

Classification eval

Cross validation
Bootstrap
Holdout method
ROC curve (comparison)

Ensemble methods

Bagging
Boosting

Special accomodations needed for class-imbalanced datasets (where positive tuples very rare)

Linear classifiers (discriminative instead of generative)

Logistic regression

Adapts linear regression by using the logistic (sigmoid) function to map a linear-regression result to a value in the (0, 1) range, indicating a probability of belonging to one class or another.

SVM

Finds best separating line or hyperplane separating data points in two classes.
Can use nonlinear kernel mapping to higher dimension for linearly-inseparable data.
Low model complexity – only determined by number of support vectors.

Neural networks

Multi-layer Perceptron – fully-connected layers. Gets too computationally complex quickly.
Each unit takes as input a weighted sum of the input connections plus some bias (weights and bias are the params to be learned).
Activation functions – need nonlinearity function to “switch on” the unit based on input.

sigmoid
tanh
ReLU
…

Nonlinear activation functions allow approximating any function.

CNN

Used for grid-like data like images.
Much more sparse mappings than a fully-connected MLP. Same params being applied at each point too.

RNN

Used for sequence data like text.
Previous state affects processing of subsequent. Can have future state feedback too.
Need special methods to handle longer-term “memory” – SLTM, attention mechanisms, Transformer model.

Pattern-based classification

Use frequent-pattern mining to discover combinations of features to use in classification inference.

k-nearest neighbor

What is modeling?

Creating a simpler representation of a phenomenon (data) so we can use it to predict future results or understand the underlying generating mechanism.

What do we get out of modeling?

Insight
Prediction

Simple linear regression and multiple linear regression

Linear regression assumptions:

○ Linear (in terms of the betas)
○ Independence (errors independent of each other)
○ Normality (all errors follow normal distribution)
○ Equal variance (homoscedasticity)

How to calculate estimates of β parameters
How to calculate confidence intervals around β parameter point estimates.

Significance-of-regression testing

Can do a t-test to determine if each regression coefficient is significant in the context of the others. Is it possible β_j=0? Is 0 in this parameter estimate’s confidence interval?

Can calculate a confidence interval around the “mean response” – the prediction returned by the model when new predictor values provided.
Can also calculate the prediction interval – where you expect most of the data to lie.
In hypothesis testing, you’re assuming a null hypothesis and a distribution centered at the value the null hypothesis asserts, e.g., that a β parameter’s true value is 0. Then you look at where your estimate falls on that distribution – how far into the tail is it? What percentage of expected outcomes are expected to fall this far away from the prediction (+ or -) or farther? The significance level is a threshold you apply to say, “If a result appears so far away [like in one of the tails where only 5% of results fall], I will reject the null hypothesis and conclude this distribution isn’t the true distribution, or at least this parameter value where it’s centered is wrong.”
Hierarchical models – comparing w/ ANOVA to determine if larger model is significant w.r.t. nested one.
When you don’t know the true standard deviation, estimate it based on the sample. This estimate is called the standard error.
Sometimes variables “interact”, and you include interaction terms in the model to represent that their contributions to the prediction are not independent. Test whether the added term is significant a hypothesis test.

How to check linear regression assumptions

Linearity: inspect fitted vs. residuals plot
Independence: look for autocorrelation
Normality: normal Q-Q plot and Shapiro-Wilk test
Equal-variance: fitted-vs.-residuals plot and Breusch-Pagan test.

How to identify high-leverage points.
How to identify outliers (using standardized residuals).
Cook’s distance – combines effect of leverage and outlier status

Transformations – predictor and response

Can use response transformations to help problem better conform to LINE assumptions
Variance-stabilizing
Response transformations include log and adding polynomial terms.

You have to use tools other than visual inspection to evaluate multiple regression results – have to “fly by instruments”

Multicollinearity

When there’s correlation among the predictors, it causes higher variance in the parameter estimates.
Makes it harder to tell which predictors are significant because each one by itself might look like a fail-to-reject since the other(s) are providing the predictive power already, so removing this one doesn’t change the model much. But this can be misleading if those other predictors are varying in response to this one.
Doesn’t typically hurt predictive power, but definitely can make explanatory inference harder.

How to prevent overfitting

Use metric like AIC or BIC to decide which parameters add enough predictive power to be worth the added variance they entail.
Use a stepwise process of adding, removing, or trying both iteratively to improve model based on AIC or BIC.

Cross-validation directly attacks overfitting by testing error on unseen data.
Logistic regression and use for classification

How to use Tableau

Model human processor

Working/short-term memory, long-term memory
How things get from short-term memory to long-term memory
Sensory memory
Various ways our memory is distorted

Vision

Some perceptual processing mechanisms we rely on to perceive the 3D world from effectively a 2D image can end up tricking us.

Our perception of size is influenced by our brain’s habit of using size to infer distance.
Lines in a 2D arrangement that appear as they would in 3D when receding away from us can distort our perception.

Vector and raster graphics

Coordinate systems
Vector graphics have hierarchical coordinates (canvas within canvas)
SVG basics

Photorealism cues to perceptual system to interpret a 2D images as a 3D scene

Occlusion used as a cue to imply a visual sort from near to far. It’s one of the strongest cues the brain uses.
Illumination helps us perceive the orientation of a surface.
…

Non-photorealism

We have varying accuracy at the perceptual tasks of evaluating relative magnitude/intensity, ordering, or grouping, depending on how the data are presented.

A viewer will reason about visual ordering and confer some importance to it, often even without realizing it.

Chart types

Map-based

Graphs

Dashboards/interactive visualizations

Modes of data visualization

DOM

Document object model – the hierarchical representation of the structure (tags) in a webpage
Use Javascript to dynamically update the content on the web page.

SVG

D3.js – data-driven documents

Facilitates interactive data visualization on the web
Works alongside DOM and SVG. Treats the document as a database.
Associates a data element to each html element.
Fundamental contribution is integration of data into html, not the chart creation.

User interface design: Task Analysis first then Dialog Design.
Model-View-Controller

Event loop, callbacks

Promises to avoid blocking
async/await pattern

Narrative-vis design

Narrative Spectrum

Four fundamental elements of narrative visualization

• Scenes, consisting of charts – like slides of a presentation
• Annotations of those charts – for messaging
• Parameters used to create those charts
• Triggers used to transition between charts and interact with the visualizations

Declarative vs. imperative programming for graphical specification

Tableau, JS, D3, Vega, Vega-Lite, Ellipsis