近似エントロピーによる

(1)

修士学位論文

近似エントロピーによる

道路区画地図複雑さ数値化方法の研究

指導教授鈴木登志雄准教授

首都大学東京

理工学研究科数理情報科学専攻学修番号

氏名長谷川香

平成年月日

(2)

(3)

第章序

はじめに

エントロピーという概念は自然科学のいろいろな学問領域に登場する．

１８６５年，クラウジウスは温度に対する熱量変化の比率としてエントロピーを導入した．啓蒙書や応用研究では，しばしば「不確定さ・乱雑さ・無秩序」の度合いを表す概念として捉えられる場面も見られる．しかし，このエントロピー自体を乱雑さの尺度と出来る訳ではない．一定の前提の下で「不確定さ・乱雑さ・無秩序」とみなし得るにすぎない．したがって，この熱力学から生まれたエントロピーという概念は現在では統計力学や情報理論など様々な分野で導入，及び確立されているが，その計算式は，各分野に適した形で独自の発展を成し遂げ，用いられている．しかし，いずれもあるパターンを基準にしての秩序性・規則性の定量化という考え方に基づいている．１９５０年代に考案されたエントロピー（エントロピー）を始めとしてエントロピー概念を導入し，時系列的なデータの特性を定量的に捉えようとする試みがされてきた．

そして１９９０年代に入り，実験データを規則性において判別することに重点を置いた近似エントロピー（）という概念が考案された．近似エントロピーとエントロピーは，類似しているが，近似エントロピーは比較的少ない有限個のデータで適正な値を導き出せるよう工夫されている．現在では，主に生理学の分野で適用されており，標準偏差にほとんど差の見られないデータであっても，規則性を定量化した近似エントロピーはその差を表せることから，心拍データの解析などに用いられている．また，

(6)

第章序

道路渋滞の解析などへの適用も試みられている．

そこで，本研究では，近似エントロピーの概念を「道路区画地図の複雑さの定量化」へ適用するに当たっての，適用方法を検討し，適用例を示す．また，本研究においては

でも用いられている近似エントロピーの計算式を採用している．

近似エントロピーはという数列の階差で定義されている．具体的には以下の通りである．与えられた有限個の時系列データに対してそこから（連続する）長さ

の部分列（）をランダ

ムに２つ取り出すときに，それらが誤差で一致する確率をとする．そのとき

と定義する．このとき，近似エントロピーを

と定義する．

本研究では，三角関数によって長方形格子を歪ませたモデル図形を用いたシミュレーションを行う．これにより，近似エントロピーの概念を道路区画地図へ適用した場合の性質や特徴，つまり道路区画地図の何を反映し，その一方で何を表わせないのかを検討する．

また，このシミュレーションにおいて，近似エントロピーの値とが「負の相関」を持つという現象がみられた．

そこで，対象を四辺形に限定した場合に「四辺形を微小変形して長方形に近づけるとき近似エントロピーは増加し，は減少する」ことを数学的に証明する．

各区画が四辺形に近い道路区画地図においても，近似エントロピーとの間に同様の関係が成り立つとみなせる．

このことを応用し，道路区画地図の複雑さの指標として近似エントロピーの代わりにを用

(7)

はじめに

いることを提案する．これにより，近似エントロピーを計算する方法に比べ，計算量を約半分にできる．

また，倉本は地図の複雑さを数値化する指標として周二乗面積比・区画面積の分散に基づいた指標を提案した．本研究で提案するは，倉本の提案した指標と比較すると，長方形格子を多く含む（地域である）京都と，入り組んだ路地の多い（地域である）東京都との差を明確に表わすことがわかった．

第章では，近似エントロピーの説明，および川村，倉本が提案した指標について詳しく述べる．

第章では，近似エントロピーの格子状図形への適用方法について述べる．

第章では，モデル図形への適用例を基に，「と」の関係について数学的な証明を与える．

第章では，実際の道路区画地図への適用例を示す．

(8)

第章序

用語の説明

近似エントロピー（）

近似エントロピー（）は，有限個の時系列データを規則性に基づいて判別する指標として導入された．以降では，近似エントロピー（）をと記述する．これは，長さの時系列データ

が与えられたときにを長さの（連続する）部分列をランダムに２つ取り出し，それらが誤差で一致する確率の分布から導かれる量である．

それにはまず，時系列データに対し，長さの部分列

（ただし，）

を定める．また，部分列との距離を

とする．さらに，をを満たすの個数とする．

このの平均値であるを以下のように定義する．

(9)

用語の説明

さらに式の平均をとおく

そうしてこのの対数値を：

とする．このとき，近似エントロピーは

