🌟

SSA (Singular Spectrum Analysis) と周期的構造への分解

に公開

話すこと

SSA (Singular Spectrum Analysis) を使うと周期関数であり実数値を取る入力信号を複数の周期的信号に分解できます。
本記事では SSA の入出力、求め方、周期的なものに分解できる理由を述べます。
NumPy を使った SSA の実装と具体例を最後にまとめます。

話さないこと

  • 入力が周期関数ではない時の SSA
  • 特異値分解 (SVD)

実施例

SSA (Wikipedia) の画像のような信号を作り SSA を実行した結果です。周期的な信号で分解されていることが分かります。

ssa demo

SSA の処理方法

データ作成: Hankel Matrix

N 個のデータを持つ入力信号 x_n (n=0, 1, \cdots N-1) とします。入力データから行数 L とする行列 X を作ります。

\begin{align*} X = \begin{pmatrix} x_0 & x_1 & x_2 & \cdots & x_{N-L} \\ x_1 & x_2 & x_3 & \cdots & x_{N-L+1} \\ & & & \cdots \\ x_{L-1} & x_{L} & x_{L+1} & \cdots & x_{N-1} \end{pmatrix} \end{align*}

各要素は右隣あるいは下に行くとインデックスが 1 つ増えます。このような行列を Hankel Matrix と呼びます。SSA ではこの行列を使います。

特異値分解による SSA

入力データを Hankel Matrix 化した行列 X を特異値分解します。すなわち、以下のように表現されます。

X = U \Sigma V^{T}

行列 X のサイズを 行数 L, 列数 K = N - L + 1 とします。特異値分解した行列のサイズは U: (L \times L), \Sigma: (L \times K), V^{T}: (K \times K) になります。
行列 U には (x_0, x_1, \cdots) のように並べたベクトルの構造が入っており、行列 V はその構造の時間ごとの係数と考えられます。今回の場合、行列 U の構成要素に sin 関数のような周期的な信号があると予想できます。

低ランク近似による X の近似

特異値を大きい順から r 個選び、対応する U, V を使い行列 X を近似します。これを X_r とし、U_r, \Sigma_r, V_r を r 個だけ抜き取った行列とします。

\begin{align*} X_r &= U_r \Sigma_r V_r^T \\ &\sim X \end{align*}

残差 X - X_r (r+1 個目からの特異値を使い再構成したもの) はノイズのような主たる要素でないものになります。

周期的な信号で分解される理由

周期関数であるデータ列 x_n が SSA により複数の周期的な信号で分解されることを説明します。
前提として x_n は周期関数から得られた信号列であり、フーリエ級数展開で表せるとします。

時間埋め込みが周期性を作る

簡単のため x_n を \sin \omega t とします。(インデックス n を時刻 t とすれば x_n = \sin \omega n になります)
Hankel Matrix にした時系列の情報が埋め込まれたベクトルを考えます。これを \bm{x} = (x_t, x_{t+1}, \cdots, x_{t + L-1})^T とします。この要素 x_{t+k} は加法定理を使うと次式になります。

x_{t+k} = \sin \omega t \cos \omega k + \cos \omega t \sin \omega k

k = 0, 1, \cdots L-1 であり、 \bm{x} を書き直すと、

\bm{x} = \sin \omega t \begin{pmatrix} \cos 0\omega \\ \cos 1\omega\\ \vdots \end{pmatrix} + \cos \omega t \begin{pmatrix} \sin 0\omega \\ \sin 1\omega\\ \vdots \end{pmatrix}

\cos, \sin で作られるベクトルを \bm{a}, \bm{b} とすると、\bm{x} = \sin \omega t \ \bm{a} + \cos \omega t \ \bm{b} になります。
\bm{x} は Hankel Matrix のある列ベクトルです。他の列ベクトルも同様に \bm{x}^{\prime} = \sin \omega t^{\prime} \ \bm{a} + \cos \omega t^{\prime} \ \bm{b} と表現でき、ベクトル \bm{a}, \bm{b} は変わりません。
特異値分解の結果を考えると、U はベクトル \bm{a}, \bm{b} が主要な列ベクトルであり対応する V は (\sin \omega t_0, \sin \omega t_1, \cdots), \ (\cos \omega t_0, \cos \omega t_1, \cdots) で作られると考えられます。このように時間埋め込みされたベクトルから周期的な構造が生まれることが分かります。

NumPy 実装

SSA クラスを定義し、Hankel Matrix 化と特異値分解による SSA 処理と特異値ごとの信号の再構成処理を行います。

全体像

以下のように SSA クラスを定義します。

