Data, Measurements, and Data Preprocessing

Data, Measurements, and Data Preprocessing

Overview

Exam: ★★★★☆

Data mining begins before any mining algorithm is run. A dataset must first be represented in a form whose objects, attributes, scales, distributions, and relationships are understood; then its quality must be assessed and, when necessary, its representation must be cleaned, transformed, reduced, or re-expressed. This chapter therefore follows a natural pipeline: represent the data describe its statistical structure define meaningful proximity repair and integrate imperfect sources transform and reduce the representation.

The central theme is that preprocessing is not a collection of unrelated tricks. The meaning of an operation depends on the type of attribute and on what information the later analysis needs to preserve. For example, an ordinal variable should not be treated exactly like a nominal label; Euclidean distance is not appropriate for every representation; a missing value is not the same as a noisy value; and a dimensionality-reduction method can preserve linear variance while destroying nonlinear neighborhood structure.

Data Objects, Dataset Structures, and Attribute Types

Exam: ★★★★☆

A data object represents an entity described by a collection of attributes. Depending on context, the same concept is also called a sample, example, instance, data point, tuple, or object. In a conventional table, rows are data objects and columns are attributes. The object represented by a row depends on the semantics of the table: a row may represent a customer, patient, transaction, document, location, or any other unit of analysis.

The slides distinguish several important dataset structures. Record data include relational records, numerical data matrices, transaction data, and document-term matrices. In a transaction table, an object is a transaction and the attributes are often item-presence indicators. In a document-term matrix, an object is a document and the dimensions correspond to terms, with entries such as term frequencies. Graph and network data represent objects and relations jointly; examples include transportation networks, the Web, molecular structures, and social or information networks. Ordered data include video sequences, time series, transaction sequences, and genetic sequences, where position or temporal order carries information. Spatial and multimedia data include maps, raster/vector spatial layers, images, and video. These structures matter because the same numerical array can require very different analysis when its dimensions encode categories, time, space, or network connectivity.

Structured data are also characterized by dimensionality, sparsity, resolution, and distribution. High dimensionality can lead to the curse of dimensionality; sparse data often contain many zero or absent entries, for which presence may be more informative than absence; patterns can depend strongly on spatial, temporal, or measurement resolution; and distributions are summarized by their central tendency and dispersion. These properties anticipate later choices of distance, preprocessing, and dimensionality reduction.

Attribute measurement scales

An attribute (also called a dimension, feature, or variable) is a data field that describes some characteristic of a data object. The measurement scale determines which comparisons and arithmetic operations are meaningful.

• Nominal: values are unordered names or categories, such as hair color, occupation, ZIP code, or an identifier. Equality and inequality are meaningful, but ordering and arithmetic are not.
• Binary: a nominal attribute with two states. For a symmetric binary attribute, the two states are equally important. For an asymmetric binary attribute, one state is the informative or rare event and is conventionally coded as 1; a positive medical test is the slide example.
• Ordinal: values have a meaningful order, but the magnitude of the gap between adjacent levels is not defined. Examples include small/medium/large, academic year, grades, and rankings.
• Interval-scaled numeric: equal differences are meaningful, but there is no true zero. Temperature in Celsius or Fahrenheit and calendar dates are standard examples; saying that 20 °C is twice 10 °C is not meaningful.
• Ratio-scaled numeric: equal differences and ratios are meaningful because there is an inherent zero. Kelvin temperature, length, counts, and monetary quantities are typical examples. Since , Celsius and Kelvin encode the same temperature differences but different zero points.

Discrete and continuous attributes

A discrete attribute takes values from a finite or countably infinite set. Blood type is finite, while integer-valued years form a countable set. Binary variables are a special case of discrete variables. A continuous attribute is conceptually real-valued, such as temperature, height, or weight; in a computer, it is necessarily represented with finite precision.

The discrete/continuous distinction is independent of the nominal/ordinal/interval/ratio distinction. For example, a count is discrete and ratio-scaled, while Celsius temperature is typically continuous and interval-scaled.

Statistical Description of Data

Exam: ★★★★★

Statistical description answers two complementary questions: where is the data concentrated, and how widely is it spread? It also studies how variables co-vary and how distributions can be inspected visually. The slides emphasize that dispersion should be considered at multiple granularities. Emergency-department wait times, for example, may have different variability when summarized by hour, day, or week; rounding changes the observed spread; and subgroups may have different dispersions. Thus a single global summary can hide structure that appears at another resolution.

