九州大学 海洋システム工学専攻
システム設計特論 （木村）(4) 教師なし学習（クラスタリング・自己組織化）

授業の資料等は
p // y p
yjp/g /
http://sysplan.nams.kyushu‐u.ac.jp/gen/index.html
1

【復習】データの量子化（クラスタリング・教師無し学習）
試行

１２３４５６７８９１０

１１

１２

0.21
Ｘの観測値

0.74

0.32

0.25

0.12

0.38

0.32

0.22

0.04

0.44

0.940.16【例】
表のように観測される確率事象において，確率変数 x の観測値は 0 ≦ x ＜ 1 の連続値だが，あるしきい値 Θ1, Θ2を設定して、0 ≦ x ＜ Θ1 のとき「低」,Θ1 ≦ x ＜ Θ2 のとき「中」,Θ2 ≦ x < 1 のとき「高」, という表示を行うことを考える．
このとき， 低」 中」 高」による表示の平均情報量を最大化するには，このとき，「低」「中」「高」による表示の平均情報量を最大化するには，しきい値 Θ1, Θ2 をどのように設定したら良いか？

低

Θ1中Θ2

高2

【復習】データの量子化（クラスタリング・教師無し学習）「低」に分類される事象の確率を P1「中」に分類される事象の確率を P2「高」に分類される事象の確率を P3 と表すと、全表示の平均情報量 Ｉ は
Ｉ = ‐ P1 log2 P1 ‐ P2 log2 P2 ‐ P3 log2 P3
ただし P1 + P2 + P3 = 1 である。
よって等式制約条件下での極値問題になるので、ラグランジュの未定乗数法によって Ｉ が最大になる P1, P2, P3 を求めると
P1 = P2 = P3 = 1／3 である。

空間がｎ次元の場合は?

データは12個なので、これらをちょうど4個ずつ3等分するようにしきい値Θ1, Θ2 を設定すれば良い。

低Θ1

中 Θ2

高3

教師なし学習（ベクトル量子化・自己組織化）
正解ラベルの付いていない観測データを、その分布に従っていくつかのクラスタに分類
正解ラベルの付いていない観測デタを その分布に従っていくつかのクラスタに分類（ただし、分割すべきクラスタの個数は与える）→ クラスタリング（clustering），自己組織化（self‐organization）
正解ラベルすなわち教師信号がない → 教師なし学習（unsupervised learning）
連続な信号空間の離散化 → ベクトル量子化（vector quantization）

x2
C1

C4
C5
C3

C2

x1 4

クラスタリングの目的： 何のためにデータを分割するのか？
１）膨大なデータを
１）膨大なデタを、なるべくそのデなるべくそのデータの持つ「情報」をタの持つ「情報」を損なわないように圧縮・単純化する
２）（連続値で構成された）データを離散化する【情報理論】 符号化・量子化 ＝ 平均情報量の最大化【関数近似】 データ分布に重みづけされた近似誤差の最小化
ボロノイ分割とも関連【データからの知識抽出】 決定木と関連

クラスタリングの目的： 何のためにデータを分割するのか？
１）膨大なデータを
１）膨大なデタを、なるべくそのデなるべくそのデータの持つ「情報」をタの持つ「情報」を損なわないように圧縮・単純化する
２）（連続値で構成された）データを離散化する【情報理論】 符号化・量子化 ＝ 平均情報量の最大化【関数近似】 データ分布に重みづけされた近似誤差の最小化
ボロノイ分割とも関連【データからの知識抽出】 決定木と関連

クラスタリングの代表的手法：ボトムアップクラスタリング法（ヒューリスティクス：最適解の保障なし） 「距離尺度」が重要！
Ｎコのデータ点をすべて別のクラスとみなす状態から出発して、あらかじめ定義されたクラス間の距離に従って最も近いデータ点同士を融合してゆき、最終的に目標とする分割個数のクラスタを得る方法
1
C12
階層的な２分木構造が得られる
C4
3C2x2
4C35
1 C12

データと代表点を融合してできたクラスタC3の代表点

5C33

データ

データを融合してできたクラスタC2の代表点

C2
4x1 7

