Data Mining ch3 notes

Read this chapter in Aggarwal a few weeks ago, but forgot to write up my notes. I may need them tomorrow for the exam (if nothing else, writing them up is a good review). More than just terms from this chapter as there are several important formulas to remember.

Quantitative distance measures:
Lp norms: Dist(X,Y) = sum(|x_i - y_i|^p)^1/p
Special cases:

• L₀ - Doesn't really work mathematically, but intuitively it's the number of dimensions that differ between X and Y, so that's how we define it.
• L₁ - grid (AKA: taxicab or Manhattan) distance: sum of all the absolute differences along each dimension.
• L₂ - standard Euclidean distance.
• L_∞ - greatest single dimension distance (i.e., max(|x_i - y_i|).

Issues with higher dimensionality - loss of contrast (max - min dist from origin)/mean dist from origin. Lower values of p (possibly between 0 and 1) help with higher dimensions, but all degrade as p gets large with distance dominated by white noise rather than relevant feature distinction.

Proximity thresholding: divide data into discretized buckets for each dimension. The proximity set S(X,Y) is the set of dimensions where X and Y map to the same bucket. Then apply the distance formula only to dimensions in S(X,Y):

PSelect(X,Y) = [sum_i∈S(X,Y)(1 - (|x_i - y_i|/(range of bucket))^p]^1/p

This gives a similarity metric rather than a distance metric ([0,1] with 1 being similar).

Mahalanobis distance: Maha(X,Y) = sqrt[(X - Y)Σ^-1(X-Y)^T] where Σ is the covariance matrix. Basically Euclidean distance on data after Principal Component Analysis has been applied.

ISOMAP and Geodesic distance: shortest path along using path that passes only to k-nearest neighbor. Once the all-pairs shortest path graph is constructed using k-dist hops, multidimensional scaling (MDS) can be used to embed the data into a lower dimensional space where a euclidean distance metric will work.

Shared Nearest-Neighbor Similarity: number of common k-dist neighbors between two points.

Generic Methods: Partition the data into local regions (typically via a clustering algorithm). For each pair, determine the appropriate region and apply the distance metric using the statistics for that region.

Categorical distance measures:
Overlap measure: S(x_i, y_i) = {1 if x_i = y_i; 0 otherwise. Similarity S(X,Y) = sum(S(x_i, y_i)).

Inverse frequency similarity (reduces noise from common attributes): Let p_k(x) = proportion of records where attribute k = x. S(x_i, y_i) = { 1/p_k(x_i)² if x_i = y_i; 0 otherwise.

Goodall measure: S(x_i, y_i) = {1-p_k(x_i)² if x_i = y_i; 0 otherwise.

Cosine distance:

cos(X,Y) = X · Y / ||X|| ||Y|| = sum(x_i y_i) / [sum(x_i²)sum(y_i²)]^1/2

Inverse document frequency id: norm each term by id_i = log(n/n_i) where n is the total number of documents and n_i is the number of documents containing the word.

Normalized frequency: h(x_i) = f(x_i) id_i. Then the cosine measure is simply applied to the normalized vector X' = f(X) = (f(x_i)).

Jaccard coefficient: J(X,Y) = sum(h(x_i) h(y_i)) / [sum(h(x_i)² + sum(h(y_i)² - sum(h(x_i) h(y_i))]
More commonly used for sparse binary data than text. In the binary domain, this reduces to:
J(X, Y) = |S_X ∩ S_Y| / |S_X ∪ S_Y|

Time series transformations
Behavioral attribute scaling (variance normalization) and translation (mean shifting)
Temporal (contextual) attribute translation (shifting to align series)
Temporal (contextual) attribute scaling (time warping). May be fixed throughout series or vary over time (dynamic time warping).
Noncontiguity matching (deleting/ignoring noise segments)

Discrete sequence
(AKA Levenshtein distance) - minimum cost function to transform one string to another given a cost function for each type of edit.
Dynamic programming objective function:

Edit(i,j) = min{Edit(i-1, j) + Cost(delete); Edit(i, j-1) + Cost(insert); Edit(i-1,j-1) + I_ij Cost(replace)

where I_ij is 1 iff x_i <> y_j

Longest Common Subsequence: also solved via dynamic programming.

Graphs
Homophily measures: short path and/or many path measures.
Random walk-based similarity
Maximum common subgraph distance (extension of longest common subsequence)
Substructure-based similarity: counts matching substructures
Graph edit distance
Graph kernels