DBSCAN and OPTICS clustering algorithms.

Last update: Dec 15, 2022

Overview

petal-clustering

A collection of clustering algorithms. Currently this crate provides DBSCAN and OPTICS.

Examples

The following example shows how to cluster points using DBSCAN.

use ndarray::array;
use petal_clustering::{Dbscan, Fit};

let points = array![[1.0, 2.0], [2.0, 2.0], [2.0, 2.3], [8.0, 7.0], [8.0, 8.0], [25.0, 80.0]];
let clustering = Dbscan::new(3.0, 2).fit(&points);

assert_eq!(clustering.0.len(), 2);        // two clusters found
assert_eq!(clustering.0[&0], [0, 1, 2]);  // the first three points in Cluster 0
assert_eq!(clustering.0[&1], [3, 4]);     // [8.0, 7.0] and [8.0, 8.0] in Cluster 1
assert_eq!(clustering.1, [5]);            // [25.0, 80.0] doesn't belong to any cluster

Minimum Supported Rust Version

This crate is guaranteed to compile on Rust 1.49 and later.

License

Licensed under Apache License, Version 2.0 (the "License"); you may not use this crate except in compliance with the License.

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See LICENSE for the specific language governing permissions and limitations under the License.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be licensed as above, without any additional terms or conditions.

Comments

Custom Distance Metric Implementation Example

Hi, sorry for the dumb question, I'm new to rust and algorithms in general but I'm trying to implement a distance metric using lat, lon coordinates to return the number of meters:

    fn earth_distance(start: [f64; 2], end: [f64; 2]) -> f64 {
        let d_lat: f64 = (end[0] - start[0]).to_radians();
        let d_lon: f64 = (end[1] - start[1]).to_radians();
        let lat1: f64 = (start[0]).to_radians();
        let lat2: f64 = (end[0]).to_radians();
    
        let a: f64 = ((d_lat / 2.0).sin()) * ((d_lat / 2.0).sin())
            + ((d_lon / 2.0).sin()) * ((d_lon / 2.0).sin()) * (lat1.cos()) * (lat2.cos());
        let c: f64 = 2.0 * ((a.sqrt()).atan2((1.0 - a).sqrt()));
    
        6.371 * c
    }

I notcied that petal-clustering has support for custom metric functions, but it's not clear how to implement this in my code. Any advice would be greatly appreciated, thank you!

opened by TurtIeSocks 2

Update criterion requirement from 0.3 to 0.4
Updates the requirements on criterion to permit the latest version.

Changelog

Sourced from criterion's changelog.

[0.4.0] - 2022-09-10

Removed

The Criterion::can_plot function has been removed.

The Criterion::bench_function_over_inputs function has been removed.

The Criterion::bench_functions function has been removed.

The Criterion::bench function has been removed.

Changed

HTML report hidden behind non-default feature flag: 'html_reports'

Standalone support (ie without cargo-criterion) feature flag: 'cargo_bench_support'

MSRV bumped to 1.57

rayon and plotters are optional (and default) dependencies.

Status messages ('warming up', 'analyzing', etc) are printed to stderr, benchmark results are printed to stdout.

Accept subsecond durations for --warm-up-time, --measurement-time and --profile-time.

Replaced serde_cbor with ciborium because the former is no longer maintained.

Upgrade clap to v3 and regex to v1.5.

Added

A --discard-baseline flag for discarding rather than saving benchmark results.

Formal support for benchmarking code compiled to web-assembly.

A --quiet flag for printing just a single line per benchmark.

A Throughput::BytesDecimal option for measuring throughput in bytes but printing them using decimal units like kilobytes instead of binary units like kibibytes.

Fixed

When using bench_with_input, the input parameter will now be passed through black_box before passing it to the benchmark.

[0.3.6] - 2022-07-06

Changed

MSRV bumped to 1.49

Symbol for microseconds changed from ASCII 'us' to unicode 'µs'

Documentation fixes

Clippy fixes

[0.3.5] - 2021-07-26

Fixed

Corrected Criterion.toml in the book.

Corrected configuration typo in the book.

Changed

Bump plotters dependency to always include a bug-fix.

MSRV bumped to 1.46.

... (truncated)

Commits

5e27b69 Merge branch 'version-0.4'

4d6d69a Increment version numbers.

935c632 Add Throughput::BytesDecimal. Fixes #581.

