Skip to content

下面这份笔记严格以你上传的 Chapter 2《Data, Measurements, and Data Preprocessing》为主线整理,覆盖课件 113 页的知识结构、公式、例题、图示含义以及方法之间的演进关系。对于课件中少数前后不完全一致之处,我会明确标注,而不是自行“修正”后隐藏掉。

重要程度标记:

  • ★★★★★:期末应达到“能定义、能解释、能计算、能比较”的程度
  • ★★★★☆:核心概念,通常需要理解 Why / How
  • ★★★☆☆:应认识并能够辨析
  • ★★☆☆☆:理解用途即可
  • ★☆☆☆☆:背景知识

Chapter 2:Data, Measurements, and Data Preprocessing ​

0. 全章到底在解决什么问题?★★★★★ ​

本章真正的核心不是“背一堆 preprocessing 方法”,而是在回答一个更基础的问题:

在把现实世界的数据交给 Data Mining algorithm 之前,我们究竟应该如何表示、理解、比较、清洗、转换和压缩它,使后续算法处理的对象真正具有可计算意义?

整个章节可以理解成一条逐层演进的 pipeline:

text
现实世界对象
   ↓
如何表示?
Data objects + Attributes + Data types
   ↓
数据长什么样?
Central tendency / Dispersion / Distribution / Correlation
   ↓
两个对象有多像?
Similarity / Distance / Proximity
   ↓
现实数据不干净怎么办?
Cleaning + Integration
   ↓
数据尺度/形式不适合算法怎么办?
Normalization + Discretization + Feature construction
   ↓
数据太多怎么办?
Compression + Sampling + Numerosity reduction
   ↓
维度太高怎么办?
Feature Selection / Feature Extraction
   ↓
PCA
   ↓
线性结构不够怎么办?
KPCA / SNE / t-SNE

因此本章的“技术进化树”可以概括为:

text
Raw Data
│
├─ 数据语义问题
│   ├─ Data type
│   ├─ Attribute type
│   └─ Data object
│
├─ 数据理解问题
│   ├─ Mean / Median / Mode
│   ├─ Variance / Standard deviation
│   ├─ Covariance / Correlation
│   └─ Visualization
│
├─ 对象比较问题
│   ├─ Numeric → Minkowski
│   ├─ Binary → Matching / Jaccard
│   ├─ Nominal → Simple matching
│   ├─ Ordinal → Rank normalization
│   ├─ Vector → Cosine
│   └─ Distribution → KL divergence
│
├─ 数据质量问题
│   ├─ Missing
│   ├─ Noise
│   ├─ Inconsistency
│   └─ Multi-source conflicts
│
├─ 数据形式问题
│   ├─ Normalization
│   ├─ Discretization
│   └─ Concept hierarchy
│
├─ 数据规模问题
│   ├─ Compression
│   ├─ Sampling
│   ├─ Regression
│   ├─ Histogram
│   └─ Clustering
│
└─ 高维问题
    ├─ Attribute subset selection
    ├─ PCA
    │   └─ 只能线性
    └─ Nonlinear DR
        ├─ KPCA
        └─ SNE / t-SNE

这条链就是整章最值得记住的逻辑结构。


1. Data Types:首先弄清楚“数据到底是什么”★★★★★ ​

1.1 四大类 Data Sets ​

课件 pp.2–5 将数据集分成四类。

1. Record Data ★★★★★ ​

本质:

一个 object 对应一条 record,每条 record 由若干 attributes 描述。

包括:

  1. Relational records
  2. Relational tables
  3. Data matrix
  4. Crosstabs
  5. Transaction data
  6. Document data

Relational table ​

典型形式:

通常:

  • row → data object
  • column → attribute
  • → objects 数量
  • → attributes / dimensions 数量

Transaction data ​

例如:

TIDItems
1Bread, Coke, Milk
2Beer, Bread
3Beer, Coke, Diaper, Milk

它与普通 data matrix 不同:

每个 transaction 实际包含的是一个 set,而不是固定长度的普通数值向量。

这是后续 association rule mining 的基础。

Document data ​

把 document 转换成 term-frequency vector。

例如词汇表有 个词:

其中

于是自然语言 document 被变成 vector。

后面 cosine similarity 就是为这类高维 sparse vectors 服务的。


1.2 Graphs and Networks ★★★☆☆ ​

pp.3:

  • Transportation network
  • World Wide Web
  • Molecular structures
  • Social/information networks

核心变化:

Record Data:

Graph:

因此 graph data 中不仅节点本身重要:

还需要考虑边:

这也是后面课件指出传统 vector similarity 无法表达复杂 semantics 的原因之一。


1.3 Ordered Data ★★★☆☆ ​

pp.4:

  • Video:sequence of images
  • Temporal data:time series
  • Sequential data:transaction sequences
  • Genetic sequence

和 Record Data 的核心区别:

顺序本身携带信息。

例如:

text
A → B → C

和

text
C → B → A

即使元素完全一样,也不一定具有同样语义。

这是 Bag-of-Words 方法的重要局限之一。


1.4 Spatial / Image / Multimedia Data ★★★☆☆ ​

pp.5:

  • Spatial data:maps
  • Image
  • Video

Spatial data 的一个重要特点:

Spatial relationship 自身构成信息。

例如:

  • nearby
  • overlap
  • inside
  • north of
  • adjacency

因此不能简单把它们视作 unordered attributes。


2. Structured Data 的四个重要特性★★★★☆ ​

课件 p.6:

2.1 Dimensionality ​

维数 很高会出现:

Curse of dimensionality。

后面 PCA / dimensionality reduction 就是为解决这个问题。


2.2 Sparsity ​

高维数据经常大量为 0。

例如 document vector:

课件特别写:

Only presence counts

对于很多 sparse binary / transaction tasks:

“出现”可能比“不出现”信息量更大。

因此后面 asymmetric binary / Jaccard 会:

不考虑 0–0 matching。


2.3 Resolution ​

Patterns depend on scale.

例如等待时间:

  • hourly level
  • daily level
  • weekly level

可能显示完全不同的规律。

因此没有所谓唯一“正确”的 resolution。


2.4 Distribution ​

数据分析主要看:

  • Centrality
  • Dispersion

即:

以及


3. Data Objects 与 Attributes★★★★★ ​

3.1 Data Object ​

p.7:

Data set 由 data objects 组成。

一个 data object 表示一个现实 entity。

同义词:

  • sample
  • example
  • instance
  • data point
  • object

例如:

Sales database:

  • customer
  • item
  • sale

Medical database:

  • patient
  • treatment

University:

  • student
  • professor
  • course

关系数据库中:

课件提问:What is the data object of a Crosstab? ​

课件只提出问题,没有给正式答案。

严格而言取决于 crosstab 的建模方式。如果作为二维 data matrix 使用,通常 row 可以视作 object;但在 OLAP-style crosstab 中,一个 cell 也可能表示一个由 row category × column category 定义的 aggregated group。

所以期末若出现,首先看题目如何定义 observation。


4. Attribute Types:极重要★★★★★ ​

这一部分是后面:

  • distance
  • normalization
  • discretization
  • statistical analysis

的基础。


4.1 Nominal Attribute ★★★★★ ​

