归一化压缩距离
概述
归一化压缩距离（NCD）是基于 Kolmogorov 复杂性的近似距离度量，用于无参数聚类和分类，是算法信息论在数据挖掘中的直接应用。
关键内容
定义
归一化压缩距离基于 Kolmogorov 复杂性的归一化信息距离：
$$NCD(x, y) = \frac{C(xy) - \min(C(x), C(y))}{\max(C(x), C(y))}$$
其中 C(x) 是 x 的压缩长度（K(x) 的可计算近似），C(xy) 是 x 和 y 拼接后的压缩长度。
直觉
如果 x 和 y 高度相似，那么 C(xy) ≈ C(x) ≈ C(y)，NCD 接近 0。如果 x 和 y 完全不相关，那么 C(xy) ≈ C(x) + C(y)，NCD 接近 1。
应用
- 无参数聚类：不需要预先指定距离函数，压缩算法自动发现数据的内在相似性
- 语言分类：基于文本压缩距离自动将文档按语言分类
- 音乐分类：基于 MIDI 文件压缩距离自动将音乐按风格分类
- 基因组学：基于 DNA 序列压缩距离进行物种分类
优势
NCD 是"万能"距离度量——它不依赖于特定领域知识，适用于任何可以用比特串表示的数据。
来源
- raw/books/信息论/09_kolmogorov_1965_three_approaches_to_information.md — Kolmogorov (1965) 深度解析