Geodesic
Symmetry in Data Mining and Analysis: A~Unifying View Based on Hierarchy
Informatics and Automation, Selected topics of mathematical physics and $p$-adic analysis, Tome 265 (2009), pp. 189-210.

Voir la notice de l'article provenant de la source Math-Net.Ru

Data analysis and data mining are concerned with unsupervised pattern finding and structure determination in data sets. The data sets themselves are explicitly linked as a form of representation to an observational, or otherwise empirical, domain of interest. “Structure” has long been understood as symmetry which can take many forms with respect to any transformation, including point, translational, rotational, and many others. Symmetries directly point to invariants that pinpoint intrinsic properties of the data and of the background empirical domain of interest. As our data models change, so too do our perspectives on analyzing data. The structures in data surveyed here are based on hierarchy, represented as $p$-adic numbers or an ultrametric topology. 
@article{TRSPY_2009_265_a16,
     author = {F. Murtagh},
     title = {Symmetry in {Data} {Mining} and {Analysis:} {A~Unifying} {View} {Based} on {Hierarchy}},
     journal = {Informatics and Automation},
     pages = {189--210},
     publisher = {mathdoc},
     volume = {265},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2009_265_a16/}
}
TY  - JOUR
AU  - F. Murtagh
TI  - Symmetry in Data Mining and Analysis: A~Unifying View Based on Hierarchy
JO  - Informatics and Automation
PY  - 2009
SP  - 189
EP  - 210
VL  - 265
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2009_265_a16/
LA  - en
ID  - TRSPY_2009_265_a16
ER  - 
%0 Journal Article
%A F. Murtagh
%T Symmetry in Data Mining and Analysis: A~Unifying View Based on Hierarchy
%J Informatics and Automation
%D 2009
%P 189-210
%V 265
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2009_265_a16/
%G en
%F TRSPY_2009_265_a16
F. Murtagh. Symmetry in Data Mining and Analysis: A~Unifying View Based on Hierarchy. Informatics and Automation, Selected topics of mathematical physics and $p$-adic analysis, Tome 265 (2009), pp. 189-210. http://geodesic.mathdoc.fr/item/TRSPY_2009_265_a16/

[1] Bandt C., “Ordinal time series analysis”, Ecol. Modell., 182 (2005), 229–238 | DOI

[2] Bandt C., Pompe B., “Permutation entropy: A natural complexity measure for time series”, Phys. Rev. Lett., 88:17 (2002), Pap. 174102 | DOI

[3] Bandt C., Shiha F., “Order patterns in time series”, J. Time Series Anal., 28:5 (2007), 646–665 ; http://www.math-inf.uni-greifswald.de/~bandt/pub/orderpattern3.pdf | DOI | MR | Zbl

[4] Baraniuk R. G., Cevher V., Duarte M. F., Hegde C., Model-based compressive sensing, E-print , 2008 arXiv: 0808.3572

[5] Benedetto J. J., Benedetto R. L., “A wavelet theory for local fields and related groups”, J. Geom. Anal., 14 (2004), 423–456 | DOI | MR | Zbl

[6] Benedetto R. L., “Examples of wavelets for local fields”, Wavelets, frames and operator theory, Contemp. Math., 345, eds. C. Heil, P. E. T. Jorgensen, D. R. Larson, Amer. Math. Soc., Providence, RI, 2004, 27–47 | DOI | MR | Zbl

[7] Benzécri J.-P., L'analyse des données. T. 1: La taxinomie, 2nd ed., Dunod, Paris, 1979 | MR

[8] Bradley P. E., “Mumford dendrograms”, Comput. J., 2008; http://comjnl.oxfordjournals.org/cgi/content/abstract/bxm088

[9] Brekke L., Freund P. G. O., “$p$-Adic numbers in physics”, Phys. Rep., 233 (1993), 1–66 | DOI | MR

[10] Chakraborty P., Looking through newly to the amazing irrationals, E-print , 2005 arXiv: math/0502049v1

[11] Costa M., Goldberger A. L., Peng C.-K., “Multiscale entropy analysis of biological signals”, Phys. Rev. E, 71:2 (2005), Pap. 021906 | DOI | MR

