Generating ideal step functions using actual step function

user_7422352 0
Viewed 122

I plotted a runtime(in seconds) vs input plot for a function as follows:

enter image description here

You can observe a lot of runtimes which larger than expected represented by the individual points above.

I want to map these points to their expected time downwards to get an ideal step function as follows:

enter image description here

RED dots = runtimes which larger than expected

In the following case the RED dots get mapped to respective expected runtimes:

enter image description here

But it is not always easy to decide where the RED dots should be mapped. For eg:

enter image description here

In the above case, how will we decide to map the RED dot to runtimes T1 or T2?

Also, there are following cases in which we cannot be sure on how to map the RED dots downwards to their ideal or expected runtimes:

enter image description here

The blue dots can create noise for mapping the RED dots downwards in case if we decide to map the dots by judging the neighbours

Finally, there can be a lot of noise as in the following Case:

enter image description here

So, the aim is to achieve an ideal step function to the best possible accuracy by mapping the RED dots downwards to their ideal expected runtimes

Will be thankful for any suggestion.

math algorithm
1 Answers

If the runtime is really linear like the plot tells us.

You can create a linear regression over your data, it will fit the main line of dots without the dots with runtime larger than expected. Than for all the other dots you can take the x value and fit it over the regression, than round it up or down based on if the number modulo 1 is greater than 0.5 or not.

In the first case (practical scenario) you do not have to use this but it will still work since the regression should pass through the middle of all the horizontal lines. This method is very useful in case 4 since it is ignoring the nearby points.

Tip:
While creating the linear regression try to develop a method to ignore the outliers in order to achieve a "clean" regression.

Edit:
More explanation enter image description here

The red line is the output of the linear regression, now for each point take its light blue line and find the intersection point. Now for that intersection point round it up or down (depending on which one is closer) to the T level that match.

user_75015010
Related