クラスタリングの代表的手法：Kー平均法（k‐means clustering method）（ヒューリスティクス：最適解の保障なし）
クラスの数Ｋを既知として、以下の繰り返し計算により各クラスの平均ベクトルを求める：
１） Ｋコの平均ベクトルの初期値を適当に選ぶ （学習データからランダムにＫコ選ぶ）。
２） 現在の平均ベクトルを用いて、Ｎコのデータを最も距離の近い平均ベクトルのクラスへ分類する。
３） 全データの分類が終わったら、改めて各クラスの平均ベクトルを計算し直す。
４）） 全ての平均ベクトルが変化しなくなるまで手順２・３を繰り返す
全 の平均ベクト が変化しなくなるま 手順を繰り返す

x2

1

C1

C3

クラスタC3の代表点
代表（平均ベクトル）

523

データ

クラスタC2の代表点（平均ベクトル）C2
4x1

クラスタリングの結果は、平均ベクトルの初期値に大きく依存する 8【参考】クラスタリングとして一般的ではないが、「勢力範囲」の距離を与えてクラスタを生成し、その個数で分布を分析・評価する場合もある

パイプの「グループ化」の必要性
メンテナンスのしやすさ
スペースの確保見栄え
見

集合性をどう表現するか？
着眼点を変えるエルボが密集している。
エルボからパイプの伸びる方向がボプびが一致している
壁付近に配置されている。

エルボの分布のクラスタリングによりパイプの「グループ化」度合いを数値化

エルボのクラスタリングアルゴリズム• パイプのグループ性（集合性）を数値化するアルゴリズム
5 1～4を繰りかえす。全てのエルボがコア対象となれば終了。
5.
1～4を繰りかえす 全てのエルボがコア対象となれば終了= エルボ

End= パイプの伸びる方向End= コア対象ア対象

赤い円は勢力範囲
End

EndEnd10

エルボのクラスタリングアルゴリズム• パイプのグループ性（集合性）を数値化するアルゴリズム
6 クラスタの個数を計算する
6.
クラスタ数 = 5= パイプの伸びる方向

互いの中心が勢力範囲に入るものでグループ化

操作性の良いバルブ配置の評価アルゴリズムにも使用できる11【参考２】 計測機器Kinect
深度計測機器Kinect
KinectはMicrosoftが発売したXbox360の付属機器であり、縦480×横640pixelそれぞれの深度データを取得することが出来る。

対象との距離をスキャン

深度マップ生成12Kinectの深度データからの3DCADデータ生成（1）クラスタリング
計測データである点集合から平面を検出し、距離を考慮した上で複数のクラスタに振り分ける。
本研究
本研究ではクラスタに振り分ける条件の一つ、平面の判定には主成分分析を用クラ タ 振り分ける条件、平面 判定
成分分析を用いる。主成分分析によって得られる三つの固有値に対し、一つの固有値が他の二つの固有値に比べて極端に小さい時、平面であると判定する。

【主成分分析とは】y

データを無相関な（少数の）特性値に縮約する統計処理
データが3次元空間中の点列の場合、第3主成分の分散の大きさが第1・第2主成分の分散に比べて極端に小さければ点列は平面に分布している

x点列が平面かどうかの判定に利用 13

Kinectの深度データからの3DCADデータ生成（ ）ク（１）クラスタリング
タリ グ
まずデ タ点列からランダムに１点を選び、その近傍20点について主成分分析に
まずデータ点列からランダムに１点を選びその近傍20点について主成分分析により平面上に分布しているかどうか判定する。平面に分布していたらそれらの点列を１つのクラスタとする。

Kinectの精度を考慮し、主成分分析での判定は比較的ゆるくなっているため、主成分分析のみでクラスタリングを行った場合、図のように平面からやや離れ離れている点も含んでしまう。
る点も含ん しまう

14

Kinectの深度データからの3DCADデータ生成
3.1クラスタリング

そのため、一度クラスタから平面の方程式を導く。
この時に最小メジアン法を使用することで平面から離れた点に影響されず平面の方程式を導くことが出来る。この平面の方程式とクラスタの点の距離を計算することにより、一定以上離れている点を除外することが出来る。
誤差が許容範囲内の点を追加していく＝RANSAC法
追加出来る点が出来なくなった場合、クラスタに含追加出来る点が出来なくなった場合クラスタに含まれる点の数が一定以上の場合は次のクラスタに移る。点の数が足りない場合はやり直す。
最終的に一定数のクラスタを作成するか、クラスタが作成出来なくなった時点でクラスタリングの処理終了する。
は終了する。
問題に応じて様々な「距離尺度」が用いられる！

