1

データサイエンス概論I＆II
クラスタリングと異常検出

九州大学 数理・データサイエンス教育研究センター

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

2（再掲）距離は超便利！
 データ間の比較が定量的にできる
 「𝒙と𝒚は全然違う/結構似ている」 「𝒙と𝒚は28ぐらい違う」
 「𝒙にとっては，𝒚よりも𝒛のほうが似ている」
 データ集合のグルーピングができる 「近く」のデータどうしでグループを作る 「クラスタリング」と呼ばれる
 データの異常度が測れる
 「近く」にデータがたくさんあれば正常，一つもなければ異常[Goldstein, Uchida, PLoSONE, 2016]

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

3

データのクラスタリング①

クラスタリングの基本的考え方

クラスタリング＝“clustering”
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

4

データ集合をグルーピングする
 我々は「距離」や「類似度」を手に入れた その結果，「与えられたデータ集合」を「それぞれ似たデータからなる幾つかのグループに分ける」ことが可能に！

 要は「大量のデータを整理整頓してわかりやすく！」九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

5

グルーピング（クラスタリング）は何が便利？
全国ラーメン屋の「味」データを例に考える
 いくつのグループ（クラスタ）に分かれたか？
 グループの分布の把握

主要なラーメンのタイプはいくつあるのか？

 各クラスタのメンバ数はどうなっているか？
 各グループのメンバの多寡 微小クラスタ（マイノリティ）や，巨大クラスタ（マジョリティ）各タイプの店がどれぐらいあるのか？（どの味がマジョリティー？） 各クラスタの代表データ(代表ベクトル)は？
 主要例を理解 膨大なデータを高々数個で概観

各タイプの最も代表的な店はどれか？
（それだけ食べ歩けばラーメンの味はほぼわかる）

 各クラスタの広がりは？
 各グループの変動傾向理解

各タイプで，味のバリエーションはどれぐらい？
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

6

グルーピング（クラスタリング）は何が便利？
アンケートデータを例に考える
 いくつのグループ（クラスタ）に分かれたか？
 グループの分布の把握

典型的な回答のタイプはいくつあるのか？

 各クラスタのメンバ数はどうなっているか？
 各グループのメンバの多寡 微小クラスタ（マイノリティ）や，巨大クラスタ（マジョリティ）「典型的な回答のタイプ」
それぞれはどれぐらいメジャーなのか？

 各クラスタの代表データ(代表ベクトル)は？
 主要例を理解 膨大なデータを高々数個で概観
 各クラスタの広がりは？
 各グループの変動傾向理解

典型的な回答は，どんな回答パターンか？
全回答をみなくても，ざっくり傾向がわかる！

各タイプに属する回答例のバリエーションはどれぐらい？
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

7

クラスタ(cluster)とは？
 「房（ふさ）」，「集団」，「群」

クラスタ感染[国立感染症研究所]

PCクラスタhttp://www.ims.cs.uec.ac.jp/~naoki

星団(star cluster)

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

8クラスタリング(clustering)＝
データの集合をいくつかの部分集合に分割する(グルーピング) 各部分集合＝「クラスタ」と呼ばれる九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

9各クラスタから代表的なデータを選ぶと...
これらの代表データを見るだけで，データ集合全体の概略が見える

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

10

どういう分割がよいのか？
 𝑁個のデータを𝐾個に分割する方法はおよそ𝐾 𝑁 通り
 100個のデータを10分割→およそ10100 通り (全宇宙の元素の数1080 より大) 近くにあるデータが，なるべく同じグループになるように
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

11

データのクラスタリング②

𝑘-means法

Mean = 平均．だから「平均を𝑘個」求める方法．
古典的だが，いまでもクラスタリングの代表的方法（便利！）九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

12𝑘-means法（0）初期代表ベクトル
わかりやすい比喩：
代表＝アイドル，データ＝民衆

データ例えばランダムに与える

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

13𝑘-means法（1）データの分割：
代表ベクトルとの距離でデータをわける

わかりやすい比喩：
民衆は自分に一番近いアイドルのファンになる

代表ベクトルのファンクラブ（支持者集合）

注：用いる距離によって分割は変わる

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

14𝑘-means法（2）代表ベクトル更新
わかりやすい比喩：
けなげなアイドルがファンクラブの真ん中に移動

この中のデータの平均に移動

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

15

𝑘-means法（1）データ分割
わかりやすい比喩：
アイドルの移動により，ファンクラブ構造が変ってしまう

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

16

𝑘-means法（2）代表ベクトル更新
わかりやすい比喩：
けなげなアイドルは新しいファンクラブの真ん中に再び移動

以後，代表ベクトルが動かなくなるまで反復九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

17

𝑘-means法実例：データセット

データ

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

18

𝑘-means法実例：結果（𝑘 = 3）

初期代表
ベクトル

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

19

𝑘-means法実例：結果（𝑘 = 5）

最初，もうちょっとよいところに置いてあげればよかったのに…

