logo标签列表

如何在ArrayList中检测异常值

javaarraylistoutliers
6

我正在尝试思考一些代码，使我可以搜索我的ArrayList并检测任何超出“好值”常见范围的值。

示例： 100 105 102 13 104 22 101

我应该如何编写代码以检测到（在这种情况下）13和22不在大约100的“好值”范围内？

8
你需要严格定义你所说的“好价值观”。它们是指比平均值高x个标准差的价值观吗？还是其他什么？ - Kon
4
使用一些if语句很容易实现。 - user1231232141214124
1
阅读有关异常值检测的内容：http://en.wikipedia.org/wiki/Outlier#Identifying_outliers - NPE
你能解释一下如何使用 if 语句来实现这个吗，@redFIVE。谢谢。 - Ashton
不行。你需要学会如何使用if语句。 - user1231232141214124
1
@redFIVE 我只是想确保我选择了正确的起始点。我明白 if 语句是一个布尔比较，只有在该比较通过时才会执行嵌套在该比较下方的代码块中的语句，并返回值为1而非0。不过，还是谢谢你的建议。我考虑过使用 if 语句，并在循环中进行比较，判断这两个变量是否有任何一个大于五或小于负五的值。但是，我遇到了一个问题，即如何确定应该删除哪个元素。 - Ashton
9个回答
7
package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Double> data = new ArrayList<Double>();
        data.add((double) 20);
        data.add((double) 65);
        data.add((double) 72);
        data.add((double) 75);
        data.add((double) 77);
        data.add((double) 78);
        data.add((double) 80);
        data.add((double) 81);
        data.add((double) 82);
        data.add((double) 83);
        Collections.sort(data);
        System.out.println(getOutliers(data));
    }

    public static List<Double> getOutliers(List<Double> input) {
        List<Double> output = new ArrayList<Double>();
        List<Double> data1 = new ArrayList<Double>();
        List<Double> data2 = new ArrayList<Double>();
        if (input.size() % 2 == 0) {
            data1 = input.subList(0, input.size() / 2);
            data2 = input.subList(input.size() / 2, input.size());
        } else {
            data1 = input.subList(0, input.size() / 2);
            data2 = input.subList(input.size() / 2 + 1, input.size());
        }
        double q1 = getMedian(data1);
        double q3 = getMedian(data2);
        double iqr = q3 - q1;
        double lowerFence = q1 - 1.5 * iqr;
        double upperFence = q3 + 1.5 * iqr;
        for (int i = 0; i < input.size(); i++) {
            if (input.get(i) < lowerFence || input.get(i) > upperFence)
                output.add(input.get(i));
        }
        return output;
    }

    private static double getMedian(List<Double> data) {
        if (data.size() % 2 == 0)
            return (data.get(data.size() / 2) + data.get(data.size() / 2 - 1)) / 2;
        else
            return data.get(data.size() / 2);
    }
}

输出: [20.0]

解释:

  • 将整数列表按从小到大的顺序排序
  • 通过中间值将整数列表分成两部分，并将它们放入两个新的独立的ArrayLists中（称为"left"和"right"）
  • 在这两个新的ArrayLists中找到中间数（中位数）
  • Q1是左侧的中位数，Q3是右侧的中位数
  • 应用以下数学公式：
  • IQR = Q3 - Q1
  • LowerFence = Q1 - 1.5*IQR
  • UpperFence = Q3 + 1.5*IQR
  • 关于这个公式的更多信息：http://www.mathwords.com/o/outlier.htm
  • 循环遍历所有原始元素，如果它们低于下限或高于上限，则将它们添加到"output" ArrayList中
  • 这个新的"output" ArrayList包含异常值
这段代码非常糟糕。它假设输入已经排序好了。如果数据为空或者数据大小为1，getMedian函数会出现错误。 - Mladen Adamovic
7
总的来说，Stackoverflow上的代码应该被视为给其他人指导的方向，而不是“生产代码，可以复制/粘贴”，这至少是专业工程师们的做法。基于边缘情况批评比编写像sklimkovitch那样完整的算法要容易得多。就像流行歌曲唱的那样：“要谦虚”;-) - Clint Eastwood
7

