在簡單的線性數據集中查找並修復錯誤的值

Question

這可能是一個簡單的問題，但我找不到一個好的方法。

我已經得到了有限數量的有序int值，這些值應該是彼此相似的距離，例如：32, 42, 52, 62, 72, 82。

但實際上，有些值是錯誤的。我們可能會以32, 51, 62, 66, 71, 83結束。

我怎樣才能找到明顯錯誤的值（在這種情況下：66），並將其移動到正確的位置（42）？

• 可以假設大多數數據仍然有效，所以仍然可以計算點之間的正確距離（這裏：10）的一個好猜測。
• 點的數量是已知和正確的（即，我們只需要移動但不添加或移除點）。
• 左側和右側的數據邊界是未知的，邊緣情況下的行爲可以自由定義。

---

在寫我想到了什麼問題。一個想法可能是提取一個函數f(x) = a + x * b（這很容易）並迭代已知數量的點。與迭代點距離最大的基準點被移除並插入到原點距離最大的迭代位置。

Answer 1

如果只有一個數據是錯誤的，並假設增加值（如你的例子）： 數據進入數據和DATA_SIZE和閾值是允許的

#include <stdio.h> 
#define THRESHOLD 3 

#define DATA 32, 51, 62, 66, 71, 83 
#define DATA_SIZE 6 
void main() 
{ 
    int data[]={DATA}; int size = DATA_SIZE; 
    int skip = 0, diffs, curDif, maxDif, lastItem, item, dif, maxPos; 
    int maxDiffs = 10000, location, newPosition, newValue; 
    for(skip = 0; skip < size; skip++) 
    { 
     diffs = 0; 
     curDif = 0; 
     maxDif = 0; 
     maxPos = -1; 
     lastItem = (skip == 0); 
     for(item = lastItem+1; item < size; item++) 
     { 
     if(item == skip)continue; 
     dif = data[item]-data[lastItem]; 
     if(abs(dif - curDif) > THRESHOLD) 
     { 
      curDif = dif; 
      diffs++; 
      if(curDif > maxDif) 
      { 
      maxDif = curDif; 
      maxPos = item; 
      } 
     } 
     lastItem = item; 
     } 

     if(diffs < maxDiffs) 
     { 
      maxDiffs = diffs; 
      location = skip; 
      newPosition = maxPos; 
      newValue = data[maxPos-1]+(maxDif>>1); 
     } 
    } 
    printf("Found... \nindex %d\nValue: %d\nGoes in:%d\nNew value:%d\n", location, data[location], newPosition, newValue); 
} 

Answer 2

我用了很多的實驗偏差不同的方法，這是我結束了。基本的想法是爲期望值數組分配好的有效值。無法分配的值可以通過使用缺少的預期值來修復。

鑑於實際數據列表peaks。

建立預期的數據

var expected = Enumerable 
    // 19 is the known number of values 
    .Range (0, 19) 
    // simply interpolate over the actual data 
    .Select (x => peaks.First() + x * (peaks.Last() - peaks.First())/18) 
    .ToList(); 

列表構建所有點

var distances = expected.SelectMany (dst => peaks.Select (src => new { 
    Expected = dst, 
    Original = src, 
    Distance = Math.Abs (dst - src) 
})); 

重複的距離的矩陣

for (;;) 
{ 

選擇最佳距離

var best = distances 
    // ignore really bad values 
    .Where (x => x.Distance < dAvgAll * 0.3) 
    .OrderBy (x => x.Distance).FirstOrDefault(); 

如果沒有找到很好的分配，退出

if (best == null) { 
    break; 
} 

否則，保存比賽

expected.Remove (best.Expected); 
peaks.Remove (best.Original); 

} 

在我們的源的所有有效條目已經確定，並刪除。我們只是使用預期集合中的剩餘值，忽略剩餘的原始值來完成我們的最終數據集。

其他嘗試的方法，包括從古斯布羅的改編版本，工作不太好，經常表現出不好的行爲。

Answer 3

我會嘗試勾勒的算法（我不知道這是否會給出一個正確的結果，對於每個輸入序列，爲此把它當作一個想法）：

輸入的算法是有序序列R。對於實施例32 {51，62，66，71，83}的點之間

1. 查找距離d。我在考慮：

   • 排序元素之間的差異並取中位數。
     分類差異= {4,5,11,12,19} - >中位數= 11
   • 或計算差異的平均值。
     均值= 10.2 - >圓角均值= 10

2. 構建平均值R元素m。
   在我們的例子（32 + 51 + 62 + 66 + 71 + 83）/ 6 = 30.2
   圓角= 30

3. 構建比較SQUENCE S其中第一元件S_0具有值 m - (n/2) * d（其中n是元素的數量），並且任何其他元素S_i具有值S_1 + i * d。
   在我們的例子S = {30，40，50，60，70，80}

4. 因爲在輸入序列中的元素可能已經移動到另一個位置， 構建每個的排列R

5. 找到置換其中的異常值的數目是最小的（離羣值是元件，其中元件差大於0.3 * d

     S = { 30, 40, 50, 60, 70, 80 } 
    permutation x of R = { 32, 51, 62, 66, 71, 83 } three outliers 
    permutation y of R = { 32, 66, 51, 62, 71, 83 } one outlier 
    permutation z of R = ... 

在這個例子中算法的結果是置換y，並且找到元素66的正確位置。

Answer 4

您可以使用robust regression，這只不過是一個奇特的術語，用於「以合適的方式將不適合的點適當地移除，以適合一組點的直線」。

如果您不想編寫非線性優化代碼，則可以使用iteratively reweighted least squares來利用任何現有的加權線性迴歸代碼。

想法是，你做weighted least squares，以適應你的觀點的直線。然後，您爲每個點指定一個權重，衡量您是否認爲它是outlier，偏離迴歸線太多（例如，通過Huber loss function）。然後用重量重新進行迴歸。你會得到一個新的線，因此可以計算一組新的權重。重複，直到收斂（或最大迭代次數）。你會留下權重，告訴你哪些點是不好的，以及一條很適合剩餘點並且可以用來替代異常點的線。

我認爲這個實現並不比上面的文本描述長得多。