按年被提到
20032018 · 2 次2026
机器学习与深度学习›贝叶斯方法与 AutoML·arXiv:cs/0312044 · cs.CV

Clustering by compression

通过压缩进行聚类
Rudi Cilibrasi, Paul Vitanyi · 2003

用归一化压缩距离 NCD 做不依赖领域知识的通用聚类

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2018-08-10 · 最近 2024-07-11
5不同的人
5活跃月份
5讨论串
1,180被引(OpenAlex)

论文提出一种基于压缩的聚类方法,不使用特定领域的特征或背景知识:先根据单个与两两拼接后压缩文件的长度计算通用相似度距离,即归一化压缩距离(NCD),再做层次聚类。NCD 是理论上最优但不可计算的归一化信息距离(基于 Kolmogorov 复杂度)的可计算近似,作者用新的四元组方法生成树状图,并在基因组学、病毒学、语言、文学、音乐、手写数字、天文等多个领域验证了其通用性与对压缩器选择的稳健性,还对哺乳动物进化问题给出了新证据。

HN 为什么提它

评论者用它说明「直接用压缩来聚类」这个老而仍然有用的思想,例如按语系谱系对语言分组,并把它与用可计算指标近似 Kolmogorov 复杂度联系起来。

方法难度 4 / 5约 60 分钟经得起时间
读之前最好知道
1Kolmogorov 复杂度
2数据压缩与常见压缩器(如 gzip、bzip2)
3层次聚类与树状图(dendrogram)
4信息距离(information distance)

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

候选里只有一篇与压缩式聚类直接相关,所以路径较短:先看用压缩软件衡量文本相似性的先驱工作,再读 NCD 的系统化版本。

  1. 1

    用 gzip 一类压缩器衡量文本之间的相对熵并据此建语言树,是 NCD 思路的直接前身。

    读抓如何用压缩后的长度近似文本间的距离,以及用它对语言做聚类和作者归属的例子。

  2. 2
    Clustering by compression通过压缩进行聚类 · 2003 · 就是这篇

    目标论文:把这类思路形式化为归一化压缩距离 NCD,并配合层次聚类。

    读抓 NCD 的定义与公式、它对 Kolmogorov 复杂度的近似关系,以及不同领域的聚类实验。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐sischoel · 2021-05

“This paper here shows some interesting applications - it is not the first one, but the first non-paywalled one that I found:”

推荐它展示了有趣的应用,是找到的第一篇无付费墙的
Kolmogorov Complexity: Extensions and Applications原评论 ↗
引用jkabrg · 2018-08

“See this paper on how to cluster using compression: Clustering by compression”

给出如何用压缩做聚类的论文
Functional Bits: Lambda-calculus based algorithmic information theory [pdf]原评论 ↗
引用bediger4000 · 2018-12

“The emphasis in this paper was not on "efficiency", but rather on phylogenetic grouping.”

说明论文重点不在效率,而在系统发生学式的分组
The World's Most Efficient Languages (2016)原评论 ↗
引用nextos · 2023-07

“This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons.”

指出这是个老想法,但仍然很有用,如同感知机
Gzip and KNN Outperforms Transformers on Text Classification原评论 ↗
引用Kim_Bruning · 2024-07

“Sometimes you can even use compression directly, like here: Clustering by compression.”

举例说明有时可以直接用压缩来做聚类
Judge dismisses DMCA copyright claim in GitHub Copilot suit原评论 ↗