パーシステントホモロジーによる多次元ファジィ集合の同定

修 士 論 文 和 文 要 旨 研究科 専攻 大学院 情報理工学研究科 情報 ッ ワ 工学専攻 博士前期課程 氏 原田 貴史 学籍番号 1631121 論 文 題 目 パ ン モロ 多次元 ァ 集合 定 要 旨 ラ ニン を用い 多変量 多次元 タを解析した タ ラッ ッ い 問題 あ こ 人 理解し タを編集す 上 大 阻害 い そこ 多変量 多次元 タを人 感覚を反映した タへ 解析す 手法 し 多次元 ァ 集合 あ 既存手法 タ ッ ワ 構造を作成す こ 幾何学構造を保存し ッ ワ 構造上 タ 分布密度を計算し 多次元 ァ 集合を生成し い 人 感覚を反 映す た サン ル密度を計算す た 閾値_� 幾何学構造を保存す た 閾値_��を 決定す 必要 あ 既存手法 手動 模索し閾値を導出し いた 本研究 パ ン モロ を用い 幾何学構造を 定し 閾値_{� , ��}を導出す こ 自動 多次元 ァ 集合を生成し 手動 求 た閾値 生成した多次元 ァ 集合 比較検討を行 た モロ 群 単体複体 呼 対し 各次元 大域的 具合を表す あ 1_{次元 連結成分 2 次元 穴 3 次元 わ 穴 関連した幾何学的} 意味を持 パ ン モロ 単体複体 増大列を用い こ モロ 群 生成さ た時間_{� 消滅した時間�を計算す 手法 あ} こ 対象 モロ 群 生 成元 遷移を特徴 け こ 本研究 パ ン モロ 群 中 生存時間 短い要素を 考え 重み関 数 重み付けを行 た 二 閾値_{� , ��}を 重み 付いたパ ン モロ 群 0 _{次 元 モ ロ を 除 生 存 時 間 中 点 重 み 付 平 均}� = ∑_{�=1 �} �_�+ �� / 2 ∑�=1 � 消滅時間 重み付 平均��= ∑�=1 � ��/∑�=1 � した こ タ 幾何学構造を保存し 閾値を導出す こ た 導出した閾値 手動 求 た閾 値を用い 比較実験を行い有用性を確認した

電気通信大学情報理工学研究科 情報・ ネ ッ ト ワ ーク 工学専攻情報数理工学プロ グラ ム 修士論文

パーシステン ト ホモロ ジーによ る

多次元フ ァ ジィ 集合の同定

平成 30 年 3 月 13 日

情報数理工学プロ グラ ム

学籍番号

1631121

原田貴史

指導教員 緒方 秀教 村松 正和 助言 西野 順二

目 次

第 1 章 序論 2 1.1 研究の背景と 目的 . . . 2 1.2 研究の概要 . . . 3 第 2 章 多次元フ ァ ジィ 集合 5 2.1 フ ァ ジィ 理論 . . . 5 2.2 フ ァ ジィ 集合 . . . 5 2.3 多次元フ ァ ジィ 集合 . . . 6 2.4 既存手法 . . . 6 2.4.1 幾何学的構造を 保存する ための閾値 ϵM . . . 7 2.4.2 サン プル密度を 計算する ための閾値 ϵF . . . 7 2.5 各閾値の算出 . . . 7 2.5.1 課題 1:幾何学構造を 保存する ための閾値 ϵM . . . 7 2.5.2 メ ン バーシッ プ値の分布分析 . . . 10 2.5.3 課題 2:サン プル密度を 計算する ための ϵF . . . 12 第 3 章 パーシステン ト ホモロジー 16 3.1 ホモロ ジー群 . . . 16 3.2 パーシステン ト ホモロ ジー群 . . . 17 第 4 章 パーシステン ト ホモロジーによ る 多次元フ ァ ジィ 集合生成手法 20 4.1 提案手法 . . . 20 4.2 比較実験 . . . 23 4.2.1 実験設定 . . . 23 4.2.2 実験結果 . . . 23 4.2.3 考察 . . . 29 第 5 章 結論と 今後の展望 30 5.1 結論 . . . 30 5.2 今後の課題 . . . 30

第

1

章 序論

1.1

研究の背景と 目的

近年、 計算機の進歩によ り ビッ グデータ と いう 複雑で膨大なデータ が得ら れる よ う になっ て き た。 こ のビッ グデータ を 活用する ために、 ディ ープラ ーニン グと いっ た機械学習によ る 解析 が行われて いる が、 解析手法によ っ て は解析し たデータ が、 人が見て も 理解でき ないブラ ッ ク ボッ ク スになっ て いる 場合がある 。 ビッ グデータ の解析を 理解し 有効活用する には、 人の感覚 で理解でき る よ う な 手法が必要である 。 人の感覚を システムに反映する 理論と し て 、 フ ァ ジィ 理論 [1][2] と いう も のがある 。 フ ァ ジィ 理論は人が関係する システムを 運用する ために、 ザデーが 1965 年に提案し たも のである 。 フ ァ ジィ 理論の基礎と なる フ ァ ジィ 集合では、 データ がある 集合に属する 度合いである メ ン バーシッ プ値と いう も のが与え ら れる 。 こ のメ ン バーシッ プ値によ っ て データ のあいま いさ やデータ に 対する 人の感覚が示さ れる 。 フ ァ ジィ 集合は多く の場合、 一次元のデータ から 変換さ れて 生成 さ れて おり 、 従来の多次元データ のフ ァ ジィ 集合は、 一次元フ ァ ジィ 集合と その直積によ っ て 表さ れて き た。 し かし ながら 、 こ の方法では多次元かつ多変量空間において は、 組み合わせが 多く なり 複雑なも のを 表すのが困難になっ て いる 。 こ れに対し 糟谷ら が多次元な問題に対し て 自然な 多次元のフ ァ ジィ 集合を 定義する 方法 [3][4][5] を 提案し て いる 。 問題の表現空間の変数 が多数である よ う な複雑問題に対する 、 フ ァ ジィ 集合によ る アプロ ーチを こ のへんフ ァ ジィ と 呼ぶ [6]。 糟谷ら が提案し た手法は、 モデリ ン グ対象のラ ン ダムサン プリ ン グデータ を も と に幾何学的 な 構造を 保存し な がら 空間中のサン プル密度に も と づき フ ァ ジィ 集合を 構成する 手法である 。 こ の手法では、 サン プル点同士の近傍点を パス でつな ぐ こ と で、 ネ ッ ト ワ ーク 構造を 構成し 、 幾何学的構造を 保存し て いる 。 こ の手法によ り 、 n 次元ユーク リ ッ ド 空間に分布し たサン プル 点に大域的な幾何的構造を 与え る こ と ができ 、 幾何学的構造を 保存する こ と で、 よ り 人の感覚 に近い多次元フ ァ ジィ 集合ができ る と 考え ら れて いる 。 し かし 、 糟谷ら が提案し た手法では、 幾何学構造を 保存する ための閾値 ϵM を 手動で求める 必要がある 。 手動で編集する こ と で、 人の感覚に近い幾何学構造を 保存する こ と ができ る が、 人が多次元空間を 認識する こ と は難し く 、 その調整が困難である 。 ま た、 閾値の値によ っ て は 全点が孤立し てし ま う 場合や、 全点同士が結合し てし ま う よ う なネッ ト ワ ーク を 作っ てし ま い、 ネ ッ ト ワ ーク 構造を 構成する 意味がな く な っ て し ま う 可能性がある 。 ま た、 こ の手法では、 サン プル密度を 計算する ための閾値も 手動で編集する 値と なっ ている 。 サン プル密度は、 ある 点における 自身を 含めた近傍点の個数を 、 全点における 近傍点の個数の 最大値で除し たも のであり 、 こ れを フ ァ ジィ 集合に属する 度合いである メ ン バーシッ プ値と し て いる 。 よ っ て 、 こ のサン プル密度を 計算する 閾値によ っ て フ ァ ジィ 集合の値は決定づけら れ

