Thuật toán nào sử dụng để phân đoạn chuỗi số thành n tập con, để giảm thiểu độ lệch chuẩn của tổng số trong mỗi tập hợp con

Question

Tôi đang tìm một thuật toán để phân đoạn chuỗi số dương thành n chuỗi, chẳng hạn rằng độ lệch chuẩn của tổng các số trong mỗi tập con được giảm thiểu.

Trật tự của các số trong mỗi dãy con cần phải được giống như thứ tự trong chuỗi gốc

Ví dụ:

Giả sử tôi có một dãy {1,1,1,1,1 , 1,10,1} mà tôi muốn phân đoạn thành 2 chuỗi.
Tôi tin rằng giải pháp tối ưu sẽ là {1,1,1,1,1,1}, {10,1}.

Tổng số lần thứ 1 là 6, tổng của hậu tố thứ 2 là 11
Độ lệch chuẩn của hai số là ~ 3,5, mà tôi tin là thấp nhất có thể.

Giả sử tôi có một chuỗi {4,1,1,1,1,6} mà tôi muốn phân đoạn thành 3 chuỗi.
Tôi tin rằng giải pháp tối ưu sẽ là {4}, {1,1,1,1}, {6}
Tổng số các dãy là 4, 4 và 6.
Độ lệch chuẩn của 3 số là ~ 1.15, mà tôi tin là thấp nhất có thể.

Thuật toán tốt nhất tôi có thể tìm ra là tìm tổng tích lũy của mỗi số trong chuỗi và phân đoạn chuỗi tại mỗi khoảng [totalSum/numSubsequences]. Ví dụ, với chuỗi {4,1,1,1,1,6}, tổng tích lũy của các số của mỗi chuỗi là {4,5,6,7,8,14}. Tổng số của tất cả các số trong dãy là 14, vì vậy, cho rằng tôi muốn 3 subsequences, tôi nên phân đoạn trình tự khi tổng số đạt 14/3 = 4.66 và 2 * 14/3 = 9.333333.

Tuy nhiên, không có vị trí thực tế trong chuỗi nơi tổng tích lũy bằng 4.66 - tổng tích lũy đầu tiên là 4 và tổng tích lũy tiếp theo là 5. Vì vậy, tôi nên làm tròn hoặc tôi nên làm tròn? Trong trường hợp này, làm tròn xuống đến 4 cho giải pháp tối ưu, nhưng đó không phải lúc nào cũng như vậy. Điều tốt nhất tôi có thể nghĩ đến là thử mọi kết hợp làm tròn lên và xuống, nhưng điều đó dẫn đến sự phức tạp của O (2^numSubsequences).

Điều này có vẻ là loại điều sẽ có một thuật toán từ trước để áp dụng, tuy nhiên Googling của tôi đã không thành công với tôi. Tôi biết về số Partition Problem, NP-complete, nhưng giao dịch với các bộ không theo thứ tự và không phải là chuỗi được sắp xếp.

Mọi trợ giúp sẽ được đánh giá cao.

Answer 1

Giả sử độ dài của chuỗi gốc là L và số lượng các dãy là N.

Bạn có thể simplify the expression for standard deviation để có được sqrt(E[X^2] - E[X]^2), nơi E biểu thị mong đợi/trung bình và X biểu thị biến ngẫu nhiên của bạn - trong trường hợp của bạn, tổng các subsequences. (Công thức tương tự áp dụng cho "độ lệch chuẩn mẫu".) Lưu ý rằng E[X] không phụ thuộc vào cách bạn tách chuỗi của bạn, vì nó sẽ luôn là tổng số chia cho N. Vì vậy, chúng tôi chỉ muốn giảm thiểu E[X^2] hoặc tương đương, tổng của X^2 (chúng khác nhau theo hệ số là N theo định nghĩa trung bình).

Tại thời điểm này, chúng ta có thể thấy rằng vấn đề này có thể được giải quyết bằng lập trình động.Hãy f(i,j), cho i0-M và j1-N, là tổng tối thiểu bình phương của số tiền của subsequences từ sự chia rẽ của i yếu tố đầu tiên của chuỗi của bạn vào j subsequences. Sau đó, chúng tôi thấy rằng f(i,j) có thể được tính theo tất cả các f(i',j') với i' <= i và j < j'. Cụ thể hơn, nếu chuỗi của bạn được lập chỉ mục từ a[k]0 để M-1:

f(i,1) = sum(a[k] for 0 <= k < i)^2 
f(i,j) = minimum of f(l,j-1)+sum(a[k] for l < k < i)^2 for l from 0 to i 

Sau khi giảm thiểu f(N,L), bạn có thể sử dụng kỹ thuật lập trình động tiêu chuẩn để phục hồi các chia rẽ. Cụ thể, bạn có thể lưu trữ l để giảm thiểu số f(i,j).

Thời gian chạy của giải pháp này là O(L^2 N) vì bạn tính O(L N) giá trị khác nhau của f và minimum kết thúc O(L) giá trị khác nhau của l.

Dưới đây là một việc thực hiện đơn giản trong Perl:

#!/usr/bin/perl 

use strict; 
use warnings; 

local $\ = $/; 
print join ", ", map {"@$_"} best(2, qw(1 1 1 1 1 1 10 1)); 
# prints "1 1 1 1 1 1, 10 1" 

print join ", ", map {"@$_"} best(3, qw(4 1 1 1 1 6)); 
# prints "4, 1 1 1 1, 6" 