class SSA:
    def __init__(self, window_length: int) -> None:
        # 窓幅 L
        self.window_length = int(window_length)
        # SSA (SVD) の結果
        self.u: NDArray[np.floating] | None = None
        self.s: NDArray[np.floating] | None = None
        self.vt: NDArray[np.floating] | None = None
        # SSA に使う Hankel Matrix
        self._hankel_matrix: NDArray[np.floating] | None = None

    def _hankel(
            self, series: NDArray[np.floating], window_length: int) -> NDArray[np.floating]:
        """Hankel Matrix 作成

        Args:
            series (NDArray[np.floating]): 入力1次元データ
            window_length (int): 窓幅 L

        Returns:
            NDArray[np.floating]: Hankel matrix with shape (window_length, column_count).
        """
        series_length = len(series)
        column_count = series_length - window_length + 1
        if window_length <= 0 or column_count <= 0:
            raise ValueError("window_length must satisfy 1 <= window_length <= len(series)")
        return np.column_stack([series[i:i + window_length] for i in range(column_count)])

    def _diagonal_averaging(self, matrix: NDArray[np.floating]) -> NDArray[np.floating]:
        """Hankel Matrix から 1次元信号に復元する

        Args:
            matrix: Hankel Matrix

        Returns:
            NDArray[np.floating]: 復元された 1次元信号
        """
        row_count, column_count = matrix.shape
        series_length = row_count + column_count - 1
        diagonal_indices = np.add.outer(
            np.arange(row_count, dtype=int),
            np.arange(column_count, dtype=int),
        ).ravel()
        flattened = matrix.ravel()
        values = np.bincount(diagonal_indices, weights=flattened, minlength=series_length)
        weights = np.bincount(diagonal_indices, minlength=series_length)
        return values / weights

    def fit(self, series: NDArray[np.floating]) -> "SSA":
        """SSA 処理実行

        Args:
            series (NDArray[np.floating]): Input 1D series.

        Returns:
            Fitted SSA instance.
        """
        self._hankel_matrix = self._hankel(series, self.window_length)
        self.u, self.s, self.vt = np.linalg.svd(self._hankel_matrix, full_matrices=False)
        return self

    def reconstruct(self, indices: int|Sequence[int]|NDArray[np.integer]) -> NDArray[np.floating]:
        """特異値のインデックスを指定し信号を復元する

        Args:
            indices: 特異値のインデックス (特異値が大きい順に並ぶ)

        Returns:
            NDArray[np.floating]: 復元された信号
        """
        if self.u is None or self.s is None or self.vt is None:
            raise ValueError("Call fit(x) before reconstruct().")
        if isinstance(indices, int):
            indices = [indices]
        # 特異値のインデックスから U.S.VT を計算する
        component_indices = np.asarray(indices, dtype=int)
        reconstructed_matrix = (
            self.u[:, component_indices] * self.s[component_indices]
        ) @ self.vt[component_indices]
        return self._diagonal_averaging(reconstructed_matrix)

    def get_svd(self) -> tuple[NDArray[np.floating], NDArray[np.floating], NDArray[np.floating]]:
        """SVD の結果を取得する

        Returns:
            tuple[NDArray[np.floating], ...]: Tuple of (U, S, VT) from the SVD.
        """
        if self.u is None or self.s is None or self.vt is None:
            raise ValueError("Call fit(x) before get_svd().")
        return self.u, self.s, self.vt

    def calculate_cumulative_contribution(self) -> NDArray[np.floating]:
        """寄与度の累積分布を求める

        Returns:
            NDArray[np.floating]: 累積寄与度
        """
        if self.s is None:
            raise ValueError("Call fit(x) before calculate_cumulative_contribution().")
        # 寄与度 (特異値の 2乗) の累積分布を求める
        singular_values_squared = self.s**2
        total_variance = np.sum(singular_values_squared)
        cumulative_contribution = np.cumsum(singular_values_squared) / total_variance
        return cumulative_contribution

各処理について

Hankel Matrix 関係

Hankel Matrix は前述の通り、次式の形になります。入力データと行数 L を決めると列数が決まります。L 個のデータを並べたものが Hankel Matrix になった X になります。実装では _hankel() 関数です。

\begin{align*} X = \begin{pmatrix} x_0 & x_1 & x_2 & \cdots & x_{N-L} \\ x_1 & x_2 & x_3 & \cdots & x_{N-L+1} \\ & & & \cdots \\ x_{L-1} & x_{L} & x_{L+1} & \cdots & x_{N-1} \end{pmatrix} \end{align*}

SSA では特異値分解されたものから信号を再構成します。結果は X と同サイズの行列であり 1次元信号ではありません。再構成された X_r から 1次元信号にする関数が reconstruct() 関数と内部で呼ばれる _diagonal_averaging() 関数です。1次元信号で各要素に対して X (X_r) での登場回数と対応する要素から平均を求めます。
例として以下の小さい Hankel Matrix を用意します。これは入力データから作られたものです。x_0, x_3 は 1回登場し、x_1, x_2 は 2回現れます。

