Here I am talking about the algorithm used for finding the regions in which
we are to quantize the given set of values and the values themselves.
As per the Max-Lloyd algo
1) we choose a given set of points as the quantization points
2) we then proceed to find out the region boundary points as perpendicular bisectors so as to minimize the error from the respective set of points
3) we then find the expected value of the point chosen to lie in the interval of interest and call this the new quantization value and so on reiterate the algo
what this basically does is we chose some points and move onto a better approximation of the points, however the algo by itself does not have any clue of the shape of the region so achieved considering two or more dimensional vector space for the points chosen ie group pairs of points.
Hence, even if better MSE(mean square error) can be achieved by changing some of the parameters of the shape of the particular area in consideration then may be the MSE can be reduced further more
For eg if we consider a two dimensional vector space then the algo would most likely settle on a square grid as the best value for MSE. However, a circle would have the least MSE but that will cause problems of coverage and hence hexagons would be the next best option.
So taking all this into account why not modify one the steps of the Lloyd-Max algo
It can be as follows:
Steps 1) , 2) and 3) remain the same during the 1st iteration.
During the next iteration add one more step after step 2) in the algo
Step 3) would now become
Find the MSE on the bisectors at fixed distances. The fixed distance would depend on the spacing of the two dimensional vectors. So when we obtain this we can realize how the MSE changes and modify the shape of the area.
But this would lead to a circle and some areas will remain untouched.
To solve this problem
I have asked to take measurements at fixed distance and not extremely close
Now the previous step 3 will become step 4
And the reiteration can take place
If increasing the quantization levels is permitted then
We can assign a few levels for the spaces that will be left considering that circles would leave some areas untouched.
However the probability that those spaces are actually utilised by the points will be very less due to the very nature in which the algo works
As per the Max-Lloyd algo
1) we choose a given set of points as the quantization points
2) we then proceed to find out the region boundary points as perpendicular bisectors so as to minimize the error from the respective set of points
3) we then find the expected value of the point chosen to lie in the interval of interest and call this the new quantization value and so on reiterate the algo
what this basically does is we chose some points and move onto a better approximation of the points, however the algo by itself does not have any clue of the shape of the region so achieved considering two or more dimensional vector space for the points chosen ie group pairs of points.
Hence, even if better MSE(mean square error) can be achieved by changing some of the parameters of the shape of the particular area in consideration then may be the MSE can be reduced further more
For eg if we consider a two dimensional vector space then the algo would most likely settle on a square grid as the best value for MSE. However, a circle would have the least MSE but that will cause problems of coverage and hence hexagons would be the next best option.
So taking all this into account why not modify one the steps of the Lloyd-Max algo
It can be as follows:
Steps 1) , 2) and 3) remain the same during the 1st iteration.
During the next iteration add one more step after step 2) in the algo
Step 3) would now become
Find the MSE on the bisectors at fixed distances. The fixed distance would depend on the spacing of the two dimensional vectors. So when we obtain this we can realize how the MSE changes and modify the shape of the area.
But this would lead to a circle and some areas will remain untouched.
To solve this problem
I have asked to take measurements at fixed distance and not extremely close
Now the previous step 3 will become step 4
And the reiteration can take place
If increasing the quantization levels is permitted then
We can assign a few levels for the spaces that will be left considering that circles would leave some areas untouched.
However the probability that those spaces are actually utilised by the points will be very less due to the very nature in which the algo works
No comments:
Post a Comment