| 
 | 
 
 樓主 |
發表於 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解決。 
 
 |   
 
 
 
 |