合と し て 、 人の感覚を 反映し やすく なる が、 こ の閾値も 問題に対し て 、 極端に大き く も し く は 小さ い値を と っ た場合に、 サン プル密度が全点において 同じ も し く は一部の点に大き く 偏る こ と がある 。 こ れはデータ に対し て 人の感覚を 反映でき て いない可能性があり 、 ま たシステムと し て 扱い辛い集合と な る 。 こ れに対し 、 原田ら によ っ て パーシステン ト ホモロ ジーによ る 多次元フ ァ ジィ 集合の生成が 提案さ れて る [7][8]。 こ の手法では最も よ く 現れる 幾何学構造し か保存でき て おら ず、 データ に 含ま れる よ り 多く の幾何学構造を 考慮する 必要がある と 考え ら れる 。 こ こ ま での経緯を ま と める と 以下のよ う にな る 。 1. 多次元フ ァ ジィ 集合の提案（ 西野） 2. サン プル密度によ る 自動生成 3. ネ ッ ト ワ ーク 距離によ る 改善（ 糟谷） 4. パーシステン ト ホモロ ジーによ る 改善（ 本研究 原田） よ っ て 、 本研究の目的は、 先行研究の問題点を 改善する ために、 二つの閾値、 幾何学構造を 保存する ための閾値、 サン プル密度を 計算する ための閾値に対し て 、 妥当な値を 導出する 方法 を 提案する こ と である 。

1.2

研究の概要

糟谷ら が提案し た手法における 、 手動で決定する 二つの閾値の問題点はそれぞれ、 値の取り 方によ っ て 極端なデータ 構造を 生成し て し ま う こ と である 。 そこ でデータ の幾何学的構造を 同 定し 、 そこ から 二つの閾値を 導出する 方法を 提案する 。 幾何学構造を 同定する 手段と し て 、 ホモロ ジー群がある 。 ホモロ ジー群はデータ の各次元に 対応し て 、 1 次元では連結数、 2 次元では穴、 3 次元ではわっ かなど 、 各次元の穴に相当する 幾 何学的特徴を 捉え る も のである [9][10]。 本研究で用いる サン プル点データ の場合、 ホモロ ジー 群を 計算する 際に、 n 次元空間の一般の位置にある n + 1 個の点の集ま り によ る 単体を 生成し 、 その単体の集ま り である 単体複体を 構成する 。 計算ホモロ ジー群はこ の単体複体と 穴を 計算手 続き によ っ て 導出する 。 本研究の対象データ はサン プル点データ である 、 よ っ て 単体を 生成す る 際、 ある 点と ど の位置にある 点の集ま り を 単体と し て みなすか閾値を 決める 必要がある 。 そ こ で、 その閾値の変化と ホモロ ジー群の遷移を 確認する 計算手法と し て パーシステン ト ホモロ ジー [11][12] を 用いる 。 パーシステン ト ホモロ ジーでは、 どの異なる 点同士を 単体する かと いう 閾値を 、 ある 初期値から ある タ イ ムステッ プ毎に増加さ せて いき 、 それぞれの閾値でのデータ のホモロ ジー群を 計算する 。 こ の手法によ っ て、 ホモロ ジー群の値がどの閾値で生成さ れ初め、 ど の閾値では消滅し たのか確認する こ と ができ る 。 こ れによ っ て 、 単体を 生成する 閾値の変化 と 幾何学構造と の関係がわかる 。 こ のよ う なホモロ ジー群の生成と 消滅を 表し たも のを パーシ ステン ト 図と 呼ぶ。 パーシステン ト 図では、 一部のホモロ ジー群では生成さ れたタ イ ムステッ プと 、 消滅し たタ イ ムステッ プが非常に近いも のも 生成さ れる 。 こ の点はノ イ ズである 可能性が高いため、 他の

点と 区別する 必要がある 。 よ っ て こ のノ イ ズを 区別する ために先行研究の手法を 用いて 重み付 け を 行う 。 そし て 、 重み付けを 行われたパーシステン ト 図に対し て 、 ホモロ ジー群の生成と 消 滅時刻の重み付き 平均を 計算し 、 その点を 幾何学構造を 保存する ための閾値と する 。 同様に 、 ホモロ ジー群の消滅時刻の重み付き 平均を 計算し 、 その点を サン プル密度を 計算する 閾値と す る こ と を 提案し た。