Central tendency: mean, median, and mode

For a sample , the arithmetic sample mean is

while the population mean for a population of size is . A weighted mean is

A trimmed mean removes a chosen fraction of extreme observations before computing the mean, reducing sensitivity to extremes; the slides use judged sports scores as the motivating example.

The median is the middle observation after sorting when is odd, or the average of the two middle observations when is even. For grouped data, the slides estimate the median by interpolation within the median interval:

where is the lower boundary of the median interval, is the cumulative frequency before that interval, is its frequency, and is the interval width.

The mode is the most frequent value. A distribution may be unimodal, bimodal, trimodal, or more generally multimodal. The slides also give the empirical relation

which is a rough heuristic for moderately skewed unimodal distributions, not a general identity.

For a symmetric unimodal distribution, mean, median, and mode coincide. In a positively skewed distribution the long right tail pulls the mean rightward, typically giving ; for negative skewness the ordering is typically reversed.

Dispersion: variance and standard deviation

For a random variable with mean , variance is the expected squared deviation from the mean:

For a discrete random variable this is ; for a continuous variable it is . The standard deviation is and has the same physical units as the original variable.

For sample data, two denominators appear in the slides. The descriptive or maximum-likelihood-style second moment is

whereas the usual unbiased sample variance is

The latter can be written in a computational form as

The population variance is .

For a normal distribution, the familiar empirical rule is that approximately 68% of the mass lies within , 95% within , and 99.7% within . Here locates the center while controls spread.

Covariance and correlation for numerical variables

For two random variables and with means and , covariance is

Positive covariance indicates that the variables tend to deviate from their means in the same direction; negative covariance indicates opposite directions. Variance is the special case .

The slides’ stock example uses observations , , , , . The means are and , and

so the covariance is positive.

Independence implies zero covariance whenever the relevant moments exist, because . The converse is false in general: zero covariance means no linear co-movement, not independence. Under additional assumptions such as joint multivariate normality, zero covariance does imply independence.

Correlation standardizes covariance to remove the variables’ scales:

For a sample, the correlation can be computed directly as

Values near 1 indicate strong positive linear association, values near −1 strong negative linear association, and values near 0 weak linear association. Scatter plots make this geometry visible: a narrow rising cloud has large positive correlation, a narrow falling cloud has large negative correlation, and a diffuse or nonlinear cloud can have correlation near zero.

Covariance matrix

For a -dimensional random vector with mean vector , the covariance matrix is

Its diagonal entries are variances and its off-diagonal entries are pairwise covariances. For two dimensions,

For real-valued variables, , so is symmetric. This matrix later becomes the central object in PCA.

Association for categorical variables: chi-square test

For a contingency table, the chi-square statistic compares observed counts with expected counts under an independence model:

For a cell in row and column with grand total , the expected count is

In the slide example, 450 of 1500 people like science fiction and 300 of 1500 play chess, so under independence the expected count in the “like science fiction and play chess” cell is . Using all four cells yields . For a table with row categories and column categories, the degrees of freedom are ; hence the example has one degree of freedom.

The null hypothesis is that the two categorical variables are independent. Cells with large standardized deviations between observed and expected counts contribute most to . The decision must be made by comparing the statistic with a chi-square distribution using the correct degrees of freedom, or equivalently by using a p-value.

Graphical summaries

A boxplot summarizes a distribution through its quartiles. is the 25th percentile, the median, and the 75th percentile; the interquartile range is . A classical five-number summary is . In a Tukey-style boxplot, the box spans to , the median is drawn inside, and outliers are commonly defined relative to the fences and .

A histogram displays the distribution of quantitative data by dividing its numeric range into bins. When bin widths are unequal, bar area should encode frequency (or probability), so the height corresponds to frequency density. A bar chart instead compares categorical values; categories may be reordered, while histogram bins retain their numerical order. Thus student heights, ER waiting times, and house prices naturally call for histograms, while blood types, diagnoses, cities, and smoker/non-smoker categories call for bar charts. Small integer-valued distributions are borderline cases: a bar chart can emphasize discrete outcomes, while a histogram-like display can emphasize their distribution.