检测异常值有几个标准。最简单的标准，如Chauvenet's criterion，使用从样本计算出的平均值和标准差确定值的“正常”范围。任何超出此范围的值都被视为异常值。

其他标准包括Grubb's test和Dixon's Q test，例如如果样本来自偏斜分布，则可能比Chauvenet的标准产生更好的结果。

我不确定我是否计算标准差错误。在我的JUnit中，我的数组是10、12、11、25、13和14。我计算出的标准差是5.----。我不确定如何解释这个答案并将其作为数据因素使用。 - Ashton
4

可以在MathUtil.java找到Grubb's test的实现。它将找到一个异常值，你可以从列表中删除并重复此过程，直到删除所有异常值。

依赖于commons-math，所以如果你使用Gradle：

dependencies {
  compile 'org.apache.commons:commons-math:2.2'
}
1

使用此算法。该算法使用平均值和标准差。这两个数字是可选值（2 * standardDeviation）。

 public static List<int> StatisticalOutLierAnalysis(List<int> allNumbers)
            {
                if (allNumbers.Count == 0)
                    return null;

                List<int> normalNumbers = new List<int>();
                List<int> outLierNumbers = new List<int>();
                double avg = allNumbers.Average();
                double standardDeviation = Math.Sqrt(allNumbers.Average(v => Math.Pow(v - avg, 2)));
                foreach (int number in allNumbers)
                {
                    if ((Math.Abs(number - avg)) > (2 * standardDeviation))
                        outLierNumbers.Add(number);
                    else
                        normalNumbers.Add(number);
                }

                return normalNumbers;
            }
Java版本未经测试：https://gist.github.com/melanke/69d14ed6a719cbe97c5a761856dfca57 - melanke
1

正如 Joni所指出的那样，您可以通过标准偏差和平均值的帮助消除异常值。以下是我的代码，您可以用于您的目的。

    public static void main(String[] args) {

    List<Integer> values = new ArrayList<>();
    values.add(100);
    values.add(105);
    values.add(102);
    values.add(13);
    values.add(104);
    values.add(22);
    values.add(101);

    System.out.println("Before: " + values);
    System.out.println("After: " + eliminateOutliers(values,1.5f));

}

protected static double getMean(List<Integer> values) {
    int sum = 0;
    for (int value : values) {
        sum += value;
    }

    return (sum / values.size());
}

public static double getVariance(List<Integer> values) {
    double mean = getMean(values);
    int temp = 0;

    for (int a : values) {
        temp += (a - mean) * (a - mean);
    }

    return temp / (values.size() - 1);
}

public static double getStdDev(List<Integer> values) {
    return Math.sqrt(getVariance(values));
}

public static List<Integer> eliminateOutliers(List<Integer> values, float scaleOfElimination) {
    double mean = getMean(values);
    double stdDev = getStdDev(values);

    final List<Integer> newList = new ArrayList<>();

    for (int value : values) {
        boolean isLessThanLowerBound = value < mean - stdDev * scaleOfElimination;
        boolean isGreaterThanUpperBound = value > mean + stdDev * scaleOfElimination;
        boolean isOutOfBounds = isLessThanLowerBound || isGreaterThanUpperBound;

        if (!isOutOfBounds) {
            newList.add(value);
        }
    }

    int countOfOutliers = values.size() - newList.size();
    if (countOfOutliers == 0) {
        return values;
    }

    return eliminateOutliers(newList,scaleOfElimination);
}
  • eliminateOutliers()方法负责所有工作
  • 这是一个递归方法，每次递归调用都会修改列表
  • 传递给该方法的scaleOfElimination变量定义了要删除异常值的比例尺：通常我使用1.5f-2f，变量越大，删除的异常值就越少

代码输出结果：

之前：[100, 105, 102, 13, 104, 22, 101]

之后：[100, 105, 102, 104, 101]

1
  • 找到您列表的平均值
  • 创建一个将数字映射到与平均值的距离的Map
  • 按距离从平均值排序数值
  • 区分最后的n个数字，确保距离没有不公正的情况