\begin{align*} X = \begin{pmatrix} x_0 & x_1 & x_2 \\ x_1 & x_2 & x_3 \end{pmatrix} \end{align*}

再構成された行列 A は以下になります。これをもとに入力信号 x_n を復元します。

\begin{align*} A = \begin{pmatrix} a_{0, 0} & a_{0, 1} & a_{0, 2} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} \end{pmatrix} \end{align*}
\hat{\bm{x}} = (a_{0,0}, \frac{(a_{0,1} + a_{1,0})}{2}, \frac{(a_{0,2} + a_{1,1})}{2}, a_{1,2})

SSA 処理

fit() 関数で SSA を実行します。以下のように入力データを Hankel Matrix にし特異値分解を行います。行列 U, \Sigma, V^T を get_svd() 関数で取り出します。

class SSA:
    def fit(self, series: NDArray[np.floating]) -> "SSA":
        self._hankel_matrix = self._hankel(series, self.window_length)
        self.u, self.s, self.vt = np.linalg.svd(self._hankel_matrix, full_matrices=False)
        return self

特異値から寄与度を計算

全 M 個の特異値に関する寄与度の累積分布を求めます。累積分布は次のように定義されます。
calculate_cumulative_contribution() で実装されます。例えば累積分布が 0.99 を超えるところまでを低ランク近似に採用する、などの利用があります。

\begin{align*} \text{total} &= \sum_{i=1}^{M} \sigma_i^2 \\ \text{Cumulative} (r) &= \frac{\sum_{i=1}^{r} \sigma_i^2}{\text{total}} \end{align*}

具体例

入力データ

3種の周期的な信号とノイズを加えたものを例にします。トレンドとしてゆっくりと変化するもの、振幅が変化する 2つの周期的な信号を作ります。サンプリング周波数を 100 [Hz] とした 10秒分のデータです。

  • 0.2 \cos (2\pi \cdot 0.1 t)
  • 0.05 (1 + 0.2 | t - 5|) \sin(2\pi \cdot 1 t) (振幅はデータ中央で最小になる)
  • 0.04 (1 - 0.2 | t - 5|) \cos(2\pi \cdot 2 t) (振幅はデータ中央で最大になる)
def generate_data() -> tuple[NDArray[np.float64], NDArray[np.float64], list[NDArray[np.float64]]]:
    """Generate sample displacement data."""
    # trend: parabola
    fs = 100.0  # [Hz]
    duration = 10.0  # [s]
    times = np.arange(0, duration, 1 / fs)
    trend = 0.2 * np.sin(2 * np.pi * 0.1 * times + np.pi / 2)
    # frequency components
    wave1 = 0.05 * np.sin(2 * np.pi * 1.0 * times)  # 1.0 Hz
    wave1 *= 1 + 0.2 * np.abs(times - duration / 2)  # amplitude modulation
    wave2 = 0.04 * np.sin(2 * np.pi * 2.0 * times + np.pi / 2)  # 2.0 Hz
    wave2 *= 1 - 0.2 * np.abs(times - duration / 2)  # amplitude modulation
    # noise
    noise = 0.005 * np.random.normal(size=len(times))
    result = trend + wave1 + wave2 + noise
    return times, result, [trend, wave1, wave2, noise]

入力データを図示します。灰色が入力データであり、青線がトレンド (0.1 [Hz])、オレンジ線が 1 [Hz]、緑線が 2 [Hz] の信号です。入力データはノイズも付加されています。

example

結果

窓幅 L = 150 とし SSA を実行します。3つの周期的な信号で構成されることから、6個の大きい特異値があると予想されます。上位 6個の特異値を使い信号を再構成した結果は下図になります。紫線が再構成した信号です。

# generate data
times, data, components = generate_data()
# apply SSA
window_length = 150
ssa_model = SSA(window_length=window_length)
ssa_model.fit(data)
# reconstruction
reconstructed = ssa_model.reconstruct([0, 1, 2, 3, 4, 5])

reconstruction

次に上記で使用した特異値を 2個ずつに分けて信号を再構成します。トレンド, 1 [Hz] の信号, 2 [Hz] の信号と予想されるため、それぞれの元信号と比較します。

component reconstruction

最後に特異値分解の結果である行列 U の列ベクトルを眺めます。節: 周期的な信号で分解される理由 で述べたように周期的な信号であると考えられます。6個の列ベクトルを表示したものは以下です。
緑線と赤線を見ると 1 [Hz] の基本的な信号、紫線と茶線を見ると 2 [Hz] の基本的な信号に見えます。

u vectors

まとめ

SSA (Singular Spectrum Analysis) の処理と実装、SSA が周期的な信号に分解する説明、擬似的に生成した信号による再構成の例を挙げました。

参考文献

以下を参考にしました。

Discussion