により定義される．

道路区画地図

本研究では，国土地理院が発行する「数値地図（空間データ基盤）関東版」

・「数値地図（独自形式）近畿版」から道路中心線を抽出した地図データを用いている．まず，地図をモノクロファイルとして与え，それをいくつかの正方形領域に分割する．このとき，道路中心線は黒ピクセル，その他の領域は白ピクセルで表わされる．また，正方形領域はとなるように分割する．近似エントロピー等を適用する地図は，分割後のの正方形領域である．

周二乗面積比

心理学実験では世紀半ば以降，たびたび閉曲線で囲まれた図形に対する複雑さの心証についての実験と分析がなされている．特にとは，相似拡大で不変な量として閉曲線の周の長さの二乗と，閉曲線が囲む面積の比に注目した．以下ではこれを周二乗面積比と呼ぶ．各区間の周の長さを，面積をとするときののことを周二乗面積比と

(10)

第章序

呼ぶ．

具体的に，円では最小値をとり，正方形では，星形のように凹凸が多い図形では大きくなる．地図上に指定された正方形領域において，この領域に含まれる区画のすべてに渡って周二乗面積比の平均値を求める．ただし，区画の面積に比例した加重平均をとる．

ただし

区画面積の分散を修正した量

地図上に指定された正方領域において，この領域に含まれる区画の面積の分散を，平均をとし，以下の量に着目する．

分散に基づく指標なので，合同な区画だけからなる領域では最小値をとる．

連の長さを修正した量

上記のと似た量を次元で考える．地図上の領域を横切る直線上において道路中心線でないピクセルが続くかたまり，つまり連の長さの分散を求めて，それを平均値の二乗で割る．

この実験で用いる地図画像ビットマップにおいては道路中心線が黒，そうでない部分が白で表わされたモノクロファイルを基に（黒）と（白）のビット列を作る．（詳しくは次章参照）こうして得たビット列について，の連の長さの分散と平均を求め

を求める．画像に対して縦・横方向から生成したビット列についてのの平均値を求め，次に斜め度・度の方向から生成したビット列についてのの平均値を求める．こうして得たふたつの平均値のうち，小さい方をとする．

(11)

用語の説明

周二乗面積比と面積の分散を基にした指標

倉本は，（地図を）スキャンする角度による影響を軽減する方法として，指標式式を用いて，回転により不変な指標式を提案した．

と定義して，角度によらない指標

を考案した．

(12)

(13)

第章格子状図形のための近似エントロピー

近似エントロピーの定義

与えられた道路区画地図を元に，地図上の領域を横切る直線上において道路中心線でないピクセルが続くかたまり，つまり連の長さからなる列を作る．その数列に対して，近似エントロピーを（計算して）求める．具体的には以下の通りである．

この実験で用いる地図画像ビットマップにおいては道路中心線が黒，その他の部分が白で表わされている．与えられたの正方形領域を以下の方向からスキャンし，（黒）

と（白）の列を作る．ここで，行は水平の並び，列は垂直の並びを表わす．

（）上の行から順に，左から右へスキャン（英文方式）

（）右の行から順に，上から下へスキャン（和文方式）

（）正方形領域を反時計回りに度回転させてから，上の行から順に，左から右へスキャン

（）と同様に正方形領域を反時計回りに度回転させてから，右の行から順に，上から下へスキャン

ただし，（）（）を行う前に，の形のブロックをに修正し，さらに

をに修正する．これは，斜めの線を連結にするためである．

(14)

こうして得たつのビット列の各々について，の連の長さを並べた列ここで

を作り，このに対し，としてを求める．の定め方については，次の節で述べる．

図部分列イメージ図

ここで，

（）

となる長さの部分列を作るが，適用する対象が地図であるため，図（右側で）太字で示した行を跨ぐ部分列は含まないものとし，その総数をとする．

(15)

パラメータ，の決定

次に

を満たすの個数

と定義する．そして，この部分列のうち，すなわちを満たすの数を求める．

ここで，とおき，その平均をとする．

このとき，は

と定義される．また，近似エントロピーを

で定義する．

パラメータ，の決定

第節では，近似エントロピーを計算する際，パラメータ，を，と設定しているが，これは以下のような理由からである．

相似拡大による影響が小さい．

長方形格子からの乖離度を最も顕著に反映している．

節参照

以下では，パラメータを決定するために行った，単純モデルによる考察について述べる．

(16)

パラメータの決定

パラメータは，式のを数え上げる際の誤差ととらえることができるため，例えば対象となる図形を倍に拡大した場合，誤差も倍となるのが妥当である．しかし，

