[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.