0
感谢@Emil_Wozniak发布完整的代码。我曾经苦苦挣扎，不知道eliminateOutliers()实际上返回的是离群值，而不是已经删除它们的列表。 isOutOfBounds()方法也很令人困惑，因为它实际上在值在范围内时返回TRUE。以下是我的更新，其中包含一些（在我看来）改进：
  • eliminateOutliers()方法返回已删除离群值的输入列表
  • 添加getOutliers()方法以获取离群值列表
  • 删除混淆的isOutOfBounds()方法，改用简单的过滤表达式
  • 扩展N列表，支持多达30个输入值
  • 当输入列表太大或太小时，防止越界错误
  • 将统计方法（平均值、标准差、方差）作为静态实用程序方法
  • 仅在每次比较时计算上/下限
  • 在构造函数中提供输入列表并存储为实例变量
  • 重构以避免使用与实例和局部变量相同的变量名

代码：

/**
 * Implements an outlier removal algorithm based on https://www.itl.nist.gov/div898/software/dataplot/refman1/auxillar/dixon.htm#:~:text=It%20can%20be%20used%20to,but%20one%20or%20two%20observations).
 * Original Java code by Emil Wozniak at https://dev59.com/dXbZa4cB1Zd3GeqPKtgf
 * 
 * Reorganized, made more robust, and clarified many of the methods.
 */

import java.util.List;
import java.util.stream.Collectors;

public class DixonTest {
    protected List<Double> criticalValues = 
            List.of( // Taken from https://sebastianraschka.com/Articles/2014_dixon_test.html#2-calculate-q
                    // Alfa level of 0.1 (90% confidence)
                    0.941,  // N=3
                    0.765,  // N=4
                    0.642,  // ...
                    0.56,
                    0.507,
                    0.468,
                    0.437,
                    0.412,
                    0.392,
                    0.376,
                    0.361,
                    0.349,
                    0.338,
                    0.329,
                    0.32,
                    0.313,
                    0.306,
                    0.3,
                    0.295,
                    0.29,
                    0.285,
                    0.281,
                    0.277,
                    0.273,
                    0.269,
                    0.266,
                    0.263,
                    0.26     // N=30
                    );
    
    // Stats calculated on original input data (including outliers)
    private double scaleOfElimination;
    private double mean;
    private double stdDev;
    private double UB;
    private double LB;
    private List<Double> input;
    
    /**
     * Ctor taking a list of values to be analyzed. 
     * @param input
     */
    public DixonTest(List<Double> input) {
        this.input = input;
        
        // Create statistics on the original input data
        calcStats();
    }

    /**
     * Utility method returns the mean of a list of values.
     * @param valueList
     * @return
     */
    public static double getMean(final List<Double> valueList) {
        double sum = valueList.stream()
                .mapToDouble(value -> value)
                .sum();
        return (sum / valueList.size());
    }

    /**
     * Utility method returns the variance of a list of values.
     * @param valueList
     * @return
     */
    public static double getVariance(List<Double> valueList) {
        double listMean = getMean(valueList);
        double temp = valueList.stream()
                .mapToDouble(a -> a)
                .map(a -> (a - listMean) * (a - listMean))
                .sum();
        return temp / (valueList.size() - 1);
    }

    /**
     * Utility method returns the std deviation of a list of values.
     * @param input
     * @return
     */
    public static double getStdDev(List<Double> valueList) {
        return Math.sqrt(getVariance(valueList));
    }
    
    /**
     * Calculate statistics and bounds from the input values and store
     * them in class variables.
     * @param input
     */
    private void calcStats() {
        int N = Math.min(Math.max(0, input.size() - 3), criticalValues.size()-1); // Changed to protect against too-small or too-large lists
        scaleOfElimination = criticalValues.get(N).floatValue();
        mean = getMean(input);
        stdDev = getStdDev(input);
        UB = mean + stdDev * scaleOfElimination;
        LB = mean - stdDev * scaleOfElimination;        
    }

    /**
     * Returns the input values with outliers removed.
     * @param input
     * @return
     */
    public List<Double> eliminateOutliers() {

        return input.stream()
                .filter(value -> value>=LB && value <=UB)
                .collect(Collectors.toList());
    }

    /**
     * Returns the outliers found in the input list.
     * @param input
     * @return
     */
    public List<Double> getOutliers() {

        return input.stream()
                .filter(value -> value<LB || value>UB)
                .collect(Collectors.toList());
    }

