|
樓主 |
發表於 16-5-16 15:24
|
顯示全部樓層
Top down 的意思是給定一個最高standard error 門檻數值。然後在數列中,每次找一個新折點,令加入折點後數列的standard error總和為最小。然後看折好後的數列,如果數列的standard error仍高於門檻的話,用同樣方法處理, 直至每個數列的standard error都少於門檻數值。
因為不知道最終要折多少次,所以iteration approach不能用。
參考pseudo code:
Algorithm Seg_TS = Top_Down(T , max_error)
best_so_far = inf;
for i = 2 to length(T) - 2 // Find best place to split the time series.
improvement_in_approximation = improvement_splitting_here(T,i);
if improvement_in_approximation < best_so_far
breakpoint = i;
best_so_far = improvement_in_approximation;
end;
end;
// Recursively split the left segment if necessary.
if calculate_error(T[1:breakpoint]) > max_error
Seg_TS = Top_Down(T[1: breakpoint]);
end;
// Recursively split the right segment if necessary.
if calculate_error( T[breakpoint + 1:length(T)] ) > max_error
Seg_TS = Top_Down(T[breakpoint + 1: length(T)]);
end;
以上參考文章為"An Online Algorithm for Segmenting Time Series" from Department of Information and Computer Science, University of California
現在在看Ramer–Douglas–Peucker algorithm會不會比較好, 這個能用iteration解決。
|
|