ファンが一人もつかずにそのまま残ってしまった！

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

20

𝑘-meansは「初期値が違うと結果が異なる」：
それが困るなら…
 「マルチスタート戦略」をやってみてもよい 異なる初期値で𝑃回k-meansを実施
 𝑃個の結果のなかで，最もよかった結果を選ぶ
 “k-means++”という，うまい初期値の決定法もありk-means++による初期値選びのイメージ
ランダム

遠いやつ

クラスタ数kの決め方も色々→付録

遠いやつ九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

21

データのクラスタリング③

その他のクラスタリング法

まだ色々あります九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

22

𝑘-means，もう一つの問題（？）
 代表データは「平均」なので，原データの一つではない 原データにあるものを「代表」としたい場合には...!?
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

23

𝑘-medoid法
 Medoid = 「クラスタ内のデータの中で他のデータとの距離を最も小さくできるもの」

 「平均」ではない．

medoidならば九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

24

𝑘-medoid法と𝑘-meansの違いは一か所だけ！

この中のデータのmedoidに移動

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

25

もう一つの代表的クラスタリング法：
階層的クラスタリング

wikipedia の図を一部引用
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

26

異常検出

距離さえあれば，異常なデータを見つけることができる！
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

27

異常検出（異常検知）とは？
 今与えられたデータが「一般的に期待していたデータ」とは異なるものであることを見出す手法

 なぜ異常は起こるか？
 機器やセンサの故障，身体の病気やケガ うっかりや見落とし，事故や失敗など，人為的ミス
 侵入や破壊，悪用など，意図的な悪意のある行為
 甚大な自然災害など，想定外もしくは稀な現象の発生
 Etc...

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

28

異常検出の応用例
 人々を対象とした異常検出
 エレベータ内のカメラで人々の動きを認識し，さらに普通でない動きを判断 独居者の異常検出：日常と異なる行動パターンを通知し通知
 病院内での患者の異常検出：特に気づきにくい早期の異常検出
 食品や生産物の異常検出
 表面の傷の検出，異物の検出
 機械・建造物・コンピュータシステムの異常検出
 サイバー攻撃の検出
 機械の故障の検出
 橋や道の異常検出※そのうちやる「分類・パターン認識」とも関係

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

29

距離による異常検出の基本的な考え方
 「注目しているデータが，他のデータから離れている(距離が遠い)」→

異常度が高い周りにデータなし→高い異常度周りにデータ多い→低い異常度
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

30

異常の種類(1/3)
 大局的異常 まわりに「近い」データがない「似た」データがない＝どう考えても異常 𝑥1 , 𝑥2

局所的異常

大局的異常

微小クラスタ

大局的異常[Goldstein, Uchida, PLoSONE, 2016]

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

31

異常の種類(2/3)
 局所的異常 そのデータ周辺の平均的な近さで考えると，「近くない」
 𝑥3 は局所的異常• 付近にある𝑐2 グループ基準でみると異常• ただし𝑐1 グループ基準だとそこまで遠くはない

わかりやすい比喩：
その家がある都会では「町はずれの一軒家」だが，田舎視点だと十分ご近所[Goldstein, Uchida, PLoSONE, 2016]

局所的異常

大局的異常

微小クラスタ

大局的異常九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

32

異常の種類(3/3)
 微小クラスタ 周りに近いデータはあるものの，その数は限定的 𝑐3 の3つのデータが相当

局所的異常

大局的異常

微小クラスタわかりやすい比喩：
要は「オタク」集団(?)．
近くに同志は少数いるが，世間全体からは浮いている[Goldstein, Uchida, PLoSONE, 2016]

大局的異常九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

33

𝑘近傍法による異常検出(1/3)
𝑘個の近いデータ原理
 単一タイプ：𝑘番目に近いデータへの距離

𝒑 − 𝒒𝑘 or+ ⋯ + 𝒑 − 𝒒𝑘

 合計タイプ： 𝒑 − 𝒒1 + 𝒑 − 𝒒2
 大局的異常検出

𝒒3

𝑘=3𝒒1
𝒑𝒒2

 𝑘 − 1個のデータからなる微小クラスタも異常として検出可能
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

34

𝑘近傍法による異常検出(2/3)
異常度計算結果例(𝑘 = 10, 合計)
 半径が大きな点(データ)ほど異常度が高いと計算されている[Goldstein, Uchida, PLoSONE, 2016]

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

35

𝑘近傍法による異常検出(3/3)
問題点 「ぎっしりクラスタ」と「すかすかクラスタ」が共存していると...

「都会基準で田舎を全部異常」と見ていいのか？
「都会は都会基準」「田舎は田舎基準」で見たいところ(要は局所異常の検出が苦手→LOF法(付録)を使おう)
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

36

【付録１】
クラスタ数𝑘はどうやって決めるか？

「絶対これ！」という正解はないのがポイント．
「このクラス全体をグループにわけろ」と言われても，グループ数は色々考えられるのと同じ
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

37
37