A boxplot can hide distributional shape. The slides show two different histograms with the same minimum, quartiles, median, and maximum; therefore the same boxplot can correspond to distinct modality or concentration patterns. Histograms retain more shape information at the cost of depending on binning choices.

A quantile plot sorts observations and pairs each with a cumulative fraction , so approximately percent of the data are at or below . Unlike a five-number summary, it displays the full ordered sample and can reveal unusual observations.

A Q-Q plot compares corresponding quantiles of two univariate distributions. If the two distributions are similar up to location and scale, points tend to follow an approximately straight line; systematic curvature indicates different distributional shape. The slides use one Q-Q plot to compare prices at two branches and another to compare sample data with a normal reference distribution. A branch whose corresponding quantiles lie systematically below the other tends to have lower values at those probability levels.

A scatter plot displays paired numerical observations as points in a plane. It provides a first look at clusters, outliers, trend direction, heteroscedasticity, and nonlinear patterns. The slide with an inverted-V pattern is especially important: the left half is positively correlated and the right half negatively correlated, but their combination may have low overall linear correlation. This is a visual reminder that “uncorrelated” does not mean “unstructured.”

Similarity, Dissimilarity, and Proximity

Exam: ★★★★★

A similarity function assigns larger values to more alike objects, often in . A dissimilarity or distance assigns smaller values to more alike objects, commonly with minimum 0 and range or . Proximity is an umbrella term for either similarity or dissimilarity. The correct proximity definition depends on the attribute type and on the semantics of “closeness.”

A data matrix stores objects by attributes. A dissimilarity matrix instead stores pairwise distances between the objects. For a symmetric distance, the matrix is symmetric with zero diagonal, so one triangle is sufficient. The slides’ four-point numerical example shows how a two-column data matrix becomes a Euclidean dissimilarity matrix.

Minkowski distance for numerical data

For two -dimensional objects and , Minkowski distance of order is

A metric satisfies non-negativity with identity of indiscernibles, symmetry, and the triangle inequality:

• and exactly when the objects coincide;
• ;
• .

Not every useful dissimilarity is a metric.

Important special cases are:

• : Manhattan or city-block distance, ;
• : Euclidean distance, ;
• : Chebyshev or supremum distance, .

For binary vectors, Manhattan distance equals Hamming distance: the number of bit positions at which the two vectors differ. The slide example illustrates that the same four points produce different pairwise distances under , , and , because each norm aggregates coordinate-wise differences differently.

Binary, nominal, ordinal, and mixed attributes

For two binary objects, define the contingency counts: = number of attributes where both are 1, = 1 for object and 0 for , = 0 for and 1 for , and = both 0. For symmetric binary attributes, simple mismatch distance is

For asymmetric binary attributes, joint absence is ignored:

The corresponding Jaccard similarity is

This is appropriate when co-presence is informative but co-absence is not. The medical-record example in the slides therefore excludes gender from the asymmetric calculation and obtains , , and from the remaining binary attributes.

For nominal attributes, a simple matching dissimilarity counts mismatches. If of attributes match,

An alternative is one-hot encoding: a nominal variable with states is expanded to binary indicators.

For an ordinal attribute with ordered states, the slides map rank to

then treat as interval-scaled. Thus freshman, sophomore, junior, senior can map to , giving distances 1 between freshman and senior and between junior and senior. This preserves order and imposes equal spacing without pretending that the values have a meaningful ratio zero.

For mixed-type data, the slides combine per-attribute dissimilarities through a weighted average:

The indicator/weight can exclude unavailable or inapplicable comparisons and can encode application-specific importance. Numeric attributes should first use a normalized distance so that large numerical scales do not dominate; binary and nominal attributes use type-appropriate matching; ordinal attributes are rank-normalized first.

Cosine similarity

Long sparse vectors, especially document-term vectors, are often compared by their orientation rather than raw Euclidean distance. For two vectors and ,

The document example uses and . Their dot product is 25, their lengths are approximately 6.481 and 4.12, and the cosine similarity is approximately .

Cosine similarity is insensitive to a common positive scaling of a vector, so two documents with similar term proportions but different lengths can still be highly similar.

KL divergence for probability distributions

The Kullback-Leibler divergence compares probability distributions over the same variable. For discrete distributions,