詳しい説明は「河内 基樹，木村 元：深度計測デバイスによるデータからの3D 図面自動生成に関する研究，
日本船舶海洋工学会講演会論文集 Vol.17, pp.489‐‐492 」

http://sysplan.nams.kyushu‐u.ac.jp/gen/papers/papersj.html

15

Kohonen（1982）の自己組織化マップ（self‐organization map: SOM）
感覚器上で近い部分は、大脳皮質でも近くの部位へ刺激が投射される → 特徴地図
入力層x1x2

重み wij
出力層：重みが入力ベクトルXに最も近い素子１コだけが反応→ 素子１コが１クラスを分担i*：反応した素子反応した素子

 (i, i * ) ：近傍関数
入力ベクトルXに最も近い重みを持つ素子、およびその近傍の素子の重み変数を、入力ベクトルXに近づける方向へ少しずつ更新していく（競合学習：勝者総取り）
w  w  (i, i * )( x  w )
ijij

iij

データの分布密度を反映したクラスタリング → 空間の充填、データ圧縮符号化

16

ＳＯＭの学習の様子

17そもそも自己組織化とは？
『 要素間の相互作用のみによって自発的に進行する組織化
素相 作
自 的 進 す 組織 』
他の自己組織化の例 骨のリモデリング
他の自己組織化の例：
骨は、応力が繰り返しかかる部分では骨細胞が骨を強化していき、応力があまりかからない部分では消えていく→ トポロジー最適化
トポロジ 最適化

畔上秀幸：形状最適化問題の解法，計算工学Vol.2 No.4(1997)18
東京大学 藤井大地教授のPPT資料より引用

自己組織化の例：細胞群の形態生成
個々の細胞が膨らんだりしぼんだりして互いにくっついたり離れたりを繰り返す

WAA ＝ WBB ＞ WAB

WAA ＞ WAB ＞ WBB

WAB ＞ WAA ＝ WBBWAA: A細胞同士の接着力
WBB: B細胞同士の接着力
WAB: AとBとの間の接着力
単純なルールで複雑な形態を生成
松場弘明, 前川知毅, 清水正宏, 石黒章夫：
制御系‐機構系間の有機的連関を通した自己組み立て・自己修復
計測自動制御学会 第18回SICE自律分散システムシンポジウム, pp.61‐‐66（2006年1月）

自己組織化の例： アリの行動
アリが巣穴の中で物をきれいに（1か所に）格納する仕組み
１） 何も持っていない状態で物にぶつかったら、その物をつかむ
２） 物をつかんだ状態で他の物にぶつかったら、持っている物を放す
３） 上記以外の場合、ランダムに動き回る
上記以外の場合 ランダムに動き回るエサを持ったアリがエサ場から一直線に巣へ戻れる仕組み
１） エサを見つけたアリは地面にフェロモンをつける（蟻道）
２） アリはフェロモンをたどって歩く
３） 分岐点では、分岐点では必ず鈍角に曲がっている
ほうへ曲がる巣

このような単純な制御ルールをいくつか組み合わせるだけで、複雑な動きが可能で、しかも故障などのトラブルに強い頑健（ロバストと呼ばれる）なシステムを構築することが可能な場合がある。トヨタのカンバン方式はこれに類似。
このような分散システムのパフォーマンスは一般に「最適」では無いが、時に非常に強力である

自己組織化を用いたシステム
・倉庫内の物品の配置の最適化
適大きな倉庫から必要な物品を短時間で取り出せるようにしたい→ 物品が使用される毎に、その品の置場を一定距離だけ入口近くへ移動

この操作を繰り返すと、使用頻度の高い順に物品がソートされ、使用頻度の高い物品ほど入口近く（取出し時間が短い場所）へ
これはデータベースにおいて検索時間を減らすようなデータの格納方法としても使用される
類似例：不要書類の整理法（超整理法）
新しい書類が発生する度にファイルして時間順に並べていき 使用したら また先頭に新しい書類が発生する度にファイルして時間順に並べていき、使用したら、また先頭に戻すという方法。デメリットはめったに使わないファイルはひたすら探すしかない点

