k-Shape

Рост числа и повсеместность временных данных в различных дисциплинах вызвали значительный интерес к анализу и майнингу временных рядов. Кластеризация является одним из самых популярных методов анализа данных не только благодаря своей исследовательской способности, но и как этап предобработки или подпрограмма для других методов. В этой статье мы представляем k-Shape, новый алгоритм кластеризации временных рядов. k-Shape опирается на масштабируемую итеративную процедуру уточнения, которая создаёт однородные и хорошо разделённые кластеры. В качестве меры расстояния k-Shape использует нормализованную версию меры взаимной корреляции, чтобы учитывать формы временных рядов при их сравнении. Исходя из свойств этой меры расстояния, мы разработали метод вычисления центроидов кластеров, которые используются на каждой итерации для обновления принадлежности временных рядов к кластерам. Чтобы продемонстрировать устойчивость k-Shape, мы провели обширную экспериментальную оценку нашего подхода по сравнению с методами партиционной, иерархической и спектральной кластеризации с комбинациями наиболее конкурентоспособных мер расстояния. k-Shape превосходит все масштабируемые подходы по точности. Более того, k-Shape также превосходит все несмасштабируемые (и потому непрактичные) комбинации, за исключением одного случая, достигающего схожих результатов по точности. Однако, в отличие от k-Shape, эта комбинация требует настройки своей меры расстояния и работает на два порядка величины медленнее, чем k-Shape. В целом k-Shape выступает как предметно-независимый, высокоточный и высокоэффективный подход к кластеризации временных рядов с широким спектром применений.