and for continuous densities,

It measures the expected information penalty incurred when a code or model based on is used for samples generated from . In applications, is often the reference or data-generating distribution and an approximation. and equals zero exactly when the two distributions agree almost everywhere.

KL divergence is not a metric: in general and the triangle inequality does not hold. If , the contribution is defined by the limit . If but , then because assigns zero probability to an event that can occur under .

The slides therefore motivate smoothing when empirical frequency distributions have unseen symbols. If and have different observed supports, a small can be assigned to missing symbols and the remaining probabilities adjusted so that each distribution still sums to one.

Limits of hand-designed proximity

Simple matching, vector norms, cosine similarity, and KL divergence operate on representations whose semantics are already explicit. They do not automatically recover hidden meaning. A bag-of-words representation can make “the cat bites a mouse” and “the mouse bites a cat” nearly identical despite reversing semantic roles. Graphs and other structured objects also contain relations that are not captured by flat vectors. The slides therefore motivate richer distributed representations and representation learning as ways to learn a space in which proximity better reflects latent semantics.

Data Quality, Cleaning, and Integration

Exam: ★★★★☆

Real-world data are often incomplete, noisy, inconsistent, duplicated, stale, or difficult to interpret. The slides describe data quality as multidimensional: accuracy asks whether values are correct; completeness whether required values are available; consistency whether sources and records agree; timeliness whether values are current; believability whether the source can be trusted; and interpretability whether the representation is understandable.

Preprocessing therefore includes data cleaning, integration, reduction, transformation, and discretization. Cleaning handles missingness, noise, outliers, and inconsistencies. Integration combines sources. Reduction seeks a smaller representation with nearly the same analytical value. Transformation changes the representation, including normalization and discretization.

Missing, noisy, inconsistent, and disguised values

Missing data can arise from equipment malfunction, deletion of inconsistent measurements, misunderstanding during data entry, fields that were not considered important at collection time, or failure to record historical changes. Common responses in the slides are:

• ignore the tuple, especially when a class label is missing and losing the tuple is acceptable;
• fill the value manually, which is usually infeasible at scale;
• use a global constant such as “unknown”;
• impute the attribute mean;
• impute a class-conditional mean;
• infer the most probable value using a probabilistic model or decision tree.

These methods make different assumptions. Mean imputation is simple but shrinks variability; a global “unknown” category changes the attribute’s state space; inference-based methods can preserve structure better but can also introduce model bias.

Noise is random error or variance in a measured variable. Incorrect values may originate from faulty instruments, data-entry or transmission errors, technical limits, or inconsistent naming conventions. Other quality problems include duplicates, incomplete records, and inconsistencies such as a recorded age that conflicts with the date of birth, or a rating system that changed from numeric to alphabetic codes. Missingness can also be disguised intentionally or operationally, such as an implausible default birthday used for many people.

The slides list several noise-handling methods. Binning first sorts the data and partitions it, then smooths values by bin means, medians, or boundaries. Regression smooths by fitting a function. Clustering can expose observations that do not fit dense groups. Semi-supervised inspection flags suspicious values computationally and delegates ambiguous cases to humans.

Cleaning as an iterative process

Data cleaning begins with discrepancy detection using metadata such as domains, ranges, dependencies, distributions, uniqueness constraints, sequential rules, and null rules. It should also detect overloaded fields such as a single Name field containing multiple subfields. Data scrubbing uses simple domain knowledge, dictionaries, postal-code rules, or spell checking to detect and correct errors. Data auditing analyzes the data itself to discover rules and relationships whose violators may be errors or outliers, for example through correlation or clustering.

Migration and ETL tools operationalize transformations across systems: ETL means extraction, transformation, and loading. The slides stress that cleaning and integration are not one-off stages; they are iterative and interactive because correcting one discrepancy can expose another.

Data integration and conflict resolution

Data integration combines multiple databases, cubes, or files into a coherent store. It can provide a more complete picture and improve mining efficiency and quality, but it introduces schema, entity, and value-resolution problems.

Schema integration aligns semantically equivalent fields, such as A.cust-id and B.cust-#, and reconciles metadata. Entity identification determines when different records refer to the same real-world entity, even when names differ.

