Fast and explainable clustering in the Manhattan and Tanimoto distance
The CLASSIX algorithm is a fast and explainable approach to data clustering. In its original form, this algorithm exploits the sorting of the data points by their first principal component to truncate the search for nearby data points, with nearness being defined in terms of the Euclidean distance. Here we extend CLASSIX to other distance metrics, including the Manhattan distance and the Tanimoto distance. Instead of principal components, we use an appropriate norm of the data vectors as the sorting criterion, combined with the triangle inequality for search termination. In the case of Tanimoto distance, a provably sharper intersection inequality is used to further boost the performance of the new algorithm. On a real-world chemical fingerprint benchmark, CLASSIX Tanimoto is about 30 times faster than the Taylor--Butina algorithm, and about 80 times faster than DBSCAN, while computing higher-quality clusters in both cases.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Mathematical Morphology in Machine Learning
This work introduces mathematical morphology-an established visual computing theory-into machine learning to exploit shape and density aspects often overlooked by standard techniques. We propose a fast clustering algorit…
Tanimoto Random Features for Scalable Molecular Machine Learning
The Tanimoto coefficient is commonly used to measure the similarity between molecules represented as discrete fingerprints, either as a distance metric or a positive definite kernel. While many kernel methods can be acce…
Molecular Property PredictionProperty PredictionFast and explainable clustering based on sorting
We introduce a fast and explainable clustering method called CLASSIX. It consists of two phases, namely a greedy aggregation phase of the sorted data into groups of nearby data points, followed by the merging of groups i…
ClusteringQuasi Manhattan Wasserstein Distance
The Quasi Manhattan Wasserstein Distance (QMWD) is a metric designed to quantify the dissimilarity between two matrices by combining elements of the Wasserstein Distance with specific transformations. It offers improved …
Weighted Tanimoto Coefficient for 3D Molecule Structure Similarity Measurement
Similarity searching of molecular structure has been an important application in the Chemoinformatics, especially in drug discovery. Similarity searching is a common method used for identification of molecular structure.…
Drug Discovery