[12] Critchley F., Heiser W., “Hierarchical trees can be perfectly scaled in one dimension”, J. Classif., 5 (1988), 5–20 | DOI | MR | Zbl

[13] Davey B. A., Priestley H. A., Introduction to lattices and order, 2nd ed., Cambridge Univ. Press, Cambridge, 2002 | MR | Zbl

[14] Delon F., “Espaces ultramétriques”, J. Symb. Log., 49 (1984), 405–424 | DOI | MR | Zbl

[15] Deutsch S. B., Martin J. J., “An ordering algorithm for analysis of data arrays”, Oper. Res., 19 (1971), 1350–1362 | DOI | Zbl

[16] Donoho D. L., Tanner J., “Neighborliness of randomly-projected simplices in high dimensions”, Proc. Nat. Acad. Sci. USA, 102 (2005), 9452–9457 | DOI | MR | Zbl

[17] Dragovich B., Dragovich A., “$p$-Adic modelling of the genome and the genetic code”, Comput. J., 2007; http://comjnl.oxfordjournals.org/cgi/content/abstract/bxm083v1

[18] Fisher R. A., “The use of multiple measurements in taxonomic problems”, Ann. Eugen., 7 (1936), 179–188 | DOI

[19] Foote R., “An algebraic approach to multiresolution analysis”, Trans. Amer. Math. Soc., 357 (2005), 5031–5050 | DOI | MR | Zbl

[20] Foote R., “Mathematics and complex systems”, Science, 318 (2007), 410–412 | DOI | MR | Zbl

[21] Foote R., Mirchandani G., Rockmore D. N., Healy D., Olson T., “A wreath product group approach to signal and image processing. I: Multiresolution analysis”, IEEE Trans. Signal Process., 48 (2000), 102–132 | DOI | MR | Zbl

[22] Foote R., Mirchandani G., Rockmore D. N., Healy D., Olson T., “A wreath product group approach to signal and image processing. II: Convolution, correlation, and applications”, IEEE Trans. Signal Process., 48 (2000), 749–767 | DOI | MR | Zbl

[23] Freund P. G. O., “$p$-Adic strings and their applications”, $p$-Adic mathematical physics, Proc. 2nd Intern. Conf. (Belgrade, 2005), AIP Conf. Proc., 826, eds. A. Yu. Khrennikov, Z. Rakić, I. V. Volovich, Amer. Inst. Phys., Melville, NY, 2006, 65–73 | DOI | MR | Zbl

[24] Gajić L., “On ultrametric space”, Novi Sad J. Math., 31 (2001), 69–71 | MR | Zbl

[25] Formal concept analysis: Mathematical foundations, Springer, Berlin, 1999 | MR | MR | Zbl | Zbl

[26] Gouvêa F. Q., $p$-Adic numbers: An introduction, Springer, Berlin, 2003 | MR | Zbl

[27] Hall P., Marron J. S., Neeman A., “Geometric representation of high dimension, low sample size data”, J. Roy. Stat. Soc. B, 67 (2005), 427–444 | DOI | MR | Zbl

[28] Hitzler P., Seda A. K., “The fixed-point theorems of Priess-Crampe and Ribenboim in logic programming”, Fields Inst. Commun., 32 (2002), 219–235 | MR | Zbl

[29] Jain A. K., Dubes R. C., Algorithms for clustering data, Prentice-Hall, Englewood Cliffs, NJ, 1988 | MR | Zbl

[30] Jain A. K., Murty M. N., Flynn P. J., “Data clustering: a review”, ACM Comput. Surv., 31 (1999), 264–323 | DOI

[31] Janowitz M. F., “An order theoretic model for cluster analysis”, SIAM J. Appl. Math., 34 (1978), 55–72 | DOI | MR | Zbl

[32] Janowitz M. F., Cluster analysis based on abstract posets, Tech. rep. , 2005–2006 http://dimax.rutgers.edu/~melj/poset_paper.pdf

[33] Jansen M., Nason G. P., Silverman B. W., “Multiscale methods for data on graphs and irregular multidimens ional situations”, J. Roy. Stat. Soc. B, 71 (2009), 97–125 | DOI | Zbl

[34] Johnson S. C., “Hierarchical clustering schemes”, Psychometrika, 32 (1967), 241–254 | DOI

