[Assignment] - dictionnary based numbers compression

Question

You want to compress a set of numbers s=[s0,s1,...sn-1] to k numbers [v0...vk-1] with n>k.
Each number in s will be replaced with the nearest of the numbers in v. ie si will be replaced by vi such that min(abs(si-vp for p in 0..k-1))=abs(si-vi)
To maximize the quality of the compression, you will try to minimize the squared error, ie
Sum for i in [0..n-1] (min(Si-vj)^2 for j in [0...k-1])
Program the function compress(s,k) returning v0...vk-1

Answer 1

yeah, I was pondering if I write a generic n-dimensional solution or if I stick to one dimension and get some optimization on the distance calculation, ordering and averaging. Your proposal is to stick in 1D, well! Let's try it.

Answer 2

The week was full, so only today I had some time to work on it.
https://code.sololearn.com/cvv8C7XYd7sJ/?ref=app

Answer 3

Edward VcC
I've found that by choosing the initial values based on the largest gaps you get an error that is smaller in most cases.
Edit: In some cases!
https://code.sololearn.com/cyNv1QxMoawy/#py

Answer 4

I tried a few things, but I am not close to where you and Edward are.
Started having a look at K-means.
Pythons graphics limitations are frustrating.
Found this nice online sample.
check it out
https://miguelmota.com/blog/k-means-clustering-in-javascript/demo/

Answer 5

VcC what I could figure out playing around with k-means in octave is that in well defined problems, where k has the size of well grouped points, the algorithm is really good. In ill defined problems like k 1 or 2 bigger than the points groups the algorithm gets very sensitive to initial conditions, not necessarily delivering the global minimum. If you want I can send the code from octave (i.e. Matlab) so you can play with it. Louis for you as well.

Answer 6

interesting !

Answer 7

https://code.sololearn.com/cPIbiVwbJT5f/?ref=app

Answer 8

You sure are !

Answer 9

Edward kmeans for dimension 1 can be optimized versus the naive version i propose.

Answer 10

Edward what is funny is that when you compare kmean with the exact solution given by my codes you often have differences even for small sets...

Answer 11

yes, Kmeans does not guarantee the optimum solution and is VERY dependent on the inicial choice of starting points. But Kmean implementations are relatively fast and can do a job that is 99,99% good at a fraction of the time. Specially at large sets (above many thousend) kmeans tends to perform very well. In your program this can be seen.

Answer 12

Additionay, Kmeans is developed to separate unlabeled data in categories and not to express the data in a mathematical precise compressed form.

Answer 13

Edward kmeans can be up to 20% more distance than the optimal. Agree it is fast but there are cases where it gives local minimums which are fnot so close from the optimal.

Answer 14

Edward the problem stated here is exactly what kmeans are made for- reduce n points to k centroids while minimizing the squared distance

Answer 15

cc Louis Cépagrave Nevfy LukArToDo Edward any proposition ?

Answer 16

Thanks VcC. I'm not sure if I'm clever enough, but I'll give it a go.

Answer 17

VcC I'm assuming that Si is a list of floats you're trying to convert to integer while minimizing the error. The list Vi has same number of elements as Si (k). I do not recognize the issue...my statement has a mathematical closed form (quite simple), so maybe I'm missing your point here.
[edit] I cheated and looked to your code in order to understand what you mean ... so list S has n elements and list V has k elements, and n>=k.
Since I cheated (and I knew the optimized version of the algorithm because I took the class, can be solved with 3 or 4 lines of NumPy within a loop) I consider myself an "outrunner" not participating in the contest.