f82ce59 Remove critcmp code (it belongs in cargo-criterion) (#610)

a18d080 Merge branch 'master' into version-0.4

f9c6b8d Merge pull request #608 from Cryptex-github/patch-1

8d0224e Fix html report path

2934163 Add missing black_box for bench_with_input parameters. Fixes 566.

dfd7b65 Add duplicated benchmark ID to assertion message.

ce8259e Bump criterion-plot version number.

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 1
Update petal-neighbors requirement from 0.7.1 to 0.8.0
Updates the requirements on petal-neighbors to permit the latest version.

Changelog

Sourced from petal-neighbors's changelog.

[0.8.0] - 2022-04-18

Added

Add pairwise distance computation function.

Changed

Make fields of Node, BallTree accessible for user.

MSRV is changed to 1.53.0.

[0.7.1] - 2021-07-06

Added

Implement Clone and Sync for Euclidean struct.

[0.7.0] - 2021-06-23

Changed

Add Metric trait, use it for distance calculation instead of function pointer.

Add Euclidean struct, which implements Metric trait.

[0.6.0] - 2021-03-29

Changed

Upgrade ndarray to 0.15.0

Requires Rust 1.49 or later.

[0.5.2] - 2021-02-16

Changed

Fixed build on aarch64.

[0.5.1] - 2020-12-30

Changed

Upgrade ndarray to 0.14.0

[0.5.0] - 2020-08-20

Changed

BallTree and VantagePointTree accept an ndarray as a point.

Fixed

... (truncated)

Commits

44c0d6e update License

3dc2e02 Bump version to 0.8.0

884d3f2 usize::BITS requires rust 1.53.0

2611f76 fix changelog

c3c3279 use usize::BITS instead of size_of

f84d650 add functions for accessing ball tree data

e55fc70 add unit test for balltree

7f38759 update CHANGELOG

b5b7b6d expose members of ball tree for user

2aaec77 calculate pairwise distances of x, given metrics

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 1
Update ndarray requirement from 0.14 to 0.15
Updates the requirements on ndarray to permit the latest version.

Changelog

Sourced from ndarray's changelog.

Version 0.15.0 (2021-03-25)

New features

Support inserting new axes while slicing by [@jturner314]. This is an example:

let view = arr.slice(s![.., -1, 2..;-1, NewAxis]);

rust-ndarray/ndarray#570

Support two-sided broadcasting in arithmetic operations with arrays by [@SparrowLii]

This now allows, for example, addition of a 3 x 1 with a 1 x 3 array; the operands are in this case broadcast to 3 x 3 which is the shape of the result.

Note that this means that a new trait bound is required in some places when mixing dimensionality types of arrays in arithmetic operations.

rust-ndarray/ndarray#898

Support for compiling ndarray as no_std (using core and alloc) by [@xd009642] and [@bluss]

rust-ndarray/ndarray#861 rust-ndarray/ndarray#889

New methods .cell_view() and ArrayViewMut::into_cell_view that enable new ways of working with array elements as if they were in Cells - setting elements through shared views and broadcast views, by [@bluss].

rust-ndarray/ndarray#877

New methods slice_each_axis/_mut/_inplace that make it easier to slice a dynamic number of axes in some situations, by [@jturner314]

rust-ndarray/ndarray#913

New method a.assign_to(b) with the inverse argument order compared to the existing b.assign(a) and some extra features like assigning into uninitialized arrays, By [@bluss].

rust-ndarray/ndarray#947

Enhancements

... (truncated)

Commits

c7ae4eb 0.15.0

3e48234 Merge pull request #952 from rust-ndarray/update-complex

383ac0e TEST: Update dev-dependency itertools to 0.10

888c160 API: Update num-complex to 0.4

175b8f8 Merge pull request #951 from rust-ndarray/disconnect-blas-dependency

5b96f1d TEST: Remove ndarray build.rs and test-blas-openblas-sys feature flag

f98e5c0 API: Drop direct blas-src dependency, update docs for blas integration

fdbc884 Merge pull request #948 from rust-ndarray/neg-stride-constructors

67397ac Merge pull request #949 from rust-ndarray/rename-directories

5c6ff77 MAINT: Rename directories for misc and tests in the root

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 1
Update ndarray requirement from 0.13 to 0.14
Updates the requirements on ndarray to permit the latest version.

Changelog

Sourced from ndarray's changelog.

Version 0.14.0 (2020-11-28)

New features

Zip::apply_collect and Zip::par_apply_collect now supports general elements (not just Copy) rust-ndarray/ndarray#817

New function stack (new behaviour!) by [@andrei-papou]

Enhancements

Handle inhomogenous shape inputs better in Zip, in practice, guess better whether to prefer c- or f-order for the inner loop by [@bluss] rust-ndarray/ndarray#809

API changes

The old function stack has been renamed to concatenate. A new function stack with numpy-like semantics have taken its place. Old usages of stack should change to use concatenate.

concatenate produces an array with the same number of axes as the inputs.
stack produces an array that has one more axis than the inputs.

This change was unfortunately done without a deprecation period, due to the long period between releases.

Enum ErrorKind is now properly non-exhaustive and has lost its old placeholder invalid variant. By [@Zuse64] rust-ndarray/ndarray#848

Remove deprecated items:

RcArray (deprecated alias for ArcArray)

Removed subview_inplace use collapse_axis

Removed subview_mut use index_axis_mut

Removed into_subview use index_axis_move

Removed subview use index_axis

Removed slice_inplace use slice_collapse

Undeprecate remove_axis because its replacement is hard to find out on your own.

Update public external dependencies to new versions by [@Eijebong] and [@bluss]

num-complex 0.3

approx 0.4 (optional)

blas-src 0.6.1 and openblas-src 0.9.0 (optional)

rust-ndarray/ndarray#810

... (truncated)

Commits

fec35f7 0.14.0

f51f3e4 API: Remove deprecated subview and indexing methods

8fec0eb API: Remove RcArray (deprecated alias of ArcArray)

dd06116 Merge pull request #851 from rust-ndarray/further-dep-bumps

84eeb11 MAINT: Write license spec in Cargo.toml in the more spec-correct way

a9b4ab8 API: Bump approx to 0.4

5cf7572 API: Bump num-complex to version 0.3

76c8a95 Merge pull request #810 from Eijebong/deps

716221c Merge pull request #850 from andrei-papou/stack-concatenate-renaming

2bae4cc Merge pull request #834 from acj/patch-1

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 1
Update petal-neighbors requirement from 0.4 to 0.5
Updates the requirements on petal-neighbors to permit the latest version.

Changelog

Sourced from petal-neighbors's changelog.

[0.5.0] - 2020-08-20

Changed

BallTree and VantagePointTree accept an ndarray as a point.

Fixed

No longer panics when a coordinate is NaN; the distance from a point with NaN in its coordinate and another point is considered greater than the distance between any two points without NaN in their coordinates.

BallTree::query returns empty vectors, rather than panics, when k is zero.

[0.4.0] - 2020-06-01

Added

A vantage point tree data structure to find nearest points.

BallTree accepts not only an f64 array but also an f32one.

BallTree::euclidean to create a ball tree withoug having to pass a distance metric as an argument.

Changed

The codinates of each point must be stored in a contiguous area in memory.

A distance metric is now a function, not a trait.

[0.3.0] - 2020-04-17

Changed

The ownership of the input can be transferred to BallTree, which accepts both an owned array and a view.

An error is returned, rather than a panic, if an empty array is given to construct a BallTree.

query_one has been renamed query_nearest.

query returns indices and distances separately, so that data of the same type are stored together.

[0.2.0] - 2020-04-09

Changed

BallTree takes ArrayBase as its input, instead of ArrayView, to allow more types in ndarray.

[0.1.0] - 2019-11-20

Added

Commits

8973eb9 Release 0.5.0 (#34)

ae234fc Avoid panic when k for k-neighbor search is zero (#33)

77a89cf Avoid panic when a coordinate is NaN (#32)

c1e96f2 Accept an ndarray as a point (#31)

86f5692 Add license information to README

6246561 Silence a clippy warning with Rust 1.45 (#29)

30b6834 Create dependabot.yml

See full diff in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 1
Update petal-neighbors requirement from 0.3 to 0.4
Updates the requirements on petal-neighbors to permit the latest version.

Changelog

Sourced from petal-neighbors's changelog.

0.4.0 - 2020-06-01

Added

A vantage point tree data structure to find nearest points.

BallTree accepts not only an f64 array but also an f32one.

BallTree::euclidean to create a ball tree withoug having to pass a distance metric as an argument.

Changed

The codinates of each point must be stored in a contiguous area in memory.

A distance metric is now a function, not a trait.

0.3.0 - 2020-04-17

Changed

The ownership of the input can be transferred to BallTree, which accepts both an owned array and a view.

An error is returned, rather than a panic, if an empty array is given to construct a BallTree.

query_one has been renamed query_nearest.

query returns indices and distances separately, so that data of the same type are stored together.

0.2.0 - 2020-04-09

Changed

BallTree takes ArrayBase as its input, instead of ArrayView, to allow more types in ndarray.

0.1.0 - 2019-11-20

Added

A ball tree data structure to find nearest neighbors.

Commits

See full diff in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot will not automatically merge this PR because this dependency is pre-1.0.0.

Note: This repo was added to Dependabot recently, so you'll receive a maximum of 5 PRs for your first few update runs. Once an update run creates fewer than 5 PRs we'll remove that limit.

You can always request more updates by clicking Bump now in your Dependabot dashboard.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

@dependabot use these labels will set the current labels as the default for future PRs for this repo and language

@dependabot use these reviewers will set the current reviewers as the default for future PRs for this repo and language

@dependabot use these assignees will set the current assignees as the default for future PRs for this repo and language

@dependabot use this milestone will set the current milestone as the default for future PRs for this repo and language

@dependabot badge me will comment on this PR with code to add a "Dependabot enabled" badge to your readme

Additionally, you can set the following in your Dependabot dashboard:

Update frequency (including time of day and day of week)

Pull request limits (per update run and/or open at any time)

Automerge options (never/patch/minor, and dev/runtime dependencies)

Out-of-range updates (receive only lockfile updates, if desired)

Security updates (receive only security updates, if desired)

dependencies
opened by dependabot-preview[bot] 1
Use tarpaulin for code coverage

Tarpaulin is a code coverage reporting tool written in Rust. This replaces kcov, which required installing many library packages, often leading to network-related errors.

Note: Because Tarpaulin's coverage calculation is slightly different from kcov, this pull request shows lower coverage even though it contains no change in Rust files.

opened by msk 1
faster parallel HDBSCAN

Hello petal-cluster team,

I noticed that there is a new idea to parallel HDBSCAN here: https://dl.acm.org/doi/abs/10.1145/3448016.3457296

Any possibility to also implement this one.

Thanks,

Jianshu

opened by jianshu93 0