第

2

章 多次元フ ァ ジィ 集合

2.1

フ ァ ジィ 理論

フ ァ ジィ 理論と は、 フ ァ ジィ 集合、 フ ァ ジィ 論理、 フ ァ ジィ 測度を コ アと する 理論枠組みの こ と である 。 人間の思考過程の重要な要素は言語である と いっ て よ い。 言語なく し て は人間は考え る こ と ができ ず、 思考の系列と いう も のがある と すれば、 それは言語の系列である 。 こ の言語は数学 記号などと 異なっ て、 あいま いさ を も つも のである 。 こ のあいま いさ がフ ァ ジィ 理論でフ ァ ジィ ネ スと 呼ばれて いる も のである 。 フ ァ ジィ ネ スと はたと え ば、「 若者」 や「 大き い」 に見ら れる 言葉の意味と か概念の定義のあ いま いさ のこ と である 。 こ れま でのシステムの不確かさ は、 確率的不確かさ であり 、「 明日、 雨 が降る 」 こ と の偶然性な ど である 。 フ ァ ジィ 理論において はシステムの記述言語と し て フ ァ ジィ ネ スを 含むも のを 使い、 こ のこ と によ っ て システムの複雑性と データ の不完全性に対処する 人間の認識、 判断、 思考など の術 を あら わそう と する のである 。 たと えば、 右に曲がる カーブを 車が抜ける と き 、「 カーブに近づいたら 徐々 に減速し 、 ハン ド ルを ゆっ く り 右に切る 」 と いう よ う な 制御アルゴリ ズム を フ ァ ジィ 制御では用いる 。

2.2

フ ァ ジィ 集合

フ ァ ジィ 集合と は、 言葉の意味や概念の定義にみら れる あいま いさ を 定量的に表すための集 合概念である 。 熱いー冷たい、 近いー遠い、 など の言葉の意味は事物の置かれた状況と 、 判断する 人間の感 覚に依存し て 、 と て も あいま いである 。 われわれが日常的に使っ て いる 自然言語は数値を 用い ない定性的なも のである が、 こ れら の例にみら れる 言葉はなにかし ら 量に関係し た、 比較的に 定量化し やすいも のであり 、 フ ァ ジィ 集合はさ し あたっ て こ の種の言葉のあいま いさ を 扱う も のと 考え て よ い。 言葉のも つ意味のあいま いさ の定量化を「 風呂の湯が熱い」 と いう と き の「 熱い」 を 例にと っ て 考え て みる 。 図 2.1 は「 熱い」 と いう 言葉の意味を 関数を 用いて 定量化し たも のである 。 横 軸には風呂の湯の温度を 32 ℃から 48 ℃ま でと っ て ある 。 縦軸は 0 から 1 ま でのグレ ード と 呼 ばれる 数値を 示し て いる 。 横軸は言葉の意味を 考え る と き の量の世界であり 「 台」 と 呼ぶ。「 熱 い」 と いっ て も 風呂と お茶では変わっ て く る ので台の範囲は対象と し て いる 世界によ っ て 変化 し 、 ま た縦軸のグレ ード も 対象と する 人によ っ て 変化する 。 こ のグラ フ のグレ ード は湯のそれ ぞれの温度に 対し て 、 その温度がど の程度「 熱い」 と みな せる かと いう 度合いを 示し て いる 。

図 2.1 ではグレ ード の値は湯の温度が 38 ℃なら 0.3、 44 ℃なら 0.9 を と っ て おり 人間の「 熱い」 に対する あいま いな 思考を 表現でき て いる 。 グレ ード の最大値が 1、 最小値が 0 と いう 数値そ のも のはと く に意味を も つわけ ではな い。 図 2.1: フ ァ ジィ 集合 こ のよ う に、 意味の定量化は台の範囲と 台の上のグラ フ の形の 2 つに依存する 。 台の範囲は 客観的、 グラ フ は主観的と いう 比較ができ る 。 例から わかる よ う に、 言葉の意味のあいま いさ は、 グレ ード が 0 か 1 の間のいろ いろ な 値を と る と いう と こ ろ に現れて いる 。

2.3

多次元フ ァ ジィ 集合

多次元フ ァ ジィ 集合は、 µA(x), x ∈ Rn のメ ン バーシッ プ関数で特徴付け ら れた任意の n 次 元パラ メ ータ 空間 Rn_{上の曖昧な 部分集合と し て 定義さ れる 。 n 次元上のフ ァ ジィ 集合は、 こ} れま では一次元フ ァ ジィ 集合の直積又は和によ っ て 表さ れて き た。 こ の方法では多次元空間上 において 多数のフ ァ ジィ 集合が必要と なり 集合が複雑になっ て し ま い、 シン プルで精度を 良く 表現する こ と は難し く なる 。 そこ で多次元フ ァ ジィ 集合を 直接定義する こ と で多次元空間上で も 自然に表現する こ と ができ る 。

2.4

既存手法

先行研究におけ る 、 多次元フ ァ ジィ 集合の生成方法を 示す。 こ の手法では 2 つの閾値を 用い て 、 多次元フ ァ ジィ 集合を 生成する 。

2.4.1

幾何学的構造を 保存する ための閾値

_ϵ

_M 1. パラ メ ータ 空間 Rn_{のサン プル点の集合を D = {x} 1, x2, . . . , xN}と する 。 2. 近傍閾値 ϵMは、 ある 2 点 xi, xjのユーク リ ッ ド 距離 di,jと し 、 定数 Km ∈ R を 用いて 、 式 (2.1)のよ う に定義する 。 ϵM = N ∑ i=1 N min j=1(di,j) N × Km. (2.1) 3. 二点 xi, xj ∈ Dのユーク リ ッ ド 距離が、 近傍閾値 ϵM 以下の組を 連結し た近傍グラ フ を 構 成する 。 4. 任意の二点 xi, xjのネ ッ ト ワ ーク 距離 dpを 、 近傍グラ フ 上の最短パスによ っ て 定義する 。

2.4.2

サン プル密度を 計算する ための閾値

_ϵ