sub best { 
    my($N, @a) = @_; 

    my(@f, @g, $i, $j, $k, $sum); 

    # DP base case 
    $sum = 0; 
    $f[0][1] = $g[0][1] = 0; 
    for $i (1 .. @a) { 
     $sum += $a[$i-1]; 
     $f[$i][1] = $sum * $sum; 
     $g[$i][1] = 0; 
    } 

    # DP recurrence 
    for $j (2 .. $N) { 
     $f[0][$j] = $g[0][$j] = 0; 
     for $i (1 .. @a) { 
      $sum = 0; 
      $f[$i][$j] = $f[$i][$j-1]; 
      $g[$i][$j] = $i; 
      for $k (reverse 0 .. $i-1) { 
       $sum += $a[$k]; 
       if($f[$i][$j] > $f[$k][$j-1] + $sum * $sum) { 
        $f[$i][$j] = $f[$k][$j-1] + $sum * $sum; 
        $g[$i][$j] = $k; 
       } 
      } 
     } 
    } 

    # Extract best expansion 
    my(@result); 
    $i = @a; $j = $N; 

    while($j) { 
     $k = $g[$i][$j]; 
     unshift @result, [@a[$k .. $i-1]]; 
     $i = $k; 
     $j--; 
    } 

    return @result; 
} 

Answer 2

Một ý tưởng đến với tâm trí của tôi là sử dụng thuật toán tìm kiếm A *.

Thông tin thêm về rằng:

http://en.wikipedia.org/wiki/A*_search_algorithm 

Tốt cuốn sách để đọc về điều đó:

Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig 

Một số điều bạn có thể sử dụng cho A *:

• Nhà nước ban đầu: Tách chuỗi thành n bằng nhau (nhiều nhất có thể) sau số
• Tiếp theo S tate: Đối với mỗi tập hợp con, hãy thêm số bên trái hoặc phải (số cuối của tập con i-1 (nếu i! = 0) hoặc số đầu tiên của tập con i + 1 (nếu i! = n)) vào nó (để tạo tất cả các nút giảm dần của nút trạng thái hiện tại)
• Heuristic: Giá trị tối ưu sẽ là giá trị trung bình của tất cả các giá trị. Có thể chấp nhận để nó có thể được sử dụng với A *.

Không chắc chắn sẽ thực sự giúp bạn giải quyết vấn đề của bạn, vì tôi chưa giải quyết được vấn đề này, nhưng tôi nghĩ nó có thể hoạt động khá tốt. Nó cũng có thể không phải là giải pháp phức tạp nhất cho vấn đề cụ thể này, nhưng nó chắc chắn là tốt hơn so với bất kỳ phương pháp "thử tất cả các kết hợp" nào. Nó cũng là âm thanh và hoàn chỉnh (bởi vì các heuristic chấp nhận được).

Nếu bạn có thêm câu hỏi về yêu cầu này và tôi sẽ cố gắng hết sức để trợ giúp bạn.

Answer 3

Tôi nghĩ rằng bạn có nghĩa là chia thành các phần liền kề nhau, hoặc nói cách khác là tìm những nơi n-1 để cắt chuỗi thành từng phần. (Nếu bạn thực sự muốn cho phép các chuỗi xen kẽ tạo chuỗi chính, bạn có thể sắp xếp chuỗi, giải quyết vấn đề đoạn, và sau đó theo dõi các số riêng lẻ đến từ đâu để cung cấp các chuỗi xen kẽ).

Tôi nghĩ bạn có thể giải quyết điều này theo thời gian tỷ lệ thuận với n lần độ dài chuỗi sử dụng lập trình động. Làm việc từ trái sang phải để điền vào các mảng bestCost [i] [j] và lastCut [i] [j], trong đó i chạy dọc theo trình tự và j chạy từ 0 đến n-1. bestCost [i] [j] là chi phí của cách tốt nhất để cắt chuỗi từ 0 đến i thành khối j. lastCut [i] [j] là vị trí của vết cắt gần đây nhất cho vết cắt tạo ra bestCost [i] [j]. bestCost [i + 1] [j] = độ lệch min_k std (i + 1 đến k) + bestCost [k - 1] [j - 1]. và sau đó lastCut [i + 1] [j] = k. Cuối cùng, bạn tính toán chi phí của câu trả lời tốt nhất cho n vết cắt theo cách tương tự và sau đó sử dụng lastCut [] [] để theo dõi đường đi của bạn trở lại để tìm các vết cắt khác.

Answer 4

Tôi đồng ý rằng lập trình năng động có thể là phương pháp tốt nhất - một kỹ thuật mà tôi sẽ loại trừ là tối ưu hóa phi tuyến tính. Bạn có một hàm mục tiêu phi tuyến tính cho dù bạn đang giảm thiểu căn bậc hai hay chỉ là tổng của các khác biệt bình phương. Bạn cũng có một biến số nguyên như là một phần của bộ hạn chế của bạn - gán các thành viên cho các bộ đòi hỏi một số biến số nguyên bất kể công thức của bạn. Một tối ưu hóa phi tuyến tính với các biến số nguyên thường rất khó nếu không thể giải quyết tối ưu. Nếu bạn chỉ cần một giải pháp gần đúng, một thuật toán di truyền có thể là một cách tiếp cận tốt, nơi chuỗi di truyền là một đại diện cho việc gán một thành viên cho một tập hợp.

Theo như làm tất cả điều này trong chưa đầy một giây .... Chúc bạn may mắn!