機器の配置は、それらを繋ぐパイプのコストを大きく左右

機器配置問題に「自己組織化」を利用できるか？

22自己組織化を利用した解決法
接続先の要素接続先の要素接続先の要素中点

三角形の重心

接続先の要素注目する要素(a) 注目する要素の接続先が2箇所の場合

接続先の要素注目する要素(b) 注目する要素の接続先が３箇所の場合

上記の操作を全ての要素についてランダムな順序で繰り返す→ こんがらがっていた要素が整然と並ぶ
23

自己組織化

13 floatingg equipments
q p
5 fixed equipments
19 pipes

Demo自己組織化

32 floatingg equipments
q p
4 fixed equipments
72 pipes

Demoランダム配置

自己組織化
オペレーション
適用後

26

グラフ構造可視化： Eadesのスプリングモデル●データ間の接続関係を利用してグラフ構造を可視化するグラフ自動描画アルゴリズムの一種

データ同士に接続関係がある場合、2次元平面上距離を d ij とするとするの距離をfaij   log

d ijdの引力で引き合う

またデータ同士の接続に関係なく、データ間はfrij  
ただし

1d ij2の斥力によって反発する。

d はデータ間の理想長、 ,  は定数

相互結合型ニューラルネット：ホップフィールドネットワーク
ホップフィールドネットワークのニューロン素子： １ or －１の２値

fwij

10

NET－1
●自分自身への結合重みはゼロ●結合重みは対称

wii  0wij  w ji

●ネットワークへの入力： 全てのニューロンユニットに初期値「１」または「－１」を与える●ネットワークによるパターンの記憶： 以下の計算により重みwij を決める

T xit x tj
wijj   t 1
0i jtx
ただし i は t 番目のパターンの i 番目のユニットi j

記憶させるパターン数Tは、ユニットの個数の１５%程度

同じ値のユニット同士を結ぶリンクを強化＝Hebb則●ネットワークによる計算： ネットワークに未知パターンを入力し、28ユニットを適当に選んで計算。状態が安定するまで続けると記憶したパターンへ収束記憶パターン

入力パターン

想起された
パタ ン
パターン

入力パターンが多少歪んでいたりノイズを含んでいても修正
あまり変なパタ ンを入れると安定しなかったり、反転したりあまり変なパターンを入れると安定しなかったり反転したり変なパターンへ収束したりする
29

ホップフィールドネットワークのエネルギー関数と最適化
1 n n
エネルギー関数ネ ギ 関数 E    wij xi x j
2 i 1 j 1

入力パターンEx
記憶パターン１

記憶パターン２「想起」プロセスによって、エネルギー関数値が極小値になる方向へユニットの値Ｘが遷移

wij  xi x jに正比例するとき、Eは常に負の値でエネルギー関数を最小にする

30

ボルツマンマシン

ボルツマンマシンのニューロン素子：
シグモイド関数を確率分布とした
0または1の離散的な値
1f  NET f1  exp T
wij

1

温度T高温度T低n

エネルギー関数

En1E    wij xi x j
2 i 1 j 10NET

温度Ｔを少しずつ下げていくことで、大域的な最小値へ到達 （焼きなまし法）

x 31

まとめ
（１） クラスタリング＝データ圧縮：平均情報量をなるべく大きく（２） クラスタリング法：
・ ボトムアップクラスタリング法
・ ｋ平均法・ Kohonenの自己組織化マップ「距離尺度」が重要！
最適化が保障されないヒューリスティクスだが、少ない計算量で準最適解を得る（３） 自己組織化とは？
骨のリモデリング・アリ・配置法

要素間の単純な相互作用で自発的に進行する組織化
頑健で、場合によっては非常に効果的（４） 相互結合型ニューラルネット
パターンの想起＝エネルギー関数の最小化【参考文献】
・麻生英樹 津田宏治 村田昇： パターン認識と学習の統計学、岩波書店（2003年）
・麻生英樹、津田宏治、村田昇：
パターン認識と学習の統計学 岩波書店（2003年）
・Stuart Russell and Peter Norvig: Artificial Intelligence – A Modern Approach,32
Pearson Education Inc. (2003)