_F 1. 近傍閾値 ϵFは、 ある 2 点 xi, xjのネッ ト ワ ーク 距離 d_pi,jと し 、 定数 Kf ∈ R を 用いて 、 式 (2.2)のよ う に定義する 。 ϵF = N ∑ i=1 N min j=1(dpi,j) N × Kf. (2.2) 2. ある 点 x における サン プル密度は、 ネ ッ ト ワ ーク 距離閾値 ϵF 以下の距離にある 点の個数 Nn(x)を 、 Nn(x)の最大値 Nmaxで除し て、 こ れを 当該点のメ ン バーシッ プ値 µ(x) と する 。 µ(x) = Nn(x) Nmax . (2.3) 本研究では、 先行研究におけ る 式 (2) の ϵM,ϵF を 導出する 計算について 、 パーシステン ト ホ モロ ジー群を 使用し モデルを 同定する こ と を 提案する 。

2.5

各閾値の算出

糟谷ら が提案し た多次元フ ァ ジィ 集合生成方法の課題は、 二つの閾値 ϵM,ϵF の設定方法であ る 。 二つの閾値 ϵM,ϵF は人の感覚を 多次元データ に表すための重要な パラ メ ータ である 。

2.5.1

課題

1:

幾何学構造を 保存する ための閾値

_ϵ

_M 幾何学構造を 保存する ための閾値 ϵM は、 幾何学構造を 保存する こ と でよ り 人間の感覚に近 い多次元フ ァ ジィ 集合を 生成する こ と ができ る と いう 考え から 設定さ れて いる 。 幾何学構造を 保存し な け ればいけ な いが、 その値を 手動で調整する 必要がある 。

例と し て 、 図 2.2 の 2 次元空間上のサン プリ ン グ点データ を 用いた場合、 人が修正し たも の を 図 2.3 に示す。 図 2.3 において 、 z 軸はメ ン バーシッ プ値を 表し て いる 。

図 2.2: サン プル点データ

こ のサン プリ ン グ点データ では円形の幾何学構造がある こ と がわかる こ と から 、 ド ーナツ 上 にサン プル密度が取れて いれば良いこ と がわかる 。 よ っ て 、 多次元フ ァ ジィ 集合を 生成し た際 に円の内側のサン プル密度が高ければ、 ネ ッ ト ワ ーク 構造が円の穴を 保存し て いないこ と がわ かり 、 サン プル密度のばら つき が大き ければ個々 の点が孤立し て し ま いネ ッ ト ワ ーク 構造を 保 存でき て いな いこ と がわかる 。 こ のよ う に、 2 次元ま でのデータ な ら 多次元フ ァ ジィ 集合にし た際に確認し 、 修正する こ と も 容易である 。 ま た、 ネ ッ ト ワ ーク 構造を 構成し た際の無向グラ フ を 作成する こ と で、 3 次元ま でのデータ の幾何学構造を 生成でき て いる か確認する こ と がで き る 。 図 2.4,2.5,2.6 に閾値 Km = 3, 9, 30と 調整し た場合の無向グラ フ を 示す。 図 2.4: Km = 3の無向グラ フ 図 2.5: Km = 9の無向グラ フ

図 2.6: Km = 30の無向グラ フ こ のよ う に無向グラ フ を 確認する こ と で手動で調整する こ と ができ る 。 こ の場合は、 Km= 9 の無向グラ フ が最も 円の幾何学構造を 保存でき て いる と 考え ら れる 。 こ のよ う なサン プル点が 持つ何かし ら の幾何学構造を 計算によ っ て 保存でき る こ と が人の感覚に近い多次元フ ァ ジィ 集 合を 作成し やすく する と 考え ら れる 。 ま た、 人の認識でき ない多次元空間上でも 同様に計算に よ っ て 幾何学構造を 同定し 多次元フ ァ ジィ 集合を 作成する こ と で、 人の感覚に近い多次元フ ァ ジィ 集合が作成でき る と 考え ら れる 。

2.5.2

メ ン バーシッ プ値の分布分析

メ ン バーシッ プ値の分布を 確認する こ と で、 多次元フ ァ ジィ 集合を 編集する 方法がある 。 例と し て、 極端な構造を と ら ないために、 メ ンバーシッ プ値の分布を 参考にする 方法を あげる 。 こ こ では、 ロ ボカッ プシミ ュ レ ーショ ン 2D のボールの位置のロ グデータ を 用いた。 Kf = 100 に固定し 、 Km = 1, 5, 10と 変化さ せた場合の多次元フ ァ ジィ 集合のメ ン バーシッ プ値の分布を 図 2.7∼2.9 に示す。

図 2.7: Km = 1の多次元フ ァ ジィ 集合のメ ン バーシッ プ値の分布

図 2.9: Km = 10の多次元フ ァ ジィ 集合のメ ン バーシッ プ値の分布 こ のよ う にメ ン バーシッ プ値の分布の偏り よ り から 、 多次元フ ァ ジィ 集合の極端なデータ 構 造を 把握する こ と ができ る 。 し かし こ の手法は、 元々 大き く 偏っ て いる よ う なデータ の構造は 把握する こ と ができ な いため、 一意にこ の分布から 予測でき る わけ ではな い。 こ の分布は、 システムで使用する 観点から 見る と 、 データ がバラ ついて いた方がデータ を 比 較し やすいが、 一様に分布し て いた場合、 分布が偏っ て いた方が正し いと も 考え ら れ、 多方面 から 見る 必要がでてく る 。 ネッ ト ワ ーク 構造のエッ ジの数から 検討する 手法を 用いた場合でも 、 偏り な ど から 幾何学構造は検討する こ と はでき な いと 考え ら れる 。 よ っ て 、 多次元データ に対し て 、 手動で調整する こ と も 難し く ために、 幾何学構造を 保存す る ための指標がなければ、 構造を 保存でき ずに多次元フ ァ ジィ 集合を 構成し て し ま い、 結果と し て 人の感覚を 表現でき て いな いも のと な る と 考え ら れる 。

2.5.3

課題

2:

サン プル密度を 計算する ための

_ϵ

