Recursive Similarity Hashing of Fractal Geometry

Authors: Timothee G. Leleu

Abstract:

A new technique of topological multi-scale analysis is introduced. By performing a clustering recursively to build a hierarchy, and analyzing the co-scale and intra-scale similarities, an Iterated Function System can be extracted from any data set. The study of fractals shows that this method is efficient to extract self-similarities, and can find elegant solutions the inverse problem of building fractals. The theoretical aspects and practical implementations are discussed, together with examples of analyses of simple fractals.

Keywords: hierarchical clustering, multi-scale analysis, Similarity hashing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082509

References:

[1] S. Wiggins, Introduction to Applied Nonlinear Dynamical Systems and Chaos, (Texts in Applied Mathematics 2, Springer-Verlag)
[2] J. Guckenheimer and P. Holmes, Nonlinear Oscillations, Dynamical systems and Bifurcations of Vector Fields (Springer, 1983)
[3] Pavliotis GA, Stuart AM, Multiscale Methods Averaging and Homogenization (New York , Springer, 2007 , ISBN: 9780387738284)
[4] F. Takens, Detecting strange attractors in turbulence (Dynamical Systems and Turbulence, Lecture Notes in Mathematics, vol. 898. Springer-Verlag. pp. 366-381)
[5] H. E. Stanley and P. Meakin, Multifractal Phenomena in Physics and Chemistry, Nature 335, 405-409 (1988).
[6] Tim Palmer, Paul Williams, Stochastic Physics and Climate Modelling (Royal Society Publishing, 2008, ISBN 9780854036950)
[7] L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E. Stanley, Classes of Behavior of Small-World Networks (Proc. Natl. Acad. Sci. 97, 11149-11152 (2000))
[8] G. Binnig et al., Will machines start to think like humans? (Europhysics News (2002) Vol. 33 No. 2)
[9] Palmer, T. N., The Invariant Set Postulate: a new geometric framework for the foundations of quantum theory and the role played by gravity (Proceedings of the Royal Society a Mathematical Physical and Engineering Sciences 465: 3165. doi:10.1098/rspa.2009.0080)
[10] Michael F. Barnsley, Fractal Everywhere (second edition, Hawley Rising)
[11] Paul S. Addison, The Illustrated Wavelet Transform Handbook (Institute of Physics, 2002, ISBN 0-7503-0692-0)
[12] P. Abry, P. Gon├ºalvès & J. Lévy-Véhel, Scaling Fractals And Wavelets (iSTE Publishing Company, 2005)
[13] John C. Hart, Wayne O. Cochran, Patrick J. Flynn, Similarity Hashing: A Computer Vision Solution to the Inverse Problem of Linear Fractals (Washington State University, 2008)
[14] C.R Handy and G. Mantica, Inverse problems in fractal construction: moment method solution (Physica D 43 (1990) 17-36)
[15] R. Rinaldo and A. Zakhor, Inverse and Approximation Problem for Two-Dimensional Fractal sets (IEEE trans. on image processing, Vol.3, No. 6)
[16] R. Shonkwiler, F.Mendivil, A.Deliu, Genetic Algorithms for the 1-D Fractal Inverse Problem (Georgia Institute of Technology)
[17] Timothee Leleu, Akito Sakurai, Recurrent self-similarties and machine learning: the inverse problem of buiding fractals (Proceedings of Mendel 2009)
[18] Xin Zhou and David P. Tuck, MSVM-RFE: extensions of SVM-RFE for multiclass gene selection on DNA microarray data (Bioinformatics 2007 23(9):1106-1114)
[19] Jörg Sander, Martin Ester, Hans-Peter Kriege, Hans-Peter Kriegel, Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Application (Data Mining and Knowledge Discovery archive, Volume 2 , Issue 2 , ISSN:1384-5810 (June 1998))
[20] T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, A Local Search Approximation Algorithm for k-Means Clustering (Computational Geometry: Theory and Applications, 28 (2004), 89-112.))
[21] Sloan's A008277, The On-Line Encyclopedia of Integer Sequences
[22] Timothee G. Leleu, Building "invertible" fractals: Introduction to Context-Dependant Iterated Function Systems, Proc. 2010 International Joint Conference on Neural Networks (IJCNN 2010)
[23] D Barbará, P Chen, Using the fractal dimension to cluster datasets (Proceedings of the sixth ACM SIGKDD, 2000)
[24] CA Duncan, MT Goodrich, SG Kobourov, Balanced aspect ratio trees and their use for drawing very large graphs (Lecture Notes in Computer, Springer, 1998)
[25] Michael F. Barnsley and Lyman P. Hurd, Fractal Image Compression, ISBN 0-86720-457-5
[26] T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, An efficient k-means clustering algorithm: Analysis and implementation (IEEE Trans. Pattern Analysis and Machine Intelligence, 24 (2002), 881-892)
[27] Chris Ding and Xiaofeng He, K-means Clustering via Principal Component Analysis (Proc. of Int'l Conf. Machine Learning (ICML 2004), pp 225-232. July 2004)
[28] T. Vicsek, Fractal Growth Phenomena, 2nd ed. (World Scientific, Singapore 1991).
[29] H. A. Makse, J. S. de Andrade, M. Batty, S. Havlin, and H. E. Stanley, Modeling Urban Growth Patterns with Correlated Percolation (Phys. Rev. E, 1 December, 1998)