DEIM2022 D34-4(day3 p22)

時間変化する shapelets を学習する時系列分類手法
山口 晃広†

植野

研†

鹿島

久嗣††

† 株式会社東芝 研究開発センター システム AI ラボラトリー 〒 212-8582 川崎市幸区小向東芝町 1†† 京都大学 大学院情報学研究科 知能情報学専攻 〒 606-8501 京都府京都市左京区吉田本町
E-mail: †akihiro5.yamaguchi@toshiba.co.jp
あらまし

IoT の活用として機械学習による時系列インスタンスのクラス分類手法が研究されている．特に近年，分類器を学習しながら shapelets と呼ばれる分類に用いる波形パターンを同時に学習する手法が，分類性能が高く説明性もあるため注目を集めている．本研究では，被験者の慣れ・季節性・機械の劣化などの影響による shapelets の変化を予測する技術を提案する．本提案では，時系列インスタンスとそれらが観測されたタイミングやクラスラベルから，shapelets と分類器だけでなく shapelets の変化を予測する回帰モデルも同時に学習するように数理最適化問題を定式化する．また本定式化から既製の回帰ソルバをブラックボックスとして利用できる解法を導出する．実験では被験者の慣れ・季節性・機械の劣化がある各産業分野への適用事例で有効性を示す．
キーワード

時系列分類, Shapelet, 波形変形
正例（休⽇）

負例‫ق‬਴঩‫ك‬

正例（休⽇）

負例‫ق‬਴঩‫ك‬

1 はじめにIoT の活用に向けて，機械学習による時系列データのクラス
分類手法の研究が進められている．2 クラス分類の場合は，学習時に正または負のクラスラベルが付与された複数の時系列イ

ンスタンスを正例または負例として与えて，テスト時に未知の時系列インスタンスのクラスラベルを予測する問題となる．一般のクラス分類とは異なり時系列分類では，時間軸における順

図1



崌嵛崡崧嵛崡਄੭崧崌嵇嵛崘取得タイミングにより変化する時系列インスタンス（毎日の交通機関の利用者数が季節変化する例）．

序関係や波形パターンの形状が重要であり，時系列データのノイズや波形パターンの出現位置のズレなどを扱える時系列分類

その利用状況は明らかに変化している．そのため，shapelets もに特化した手法が提案されている [1]．

時系列インスタンスを取得したタイミングに従って変化するは

時系列分類手法の中で，時系列分類に有効な複数の波形パずである．しかしながら，従来の shapelets 手法では，古典的な

ターン（shapelets）を発見することで分類器を学習する研究に

時系列分類問題に基づき，時系列インスタンスはその所得タイ

注目が集まっている [2, 3]．これらの shapelets 手法では，分ミングに依存しないことを前提としており，インスタンス取得

類に有効な特徴は長い時系列全体ではなく少数の短い部分時系

タイミングに従って変形する shapelets を扱うことができない．

列に表れるというアイデアに基づく．特長として，学習が終わインスタンス取得タイミングに従って変形する shapelets をればテスト時の分類は高速であり，高い分類性能を達成する．

学習し予測することは，分類性能の向上だけでなく，以下のよ

更に，分類に用いる波形パターンを専門家に提示できるため説うな産業応用において専門家の理解を促進することもできる．

明性がある．特に，医療・インフラ・製造などの産業分野では，専門家は時系列分類に有効な波形パターンに着目して分析する
場合が多いため，専門家に受け入れられやすい．

Shapelets 手法は，学習データから切り出される多数の部分
時系列を探索することで shapelets を発見するアプローチから始まったが [3]，近年 shapelets を任意の波形パターンとして学習する shapelets 学習法が提案されている [2]．このような shapelets 学習法では，確率的勾配降下法（SGD）により

shapelets と分類器の両方を同時に学習する．これにより，計算例 1. 被験者が短期間に一定間隔で同じ試行を繰り返した結果
をセンシングしてデータセットとして収集した場合，被験者の慣れによって時系列インスタンスの形状が試行期間中に変化する [6, 7]．事象関連電位 (ERP) では，脳と刺激の相互作用を理解するための分類問題に加えて短期間の被験者の慣れが同時に重要な問題となる [8, 9, 10]．分類に有効な波形パターンが被験者の慣れによってどのように変形するかを発見できれば，専門家は機械学習の分類結果をより納得して受け入れられる．

量を削減し正解率を向上し [2]，F 値や Area Under the Curve

例 2. 交通機関の利用は季節の影響を受けやすい [11]．図 1 の例

(AUC) などの分類性能を向上する手法も提案された [4, 5]．

のように交通インフラの整備を進めるために休日と平日の利用状

本来，時系列インスタンスはそれを取得したタイミングに依況の違いを調べる場合，分析するデータは日単位の利用状況を表存してその形状を変化させる場合が多い．図 1 の例に示すよう

す時系列インスタンスとなる．休日と平日との違いを表す利用状に，日ごとに交通機関の利用者数を 1 時間間隔で時系列インス況のパターンを発見するだけでなくそれらの季節変化までも発見タンスとして取得した場合，夏から冬への季節の変化に従ってできれば，運用計画や意思決定にそれらの知識を活用できる [12]．