𝑘-means，代表パターン数 𝑘 は？
 これは中々難しい

Wikipedia “Determining thenumber of clusters in a data set”

 「えいや！」と決める
 𝑘を増やしながら誤差や認識率を測る
 飽和したらやめる
 LBG/ISODATAやx-meansを使う
 次スライド Calinski-Harabasz基準のような，クラスタリングの精度評価指標を利用する

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

38
38

𝑘をどうやって決めるか？(1/4)
徐々に𝑘を増やすアルゴリズム
 LBG法とか，ISODATA法と呼ばれます
データ集合

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

39
39

𝑘をどうやって決めるか？(2/4)
とにかく𝑘を変えながら，誤差を評価
 例えば「誤差＝代表ベクトルとの平均的距離」と定義して， 𝑘を徐々に変えながらその誤差を測って，誤差これぐらい?

𝑘 あまり減らなくなったところで「えいや！」と決める
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

40

𝑘をどうやって決めるか？(3/4)
x-meansk-meansを実行

各クラスタで2-means

BICを測る(ラフに言えばクラスタ数と精度のバランスを評価)

2-meansによりBICが改善されてるのなら採用

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

41
41

𝑘をどうやって決めるか？(4/4)
Calinski-Harabasz基準（Pseudo Fとも）
 定義

代表パターンがどれぐらい散らばっているか

クラスタ間分散 𝑁 − 𝑘∙
クラスタ内分散 𝑘 − 1
各クラスタ内でサンプルがどれぐらいまとまっているか 大きいほどよい！

クラスタ数3の場合が(この基準では)最良

https://jp.mathworks.com/help/stats/clustering.evaluation.calinskiharabaszevaluation-class.html

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

42

【付録２】
スペクトラルクラスタリング

グラフ＝近いものどうしが手を結んでできるネットワークのこと

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

43
43

スペクトラル・クラスタリング (1/2)
 グラフ表現されたデータ集合のクラスタリング
 近いデータ間をつないでグラフ構築
 その近接性を極力保存したまま低次元空間に写像
 低次元空間でk-means

http://d.hatena.ne.jp/mr_r_i_c_e/20121214/1355499195「近さ」には任意性あり

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

44
44

スペクトラル・クラスタリング (2/2)
K-means

スペクトラル・クラスタリング

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版
http://ogrisel.github.io/scikit-learn.org/sklearn-tutorial/modules/clustering.html

45

【付録３】
異常検出，３つのシナリオ

本編では，シナリオ３「単にデータの集合しか与えられない」状況を説明しました九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

異常検出，３つのシナリオ(1/3)：「正常データ」と「異常データ」が共に準備できる場合

4646

 正常・異常を分離する「面」を求める問題

この面より外側＝異常

正常データ

異常データ
 難点：「めったに発生しないのにバリエーションは膨大」な異常データを集めるのが大変！

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

異常検出，３つのシナリオ(2/3) ：「正常データ」のみが準備できる場合

4747

 正常データを包含する「面」を求める問題

この面より外側＝異常正常データ

 利点：異常データ収集の手間は不要 難点：しかし全データが正常であることを「担保」する必要は残る
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

異常検出，３つのシナリオ(3/3) ：単にデータの集合しか与えられない48
48

 データ自身に「自分が異常かどうかを判断させる」問題

 最も現実的なシナリオだが，「判断基準」をどうするか？
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

49
49

３つのシナリオ～それぞれの呼称
 第１：「教師あり」異常検出
 結果は 正常 or 異常 第２：「半教師付き」異常検出
 結果は 正常 or 異常 第3：「教師無し」異常検出
 結果は 異常の程度(異常度)九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

50
50

３つのシナリオ～それぞれの対応法
 第１：「教師あり」異常検出
 (2クラス)パターン認識 (後述)

 第２：「半教師付き」異常検出
 1-class SVM

 第3：「教師無し」異常検出
 k近傍法, LOF
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

51

【付録４】
Local Outlier Factor (LOF)法

局所異常も検出できる手法！

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

52
52

Local Outlier Factor (LOF)法 (1/2)
原理 注目データ周囲の密度が他に比べ低い→LOF大 局所異常検出も可能
最もわかりやすい𝑘 = 1の場合
𝒑の最近傍

𝒑−𝒒1
LOF=𝒒1 −𝒓1
𝒒1 の最近傍𝒓1𝒒1𝒑

要するに，自分の周り(分子)と自分の近傍の周り(分母)を比較

九州大学 数理・データサイエンス教育研究センター／ 2022年9月版

53Local Outlier Factor (LOF)法 (2/2)
ぎっしり・スカスカどちらも大丈夫
𝒑−𝒒1
LOF=
𝒒1 −𝒓1
𝒓1

~1
𝒑−𝒒1
LOF=
𝒒1 −𝒓1~1

𝒑𝒒1

𝒓1

𝒒1

𝒑𝑘 > 1の場合はもう少し式もややこしくなります
九州大学 数理・データサイエンス教育研究センター／ 2022年9月版