In this work we present a clustering technique called \textit{multi-level conformal clustering (MLCC)}. The technique is hierarchical in nature because it can be performed at multiple significance levels which yields greater insight into the data than performing it at just one level. We describe the theoretical underpinnings of MLCC, compare and contrast it with the hierarchical clustering algorithm, and then apply it to real world datasets to assess its performance. There are several advantages to using MLCC over more classical clustering techniques: Once a significance level has been set, MLCC is able to automatically select the number of clusters. Furthermore, thanks to the conformal prediction framework the resulting clustering model has a clear statistical meaning without any assumptions about the distribution of the data. This statistical robustness also allows us to perform clustering and anomaly detection simultaneously. Moreover, due to the flexibility of the conformal prediction framework, our algorithm can be used on top of many other machine learning algorithms.

Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs Eli Chien Pan Li Olgica Milenkovic Department ECE, UIUC Department ECE, UIUC Department ECE, UIUC Abstract We describe the first known mean-field study of landing probabilities for random walks on hypergraphs. In particular, we examine clique-expansion and tensor methods and evaluate their mean-field characteristics over a class of random hypergraph models for the purpose of seed-set community expansion. We describe parameter regimes in which the two methods outperform each other and propose a hybrid expansion method that uses partial clique-expansion to reduce the projection distortion and low-complexity tensor methods applied directly on the partially expanded hypergraphs. 1 1 Introduction Random walks on graphs are Markov random processes in which given a starting vertex, one moves to a randomly selected neighbor and then repeats the procedure starting from the newly selected vertex [1]. Random walks are used in many graph-based learning algorithms such as PageRank [2] and Label Propagating [3], and they have found a variety of applications in local community detection [4, 5], information retrieval [2] and semi-supervised learning [3]. Random walks are also frequently used to characterize the topological structure of graphs via the hitting time of a vertex from a seed, the commute time between two vertices [6] and the mixing time which also characterizes global graph connectivity [7]. Recently, a new measure of vertex connectivity and similarity, termed a landing probability (LP), was introduced in [8]. A1 Eli Chien and Pan Li contribute equally to this work.Preprint version. LP of a vertex is the probability of a random walk ending at the vertex after making a certain number of steps. Different linear combinations of LPs give rise to different forms of PageRanks (PRs), such as the standard PR [2] and the heat-kernel PR [9], both used for various graph clustering tasks. In particular, Kloumann et al. [8] also initiated the analysis of PRs based on LPs for seed-based community detection. Under the assumption of a generative stochastic block model (SBM) [10] with two blocks, the authors of [8] proved that the empirical average of LPs within the seed community concentrates around a deterministic centroid. Similarly, the empirical averages of LPs outside the seed community also concentrate around another deterministic centroid.

Clustering is a fundamental unsupervised learning approach. Many clustering algorithms -- such as $k$-means -- rely on the euclidean distance as a similarity measure, which is often not the most relevant metric for high dimensional data such as images. Learning a lower-dimensional embedding that can better reflect the geometry of the dataset is therefore instrumental for performance. We propose a new approach for this task where the embedding is performed by a differentiable model such as a deep neural network. By rewriting the $k$-means clustering algorithm as an optimal transport task, and adding an entropic regularization, we derive a fully differentiable loss function that can be minimized with respect to both the embedding parameters and the cluster parameters via stochastic gradient descent. We show that this new formulation generalizes a recently proposed state-of-the-art method based on soft-$k$-means by adding constraints on the cluster sizes. Empirical evaluations on image classification benchmarks suggest that compared to state-of-the-art methods, our optimal transport-based approach provide better unsupervised accuracy and does not require a pre-training phase.

Subspace clustering refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Current subspace clustering approaches are usually based on a two-stage framework. In the first stage, an affinity matrix is generated from data. In the second one, spectral clustering is applied on the affinity matrix. However, the affinity matrix produced by two-stage methods cannot fully reveal the similarity between data points from the same subspace (intra-subspace similarity), resulting in inaccurate clustering. Besides, most approaches fail to solve large-scale clustering problems due to poor efficiency. In this paper, we first propose a new scalable sparse method called Iterative Maximum Correlation (IMC) to learn the affinity matrix from data. Then we develop Piecewise Correlation Estimation (PCE) to densify the intra-subspace similarity produced by IMC. Finally we extend our work into a Sparse-Dense Subspace Clustering (SDSC) framework with a dense stage to optimize the affinity matrix for two-stage methods. We show that IMC is efficient when clustering large-scale data, and PCE ensures better performance for IMC. We show the universality of our SDSC framework as well. Experiments on several data sets demonstrate the effectiveness of our approaches. Moreover, we are the first one to apply densification on affinity matrix before spectral clustering, and SDSC constitutes the first attempt to build a universal three-stage subspace clustering framework.