After entities are aligned, sources may still disagree about attribute values because of different representations, timestamps, units, scales, or source errors. The slides suggest several conflict-resolution policies: mean/median/mode/max/min aggregation, choosing the most recent value, or truth finding that weights sources by quality. The appropriate rule depends on semantics; for example, averaging two incompatible categorical codes is meaningless, whereas averaging repeated noisy measurements may be sensible.

Integration also introduces redundancy. The same attribute can appear under multiple names, or one field can be derivable from others, such as annual revenue from periodic values. Correlation and covariance can help detect redundant numerical attributes, but a high correlation alone does not prove semantic duplication.

Data Transformation, Discretization, Compression, Sampling, and Reduction

Exam: ★★★★★

A data transformation maps values or representations to new values while retaining the information needed for later analysis. The slides group smoothing, feature construction, aggregation, normalization, and discretization under transformation, and then treat compression, sampling, and alternative representations as forms of data reduction.

Normalization

Normalization places numerical attributes on comparable scales. For min-max normalization of an attribute from to ,

For the slide example with income between 12,000 and 98,000, mapping to sends 73,600 to approximately 0.716.

Z-score normalization uses the mean and standard deviation:

Thus if , , and , then : the value lies 1.225 standard deviations above the mean.

Decimal scaling uses

where is the smallest integer that makes the maximum absolute transformed value less than 1.

Normalization is especially important before distance-based methods when attributes have different units or scales; otherwise the largest-scale attribute can dominate proximity.

Discretization and concept hierarchies

Discretization divides the range of a continuous numerical attribute into intervals and replaces raw values by interval labels. It can reduce data size, simplify downstream models, and create higher-level concepts. Methods may be supervised or unsupervised, top-down splitting or bottom-up merging, and can be applied recursively.

The slides classify common methods as follows. Binning and histogram-based discretization are unsupervised top-down methods. Clustering can support unsupervised splitting or merging. Decision-tree discretization is supervised and chooses split points using class information such as entropy. ChiMerge is a supervised bottom-up method: adjacent intervals with similar class distributions produce low chi-square values and are merged recursively until a stopping condition is reached.

For equal-width binning over attribute range with bins, the bin width is

It is simple but sensitive to outliers and often poor for skewed data because sparse tails can consume large ranges. Equal-depth or equal-frequency binning instead creates bins with approximately equal sample counts, adapting better to skewed densities but producing unequal numeric widths.

The visual comparison in the slides shows why clustering can outperform rigid binning: equal-width and equal-depth boundaries are constrained by the binning rule, whereas K-means can adapt boundaries to groups that are naturally separated in the data.

A concept hierarchy recursively replaces low-level values by higher-level concepts, enabling analysis at multiple granularities. Numeric hierarchies can be built by discretization, such as mapping exact ages to youth/adult/senior. For nominal data, hierarchies may be specified explicitly (street < city < state < country), defined through grouped values, partially specified and completed later, or inferred heuristically from distinct-value counts. The heuristic places attributes with more distinct values at lower levels, although semantic exceptions such as weekday/month/quarter/year show that cardinality alone is not definitive.

Compression and sampling

Compression reduces storage by exploiting redundancy. String compression is commonly lossless, while audio/video compression is often lossy and progressively refinable. Data reduction and dimensionality reduction can also be viewed as semantic forms of compression because they retain only the representation required for analysis.

Sampling selects a subset to represent a larger dataset of size , potentially reducing algorithmic cost below linear dependence on . The critical requirement is representativeness. Simple random sampling gives each item equal selection probability. In sampling without replacement, a selected item cannot be selected again; in sampling with replacement, each draw is made from the full population, simplifying some probabilistic analyses and bootstrap-style procedures.

When the population is skewed, simple random sampling can underrepresent rare but important groups. Stratified sampling partitions the population into strata and samples from each stratum, often proportionally, to preserve group representation.

Sampling can reduce the number of records processed by a mining algorithm but may not reduce physical database I/O proportionally when storage is read in whole pages or blocks.

Data reduction: parametric and non-parametric representations

The goal of data reduction is a much smaller representation that yields nearly the same analytical result. Parametric methods assume a model, estimate a small parameter set, and may discard most raw data. Non-parametric methods do not commit to a fixed global model and instead use summaries such as histograms, clusters, or samples.

In regression, a response variable is modeled from one or more predictors. Simple linear regression uses