_F サン プル密度を 計算する ための閾値 ϵFは、 サン プル点データ を 見た人が密度の高い点を その 集合に属する 度合いが高く なる と 考え 、 密度が低い点は属する 度合いが低く なる と いう 考え ら れて いる 。 よ っ て 的確なサン プル密度を 取る こ と が人の感覚を 反映し た多次元フ ァ ジィ 集合を 生成する と 考え ら れる 。 極端に大き な 閾値を と っ て し ま う と 、 サン プル密度は均一にな り 、 小さ な 値を と る と 、 個々 のデータ のばら つき が大き く なり 、 人の感覚を データ に反映でき たと はいいづら く なる 。 し か し ながら 、 人の感覚と は一般的に決めら れる も のでも なく 、 個々 の考え が反映さ れる ため正解

も ない。 図 2.10 のサン プル点データ に対し て 、 閾値 Km = 3に固定し 、 閾値 Kf = 3, 30, 300と

変化さ せた場合の多次元フ ァ ジィ 集合を 図 2.11∼2.13 に示す。

図 2.10: サン プル点データ

図 2.12: 閾値 Kf = 30の多次元フ ァ ジィ 集合

図 2.13: 閾値 Kf = 300の多次元フ ァ ジィ 集合

こ のよ う に閾値を 変化さ せる こ と でサン プル密度は変化する 、 値の取り 方によ っ て は分布密 度は一定になっ て し ま う こ と がある 。 こ の閾値に対し て 、 人の視認でき ない多次元データ で調

よ う な構造でど のよ う なサン プル密度を 取っ て いる か確認し なければ、 調整する こ と も でき な い。 し かし ながら 、 こ の閾値において も 全て の点が閾値の範囲内になる 閾値やすべて の点が孤 立する よ う な閾値は、 ど のよ う なサン プル点データ において も 全点のサン プル密度が同じ にな り 多次元フ ァ ジィ 集合の意味を 成さ ないと 考え ら れる 。 よ っ て 、 そのよ う な閾値を と ら ない範 囲を 決定する 必要がある 。 ま た、 データ の種類によ っ て 閾値の変化と 関係を 調査する こ と で、 閾値の指標を 検討する こ と ができ る 。

第

3

章 パーシステン ト ホモロジー

多次元フ ァ ジィ 集合生成方法の二つ閾値を 導出する ために、 対象の幾何学構造を 導出する こ と のでき る ホモロ ジー群を 計算する 。 ホモロ ジー群は単体複体と 呼ばれる 点の集ま り に対し て、 各次元での大域的な つな がり 具合を 表すも のである 。 ま ず、 ホモロ ジー群を 計算する ため、 点から の単体複体する 必要があり 、 点から 単体複体を 作成する には、 点と 近傍点を 集ま り と みなす必要がある 。 こ の近傍点の決め方によ っ て ホモロ ジー群は変化し て し ま う 。 そこ で、 こ の単体複体の変化に対する ホモロ ジー群の遷移を 計算でき る よ う にする のが、 パー システン ト ホモロ ジー群である 。 単体複体のフ ィ ルト レ ーショ ン (増大列) に対し て 、 パーシス テン ト ホモロ ジー群を 適用する こ と で、 各閾値に対する 各次元のホモロ ジー群の生成と 消滅を 確認でき る 。 パーシステン ト ホモロ ジー群と は、 対象のホモロ ジー群の生成元の遷移を 特徴づける 方法で ある 。

3.1

ホモロジー群

n次元パラ メ ータ 空間 Rn_{内の k+1 個の点 x} 0, x1, . . . , xkが k 個の一次独立なベク ト ル −−→x0x1, . . . , −−→x0xk を 与え る 時、 それら の点で構成さ れる 最小の凸集合を k 単体と 呼ぶ。 Rn内の有限個の単体の集ま り K と する 。 K が以下の二つの条件を 満たす場合、 K を 単体複 体と 呼ぶ。 1. K に属する 単体 τ の面 σ ≺ τ も ま た K に含ま れる 。 2. 2つの単体 τ, σ ∈ K に対し て 、 τ ∩ σ が空集合でな いな ら ば、 τ ∩ σ は τ の面かつ σ の面 である 。 ホモロ ジー群は、 単体複体に対し て 、 各次元での大域的なつながり 具合を 表すも のであり 、 1 次元の連結成分、 2 次元の穴、 3 次元のわっ か、 など の「 穴」 に関連し た幾何学的意味を 持つ。 単体の頂点に順序づけし たも のを σ と 呼ぶ。 K を n 次元単体複体と し 、 そのすべて の k 単体 の集ま り を Kk = {σ1, · · · , σnk ∈ K|dimσi = k}. (3.1) で表す。

各 0 < k < n ごと に Kkで生成さ れる 自由 Z 可群 Ck(K)は Ck(K) = Z⟨Kk⟩ = {c = nk ∑ i=1 ασi⟨σi⟩|ασi ∈ Z}. (3.2) で表す。 ま た、 各 Ckごと に、 境界作要素 ∂k : Ck(K) → Ck−1(K)を 向き づけ ら れた単体ごと に ∂k⟨σ⟩ = k ∑ i=0 (−1)i⟨υ0· · · ˆυi· · · υk⟩. (3.3) で定める 。 こ こ で、 一般の k 鎖 c = Σnk i=1ασi⟨σi⟩について は線形拡張 ∂k⟨c⟩ = nk ∑ i=1 ασi∂k⟨σi⟩. (3.4) で定める 。 式 (5),(7) 導入し た鎖群と 境界作要素から な る 系列を 、 K の鎖複体と 呼ぶ。 こ こ で、 k 鎖群 Ck(K)の 2 つ部分加群を 導入する 。 Zk(K) = Ker∂k = {c ∈ Ck(K)|∂k(c) = 0}, (3.5) Bk(K) = Im∂k+1 = {c ∈ Ck(K)|c = ∂k+1(c′), c′ ∈ Ck+1(K)}. こ の二つの部分加群を 使用する と 、 単体複体 K の k 次ホモロ ジー群は、 剰余加群 Hk(K) = Zk(K)/Bk(K). (3.6) で定めら れる 。

3.2

パーシステン ト ホモロジー群

