“This paper here shows some interesting applications - it is not the first one, but the first non-paywalled one that I found:”
Clustering by compression
用归一化压缩距离 NCD 做不依赖领域知识的通用聚类
论文提出一种基于压缩的聚类方法,不使用特定领域的特征或背景知识:先根据单个与两两拼接后压缩文件的长度计算通用相似度距离,即归一化压缩距离(NCD),再做层次聚类。NCD 是理论上最优但不可计算的归一化信息距离(基于 Kolmogorov 复杂度)的可计算近似,作者用新的四元组方法生成树状图,并在基因组学、病毒学、语言、文学、音乐、手写数字、天文等多个领域验证了其通用性与对压缩器选择的稳健性,还对哺乳动物进化问题给出了新证据。
评论者用它说明「直接用压缩来聚类」这个老而仍然有用的思想,例如按语系谱系对语言分组,并把它与用可计算指标近似 Kolmogorov 复杂度联系起来。
学习路径
读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出候选里只有一篇与压缩式聚类直接相关,所以路径较短:先看用压缩软件衡量文本相似性的先驱工作,再读 NCD 的系统化版本。
- 1
用 gzip 一类压缩器衡量文本之间的相对熵并据此建语言树,是 NCD 思路的直接前身。
读抓如何用压缩后的长度近似文本间的距离,以及用它对语言做聚类和作者归属的例子。
- 2Clustering by compression
目标论文:把这类思路形式化为归一化压缩距离 NCD,并配合层次聚类。
读抓 NCD 的定义与公式、它对 Kolmogorov 复杂度的近似关系,以及不同领域的聚类实验。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“See this paper on how to cluster using compression: Clustering by compression”
“The emphasis in this paper was not on "efficiency", but rather on phylogenetic grouping.”
“This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons.”
“Sometimes you can even use compression directly, like here: Clustering by compression.”