Как я могу выполнить кластеризацию K-средних на данных временных рядов?

Question

Как я могу сделать K-средство кластеризации данных временных рядов?Я понимаю, как это работает, когда входные данные представляют собой набор точек, но я не знаю, как кластеризовать временной ряд с 1XM, где M - длина данных.В частности, я не уверен, как обновить среднее значение кластера для данных временных рядов.

У меня есть набор помеченных временных рядов, и я хочу использовать алгоритм K-средних, чтобы проверить,вернется подобный ярлык или нет.Моя X-матрица будет NXM, где N - число временных рядов, а M - длина данных, как указано выше.

Кто-нибудь знает, как это сделать?Например, как я могу изменить этот код MATLAB для k-средних , чтобы он работал для данных временных рядов?Кроме того, я хотел бы иметь возможность использовать различные метрики расстояния помимо евклидова расстояния.

Чтобы лучше проиллюстрировать мои сомнения, вот код, который я изменил для данных временного ряда:

---

% 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

Временные ряды обычно бывают многомерными. И вам нужна специализированная функция расстояния, чтобы сравнить их по сходству. Кроме того, могут быть выбросы.

k-means предназначено для пространств малых размеров с (значимым) евклидовым расстоянием. Он не очень устойчив к выбросам, так как придает им вес в квадрате.

Мне не кажется хорошей идеей использовать k-means для данных временных рядов. Попробуйте изучить более современные и надежные алгоритмы кластеризации. Многие из них позволят вам использовать функции произвольного расстояния, включая расстояния временного ряда, такие как DTW.

Answer 2

Вероятно, уже слишком поздно для ответа, но:

• k-средства могут использоваться для кластеризации продольных данных
• Анон-Мусс прав, Расстояние DWT - это путь для временных рядов

Методы, описанные выше, используют R. Вы найдете другие методы, посмотрев, например, " Итеративная инкрементная кластеризациявременного ряда".

Answer 3

Недавно я столкнулся с пакетом kml R, который утверждает, что реализует кластеризацию k-средних для продольных данных.Я сам не пробовал.

Кроме того, Кластеризация временных рядов - десятилетний обзор статьи С. Агабозорги, А. С. Ширхоршиди ​​и Т. Ин Ва, может быть полезным для васиз альтернатив.Еще одна хорошая статья, хотя и несколько устаревшая, - Кластеризация данных временных рядов - опрос , проведенный Т. Уорреном Ляо.

Answer 4

Если вы действительно хотите использовать кластеризацию, то в зависимости от вашего приложения вы можете сгенерировать низкоразмерный вектор объектов для каждого временного ряда. Например, используйте среднее значение временного ряда, стандартное отклонение, доминирующую частоту от преобразования Фурье и т. Д. Это будет подходящим для использования с k-средних, но даст ли он полезные результаты, зависит от вашего конкретного приложения и содержания вашего времени. серия.

Answer 5

Я тоже не думаю, что k-means - правильный путь для этого. Как сказал @ Anony-Mousse, вы можете использовать DTW . На самом деле, у меня была такая же проблема для одного из моих проектов, и я написал свой собственный класс для этого на Python. Логика есть;

1. Создайте все комбинации кластеров. k для количества кластеров и n для количества серий. Количество возвращенных предметов должно быть n! / k! / (n-k)!. Это были бы что-то вроде потенциальных центров.
2. Для каждой серии рассчитайте расстояния для каждого центра в каждой группе кластеров и присвойте ему минимальное значение.
3. Для каждой группы кластеров рассчитайте общее расстояние внутри отдельных кластеров.
4. Выберите минимум.

И, реализация Python здесь , если вам интересно.