本研究では、 単体複体の生成する 場合、 要素同士を 接続する ために点間のユーク リ ッ ド 距離 を 使用する 。 そ の要素間の距離の増大さ せる こ と に よ る 、 単体複体の増大列を と っ たも のが、 フ ィ ルト レ ーショ ン と な る 。 パーシステン ト ホモロ ジー群と は、 単体複体のフ ィ ルト レ ーショ ン から 、 それぞれのホモロ ジー群を 生成する こ と であり 、 各次元ホモロ ジー群の生成消滅を 確 認する こ と で、 対象のホモロ ジー群の持続性やロ バスト 性を 考察でき る よ う にする 方法である 。 こ こ で、 単体複体 Kt_{, t = 0, 1, · · · のフ ィ ルト レ ーショ ン} K : K0 ⊂ K1 _{⊂ · · · ⊂ K}t_{⊂ · · · . (3.7)}

を 考え る 。 こ こ でフ ィ ルト レ ーショ ン 内の単体複体 Kt_{を 指定する 添字 t を 時刻と 呼ぶ。 フ ィ ル} ト レ ーショ ン K は、 非負整数 Θ が存在し 、 Kj _{= K}Θ_{, J ≤ Θが成り 立つと き 、 有限型である と} いう 。 ま たこ の性質を 満たす Θ の最小値を 、 フ ィ ルト レ ーショ ン の飽和時刻と 呼ぶ。 こ のフ ィ ルト レ ーショ ン に対し て 、 k 次パーシステン ト ホモロ ジー群 P Hk(K) は P Hk(K) = Zk(K)/Bk(K). (3.8) で定めら れる 。 ま た、 Zk(K), Bk(K) は斉次部分加群な ので、 パーシス テン ト ホモロ ジー群は次数付き Z2[x] 加群と し て P Hk(K) = ⊕ t≥0 Zk(Kt)/Bk(Kt) = ⊕ t≥0 Hk(Kt). (3.9) で与え ら れる 。 パーシステン ト ホモロ ジー群 P Hk(K) は、 Zk(K) のある 斉次基底 gi, . . . , gmを 用いて P Hk(K) = s ⊕ i=0 ⟨[gi]⟩ ⊕ s+r ⊕ i=s+1 ⟨[gi]⟩ , (3.10) Ann([gi]) = (xli), i = 1, . . . , s, 1 ≤ li ≤ li+1 (3.11) Ann([gi]) = 0, i = s + 1, . . . , s + r. (3.12) と 表せる 。 よ っ て こ の表示に おいて 、 di = deg giと する と 、 生成元 [gi ] は時刻 diの単体複体 Kdiで新たに発生する ホモロ ジー類を 示す。 g iに対し て 、 時刻 diは発生し た時刻を 示し 、 liは 存続区間を 表すこ と にな る 。 パーシステン ト ホモロ ジー群に対し て 、 Ii =    [di, di+ li), i = 1, . . . , s, [di, Θ], i = s + 1, . . . , s + r (3.13) を パーシス テン ト 区間と 呼ぶ。 こ こ で Θ はフ ィ ルト レ ーショ ン の飽和時刻である 。 ま た di を パーシステン ト 区間 Iiの発生時刻、 di+ liを 消滅時刻と 呼ぶ。 ま た、 パーシステン ト 区間 Iiに対し て、 Ii(b)で区間の下限 (birth),Ii(d)で区間の上限 (death) を 表すこ と にする 。 パーシステン ト ホモロ ジー群に対し て P Hk(K) = {(Ii(b), Ii(d)) ∈ R2 | i = 1, . . . , s + r}. (3.14) を k 次パーシステン ト 図と 定める 。 こ こ で li ≥ 1かつ di ≤ Θよ り 、 パーシステン ト 図 P Hk(K) 内すべて の点は対角線上よ り 上 側にく る 。 例と し て 、 図 3.1 にロ ボカッ プサッ カーシミ ュ レ ーショ ン 2D のロ グから サン プルし た 2 次元サン プル点データ、 図 3.2 にサン プル点データ のパーシステン ト 図を 示す。 パーシステ ン ト 図の点はホモロ ジー類を 示し 、 横軸は (birth)、 縦軸は (death) を 示す。

図 3.1: サッ カ ー行動から サン プルし たサン プル点データ

第

4

章 パーシステン ト ホモロジーによ る 多

次元フ ァ ジィ 集合生成手法

4.1

提案手法

パーシステン ト ホモロ ジーを 用いて 、 幾何学的構造を 保存する ための閾値と サン プル密度を 計算する 閾値を 導出する 。 サン プル点データ の構造を 同定する ために パーシス テン ト ホモロ ジーを 用いて 計算を 行う 。 パーシステン ト ホモロ ジーの計算には Ripser[13][14] を 用いた。 パーシステン ト ホモロ ジーで生成さ れたホモロ ジー群の中には、 誕生し たタ イ ムステッ プと 消滅し たタ イ ムステッ プが近いも のがある 、 短いタ イ ムステッ プでし か生存し なかっ たホモロ ジー群はデータ の幾何学構造よ り も ノ イ ズである 可能性が高い。 よ っ て 、 ノ イ ズの影響を 少な く する ために重み付け を 行う 。 重み付け に関し て は、 先行研究 [15] の手法を 用いる 。 重み関数 w(x) = arctan(CPers(x)p_{), (4.1)} (C, p > 0), Pers(x) = d − b for x ∈ {(d, b) ∈ R2|b ≤ d}. を 用いて 、 重み付け を 行う 。 重み関数はパラ メ ータ C, p を 調整する こ と で、 パーシステン ト ホモロ ジーへの影響を 調整す る こ と ができ る 。 先行研究よ り 、 p = 5、 C = (midium{Pers(xi)|xi ∈ D})−pと 設定し た。 例と し て 、 図 4.1 にロ ボカッ プサッ カーシミ ュ レ ーショ ン 2D のロ グから サン プルし た 2 次元 サン プル点データ、 図 4.2 にサン プル点データ のパーシステン ト 図、 図 4.3 に重みを 付けたサン プル点データ のパーシステン ト 図を 示す。

図 4.1: サッ カ ー行動から サン プルし たサン プル点データ