只有类别,没有顺序。

例如:

其他:

  • marital status
  • occupation
  • ID
  • zipcode

注意:

数字编码 ≠ numeric attribute。

例如:

text
Zip code = 511400

虽然看起来是 number,但加减乘除没有语义。

因此它仍然是 nominal。


4.2 Binary Attribute★★★★★ ​

只有两个 states:

本质上:

Binary 是 nominal 的特殊情况。

但需要区分:

Symmetric binary ​

两个结果同等重要。

例如课件:

  • gender

0 和 1 没有谁更值得关注。

Asymmetric binary ​

两个 outcomes 不同等重要。

例如:

medical test:

Convention:

把更重要、较稀有的事件设为 1。

这里非常重要,因为后面 Jaccard:

0–0 不计入 similarity。


4.3 Ordinal Attribute★★★★★ ​

有顺序,但相邻 levels 的距离未知。

例如:

或者:

  • grades
  • military rankings
  • freshman / sophomore / junior / senior

知道:

但不能说:

除非我们人为进行 rank mapping。


4.4 Numeric Attribute★★★★★ ​

分两种:

Interval-scaled ​

满足:

  • 有顺序
  • equal-sized units
  • 没有 absolute zero

例如:

calendar dates。

摄氏:

不能说:

是 的两倍热。

因为 不是 absence of temperature。


Ratio-scaled ​

有 true zero。

例如:

  • Kelvin temperature
  • length
  • count
  • money

因此:

具有真正的比例意义。

课件给:

一张表记住 ​

类型分类顺序差值比例
Nominal✓✗✗✗
Ordinal✓✓✗✗
Interval✓✓✓✗
Ratio✓✓✓✓

★★★★★ 高频辨析。


5. Discrete vs Continuous★★★★★ ​

Discrete ​

只有:

  • finite
  • countably infinite

values。

例如:

年份:

Binary 是 discrete 的特殊情况。


Continuous ​

理论上取:

中的连续值。

例如:

  • temperature
  • height
  • weight

现实计算机只能有限 precision:

floating-point approximation。


6. Statistics of Data:为什么先统计?★★★★★ ​

这一部分逻辑:

text
Raw numbers
↓
中心在哪里?
Mean / Median / Mode
↓
散布有多大?
Variance / SD / IQR
↓
变量是否一起变化?
Covariance / Correlation
↓
数据到底长什么样?
Histogram / Boxplot / QQ / Scatter

7. Central Tendency★★★★★ ​

7.1 Mean ​

Sample mean ​

其中:

  • :第 个 sample
  • :sample size
  • :sample mean

Population mean ​

其中:

  • :population size
  • :population mean

Weighted Arithmetic Mean ​

其中:

  • :第 个 observation 的权重
  • :第 个值

直觉:

一个 observation 被重复 次。


Trimmed Mean ★★★★☆ ​

问题:

Mean 很容易被极端值影响。

例如:

mean:

明显不能代表典型值。

因此:

Trimmed mean:先删除一定比例最小值和最大值,再计算 mean。

课件例子:

Olympic gymnastics scoring。

方法演进 ​

text
Mean
↓
Why fails?
Extreme values strongly influence mean
↓
Trimmed mean / Median
↓
降低 outlier influence

7.2 Median★★★★★ ​

排序以后:

奇数个:

偶数个:


Grouped data 的 median 插值公式★★★★★ ​

课件 p.16:

更规范写为:

其中:

  • :estimated median
  • :median interval 的 lower boundary
  • :总 frequency
  • :median interval 之前的 cumulative frequency
  • :median interval frequency
  • :interval width

推导直觉 ​

我们要找到第:

个 observation。

进入 median bin 之前已经有:

个 observation。

因此还需要向 bin 内前进:

个。

假设数据在该 interval 中均匀分布,则走过的比例:

乘 bin 宽度:

最终:


7.3 Mode★★★★☆ ​

定义:

可能:

  • unimodal
  • bimodal
  • trimodal
  • multimodal

课件给经验关系:

因此:

注意:

这是 empirical relation,不是普遍数学定理。


8. Symmetric vs Skewed Distribution★★★★★ ​

Symmetric ​

通常:


Positive skew / right skew ​

右侧长尾:

因为大值把 mean 往右拖。

Skewness:


Negative skew / left skew ​

左侧长尾:

Skewness:


9. Normal Distribution:68–95–99.7 Rule★★★★★ ​

课件 p.19。

若:

则约:

其中:

  • :central tendency
  • :spread
  • :variance

10. Variance & Standard Deviation★★★★★ ​

10.1 Sample Variance ​

课件 p.20:

标准差:


Computational form★★★★★ ​

课件给:

推导 ​

从:

展开:

因为:

所以:

又:

所以:

于是:

意义:

只要维护 、、,就可以 incremental computation。

这就是课件问:

Can you compute it incrementally and efficiently?

的关键答案。


10.2 Population variance ​

也可写:


11. Random Variable 的 Variance★★★★★ ​

课件 p.26 把样本统计扩展到 probability distribution。

若 是 discrete:

若 continuous:

统一:

其中:


最重要恒等式★★★★★ ​

推导:

利用 expectation linearity:

由于:

所以:


一个课件细节: vs ​

p.26 同时显示:

以及:

而 p.20 明确把 sample variance 定义为 。

期末建议:

如果题目写 sample variance 且没有其他说明,按照课件 p.20 使用 。

从统计学角度:

  • :常见于 MLE / empirical variance
  • :unbiased sample variance

但这是对课件公式差异的解释,不是课件额外展开的内容。


12. Chi-Square:Categorical Correlation★★★★★ ​

数值型数据用 covariance/correlation。

Categorical variables 不能直接算普通 Pearson correlation。

于是引出:

test。


12.1 Null Hypothesis ​


12.2 Chi-square Statistic ​

更一般:

其中:

  • :observed count
  • :expected count assuming independence

值越大:

说明:

实际 joint distribution 和 independence 假设差异越大。


12.3 Expected Count★★★★★ ​

课件通过例子给出:

例如:

text
                   Chess      No Chess      Total
Like SF              250          200          450
Not Like SF           50         1000         1050
Total                300         1200         1500

若 independent:

同理:


12.4 Chi-square example★★★★★ ​

课件结果:

非常大。

因此 science fiction preference 与 chess-playing:

statistically correlated。

课件指出:

可以在显著性水平 下 reject independence hypothesis(对应 confidence level 为 )。


12.5 Degrees of Freedom★★★★★ ​

若两个 categorical variables 分别有:

  • categories
  • categories

则:

上面的 table:

为什么?

因为 row sums + column sums 固定以后:

并非所有 cells 都可以自由改变。


12.6 极重要: ​

课件例子:

  • hospitals 数量
  • car theft 数量

可能正相关。

但并不代表:

hospitals 导致 car theft。

真正 third variable:

同时导致两个变量增大。


13. Covariance★★★★★ ​

两个 random variables:

的 covariance:

其中:


等价公式★★★★★ ​

推导:

展开:


13.1 Sample Covariance ​

课件采用:

其中:

  • :sample index
  • :sample 的 variable 1
  • :sample 的 variable 2

Variance 是 covariance 的特殊情况:


Interpretation ​

若:

