Detekcja i segmentacja strumieni danych

Wprowadzenie

• Cel segmentacji: podział strumienia danych na bloki o podobnych właściwościach
• Zastosowania:
  • Przetwarzanie wstępne w rozpoznawaniu (np. wykrywanie awarii)
  • Analiza trendów w szeregach czasowych
  • Dyskretyzacja danych pomiarowych
  • Śledzenie systemów dynamicznych/niestacjonarnych (wykrywanie zmian w sygnałach)
• Efekt segmentacji: zestaw N segmentów o ustalonej długości

  y(1), ..., y(k₁) | y(k₁+1), ..., y(k₂) | ... | y(kₙ+1), ..., y(kₙ)

  gdzie s₁ < s₂ < ... < sₙ, int(sᵢ) ∩ int(sⱼ) = ∅, S = (s₁, s₂, ..., sₙ)
• Typowe błędy:
  • Zdarzenie na granicy segmentu
  • Nieodpowiedni rozmiar okna
  • Nieprawidłowe położenie okna

Okna analizy

• Segmenty: stała lub zmienna szerokość
• Analiza w oknach przesuwanych w czasie (z zakładką lub bez)
• Typy okien:
  • Prostokątne (domyślne)
  • Hamminga
  • Hanna
  • Blackmana
  • Kaisera

Metody segmentacji

1. Bazujące na klasyfikacji:
   • Wykorzystują algorytmy klasyfikacji
   • Etapy:
     1. Klasyfikacja w każdym segmencie
     2. Łączenie segmentów
   • Wady: wymagają dużych, etykietowanych danych
2. Bazujące na grupowaniu:
   • Nie wymagają zbiorów uczących
   • Przydatne przy wzorcach:
     • Częste (powtarzające się zdarzenia)
     • Rzadkie (anomalie)
   • Analiza cech statystycznych
   • Rodzaje:
     • Partycjonowanie (np. k-średnich)
     • Hierarchiczne:
       • Agregujące (bottom-up, np. AGNES)
       • Dzielące (top-down, np. DIANA)
     • Gęstościowe
     • Siatkowe
   • Metryki odległości: euklidesowa, Manhattan, maksymalna
3. Detekcja zmian:
   • Wyznaczanie momentów zmian w sygnale
   • Formulacja jako testowanie hipotez:
     • H₀: y(k) = s(k) + v(k), k ∈ [kᵢ, k_{i+1}]
     • H₁: y(k) = v(k), k ∈ [kᵢ, k_{i+1}]
   • Algorytmy:
     • Shewharta: wykrywanie zmian parametru (np. średniej, wariancji)
       • H₀: θ = θ_0
       • H₁: θ = θ_1
     • CUSUM (Cumulative Sum):
       • Śledzenie zmian średniej/odchylenia standardowego
       • Wykrywanie małych, nagłych zmian
       • Zakłada i.i.d. obserwacje poza alarmem

Generowanie cech

1. Operator energetyczny Teagera-Kaisera: tkeo(y(k)) = y^2(k) - y(k+1)y(k-1)
2. Entropia Tsallisa: ent_te(q) = - (1 - Σ p_i^q)/(q-1)
   • q: stopień nieliniowości (dla q=1 równoważna entropii klasycznej)
3. Cechy widmowe:
   • Środek ciężkości widma
   • Płaskość widma
   • Przepływ widma
   • Entropia widma
4. Analiza mel-cepstralna (MFCC):
   • Kroki:
     1. Podział sygnału na ramki (N_frm, L_frm próbek)
     2. Dyskretna transformata Fouriera: Y_DFTi(n) = Σ y_i(l)w(l)exp(-j2π nl/L_frm)
     3. Obliczenie energii w podpasmach: P_i(q) = log(Σ |Y_DFTi(n)|^2 H_q(n))
     4. Filtracja trójkątnymi filtrami (20–40) w skali mel
   • Okno analizy: najczęściej Hamminga
5. Wymiar fraktalny:
   • Miara złożoności sygnału, samopodobieństwa
   • Metody:
     • Higuchiego
     • Katza

Przykład zastosowania

• Sygnały sejsmiczne: segmentacja do wykrywania zdarzeń