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.
[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)
[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)
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:63189", author = "Timothee G. Leleu", title = "Recursive Similarity Hashing of Fractal Geometry", 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.", volume = "4", number = "4", pages = "384-8", }
