Clustering with respect to the information distance

被引：1
作者：
Romashchenko, Andrei [1 ,2 ]
机构：
[1] LIRMM, 161 Rue Ada, F-34095 Montpellier, France
[2] Univ Montpellier, LIRMM, CNRS, Montpellier, France
来源：
THEORETICAL COMPUTER SCIENCE | 2022年 / 929卷
关键词：
Kolmogorov complexity; Information distance; Clusters; ENTROPY;
D O I：
10.1016/j.tcs.2022.06.039
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We discuss the notion of a dense cluster with respect to the information distance and prove that all such clusters have an extractable core that represents the mutual information shared by the objects in the cluster. (C) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页码：164 / 171
页数：8
相关论文
共 18 条
[1]   Information distance [J].
Bennett, CH ;
Gacs, P ;
Li, M ;
Vitanyi, FMB ;
Zurek, WH .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (04) :1407-1423
[2]   Algorithmic clustering of music based on string compression [J].
Cilibrasi, R ;
Vitányi, P ;
de Wolf, R .
COMPUTER MUSIC JOURNAL, 2004, 28 (04) :49-67
[3]   Clustering by compression [J].
Cilibrasi, R ;
Vitányi, PMB .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (04) :1523-1545
[4]  
Epstein Samuel, 2021, ARXIV
[5]  
Gacs P., 1973, Problems of Control and Information Theory, V2, P149
[6]   Inequalities for Shannon entropy and Kolmogorov complexity [J].
Hammer, D ;
Romashchenko, A ;
Shen, A ;
Vereshchagin, N .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 60 (02) :442-464
[7]   3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].
KOLMOGOROV, AN .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+
[8]   LOGICAL BASIS FOR INFORMATION THEORY AND PROBABILITY THEORY [J].
KOLMOGOROV, AN .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (05) :662-+
[9]   The similarity metric [J].
Li, M ;
Chen, X ;
Li, X ;
Ma, B ;
Vitányi, PMB .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (12) :3250-3264
[10]  
Li M., 2008, INTRO KOLMOGOROV COM
12