図 4.3: サン プル点データ の重み付き パーシステン ト 図 重みを 付け ら れたパーシステン ト 図に対し て 、 0 次元ホモロ ジー群を 除き 、 biと diの中点の 重み付け 平均を 計算し 、 こ の平均値を 近傍閾値 ϵM と し 、 diの重み付け 平均を 計算し 、 こ の平 均値を 近傍閾値 ϵF と する 。 w(xi)は式 4.1 によ っ て 求める 。 ϵM = i≤N ∑ i=1 w(xi)(bi+ di) 2 i≤N ∑ i=1 w(xi) . (4.2) ϵF = i≤N ∑ i=1 w(xi)di i≤N ∑ i=1 w(xi) . (4.3)

4.2

比較実験

4.2.1

実験設定

多次元フ ァ ジィ 集合生成方法を 用いて 、 二つの閾値に対し 、 提案手法と 手動で求めた場合の 比較実験を 行っ た。 実験にはロ ボカッ プサッ カーシミ ュ レ ーショ ン 2D と 呼ばれる 2D サッ カーシミ ュ レ ーショ ン のロ グデータ を 使用し た。 • ある 試合 6000 点,46 次元のデータ から 、 ボールの移動ロ グデータ ,1000 点を ラ ン ダムサン プリ ン グし た 2 次元データ (xb(t), yb(t)) • ある 試合 6000 点,46 次元のデータ から 、 オフ ェ ン ス 2 人の移動ロ グデータ ,400 点を ラ ン ダ ム サン プリ ン グし た 4 次元データ (x1(t), y1(t), x2(t), y2(t)) を 用いた。 図 4.4 にボールの移動ロ グデータ ,1000 点を ラ ン ダム サン プリ ン グし たデータ を 示す。 図 4.4: サン プル点データ 閾値 ϵM は、 手動で KM=3,9と 設定し たも のと 、 提案手法で求めたも の、 閾値 ϵF は、 手動で KF=9,27と 設定し たも のと 、 提案手法で求めたも のを 用いた。 二つの閾値のそれぞれの組み合 わせで多次元フ ァ ジィ 集合を 生成し 、 比較検討を 行う 。

4.2.2

実験結果

ある 試合に おけ る 、 ボールの移動ロ グデータ から 1000 点ラ ン ダム サン プリ ン グし た 2 次元 データ から それぞれの閾値の組み合わせによ っ て生成し た多次元フ ァ ジィ 集合を 図 4.5∼ 図 4.13

に示す。 ま た、 それぞれの多次元フ ァ ジィ 集合のネ ッ ト ワ ーク 構造のパス数を 表 4.1 に、 メ ン バーシッ プ値の分散を 表 4.2 に示す。

図 4.7: Km = 3,Kf = 27

図 4.9: ϵM :提案手法,ϵF :提案手法

図 4.11: Km = 9,Kf = 9

図 4.13: Km = 9,Kf = 27 表 4.1: ネ ッ ト ワ ーク 構造のパス数

ϵ

M

パス数

K

m

= 3

6287

提案手法

13463

K

m

= 9

18395

表 4.2: メ ン バーシッ プ値の分散

ϵ

M

ϵ

F

K

f

= 9

提案手法

K

f

= 27

K

m

= 3

0.059381

0.067638

0.124856

提案手法

0.045772

0.046139

0.051188

K

m

= 9

0.036028

0.038696

0.047227

ある 試合におけ る 、 オフ ェ ン ス 2 人の移動ロ グデータ から 400 点ラ ン ダム サン プリ ン グし た 4次元データ から それぞれの閾値の組み合わせによ っ て 生成し た多次元フ ァ ジィ 集合のネ ッ ト ワ ーク 構造のパス数を 表 4.3 に、 メ ン バーシッ プ値の分散を 表 4.4 に示す。 表 4.3: ネ ッ ト ワ ーク 構造のパス数

ϵ

M

パス数

K

m

= 3

1794

提案手法

3339

K

m

= 9

15399

表 4.4: メ ン バーシッ プ値の分散

ϵ

M

ϵ

F

K

f

= 9

提案手法

K

f

= 27

K

m

= 3

0.079824

0.047352

0.073158

提案手法

0.058190

0.042661

0.048680

K

m

= 9

0.035861

0.042289

0.016258

4.2.3

考察

2次元データ において 、 こ の図形では上側に点が偏り 、 左上と 右上に穴が開いて いる 分布だ と 確認でき る 、 二つの閾値を パーシステン ト ホモロ ジーで導出し たも のが、 そのデータ の分布 を よ く 表すこ と ができ て いる 。 メ ン バーシッ プ値の分散を 計算し た場合、 最も 分散が大き く な る よ う な閾値はパーシステン ト ホモロ ジーから 導出し た閾値と は異なっ て いる 。 こ れは、 メ ン バーシッ プ値が 1 に近い値と 0 に近い値に二分し て いる よ う な 多次元フ ァ ジィ 集合の分散が大 き く なっ て いる ためである 。 こ こ から 、 分散が大き ければデータ のバリ エーショ ン が多く なる と は限ら な いこ と が確認でき た。 4次元データ に おいて 、 Km = 3ではパス 数が少な いこ と から データ の偏り が著し く 、 分散 が大き く な っ て いる と 考え ら れる 。 提案手法が導出し た閾値 ϵM はパス数は多く 、 分散の値も Km = 9よ り も 大き く な っ て いる こ と から 、 他の値よ り も 良い多次元フ ァ ジィ 集合が生成する こ と ができ て いる 。 し かし 、 提案手法が導出し た閾値 ϵF は、 Kf = 9, 27両方よ り も 分散が小さ く な っ て し ま っ て おり 、 他の閾値よ り 偏っ た多次元フ ァ ジィ 集合にな っ て いる と 考え ら れる 。 本研究では、 0 次元ホモロ ジー群を 除いて 、 パーシステン ト 図の重み付き 平均を 計算し て い る 。 こ れは、 0 次元ホモロ ジー群がデータ 点の数だけ生成さ れ、 birth が 0 と なっ て おり 、 重み を 付け たと し て も 大き な 影響を 与え る ため、 平均値が非常に 小さ く な っ て し ま う ためである 。 し かし 、 0 次元ホモロ ジー群も データ の幾何学的特徴ではある 。 削除する のではな く 、 ホモロ ジー群の次元によ る 重みの変更な ど を 考え る 必要がある 。