两个变量倾向:

同向变化。

若:

倾向:

反向变化。


13.2 Covariance = 0 是否 independent?★★★★★ ​

非常重要:

但是反过来:

除非加入特殊条件,例如:

multivariate normal distribution。


p.28 Example:应自己会算★★★★★ ​

三个 equally likely samples:

则:

因此:

但:

而:

不相等。

所以:

不 independent。

这是一个非常好的考试概念题。


13.3 Stock covariance example ​

数据:

于是:

课件得到:

因此:

股票价格倾向一起 rise/fall。


14. Correlation★★★★★ ​

Covariance 有一个严重问题:

magnitude 依赖 variables 的 units / scale。

于是出现 standardized covariance:

其中:

  • :covariance
  • : standard deviation
  • : standard deviation

Sample correlation ​

范围:

含义:

  • :positive
  • :negative
  • :linear relationship 越强
  • :perfect positive linear
  • :perfect negative linear

课件对 写:

independent under the same assumption as covariance discussion。

也就是说:

一般情况下只能说没有 linear correlation;加入如 multivariate normal assumption 后才可推出 independence。


15. Covariance Matrix★★★★★ ​

对于二维:

均值:

covariance matrix:

二维:

由于:

所以 covariance matrix:

是 symmetric matrix。

这会直接连接到 PCA:

PCA 做的就是 covariance matrix 的 eigendecomposition。


16. Graphic Statistical Descriptions★★★★☆ ​

课件列:

  1. Boxplot
  2. Histogram
  3. Quantile plot
  4. Q-Q plot
  5. Scatter plot

它们分别看不同信息。


17. Boxplot★★★★★ ​

Quartiles:

Interquartile range:

Five-number summary:


Outlier rule ​

课件说:

higher/lower than 。

通常理解为:

或者:

即视作 potential outlier。


18. Histogram★★★★★ ​

Histogram:

  • x-axis:value intervals / bins
  • y-axis:frequency

用于:

quantitative distribution。

Bar chart:

categorical comparison。


Histogram vs Bar Chart★★★★★ ​

属性HistogramBar chart
数据quantitativecategorical
X-axisnumeric intervalscategories
顺序不能随便改可以 reorder
目标distributioncomparison
bar meaningareaheight

课件特别强调:

如果 bins 宽度不同,histogram 表示 frequency 的是 area,而不是单纯 height。


课件判断题 ​

Histogram:

  • student heights
  • all ER wait times
  • home prices

Bar chart:

  • blood types
  • top diagnoses
  • cities temperatures
  • smokers vs non-smokers
  • pre-binned age groups
  • small integer visit counts

19. 为什么 Histogram 有时比 Boxplot 强?★★★★☆ ​

p.38:

两个完全不同 distributions 可能有相同:

所以 boxplot 一样。

但 histogram 可以显示:

  • multimodality
  • peaks
  • gaps
  • shape

因此:

text
Boxplot
→ compact robust summary
→ loses distribution shape

Histogram
→ keeps much more shape information

20. Quantile Plot★★★★☆ ​

排序:

每个:

对应:

表示大约:

数据满足:

本质:

empirical CDF 的一种表现。

优点:

displays all data,因此既能看 overall behavior,也能看到 unusual values。


21. Q-Q Plot★★★★★ ​

把 distribution A 的 quantiles 与 distribution B 的对应 quantiles 作图:

如果 distributions 很接近:

points approximately lie on a straight line。

课件用途:

看两个 distributions 是否存在 shift。

p.40 例:

Branch 1 的 unit price 通常小于 Branch 2。

p.41 又显示:

  • normal data vs normal distribution → 接近直线
  • exponential data vs normal → 明显弯曲

因此 Q-Q plot 很适合判断:

empirical distribution 是否接近某 theoretical distribution。


22. Scatter Plot★★★★★ ​

每个 observation:

作为平面 point。

用来检查:

  • correlation
  • cluster
  • outlier
  • nonlinear structure

非常重要的图示 p.43–44 ​

p.43:

数据左半部分 positive correlation,右半部分 negative correlation。

整个数据可能:

linear correlation 接近 0。

p.44 展示多个“uncorrelated”点云。

结论:

Correlation 本质主要描述:

linear dependence。


23. Similarity / Distance:为什么不同类型数据需要不同距离?★★★★★ ​

逻辑:

text
Data mining 经常要回答:
两个 objects 是否相似?
↓
Numeric objects?
Euclidean / Minkowski
↓
Binary?
Matching / Jaccard
↓
Categorical?
Simple matching
↓
Ordinal?
Rank first
↓
Vectors?
Cosine
↓
Probability distributions?
KL divergence

这也是本章非常重要的一条“方法演进链”。


24. Similarity / Dissimilarity / Proximity★★★★★ ​

Similarity ​

函数:

越大:

越相似。

常见:

其中:

  • 0:not similar
  • 1:identical / maximally similar

Dissimilarity / Distance ​

越小:

越相似。

通常:

range 可能:

或者:


Proximity ​

是 umbrella term,可以表示:

  • similarity
  • dissimilarity

25. Data Matrix vs Dissimilarity Matrix★★★★★ ​

Data matrix:

shape:

其中:

  • :objects
  • :dimensions

Dissimilarity matrix:

一般:

如果 distance symmetric:

那么只存 triangular half 即可。


26. Minkowski Distance★★★★★ ​

Numeric data 的统一 family:

其中:

  • :两个 objects
  • :attribute index
  • :dimensions
  • :distance order

也称:

norm distance。


27. Metric 三大性质★★★★★ ​

一个 distance 若满足:

Positivity ​

且:

Symmetry ​

Triangle inequality ​

则属于 metric。

注意:

dissimilarity 不一定必须是 metric。

课件例:

set differences 可以 nonmetric。


28. Minkowski Special Cases★★★★★ ​

:Manhattan ​

名称:

  • Manhattan distance
  • City-block distance

Hamming Distance ​

Binary vectors 上:

differing bits 数量。

例如:

与

difference positions 数量即 Hamming distance。


:Euclidean ​

即 。


:Chebyshev ​

也叫:

  • supremum distance

29. Minkowski example★★★★★ ​

数据:

例如:

课件完整 distance matrices:

​

x1x2x3x4
x10
x250
x3360
x46170

​

x1x2x3x4
x10
x23.610
x32.245.100
x44.2415.390

​

x1x2x3x4
x10
x230
x3250
x43150

30. Binary Attribute Proximity★★★★★ ​

考虑两个 objects 。

定义 contingency:

含义:

  • :both 1
  • :
  • :
  • :both 0

Symmetric Binary ​

0 和 1 同等重要。

matches:

mismatches:

所以:


Asymmetric Binary★★★★★ ​

0–0 不重要。

因此忽略:

得到:


31. Jaccard Similarity★★★★★ ​

对 asymmetric binary:

直觉:

实际上:

课件指出与后面 Pattern Discovery 中:

coherence

概念一致。


32. Asymmetric Binary Example★★★★★ ​

课件数据:

NameGenderFeverCoughTest1Test2Test3Test4
JackMYNPNNN
MaryFYNPNPN
JimMYPNNNN

Gender 为 symmetric:

本例不计。

其余:

结果:

因此:

Jack 与 Mary 最相似。


33. Categorical / Nominal Proximity★★★★★ ​

Simple Matching ​

假设:

  • :attributes 总数
  • :matching attributes 数

则:

即:


One-hot expansion ​

若 Color:

展开:

例如:

这是:

nominal → binary representation。


34. Ordinal Variable Distance★★★★★ ​

Ordinal 有 order,但没有 numerical spacing。

解决:

Step 1:转换为 rank ​

假设 variable 有:

levels。

第 个 object rank:

Step 2:映射到 ​

例如:

  • freshman → 0
  • sophomore →
  • junior →
  • senior → 1

于是:

之后把 :

当作 interval-scaled variable。

为什么不是 ratio-scaled? ​

因为:

只是 rank 最低点,不表示“该属性不存在”。

没有 intrinsic true zero。

所以只能解释 differences,不能解释 ratio。


35. Mixed-Type Attributes★★★★★ ​

现实数据可能同时包括:

  • nominal
  • symmetric binary
  • asymmetric binary
  • numeric
  • ordinal

因此每个 attribute 单独计算 dissimilarity,再 combine。

课件公式:

其中:

  • :attribute index
  • :attribute number
  • :attribute 上的 distance
  • :该 attribute 权重 / 是否参与计算

Binary / nominal:

这条“相同即 0”的写法适用于 nominal 与 symmetric binary。对于 asymmetric binary,两个对象同时为 0 表示共同不出现,通常不应算作 match:令该维度 ,从分子和分母一并排除。

Ordinal:

先:

再按 interval-scaled variable 处理。

Numeric:

课件只写:

Use the normalized distance

但该页没有显式给公式。

标准 range-normalized difference 通常写作:

这是理解补充,不是这一页明确打印出的公式。


36. Cosine Similarity★★★★★ ​

为什么需要 cosine?

Document term-frequency vectors 通常:

  • high-dimensional
  • sparse
  • document length 不一致

Euclidean distance 会受 magnitude 影响。

Cosine 只比较:

directions / angles。


Formula ​

其中:


36.1 Cosine Example★★★★★ ​

dot product:

课件给出的数值有一处算术错误:

因此:

高度相似。

课件特意强调:

vector length ≠ vector dimension。

指 magnitude,不是 component 数量。


37. KL Divergence★★★★★ ​

前面的:

  • Euclidean
  • Jaccard
  • cosine

主要比较 objects / vectors。

如果比较的是:

probability distributions

则引出 KL divergence。


37.1 Discrete KL ​


37.2 Continuous KL ​

解释:

衡量:

用 approximation 表示真实 时损失的信息。

通常:

  • :true / observed distribution
  • :model / approximation / theory

37.3 Information-theoretic interpretation★★★★★ ​

KL divergence:

使用基于 的编码,而真实 samples 来自 时,平均需要额外多少 information。

课件也称:

  • relative entropy
  • information divergence
  • information gain

37.4 KL 不是 metric★★★★★ ​

因为:

通常 asymmetric。

也不满足:

triangle inequality。

因此:

虽然常用于度量 distributions difference。


37.5 KL Non-negativity★★★★★ ​

课件:

而:


37.6 或 怎么办?★★★★★ ​

若:

则:

所以 项贡献为 0。


但若:

且:

则:

因此:

直觉:

P 说 event 可能发生,Q 却声称绝对不可能,因此 approximation catastrophically wrong。


37.7 Smoothing★★★★★ ​

现实 frequency distribution 可能只是:

没见过某 event,而不是 event probability 真的是 0。

因此加入:

例如:

课件:

supports:

union:

平滑后:

之后:

即可有限计算。


38. 为什么这些 similarity measures 还不够?★★★★☆ ​

课件 p.63 是从 classical data mining 向 representation learning 的一个关键转折。

传统 vector similarity 最大问题:

它只看到表面 representation,不理解 semantics。

例如:

The cat bites a mouse.

和:

The mouse bites a cat.

Bag-of-words 几乎相同。

但语义完全不同。

又如:

  • geometry
  • algebra
  • music
  • politics

仅靠 literal overlap 不一定能知道 geometry 与 algebra 更相关。

而 graph/network 更存在:

structure + connection semantics。

所以自然演进:

text
Hand-crafted similarity
↓
cannot model hidden semantics
↓
distributed representation
↓
representation learning

39. Data Preprocessing:为什么要做?★★★★★ ​

主要 tasks:

  1. Data cleaning
  2. Data integration
  3. Data reduction
  4. Data transformation
  5. Data discretization

具体:

Cleaning ​

  • missing
  • noise
  • outliers
  • inconsistency

Integration ​

  • databases
  • cubes
  • files

Reduction ​

  • dimensionality reduction
  • numerosity reduction
  • compression

Transformation ​

  • normalization
  • discretization
  • concept hierarchy

40. Data Quality Dimensions★★★★★ ​

课件 p.66 六个指标:

Accuracy ​

数据是否正确?

Completeness ​

是否缺失?

Consistency ​

不同 records / sources 是否互相矛盾?

Timeliness ​

是否及时更新?

Believability ​

是否可信?

Interpretability ​

是否容易理解?

注意这说明:

Data quality 不是单一“accuracy”。

而是 multidimensional concept。


41. Dirty Data★★★★★ ​

现实数据可能:

Incomplete ​

例如:

Noisy ​

例如:

Inconsistent ​

例如:

但是:

两者可能矛盾。

也可能 schema change:

text
1,2,3

变成:

text
A,B,C

Duplicate records ​

同一个 entity 多条记录不同。

Intentional errors ​

例如:

所有人生日都写 January 1。

可能是:

disguised missing data。


42. Missing Data★★★★★ ​

可能原因:

  • equipment malfunction
  • conflicting data deleted
  • data entry misunderstanding
  • 当时认为不重要
  • 没有保存 history/change

因此:

Missing data 不只是随机缺失。


43. Missing Data Handling:方法演进★★★★★ ​

方法 1:Ignore tuple ​

适合:

classification 中 class label missing。

问题:

如果不同 attributes missing rates 差异很大:

丢整条 row 会浪费大量有效信息。


方法 2:Manual filling ​

优点:

potentially accurate。

问题:

tedious + infeasible。


方法 3:Global constant ​

例如:

问题:

“unknown”可能被 algorithm 当成一个新的真实 class。


方法 4:Attribute Mean ​

问题:

会:

shrink variance / distort distribution。

课件未展开数学副作用,但直觉要知道。


方法 5:Class-specific Mean ​

如果 class 已知:

比 global mean 更合理,因为使用了:

conditional information。


方法 6:Most Probable Value ​

通过:

  • Bayesian formula
  • decision tree

infer missing value。

演进逻辑:

text
Delete
↓
太浪费
Global filling
↓
不利用上下文
Class mean
↓
利用 label
Probabilistic inference
↓
利用更多 dependency structure

44. Noise★★★★☆ ​

Noise:

random error / variance in measured variable。

原因:

  • faulty instruments
  • data entry
  • transmission
  • technology limitation
  • inconsistent naming
  • duplicates
  • incomplete
  • inconsistent data

45. Handling Noise★★★★★ ​

1. Binning ​

流程:

smooth by:

  • bin mean
  • bin median
  • bin boundary

2. Regression ​

用 regression function:

代替 noisy observations。


3. Clustering ​

outliers 往往:

远离 major clusters。

因此 detect/remove outlier。


4. Semi-supervised inspection ​

Computer:

detect suspicious values。

Human:

verify。

这体现:

自动检测效率 + domain expert judgment。


46. Data Cleaning as a Process★★★★☆ ​

不是一次 function call,而是 iterative workflow。

Discrepancy detection ​

使用 metadata:

  • domain
  • range
  • dependency
  • distribution

检查:

  • field overloading
  • uniqueness
  • consecutive rule
  • null rule

Data Scrubbing ​

使用简单 domain knowledge:

  • postal codes
  • spell checking

detect + correct errors。


Data Auditing ​

分析数据发现:

  • rules
  • relationships

然后寻找 violators。

例如:

  • correlation
  • clustering
  • outlier detection

Migration + Integration ​

ETL:

整个 process:

iterative + interactive。


47. Data Integration★★★★★ ​

定义:

combining multiple data sources into a coherent store。

为什么?

  1. reduce/avoid noise
  2. more complete picture
  3. improve mining speed
  4. improve mining quality

47.1 Schema Integration ​

例如:

名字不同:

semantic entity 相同。


47.2 Entity Identification ​

例如:

需要识别:

两条记录是否代表同一个现实对象。


48. Conflicts in Integration★★★★★ ​

不同 sources 对同一个 entity 可能给不同 value。

原因:

  • representation difference
  • timestamp difference
  • scale/unit difference

例如:


Conflict resolution ​

可以:

  • mean
  • median
  • mode
  • max
  • min
  • most recent
  • truth finding

Truth finding:

根据 source quality 估计哪个 source 更可信。


49. Redundancy in Integration★★★★★ ​

来源:

Same object different names ​

Derived attributes ​

例如 annual revenue 可以由 monthly revenue 得到。


为什么 redundancy 是问题? ​

课件给出一组很值得理解的式子:

若:

那么同一个 relationship 可以写:

也可以:

甚至:

因为:

所以存在大量 parameter combinations。

本质:

attributes linearly redundant → model coefficients become non-identifiable / unstable。

这就是 multicollinearity 的直觉。

因此 redundancy 可通过:

  • covariance
  • correlation

来发现。


50. Data Transformation★★★★★ ​

Transformation:

把一个 attribute 的原始 value set 映射到新的 replacement values。

方法:

  1. smoothing
  2. attribute construction
  3. aggregation
  4. normalization
  5. discretization

51. Normalization★★★★★ ​

目的:

不同 variables 尺度差异太大时,distance / optimization 可能被大尺度 attribute 主导。

例如:

text
Age:       18–80
Income: 10000–1000000

Euclidean distance 中 Income 会主导。

因此 normalize。


51.1 Min-Max Normalization★★★★★ ​

将原区间:

映射到:

公式:

推导直觉 ​

第一步:

将位置变成:

第二步 scale:

第三步 shift:


课件例子有一个数值不一致★★★★★ ​

文字写:

$73,000

但公式实际使用:

因为:

课件结果:

确实对应 ,而不是 。

如果真是:

则结果约:

所以这是 slide 中值得注意的 typo / inconsistency。


51.2 Z-score Normalization★★★★★ ​

其中:

  • :attribute mean
  • :standard deviation

意义:

raw score 与 mean 相差多少个 standard deviations。

若:

意味着:

高于 mean 1.5 SD。

课件例:

用实际 equation 中的:

则:


51.3 Decimal Scaling ​

其中 为满足:

的最小 integer。

例如最大 absolute value 为 987:

因为:


52. Discretization★★★★★ ​

定义:

Divide continuous attribute range into intervals and replace raw values by interval labels。

例如:

变:

作用:

  1. reduce data size
  2. simplify analysis
  3. prepare classification
  4. concept hierarchy

三个分类轴★★★★★ ​

Supervised vs Unsupervised ​

是否使用 labels。

Split vs Merge ​

Top-down:

text
whole interval
↓
split
↓
smaller intervals

Bottom-up:

text
many small intervals
↓
merge
↓
larger intervals

Recursive vs one-step ​

可以反复进行。


53. Discretization Methods★★★★★ ​

课件 p.80:

MethodSupervisionDirection
BinningUnsupervisedTop-down
HistogramUnsupervisedTop-down
ClusteringUnsupervisedTop-down or bottom-up
Decision treeSupervisedTop-down
Correlation / slide p.80 写 UnsupervisedBottom-up

但是 p.84 对 Chi-merge 又明确写:

Supervised: use class information。

因为 Chi-merge 比较 neighboring intervals 的:

class distributions。

因此课件内部这里存在不一致。

从 p.84 的具体机制看:

更符合其描述。

考试若老师严格按 PPT,建议记住这一处矛盾。


54. Equal-width Binning★★★★★ ​

设:

  • minimum =
  • maximum =
  • number of bins =

则:

每个 interval width 相同。

优点:

straightforward。

问题:

Outliers dominate ​

若存在极端大值:

绝大多数数据可能挤在前几个 bins。

Skewed data ​

也处理不好。


55. Equal-depth / Equal-frequency★★★★★ ​

每个 bin 包含大致相同:

优点:

better scaling for skewed data。

问题:

interval widths 会不同,而且 categorical handling tricky。


56. Binning Smoothing Example★★★★★ ​

原始排序数据:

Equal-depth:

Bin 1 ​

Bin 2 ​

Bin 3 ​


Smooth by bin means ​

Bin 1 mean:

变:

Bin 2 approximately:

Bin 3:


Smooth by boundaries ​

Bin 1 boundaries:

每个 point 替换为 nearest boundary:

因为 距 更近,而 距 更近。课件此处把 也替换为 ,是例题笔误。

Bin 2:

Bin 3:


57. Binning → Clustering 的演进★★★★☆ ​

课件 p.83:

Equal-width:

boundaries fixed by value range。

Equal-depth:

boundaries fixed by frequency。

二者共同问题:

它们不真正理解 natural groups。

于是:

K-means 等 clustering 可以根据 actual data structure 决定 partition。

方法演进:

text
Equal-width
↓
fails on skew/outliers
Equal-depth
↓
better population balance, but still rigid
Clustering
↓
data-driven boundaries

58. Supervised Discretization★★★★★ ​

Decision Tree ​

给 class labels。

例如:

利用:

entropy

选择 split point。

特点:

  • supervised
  • top-down
  • recursive

Chi-Merge ​

利用:

比较 neighboring intervals 的 class distributions。

若两个 intervals class distribution 很相近:

则 merge。

不断 merge:

until stopping condition。

特点:


59. Concept Hierarchy★★★★☆ ​

目的:

从细粒度 concepts 推到粗粒度 concepts。

例如:

或者:

支持 data warehouse 的:

  • drill-down
  • roll-up

多粒度分析。


60. Nominal Concept Hierarchy ​

四种方式:

Explicit total/partial ordering ​

Explicit grouping ​

Partial hierarchy only ​

例如只知道:

Automatic generation ​

根据:

distinct value count。


61. Automatic Concept Hierarchy★★★★☆ ​

