Many clustering algorithms exist that estimate a cluster centroid, such as K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters data by returning exactly K meaningful modes. We propose a natural definition of a K-modes objective function by combining the notions of density and cluster assignm…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
33 results for “K-medoids”
EKM solves the K-medoids problem in polynomial time.
problem The -medoids problem in data analysis.
method EKM is a novel algorithm using transformational programming and combinatorial generation.
result EKM solves the -medoids problem in worst-case $O\left(N^{K+1}
ight)$ time complexity.
BanditPAM clusters data faster than traditional methods.
problem Efficiently clustering large datasets with arbitrary distance metrics.
method Inspired by multi-armed bandits, reduces PAM complexity from to .
result Matches state-of-the-art clustering loss with up to 4x faster results and 200x fewer distance computations.
K-Medoids(KM) is a standard clustering method, used extensively on semi-metric data.Error analyses of KM have traditionally used an in-sample notion of error,which can be far from the true error and suffer from generalization gap. We formalize the true K-Medoid error based on the underlying data distribution.We decompo…
This paper studies clustering of data sequences using the k-medoids algorithm. All the data sequences are assumed to be generated from \emph{unknown} continuous distributions, which form clusters with each cluster containing a composite set of closely located distributions (based on a certain distance metric between di…
In this paper, we firstly give a brief introduction of expectation maximization (EM) algorithm, and then discuss the initial value sensitivity of expectation maximization algorithm. Subsequently, we give a short proof of EM's convergence. Then, we implement experiments with the expectation maximization algorithm (We im…
Determinantal consensus clustering improves clustering robustness.
problem Robustness of clustering algorithms.
method Use of determinantal point processes (DPP) for random restart of clustering algorithms.
result Determinantal consensus clustering outperforms classical algorithms.
Improved k-medoids clustering with faster algorithms for big data.
problem High runtime cost of k-medoids clustering algorithms.
method Modifications to PAM, CLARA, and CLARANS algorithms to achieve O(k) runtime improvement.
result 458x and 1191x speedup in runtime for k=100,200 respectively.
Paper proposes SLINK clustering for nonparametric data sequences with improved consistency.
problem Nonparametric clustering of data sequences from unknown distributions.
method Exponentially consistent nonparametric SLINK clustering algorithm.
result SLINK clustering achieves exponential consistency under less strict conditions.
This paper introduces a noise-robust clustering method using distribution distances.
problem Reducing noise impact on clustering results.
method Introduces expectation distance (ED) for distribution clustering, extending K-means and K-medoids.
result Improved clustering accuracy and reduced computation time.
Support Vector Machines have been a popular topic for quite some time now, and as they develop, a need for new methods of feature selection arises. This work presents various approaches SVM feature selection developped using new tools such as entropy measurement and K-medoid clustering. The work focuses on the use of o…
The paper proposes a new method to evaluate LLM agent responses using ECDF clustering.
problem The standard evaluation of LLM agent responses via majority voting obscures response quality and distribution.
method The paper introduces a novel evaluation framework based on ECDF of cosine similarities and clustering of ECDFs using distances and -medoids algorithm.
result ECDF clustering reveals interpretable group structures in LLM responses, offering insights into agent settings.
For a certain class of distributions, we prove that the linear programming relaxation of -medoids clustering---a variant of -means clustering where means are replaced by exemplars from within the dataset---distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn a…
Paper uses autoencoders for time series clustering with energy data.
problem Challenges in time series clustering, especially with outliers.
method Combines convolutional autoencoder and k-medoids for clustering.
result Improves clustering robustness to outliers and finer clusters.
Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does no…
We present a new algorithm, trimed, for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under certain assumptions, expected run time O(N^(3/2)) in R^d where N is the set size, making it the first sub-quadratic exact m…
New theory for clustering in geometric and adaptive settings.
problem Clustering in non-Euclidean spaces and adaptive parameters.
method Asymptotic theory for -means and related methods.
result Strong consistency and asymptotic limit theorems for various clustering procedures.
We develop a Vector Quantized Spectral Clustering (VQSC) algorithm that is a combination of Spectral Clustering (SC) and Vector Quantization (VQ) sampling for grouping Soybean genomes. The inspiration here is to use SC for its accuracy and VQ to make the algorithm computationally cheap (the complexity of SC is cubic in…
Graph Neural Networks (GNNs) for prediction tasks like node classification or edge prediction have received increasing attention in recent machine learning from graphically structured data. However, a large quantity of labeled graphs is difficult to obtain, which significantly limits the true success of GNNs. Although …
Having the right assortment of shipping boxes in the fulfillment warehouse to pack and ship customer's online orders is an indispensable and integral part of nowadays eCommerce business, as it will not only help maintain a profitable business but also create great experiences for customers. However, it is an extremely …
Generative adversarial networks (GANs) are the state of the art in generative modeling. Unfortunately, most GAN methods are susceptible to mode collapse, meaning that they tend to capture only a subset of the modes of the true distribution. A possible way of dealing with this problem is to use an ensemble of GANs, wher…
We quantify the amount of information filtered by different hierarchical clustering methods on correlations between stock returns comparing it with the underlying industrial activity structure. Specifically, we apply, for the first time to financial data, a novel hierarchical clustering approach, the Directed Bubble Hi…
Diffusion maps are a nonlinear manifold learning technique based on harmonic analysis of a diffusion process over the data. Out-of-sample extensions with computational complexity , where is the number of points comprising the manifold, frustrate applications to online learning applications requiring…
Quantum machine learning improves satellite image alignment.
problem Align satellite images taken at different times and angles.
method Quantum machine learning techniques for feature extraction and matching.
result Quantum methods show potential for future improvements.
Graph clustering improved using Boltzmann machine heuristics.
problem Graph clustering to form densely connected clusters.
method Two mathematical programming formulations, two variations of Boltzmann machine heuristic.
result Boltzmann machine provides superior solutions and faster computation times.
Cakewalk Samplingstat.ML
We study the task of finding good local optima in combinatorial optimization problems. Although combinatorial optimization is NP-hard in general, locally optimal solutions are frequently used in practice. Local search methods however typically converge to a limited set of optima that depend on their initialization. Sam…
Neural clustering learns time series affinity from statistical features.
problem Challenging time series clustering with unknown cluster shapes and structures.
method Amortized neural inference using statistical features.
result Competitive clustering accuracy without manual specification of cluster shapes.
In this paper, we develop four malware detection methods using Hamming distance to find similarity between samples which are first nearest neighbors (FNN), all nearest neighbors (ANN), weighted all nearest neighbors (WANN), and k-medoid based nearest neighbors (KMNN). In our proposed methods, we can trigger the alarm i…
Starting from a dataset with input/output time series generated by multiple deterministic linear dynamical systems, this paper tackles the problem of automatically clustering these time series. We propose an extension to the so-called Martin cepstral distance, that allows to efficiently cluster these time series, and a…
ProtoBandit uses bandits to find prototypes efficiently.
problem Finding a compact set of prototypes from a large dataset.
method Stochastic greedy search and multi-armed bandits.
result ProtoBandit reduces similarity comparisons to , independent of target set size.
We introduce an evolutionary algorithm called recombinator--means for optimizing the highly non-convex kmeans problem. Its defining feature is that its crossover step involves all the members of the current generation, stochastically recombining them with a repurposed variant of the -means++ seeding algorithm. Th…
In this paper, we propose a technique for time series clustering using community detection in complex networks. Firstly, we present a method to transform a set of time series into a network using different distance functions, where each time series is represented by a vertex and the most similar ones are connected. The…
A new method reduces high-dimensional parameter spaces for faster numerical tasks.
problem Efficiently reducing high-dimensional parameter spaces for numerical tasks.
method Local Active Subspaces (LAS) combining active subspaces with clustering techniques.
result Significant speed-up in numerical tasks through efficient dimension reduction.