arXiv:2407.18287v1 Announce Sort: new
Summary: Clustering algorithms steadily require the variety of clusters to be chosen prematurely, however it’s normally not clear how to do that. To sort out this problem when clustering inside sequential knowledge, we current a technique for estimating the variety of clusters when the info is a trajectory of a Block Markov Chain. Block Markov Chains are Markov Chains that exhibit a block construction of their transition matrix. The tactic considers a matrix that counts the variety of transitions between completely different states throughout the trajectory, and transforms this right into a spectral embedding whose dimension is ready by way of singular worth thresholding. The variety of clusters is subsequently estimated by way of density-based clustering of this spectral embedding, an method impressed by literature on the Stochastic Block Mannequin. By leveraging and augmenting latest outcomes on the spectral focus of random matrices with Markovian dependence, we present that the strategy is asymptotically constant – despite the dependencies between the rely matrix’s entries, and even when the rely matrix is sparse. We additionally current a numerical analysis of our methodology, and examine it to options.
Supply hyperlink