GENERALIZED COMPRESSION DICTIONARY DISTANCE AS UNIVERSAL SIMILARITY MEASURE

We present a new similarity measure based on information theoretic measures which is superior than Normalized Com-pression Distance for clustering problems and inherits the useful properties of conditional Kolmogorov complexity. We show that Normalized Compression Dictionary Size and Normalized Compression Dictionary Entropy are com-putationally more efficient, as the need to perform the com-pression itself is eliminated. Also they scale linearly with ex-ponential vector size growth and are content independent. We show that normalized compression dictionary distance is compressor independent, if limited to lossless compres-sors, which gives space for optimizations and implementation speed improvement for real-time and big data applications. The introduced measure is applicable for machine learn-ing tasks of parameter-free unsupervised clustering, super-vised learning such as classification and regression, feature selection, and is applicable for big data problems with order of magnitude speed increase. Index Terms — dissimilarity, distance function, normal-ized compression distance, time-series clustering, parameter-free data-mining, heterogenous data analysis, Kolmogorov complexity, information theory, machine learning, big data 1