[35] Keller K., Lauffer H., “Symbolic analysis of high-dimensional time series”, Intern. J. Bifurcation and Chaos Appl. Sci. and Eng., 13 (2003), 2657–2668 | DOI | MR | Zbl

[36] Keller K., Lauffer H., Sinn M., “Ordinal analysis of EEG time series”, Chaos and Complexity Lett., 2 (2007), 247–258

[37] Keller K., Sinn M., “Ordinal analysis of time series”, Physica A, 356 (2005), 114–120 | DOI

[38] Keller K., Sinn M., Ordinal symbolic dynamics, Tech. rep. A-05-14, Inst. Math. Univ. Lübeck, 2005; http://www.math.uni-luebeck.de/mitarbeiter/keller/wwwpapers/osdc.pdf

[39] Khrennikov A., Information dynamics in cognitive, psychological, social and anomalous phenomena, Kluwer, Dordrecht, 2004 | MR | Zbl

[40] Khrennikov A. Yu., Gene expression from polynomial dynamics in the 2-adic information space, E-print , 2006 arXiv: q-bio/0611068v2 | MR

[41] Klein F., Vergleichende Betrachtungen über neuere geometrische Forschungen, 1872; “A comparative review of recent researches in geometry”, Bull. New York Math. Soc., 2 (1892–1893), 215–249 | DOI

[42] Kozyrev S. V., “Teoriya vspleskov kak $p$-adicheskii spektralnyi analiz”, Izv. RAN. Ser. mat., 66:2 (2002), 149–158 | DOI | MR | Zbl

[43] Kozyrev S. V., “Vspleski i spektralnyi analiz ultrametricheskikh psevdodifferentsialnykh operatorov”, Mat. sb., 198:1 (2007), 103–126 | DOI | MR | Zbl

[44] Krasner M., “Nombres semi-réels et espaces ultramétriques”, C. r. Acad. sci. Paris, 219 (1944), 433–435 | MR | Zbl

[45] Latora V., Baranger M., “Kolmogorov–Sinai entropy rate versus physical entropy”, Phys. Rev. Lett., 82 (1999), 520–523 | DOI

[46] Lerman I. C., Classification et analyse ordinale des données, Dunod, Paris, 1981 | MR | Zbl

[47] Levy A., Basic set theory, Dover Publ., Mineola, NY, 2002 | MR | Zbl

[48] Madeira S. C., Oliveira A. L., “Biclustering algorithms for biological data analysis: a survey”, IEEE/ACM Trans. Comput. Biol. and Bioinform., 1 (2004), 24–45 | DOI

[49] March S. T., “Techniques for structuring database records”, Comput. Surv., 15 (1983), 45–79 | DOI | Zbl

[50] McCormick W. T. (Jr.), Schweitzer P. J., White T. J., “Problem decomposition and data reorganization by a clustering technique”, Oper. Res., 20 (1972), 993–1009 | DOI | Zbl

[51] Van Mechelen I., Bock H.-H., De Boeck P., “Two-mode clustering methods: a structured overview”, Stat. Methods Med. Res., 13 (2004), 363–394 | DOI | MR | Zbl

[52] Mirkin B., Mathematical classification and clustering, Kluwer, Dordrecht, 1996 | MR | Zbl

[53] Mirkin B., Clustering for data mining, Chapman and Hall/CRC Press, Boca Raton, FL, 2005 | MR | Zbl

[54] Murtagh F., “A survey of recent advances in hierarchical clustering algorithms”, Comput. J., 26 (1983), 354–359 | DOI | Zbl

[55] Murtagh F., “Complexities of hierarchic clustering algorithms: state of the art”, Comput. Stat. Quart., 1 (1984), 101–113 | Zbl

[56] Murtagh F., “Counting dendrograms: a survey”, Discr. Appl. Math., 7 (1984), 191–199 | DOI | MR | Zbl

[57] Murtagh F., Multidimensional clustering algorithms, Physica-Verlag, Heidelberg–Vienna, 1985 | MR | Zbl

[58] Murtagh F., “Comments on ‘Parallel algorithms for hierarchical clustering and cluster validity’ ”, IEEE Trans. Pattern Anal. and Mach. Intell., 14 (1992), 1056–1057 | DOI

