Makine Öğrenmesi

k-NN Tabanlı Zaman Serisi Sınıflandırması

Literatürdeki farklı yaklaşımlara genel bir bakış

Zaman serisi analizi, istatistiğin en popüler dallarından biridir. Zaman serileri her yerde bulunur ve birçok alanda kullanımı vardır. Zaman Serisi Sınıflandırması (TSC), veri madenciliği, makine öğrenmesi, sinyal işleme, istatistik vb. gibi geniş bir alanda önemi ile birlikte zorlu bir iştir. Bu karmaşık görevi ele almak için kullanılan en popüler ve basit yöntemlerden biri k-en yakın komşudur (k-NN). k-NN sınıflandırıcı, yeni örnekleri çoğunluk bazında sınıflandırmadan önce eğitim alanına gömmekten oluşan basit sınıflandırma kuralına dayanmaktadır. Nihai sonuç, benzer olmayan veri noktalarını uzakta tutarken benzer veri noktalarının birbirine yakın olmasına neden olur. Basitliğine rağmen, k-NN, önemli ölçüde mesafe veya yakınlık ölçüsünün seçimine bağlı olarak performansıyla rekabet halinde kalır. Literatüre dayalı olarak, Dinamik Zaman Bükülmesine (DTW) dayalı kNN, en popüler ve rekabetçi yaklaşımlar arasında yer almaktadır. Bunun üzerine inşa edilen standart DTW’nin çeşitli varyantları geliştirildi ve performansı daha da iyileştirildi.

TSC sorununu etkin bir şekilde çözmek için literatürde mevcut olan farklı yöntemlerin doğru bir şekilde anlaşılması çok önemlidir. Ek olarak, araştırma açısından bu aynı zamanda mevcut yaklaşımın üzerine inşa edilmesine yardımcı olur ve böylece daha verimli çözümlerin yolunu açar. Bu doğrultuda, bu makale, incelenen bilimsel problem açısından k-NN tabanlı zaman serisi sınıflandırması alanını oluşturan üç bilimsel araştırma makalesine ve çözümün kilit kısımlarını vurgulayarak formüle edilen yaklaşıma genel bir bakış sunmaktadır.

1. Yerel ağırlıklı zaman atlamaları altında büyük bir marjlı zaman serisi en yakın komşu sınıflandırması

Bilimsel Problem: Standart DTW’nin dezavantajlarını ortadan kaldıran ve global bir kısıt çarpıtma modeli öğrenen ve k-NN ile büyük komşuluk marjlarını dikkate alan TSC yaklaşımı.

Yaklaşım: Yerel Ağırlıklı Dinamik Zaman Çarpıtma (LWDTW)

Bu makale, karmaşık zaman serilerinin sınıflandırılmasında problemler yaratarak zaman serilerinin tek tip olarak dağıtıldığını düşünen standart DTW’nin dezavantajını doğaçlama yaparak, yerel ağırlıklı dinamik zaman atlamasını (LWDTW) göz önünde bulunduran TSC için yeni bir yaklaşım sunmaktadır. Standart DTW değişkenleri üzerinde yerel ağırlık vektörlerini kullanan LWDTW, kısıtlı DTW varyantı (performansını artırmak için DTW’ye kısıtlamanın uygulandığı varyant) olarak sınıflandırılır ve sınıflandırma için k-NN sınıflandırıcısı ile birlikte kullanılır. LWDTW, zaman serisi verilerinden yerel ayırt edici özellikleri yakalayarak yerel olarak bilinçli bir ağırlıklı DTW’nin (zaman serisi öğeleri için ağırlıklar) öğrenilmesini içerir. Bunu yaparak, tek biçimli olmayan TSC’ye yönelik küresel kısıtlama çarpıtma modelinin gerekliliğini ve sınırlamasını ortadan kaldırır. Ağırlıkların TSC’de k-NN ile DTW yaklaşımına dahil edilmesi, k-NN süreci üzerinde, komşu zaman dizileri arasındaki benzerlikleri/farklılıkları yakalamaya, zaman dizisi öğelerinin zamansal hizalanmasını sağlamaya, farklı ağırlıklardaki zaman dizisi öğelerinin uygun şekilde ele alınmasına yönelik olumlu bir etkiye sahiptir. LWDTW yaklaşımı, zaman serilerindeki varyanstan etkilenir, daha düşük varyans daha yüksek bir ağırlığı gösterir ve bunun tersi de geçerlidir. Ayrıca k-NN sınıflandırıcısı ile büyük marjlar (geniş mahalleler) göz önüne alındığında daha iyi genelleme performansına sahip çözümler üretmektedir.

