|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
NormalizedCompressionDistance(NCD)是一种用真实压缩器近似Kolmogorov复杂度的无参相似度度量,它通过比较单个文件与拼接文件的压缩长度差异来衡量关联度。
学术评估显示,用NCD可自动重建语言与基因组的系统发生树,且效果与专用生物信息方法相当。
该方法的魅力在于通用性:无需了解数据内容,只要能用ZIP等无损压缩器处理就能使用。
在线学习:
相比之下,像JPEG这类有损压缩格式会丢弃信息,因此不适合作距离度量。
典型无损压缩器(如ZIP采用的DEFLATE算法)通过滑动窗口和指针重用早先出现的短语来缩短比特序列,从而把文件映射到更短的二进制串。
若一个文件高度重复,其压缩后长度将远小于原长度,而随机或复杂数据几乎无法被进一步缩短,这一现象可视为Kolmogorov复杂度的经验估计。
于是研究者提出公式NCD(X,Y)=(C(XY)-min(C(X),C(Y)))/max(C(X),C(Y)),将拼接压缩长度与单独压缩长度结合,得到介于0和1的归一化距离。
此度量无需任何特征工程且跨文本、基因、音频等任意二进制数据域均可直接应用。
小甲鱼老师课程:
评论区聊聊你的想法吧
如果有收获,别忘了评分 :
|
|