Tôi làm cách nào để thực hiện phân cụm K trên dữ liệu chuỗi thời gian?

Question

Tôi làm cách nào để phân cụm dữ liệu chuỗi thời gian K? Tôi hiểu cách hoạt động này khi dữ liệu đầu vào là một tập hợp các điểm, nhưng tôi không biết cách phân cụm chuỗi thời gian với 1XM, trong đó M là độ dài dữ liệu. Đặc biệt, tôi không chắc chắn làm thế nào để cập nhật trung bình của cụm cho dữ liệu chuỗi thời gian.

Tôi có tập hợp chuỗi thời gian được gắn nhãn và tôi muốn sử dụng thuật toán K-means để kiểm tra xem tôi có nhận lại nhãn tương tự hay không. Ma trận X của tôi sẽ là N X M, trong đó N là số chuỗi thời gian và M là chiều dài dữ liệu như đã đề cập ở trên.

Có ai biết cách thực hiện việc này không? Ví dụ, làm thế nào tôi có thể sửa đổi this k-means MATLAB code để nó sẽ làm việc cho dữ liệu chuỗi thời gian? Ngoài ra, tôi muốn có thể sử dụng các số liệu khoảng cách khác nhau ngoài khoảng cách Euclide.

Để minh hoạ rõ hơn những nghi ngờ của tôi, đây là đoạn code tôi sửa đổi cho loạt dữ liệu thời gian:

---

% Check if second input is centroids 
if ~isscalar(k) 
    c=k; 
    k=size(c,1); 
else 
    c=X(ceil(rand(k,1)*n),:); % assign centroid randomly at start 
end 

% allocating variables 
g0=ones(n,1); 
gIdx=zeros(n,1); 
D=zeros(n,k); 

% Main loop converge if previous partition is the same as current 
while any(g0~=gIdx) 
%  disp(sum(g0~=gIdx)) 
    g0=gIdx; 
    % Loop for each centroid 
    for t=1:k 
     % d=zeros(n,1); 
     % Loop for each dimension 
     for s=1:n 
      D(s,t) = sqrt(sum((X(s,:)-c(t,:)).^2)); 
     end 
    end 
    % Partition data to closest centroids 
    [z,gIdx]=min(D,[],2); 
    % Update centroids using means of partitions 
    for t=1:k 

     % Is this how we calculate new mean of the time series? 
     c(t,:)=mean(X(gIdx==t,:)); 

    end 
end 

Answer 1

Time loạt thường chiều cao. Và bạn cần chức năng khoảng cách chuyên biệt để so sánh chúng với sự giống nhau. Ngoài ra, có thể có các ngoại lệ.

k-means được thiết kế cho không gian có chiều thấp với khoảng cách euclide (có ý nghĩa). Nó không phải là rất mạnh mẽ đối với các ngoại lệ, vì nó đặt trọng lượng bình phương trên chúng.

Không có ý tưởng hay đối với tôi khi sử dụng k-means trên dữ liệu chuỗi thời gian. Hãy thử xem xét các thuật toán phân cụm hiện đại, mạnh mẽ hơn. Nhiều người sẽ cho phép bạn sử dụng các hàm khoảng cách tùy ý, bao gồm khoảng cách chuỗi thời gian như DTW.

Answer 2

Đây có thể là quá muộn cho một câu trả lời, nhưng:

• k-means có thể được sử dụng để cluster longitudinal data
• Anony-Mousse là đúng, DWT distance is the way to go for time series

Các phương pháp trên sử dụng R. Bạn sẽ tìm thấy nhiều phương pháp hơn bằng cách tìm kiếm, ví dụ: "Iterative Incremental Clustering of Time Series".

Answer 3

Nếu bạn thực sự muốn sử dụng phân cụm, thì phụ thuộc vào ứng dụng của bạn, bạn có thể tạo ra một vectơ tính năng chiều thấp cho mỗi chuỗi thời gian. Ví dụ, sử dụng chuỗi thời gian có nghĩa là độ lệch chuẩn, tần số chiếm ưu thế từ biến đổi Fourier, v.v. Điều này phù hợp để sử dụng với k-means, nhưng liệu nó có mang lại kết quả hữu ích hay không tùy thuộc vào ứng dụng cụ thể của bạn và nội dung thời gian của bạn loạt.

Answer 4

Gần đây tôi đã xem qua gói kml R xác nhận việc triển khai cụm từ k-means cho dữ liệu theo chiều dọc. Tôi đã không tự mình thử.

Ngoài ra giấy Time-series clustering - A decade review của S. Aghabozorgi, A. S. Shirkhorshidi và T. Ying Wah có thể hữu ích cho bạn để tìm kiếm các giải pháp thay thế. Một giấy đẹp khác mặc dù có phần ngày là Clustering of time series data-a survey bởi T. Warren Liao.