[59] Murtagh F., “On ultrametricity, data coding, and computation”, J. Classif., 21 (2004), 167–184 | DOI | MR | Zbl

[60] Murtagh F., “Identifying the ultrametricity of time series”, Eur. Phys. J. B, 43 (2005), 573–579 | DOI

[61] Murtagh F., “The Haar wavelet transform of a dendrogram”, J. Classif., 24 (2007), 3–32 | DOI | MR | Zbl

[62] Murtagh F., “The remarkable simplicity of very high dimensional data: application of model-based clustering”, J. Classif., 2009 (to appear) | Zbl

[63] Murtagh F., “The correspondence analysis platform for uncovering deep structure in data and information”, Comput. J., 2008; http://comjnl.oxfordjournals.org/cgi/content/abstract/bxn045

[64] Murtagh F., Downs G., Contreras P., “Hierarchical clustering of massive, high dimensional data sets by exploiting ultrametric embedding”, SIAM J. Sci. Comput., 30 (2008), 707–730 | DOI | MR | Zbl

[65] Murtagh F., Starck J.-L., Berry M. W., “Overcoming the curse of dimensionality in clustering by means of the wavelet transform”, Comput. J., 43 (2000), 107–120 | DOI

[66] Ostrowski A., “Über einige Lösungen der Funktionalgleichung $\phi(x)\cdot\phi(y)-\phi(xy)$”, Acta math., 41 (1917), 271–284 | DOI | MR | Zbl

[67] Rammal R., Angles d'Auriac J. C., Doucot B., “On the degree of ultrametricity”, J. Phys. Lett., 46 (1985), 945–952 | DOI | MR

[68] Rammal R., Toulouse G., Virasoro M. A., “Ultrametricity for physicists”, Rev. Mod. Phys., 58 (1986), 765–788 | DOI | MR

[69] Reiter H., Stegeman J. D., Classical harmonic analysis and locally compact groups, 2nd ed., Oxford Univ. Press, Oxford, 2000 | MR | Zbl

[70] Van Rooij A. C. M., Non-Archimedean functional analysis, M. Dekker, New York, 1978 | MR | Zbl

[71] Schikhof W. H., Ultrametric calculus, Cambridge Univ. Press, Cambridge, 1984, Chs. 18–21 | MR | Zbl

[72] Seda A. K., Hitzler P., “Generalized distance functions in the theory of computation”, Comput. J., 2008; http://comjnl.oxfordjournals.org/cgi/content/abstract/bxm108

[73] Sibson R., “SLINK: An optimally efficient algorithm for the single-link cluster method”, Comput. J., 16 (1973), 30–34 | DOI | MR

[74] Simon H. A., The sciences of the artificial, MIT Press, Cambridge, MA, 1996

[75] Sloane N. J. A., Sequence A000111, On-line encyclopedia of integer sequences http://www.research.att.com/~njas/sequences/A000111

[76] Steinley D., “K-means clustering: A half-century synthesis”, Br. J. Math. and Stat. Psychol., 59 (2006), 1–3 | DOI | MR

[77] Steinley D., Brusco M. J., “Initializing K-means batch clustering: A critical evaluation of several techniques”, J. Classif., 24 (2007), 99–121 | DOI | MR | Zbl

[78] Tung Wu-Ki, Group theory in physics, World Sci., Singapore, 1985 | MR | Zbl

[79] Vempala S. S., The random projection method, DIMACS Ser. Discr. Math. and Theor. Comput. Sci., 65, Amer. Math. Soc., Providence, RI, 2004 | MR | Zbl

[80] Volovich I. V., Number theory as the ultimate physical theory, Preprint No TH 4781/87, CERN, Geneva, 1987

[81] Volovich I. V., “$p$-Adic string”, Class. and Quantum Grav., 4 (1987), L83–L87 | DOI | MR

[82] Weckesser W., Symbolic dynamics in mathematics, physics, and engineering, Tech. rep. , 1997 http://www.ima.umn.edu/~weck/nbt/nbt.ps

[83] Weyl H., Symmetry, Princeton Univ. Press, Princeton, 1983 | MR

[84] Xu Rui, Wunsch D., II, “Survey of clustering algorithms”, IEEE Trans. Neural Netw., 16 (2005), 645–678 | DOI