୞৯峘VKDSHOHWとの距離崌嵛崡崧嵛崡਄੭崧崌嵇嵛崘
ૻຎু১ 1R/(76正例୞৯峘VKDSHOHWとの距離୞৯峘VKDSHOHWとの距離઀੧ু১ /(76負例્ඉ૬৑崌嵛崡崧嵛崡਄੭崧崌嵇嵛崘

負例ૻຎু১ 1R/(76崮崡崰崯嵤崧

正例઀੧ু১ /(76৾ಆ崯嵤崧୞৯峘VKDSHOHWとの距離

図2

インスタンス取得タイミング 20 において，提案手法（上段）では shapelets の変形を予測できるため（左），特徴空間でも正例と負例を正しく分離でき分類性能を大幅に向上させる（右）．

例 3. 一般に寿命のある機械は，安定期を過ぎると機械の稼働

LETS と NoLETS のいずれも，図 2(左) の太青線と太橙線で回数に応じて劣化していく [6]．この劣化は，機械に取り付け描いた 2 つの shapelets を学習した．Shapelets は時系列データ

られたセンサによって波形の歪みとして現れることがある．一にベストマッチングした箇所に描かれている．インスタンス取方，機械が稼働している状態や周辺環境をセンサで認識するこ

得タイミングが 20 のとき，提案手法 LETS だけが，上に尖っとは，機械工学などの分野で重要な課題である [13]．専門家は，た波形パターンの高さが徐々に上昇することを学習しその結果機械が稼働している状態を区別できる波形パターンを発見でき

可変 shapelets を正しく予測できていることが分かる．

るだけでなくその波形パターンがどのように劣化していくかを

図 2(右) では，インスタンス取得タイミングが 20 のときにつ発見できれば，効果的・効率的な機械の設計に役立てられる．

いて，各時系列インスタンスを 2 つの shapelets への距離 2 とし本研究では，分類器と shapelets に加えて shapelets の変化を予測する回帰モデルを同時に学習する shapelets 学習法 “LETS”を提案する．LETS では，時系列インスタンスとその取得タイ
ミング，及びクラスラベルが与えられると，学習データに含まれない取得タイミングに対しても，学習した回帰モデルを用いた外挿や内挿により shapelets の変形を予測することができる．
我々の知る限り，時系列インスタンスの取得タイミングに従って変形できる shapelets（可変 shapelets）を扱うのは，本研究が初めてである．以下では，可変 shapelets を予測した場合の効果について簡単な例を用いて説明する．

1. 1 提案するアプローチの有効性を示す例
図 2 の黒線は上に尖った波形周辺を拡大した時系列インスタンスである．上に尖った波形の傾きは負例では正例よりも緩やかに上昇するため，上に尖った波形に着目することで正例と負例を正しく分類できる．しかし，この上に尖った波形はインス
タンスの取得タイミングに従って高さが線形に増加していく．
学習時には，インスタンス取得タイミングは 4 から 12 の間で一様にランダムに選ぶ．この例では，インスタンス取得タイミングが 20 のときの可変 shapelets を予測する効果を確認する．
従来の shapelets 学習法のように可変 shapelets を予測できない比較手法 “NoLETS” と提案手法 LETS とを比較する 1 ．

て定義される 2 次元特徴ベクトルとして特徴空間へマッピングしている．正例と負例をそれぞれ “+” と “×” としてプロットしている．この結果から，提案手法 LETS では全てのインスタンスを正しく分類できる（AUC=100%）のに対し、比較手法 NoLETS
では分類できない（AUC=58%）という大きな性能差が生じる．

NoLETS と同様に，[2, 4, 5] などの従来の shapelets 手法でも可変 shapelets を予測できないため，インスタンス取得タイ
ミングが 20 のとき shapelets を上に尖った波形に正しくマッチ
ングできない．その結果，AUC も大きく劣化する．それゆえ，
この単純な例では可変 shapelets を予測することが分類性能においても有効であることが分かった．

1. 2 本研究の主な貢献
本論文の主な貢献を以下に示す．なお，本内容は基本的に[14] に準じ，詳しくは [14] を参照いただきたい．
• 従来手法が shapelets の時間変化を考慮できないのに対して，本研究では初めて shapelets の時間変化を考慮する．

•

Shapelets と分類器だけでなく shapelets の変化を予測する回帰モデルも同時に学習するという新しい技術課題をもた
らし，それを 1 つの数理最適化問題として定式化する．

•

本最適化において，理論的かつ実践的な解法を導出し，既製の回帰ソルバを用いて回帰モデルを学習できることを示す．

•

医療・インフラ・製造の各産業分野への適用事例で提案

手法 LETS の有効性を示す．
1：可変 shapelets を予測する効果を比較評価するため，比較手法 NoLETS では提案手法 LETS から shapelets の変形を予測する機能を除外する．

2：時系列インスタンスと shapelet との距離は 3. 2 節で定義する．

2 準

備

2. 1 記号と定義

合を学習インスタンス取得タイミング集合 P と記述する．学習
インスタンス取得タイミング集合 P は |P| <= I であるため有限集合である．なお，p ∈ P にわたって，S(p) や sk (p) や sk,l (p) の集合をとったものをそれぞれ S(P) や sk (P) や sk,l (P) と記述する．

時系列インスタンスを 2 クラス Y := {1,−1} に分類する問題

本研究では，可変 shapelets S(P) とその変化を予測する回を扱う．学習データのインスタンスの数を I 個として，i 番目

帰モデルを学習し，P に含まれないインスタンス取得タイミンのインスタンスは時系列インスタンス ti とクラスラベル yi とグの値 p ∈/ P でも可変 shapelets S(p) の変化を予測する．

インスタンス取得タイミング pi の 3 つ組とする．つまり，学習データ T は {(t1 ,p1 ,y1 ),(t2 ,p2 ,y2 ),···,(tI ,pI ,yI )} である．従来の shapelets 手法とは異なり，i 番目の時系列インスタンスが取得されたタイミング pi ∈ R を考慮する．
インスタンス取得タイミングの意味はアプリケーションに依2. 2 従来の shapelets 学習法
本節では文献 [2] の定式化を説明する．インスタンスの取得タ
イミングに従来の shapelets は依存しないため，本節ではそれらを不変 shapelets C として扱う．各時系列インスタンスに対し存する．例えば，例 1 における被験者の反応の慣れであれば試て長さ L の部分時系列は J := Q−L+1 個ある．j 番目の部分時

行回数として，例 2 における交通機関の利用状況の季節性であ系列 (ti,j ,ti,j+1 ,···,ti,j+L−1 ) と ck とのユークリッド距離を測り，ればある時刻からの経過時間として，例 3 における機械の劣化

j = 1,2,···,J の中で最小のものを ti と ck との距離と定義する．

であれば機械の稼働回数として，扱うことができる．
図 2 に示すように，時系列インスタンスと shapelet はそれぞれ長い数列と短い数列として表される．長さ Q の時系列データセットを T ∈ RI×Q とし，shapelets の個数と長さをそれぞれ Kと L とする．従来の shapelets との違いを明確にするため，インスタンス取得タイミングに応じて shapelets が変形しないか変形しうるかで，不変 shapelets と可変 shapelets を区別する：
定義 1. k = 1,2,··· ,K 及び l = 1,2,··· ,L に対して，k 番目の1∑(ti,j+l−1 −ck,l )2 .
j=1,2,···,J L
L

x̃i,k (ck ,ti ) :=

min

(1)

l=1

i 番 目 の イ ン ス タ ン ス に 対 す る 特 徴 ベ ク ト ル x̃i ∈ RK を(x̃i,1 , x̃i,2 , ··· , x̃i,K ) で定義する．バイアス項を含めた分類器の重み w̃ ∈ RK+1 が与えられて，次の線形モデルを用いる．

ŷi (x̃i ,w̃) := w̃0 +K∑w̃k x̃i,k .

(2)

k=1

不変 shapelet ck とは，インスタンス取得タイミング p に ckの l 番目の値 ck,l が依存しない shapelet である．K 個の不変クラスラベルが Y = {1,−1} であることに注意し 3 ，ŷi とシグ

shapelets を C ∈ RK×L と記述する．

モイド関数 σ を介してロジスティック損失関数を用いる．

定義 2. k = 1,2,··· ,K 及び l = 1,2,··· ,L に対して，k 番目の可変 shapelet sk (p) とは，インスタンス取得タイミング p に

sk (p) の l 番目の値 sk,l (p) が依存する shapelet である．イン
スタンス取得タイミング p における K 個の可変 shapelets をS(p) ∈ RK×L と記述する．

1−yi
1+yi
ln(σ(ŷi ))−ln(1−σ(ŷi )),L(yi ,ŷi ) := −
2
2
(
)−1
σ(ŷi ) := 1+e−ŷi.

最終的には，特徴ベクトル X̃ を介して不変 shapelets C と分類
器の重み w̃ とを同時に学習する最適化問題として定式化される．

可変 shapelets の変形の仕方はアプリケーションに依存する．
そのため，後述の定理 2 で理論的に保証されるように本研究では任意の回帰モデルを利用できる．ここでは例 1–3 をもとに 3 つの変形パターンをあげるが，本研究はこれらの例に限定されず，回帰モデルで予測できればどのような変形パターンであっても良い．

minimizeC∈RK×L , w̃∈RK+1

I∑
L(yi ,ŷi )+αΩ̃(w̃).

ここで，α >
= 0 は正則化パラメータであり，Ω̃(w̃) は次で定義される分類器の重み w̃ における ℓ2 正則化である．

Ω̃(w̃) :=shapelet の各点が周期的に変化する．これは，季節などの影響による可変 shapelets の変化を捉えるのに有効である．
例 6. 複数モード的変形は，shapelet がインスタンス取得タイ

K
∑

wk2 .

(5)

k=1

可変 shapelet の変化のトレンドを発見するのに有効である．
例 5. 周期的変形は，インスタンス取得タイミングに従って

(4)

i=1

例 4. 線形的変形は，インスタンス取得タイミングに従って

shapelet の各点が線形回帰モデルに従って変化する．これは，(3)

この非凸最適化問題には制約式は無くインスタンスごとに目的関数を分解できることから SGD アルゴリズムを用いて解かれる．
しかしながら，従来の shapelets 手法では，時系列インスタンスが取得タイミング p に依存しないことを前提としており，
可変 shapelets S(p) を予測できない．

ミングの区間によって異なる回帰モデルに従って変化する．これは，可変 shapelets の変形に対して安定期と不安定（劣化）期など複数のモードを考慮する必要がある場合に有効である．
古典的な時系列分類の問題設定とは異なり，本研究では学習

3 提案手法の定式化
提案する数理最適化問題は，分類器の重みと可変 shapeletsと可変 shapelets の変化を予測する回帰モデルとをそれらの相データとテストデータにインスタンス取得タイミングが含まれる．学習データに含まれるインスタンス取得タイミングの値の集

3：yi = −1 を yi = 0 と置換することで式 (3) は [2] の定式化と等価となる．

互依存を考慮して同時に学習するように定式化される．この最జਟ峘ীథஓ峘੎峩峘ਫಋ৲峘峩峼৷岮峉ৃ়

適化問題は，可変 shapelets と回帰モデルとを関連付ける等式制約を持つ．以降では，3. 1 節でその等式制約をまず定式化し，

崗嵑崡 

崗嵑崡 

3. 2 節で制約付き最適化問題として定式化する．
3. 1 可変 shapelets と回帰モデルとを関連付ける等式制約
本節では，可変 shapelets とその変化を予測する回帰モデルとを関連付けるための等式制約を定式化する．k = 1,2,···,K に

6KDSHOHWV峕੦峏岹特徴量の正則化を導⼊した場合
崗嵑崡 崗嵑崡 

おいて，学習インスタンス所得タイミング p ∈ P における可変shapelet sk (p) の重心を不変 shapelet ck とみなす．
ck,l (sk,l (P)) :=1 ∑|P| p∈P

図 3 Shapelets に基づく特徴量の正則化による効果．

sk,l (p).

(6)
ŷi (xi ,pi ,w) := w0 +wK+1 pi +回帰モデルのパラメータ（以降，回帰パラメータ）を ak とする．また，sk,l (p) と ck,l の差を予測するために，インスタンス
所得タイミング p と shapelet の長さに対するインデックス l とK∑
wk xi,k .

(10)

k=1

式 (10) を介して式 (3) のロジスティック損失関数 L を用いる．
従来の shapelets 学習法では式 (5) において ℓ2 正則化のみをを 2 つの従属変数とする回帰モデル fk (p,l;ak ) を導入する．つ

導入していたが，shapelets の説明性を保持するために，更にまり，以下のように可変 shapelet sk (p) と不変 shapelet ck とshapelets に基づく特徴量の正則化を導入する．まず，これを導入の差を回帰モデル fk として定義する．

する動機を明らかにする．図 3 はインスタンス取得タイミングがfk (p,l;ak ) = sk,l (p)−ck,l .

(7)回帰モデルの予測誤差を無くすように次の等式制約を定義する．

6 の場合で 1. 1 節（図 2）と同じ時系列インスタンスを表している．図 3 （上）の青太線と橙太線は，式 (5) で用いられる古典的なℓ2 正則化のみを用いて学習した 2 つの可変 shapelets S(6) を表している．この図より S(6) は元の時系列波形に似ていないことがdk (sk (P),ak ) = 0,
dk (sk (P),ak ) :=分かる．一方，図 3 （下）の青太線と橙太線は，shapelets に基づ

L ∑
∑

(8)

(fk (p,l;ak )−(sk,l (p)−ck,l ))2 .

く特徴量の正則化を導入して学習した 2 つの可変 shapelets S(6)を表している．このように、S(6) は片方のクラスの元の時系列

l=1 p∈P

波形に似ていることが分かる．以下の性質は，時系列インスタ
等号制約式 (8) は式 (7) を満たす必要十分条件となる．
具体的な回帰パラメータ ak の意味は回帰モデル fk の種類に依存する．例えば，fk が線形回帰であれば ak は回帰係数となり，fk がカーネルリッジ回帰であれば重みベクトルとそれらの係数とンス ti と可変 shapelet sk (pi ) との距離を縮めること（つまり，

shapelets に基づく特徴量 xi,k を縮小すること）は，yi wk < 0の条件下で分類性能に悪影響を及ぼさないことを保証する [14]．

なる．しかし，4. 1 節で後述するように，既製の回帰ソルバを用

定理 1. 任意の i = 1,2,···,I 及び k = 1,2,···,K に対して，i 番

いて回帰パラメータ ak を最適化できることが示されるため，本目の時系列インスタンス ti と k 番目の可変 shapelet sk (pi ) と定式化において特定の回帰パラメータ ak を意識する必要がない．

の距離は，式 (9) で定義される特徴量と一致することに注意す

次節で後述するように，等号制約式 (8) は，回帰パラメータ

る．ti と sk (pi ) の距離が縮まるとき次の 3 ケースがある:ら A と可変 shapelets S(P) とを同時に学習するように LETS(a) yi wk < 0 の場合，式 (3) の分類損失は減少する．

の数理最適化問題に組み込まれる．

(b) yi wk > 0 の場合，式 (3) の分類損失は増加する．
(c) wk = 0 の場合，式 (3) の分類損失は変化しない．

3. 2 数理計画問題の定式化
本節では，提案手法 LETS の数理計画問題を定式化する．ま定理 1 を考慮して，式 (5) の代わりに本定式化における正則

ず可変 shapelets とインスタンス取得タイミングによる特徴ベ化では分類器の重み w と shapelets に基づく特徴ベクトル X

クトルと分類器を定義し，次に数理最適化問題としてまとめる．

との両方を以下のように縮小する．

式 (1) における従来の特徴ベクトルの代わりに，i = 1,2,···,I及び k = 1,2,···,K に対して，i 番目の時系列インスタンス ti とk 番目の可変 shapelet sk (pi ) とを用いて，特徴量 xi,k は次のような最小ユークリッド距離で定義される．

1∑(ti,j+l−1 −sk,l (pi ))2 . (9)j=1,2,···,J L
L

xi,k (sk (pi ),ti ) :=

min

l=1

ここで，特徴量 xi,k (sk (pi ),ti ) は非負であり，特徴ベクトルは xi := (xi,1 ,xi,2 ,···,xi,K ) となる．分類器の重み w ∈ R
用いて，従来の式 (2) を次の式に換える．

K+2をΩ(w,X,y) :=

K
K
I
∑
∑
∑
wk2 +
βk
xi,k I(yi wk < 0).
k=1

k=1

(11)

i=1

ここで，インジケータ関数 I(·) は引数が真のとき 1 を返し偽のとき 0 を返し，式 (9) より xi,k >= 0 である．正則化パラメー
タ βk > 0 は shapelets があるクラスの時系列に似ていないことを罰する程度を調整するもので自動的かつ動的に調整される [14]．
最終的には，学習データ T が与えられて，LETS の定式化
は可変 shapelets S(P)，分類器の重み w，及び回帰パラメー
タら A を以下のように制約付きで同時に最適化する．

I∑

minimize
S(P)∈R
A∈AK

K×L

×P,w∈RK+2

4. 1 回帰パラメータ集合 A の学習

L(yi ,ŷi )+αΩ(w,X,y)
(12)

i=1

本節では，式 (14) の最適化問題が本質的には回帰モデルの標準的な最適化問題に変換できることを示す．この事実は，標s.t.

equality constraints in Eq. (8).

準的な回帰モデルの学習から得られた回帰パラメータが式 (14)

ここで，A は回帰パラメータ集合 A を含むような集合であの最適な回帰パラメータでもあることを保証する．つまり，既り，分類損失関数 L は式 (9) と (10) とを介して式 (3) と同じ製の回帰ソルバをそのまま用いて式 (14) の最適化問題を解けであり，Ω は式 (11) と同じ正規化である．式 (12) の実行可る．これを保証するために以下の定理を導出する [14]．

能解は式 (8) の等式制約を満たす．そのため，学習が完了すれば式 (7) で可変 shapelets S(p) を予測できる．加えて，[5] のProposition 4.1 と同様に，可変 shapelets は次の性質を持つ．
性質 1. 可変 shapelets S(P) は式 (12) の問題を最適化する K
個の shapelets である．その目的関数から，LETS は式 (3) の分類損失と式 (11) の正則化とを削減するように可変 shapelets を

定理 2. k = 1,2,···,K に対して，次の最適化問題を最小化する
回帰パラメータ ak は，式 (14) の最適化問題も最小化する．

arg minak ∈Adk (sk (P),ak ),dk (sk (P),ak ) :=L ∑∑学習する．定理 1 と式 (11) から，i = 1,2,···,I 及び k = 1,2,···,K(16)(fk (p,l;ak )−(sk,l (p)−ck,l ))2 .

l=1 p∈Pにおいて yi wk < 0 のとき，この損失とこの正則化はそれぞれそれぞれ sk,l (p) − ck,l と fk (p,l;ak ) とを k 番目の回帰モデ

式 (9) における距離 xi,k を縮める方向に働く．すなわち，kル fk における観測値と予測値とみなすと，式 (16) の最適化問題

番目の可変 shapelet は，式 (9) の距離において wk < 0 及びは，p ∈ P と l = 1,2,···,L にわたって sk,l (p)−ck,l と fk (p,l;ak )wk > 0 の場合にそれぞれ正例と負例の時系列インスタンスに類の 2 乗誤差の和を最小化しているだけである．したがって，似する傾向がある．そのため，k 番目の可変 shapelet の属する

式 (16) は標準的な回帰問題の最適化と本質的に同じである．

クラスは，wk < 0 なら 1 として wk > 0 なら-1 とする．

4. 2 可変 shapelets S(P) と分類器の重み w の学習
部分問題の式 (15) は非凸最適化問題のままであるが，その4 提案手法の解法

目的関数はインスタンスごとの目的関数 Gi に分解できる．

前節で提案した式 (12) は非凸の目的関数と非線形の等式制約から構成されている．有効な解法アプローチとして，拡張ラグランジュ法を用いて式 (12) を等価な無制約最適化問題に変換する．
I∑

arg min
K×L

S(P)∈R
×P,w∈RA∈AK ,λ∈RK

K+2

µ
1
+ ⟨λ,d(S(P),A)⟩+ ∥d(S(P),A)∥22 .
I
2I

(13)
Ωi (w,xi ,yi ) :=µ+⟨λ,d(S(P),A)⟩+ ∥d(S(P),A)∥22 .
2
ここで k = 1, 2, ··· , K に対して，d(S(P), A) は，式 (8) のdk (sk (P),ak ) が k 番目の要素となる K 次元ベクトルであり，
λ ∈ RK はラグランジュ乗数であり，µ >= 0 は罰則パラメータであり，⟨·,·⟩ は内積を表し，∥·∥2 は ℓ2 ノルムを表す．

を用いて，以下の手順を反復する．

(2) 以下の部分問題を解き可変 shapelets S(P) と分類器の重み w を更新する．

k=1

k=1

(18)

∂Gi (S(P),w) ∂L(yi ,ŷi ) ∂ ŷi ∂xi,k=∂sk,l (p)∂ ŷi∂xi,k ∂sk,l (p)+α∂Ωi (w,xi ,yi ) ∂xi,k∂xi,k∂sk,l (p)
L ∑
∑

2
2µ
+ λk zk,l (p)+ zk,l (p)
I
I
′

(19)

zk,l′ (p′ )2 .

ここで，zk,l (p) := sk,l (p) − ck,l − fk (p,l;ak ) である．分類器の重み w に対する Gi の勾配も，同様に次のように書き下せる．

∂Gi (S(P),w) ∂L(yi ,ŷi ) ∂ ŷi∂Ωi (w,xi ,yi )
=
+α
.
∂wk
∂ ŷi
∂wk
∂wk

(20)

式 (19) と (20) の右辺の各勾配は，従来の shapelets 学習法と同様のアプローチで個別に導出する．特に，勾配 ∂xi,k /∂sk,l (p)L(yi ,ŷi )+αΩ(w,X,y)

S(P)∈RK×L ×P,w∈RK+2 i=1(15)µ+⟨λ,d(S(P),A)⟩+ ∥d(S(P),A)∥22 .
2(3) ラグランジュ乗数 λ を λ+µd(S(P),A) として更新する．
次の 2 つの節では，式 (14) と (15) の部分問題の解き方を述べる．
4：

K

l =1p′ ∈P(1) 以下の部分問題を解き回帰パラメータら A を更新する 4 ．
µ
arg min ⟨λ,d(S(P),A)⟩+ ∥d(S(P),A)∥22 .
(14)
2
A∈AK

arg minK

する Gi の勾配は，微分の連鎖律を用いて次のように書き下せる．

タ集合 A とし，2 つ目のブロックを可変 shapelets S(P) と分類
器の重み w とする．式 (13) を効率的に解くため ADMM [15]1∑ 2 ∑wk +βk xi,k I(yi wk < 0).
I

SGD を用いて S(P) と w を学習する．可変 shapelets S(P) に対

変数を 2 つのブロックに分け，1 つ目のブロックを回帰パラメー

I
∑

(17)

ここで，Ωi は式 (11) をインスタンスごとに分解した式である．

L(yi ,ŷi )+αΩ(w,X,y)i=1

Gi (S(P),w) := L(yi ,ŷi )+αΩi (w,xi ,yi )∑I

i=1 L(yi ,ŷi )+αΩ(w,X,y) は変数 A に依存しないので，式 (14) では

これらの項を式 (13) から除外している．

については，[5, 16, 17] と同様に劣勾配を用いて導出することで時系列長に対する計算量を線形オーダーまで削減できる [14]．

5 適用事例
例 1–3 で挙げた 3 つの産業分野への適用事例を用いて，可変shapelets を予測することへの有効性を示す．

崗嵑崡 

೬঩崗嵑崡 

਴঩











崗嵑崡 
೬঩

崗嵑崡 
೬঩


図 4 自転車シェアリングの時系列インスタンスの例．








5. 1 実 験 設 定
崗嵑崡 
਴঩k = 1,2,···,K に対して，k 番目の shapelet の分類への寄与度

崗嵑崡 
਴঩

を分類器の重みの絶対値 |wk | で測る．一般性を損なうことな
く，shapelets のインデックスは分類器の重みの絶対値の降順にソートする（つまり，|w1 | >= |w2 | >= ... >
= |wK |）．可変 shapelets

図5

自転車シェアリングにおける予測結果．左：2012/10，右：2012/12．

を扱える従来手法は存在しないため，予測された可変 shapeletsの変化が専門家の知識や物理現象と一致するかを検証する．
また，AUC は分類器の閾値に依存せず均衡／不均衡データのいずれでも適切な分類性能指標であり，提案手法 LETS と以下のベースライン手法との AUC も比較する．LTS [2] は，
古典的な時系列分類において高い正解率を達成する [2, 18, 19]．

LTSSFS [5] は，教師有り特徴選択を介して初期 shapelets を選定し self-paced learning で更に学習することで 2 クラス分類

図 6 自転車シェアリングにおける可変 shapelets の変化．

において高い AUC を達成する．CSLTS [4] は，本研究の実験
データセットの一部にも含まれるような不均衡な 2 クラス分類

する．時系列インスタンスの幾つかを図 4 に示す．2011/1/1を扱うためのコスト考慮型学習を LTS に導入する．NoLETSからの経過時間をインスタンス取得タイミング p とする．季は，可変 shapelets の純粋な導入効果を比較評価するために，

節効果を考慮するため，例 5 の周期的変形を予測することを狙LETS から可変 shapelets の変形を予測する機能を除外する．

う．LETS では，Mackay 周期カーネルを用いたカーネルリッ

LTS や LTSSFS や CSLTS などの従来の shapelets 手法ではイジ回帰モデルを採用し，周期パラメータを 1 年に設定する．

ンスタンス取得タイミングを入力情報として活用できない．こ図 5 (上) と (下) は，それぞれクラス 1（休日）とクラス -1（平の潜在的な不公平さを解消するため，NoLETS は式 (10) を介

日）の時系列インスタンスを黒線で描き，それらにベストマッチ

してインスタンス取得タイミングを考慮した分類器を学習する．

ングする位置に可変 shapelets を重ね描きしている．以降，1 番

5. 2 事例：季節変化の影響を受ける交通機関の利用
交通期間の利用において，自転車シェアリングの利用者数に

目と 2 番目に貢献度の高い可変 shapelets（つまり，s1 と s2 ）を
赤太線と青太線で描く．分類器の重み w1 と w2 の符号は両方とも負であり，可変 shapelets s1 と s2 はいずれもクラス -1 よりおける日別の推移は季節変化の影響を受ける時系列インスタンもクラス 1 の時系列データに類似していることが分かる．このスである．米国では温暖な季節に比べて冬季の自転車シェアリ

結果は性質 1 と一致する．図 5 (左) と (右) は，インスタンス取

ングシステムの予約者は少ない [11]．一方で，自転車再配置に得タイミング p がそれぞれ 2012/10 と 2012/12 のときの結果では時間的・空間的にコストがかかるため，これらのシステムである．最も貢献度の高い可変 shapelet s1 (p) は，休日の深夜 0 時

は適切な自転車配置の戦略が重要であり，特に休日と平日とでから早朝 3 時頃における利用者数が平日の場合よりも多いとい

は利用パターンが異なる [12]．そのため，季節の影響を考慮しう事実を捉えている．2 番目に貢献度の高い可変 shapelet s2 (p)ながら 1 日の利用パターンの違いを発見することで，意思決定は，休日の利用者数は平日のように 2 つの鋭いピークを持つの者がより良い運用計画を立てやすくなる．

ではなく 10 時から 16 時頃に緩やかな 1 つのピークを持つこ

使用する自転車シェアリングの時系列データは，2011 年ととを捉えている．テストデータの AUC は，LETS と NoLETS

2012 年の 2 年間にわたりワシントン D.C. 周辺で収集されたと LTS と LTSSFS と CSLTS とでそれぞれ 97%, 92%, 91%,

レンタルバイクの 1 時間ごとの利用台数であり [20]，UCI の91%, 73%である．これらの結果から，可変 shapelets は休日と公開データセットに含まれる 5 ．この元となる時系列データ

平日の分類に有効な利用パターンを捉えれることが分かる．

から日単位で時系列インスタンスを取得する．学習データは

図 6 は，2012/2/16 から 2012/12/16 にかけてインスタンス取2011/1/1 から 2012/9/30 までで，テストデータは 2012/10/1

得タイミング p が変化したときの可変 shapelets s1 (p) と s2 (p)から 2012/12/31 までである．学習用インスタンスは 569 個でを示している．可変 shapelets s1 (p) と s2 (p) が表す利用パター

テスト用インスタンスは 86 個であり，残りの 76 日は欠損してンは，冬季になるとその変化が緩やかになり自転車利用者数がいる．休日と平日をそれぞれクラス 1 とクラス -1 として分類減少する．この結果は [11] の報告とも一致する．更に，この現象
は貢献度の最も高い可変 shapelet s1 (p) に特によく現れている．

5：https://archive.ics.uci.edu/ml/datasets/bike+sharing+dataset

図 5 (上) から，2012/10 と 2012/12 の休日の s1 (p) の変化は，冬崗嵑崡  &崗嵑崡  &崗嵑崡  )=図 7 脳波における時系列インスタンスの例．

図9崗嵑崡  )=脳波における可変 shapelets の予測結果．

崗嵑崡  ੂ਋崡崕嵋嵛崗嵑崡  ৴ਢ崡崕嵋嵛

図 8 脳波における可変 shapelets の変化．

の深夜 0 時から早朝 3 時頃にかけての自転車の利用者数が冬季に

図 10

機械のローラー劣化における時系列インスタンスの例．

図 11

機械のローラー劣化における可変 shapelets の変化．

減少することを捉えており，恐らく殆どの利用者は真冬の休日の早朝に自転車に乗りたくないため，これは納得できる結果である．
本節の実験評価から，LETS により発見された可変 shapelets
は休日と平日を区別する利用パターンを捉えるだけでなく季節変化による利用パターンの変化も捉えれることを確認できた．

5. 3 事例：被験者の慣れの影響を受ける脳波の測定
事象関連電位（ERP）は認知刺激に関する非侵襲な脳波の時マッチングする位置に可変 shapelets を重ね描きしている．分

系列データである．同じ刺激が短い間隔で単調に繰り返される類器の重み w1 と w2 の符号は共に正であり，可変 shapelets のと，脳内反応は短期間の試行で慣らされ減衰していく．この短期

いずれもクラス 1 よりもクラス -1 の時系列データに類似してい間の慣れが ERP 波形を減衰させることが知られている [8, 9]．

ることが分かる．この結果は性質 1 と一致する．可変 shapelets

また，異なる頭皮領域間の ERP を区別する波形パターンを理解

はクラス 1 の波形の方がクラス -1 の波形よりも細かな変動がすることは，脳領域と刺激の相互作用を理解し頭皮に装着するあるという違いを捉えている．テストデータの AUC は，LETS

電極を効率的に選択するための手がかりとなる [10]．したがっと NoLETS と LTS と LTSSFS と CSLTS とでそれぞれ 79%,て本研究では，異なる頭皮領域（チャンネル）間の ERP を分類

70%, 65%, 68%, 62%である．本節の実験評価から，LETS はする波形パターンを可変 shapelets として発見し，被験者の短チャンネルの分類に有効な可変 shapelets を発見するだけでな

期間の慣れによる可変 shapelets の変化も発見することを狙う．

く被験者の短期間の慣れに起因する可変 shapelets の変化を期使用する ERP 時系列データ は，被験者の短期間の慣れによっ6て生じる ERP 波形の歪みを研究するために用意された [8]．頭皮
領域の C4 チャンネルと FZ チャンネルで収集された時系列インス
タンスをそれぞれクラス 1 とクラス -1 として分類する．被験者は19–31 歳の健常者 32 名（女性 14 名）であり，各自 7 回同じ実験を試行し短期間の慣れを評価した．32 名を 28 名（インスタンス数
としては 28×7×2 個）と 4 名（インスタンス数としては 4×7×2個）に分けて，それぞれ学習データとテストデータとする．時系
列インスタンスの幾つかを図 7 に示す．各被験者の試行回数をインスタンス取得タイミング p とする．試行回数に対する可変shapelets の変化のトレンドを発見するため，例 4 の線形的変形を予測することを狙い，LETS では線形回帰モデルを採用する．
図 8 は，1 回目から 7 回目まで（つまり，p = 1,2,···,7）の試行における 1 番目と 2 番目に貢献度の高い可変 shapelets s1 (p)と s2 (p) の変化を示している．試行回数 p が増加すると各可変

shapelets の振幅は減衰している．この結果は，被験者の短期間の慣れに関する専門家の知見と一致する [8, 9]．
図 9 (左) と (右) は，それぞれクラス 1 とクラス -1 のテスト
用被験者の時系列インスタンスを黒線で描き，それらにベスト

待通り予測できることを確認できた．

5. 4 事例：ローラー劣化の影響を受ける機械の稼動状態
スキャナやコピー機やプリンタなどの機械においてローラーは紙を搬送する重要な部品である．ローラーは何度も使用するうちにほこりの堆積や摩耗により徐々に滑りやすくなることが知られており，この種の機械は安定期を過ぎると動作が不安定になる．
また，ローラーにかかる負荷は稼動状況によって異なる．機械に取り付けた安価なセンサからこのような現象を発見できれば，機械設計の改善やプロアクティブな保守に役立てることができる．
我々はスキャナのローラーの近くに低コストの加速度センサ（MMA7361）を取り付けて 26 万枚の紙をスキャンしてローラーを劣化させた．25 万枚の紙をスキャンする前後で，学習データとテストデータを分ける．初期スキャンと連続スキャンをそれぞれ
クラス 1 とクラス -1 として稼動状況を分類する．時系列インスタ
ンスの幾つかを図 10 に示す．スキャンの回数をインスタンス取得
タイミング p とする．安定期と不安定期に対して例 6 の複数モード的変形を考慮し，LETS では線形回帰木モデルを採用する 7 ．
図 11 は，スキャンの回数 p が 1 回から 260,000 回まで変化
7：線形回帰木とは葉に線形回帰モデルを持つ決定木であり，関数の連続性が保6：https://osf.io/8wj3s/

証されないため拡張版 LETS を用いる [14]．

崗嵑崡  ੂ਋崡崕嵋嵛崗嵑崡  ৴ਢ崡崕嵋嵛

[3]

L. Ye and E. Keogh. “Time Series Shapelets: A New Primitive for Data Mining”. In: KDD. ACM, 2009.

[4]

S. Roychoudhury, M. Ghalwash, and Z. Obradovic. “CostSensitive Time-Series Classification”. In: ECML PKDD.
Springer, 2017.

[5]
図 12

A. Yamaguchi and K. Ueno. “Learning Time-series
Shapelets via Supervised Feature Selection”. In: SDM.

機械のローラー劣化における可変 shapelets の予測結果．

SIAM, 2021.

したときに予測された可変 shapelets s1 (p) と s2 (p) を示してい[6]

ducing Time Series Chains: A New Primitive for Time Se-

る．スキャン回数 p が増加するとローラーのスリップによりこ
れらの可変 shapelets は平坦になっていく．特に s1 (p) は s2 (p)よりも明瞭に変化している．一方で，20 万枚を超えたあたりかries Data Mining”. In: Knowl. Inf. Syst. (2019).
[7]ていることが分かる．これらの結果から，可変 shapelets の変Improves Robustness”. In: KDD. ACM, 2020.
[8]

F. Mancini, A. Pepe, A. Bernacchia, G. Di Stefano, A.
Mouraux, and G. D. Iannetti. “Characterizing the Short-

化が機械的な知見と一致していることが分かる．

Term Habituation of Event-Related Evoked Potentials”.

図 12 (左) と (右) は，それぞれクラス 1（初期スキャン）とクラス -1（連続スキャン）のテスト用時系列インスタンスを黒M. Imamura, T. Nakamura, and E. Keogh. “Matrix Profile XXI: A Geometric Approach to Time Series Chains

らスキャナはメンテナンスを促す警告を発しており，s1 (p) が変形する速さは 20 万枚を超える前より後の方がより速くなっ

Y. Zhu, M. Imamura, D. Nikovski, and E. Keogh. “Intro-

In: eNeuro (2018).
[9]

O. Hernandez, R. Garcia-Martinez, and V. Monteon. “Al-

線で描き，それらにベストマッチングする位置に可変 shapelets

cohol eﬀects on the P2 component of auditory evoked po-を重ね描きしている．分類器の重み w1 と w2 の符号は共に負でtentials”. In: Anais da Academia Brasileira de Ciencias

あり，可変 shapelets のいずれもクラス -1 よりもクラス 1 の時(2014).

系列データに類似していることが分かる．この結果は性質 1 と[10]

F. Lotte. “A Tutorial on EEG Signal Processing Tech-一致する．初期スキャン時の摩擦は連続スキャン時よりも強い．

niques for Mental State Recognition in Brain-Computer

1 番目の可変 shapelets は初期スキャンのピークが連続スキャ

Interfaces”. In: Guide to Brain-Computer Music Interfacing. Springer, 2014.

ンのものより鋭いことを捉えており，この現象と一致する．テ
ストデータの AUC は，LETS と NoLETS と LTS と LTSSFS[11]

ing in US: user willingness, and operator’s challenges andと CSLTS とでそれぞれ 73%, 64%, 60%, 64%, 61%である．本

best practices”. In: Sustainable cities and society (2017).

節の実験評価から，LETS はこの稼動状況の分類に有効な可変shapelets を発見でき，可変 shapelets とのその変化は機械的な[12]

本研究では，インスタンス取得タイミングに従って形状を

S. Reiss and K. Bogenberger. “Validation of a Relocation
Strategy for Munich’s Bike Sharing System”. In: Trans-

知見と一致することを確認できた．

6 ま と めR. P. Godavarthy and A. R. Taleciani. “Winter bikeshar-portation Research Procedia (2016).
[13]“Learning from accelerometer data on a legged robot”. In:
IFAC Proceedings Volumes (2004).

[14]

A. Yamaguchi, K. Ueno, and H. Kashima. “Learning

変化させられる可変 shapelets を導入した．提案手法 LETS

Evolvable Time-series Shapelets”. In: ICDE. IEEE, 2022

では，任意のインスタンス取得タイミング p における可変(to appear).

shapelets S(p) を予測するため，可変 shapelets S(P) とその[15]“Distributed Optimization and Statistical Learning via the

変化を予測する回帰モデル f と分類器 w を同時に学習する．

Alternating Direction Method of Multipliers”. In: Found.

ADMM に基づき導出された解法では既製の回帰ソルバを用いてこの回帰モデル f を学習できる．インフラ・医療・製造の各産業分野への適用事例により本手法の有効性を確認した．

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.

Trends Mach. Learn. (2011).
[16]

A. Yamaguchi, S. Maya, K. Maruchi, and K. Ueno.
“LTSpAUC: Learning Time-series Shapelets for Optimizing Partial AUC”. In: SDM. SIAM, 2020.

[17]

文

献

A. Yamaguchi, S. Maya, and K. Ueno. “RLTS: Robust Learning Time-series Shapelets”. In: ECML PKDD.
Springer, 2020.

[1]

H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E.
Keogh. “Querying and Mining of Time Series Data: Ex-[18]

of Timeseries Shapelets”. In: AAAI. AAAI Press, 2016.

perimental Comparison of Representations and Distance
Measures”. In: Proc. VLDB Endow. (2008).
[2]

[19]

ACM, 2014.

X. Li and J. Lin. “Evolving Separating References for Time
Series Classification”. In: SDM. SIAM, 2018.

J. Grabocka, N. Schilling, M. Wistuba, and L. SchmidtThieme. “Learning Time-series Shapelets”. In: KDD.

L. Hou, J. T. Kwok, and J. M. Zurada. “Eﬃcient Learning[20]

H. Fanaee-T and J. Gama. “Event labeling combining ensemble detectors and background knowledge”. In: Progressin Artificial Intelligence (2013).