とすることにより，近似エントロピーを相似拡大の影響を受けにくい指標としたい．

例として，図の二つのモデル図形が与えられたときを考える．

図相似図形

このとき，で与えられた部分列のうち

を満たすの個数であるを求めるのであるが，２つの図形は相似であるので

(17)

パラメータ，の決定

ゆえにパラメータは相似拡大の影響を受けるが，とすると

より，各々の図形における，，の値は等しくなる．ゆえに，

としたとき，相似拡大の影響を最小限に抑えることができる．

パラメータの決定

図格子図形の変形

は，与えられたデータ列についての部分列を作る際の各部分列の長さである．本研究では，部分列をつくるとき，行を跨ぐものは排除している第節参照．ゆえに，対象となる正方形領域の分割数による影響を受ける．分割数の少ない場合を考えたとき，が１行に含まれる白い連の個数よりも大きくなると，計算対象となる数列から排除されてしまう．そのため，

は出来るだけ小さな値としたい．そこで，本研究ではとして近似エントロピー，およびを求める．これは，近似エントロピーとを求めることができる最小のの値である．

さらに，図のようなモデル図形について考察する．これは，正方領域を分割・分割・分割した格子図形をのモノクロファイルとして与えられたとき，

その中に含まれる直線を三角関数によって歪ませたものである．実際には，格子図形内に含まれる交点から交点までを周期とし，振幅をづつ増やして歪ませ，歪みの度合いに変化を

(18)

つけている．ただし，歪んだ格子状図形は，元の格子状図形と同相であるもののみを対象とし，

その範囲内で振幅を増加させるものとする．

を図のようにおき，振幅をとしたとき

の近似値をプロットしている．

a

i

a

_i₊₁

b

j

b

m

0

256

b

1

a

1

図振幅モデル図形

として，でを変化させ，正方形領域の分割数が異なるモデル図形に対しを計算するシミュレーションを行った．その結果，いずれの分割の場合においても，

としたとき，振幅の増加に伴い，の値が増加することがわかった．このことから，本研究においてパラメータとすることを妥当と考える．シミュレーション結果については第章参照

(19)

何が表わせるのか

図分割格子図形の近似エントロピー

何が表わせるのか

第節で用いた格子図形を三角関数によって歪ませたものを対象とし，面積の分散と近似エントロピー（），との関連性について述べる．

図のように周囲の境界を含んだ四角形は黒く塗りつぶし，考えないものとする．このとき，近似エントロピーが適用される白ピクセルで構成される部分の面積は曲線の振幅の増加によらず，ほぼ一定に保たれている．

このモデル図形に対して近似エントロピーの計算を施すと格子の歪み，つまり振幅が増すにつれ，の値は増加していることがわかった．つまり，近似エントロピーは，面積の分散に殆ど変化のないモデルにおいても，振幅を表わすことができると考えられる．ただし，その反面，近似エントロピーの大小によって面積の分散を表わすことは出来ないこともわかる．

(20)

図格子図形

観察された現象

前節で述べたシミュレーションを行った結果，ほぼ全てのモデル図形において，格子の歪み，

つまり振幅が増すにつれ，の値は増加する．しかし，その一方での値は減少するという減少が観察された．

図と図は分割の異なるモデル図形に行ったシミュレーションをまとめたものである．

この現象については，次章で詳しく分析をする．

(21)

観察された現象

図

(22)

(23)

第章との間の負の相関

観察された現象としての負の相関

第節におけるシミュレーション結果により，とが「負の相関」をもつことが示唆される．本節では，四辺形に限定して，とが「負の相関」をもって動くことを証明する．与えられた四辺形に対し，第節で定めた方法によって近似エントロピーを計算することを考える．このとき，四辺形に僅かな変形を施し，長方形へ近づけていくと，は増加し，は減少することを示す．（図図参照）

単純化したモデルにおける数学的証明

図モデルとなる四辺形における長さのグラフ

平行な辺を組もつ四辺形について第節で定義した方向で長さをとったとき，その

(24)

第章との間の負の相関

グラフは平行な部分をつ持ち，それに直線を張り合わせたものになる．

ここで，最も単純なモデルとして図のような図を考える．このとき，第節で定義した方向で長さをとったグラフは図のようになる．

の場合を考える．は，閉区間で定義された正値折れ線関数である．

さて，を小さい正の数とし，

となる自然数をとる．また，はより十分小さい正整数とする．

各に対し，

とおく．をランダムにえらぶとき，となる確率をとおく．

となるをとり，なるを１つ固定してランダムにを選ぶとき

(25)

単純化したモデルにおける数学的証明

また，なるを１つ固定してランダムにを選ぶとき

