Random forests are state-of-the-art supervised machine learning models for tabular data. The decision paths in a trained random forest can be used to generate an affinity measure between instances, which can in turn be used in any similarity matrix-based clustering algorithm. However, in the unsupervised setting, labels are not available to train the random forest in the first place. A popular extension of the algorithm for unsupervised learning involves the introduction of a synthetic “negative class”, transforming the problem into binary classification. In this paper, we instead propose AutoAssociative Random Forest Clustering (AARFC), transforming the problem into multi-target regression by training the random forest on the variance in the input features. AARFC more directly optimizes towards the end goal of clustering the instances and does not increase the number of instances in the original input data. We have extensively benchmarked AARFC against the current state-of-the-art using a collection of 223 benchmark datasets with reference labelings. The results show that AARFC is computationally superior, while being competitive. We also propose a hybrid approach that adaptively chooses the best method based on several internal validation criteria. Despite the fact that this hybrid approach outperforms both the current approach used in the literature as well as AARFC, k-means still outperforms the random forest clustering method in the majority of benchmark datasets.