2. Pozitif etiketlenmemiş zaman serisi sınıflandırma problemlerinde k-en yakın komşu için durdurma kriterleri üzerine

Bilimsel Problem: Kendi kendine gelişen Pozitif Etiketsiz (PU) öğrenmede erken durma sorununu ortadan kaldıran durdurma kriteri

Yaklaşım: Grafiksel Analiz durdurma kriteri 4 (CBD-GA-SC4) kullanılarak Sınıf Sınırı Açıklaması. SC4, sınıf sınırını artan ve azalan eğrilerin yüksekliği arasındaki maksimum değer olarak tanımlar.

Pozitif Etiketsiz (PU) öğrenme, TSC problemlerinde etiketlenmemiş verilerin etiketlerini öğrenmek için uygun bir çözümdür. Ancak kendi kendini eğiten PU tekniğinde, etiketlenmemiş verilerin (durdurma kriterleri) etiketlenmesinin ne zaman durdurulacağı kararı çok önemlidir. Durdurma kriterlerindeki en gelişmiş yöntemlerin çoğu, erken durdurma ile sonuçlanır, bu da eğitilmiş sınıflandırıcının eksik öğrenilmesine ve nihayetinde muhafazakar bir yaklaşıma neden olur. Bu makale, sınıf sınırını belirlemek için örnekler arasındaki mesafe noktalarının eğilimlerine dayalı grafik analiz tekniklerini kullanarak durdurma kriterleri için Grafik Analizi (CBD-GA) kullanarak Sınıf Sınır Tanımı yaklaşımını formüle etmektedir. Kağıt, sırasıyla Öklid mesafesi ve DTW ile k-NN üzerinde deneysel değerlendirme ile üç grafik eğrinin (artan, azalan, kararlı) farklı kombinasyonlarına dayanan parametresiz, uygun maliyetli durdurma kriterleri (SC1-SC5) ailesini formüle eder. Makale daha sonra, SC4’ün sınıf sınırını, sağlam olan olarak artan ve azalan eğrilerin yüksekliği arasındaki maksimum değer olarak tanımlayan CBD-GA-SC4 yaklaşımını deneysel olarak doğrular. Bu aynı zamanda Öklid ve DTW mesafe ölçümlerini kullanarak k-NN ile rekabete dayalı sonuçlar elde eden son teknoloji ürünü performanstan daha iyi performans gösterir ve böylece erken durmayı önler.

3. Elastik mesafe ölçümleri toplulukları ile zaman serisi sınıflandırması

Bilimsel Problem: TSC problemleri için sınıflandırma doğruluğuna dayalı olarak 11 farklı elastik mesafe sınıflandırıcısı arasında karşılaştırma. Bireysel sınıflandırıcılardan daha iyi performans gösterecek grup sınıflandırıcı formülasyonu

Yaklaşım: Orantılı (PROP) topluluk sınıflandırıcısı.