したがって，とをランダムに選ぶとき

ここで，を少しに近付けるとき，すなわちを少しに近付けるときを考える．

のとの差分をとり

に注意すると，の値が減少するときは増加することがわかる．

同様にして

ここで，を考えると

(26)

この式についてとの差分を考え

の分子がであることに注意するとの値が減少するときは減少することがわかる．したがって，このときも減少する．

以上より，与えられた四角形が長方形へ近づくとき，は増加し，は減少することが示された．

との間の負の相関についての反例

前節までに，対象が四辺形を多く含む場合，とが負の相関をもって動くことを示した．しかし，これは一般に言えることではない．

本節では，つのデータ列に対して，近似エントロピーとの間に「負の相関」が成り立たない例をあげる．

二つの数列

を例にとる．

は，自然数に対して，

となる．

のときを満たすの個数は，またのときは

(27)

との間の負の相関についての反例

となる．よって，

となる．

同様にして

一方，のの値は

・

が十分大きいとき

よりはともに増加する．さらに

より近似エントロピーも増加する．

(28)

負の相関の応用：指標の提案，計算量の半減

前節までにより，対象を四辺形に限定した場合，近似エントロピーとが「負の相関」をもつことが示された．これにより，近似エントロピーによって定められる「複雑さの」相対的大小はのみの計算によって求めることができるとみなせる．よって，道路区画地図の複雑さの指標として近似エントロピーの代わりにを用いることを提案する．

近似エントロピーはという数列の階差で定義されている．ゆえに，新指標としてを採用することにより，近似エントロピーを計算する方法に比べ，計算量を約半分にすることができる．

(29)

第章適用例

本章では，第章で提案した方法を実際の道路区画地図へ適用し，の値を算出し，結果を検討する．

道路区画地図への適用実例

本節で用いた地図データは，国土地理院が発行する版数値地図，を用い，

道路中心線だけを抽出したものである．そのなかでも東京都世田谷区・目黒区，および京都市中京区のものを扱い，それらをモノクロファイルに変換した．ここまでは，倉本と同様の条件である．

このモノクロファイルに変換された地図データに対し，近似エントロピーによる複雑さの数値化を行う．ただし，第３章で示した通り，「近似エントロピー」によって定められる「複雑さ」の相対的大小はのみで求められる．そこで，本章では近似エントロピーの代わりにを用いる．詳しくは次の通りである．第２章の方法により，つのファイルに対して，の方向から求めたつの値を求める．このとき方向でのの値を方向でのの値を方向でのの値を方向でのの値をとして

を与えられた地図データの値として採用する．第節参照

(30)

第章適用例

表の平均と分散平均値分散東京

京都

表の平均と分散引用平均値分散東京

京都

表の平均と分散引用平均値分散東京

京都

第節の計算方法を京都市中京区，ならびに東京都目黒区，世田谷区の地図へ適用した結果における，数値の分布は図図のようになった．

京都は，一般に格子状の道路網が多い地域であるといわれる．ここで，東京と京都のシミュレーション結果を比較してみると表表表のようになった．

京都市中京区のの値の平均値は，その一方で東京都目黒区・世田谷区の平均値はとなった．倉本の提案した指標と比較すると，平均値においても，東京都と長方形格子に近い京都市の特徴の違いが現れる結果となった．さらに，図図からも分かる通り，数値の分散においては，地域の特徴の違いがはっきりと表れる結果となった．

分布表については第章参照

(31)

道路区画地図への適用実例

塗り分け方法

本節では，第節での結果を元に，塗りわけを行う．の値が低くなるにつれて，青緑黄色橙色赤となるように段階に塗り分けている．

対応する色赤橙黄緑青

図使用した地図データ（京都市中京区）

道路区画地図に対して近似エントロピー，およびを計算するにあたり，地図データをの正方形領域に分割する必要がある．（第節参照）しかし，正方形領域に分割したことによって，元の地図データではつの区画だったものが，分割されてしまう可能性が考えられる．このとき，近似エントロピー，およびの値は，分割の方法によって異なってしまう．

よって，本研究では，倉本が用いた塗り分け領域を採用している．具体的には，与えられた正方形領域の中心部に元の正方形領域１辺の長さの倍の長さの小正方形領域を考える．この小正方形領域の面積は，元の正方形領域と比べて倍でおよそ半分となる．

(32)

第章適用例

また，塗り分け結果は第節に掲載している．

(33)

第章まとめ