and typically estimates and by least squares. Multiple linear regression generalizes this to

Nonlinear regression uses a nonlinear relation and is often fitted iteratively. Log-linear models make the logarithm of the modeled quantity linear in parameters, permitting linear-model machinery to summarize certain multi-dimensional relationships. In the data-reduction view, the key point is not the regression task itself but the replacement of many observations by a compact set of fitted parameters.

Histograms reduce data by storing bucket-level summaries rather than individual records. Clustering partitions data by similarity and can store only cluster representatives such as centroids and diameters; this is effective when the data genuinely form compact groups but less effective when the distribution is smeared without clear clusters.

Dimensionality Reduction

Exam: ★★★★★

Dimensionality reduction addresses the growth of sparsity and combinatorial complexity as the number of features increases. In high-dimensional spaces, local density is harder to estimate, pairwise distances can become less discriminative, and the number of possible feature subsets grows exponentially. Reducing dimensionality can remove irrelevant or redundant features, suppress noise, reduce time and space cost, and enable visualization.

Two broad strategies must be distinguished. Feature selection keeps a subset of the original variables. Feature extraction creates a new lower-dimensional representation, usually by combining or transforming the original features.

Principal Component Analysis

PCA is a linear feature-extraction method. It applies an orthogonal transformation so that possibly correlated numerical variables are represented by linearly uncorrelated principal components. The components are directions of decreasing variance, and the top components provide a lower-dimensional approximation.

Let centered data vectors be with covariance matrix . PCA solves the eigenproblem

where the eigenvectors define orthogonal directions and the eigenvalues give the variance captured along those directions. Sorting orders components from strongest to weakest. Keeping the first eigenvectors in projects a centered observation to

and reconstructs the rank- approximation as .

The slides’ method can therefore be organized as:

• center the numerical data; when feature scales are incomparable, also scale or standardize them;
• compute the covariance matrix;
• compute its eigenvectors and eigenvalues;
• sort eigenvectors by decreasing eigenvalue;
• retain the top directions and project the data onto them.

The three-camera example supplies the geometric intuition: several measured coordinates can be highly redundant because the ball actually moves along a lower-dimensional trajectory. PCA discovers directions that summarize the dominant linear variation.

Attribute subset selection

Attribute subset selection removes redundant or irrelevant original variables. A redundant attribute duplicates information already available elsewhere, such as a sales-tax field that is deterministically derived from purchase price under a fixed rate. An irrelevant attribute provides little useful information for the current task, such as a student ID for GPA prediction.

Exhaustively evaluating all subsets of attributes requires considering combinations, so the slides motivate heuristic search:

• choose the best single attribute under an independence assumption;
• forward selection: start from the best attribute and repeatedly add the next attribute that most improves the criterion conditional on those already selected;
• backward elimination: start with a larger set and repeatedly remove the weakest attribute;
• combine forward addition and backward checking;
• use branch-and-bound search when a suitable bound permits pruning and backtracking.

Feature generation is the complementary idea: rather than merely deleting attributes, construct more informative ones. The slides distinguish domain-specific extraction, mappings to new spaces such as Fourier/wavelet/manifold transforms, direct feature construction by combining existing attributes, and discretization.

Nonlinear dimensionality reduction: preserving proximity

When important structure is nonlinear, a linear projection can fail even if the intrinsic dimension is low. The slides express nonlinear dimensionality reduction through a common two-step idea: construct a high-dimensional proximity matrix , then learn low-dimensional representations whose induced proximity is as close as possible to . Different methods differ mainly in how they define proximity and how they measure preservation error.

Kernel PCA.

Kernel PCA first defines a kernel matrix

Typical kernels in the slides include the polynomial kernel

and the radial basis function kernel

After centering the kernel matrix, KPCA uses its leading eigenvectors/eigenvalues to obtain a low-dimensional representation. The slides summarize its preservation objective as making close to , for example by a squared Frobenius discrepancy .

Stochastic Neighborhood Embedding.

SNE interprets proximity probabilistically. In the simplified form shown in the slides, high-dimensional neighbor probabilities are defined from squared distances,

with proportional to . A low-dimensional embedding induces corresponding probabilities . The embedding is optimized so that each original neighborhood distribution is close to its low-dimensional counterpart, using