规则:

distinct values 越多,通常层级越低。

课件:

所以:

text
country
  ↓
state
  ↓
city
  ↓
street

但有 exceptions:

  • weekday
  • month
  • quarter
  • year

不能机械只看 distinct counts。


62. Data Compression★★★☆☆ ​

String compression ​

通常:

lossless。

可以完整恢复原数据。

但不 decompress:

操作能力有限。


Audio / Video ​

通常:

lossy。

允许 approximation。

课件指出:

progressive refinement。


Time sequence ≠ audio ​

Time sequence 通常:

  • shorter
  • slowly varying

需要不同处理。


Data reduction / dimensionality reduction:

也可看作 compression。


63. Sampling★★★★★ ​

目标:

从完整数据:

抽出:

使它代表 whole dataset。

优点:

mining complexity 可以变成 sub-linear in 。

核心:


63.1 Simple Random Sampling ​

每个 item 有相同 selection probability。


Without replacement ​

被选一次后:

remove from population。

不会重复。


With replacement ​

被选后:

仍留在 population。

因此可能重复。

课件标了“why?”。

重要直觉:

有放回抽样使不同 draw 可以近似看作 independent,是 bootstrap 等统计方法的基础。

这部分是解释补充。


63.2 Stratified Sampling★★★★★ ​

先 partition:

然后每个 stratum 分别 sample。

通常按比例:

作用:

保留 minority / skewed groups。

为什么需要?

课件明确指出:

Simple random sampling 在 skewed data 上可能非常差。


一个容易忽略的点 ​

课件:

Sampling may not reduce database I/Os.

因为 database 常:

page at a time。

即使只要一个 tuple,也可能必须读整 page。


64. Data Reduction★★★★★ ​

目标:

获得:

满足:

但:

为什么?

因为 database 可能:

terabytes。

完整 mining 时间非常长。


65. Parametric vs Non-parametric Reduction★★★★★ ​

Parametric ​

假设 data obey 某 model:

然后只存:

而不是 raw data。

典型:

  • regression
  • log-linear models

优点:

compression ratio 高。

问题:

如果 model assumption 错,information loss 可能严重。


Non-parametric ​

不预设 fixed model。

典型:

  • histogram
  • clustering
  • sampling

演进直觉:

text
Parametric
→ very compact
→ but risk model misspecification

Non-parametric
→ more flexible
→ but may require more storage

66. Regression as Data Reduction★★★★☆ ​

Regression 的任务:

用:

  • dependent variable
  • independent variables

建立:

然后 raw points 可以一定程度由:

model parameters

表示。


66.1 Linear Regression★★★★★ ​

其中:

  • :slope
  • :intercept

目标:

best fit。

课件主要说:

least squares。

标准 least-squares objective 可写:

这条 objective 是对“least squares”的数学展开。


Why square error? ​

Error:

若直接 sum:

positive / negative 可能互相取消。

平方:

保证非负,同时 stronger penalty large errors。


66.2 Nonlinear Regression ​

形式:

其中 对 parameters 可以 nonlinear。

课件:

fitted by successive approximations。

也就是通常不能一步 closed-form solution,需要 iterative optimization。


66.3 Multiple Regression★★★★★ ​

课件:

更一般:

用于 multidimensional feature vector。


67. Log-Linear Model★★★☆☆ ​

核心:

一个 function 取 logarithm 后,对 model parameters 是 linear combination。

一般直觉:

于是可以利用 linear modeling techniques。

课件用途:

对 discretized multidimensional attributes,通过少量 marginal combinations 估计整个 multidimensional space 中 tuples 的 probability。

用途:

  • dimensionality reduction
  • smoothing

68. Histogram as Reduction★★★☆☆ ​

将原始 observations:

divide into buckets。

每个 bucket 只存:

  • average
  • sum
  • frequency

因此从 many raw values:

变成少量 bucket summaries。

partition:

  • equal-width
  • equal-frequency

69. Clustering as Reduction★★★★☆ ​

先把:

partition into clusters:

然后不存所有 points,只存 cluster representation,例如:

  • centroid
  • diameter

如果 data 天然 clustered:

very effective。

如果 data “smeared”:

approximation 较差。

也可以 hierarchical clustering:

存到 multidimensional index tree。


70. Dimensionality Reduction:为什么需要?★★★★★ ​

这一部分是全章最后的大高潮。

Curse of dimensionality:

当:

会发生:

1. Data sparsity ↑ ​

有限 分散到越来越大的 feature space。

2. Distance less meaningful ​

最近邻和远邻距离趋于接近。

因此:

  • clustering
  • outlier detection

变差。

3. Number of subspaces exponential ​

若每个 feature 可选 / 不选:

possible subsets。


71. DR 的两个根本路线★★★★★ ​

Feature Selection ​

从原 features:

中选择 subset:

特点:

原始 feature semantics 保留。


Feature Extraction ​

构造新 features:

其中:

并且:

PCA 就属于:


72. PCA★★★★★ ​

定义:

使用 orthogonal transformation,把可能 correlated 的 variables 转换成 linearly uncorrelated principal components。

核心目标:

同时尽量保留:

variance / information。


73. PCA 的核心几何思想★★★★★ ​

假设二维 points 沿一条 diagonal 方向排列。

原 coordinates:

高度 correlated。

真正自由度可能只有:

沿 diagonal 的一个 direction。

PCA 寻找:

使 projection variance 最大。

剩余 orthogonal direction:

variance 很小。

于是只保留:

完成:


74. PCA 与 Covariance Matrix★★★★★ ​

课件核心:

这里的 实际是 covariance matrix:

因此:

其中:

  • :eigenvector → principal component direction
  • :eigenvalue → variance along that direction

所以:

按 eigenvalue 从大到小排序。


75. 为什么 eigenvector 就是最大 variance direction?★★★★★ ​

这是 PCA 最值得会推导的一步。

假设数据已经 centered:

选择 unit vector:

project:

variance:

centered data 有:

所以:

目标:

subject to:

构造 Lagrangian:

对 求导:

得到:

而此时:

因此:

variance 最大的 direction,就是 largest eigenvalue 对应 eigenvector。

这就是 PCA 最核心数学逻辑。


76. PCA Algorithm★★★★★ ​

课件 pp.103–105:

Step 1 ​

Normalize data,使 attributes roughly comparable。

Step 2 ​

计算 covariance matrix:

Step 3 ​

求:

  • eigenvalues
  • eigenvectors

满足:

Step 4 ​

排序:

Step 5 ​

保留 top eigenvectors:

Step 6 ​

project data:

这里 是每列均值。只有在前一步已经把 明确记作中心化后的数据矩阵时,才可简写为 ;中心化不是可随意省略的 convention。


课件关于 preprocessing 的一个理解细节 ​

课件写:

Normalize input data: Each attribute falls within the same range.

严格 PCA 数学中最基本的是:

center data。

即:

是否进一步 scale 到相同 range / standard deviation:

取决于应用。

不过考试按 PPT 应记:

PCA 前先 normalize,使 attributes comparable。


77. PCA 为什么可以降维?★★★★★ ​

原向量可以表示:

如果:

很大,而:

很小。

则 weak components 贡献很小。

近似:

因此只存:

即可。