第

5

章 結論と 今後の展望

5.1

結論

本研究によ り 、 データ のパーシステン ト 図を 計算し 、 0 次元ホモロ ジー群を 除き 重み付き 平均 を と る こ と で閾値 ϵM,ϵF の指標と なる 値を 式 5.1,5.2 のよ う に提案する こ と ができ た。 こ こ で bi はホモロ ジー群 xiにおける birth、 diはホモロ ジー群 xiにおける death、 w(xi)は式 5.3 によ っ て 求める ホモロ ジー群 xiにおけ る 重みである 。 ϵM = i≤N ∑ i=1 w(xi)(bi+ di) 2 i≤N ∑ i=1 w(xi) . (5.1) ϵF = i≤N ∑ i=1 w(xi)di i≤N ∑ i=1 w(xi) . (5.2) w(x) = arctan(CPers(x)p) (5.3) (C, p > 0), Pers(x) = d − b for x ∈ {(d, b) ∈ R2_{|b ≤ d}.} パーシステン ト ホモロ ジーはデータ の幾何学構造を 同定する こ と ができ 、 多次元データ でも 用いる こ と ができ る ため、 多次元フ ァ ジィ 集合へ応用さ せる こ と ができ た。 ま た、 重みを 付け て いる ため birth と death が近いノ イ ズである ホモロ ジー群の影響を 小さ く する こ と ができ て いる 。 0 次元ホモロ ジー群を 除いて いる ため、 データ の連結成分に関する 幾何学構造を 同定す る こ と はでき て いないが、 他次元のホモロ ジー群によ る 幾何学構造を 同定する こ と で、 幾何学 構造を 保存する よ う な 閾値を 提案でき た。 人が視認でき ない多次元空間において 、 幾何学構造を 用いる こ と で多次元フ ァ ジィ 集合を 編 集する ための検討材料の一つにする こ と ができ たと 言え る 。

5.2

今後の課題

本研究の課題はパーシステン ト ホモロ ジーから よ り よ い閾値を 導出する こ と である 。 平均を 取っ た場合、 0 次元ホモロ ジー群の birth が多いため値が小さ く なる 傾向がある 。 本研究では 0

次元ホモロ ジー群を 除いて 計算し たが、 0 次元ホモロ ジー群も 幾何学構造である ために、 ホモ ロ ジー群の次元によ っ て 重みを 変更する な ど 方法を 検討する 必要がある 。 サン プル密度を 計算する ための閾値は、 本研究の手法では幾何学構造を 保存する ための閾値 と 近く なり 、 幾何学構造を 保存し た意味がなく なっ て し ま う ため、 他の計算手法も 検討する 必 要がある 。 ま た、 本研究によ っ て 提案し た閾値は人が編集する 際の指標の一つであり 、 よ り 人が多次元 データ を 理解する ために他の検討材料を 提案する こ と が課題である 。 統計量を 用いる こ と や、 人が理解でき る よ う 次元を 削減し たデータ を 用いる こ と が必要にな る 。 そし て 、 システム面から 考え 、 システムにおいて 使いやすいためにメ ン バーシッ プ値の分散 が最も 大き く なる 閾値を 取る と いう 考え 方も ある 。 様々 な点から 検討でき る よ う にする こ と が 一番の課題である 。

参考文献

[1] Lotfi A Zadeh. The concept of a linguistic variable and its application to approximate reasoning―i. Information sciences, Vol. 8, No. 3, pp. 199–249, 1975.

[2] Lofti A Zadeh. Information and control. Fuzzy sets, Vol. 8, No. 3, pp. 338–353, 1965. [3] Takaki Okuyama, Nobuhiko Kawashiro, and Junji Nishino. Humanoid motion generation

with fuzzy state knowledge. In 27th Fuzzy System Symposium, pp. 175–178, 2011.

[4] Junji Nishino and Akihiro Kasuya. Gpgpu for human modelling with konohen fuzzy set. In 27th Fuzzy System Symposium, p. to be appeared, 2011.

[5] Akihiro Kasuya and Junji Nishino. High-speed generation of multi-dimensional, fuzzy set with gpgpu. In 26th Fuzzy System Symposium, pp. 1232–1235, 2010.

[6] Junji Nishino. Konohen fuzzy: A sample points based computational model for multi-dimensional fuzzy set. In Granular Computing (GrC), 2014 IEEE International Conference on, pp. 230–234. IEEE, 2014.

[7] Takashi Harada and Junji Nishino. Multi-dimensional fuzzy set identification using per-sistent homology. International Fuzzy Systems Association, 2017.

[8] 原田貴史, 西野順二. 多次元フ ァ ジィ 集合生成におけ る パーシステン ト ホモロ ジーの応用. 第 33 回フ ァ ジィ システム シン ポジウ ム , 2017.

[9] Yasuaki Hiraoka. Protein Structure and Topology : Introduction to Persistent Homology. Kyoritsu Shuppan, 2013.

[10] Mark Anthony Armstrong. Groups and Symmetry. Springer Japan, 1988.

[11] Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. In Discrete Comput Geom 33, pp. 249–274, 2005.

[12] Herbert Edelsbrunner and John Harer. Persistent homology - a survey. In Contemporary Mathematics Volume 453, pp. 257–282, 2008.

[13] Ulrich Bauer. Ripser. https://github.com/Ripser/ripser, 2015–2016.

[14] Otter N, Porter MA, Tillmann U, Grindrod P, and Harrington HA. A roadmap for the computation of persistent homology. http://arxiv.org/abs/1506.08903, 2015.

[15] Genki Kusano, Kenji Fukumizu, and Yasuaki Hiraoka. Persistence weighted gaussian kernel for topological data analysis. International Conference on Machine Learning, pp. 2004–2013, 2016.

謝辞

本研究に際し て， 日頃よ り 様々 なご指導を 頂いた西野順二助教に心よ り 御礼申し 上げま す． ま た， 様々 な手続き でお世話になっ た主任指導教員の緒方秀教教授， 合同ゲームゼミ で貴重なご 意見を 頂いた保木邦仁准教授そし て 研究生活の中で多く の助言を 頂いた研究室の皆様に深く 感 謝致し ま す．