Public transport is one of the major forms of transportation in the world. This makes it vital to ensure that public transport is efficient. This research presents a novel real-time GPS bus transit data for over 500 routes of buses operating in New Delhi. The data can be used for modeling various timetable optimization tasks as well as in other domains such as traffic management, travel time estimation, etc. The paper also presents an approach to reduce the waiting time of Delhi buses by analyzing the traffic behavior and proposing a timetable. This algorithm serves as a benchmark for the dataset. The algorithm uses a constrained clustering algorithm for classification of trips. It further analyses the data statistically to provide a timetable which is efficient in learning the inter- and intra-month variations.

Motivation: Identifying interaction clusters of large gene regulatory networks (GRNs) is critical for its further investigation, while this task is very challenging, attributed to data noise in experiment data, large scale of GRNs, and inconsistency between gene expression profiles and function modules, etc. It is promising to semi-supervise this process by prior information, but shortage of prior information sometimes make it very challenging. Meanwhile, it is also annoying, and sometimes impossible to discovery gold standard for evaluation of clustering results.\\ Results: With assistance of an online enrichment tool, this research proposes a semi-supervised hierarchical clustering method via deconvolved correlation matrix~(SHC-DC) to discover interaction clusters of large-scale GRNs. Three benchmark networks including a \emph{Ecoli} network and two \emph{Yeast} networks are employed to test semi-supervision scheme of the proposed method. Then, SHC-DC is utilized to cluster genes in sleep study. Results demonstrates it can find interaction modules that are generally enriched in various signal pathways. Besides the significant influence on blood level of interleukins, impact of sleep on important pathways mediated by them is also validated by the discovered interaction modules.

In this post, we will take a look at a few cases, where KMC algorithm does not perform well or may produce unintuitive results. All of these conditions can lead to problems with K-Means, so let's have a look. To make it easier, let's define a helper function compare, which will create and solve the clustering problem for us and then compare the results. Despite having distinct clusters in the data, we underestimated their number. As a consequence, some disjoint groups of data are forced to fit into one larger cluster.

In this paper, we propose a unified clustering approach that can estimate number of clusters and produce clustering against this number simultaneously. Average silhouette width (ASW) is a widely used standard cluster quality index. We define a distance based objective function that optimizes ASW for clustering. The proposed algorithm named as OSil, only, needs data observations as an input without any prior knowledge of the number of clusters. This work is about thorough investigation of the proposed methodology, its usefulness and limitations. A vast spectrum of clustering structures were generated, and several well-known clustering methods including partitioning, hierarchical, density based, and spatial methods were consider as the competitor of the proposed methodology. Simulation reveals that OSil algorithm has shown superior perform in terms of clustering quality than all clustering methods included in the study. OSil can find well separated, compact clusters and have shown better performance for the estimation of number of clusters than several methods. Apart from the proposal of the new methodology and it's investigation this papers offer a systematic analysis on the estimation of cluster indices, some of which never appeared together in comparative simulation setup before. The study offers many insightful findings useful for the selection of the clustering methods and indices.

Because of transportation planning, traffic management and dispatch optimization importance, the passenger origin-destination prediction has become one of the most important requirements for intelligent transportation systems management. In this paper, we propose a model to predict the origin and destination of travels which will occur in the next specified time window. In order to extract meaningful travel flows we use K-means clustering in four-dimensional space with maximum cluster size limitation for origin and destination. Because of large number of clusters, we use non-negative matrix factorization to decrease the number of travel clusters. We also use a stacked recurrent neural network model to predict travels count in each cluster. Comparing our results with other existing models show that our proposed model has 5-7% lower mean absolute percentage error (MAPE) for 1-hour time window, and 14% lower MAPE for 30-minute time window.

ABSTRACT W e address the problem of simultaneously learning a k -means clustering and deep feature representation from unlabelle d data, which is of interest due to the potential of deep k -means to outperform traditional two-step feature extraction and shallow-clustering strategies. W e achieve this by develop ing a gradient-estimator for the non-differentiable k -means objective via the Gumbel-Softmax reparameterisation trick. In contrast to previous attempts at deep clustering, our concr ete k -means model can be optimised with respect to the canonical k -means objective and is easily trained end-to-end without resorting to alternating optimisation. W e demonstrate the efficacy of our method on standard clustering benchmarks. Index T erms-- Deep Clustering, Unsupervised Learning, Gradient Estimator 1. INTRODUCTION Clustering is a fundamental task in unsupervised machine learning, and one with numerous applications.