78. PCA 局限★★★★★ ​

课件:

  1. numeric data only
  2. linear method
  3. each PC 是 original attributes 的 linear combination

适合:

  • 主要结构近似位于低维 linear subspace;
  • 希望用最大方差方向作线性压缩/可视化。

approximately Gaussian 只是一种常见的经验情形;PCA 不要求数据 Gaussian,也不以“类别线性可分”为必要条件或目标。

问题:

若 data 在 nonlinear manifold 上:

PCA 只能做 linear rotation/projection。

于是进入 nonlinear dimensionality reduction。


79. Attribute Subset Selection★★★★★ ​

另一条 DR 路线。

删除:

Redundant attributes ​

例如:

  • purchase price
  • sales tax

若 sales tax 是固定比例:

则高度 redundant。


Irrelevant attributes ​

例如预测 GPA 时:

Student ID。

它几乎不携带 predictive information。


80. Feature Selection 为什么不能 exhaustive search?★★★★★ ​

若 features:

每个 feature:

  • choose
  • not choose

所以:

possible subsets。

当:

则:

完全不可穷举。

因此需要:

heuristic search。


81. Feature Selection Heuristics★★★★★ ​

Best single attribute ​

在 independence assumption 下:

用 significance test 选最强单 feature。

问题:

interaction features 可能单独都不强,但组合很强。


Step-wise Forward Selection ​

流程:

text
∅
↓
选最好 feature
↓
在已有 subset 条件下继续加最好 feature
↓
repeat

Step-wise Elimination ​

从:

开始。

不断:

remove worst feature。


Combined Selection + Elimination ​

Forward + backward 交替。

比纯 forward 更好,因为:

一个 feature 加入后,之前 feature 的价值可能变化。


Branch and Bound ​

使用:

  • elimination
  • backtracking

尝试找到更接近 optimal subset。


82. Combined Selection Example★★★★☆ ​

预测 final score:

  • :StudyHours
  • :Attendance
  • :FavoriteColor

Null model:

单独加入:

所以先选:

第二步加入:

模型:

Backward check:

两者 significant → keep。

再试:

没有 improvement:

reject。

最终:


83. Feature Generation★★★★☆ ​

不是删 feature,而是:

构造比原 features 更有效的新 features。

三类:

Attribute extraction ​

domain-specific。

Mapping to new space ​

例如:

  • Fourier transform
  • Wavelet transform
  • Manifold methods

Attribute construction ​

组合已有 features。

也包括:

discretization。


84. PCA → Nonlinear DR:关键方法演进★★★★★ ​

这是本章方法论演进最明显的一段。

text
High dimensional data
↓
PCA
↓
preserve largest linear variance
↓
Problem:
nonlinear manifold cannot be unfolded by linear projection
↓
Construct pairwise proximity P
↓
Instead of preserving coordinates,
preserve relationships
↓
KPCA / SNE

核心思想发生了变化:

PCA:

preserve variance。

Nonlinear DR:

preserve pairwise proximity / neighborhood structure。


85. Nonlinear DR 的统一框架★★★★★ ​

输入:

构造 proximity matrix:

其中:

表示 的 similarity / neighborhood relationship。

然后学习:

其中:

使低维空间中的:

尽量保留:

即:


86. Kernel PCA★★★★★ ​

核心:

不直接在 input coordinates 做 PCA,而是通过 kernel 建模 nonlinear similarity。

构造:

其中:

为 kernel function。

然后使用 kernel matrix 的:

top- eigenvectors/eigenvalues。


87. Polynomial Kernel★★★★☆ ​

课件:

其中:

  • :dot product
  • :polynomial degree

它隐式对应:

higher-order interaction features。


88. RBF Kernel★★★★★ ​

课件:

其中:

  • :Euclidean distance
  • :kernel bandwidth

若两点接近:

则:

若远:

因此 RBF kernel 把 distance 转成 local similarity。


89. KPCA preserving proximity★★★★★ ​

课件给 Step 2:

也写作:

其中:

即 Frobenius norm。

意思:

让低维 representation 重建出来的 proximity matrix 与原 kernel matrix 尽量一致。


90. Linear kernel 为什么退化到 PCA?★★★★★ ​

如果:

没有 nonlinear transformation。

此时 kernel matrix 只表达普通 linear inner products。

课件:


91. SNE★★★★★ ​

SNE:

它不再把 proximity 当普通 real-valued similarity,而是:

变成 neighbor probability。


91.1 High-dimensional Proximity ​

课件定义:

然后:

含义:

对于固定 :

所以 是一个 probability distribution。


91.2 Low-dimensional proximity ​

学习:

以后,在 low-dimensional space 用类似方式计算:

现在目标:

高维 neighborhood distribution 和低维 neighborhood distribution 尽量相同。


91.3 为什么 SNE 用 KL?★★★★★ ​

因为:

都是 probability distributions。

因此自然使用:

比较。

Objective:

课件写作:

更严格地说应理解为:

jointly optimize all low-dimensional coordinates。

这正好把本章前面的 KL divergence 用到了最后的 nonlinear DR 中。

这是本章隐藏得非常漂亮的一条知识闭环:

text
Probability-distribution similarity
        ↓
    KL divergence
        ↓
Neighborhood distribution
        ↓
       SNE

★★★★★ 很值得记。


92. PCA vs KPCA vs SNE★★★★★ ​

方法保留什么Relationship representation核心 objectiveLinear?
PCAvariancecovariancemax varianceYes
KPCAkernel proximityNonlinear
SNEneighborhood probabilityNonlinear

更深层的演进:

text
PCA
坐标方差
↓
KPCA
pairwise kernel similarity
↓
SNE
pairwise similarity → probability distribution
↓
通过 KL 保 neighborhood

93. PCA 为什么不能解决课件的 nonlinear example?★★★★★ ​

pp.113–114 图中:

红蓝数据形成类似弯曲 / moon-shaped nonlinear structures。

原数据:

not linearly separable。

PCA:

只能 rotate + linear project。

线性 transformation:

无法把 nonlinear topology 真正“展开”。

因此:

PCA 后依然不 linearly separable。


KPCA:

通过 nonlinear kernel:

隐式映射到高维 feature space。

在那里:

nonlinear boundary 可能变成 linear。

所以可以更好分开。


t-SNE:

通过 preservation of neighborhood:

直接让同类 local neighborhoods 聚集、不同结构分离。

课件结果也显示:

可以把红蓝 structures 分开。

课件本章没有给出 t-SNE 的 Student- low-dimensional formula,所以这里不额外把未出现在 slide 的 t-SNE 数学公式混入考试笔记。


94. Proximity Heatmap:应该会读图★★★★☆ ​

p.114:

matrix 按:

text
red samples
blue samples

排序。

得到四个 blocks:

text
          red      blue
red      RR       RB
blue     BR       BB

Diagonal:

  • RR
  • BB

表示:

within-cluster proximity。

Off-diagonal:

  • RB
  • BR

表示:

between-cluster proximity。

好的 representation 应满足:

课件指出:

KPCA / t-SNE:

比 linear PCA 更清晰地形成 diagonal blocks。


95. 本章最核心的“Why it fails → How it fixes”总表★★★★★ ​

