Adaptive Explicit Kernel Minkowski Weighted K-means

• URL: http://arxiv.org/abs/2012.02805v1
• Date: Fri, 4 Dec 2020 19:14:09 GMT
• Title: Adaptive Explicit Kernel Minkowski Weighted K-means
• Authors: Amir Aradnia, Maryam Amir Haeri and Mohammad Mehdi Ebadzadeh
• Abstract summary: The kernel K-means, which extends K-means into the kernel space, is able to capture nonlinear structures and identify arbitrarily shaped clusters. This paper proposes a method to combine the advantages of the linear and nonlinear approaches by using driven corresponding approximate finite-dimensional feature maps.
• Score: 1.3535770763481905
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The K-means algorithm is among the most commonly used data clustering methods. However, the regular K-means can only be applied in the input space and it is applicable when clusters are linearly separable. The kernel K-means, which extends K-means into the kernel space, is able to capture nonlinear structures and identify arbitrarily shaped clusters. However, kernel methods often operate on the kernel matrix of the data, which scale poorly with the size of the matrix or suffer from the high clustering cost due to the repetitive calculations of kernel values. Another issue is that algorithms access the data only through evaluations of $K(x_i, x_j)$, which limits many processes that can be done on data through the clustering task. This paper proposes a method to combine the advantages of the linear and nonlinear approaches by using driven corresponding approximate finite-dimensional feature maps based on spectral analysis. Applying approximate finite-dimensional feature maps were only discussed in the Support Vector Machines (SVM) problems before. We suggest using this method in kernel K-means era as alleviates storing huge kernel matrix in memory, further calculating cluster centers more efficiently and access the data explicitly in feature space. These explicit feature maps enable us to access the data in the feature space explicitly and take advantage of K-means extensions in that space. We demonstrate our Explicit Kernel Minkowski Weighted K-mean (Explicit KMWK-mean) method is able to be more adopted and find best-fitting values in new space by applying additional Minkowski exponent and feature weights parameter. Moreover, it can reduce the impact of concentration on nearest neighbour search by suggesting investigate among other norms instead of Euclidean norm, includes Minkowski norms and fractional norms (as an extension of the Minkowski norms with p<1).

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Robust Kernel Sparse Subspace Clustering [0.0]
  We propose for the first time robust kernel sparse SC (RKSSC) algorithm for data with gross sparse corruption. The concept, in principle, can be applied to other SC algorithms to achieve robustness to the presence of such type of corruption.
  arXiv  Detail & Related papers  (2024-01-30T14:12:39Z)
• Linear time Evidence Accumulation Clustering with KMeans [0.0]
  This work describes a trick which mimic the behavior of average linkage clustering. We found a way of computing efficiently the density of a partitioning, reducing the cost from a quadratic to linear complexity. The k-means results are comparable to the best state of the art in terms of NMI while keeping the computational cost low.
  arXiv  Detail & Related papers  (2023-11-15T14:12:59Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• K-Splits: Improved K-Means Clustering Algorithm to Automatically Detect the Number of Clusters [0.12313056815753944]
  This paper introduces k-splits, an improved hierarchical algorithm based on k-means to cluster data without prior knowledge of the number of clusters. Accuracy and speed are two main advantages of the proposed method.
  arXiv  Detail & Related papers  (2021-10-09T23:02:57Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  We propose a simple yet effective multiple kernel clustering algorithm, termed simple multiple kernel k-means (SimpleMKKM) Our criterion is given by an intractable minimization-maximization problem in the kernel coefficient and clustering partition matrix. We theoretically analyze the performance of SimpleMKKM in terms of its clustering generalization error.
  arXiv  Detail & Related papers  (2020-05-11T10:06:40Z)
• Ball k-means [53.89505717006118]
  The Ball k-means algorithm uses a ball to describe a cluster, focusing on reducing the point-centroid distance computation. The fast speed, no extra parameters and simple design of the Ball k-means make it an all-around replacement of the naive k-means algorithm.
  arXiv  Detail & Related papers  (2020-05-02T10:39:26Z)
• Fast Kernel k-means Clustering Using Incomplete Cholesky Factorization [11.631064399465089]
  Kernel-based clustering algorithm can identify and capture the non-linear structure in datasets. It can achieve better performance than linear clustering. computing and storing the entire kernel matrix occupy so large memory that it is difficult for kernel-based clustering to deal with large-scale datasets.
  arXiv  Detail & Related papers  (2020-02-07T15:32:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.