[ENH] Implement K-Shape clusterer

[MatthewMiddlehurst]

Describe the feature or idea you want to propose

We have a wrapper for K-Shape, but no internal implementation. It may be good to have one and possibly deprecate the wrapper if results match. This should be original, not a copy/paste of the wrapper.

https://dl.acm.org/doi/abs/10.1145/2723372.2737793?casa_token=z9DS09mWDPoAAAAA:01XNIoB-lN0MfyDgh4ox3nBBhkfKyCOTFWcum5hxHsOwrsB-qlYyj8XcObSv-qYQR9QGhg3esMNg-w

Describe your proposed solution

Implement the K-Shape algorithm. It will be on the contributor to evaluate the accuracy of their implementation to published code and results. Efficiency is also a concern here, ideally we would be faster than the wrapper.

Describe alternatives you've considered, if relevant

No response

Additional context

No response

[tanishy7777]

@aeon-actions-bot assign @tanishy7777

[tanishy7777]

I was trying to implementing the kshape clustering algorithm for aeon.
and I noticed that our implementation for the sbd_distance in aeon differs slightly from how tslearn handles it. This dosen't matter for univariate series but for multivariate series we do see differences.

sbd_distance: finds the distance for each channel independently and then takes its average
normalized_cc: finds the correlations for each of the channels and then sums the max of each channels, and then normalizes using the norm of the the entire multivariate series.

This changes the final clustering output? How should we handle this?
If we use aeon's sbd distances we will have to change the test cases to reflect the same, but then we wouldnt have something to compare it against.

I found another implementation of kshape online, one of its contributors is the original author of the kshapes paper. They handle this the same way as tslearn. https://github.com/TheDatumOrg/kshape-python

Image first compares 2 multivariate series and then 2 univariate series, this shows that in the first case there is a difference but in the second case the distances are same.

[SebastianSchmidl]

I found another implementation of kshape online, one of its contributors is the original author of the kshapes paper. They handle this the same way as tslearn. https://github.com/TheDatumOrg/kshape-python

This is the original implementation. In this case, we should adapt the implementation of SBD in aeon to align with the original proposal.

First fix SBD in one PR, then we continue implementing k-shape.

[tanishy7777]

I found another implementation of kshape online, one of its contributors is the original author of the kshapes paper. They handle this the same way as tslearn. https://github.com/TheDatumOrg/kshape-python

This is the original implementation. In this case, we should adapt the implementation of SBD in aeon to align with the original proposal.

First fix SBD in one PR, then we continue implementing k-shape.

Got it, will start working on this.

[tanishy7777]

I found another implementation of kshape online, one of its contributors is the original author of the kshapes paper. They handle this the same way as tslearn. https://github.com/TheDatumOrg/kshape-python

This is the original implementation. In this case, we should adapt the implementation of SBD in aeon to align with the original proposal.

First fix SBD in one PR, then we continue implementing k-shape.

Also I don't think SBD distances have tests. Would it be better if I combine it with the fix PR or should I add a separate PR for the tests?

[SebastianSchmidl]

They are tested. There is no explicit test file for SBD because it is included in the general distance-test machinery; e.g.

• 1-to-1 tests: https://github.com/aeon-toolkit/aeon/blob/main/aeon/distances/tests/test_distances.py
• expected results: https://github.com/aeon-toolkit/aeon/blob/main/aeon/testing/expected_results/expected_distance_results.py#L114

[tanishy7777]

They are tested. There is no explicit test file for SBD because it is included in the general distance-test machinery; e.g.

* 1-to-1 tests: https://github.com/aeon-toolkit/aeon/blob/main/aeon/distances/tests/test_distances.py

* expected results: https://github.com/aeon-toolkit/aeon/blob/main/aeon/testing/expected_results/expected_distance_results.py#L114

oh I see. Thanks! Will proceed with fixing the sbd distance and changing the tests to match with tslearn's output.

[tanishy7777]

@SebastianSchmidl

SBD(official implementation and tslearn) works with unequal length time series but requires them to have equal no of channels.

But in the aeom/tests/test_distances.py under the UNEQUAL_LENGTH_SUPPORT for multivariate case:
We are checking for both unequal length and unequal no of channels? Shouldn't we keep the channels same and if we do want to check if the distance works with different no of channels check that separately?

# ================== Test unequal length ==================
    if dist["name"] in UNEQUAL_LENGTH_SUPPORT_DISTANCES:
        #prev code here       

        # Test multivariate unequal length of shape (n_channels, n_timepoints)
        _validate_distance_result(
            make_example_2d_numpy_series(5, 5, random_state=1),
            make_example_2d_numpy_series(10, 10, random_state=2),
            dist["name"],
            dist["distance"],
            dist["symmetric"],
            _expected_distance_results[dist["name"]][3],