What class of algorithms reduce margin of error in continuous stream of input?

A machine is taking measurements and giving me discrete numbers continuously like so:

1 2 5 7 8 10 11 12 13 14 18

Let us say these measurements can be off by 2 points and a measurement is generated every 5 seconds. I want to ignore the measurements that may pote开发者_运维技巧ntially be same

Like continuous 2 and 3 could be same because margin of error is 2 so how do I partition the data such that I get only distinct measurements but I would also want to handle the situation in which the measurements are continuously increasing like so:

1 2 3 4 5 6 7 8 9 10

In this case if we keep ignoring the consecutive numbers with difference of less than 2 then we might lose actual measurements.

Is there a class of algorithms for this? How would you solve this?

Just drop any number that comes 'in range of' the previous (kept) one. It should simply work.

For your increasing example:

1 is kept, 2 is dropped because it is in range of 1, 3 is dropped because it is in range of 1, then 4 is kept, 5 and 6 are dropped in range of 4, then 7 is kept, etc, so you still keep the increasing trend if it's big enough (which is what you want, right?

For the original example, you'd get 1,5,8,11,14,18 as a result.

In some lines of work, the standard way to deal with problems of this nature is by using the Kalman filter.

To quote Wikipedia:

Its [Kalman filter's] purpose is to use measurements observed over time, containing noise (random variations) and other inaccuracies, and produce values that tend to be closer to the true values of the measurements and their associated calculated values.

The filter itself is very easy to implement, but does require calibration.

I would have two queues:

• Temporary Queue
• Final Queue/List

Your first value would go into the temporary queue and in the final list. As new values come in, check to see if the new value is within the deadband of the last value in the list. If it is then add it to the temporary queue. If not then add it to the final list. If your temporary queue starts to increase in size before you get a new value outside of the deadband, then once you are outside of the deadband do a check to see if the values are monotonically increasing or decreasing the whole time. If they are always increasing or decreasing then add the contents of the queue to the final list, otherwise just add the single new value to the final list. This is the general gist of it.

Here is some code I whipped up quickly that implements a class to do what I described above:

public class MeasurementsFilter
    {
        private Queue<int> tempQueue = new Queue<int>();
        private List<int> finalList = new List<int>();

        private int deadband;

        public MeasurementsFilter(int deadband)
        {
            this.deadband = deadband;
        }

        public void Reset()
        {
            finalList.Clear();
            tempQueue.Clear();
        }

        public int[] FinalValues()
        {
            return finalList.ToArray();
        }

        public void AddNewValue(int value)
        {
            // if we are just starting then the first value always goes in the list and queue
            if (tempQueue.Count == 0)
            {
                tempQueue.Enqueue(value);
                finalList.Add(value);
            }
            else
            {
                // if the new value is within the deadband of the last value added to the final list
                // then enqueue the value and wait
                if ((tempQueue.Peek() - deadband <= value) && (value <= tempQueue.Peek() + deadband))
                {
                    tempQueue.Enqueue(value);
                }
                // else the new value is outside of the deadband of the last value added to the final list
                else
                {

                    tempQueue.Enqueue(value);

                    if (QueueIsAlwaysIncreasingOrAlwaysDecreasing())
                    {
                        //dequeue first item (we already added it to the list before, but we need it for comparison purposes)
                        int currentItem = tempQueue.Dequeue();

                        while (tempQueue.Count > 0)
                        {
                            // if we are not seeing two in a row of the same (i.e. they are not duplicates of each other)
                            // then add the newest value to the final list
                            if (currentItem != tempQueue.Peek())
                            {
                                currentItem = tempQueue.Dequeue();
                                finalList.Add(currentItem);
                            }
                            // otherwise if we are seeing two in a row (i.e. duplicates)
                            // then discard the value and loop to the next value
                            else
                            {
                                currentItem = tempQueue.Dequeue();
                            }

                        }

                        // add the last item from the final list back into the queue for future deadband comparisons
                        tempQueue.Enqueue(finalList[finalList.Count - 1]);

                    }
                    else
                    {
                        // clear the queue and add the new value to the list and as the starting point of the queue
                        // for future deadband comparisons
                        tempQueue.Clear();
                        tempQueue.Enqueue(value);
                        finalList.Add(value);
                    }


                }
            }
        }

        private bool QueueIsAlwaysIncreasingOrAlwaysDecreasing()
        {
            List<int> queueList = new List<int>(tempQueue);

            bool alwaysIncreasing = true;
            bool alwaysDecreasing = true;

            int tempIncreasing = int.MinValue;
            int tempDecreasing = int.MaxValue;

            int i = 0;

            while ((alwaysIncreasing || alwaysDecreasing) && (i < queueList.Count))
            {
                if (queueList[i] >= tempIncreasing)
                    tempIncreasing = queueList[i];
                else
                    alwaysIncreasing = false;

                if (queueList[i] <= tempDecreasing)
                    tempDecreasing = queueList[i];
                else
                    alwaysDecreasing = false;

                i++;

            }

            return (alwaysIncreasing || alwaysDecreasing);

        }
    }

Here is some test code that you can throw into a Winform Load event or button click:

int[] values = new int[] { 1, 2, 2, 1, 4, 8, 3, 2, 1, 0, 6 };

            MeasurementsFilter filter = new MeasurementsFilter(2);

            for (int i = 0; i < values.Length; i++)
            {
                filter.AddNewValue(values[i]);
            }


            int[] finalValues = filter.FinalValues();

            StringBuilder printValues = new StringBuilder();

            for (int i = 0; i < finalValues.Length; i++)
            {
                printValues.Append(finalValues[i]);
                printValues.Append(" ");
            }

            MessageBox.Show("The final values are: " + printValues);