Old method/problemWhy it failsNext methodHow it fixes
Meanoutlier-sensitiveMedian / Trimmed mean减弱 extremes
Five-number summary丢失 distribution shapeHistogram显示完整 shape
Covariancescale-dependentCorrelation除以 SD 标准化
Euclidean for all data不同 attribute semanticstype-specific proximity按 nominal/binary/ordinal 处理
Symmetric matching0–0 对 rare event 无意义Jaccard忽略 joint absence
Euclidean for documentsdocument length dominatesCosine比 direction 而非 magnitude
Vector comparison不能比较 distributionsKL divergenceinformation-based distribution difference
Hand-crafted similarityhidden semantics 丢失Representation learning学习 semantic representation
Raw dirty datamissing/noise/inconsistencyCleaninginference/smoothing/auditing
Separate sourcesconflicts/redundancyIntegrationschema/entity/conflict resolution
Different scalesdistance 被大-scale feature 主导Normalizationcommon scale
Raw continuous valuesgranular, noisy, largeDiscretizationintervals/concepts
Equal-width binsskew/outliersEqual-depthequal population
Equal-depthrigid boundariesClusteringdata-driven partitions
Unsupervised discretization不关心 target labelDecision tree / Chi-Mergeuse class information
Full datasetcomputationally expensiveSampling / reductionsmaller representation
Random samplingminority/skew 被漏掉Stratified samplingpreserve groups
Parametric reductionmodel misspecificationNon-parametricfewer assumptions
High-dimensional raw datacurse of dimensionalityDRsmaller principal representation
Exhaustive feature selectionheuristic selectiontractable search
PCAonly linearKPCAnonlinear kernel
Coordinate preservationnonlinear neighborhood poorly preservedSNEpreserve probabilistic neighborhoods

96. 一张表彻底区分“Reduction”相关概念★★★★★ ​

方法减少什么是否改变 feature semantics
Samplingrows / objects否
Histogramraw values是,变 aggregate
Clustering reductionobjects用 cluster representative
Compressionstoragedepends
Feature selectioncolumns保留
PCAdimensions改变
KPCAdimensions改变
SNE/t-SNEdimensions改变
Discretizationnumber of distinct values改变 value representation

这是考试中非常容易混的一组概念。


97. 必须背熟的公式清单★★★★★ ​

建议最后复习时至少能无提示写出这些。

Mean ​

Weighted mean ​

Grouped median ​

Mean-mode-median ​

Sample variance ​

Computational variance ​

Random-variable variance ​

Chi-square ​

Expected count ​

Degrees of freedom ​

Covariance ​

Correlation ​

Covariance matrix ​

IQR ​

Minkowski ​

Manhattan ​

Euclidean ​

Chebyshev ​

Symmetric binary ​

Asymmetric binary ​

Jaccard ​

Nominal simple matching ​

Ordinal mapping ​

Mixed attributes ​

Cosine ​

KL discrete ​

KL continuous ​

Min-Max ​

Z-score ​

Decimal scaling ​

Equal-width bin ​

Linear regression ​

Multiple regression ​

PCA eigenproblem ​

PCA projection ​

Polynomial kernel ​

RBF ​

KPCA proximity objective ​

SNE distance ​

SNE neighbor probability ​

SNE objective ​


98. 期末特别容易出错的 15 个点★★★★★ ​

  1. Numeric-looking ID 不等于 numeric attribute。
  2. Ordinal 有 order,但 interval spacing 未知。
  3. Celsius 是 interval,Kelvin 是 ratio。
  4. Binary 可以 symmetric 或 asymmetric。
  5. Positive skew:
  6. Sample variance 和 population variance denominator 不同。
  7. Covariance 0 不代表 independence。
  8. Correlation 不代表 causality。
  9. Correlation 0 也不代表没有 nonlinear relationship。
  10. Histogram 是 quantitative distribution;bar chart 是 categorical comparison。
  11. Jaccard 不计算 0–0 match。
  12. KL divergence asymmetric,因此不是 metric。
  13. Equal-width 对 skew/outlier 很敏感。
  14. PCA 做 feature extraction,不是 feature selection。
  15. PCA 只能 linear;KPCA / SNE 解决 nonlinear structure。

99. 课件中两个值得特别记的“不一致 / 易混点” ​

第一,p.78 Normalization 的文字写的是 $73,000,但公式和最终结果 实际对应 $73,600。考试计算时以给出的实际 numeric expression 为准。

第二,p.80 把 correlation/ discretization 写成 “unsupervised”,但 p.84 的 Chi-Merge 明确写 “supervised: use class information”,并且其算法确实需要比较 neighboring intervals 的 class distributions。因此按方法定义和 p.84,应理解为:


100. 最后用一句话串起整个 Chapter★★★★★ ​

这章真正的逻辑不是:

“先统计,再清洗,再 PCA。”

而是:

先理解数据的语义与类型,才能选择正确的统计量与相似度;理解数据之后,再解决现实数据中的缺失、噪声、冲突和尺度问题;当数据仍然过大或过高维时,用 sampling、compression、feature selection 和 PCA 减少复杂度;当 PCA 的线性假设无法描述真实结构时,再把目标从“保留线性方差”升级为“保留 nonlinear proximity / neighborhood”,最终得到 KPCA 和 SNE。

即:

这就是整个 Chapter 2 的底层架构。


高密度复习:Data / Preprocessing ​

先判数据类型,再选距离与处理 ​

类型合法操作常用相异度 / 注意
Nominal / simple matching;类别编码不应被误当有大小
Symmetric binary0、1 同等重要match / mismatch
Asymmetric binary“1”出现更重要共同 0 忽略:该维度
Ordinal排名 + 间距不一定相等先 rank-normalize 再按 numeric 处理
Interval差有意义、零点任意Euclidean / standardized distance
Ratio差与比都可解释可按 numeric;留意长尾/尺度
Text / sparse vector方向常比长度重要cosine;

预处理五件事 ​

目标常见方法易错点
Cleaningmissing imputation、noise smoothing、outlier handling不要把异常一律当噪声删掉
Integrationschema/entity resolution、redundancy/correlation同一实体可能有不同 ID/单位
Transformationnormalization、aggregation、encoding、feature constructiontrain/test 必须使用同一拟合参数
Reductionsampling、aggregation、feature selection、PCAreduction 要保留任务相关信息
Discretizationbinning、histogram、entropy-basedboundaries 是端点;按“最近端点”计算

高频公式 ​

Pearson 的拒绝条件要写 显著性水平 ; 对应 confidence level ,不是 “confidence level 0.001”。

PCA 必背 ​

  1. 对数据中心化(必要;尺度差异大时通常再 standardize)。
  2. 求 covariance matrix / SVD,取最大 eigenvalues 对应的 。
  3. 投影:;只有 已中心化时才可写 。
  4. PCA 是线性、最大方差的表示法;不要求 Gaussian 或类别线性可分,也不保证保留分类边界。

已确认的课件陷阱 ​

  • cosine 例中 :,;课件的 4.12 / 0.94 是算术错误。
  • binning boundaries 例首 bin 应为 ,不是 。
  • mixed-type formula 要排除 asymmetric binary 的 joint absence。

Static academic notes built with VitePress and KaTeX.