近似エントロピーはという数列の階差で定義されている．この近似エントロピーという概念を道路区画地図のような，長方形格子に近い対象へ適用した場合，その性質から，道路の歪みの度合い，つまり波打ちの程度を表わすと考えられる．このことは，第章・第章で行った長方形格子を歪ませたモデル図形を用いたシミュレーションにより示された．その一方，地図に含まれる閉曲線で囲まれた部分（以下区画という）の分散は反映されないこともわかった．

さらに，このシミュレーションにおいて，近似エントロピーの値とが「負の相関」を持つという現象がみられた．

また，対象を四辺形に限定した場合に「四辺形を微小変形して長方形に近づけるとき近似エントロピーは増加し，は減少する」ことを数学的に示した．

各区画が四辺形に近い道路区画地図においても，近似エントロピーとの間に同様の関係が成り立つとみなせる．

このことを応用し，道路区画地図の複雑さの指標として近似エントロピーの代わりにを用いることで，近似エントロピーを計算する方法に比べ，計算量を約半分にできる．これにより，

計算の効率化を実現することができる．

また，を求める際には，の方向から求めているが，表からも見られる通り，通常の格子図形と斜め格子図形の結果には，大きな差異がみられた．このことから，

の値は角度の影響を受けやすいと考えられる．この影響を軽減するため，の方向から求めた値に対し，の平均，の平均を求め，その最小値をとった．

そして，本研究で提案する指標を実際の京都市中京区，ならび東京都目黒区・世田谷区の

(34)

第章まとめ

道路区画地図へ適用した結果，倉本の提案した周二乗面積比・区画面積の分散に基づいた指標と比較すると，京都など長方形格子が多く含まれる地域と入り組んだ路地が多く存在する東京との差を明確に表わすことがわかった．

(35)

第章付録

基準図形におけるシミュレーション

基準図形一覧

図複雑さが低い図形

(36)

第章付録

図複雑さが中程度の図形

(37)

基準図形におけるシミュレーション

図複雑さが高い図形

(38)

第章付録

シミュレーション結果

表基準図形における

(39)

格子図形におけるシミュレーション

モデル格子図形

分割分割

(40)

第章付録

シミュレーション結果

図正方領域を分割する格子図形についての近似エントロピー

(41)

格子図形におけるシミュレーション

図正方領域を分割する格子図形についての近似エントロピー

(42)

第章付録

その他の指標との比較

Phi 0f Kyoto

-7 -6 -5 -4 -3 -2 -1 0

020406080

図の分布（京都市中京区）

(43)

その他の指標との比較

Phi 0f Tokyo

-7 -6 -5 -4 -3 -2 -1 0

0100200300400

図の分布（東京都目黒区・世田谷）

(44)

第章付録

図の分布（京都市中京区）

(45)

図の分布（東京都目黒区・世田谷）

(46)

第章付録

図との相関グラフ（東京都目黒区・世田谷），相関係数

図との相関グラフ（京都市中京区），相関係数

(47)

図との相関グラフ（分割格子状図形），相関係数

図との相関グラフ（分割格子状図形）相関係数

(48)

第章付録

図との相関グラフ（分割格子状図形）相関係数

(49)

塗り分け結果

を用いた塗りわけ（左）と倉本（右）である。

京都市中京区の塗り分け結果

図図

(50)

第章付録

図図

(51)

塗り分け結果

図図

(52)

第章付録

東京都目黒区・世田谷区の塗り分け結果

図図

(53)

塗り分け結果

図図

(54)

第章付録

図図

(55)

塗り分け結果

図図

(56)

第章付録

図図

(57)

塗り分け結果

図図

(58)

第章付録

図図

(59)

塗り分け結果

図図

(60)

第章付録

図図

(61)

塗り分け結果

図図

(62)

第章付録

図図

(63)

塗り分け結果

図図

(64)

第章付録

図図

(65)

謝辞

指導教官である鈴木登志雄准教授に深く感謝いたします．鈴木准教授には，本研究を進めるにあたり，終始懇切丁寧なご指導と助言をいただくと共に，研究以外のことに関しても多くの助言をいただき，ご指導賜りました．また，ご指導くださった岡田正已教授，そして村上弘准教授に深くお礼申し上げます．

同研究室の畠山友司氏をはじめ，研究室のメンバー，同窓生のみなさんへ，この場を借りて感謝の意を表します．

最後に，著者を支えてくれた多くの皆様に厚くお礼申しあげます．

(66)

(67)

参考文献

(68)

第章付録

川村保敬ランダムなビット列における連：ブール決定木の複雑さと道路区画地図への応用

倉本亮介道路地図複雑さ数値化法における可変単位地区問題

国土地理院数値地図（独自形式）近畿版

国土地理院数値地図（空間データ基盤）関東版

近似エントロピーによる

修士学位論文