DEIM Forum 2013 E1-6
多次元時系列データの符号表現 Universal SAX と
次元圧縮を併用した高次元時系列データの符号表現
大西 史花
†松田 成美
†渡辺 知恵美
††お茶の水女子大学理学部情報科学科 〒112-8610 東京都文京区大塚 2-1-1
E-mail: †{onishi.ayaka, g0920537, chiemi}@is.ocha.ac.jp
あらまし センサーデバイスやシミュレーション技術の発達に伴い，大量の多次元時系データの入手が容易にな っている．時系列データのための有用な索引技術のひとつに Lin らが提案した Symbolic Aggregate Approximation (SAX) があるが，SAX は 1 次元の時系列データしか扱うことができない．よって我々は先行研究にて，多次元時系 列データのための索引 Universal SAX を提案した．本手法では空間充填曲線を使用し多次元時系列データを 1 次元 データに変換するが，このとき元の多次元空間における距離関係を用いて変換を行うためマイニングに必要となる ようなデータの特徴を欠落が少ない．我々は評価実験により本手法が既存手法よりも多次元時系列データに対して 有効な手法であることを明らかにし，加えて高次元のデータへの適用のための一手法を提案，適用実験を行う． キーワード 多次元時系列データ，データマイニング，符号表現，索引
1. は じ め に
セ ン サ ー デ バ イ ス や シ ミ ュ レ ー シ ョ ン 技 術 の 発 展 に 伴 い ，GPS ロ グ な ど の 軌 跡 デ ー タ や モ ー シ ョ ン キ ャ プ チ ャ デ ー タ な ど 大 量 の 多 次 元 時 系 列 デ ー タ の 入 手 が 容 易 に な っ て い る ． こ れ ら を 効 率 よ く マ イ ニ ン グ す る こ と で ， 我 々 は 様 々 な 研 究 や マ ー ケ テ ィ ン グ 分 析 に 役 立 て る こ と が 出 来 る が ， 膨 大 な デ ー タ を マ イ ニ ン グ す る た め に は 効 果 的 な 問 い 合 わ せ や 索 引 が 不 可 欠 で あ る ． そ の 中 の 1 つ に Lin ら が 提 案 し た Symbolic Aggregate Approximation (SAX) [7] が あ る ． SAX で は 従 来 の 手 法 と は 異 な り ， 時 系 列 デ ー タ を 実 数 値 で は な く 文 字 列 に 変 換 す る ． よ っ て 文 字 列 用 に 定 義 さ れ た 手 法 が 適 用 可 能 と な る ． 加 え て 単 純 な ア ル ゴ リ ズ ム で あ り な が ら マ イ ニ ン グ 精 度 が 良 い な ど の 利 点 も 持 つ ． し か し な が ら ，SAX は 1 次 元 の 時 系 列 デ ー タ し か 扱 う こ と が で き な い ． SAX を 多 次 元 時 系 列 デ ー タ に も 適 用 さ せ る た め ，既 存 研 究 で は 前 処 理 と し て 多 次 元 の デ ー タ を 1 次 元 に 次 元 削 減 す る ア プ ロ ー チ が と ら れ て き た ． こ れ ら の ア プ ロ ー チ に ， 重 心 距 離 法 と 主 成 分 分 析 が あ る [4][11]． 重 心 距 離 法 は 多 次 元 空 間 デ ー タ 上 の 各 点 を デ ー タ の 重 心 か ら 点 ま で の 距 離 を 使 用 し て 1 次 元 の 時 系 列 デ ー タ 状 に 変 換 す る 手 法 で あ る ． 主 成 分 分 析 は 多 次 元 デ ー タ の 相 関 を 少 数 の 合 成 変 数 で 表 現 す る こ と で 1 次 元 に 変 換 す る 手 法 で あ る ． し か し こ れ ら の 手 法 は 次 元 削 減 の 際 に 元 デ ー タ の 特 徴 を 欠 落 さ せ て し ま う 可 能 性 が あ る ． 例 え ば 重 心 距 離 法 は デ ー タ の 重 心 と 各 点 の 間 の 距 離 の み に 焦 点 を あ て て 1 次 元 化 を 行 う た め ， 同 じ 速 度 で 異 な る 方 向 に 動 く 2 つ の 多 次 元 軌 道 状 デ ー タ の 違 い を 表 現 す る こ と が 出 来 な い ．ま た 主 成 分 分 析 は ，SAX に 適 用 さ せ る と い う 目 的 を 達 成 す る た め に 第 一 主 成 分 の み を 使 用 し て 1 次 元 化 を 行 う が ， こ の 第 一 主 成 分 の 寄 与 率 が 低 い 場 合 に 元 デ ー タ の 特 徴 を 欠 落 さ せ て し ま う 可 能 性 が あ る ． な ぜ な ら ， 第 一 主 成 分 の 寄 与 率 が 低 い と い う こ と は ， 第 二 主 成 分 以 下 の 部 分 空 間 に 元 デ ー タ の 特 徴 が 多 く 表 れ て い る か ら で あ る ． つ ま り 第 二 主 成 分 空 間 上 で は 異 な る 距 離 に 位 置 す る 点 が 第 一 主 成 分 空 間 上 で は 同 じ 点 と し て 写 像 さ れ て し ま う と い う 可 能 性 が あ り ， こ れ は マ イ ニ ン グ 時 の 誤 検 出 の 原 因 と な る ． よ っ て 我 々 は 先 行 研 究 に お い て ， 空 間 充 填 曲 線 を 用 い て 多 次 元 空 間 内 の デ ー タ の 位 置 関 係 を 損 な う こ と な く 文 字 列 に 変 換 す る Universal SAX（ USAX）を 提 案 し た [10]．空 間 充 填 曲 線 と は ，多 次 元 空 間 を 曲 線 で 埋 め 尽 く す よ う に 辿 る こ と で 空 間 の 順 序 付 け を 行 う 手 法 で あ る ． USAX に お い て 文 字 列 に 変 換 後 の 各 文 字 は 元 の デ ー タ 空 間 に 適 用 し た 空 間 充 填 曲 線 に よ る 順 序 値 の 範 囲 に よ っ て 割 り 当 て ら れ る ． 空 間 充 填 曲 線 に よ る 順 序 値 の 範 囲 は 元 空 間 に お い て 多 面 体 を 成 す の で ， 2 つ の 文 字 間 の 距 離 は 2 つ の 多 面 体 間 の 最 小 距 離 と し て 計 算 す る こ と が 出 来 る ． 例 え ば 図 1 は 2 次 元 空 間 上 の デ ー タ t0, t1, … , tn−1 を USAX に 変 換 す る 概 略 図 で あ る ． こ の 図 で は 空 間 充 填 曲 線 の 1 つ で あ る ヒ ル ベ ル ト 曲 線 を 用 い て 空 間 の 順 序 付 け を 行 い ， そ の 順 序 に 従 っ て 2 次 元 空 間 を 5 つ の 領 域 に 分 割 ， そ れ ぞ れ に 文 字 を 割 り 当 て ， そ の あ と 各 文 字 領 域 内 に 存 在 す る デ ー タ を 対 応 す る 文 字 に 変 換 す る こ と で USAX 文 字 列 を 得 て い る ．こ の 時 ，そ れ ぞ れ の USAX 文 字 間 の 距 離 は 2 次 元 空 間 上 の 5 つ の 多 面 体 同 士 の 最 小 距 離 と し て 計 算 さ れ る ． つ ま り ， 文 字 列 化 後 の 距 離 測 度 と し て 元 の 多 次 元 空 間 上 の 距 離 を 用 い て い る た め ， USAX は 多 次 元 デ ー タ を 1 次 元 デ ー タ で あ る 文 字 列 に 変 換 し た 後 も 元 デ ー タ 間 の 位 置 関 係 を 保 持 す る こ と が 出 来 る ．図 1: 2 次 元 デ ー タ か ら USAX へ の 変 換 本 稿 で は USAX の 有 効 性 の 評 価 を 行 う た め ，前 述 し た 2 つ の 次 元 削 減 手 法 で あ る 重 心 距 離 法 と 主 成 分 分 析 適 用 後 に SAX を 適 用 し た デ ー タ と USAX を 適 用 し た デ ー タ と の 文 字 列 化 精 度 比 較 実 験 を 行 う ． ま た USAX を よ り 高 い 次 元 の デ ー タ に 適 用 す る 際 の 課 題 点 と そ の 解 決 の た め の 一 手 法 を 提 案 し ， 適 用 実 験 を 行 う ． 本 稿 の 構 成 は 以 下 の 通 り で あ る ． 第 2 節 で は USAX の 基 手 法 で あ る SAX に つ い て 概 説 し ， 第 3 節 で は USAX に よ る 符 号 表 現 変 換 に つ い て 解 説 す る ． 第 4 節 で は 既 存 手 法 と USAX と の 比 較 を 行 い ，第 5 節 で 高 次 元 デ ー タ へ の USAX の 適 用 に つ い て 論 ず る ． そ し て ， 第 6 節 に て ま と め と 今 後 の 課 題 を 述 べ る ．
2. SAX
SAX と は ，時 系 列 デ ー タ の 表 現 手 法 の 1 つ で ，時 系 列 デ ー タ を 文 字 列 に 量 子 化 す る 手 法 で あ る ． パ ラ メ ー タ 値 と し て ， あ ら か じ め 文 字 列 長 w（ も し く は 1 つ の 文 字 に 変 換 す る デ ー タ 数 ）と 文 字 種 類 a の 2 つ を 決 定 す る ． こ れ ら の 値 は デ ー タ に 依 存 す る た め 実 験 的 に 求 め る 必 要 が あ る ． SAX に よ る 時 系 列 デ ー タ の 文 字 列 化 の 手 順 を 図 2 と 以 下 に よ っ て 示 す ．図 2 で は 破 線 が SAX を 適 用 す る 時 系 列 デ ー タ で あ る ． な お ， 時 系 列 デ ー タ は 位 置 や ス ケ ー ル の ズ レ を 修 正 す る た め に あ ら か じ め 正 規 化 す る ． 図 2: SAX に よ る 時 系 列 デ ー タ の 文 字 列 化 (1) 時 間 軸 を 等 間 隔 に 区 分 （ 縦 実 線 ）． (2) 区 間 ご と の 平 均 値 を 算 出 （ 横 太 線 ）． (3) 正 規 分 布 の 各 面 積 が 等 し く な る よ う な 分 割 線 （ 横 実 線 ）を 定 め ，そ の 区 間 に ， a ，b ， c … と ア ル フ ァ ベ ッ ト を 割 り 振 る ． (4) (2) で 求 め た 平 均 値 を (3) で 割 り 振 っ た ア ル フ ァ ベ ッ ト に 従 い 文 字 に 変 換 （ 下 部 ）． こ こ で (3)に つ い て 詳 細 を 説 明 す る ．そ も そ も 連 続 値 を 離 散 化 す る 際 ， そ れ ぞ れ の 離 散 値 の 存 在 確 率 は 等 し い こ と が 求 め ら れ て い る [1][9]． SAX で は ， 正 規 化 さ れ た 時 系 列 デ ー タ の 値 の 分 布 は 正 規 表 現 に 従 う と い う 特 徴 を 活 か し [7]，こ の 要 求 を 正 規 分 布 の 等 面 積 分 割 に よ っ て 達 成 し て い る ． SAX を 適 用 し て 作 成 さ れ た 文 字 列 に は 性 能 の 良 い 各 種 マ イ ニ ン グ 操 作 を 行 う こ と が 可 能 で あ る ． こ れ は SAX の 近 似 距 離 が 実 距 離 の 下 界 を 抑 え る こ と を 保 障 し て い る ，つ ま り SAX に よ る 文 字 列 変 換 後 の デ ー タ 間 の 距 離 は 元 デ ー タ 間 の 距 離 よ り 常 に 小 さ く な る と い う 特 徴 を 有 し て い る た め で あ る ． こ の 特 徴 に つ い て 説 明 す る た め に ，ま ず SAX 文 字 列 に お け る 文 字 列 間 の 距 離 の 定 義 に つ い て 述 べ る ．あ る 2 つ の 時 系 列 デ ー タ C と Q の 2 つ の 距 離 を 計 算 す る 際 ， そ の 距 離 尺 度 は 一 般 的 に ユ ー ク リ ッ ド 距 離（ 図 3 の (A)）が 使 用 さ れ る ．そ れ に 対 し て SAX で の 文 字 列 （Q̂， Ĉ）間の距離は図 3 の 式 (B) で 示 さ れ る よ う に 文 字 間 の 距 離 dist(q̂, ĉ) の 二 乗 の 和 で 定 義 さ れ て い る ． n は 元 デ ー タ の デ ー タ 数 で あ る ． 文 字 間 の 距 離 dist(q̂, ĉ) は 文 字 q̂ が と り う る 値 の 最 大 値 と ĉ が と り う る 値 の 最 小 値 に よ っ て 定 義 さ れ る ． 図 3: SAX に お け る 文 字 列 間 の 距 離 の 定 義 と 概 念 図 例 え ば 図 4 の 左 側 は 正 規 分 布 を 4 分 割 し ， 4 種 類 の 文 字 を 割 り 当 て た 場 合 の 図 示 で あ る ． こ こ で dist(a,d) は a の と り う る 最 大 値 -0.67 と d の と り う る 最 小 値 0.67 の 差 と な る の で 1.34 と な る ．こ の よ う な 距 離 の 定 義 に よ り ，SAX に よ っ て 求 め ら れ る 文 字 列 間 の 距 離 （ つ ま り 元 の デ ー タ の 近 似 距 離 ） は 元 の デ ー タ の 実 距離 の 下 界 を 抑 え て い る こ と が 保 障 さ れ て い る ． 加 え て ， SAX は 文 字 間 の 距 離 を 表 （ 図 4 の 例 の 場 合 は 図 中 右 の 表 ） と し て あ ら か じ め 用 意 し て お く こ と が 可 能 で あ る ． な ぜ な ら 文 字 間 の 距 離 の 定 義 は 前 述 の よ う に 正 規 分 布 の 分 割 に よ っ て の み 計 算 さ れ る か ら で あ る ． よ っ て 一 度 だ け 距 離 表 を 作 成 す れ ば 文 字 列 間 の 距 離 を 求 め る 際 に 毎 回 文 字 間 の 距 離 を 測 る 必 要 は な い ． 図 4: SAX に お け る 文 字 間 の 距 離 の 図 示 と 表 以 上 か ら 分 か る よ う に ，SAX は 単 純 な ア ル ゴ リ ズ ム で あ り な が ら 距 離 の 下 界 を 抑 え て い る た め マ イ ニ ン グ 精 度 が 良 く ， 距 離 の 計 算 が 高 速 で ， 文 字 列 用 に 定 義 さ れ た 手 法 も 適 用 可 能 な ど 多 く の 利 点 を 持 つ ． し か し な が ら ，SAX は 1 次 元 の 時 系 列 デ ー タ し か 扱 う こ と が 出 来 な い ．
3. Universal SAX
我 々 は 先 行 研 究 に て ， 多 次 元 空 間 内 の デ ー タ の 位 置 関 係 を 損 な う こ と な く 文 字 列 に 変 換 す る Universal SAX（ USAX）を 提 案 し た [10]．本 節 に て そ の 概 略 に つ い て 紹 介 す る ．ま ず ，多 次 元 デ ー タ を USAX 文 字 列 へ 変 換 す る 手 順 に つ い て ，図 5(1) の 2 次 元 軌 跡 状 デ ー タ T を 例 に し て 説 明 す る ． (1) T を そ れ ぞ れ の 次 元 ご と で 標 準 正 規 分 布 に 正 規 化 し ，等 間 隔 に 区 分 ，区 間 ご と の 平 均 値 を 決 定 す る （ 図 5(1)で はx0, x1, … , x10）． (2) 空 間 を 2k× 2k の 格 子 状 に な る よ う 量 子 化 し ， 空 間 充 填 曲 線 の 1 つ で あ る ヒ ル ベ ル ト 曲 線 [2] を 適 用 す る ．（ 図 5(2)． こ こ で の k は ヒ ル ベ ル ト 空 間 の 解 像 度 と な る ．） (3) (1) で 算 出 し た 平 均 値 を (2) で 適 用 し た ヒ ル ベ ル ト 曲 線 に 従 っ て そ れ ぞ れ の 値 に 変 換 す る ．（ 図 5(3)で は (51,46,40,38,27,28,10,17,15,1) ） (4) 各 文 字 の 存 在 確 率 が 等 し く な る よ う 事 前 に 決 定 し て お い た 分 割 に 従 っ て ，(3)で 求 め た ヒ ル ベ ル ト 値 を そ れ ぞ れ の 文 字 に 変 換 す る（ 図 5(4)）． USAX 文 字 列 へ の 変 換 手 順 (4)に お い て ，事 前 に 決 定 す る 各 文 字 領 域 の 分 割 は ，SAX の 手 法 に 倣 い 各 文 字 の 存 在 確 率 が 等 し く な る よ う 行 わ れ る ． し か し ， USAX で は 変 換 手 順 (1) に お い て 対 象 デ ー タ を 各 次 元 で 標 準 正 規 分 布 に 正 規 化 し て い る た め ，SAX と は 符 号 の 存 在 確 率 の 等 面 積 分 割 法 が 異 な る ． 例 え ば 図 6 左 図 の よ う な 2 次 元 空 間 に 対 し て そ れ ぞ れ の 次 元 ご と に 正 規 化 を 行 う と 存 在 確 率 は 空 間 の 中 心 に 近 付 く に つ れ 高 く な る （ 図 6 左 図 ）．こ の よ う な 空 間 に お い て ヒ ル ベ ル ト 曲 線 を 適 用 す る と ， 符 号 の 存 在 確 率 分 布 は 2 次 元 デ ー タ の 場 合 だ と 三 峰 分 布 と な る （ 図 6 右 図 ）． よ っ て USAX を 2 次 元 デ ー タ に 適 用 す る 際 に は こ の 三 峰 分 布 を 等 面 積 に 分 割 す る こ と で 各 文 字 の 存 在 確 率 を 等 し く し て い る ． こ の 実 現 の た め ， 我 々 は 乱 数 を 用 い た シ ミ ュ レ ー シ ョ ン を 複 数 回 行 う こ と に よ り 近 似 解 を 求 め る 計 算 手 法 で あ る モ ン テ カ ル ロ 法 を 用 い て 三 峰 分 布 の 等 面 積 分 割 を 行 っ て い る ． ま た ， こ の 手 法 に よ っ て 分 割 さ れ た 空 間 は ， 境 界 付 近 の 分 割 が 粗 く な り す ぎ て し ま う 傾 向 が あ る た め ， 我 々 は ブ ロ ッ ク 解 像 度 （ Br） と い う し き い 値 を 導 入 し こ の 課 題 に 対 処 し て い る ． 図 5: USAX 文 字 列 へ の 変 換 例 図 6: 2 次 元 空 間 に お け る 符 号 の 存 在 確 率 の 可 視 化 （ 左 図 ） と ヒ ル ベ ル ト コ ー ド 上 で の 符 号 の 存 在 確 率 の 可 視 化 （ 右 図 ） 以 上 の 手 順 で 作 成 さ れ る USAX 文 字 列 間 の 距 離 は ， 文 字 が 割 り 当 て ら れ て い る 多 次 元 空 間 上 の 領 域 間 の 最 小 距 離 の 合 計 に よ っ て 定 義 さ れ る ． 例 え ば ， 2 次 元 空 間 に 5 種 類 の 文 字 を 割 り 当 て る と ， そ の 空 間 は ヒ ル ベ ル ト 曲 線 に 従 っ て 5 つ の 領 域 に 分 割 さ れ る（ 図 7 (A)）．文 字 間 の 距 離 は 前 述 の よ う に こ の 領 域 間 の 最 小 距 離 に よ っ て 定 義 さ れ て い る た め ，図 7(A) に お け る マ ス 目 1 つ を 距 離 1 と し た 場 合 ， 図 7(B) の よ う な 距 離 表 と し て 算 出 し て お く こ と が 出 来 る ． こ の 距 離 表 を 用 い た 2 つ の USAX 文 字 列𝐶̂={a b d d}， 𝑄̂={c d d a}間 の 距 離 dist(Ĉ, 𝑄̂)は 3 と な る ．USAX 文 字 間 の 距 離 表 は SAX と 同 じ く あ ら か じ め 算 出 す る こ と が 可 能 で あ る た め ， 実 際 に デ ー タ 間 の 距 離 の 計 算 を 行 う と き は こ の 表 の 値 を 参 照 す る だ け で 良 い ． 図 7: (A) 2 次 元 空 間 に 5 種 類 の 文 字 を 割 り 当 て た 時 の 空 間 例 ， (B) (A) に 対 応 す る 文 字 間 の 距 離 表
4. 既 存 手 法 と の 比 較
第 2 節 に て 述 べ た SAX は ，時 系 列 デ ー タ を 効 率 よ く マ イ ニ ン グ 出 来 る 索 引 で あ る が ， 1 次 元 の 時 系 列 デ ー タ し か 扱 う こ と が 出 来 な い ．よ っ て SAX を 多 次 元 時 系 列 デ ー タ に 適 用 す る た め に ， 既 存 研 究 で は 前 処 理 と し て 多 次 元 の デ ー タ を 1 次 元 に 次 元 削 減 す る ア プ ロ ー チ が と ら れ て き た ． 本 節 で は 2 種 類 の 次 元 削 減 ア プ ロ ー チ を 適 用 後 に SAX を 適 用 す る 既 存 手 法 と ，第 3 節 に て 述 べ た USAX と の 比 較 を 行 う ． 4.1 節 で は 多 次 元 デ ー タ へ の SAX 適 用 の 既 存 研 究 の 詳 細 に つ い て ， 4.2 節 で は 既 存 手 法 と の 比 較 実 験 に つ い て 述 べ る ． 4.1 多 次 元 デ ー タ へ の SAX 適 用 の 既 存 研 究 SAX を 多 次 元 時 系 列 デ ー タ に 適 用 す る た め に ，既 存 研 究 で は 前 処 理 と し て 多 次 元 の デ ー タ を 1 次 元 に 次 元 削 減 す る ア プ ロ ー チ が と ら れ て き た ． そ の 中 に Li[8] や Tanaka[13]の 研 究 が あ る ． [8] で は 多 次 元 デ ー タ に 対 し て 重 心 距 離 法 を 用 い た 後 SAX を 適 用 し て い る ． 重 心 距 離 法 と は 軌 跡 デ ー タ や 形 状 デ ー タ の よ う な 多 次 元 デ ー タ を そ の 重 心 か ら 各 点 ま で の 距 離 を 用 い て 1 次 元 表 現 に 変 換 す る 手 法 で あ る ．Li は こ の 手 法 に よ っ て 得 ら れ た 1 次 元 表 現 に 対 し て SAX を 適 用 す る こ と に よ り ，大 規 模 画 像 デ ー タ セ ッ ト か ら 例 外 画 像 を 動 的 に 検 出 す る 手 法 を 提 案 し た ． [13] で は 多 次 元 デ ー タ に 対 し て 主 成 分 分 析 を 用 い た 後 SAX を 適 用 し て い る ．主 成 分 分 析 と は 複 数 の 変 数 か ら 成 る デ ー タ の 相 関 を 少 数 の 合 成 変 数 で 表 現 す る 手 法 で あ る ． こ の 手 法 で 表 現 さ れ る 合 成 変 数 は 必 要 に 応 じ て 次 元 数 を 調 節 す る こ と が 出 来 る ． ま た 第 一 主 成 分 に 一 番 多 く の 情 報 量 が 含 ま れ る と い う 性 質 上 ， 扱 う デ ー タ に よ っ て は 第 一 主 成 分 の み を 使 用 す れ ば 十 分 で ， 多 く の デ ー タ 量 を 削 減 す る こ と が 出 来 る ．Tanaka は こ の 手 法 を 用 い て モ ー シ ョ ン セ ン サ か ら 得 た 3 次 元 セ ン サ デ ー タ を 1 次 元 表 現 に 変 換 し ， そ の デ ー タ に 対 し て SAX を 適 用 す る こ と に よ り 動 的 に 未 知 頻 出 パ タ ー ン を 検 出 す る 手 法 を 提 案 し た ． こ れ ら の 手 法 は ど ち ら も 多 次 元 デ ー タ を SAX に 適 用 す る た め に 次 元 削 減 を 行 っ て い る こ と に 注 意 し た い ． 更 に ， こ れ ら の 手 法 は 対 象 デ ー タ の 特 徴 や 使 用 用 途 に よ っ て は 次 元 削 減 を 行 っ て い て も 有 効 に 機 能 す る こ と が 各 論 文 に て 示 さ れ て い る が ， 次 元 削 減 を 行 う こ と に よ っ て 情 報 が 著 し く 欠 落 す る よ う な デ ー タ も 存 在 す る ． 重 心 距 離 法 は 前 述 の よ う に 重 心 か ら デ ー タ の 各 値 ま で の 距 離 を 使 用 し て 時 系 列 状 1 次 元 デ ー タ に 変 換 し て い る ． 従 っ て 元 デ ー タ に お い て 重 心 か ら の 距 離 が 等 し い 異 な る 値 は 全 て 同 じ 情 報 と し て 扱 わ れ る と い う 特 徴 を 持 つ ． こ の 特 徴 は 軌 跡 情 報 な ど 絶 対 的 な 位 置 を 必 要 と す る デ ー タ の 場 合 に 情 報 を 著 し く 欠 落 さ せ る 原 因 と な る ． 例 え ば ， 同 じ 速 度 で 異 な る 方 向 に 動 く 2 つ の 多 次 元 軌 道 状 デ ー タ を 考 え る（ 図 8）．こ の よ う な デ ー タ に 対 し て 重 心 距 離 法 を 適 用 す る と ， 重 心 か ら 各 値 ま で の 距 離 推 移 が ど ち ら も ほ ぼ 同 じ に な る ． よ っ て 元 デ ー タ 上 で の 軌 跡 の 傾 き は 異 な る に も か か わ ら ず 1 次 元 変 換 後 の 値 の 推 移 が ほ ぼ 同 じ と な っ て し ま う ． 図 8: 重 心 距 離 法 が 有 効 に 働 か な い 例 ま た 主 成 分 分 析 は ，SAX に 適 用 さ せ る と い う 目 的 を 達 成 す る た め に 第 一 主 成 分 の み を 使 用 し て 1 次 元 化 を 行 う が ， こ の 第 一 主 成 分 の 寄 与 率 が 低 い 場 合 ， 元 デ ー タ の 情 報 が 欠 落 す る ． な ぜ な ら 第 一 主 成 分 の 寄 与 率 が 低 い と い う こ と は ， 言 い 換 え れ ば 第 二 主 成 分 以 下 の 部 分 空 間 に 元 デ ー タ の 特 徴 が 多 く 表 れ て い る と い う こ と で あ る ． こ れ は マ イ ニ ン グ 時 の 誤 検 出 を 引 き 起 こ す ． 主 成 分 分 析 は 適 用 前 に 一 度 全 て の デ ー タ を 同 じ 空 間 に マ ッ ピ ン グ す る 必 要 が あ る た め ， こ の 問 題 は 大 き な デ ー タ セ ッ ト を 扱 う 際 に よ く 発 生 す る ．例 え ば ，図 9 の 左 部 の よ う な 4 つ の 異 な る 特 徴 を 持 つ デ ー タ セ ッ ト を 考 え る ． こ れ ら の デ ー タ セ ッ ト に 対 し て 主 成 分 分 析 を 適 用 す る た め に ， デ ー タ を 同 じ 空 間 に マ ッ ピ ン グ し た結 果 が 図 9 の 右 で あ る ． 元 の そ れ ぞ れ の デ ー タ が 持 つ 特 徴 の な い ， 相 関 の 乏 し い デ ー タ と し て 表 現 さ れ て い る こ と が 見 て と れ る ． 従 っ て 第 一 主 成 分 の 寄 与 率 は 低 く な る ． 図 9: 主 成 分 分 析 が 有 効 に 働 か な い 例 4.2 既 存 手 法 と の 比 較 実 験 本 項 で は USAX と 既 存 手 法 と の 比 較 実 験 の 結 果 に つ い て 述 べ る ． 我 々 は 実 験 に 2 種 類 の デ ー タ セ ッ ト を 使 用 し た ． 1 つ 目 の デ ー タ セ ッ ト は 疑 似 的 に 生 成 さ れ た 3 次 元 時 系 列 デ ー タ で あ る ． こ の デ ー タ は 進 む 方 向 に よ っ て 4 種 類 に 分 類 さ れ る ．図 10 は デ ー タ を 可 視 化 し た も の で あ る ． そ れ ぞ れ {data0a, data0b}， {data1a, data1b}, {data2a, data2b}, {data3a, data3b} を 同 グ ル ー プ と し て 扱 っ た ．
図 10: 実 験 に 使 用 し た 疑 似 3 次 元 時 系 列 デ ー タ 2 つ 目 の デ ー タ セ ッ ト は UCI[12]の Machine Learning Repository 中 の Character Trajectories Data Set で あ る ． こ の デ ー タ は 2858 個 の 実 際 の 筆 跡 デ ー タ セ ッ ト で ， ペ ン タ ブ レ ッ ト に よ る 入 力 を 軌 跡 （ x 軸 と y 軸 ） と 筆 圧 （ z 軸 ） か ら な る 3 次 元 の デ ー タ と し て 取 得 し た も の で あ る ． 当 レ ポ ジ ト リ に 関 す る 各 時 系 列 デ ー タ の 説 明 が 見 つ か ら な か っ た た め ， 我 々 は こ の デ ー タ セ ッ ト 内 か ら 視 覚 的 に 類 似 し て い る と 思 わ れ る 4 グ ル ー プ（ 1 グ ル ー プ に 2 個 の デ ー タ ）を 抽 出 し た ．図 11 は デ ー タ の 一 部 を 視 覚 化 し た も の で あ る ． {data1, data2} ，
{data101, data102}, {data151, data152}, {data231, data232} が そ れ ぞ れ 視 覚 的 に 類 似 し た も の と 判 定 し た ．
図 11: 実 験 に 使 用 し た Character Trajectories Data Set の 一 部 4.2.1 節 で は 文 字 列 変 換 後 の デ ー タ 量 の 比 較 実 験 と USAX に お け る 距 離 表 作 成 時 間 の 測 定 結 果 に つ い て ， 4.2.2 節 で は 既 存 手 法 と の 符 号 表 現 変 換 精 度 を 比 較 す る た め 行 っ た ク ラ ス タ リ ン グ 実 験 の 結 果 に つ い て 述 べ る ． 4.2.1 デ ー タ 量 の 比 較 と 距 離 表 作 成 時 間 の 計 測 本 項 で は 2 つ の 実 験 の 結 果 に つ い て 述 べ る ． 1 つ 目 の 実 験 で は ， 元 デ ー タ の デ ー タ 容 量 と 比 較 手 法 （ 重 心 距 離 法 (CDM)と 主 成 分 分 析 (PCA)）を 適 用 後 SAX 文 字 列 に 変 換 し た あ と の デ ー タ 容 量 ，そ し て USAX を 適 用 後 の デ ー タ 容 量 の 比 較 を 行 っ た ．比 較 手 法 と USAX に つ い て は ， そ れ ぞ れ に 文 字 列 圧 縮 （ 今 回 は ラ ン レ ン グ ス 圧 縮 を 使 用 ） を 適 用 後 の デ ー タ 容 量 と も あ わ せ て 比 較 し た ．こ の 実 験 に は Character Trajectories Data Set を 使 用 し た ． 実 験 に 使 用 さ れ た 各 パ ラ メ ー タ は 以 下 の 通 り で あ る ．比 較 手 法 の SAX の 文 字 種 類 は 8 に 設 定 し た ． USAX の 文 字 種 類 は ， 比 較 手 法 と 条 件 を 同 じ に す る た め83 = 512 と 設 定 し た ． 実 験 の 結 果 を 図 12 に 示 す ． 結 果 か ら ，USAX は 元 デ ー タ の 約 1/40 の 容 量 に 削 減 で き て い る こ と が 分 か る ． 更 に 文 字 列 の 圧 縮 を 行 う と 容 量 は 約 1/54 に ま で 削 減 で き て い る ．ま た ，比 較 手 法 は そ れ ぞ れ USAX の 約 1/2 の 容 量 で 文 字 列 化 を 行 っ て い る こ と も 分 か る ． し か し USAX は 比 較 手 法 の 64 倍
の 文 字 種 類 を 使 用 し た 高 解 像 度 な 文 字 列 化 を 行 っ て い る に も か か わ ら ず そ の デ ー タ 容 量 が 高 々 2 倍 に 収 ま っ て い る と い う 点 に 注 意 し て 下 さ い ． こ れ は ， 比 較 手 法 が ど ん な に 少 な い 文 字 種 類 を 使 用 し て も 1 文 字 の 表 現 に 必 ず 1 バ イ ト を 使 用 す る の に 対 し て ， USAX は 2 バ イ ト で 収 ま る ほ ど の 文 字 種 類 を 使 用 し て 文 字 列 化 を 行 っ て い る か ら で あ る ． 従 っ て ， こ の 実 験 結 果 は USAX が 充 分 に 小 さ な デ ー タ 容 量 で 精 度 の 高 い 文 字 列 化 を 行 う こ と が 出 来 る と い う こ と を 示 し て い る ． 図 12: デ ー タ 量 比 較 実 験 結 果 の 可 視 化 2 つ 目 の 実 験 で は ， 距 離 表 の 作 成 時 間 の 測 定 を 行 っ た ． 実 験 時 の 各 パ ラ メ ー タ と 測 定 結 果 を 表 1 に 示 す ． こ の 表 か ら ，2 次 元 デ ー タ の 距 離 表 作 成 に は 1，2 秒 程 度 の 時 間 し か 必 要 と し な い こ と が 分 か る ． 更 に ， 3 次 元 デ ー タ の 場 合 で も 十 数 分 で 作 成 す る こ と が 出 来 る こ と が 分 か る ． 第 4 節 で 述 べ た よ う に ， こ の 距 離 表 は 一 度 だ け 作 成 す れ ば よ く ， 実 際 に 距 離 を 比 較 す る 際 に は 表 を 参 照 す る だ け で あ る ． よ っ て こ の 実 験 結 果 は ， USAX で 使 用 さ れ る 距 離 表 の 作 成 時 間 が 十 分 高 速 で あ る と い う こ と を 示 し て い る ． 表 1: 距 離 表 作 成 時 間 の 測 定 結 果 解 像 度 文 字 数 Br 作 成 時 間 [ms] 9 16 7 1320 2 dim 9 64 6 1830 9 144 6 2560 9 64 7 5991 3 dim 9 512 6 209930 9 1728 6 708923 4.2.2 ク ラ ス タ リ ン グ 結 果 の 比 較 本 項 で は ， 疑 似 3 次 元 時 系 列 デ ー タ セ ッ ト と
Character Trajectories Data Set を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 結 果 に つ い て 述 べ る ． こ の 実 験 で は 元 デ ー タ ，比 較 手 法 2 種 を 適 用 し た 後 に SAX を 適 用 し た 文 字 列 ， USAX を 適 用 し た 文 字 列 の 計 4 つ を ク ラ ス タ リ ン グ 対 象 と し た ． 実 験 に 使 用 し た パ ラ メ ー タ は 4.2.1 節 の 実 験 と 同 じ で あ る ． 疑 似 3 次 元 時 系 列 デ ー タ を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 実 験 結 果 を 図 13 に 示 す ． こ の 図 か ら ， 唯 一 USAX だ け が 元 デ ー タ と 同 等 の 結 果 を 得 て い る こ と が 分 か る ． な ぜ な ら こ の デ ー タ セ ッ ト は 相 関 が 弱 く ， 各 デ ー タ の 重 心 か ら 各 値 ま で の 距 離 が 等 し く な る よ う な 動 き を す る と い う 特 徴 を も つ か ら で あ る ． こ の よ う な デ ー タ セ ッ ト を 比 較 手 法 が 苦 手 と し て い る こ と は 3 節 に て 述 べ て い る ． 重 心 距 離 法 に 至 っ て は 階 層 的 ク ラ ス タ リ ン グ を 行 う こ と も 出 来 な か っ た ． 主 成 分 分 析 に 関 し て は ， 苦 手 な 特 徴 を も つ デ ー タ セ ッ ト に 対 し て 適 用 し た こ と で 1 次 元 化 後 の 寄 与 率 が 低 く な っ て し ま い ， 多 く の 情 報 が 欠 落 し た こ と が 原 因 で あ る と 考 え ら れ る ． 図 13: 疑 似 3 次 元 時 系 列 デ ー タ を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 実 験 結 果
次 に Character Trajectories Data Set を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 実 験 結 果 を 図 14 に 示 す ． 図 か ら 分 か る よ う に ， ど の 手 法 も 元 デ ー タ と 同 程 度 の 結 果 を 得 て い る ． こ れ は ， こ の デ ー タ セ ッ ト が 強 い 相 関 を も ち 各 デ ー タ の 重 心 か ら 各 値 ま で の 距 離 が 異 な る よ う な 動 き を す る と い う 特 徴 を も つ か ら で あ る ． つ ま り 比 較 手 法 に 有 利 な デ ー タ セ ッ ト と い う こ と に な る が ， に も か か わ ら ず USAX も 有 効 に 働 い て い る こ と が 分 か る ． 以 上 の 実 験 結 果 か ら ，USAX は ど ん な デ ー タ セ ッ ト で も 効 果 的 に 文 字 列 に 変 換 す る こ と の で き る 手 法 で あ る と い え る ． 91.99 67.62 95.83 58.83 193.61 147.75 7946.14 0 50 100 150 200 250 7900[KB]
図 14: Character Trajectories Data Set を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 実 験 結 果
5. 高 次 元 デ ー タ へ の USAX の 適 用
5.1 デ ー タ の 高 次 元 化 に 伴 う 課 題 多 次 元 時 系 列 デ ー タ の 文 字 列 化 を 行 う USAX で は ， デ ー タ の 高 次 元 化 に 伴 い 以 下 の 3 つ の 課 題 が 生 じ る ． 必 要 な 文 字 の 種 類 の 増 大 例 え ば 4 次 元 の デ ー タ に 対 し て ， 各 次 元 が 8 分 割 と な る よ う 分 割 し た 場 合 に 必 要 な 文 字 数 の 目 安 は 84=4096 種 類 で あ る ． 一 方 ア ル フ ァ ベ ッ ト は 大 文 字 と 小 文 字 を 区 別 し た と し て も 52 種 類 し か 存 在 せ ず ，必 要 な 符 号 数 に は 全 く 足 り な い ．こ の 課 題 の 解 決 策 と し て ， USAX で は 文 字 デ ー タ を 一 度 バ イ ナ リ 化 し BASE64 を 適 用 し て い る ．BASE64 と は ，バ イ ナ リ デ ー タ を 64 種 類 の 英 数 字 の み を 用 い て エ ン コ ー ド す る 方 式 で あ る ． し か し 前 述 の よ う に USAX 文 字 列 化 に 必 要 な 文 字 種 類 は 次 元 が 高 く な る に つ れ 指 数 関 数 的 に 増 大 す る た め ， 高 次 元 の デ ー タ に は 対 応 で き な い ． 距 離 表 の サ イ ズ の 増 大 距 離 表 は 使 用 す る 文 字 数 の 全 組 み 合 わ せ 分 の 大 き さ と な る た め ， 例 え ば ， 先 ほ ど と 同 様 に 4 次 元 の デ ー タ 用 の 距 離 表 を 作 成 す る 際 の 距 離 表 の サ イ ズ は 4096 ×4096=16777216 と な り ，そ の デ ー タ 容 量 は 約 57.6MB に な る（ 表 2）．よ っ て ，29 次 元 な ど よ り 高 次 元 の デ ー タ 用 の 距 離 表 を 作 成 す る た め に 必 要 な 容 量 は 表 3 の 予 想 値 か ら 判 断 し て 現 実 的 で は な い と い え る ． こ の 課 題 の 解 決 策 と し て ， 距 離 表 の 容 量 に し き い 値 を 設 定 し ， そ の し き い 値 を 超 え る よ う で あ れ ば 距 離 計 算 を キ ャ ッ シ ュ 方 式 に 変 更 す る と い う 対 応 や ， 出 現 確 率 の 高 い 文 字 同 士 の 距 離 計 算 の み 事 前 に 行 っ て お き ， そ れ 以 外 の 文 字 同 士 の 距 離 は 必 要 に な っ た 時 に 行 い キ ャ ッ シ ュ と し て 保 存 し て お く な ど の 対 応 が 考 え ら れ る ． し か し こ れ ら は 本 質 的 な 課 題 解 決 に は な ら な い ． 表 2: 距 離 表 の デ ー タ 容 量 の 比 較 データ容 量 1dim 434[B] 4dim 57.6[MB] 29dim(予 想 値 ) 1.72× 3 [TB] 次 元 の 呪 い 高 次 元 デ ー タ の 信 頼 性 が 次 元 の 呪 い に よ り 低 く な っ て し ま う 点 で あ る ． 次 元 の 呪 い と は ． 高 次 元 の デ ー タ ほ ど デ ー タ 間 の 距 離 が 互 い に 等 し く な っ て し ま い 汎 化 誤 差 が 向 上 し な く な る 現 象 の こ と で あ る ． つ ま り そ も そ も 高 次 元 の デ ー タ に 対 し て 直 接 USAX を 適 用 す る こ と は 有 効 で な い と 考 え ら れ る ． 5.2 USAX と 次 元 圧 縮 の 併 用 5.1 節 で 述 べ た 3 つ の 課 題 を 解 決 す る た め に ， 我 々 は 高 次 元 デ ー タ に つ い て 以 下 の 手 順 を 行 う こ と を 提 案 す る ． (1) 高 次 元 の デ ー タ に 対 し て 主 成 分 分 析 を 適 用 し ， し き い 値 以 上 の 累 積 寄 与 率 を も つ 次 元 ま で 次 元 を 削 減 す る ． (2) USAX を 適 用 し 1 次 元 の 文 字 列 デ ー タ に 変 換 す る ． 主 成 分 分 析 と USAX の 組 み 合 わ せ に よ り ，高 次 元 デ ー タ の 次 元 を 1 次 元 に ま で デ ー タ 圧 縮 し ， か つ 元 デ ー タ 空 間 中 の 位 置 関 係 情 報 を 損 失 が 少 な い 索 引 に な る と 考 え ら れ る ． 実 際 に ， 我 々 は 上 記 の 手 順 を 用 い て 高 次 元 デ ー タ に 対 す る 階 層 的 ク ラ ス タ リ ン グ 作 成 実 験 を 行 っ た ． 実 験 に 使 用 し た デ ー タ は CMU[3] の Graphics Lab Motion Capture Database の Mocap デ ー タ セ ッ ト で あ る ． こ の デ ー タ セ ッ ト は 2431 個 の モ ー シ ョ ン キ ャ プ チ ャ デ ー タ セ ッ ト で ，人 間 の 様 々 な 動 作 を 29 次 元 の デ ー タ と し て 取 得 し た も の で あ る ．図 15 は 走 る 動 作 の 動 画 の 一 部 で あ る ．我 々 は こ の デ ー タ セ ッ ト の 中 か ら ，歩 く ，走 る ， ジ ャ ン プ す る の 3 グ ル ー プ （ 1 グ ル ー プ に 3 個 の デ ー タ ） を 抽 出 し 実 験 に 使 用 し た ． 図 15: Mocap デ ー タ セ ッ ト の 動 画 の 一 部先 述 し た よ う な USAX と 主 成 分 分 析 を 併 用 す る 手 法 の 有 効 性 を 検 証 す る た め ， 我 々 は 以 下 の 2 つ の 表 現 で 階 層 的 ク ラ ス タ リ ン グ 作 成 実 験 を 行 っ た ．SAX 適 用 時 の 文 字 種 類 は 7， USAX 適 用 時 の 文 字 種 類 は 2048， 解 像 度 が 9， Br が 6 で あ る ． 1. 1 次 元 ま で 次 元 削 減 し た あ と SAX を 適 用 し た 文 字 列 デ ー タ 2. 4 次 元 ま で 次 元 削 減 し た あ と USAX を 適 用 し た 文 字 列 デ ー タ （ 累 積 寄 与 率 の し き い 値 は 80%に 設 定 ） 実 験 の 結 果 を 図 16 に 示 す ． 線 で 囲 っ た デ ー タ が 正 解 と み な し た デ ー タ で あ る ．
図 16: Graphics Lab Motion Capture Database の デ ー タ セ ッ ト を 使 用 し た 階 層 的 ク ラ ス タ リ ン グ の 実 験 結 果 結 果 を 見 て 分 か る よ う に ，高 次 元 デ ー タ に 対 し て 次 元 削 減 を 行 っ た 後 USAX を 適 用 し た 場 合 の 方 が 優 れ た 結 果 を 得 た ． こ の 結 果 を も た ら し た 理 由 は ， 主 成 分 分 析 に よ る 次 元 削 減 時 の 累 積 寄 与 率 の 差 に よ る も の と 考 え ら れ る ． こ の デ ー タ セ ッ ト の 場 合 ， 1 次 元 ま で 削 減 し た と き の 累 積 寄 与 率 は 約 37%で あ る の に 対 し て ， 4 次 元 ま で 削 減 し た と き の 累 積 寄 与 率 は 約 84%で あ る（ 図 17）． つ ま り 1 次 元 ま で 削 減 し た 場 合 の デ ー タ よ り 2 倍 以 上 の 特 徴 を 維 持 し て い る た め そ の 後 の 文 字 列 化 の 精 度 に も 影 響 し た と 考 え る こ と が 出 来 る ． こ の 結 果 か ら ，提 案 手 法 で あ る USAX は 高 次 元 デ ー タ に 対 し て も 有 効 な 索 引 で あ る と い え る ．
図 17: Graphics Lab Motion Capture Database の デ ー タ セ ッ ト に 主 成 分 分 析 を 適 用 し た 際 の 累 積 寄 与 率
6. ま と め と 今 後 の 課 題
本 稿 で は ， 空 間 充 填 曲 線 を 用 い て 多 次 元 空 間 内 の デ ー タ の 位 置 関 係 を 損 な う こ と な く 文 字 列 に 変 換 す る Universal SAX （ USAX） の 評 価 実 験 と ， よ り 高 次 元 の デ ー タ へ の 適 用 手 法 の 提 案 と 適 用 実 験 に つ い て 述 べ ， USAX は 既 存 の 手 法 よ り も 多 次 元 時 系 列 デ ー タ の マ イ ニ ン グ に 有 効 な 索 引 で あ る こ と を 示 し た ． 今 後 は ， 提 案 手 法 の 改 良 と そ れ に 伴 う 評 価 実 験 を 行 っ て い く ． 多 次 元 空 間 を 区 分 す る ア プ ロ ー チ は ヒ ル ベ ル ト 曲 線 以 外 に も 多 く の 種 類 が あ る た め ， そ れ ら の 手 法 を 検 討 し ， よ り 有 効 な 変 換 手 法 を 模 索 す る ．
参 考 文 献
[1] Apostolico A, Bock M. E, and Lonardi, S. : Monotony of Surprise and Large-Scale Quest for Unusual Words. In proceedingsof the 6th Int’l Conference on Research , " In Computational Molecular Biology, 2002 Washington, DC, April 18-21. pp 22-31.
[2] Christos FALOUTSOS. : 5.1 SPACE FILLING CURVES, " In SEARCHING MULTIMEDIA DATABASES BY CONTEXT , 1996, pp27 -34. [3] CMU : http://mocap.cs.cmu.edu/ ， January, 2013. [4] Dengsheng Zhang and Guojun Lu. : Review of shape
representation and description techniques, " In Pattern Recognition, Vol. 37, 2004.
[5] D. Hilbert. :Über die stetige Abbildung einer Linie auf ein Flächenstück, " In Math. Ann. 38, 1891, pp459-460.
[6] J.A. Orenstein. :Spatial query processing in an object-oriented database system, " In SIGMOD, 1986, pp326-336.
[7] Jessica Lin, Eamonn Keogh, Stefano Lonardi ， and Bill Chiu. : A Symbolic Represent ation of Time Series, with Implications for Streaming Algorithms," In SIGMOD workshop, 2003.
[8] Li Wei, Keogh, E. and Xiaopeng Xi. : SAXually Explicit Images: Finding Unusual Shapes," In the IEEE International Conference on Data Mining series (ICDM), 2006.
[9] Lonardi, S. : Global Detectors of Unusual Words: Design, Implementation, and Applications to Pattern Discovery, " In Biosequences. PhD thesis, Department of Computer Sciences, Purdue University, August, 2001.
[10] 大 西 史 花 ， 渡 辺 知 恵 美 : “ Universal SAX: 空 間 充 填 曲 線 を 利 用 し た SAX の 多 次 元 時 系 列 デ ー タ へ の 適 用 ,” 第 4 回 デ ー タ 工 学 と 情 報 マ ネ ー ジ メ ン ト に 関 す る フ ォ ー ラ ム (DEIM2012), 2012. [11] Sven Loncaric. : A survey of shape analysis
techniques, " In Pattern Recognition, Vol. 31, 1998. [12] UCI : http://archive.ics.uci.edu/ml/index.html
February, 2012.
[13] Yoshiki Tanaka and Kuniaki Uehara. : D iscover Motifs in Multi Dimensional Time -Series Using The Principal Component Analysis And The MDL Principle, " In Workshop on Machine Learning and Data Mining in Pattern Recognition(MLDM), 2003.
