arXiv research

Noncommutative geometry is used to study the local geometry of ultrametric spaces and the geometry of trees at infinity. Connes's example of the noncommutative space of Penrose tilings is interpreted as a non-Hausdorff orbit space of a compact, ultrametric space under the action of its local isometry group. This is gen…

It is well-known that quasi-isometries between R-trees induce power quasi-symmetric homeomorphisms between their ultrametric end spaces. This paper investigates power quasi-symmetric homeomorphisms between bounded, complete, uniformly perfect, ultrametric spaces (i.e., those ultrametric spaces arising up to similarity …

Develops a variational method for ultrametric phylogenetic trees.

It is known that PQ-symmetric maps on the boundary characterize the quasi-isometry type of visual hyperbolic spaces, in particular, of geodesically complete \br-trees. We define a map on pairs of PQ-symmetric ultrametric spaces which characterizes the branching of the space. We also show that, when the ultrametric spac…

We announce ultrametric analogues of the results of Kleinbock-Margulis for shrinking target properties of semisimple group actions on symmetric spaces. The main applications are S-arithmetic Diophantine approximation results and logarithm laws for buildings, generalizing the work of Hersonsky-Paulin on trees.

This paper uses two hierarchical techniques, a minimal spanning tree and an ultrametric hierarchical tree, to extract a topological influence map for major currencies from the ultrametric distance matrix for 1996-2001. We find that these two techniques generate a defined and robust scale free network with meaningful ta…

There is a well-known correspondence between infinite trees and ultrametric spaces which can be interpreted as an equivalence of categories and comes from considering the end space of the tree. In this equivalence, uniformly continuous maps between the end spaces are translated to some classes of coarse maps (or even c…

Failing to distinguish between a sheepdog and a skyscraper should be worse and penalized more than failing to distinguish between a sheepdog and a poodle; after all, sheepdogs and poodles are both breeds of dogs. However, existing metrics of failure (so-called "loss" or "win") used in textual or visual classification/r…

Consider observation data, comprised of n observation vectors with values on a set of attributes. This gives us n points in attribute space. Having data structured as a tree, implied by having our observations embedded in an ultrametric topology, offers great advantage for proximity searching. If we have preprocessed d…

We prove that if X is a complete geodesic metric space with uniformly generated first homology group and $f: X\to R$ is metrically proper on the connected components and bornologous, then X is quasi-isometric to a tree. Using this and adapting the definition of hyperbolic approximation we obtain an intrinsic sufficent …

Following a review of metric, ultrametric and generalized ultrametric, we review their application in data analysis. We show how they allow us to explore both geometry and topology of information, starting with measured data. Some themes are then developed based on the use of metric, ultrametric and generalized ultrame…

Finite approximations help reconstruct countable metric and ultrametric spaces.

An analogue of the Riemannian Geometry for an ultrametric Cantor set (C, d) is described using the tools of Noncommutative Geometry. Associated with (C, d) is a weighted rooted tree, its Michon tree. This tree allows to define a family of spectral triples giving the Cantor set the structure of a noncommutative Riemanni…

Method preserves order in hierarchical clustering of ordered data.

Using data from a sample of 28 representatives countries, we propose a classification of currency crises consequences based on the ultrametric analysis of the real exchange rate movements time series, without any further assumption. By using the matrix of synchronous linear correlation coefficients and the appropriate …

The increasing needs of clustering massive datasets and the high cost of running clustering algorithms poses difficult problems for users. In this context it is important to determine if a data set is clusterable, that is, it may be partitioned efficiently into well-differentiated groups containing similar objects. We …

We model anomaly and change in data by embedding the data in an ultrametric space. Taking our initial data as cross-tabulation counts (or other input data formats), Correspondence Analysis allows us to endow the information space with a Euclidean metric. We then model anomaly or change by an induced ultrametric. The in…

We study the problem of fitting an ultrametric distance to a dissimilarity graph in the context of hierarchical cluster analysis. Standard hierarchical clustering methods are specified procedurally, rather than in terms of the cost function to be optimized. We aim to overcome this limitation by presenting a general opt…

Dendrograms used in data analysis are ultrametric spaces, hence objects of nonarchimedean geometry. It is known that there exist $p$-adic representation of dendrograms. Completed by a point at infinity, they can be viewed as subtrees of the Bruhat-Tits tree associated to the $p$-adic projective line. The implications a…

New model addresses instability in hierarchical clustering of social networks.

We study the classification of ultrametric spaces based on their small scale geometry (uniform homeomorphism), large scale geometry (coarse equivalence) and both (all scale uniform equivalences). We prove that these equivalences can be characterized with parallel constructions using a combinatoric tool called common zi…

Decomposes ultrametric spaces into scaled simplices.

I find a topological arrangement of stocks traded in a financial market which has associated a meaningful economic taxonomy. The topological space is a graph connecting the stocks of the portfolio analyzed. The graph is obtained starting from the matrix of correlation coefficient computed between all pairs of stocks of…

This note explores norms beyond ultrametric inequalities in non-Archimedean analysis.

Paper addresses limitations of traditional hierarchical clustering methods.

This paper connects ultrametric overlap gap properties to parametric RDT for symmetric binary perceptrons.

Data analysis and data mining are concerned with unsupervised pattern finding and structure determination in data sets. "Structure" can be understood as symmetry and a range of symmetries are expressed by hierarchy. Such symmetries directly point to invariants, that pinpoint intrinsic properties of the data and of the …

Hughes has defined a class of groups, which we call FSS (finite similarity structure) groups. Each FSS group acts on a compact ultrametric space by local similarities. The best-known example is Thompson's group V. Guided by previous work on Thompson's group V, we establish a number of new results about FSS groups. Our …

We consider the notion of dimension in four categories: the category of (unbounded) separable metric spaces and (metrically proper) Lipschitz maps, and the category of (unbounded) separable metric spaces and (metrically proper) uniform maps. A unified treatment is given to the large scale dimension and the small scale …

The Baire metric induces an ultrametric on a dataset and is of linear computational complexity, contrasted with the standard quadratic time agglomerative hierarchical clustering algorithm. In this work we evaluate empirically this new approach to hierarchical clustering. We compare hierarchical clustering based on the …

New method uses cohomology to quantify molecular similarity.

The Baire metric induces an ultrametric on a dataset and is of linear computational complexity, contrasted with the standard quadratic time agglomerative hierarchical clustering algorithm. We apply the Baire distance to spectrometric and photometric redshifts from the Sloan Digital Sky Survey using, in this work, about…

We present an axiomatic approach to finite- and infinite-dimensional differential calculus over arbitrary infinite fields (and, more generally, suitable rings). The corresponding basic theory of manifolds and Lie groups is developed. Special attention is paid to the case of mappings between topological vector spaces ov…

A new algorithm of the analysis of correlation among economy time series is proposed. The algorithm is based on the power law classification scheme (PLCS) followed by the analysis of the network on the percolation threshold (NPT). The algorithm was applied to the analysis of correlations among GDP per capita time serie…

The high-frequency cross-correlation existing between pairs of stocks traded in a financial market are investigated in a set of 100 stocks traded in US equity markets. A hierarchical organization of the investigated stocks is obtained by determining a metric distance between stocks and by investigating the properties o…

This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect…

We first pursue the study of how hierarchy provides a well-adapted tool for the analysis of change. Then, using a time sequence-constrained hierarchical clustering, we develop the practical aspects of a new approach to wavelet regression. This provides a new way to link hierarchical relationships in a multivariate time…

We describe many vantage points on the Baire metric and its use in clustering data, or its use in preprocessing and structuring data in order to support search and retrieval operations. In some cases, we proceed directly to clusters and do not directly determine the distances. We show how a hierarchical clustering can …

We present the characterization of metric spaces that are micro-, macro- or bi-uniformly equivalent to the extended Cantor set $\{\sum_{i=-n}^\infty\frac{2x_i}{3^i}:n\in\IN ,\;(x_i)_{i\in\IZ}\in\{0,1\}^\IZ\}\subset\IR$, which is bi-uniformly equivalent to the Cantor bi-cube $2^{<\IZ}=\{(x_i)_{i\in\IZ}\in \{0,1\}^\IZ:\e…

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 tak…

We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensi…

Boosting meta-trees improve decision tree performance.

The paper studies geometric properties of quasi-trees and tree approximations.

Efficiently updates posterior tree distributions over meta-trees.

This paper describes experiments, on two domains, to investigate the effect of averaging over predictions of multiple decision trees, instead of using a single tree. Other authors have pointed out theoretical and commonsense reasons for preferring the multiple tree approach. Ideally, we would like to consider predictio…

We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree---"Extremely Fast Decision Tree", a minor modification to the MOA implementat…

We introduce block-tree graphs as a framework for deriving efficient algorithms on graphical models. We define block-tree graphs as a tree-structured graph where each node is a cluster of nodes such that the clusters in the graph are disjoint. This differs from junction-trees, where two clusters connected by an edge al…

This paper introduces TNTK to study infinite soft tree ensembles.