Paper Info
Title
A Unified Framework for Sampling, Clustering and Embedding Data Points in Semi-Metric Spaces.
Abstract
In this paper, we propose a unified framework for sampling, clustering and embedding data points in semi-metric spaces. For a set of data points $Omega={x_1, x_2, ldots, x_n}$ in a semi-metric space, we consider a complete graph with $n$ nodes and $n$ self edges and then map each data point in $Omega$ to a node in the graph with the edge weight between two nodes being the distance between the corresponding two points in $Omega$. By doing so, several well-known sampling techniques can be applied for clustering data points in a semi-metric space. One particularly interesting sampling technique is the exponentially twisted sampling in which one can specify the desired average distance from the sampling distribution to detect clusters with various resolutions. also propose a softmax clustering algorithm that can perform a clustering and embed data points in a semi-metric space to a low dimensional Euclidean space. Our experimental results show that after a certain number of iterations of training, our softmax algorithm can reveal the topology of the data from a high dimensional Euclidean. We also show that the eigendecomposition of a covariance matrix is equivalent to the principal component analysis (PCA). To deal with the hierarchical structure of clusters, our softmax clustering algorithm can also be used with a hierarchical clustering algorithm. For this, we propose a partitional-hierarchical algorithm, called $i$PHD, in this paper. Our experimental results show that those algorithms based on the maximization of normalized modularity tend to balance the sizes of detected clusters and thus do not perform well when the ground-truth clusters are different in sizes. Also, using a metric is better than using a semi-metric as the triangular inequality is not satisfied for a semi-metric and that is more prone to clustering errors.
Year
Venue
Field
2017
arXiv: Social and Information Networks
k-medians clustering,Discrete mathematics,CURE data clustering algorithm,Data stream clustering,Correlation clustering,Affinity propagation,Computer science,Determining the number of clusters in a data set,Cluster analysis,Single-linkage clustering
DocType
Volume
Citations 
Journal
abs/1708.00316
0
PageRank 
References 
Authors
0.34
7
2
Name
Order
Citations
PageRank
Chia-Tai Chang100.68
Cheng-Shang Chang22392246.97