- This repository provides implementations of Ex-DPC, Approx-DPC, and S-Approx-DPC.
- They are fast algorithms for density-peaks clustering (proposed in Science).
- As for the details about these algorithms, please read our SIGMOD2021 paper, Fast Density-Peaks Clustering: Multicore-based Parallelization Approach or arXiv one that corrects our theoretical analyses.
- spatial library
- We used version 2.1.8.
- Boost 1.67.0
- We have not confirmed the availability of the other versions.
- The source codes of DPC algorithms have to be changed based on your paths of the above libraries.
- We assume low-dimensional datasets, as we use a kd-tree.
- Implementation is based on https://github.com/gishi523/kd-tree and spatial library.
- Ex-DPC
- Compile:
g++ -O3 main.cpp -o exdpc.out -fopenmp
and run:./exdpc.out
.
- Compile:
- Approc-DPC
- Compile:
g++ -O3 main.cpp -o approxdpc.out -fopenmp
and run:./approxdpc.out
.
- Compile:
- S-Approc-DPC
- Compile:
g++ -O3 main.cpp -o sapproxdpc.out -fopenmp
and run:./sapproxdpc.out
.
- Compile:
- As an example, we have prepared a 2-dimensional synthetic dataset used in our paper.
- If you want to test your dataset,
- Put the file at
dataset
directory. - Assign a unique dataset ID.
- Set the dimensionality at
data.hpp
. - Write codes for inputing the data file in
input_data()
function offile_io.hpp
. - Add a directory in
result
and update the functioncompute_direcotry()
. - Compile the code and run .out file.
- Put the file at
- Set some value in the corresponding txt file in
parameter
. - For \rho_min and \delta_min, we specify them in
file_io.hpp
.
- If you want to compute RI (rand index), ARI, or NMI,
- get cluster labels from Ex-DPC, and
- consult here.
If you use our implementation, please cite the following paper.
@inproceedings{amagata2021dpc,
title={Fast Density-Peaks Clustering: Multicore-based Parallelization Approach},
author={Amagata, Daichi and Hara, Takahiro},
booktitle={SIGMOD},
pages={49--61},
year={2021}
}
Copyright (c) 2020 Daichi Amagata
This software is released under the MIT license.