search

stelmo / LinearSegmentation.jl

Linear segmented regression
MIT License
10 stars 0 forks source link

Adding Dynamic Programming Based Approach #7

Open RoyiAvital opened 1 year ago

RoyiAvital commented 1 year ago

I created a solver to the segmentation based on Dynamic Programming.

It is a formulation I created on my own to the problem as defined in RcppDynProg.

I will be happy to contribute it.

stelmo commented 1 year ago

This is great! I'd be happy to include it :) Just make a PR and I will review/merge it

stelmo commented 1 year ago

Also, note how similar the cost matrix is you implemented to the edge weight matrix of my shortest_path function. A dynamic programming method can also be used to find the shortest path (look at the Graphs.jl package, I think its the Bellman-Ford algorithm). Finding the lowest total cost really is very similar to finding the shortest path...

RoyiAvital commented 1 year ago

It might be. Again, If I would use graphs, I'd go for spectral clustering. Probably first do some partitioning with the eigenvectors matching the zero eigen value.

For some reason, shortest path doesn't sound like it has to thing in the sense of partitions. It might take a single point which is greedy or something like that.

I wouldn't integrate my distance matrix. I'd use the current one if it is in the form of a matrix.

All I was after in this little challenge is just trying to practice dynamic programming.
It was fun to come up with the formulation.

stelmo commented 1 year ago

Hi there, are you still planning on making a PR or should I close this issue?

RoyiAvital commented 1 year ago

@stelmo , I am stretched at this time. But I intend to, so I'd appreciate if you keep it open.