    /**
     * Test and sample usage
     * @param args
     */
    public static void main(String[] args) {
        List<Double> testValues = List.of(1200.0,1205.0,1220.0,1194.0,1212.0);
        
        DixonTest outlierDetector = new DixonTest(testValues);
        List<Double> goodValues = outlierDetector.eliminateOutliers();
        List<Double> badValues = outlierDetector.getOutliers();
        
        System.out.println(goodValues.size()+ " good values:");
        for (double v: goodValues) {
            System.out.println(v);
        }
        System.out.println(badValues.size()+" outliers detected:");
        for (double v: badValues) {
            System.out.println(v);
        }
        
        // Get stats on remaining (good) values
        System.out.println("\nMean of good values is "+DixonTest.getMean(goodValues));
    }
}
0

非常感谢Valiyev，他的解决方案帮了我很多忙。我想在他的作品上分享我的小SRP。

请注意，我使用List.of()来存储Dixon的临界值，因此需要使用高于Java 8的版本。

public class DixonTest {
protected List<Double> criticalValues = 
    List.of(0.941, 0.765, 0.642, 0.56, 0.507, 0.468, 0.437);
private double scaleOfElimination;
private double mean;
private double stdDev;

private double getMean(final List<Double> input) {
    double sum = input.stream()
            .mapToDouble(value -> value)
            .sum();
    return (sum / input.size());
}

  private double getVariance(List<Double> input) {
    double mean = getMean(input);
    double temp = input.stream()
            .mapToDouble(a -> a)
            .map(a -> (a - mean) * (a - mean))
            .sum();
    return temp / (input.size() - 1);
}

private double getStdDev(List<Double> input) {
    return Math.sqrt(getVariance(input));
}

protected List<Double> eliminateOutliers(List<Double> input) {
    int N = input.size() - 3;
    scaleOfElimination = criticalValues.get(N).floatValue();
    mean = getMean(input);
    stdDev = getStdDev(input);

    return input.stream()
            .filter(this::isOutOfBounds)
            .collect(Collectors.toList());
}

private boolean isOutOfBounds(Double value) {
    return !(isLessThanLowerBound(value)
            || isGreaterThanUpperBound(value));
}

private boolean isGreaterThanUpperBound(Double value) {
    return value > mean + stdDev * scaleOfElimination;
}

private boolean isLessThanLowerBound(Double value) {
    return value < mean - stdDev * scaleOfElimination;
}
}

我希望它能帮助到其他人。

最好的祝福

-1

这只是一个非常简单的实现，它获取不在范围内的数字信息：

List<Integer> notInRangeNumbers = new ArrayList<Integer>();
for (Integer number : numbers) {
    if (!isInRange(number)) {
        // call with a predefined factor value, here example value = 5
        notInRangeNumbers.add(number, 5);
    }
}

此外，在 isInRange 方法内部，您必须定义什么是“好值”。下面是一个示例实现。
private boolean isInRange(Integer number, int aroundFactor) {
   //TODO the implementation of the 'in range condition'
   // here the example implementation
   return number <= 100 + aroundFactor && number >= 100 - aroundFactor;
}
我非常喜欢你的想法，但是我不能在我的程序中使用它，具体来说。数据集可以是任何一组数字，但大多数情况下会围绕某个值。如果不知道该值，是否仍然可以使用你的方法？谢谢。 - Ashton
@Dan 你的意思是这些数字大致在某个值周围，但不知道具体的值。我猜这个值必须以某种方式硬编码/预定义。你可以详细说明你想要实现什么，因为根据我看到的评论，现在还不是非常清楚。 - Łukasz Rzeszotarski
抱歉表述不够清晰。我只是想找到一个“区间平均值”，首先检查输入的数据集是否存在异常值或异常情况，将其从数组列表中删除，然后计算平均值。 - Ashton
@Dan 好的，看起来你需要实现Joni提出的一些标准。当然，你可以调整我的代码来检查一个数字是否是异常值，但现在我们清楚了重点所在。请参见https://gist.github.com/sushain97/6488296，其中有一些关于Chauvenet's Criterion for Outliers的示例。 - Łukasz Rzeszotarski
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接