An official website of the United States government
Clustering continues to be an important tool for data engineering and analysis. While advances in deep learning tend to be at the forefront of machine learning, it is only useful for the supervised classification of data sets. Clustering is an essential tool for problems where labeling data sets is either too labor intensive or where there is no agreed upon ground truth. The well studied k-means problem partitions groups of similar vectors into k clusters by iteratively updating the cluster assignment such that it minimizes the within cluster sum of squares metric. Unfortunately k-means can become prohibitive for very large high dimensional data sets as iterative methods often rely on random access to, or multiple passes over, the data set — a requirement that is not often possible for large and potentially unbounded data sets. In this work we explore an randomized, approximate method for clustering called Tree-Walk Random Projection Clustering (TWRP) that is a fast, memory efficient method for finding cluster embedding in high dimensional spaces. TWRP combines random projection with a tree based partitioner to achieve a clustering method that forgoes storing the exhaustive representation of all vectors in the data space and instead performs a bounded search over the implied cluster bifurcation tree represented as approximate vector and count values. The TWRP algorithm is described and experimentally evaluated for scalability and accuracy in the presence of noise against several other well-known algorithms.
more »
« less
Clustering characteristic diffraction vectors in 4-D STEM data sets from overlapping structures in nanocrystalline and amorphous materials
We describe a method for identifying and clustering diffraction vectors in four-dimensional (4-D) scanning transmission electron microscopy data to determine characteristic diffraction patterns from overlapping structures in projection. First, the data is convolved with a 4-D kernel, then diffraction vectors are identified and clustered using both density-based clustering and a metric that emphasizes rotational symmetries. The method works well for both crystalline and amorphous samples and in high- and low-dose experiments. A simulated dataset of overlapping aluminum nanocrystals provides performance metrics as a function of Poisson noise and the number of overlapping structures. Experimental data from an aluminum nanocrystal sample shows similar performance. For an amorphous Pd77.5Cu6Si16.5 thin film, experiments measuring glassy structure show strong evidence of 4- and 6-fold symmetry structures. A significant background arises from the diffraction of overlapping structures. Quantifying this background helps to separate contributions from single, rotationally symmetric structures vs. apparent symmetries arising from overlapping structures in projection.
more »
« less
- Award ID(s):
- 2204632
- PAR ID:
- 10629754
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Ultramicroscopy
- Volume:
- 267
- Issue:
- C
- ISSN:
- 0304-3991
- Page Range / eLocation ID:
- 114040
- Subject(s) / Keyword(s):
- 4-D STEM Amorphous Structure Nanocrystal Characterization Glass Structure Symmetry Clustering Electron Diffraction
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The size and amount of data captured from numerous sources has created a situation where the large quantity of data challenges our ability to understand the meaning within the data. This has motivated studies for mechanized data analysis and in particular for the clustering, or partitioning, of data into related groups. In fact, the size of the data has grown to the point where it is now often necessary to stream the data through the system for online and high speed analysis. This paper explores the application of approximate methods for the stream clustering of high-dimensional data (feature sizes contains 100+ measures). In particular, the algorithm that has been developed, called streamingRPHash, combines Random Projection with Locality Sensitive Hashing and a count-min sketch to implement a high-performance method for the parallel and distributed clustering of streaming data in a MapReduce framework. streamingRPHash is able to perform clustering at a rate much faster than traditional clustering algorithms such as K-Means. streamingRPHash provides clustering results that are only slightly less accurate than K-Means, but in runtimes that are nearly half that required by K-Means. The performance advantage for streamingRPHash becomes even more significant as the dimensionality of the input data stream increases. Furthermore, the experimental results show that streamingRPHash has a near linear speedup relative to the number of CPU cores. This speedup efficiency is possible because the approximate methods used in streamingRPHash allow independent and largely unsynchronized analyses to be performed on each streamed data vectors.more » « less
-
Fluctuation Electron Microscopy (FEM) examines the scattering statistics from small volumes of thin amorphous materials in order to learn subtle details about any medium-range order (MRO) that may be present [1–4]. Both modeling and simulations show that FEM is extraordinarily sensitive to the presence of MRO, much more so than high-resolution diffraction and high-resolution imaging. The essence of FEM is to measure the 'speckliness' of diffraction (or image) data from small regions of the sample.more » « less
-
Summary The statistics of earthquake populations are governed by stress changes and event interactions at various scales which promote non-linear event cascades and seismicity clustering. Earthquake clustering in space and time is observed in both tectonic and volcanically dominated regions; however, notable differences exist for instance during eruptive sequences. Here, we characterize seismicity statistics in California and Hawaii and quantify differences in background rates and clustering. We compare three statistical approaches, i.e, i) Reasenberg declustering, ii) Gamma distribution fit, and iii) Nearest Neighbor Clustering which are applied to seismicity in Hawaii, southern California, and ETAS catalogs with known clustering characteristics. Tests with ETAS-catalogs suggest that background rate variations are more consistently resolvable using the Nearest Neighbor and Gamma distribution algorithm without requiring parameter adjustments to the specific study area. The Nearest Neighbor method tends to overestimate background rates, whereas the Gamma distribution algorithm shows systematic underestimation, suggesting that an ensemble model can improve the performance over any single method. Uncertainties in background rate estimates based on small magnitude events (e.g., M≥2.5) are high, in particular for the Reasenberg method, which overpredicts true rates by up to a factor of 4, and extrapolations to larger magnitudes need to be treated cautiously. Our analysis shows that the combination of the three approaches generates new insights into the processes that govern seismicity clustering. The analysis of southern California seismicity produces consistent results between the different methods, and the distribution of background seismicity rates is indistinguishable from Poissonian rates at magnitudes above 3.5. Conversely, the seismicity in Hawaii exhibits notable non-Poissonian background rate changes. Results from the Nearest Neighbor clustering analysis suggest notable differences between tectonic and volcano seismicity, including background rate changes and more pronounced spatiotemporal clustering around active volcanoes. Hawaiian seismicity is characterized by more localized spatial-temporal clustering, in particular during the 2018 eruption. This difference may be a result of magmatic, hydrothermal and eruptive processes, which make volcanic areas susceptible to stress perturbations and earthquake triggering at small scales.more » « less
-
Background subtraction is a general problem in spectroscopy often addressed with application-specific techniques, or methods that introduce a variety of implementation barriers such as having to specify peak-free regions of the spectrum. An iterative dual-tree complex wavelet transform-based background subtraction method (DTCWT-IA) was recently developed for the analysis of ultrafast electron diffraction patterns. The method was designed to require minimal user intervention, to support streamlined analysis of many diffraction patterns with complex overlapping peaks and time-varying backgrounds, and is implemented in an open-source computer program. We examined the performance of DTCWT-IA for the analysis of spectra acquired by a range of optical spectroscopies including ultraviolet–visible spectroscopy (UV–Vis), X-ray photoelectron spectroscopy (XPS), and surface-enhanced Raman spectroscopy (SERS). A key benefit of the method is that the user need not specify regions of the spectrum where no peaks are expected to occur. SER spectra were used to investigate the robustness of DTCWT-IA to signal-to-noise levels in the spectrum and to user operation, specifically to two of the algorithm parameter settings: decomposition level and iteration number. The single, general DTCWT-IA implementation performs well in comparison to the different conventional approaches to background subtraction for UV–Vis, XPS, and SERS, while requiring minimal input. The method thus holds the same potential for optical spectroscopy as for ultrafast electron diffraction, namely streamlined analysis of spectra with complex distributions of peaks and varying signal levels, thus supporting real-time spectral analysis or the analysis of data acquired from different sources.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1016/j.ultramic.2024.114040