Bu makale, elastik mesafe ölçülerine dayalı 11 farklı sınıflandırıcının, yani Öklid mesafesi (ED), Türev Zaman Çarpıtma (DTW), Türev DTW, DDTW’nin bir kombinasyonu olan yeni bir Orantılı sınıflandırıcı (PROP) formüle etmektedir. çapraz doğrulamalı (DDTWCV), ağırlıklı DDTW (WDDTW), ağırlıklı DTW (WDTW), Taşı-Spilt-Birleştirme (MSM), çapraz doğrulamalı DTW (DTWCV), Gerçek Ceza ile Düzenleme mesafesi (ERP), En Uzun Ortak Sıra (LCSS) ), zaman alanında TSC için Zaman Çarpıtma Düzenleme mesafesi (TWE). Bu makale, formüle edilmiş hipotezini doğrulamak için 75 TSC veri setinde üç milyondan fazla deneyle en büyük zaman serisi problemleri üzerinde kapsamlı deneyler gerçekleştirir. Bu makale, TSC için 11 elastik mesafe sınıflandırıcısı arasında sınıflandırma doğruluğu açısından önemli bir fark olmadığını deneysel olarak doğrulamakta ve kanıtlamaktadır. Tanımlanan Orantılı (PROP) topluluğu, DTWCV’den (TSC’de kıyaslama olarak kabul edilir) önemli ölçüde daha doğru olduğu deneysel olarak doğrulanmıştır ve yazarın iddia ettiği gibi TSC problemlerinde bunu yapan ilk sınıflandırıcıdır. Makale, doğruluğu, TSC problemleri için algoritmaları değerlendirmek için en önemli ölçüt olarak ve dolayısıyla TSC problemleri için DTWCV yerine Orantılı (PROP) topluluk sınıflandırıcısı şeklinde yeni bir kıyaslama belirlemek için güçlü deneysel doğrulama iddiaları aracılığıyla tanımlamaktadır.

Kaynaklar

Cover, T. and Hart, P., 1967. Nearest neighbor pattern classification. IEEE transactions on information theory13(1), pp.21–27.

Ding, H., Trajcevski, G., Scheuermann, P., Wang, X. and Keogh, E., 2008. Querying and mining of time series data: experimental comparison of representations and distance measures. Proceedings of the VLDB Endowment1(2), pp.1542–1552.

Salzberg, S.L., 1997. On comparing classifiers: Pitfalls to avoid and a recommended approach. Data mining and knowledge discovery1(3), pp.317–328.

Xi, X., Keogh, E., Shelton, C., Wei, L. and Ratanamahatana, C.A., 2006, June. Fast time series classification using numerosity reduction. In Proceedings of the 23rd international conference on Machine learning (pp. 1033–1040).

Yuan, J., Douzal-Chouakria, A., Yazdi, S.V. and Wang, Z., 2019. A large margin time series nearest neighbour classification under locally weighted time warps. Knowledge and Information Systems59(1), pp.117–135.

Berndt, D.J. and Clifford, J., 1994, July. Using dynamic time warping to find patterns in time series. In KDD workshop (Vol. 10, №16, pp. 359–370).

Ding, H., Trajcevski, G., Scheuermann, P., Wang, X. and Keogh, E., 2008. Querying and mining of time series data: experimental comparison of representations and distance measures. Proceedings of the VLDB Endowment1(2), pp.1542–1552.

González, M., Bergmeir, C., Triguero, I., Rodríguez, Y. and Benítez, J.M., 2016. On the stopping criteria for k-nearest neighbor in positive unlabeled time series classification problems. Information Sciences328, pp.42–59.

Lines, J. and Bagnall, A., 2015. Time series classification with ensembles of elastic distance measures. Data Mining and Knowledge Discovery29(3), pp.565–592.

Keogh, E.J. and Pazzani, M.J., 2001, April. Derivative dynamic time warping. In Proceedings of the 2001 SIAM international conference on data mining (pp. 1–11). Society for Industrial and Applied Mathematics.

Jeong, Y.S., Jeong, M.K. and Omitaomu, O.A., 2011. Weighted dynamic time warping for time series classification. Pattern recognition44(9), pp.2231–2240.

Chen, L. and Ng, R., 2004, August. On the marriage of lp-norms and edit distance. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30 (pp. 792–803).

Marteau, P.F., 2008. Time warp edit distance with stiffness adjustment for time series matching. IEEE transactions on pattern analysis and machine intelligence31(2), pp.306–318.

Stefan, A., Athitsos, V. and Das, G., 2012. The move-split-merge metric for time series. IEEE transactions on Knowledge and Data Engineering25(6), pp.1425–1438.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Close