|
・「k平均法（k-means clustering）」を読み解く（仮）
・さらに「k平均法（k-means clustering）」をくわしくカワサキ（談）
・もっと！「k平均法（k-means clustering）」をはげしくカワサキっ
・表6 「between_SS（BCSS）」「total_SS（TSS）」の挙動（k=2...5）
（約13000字）
あくまでドラフト（草稿）ですので、あしからず。「導入編」（[3524]）、「概説編」（[3525]）、「処理編」（[3526]）からの続きです。必ず、「導入編」（[3524]）から順にお読みください。
○「k平均法（k-means clustering）」を読み解く（仮）
「階層的クラスタリング」については詳説は省きます。ここでは「非階層的クラスタリング」のうち有名なアルゴリズムとして「k平均法（k-means clustering）」を、主に小学校への算数の単元の配当を意識しながら、詳しく読み解くことを試みます。
・処理編（[3526]）から
> 「R with Excel」を体験してみよう
> ※1
ハレでも（ざーざー）アメでも（ごろごろ）アラシでも（ぴよぴよぴよ）うぃーあーざあーるういずえくせらー…ズ（ぱらぼーら）…いえ、「※1」は、「ss：sum of squares（二乗の総和）」で、これはk平均法ですよという文脈の上では明示せずとも「『距離の』二乗の総和」ですね。
・Google ストリートビュー でっかいどう！「セラーズやまだ」さん（苫小牧市）付近のぱらぼーら（仮名）
https://goo.gl/maps/tKjDXSUpgER2
https://goo.gl/maps/YZEfsCRFNvA2
https://goo.gl/maps/VPPT9Wgqew12
https://goo.gl/maps/PtXmeqN18gK2
※室蘭本線ならびに錦岡南通は本文とは無関係です。ましてやネズミーナントカっぽい日除けみたいなのを張ってある小学校の建物が見えたりするかもしれませんが、たぶん気のせいです。
ここに出てくる「88.5％」という数字は、「mykm3$betweenss」（between_SS：187.155）の値を「mykm3$totss」（total_SS：211.5083）の値で割ったもので、「（クラスターの重心間の距離の二乗の和）／（すべての点の間の距離の二乗の総和）」を示しています。これは「クラスターの分かれ度合い」を意味しています。
※なお、「totss」などの表記は、パッケージの作者がてきとーにつけたものですから、あくまでそういうものだと思って、論文などにそのまま「totss」などと書いてはいけませんよ。これにはさすがの黒柳さんもびっくりです！（棒読み）
※「1−0.885＝0.115」みたいなことをして、「（クラスターの半径が）11.5％は重なっている（確実にクラスターが異なると断定できないあいまいな領域がそれだけある）」という理解をしてもいいんでしょうか。そもそも、「（クラスターの重心間の距離の二乗の和）／（すべての点の間の距離の二乗の総和）」は、絶対に1を超えませんよね。（『負の半径』などと言い出さない限り、の意。）
■表6 「between_SS（BCSS）」「total_SS（TSS）」の挙動（k=2...5）| k | BCSS | TSS | BCSS / TSS | | | | | | 2 | 169.6 | 211.5 | 0.802 | | 3 | 187.2 | 211.5 | 0.885 | | 4 | 192.9 | 211.5 | 0.912 | | 5 | 193.4 | 211.5 | 0.915 |
※「重なり」が『15％くらい』（[3483]）が、最も複雑なデータであるというような、そういうところに着目する指標って、ないんでしょうか。翻って、「『複雑さを最も温存』したクラスタリングができた」というのを「『よく』クラスタリングできた」とみなしたい、ということです。「BCSS / TSS」が単に大きければ大きいほどいいというものではないことは、明らかではございます。（ほとんど）ぜんぶバラバラにしてしまっては、「クラスター（房）」じゃないですよね。
・スーパーえむジンせんせい「理解を助けるため」の用例ならびにご近影のイメージです付近
http://www1.doshisha.ac.jp/~mjin/R/Chap_29/29.html
http://www.cis.doshisha.ac.jp/english/course/linguisticdata/
http://www.cis.doshisha.ac.jp/english/course/linguisticdata/img/02_kim.jpg
※学位が「学術」であらせられるので、新聞記者のかたなどが紹介のしかたに困りそうだという戸惑いを表現して「スーパーえむジンせんせい」と紹介してみます、の意。（きわめてメッソウではございました。）旧タカラ「スーパーせんせい」（1997年）については[3476]を参照。よーしはりきって…スーパーえむジンせんせいをこえてゆけっ！ …お、おぅ。（棒読み）
> 理解を助けるため、2次元平面上の散布図を用いて、k 平均法のアルゴリズムのイメージを説明する。
あくまで「理解を助けるため」です。クラスタリングは多変量（多次元）に適用してこそ意味のある手法といえますから、最終的にも散布図として（たかだか2次元で）理解しさえすればよいのであれば、「主成分分析」のみを行なって、第1と第2の主成分をとって散布図を描きさえすれば、それでよいのです。
※「主成分分析」は、不良品の発生や商品のブランドイメージなどを分析して、影響の大きい変量を探り当て、最小のコストで最大の効果を得ようというような目的の分析です。分析にかける変量が（工場の管理や商品開発それに広告などの上で）じぶんたちのコントロール下にあるということですね＝分析結果を見て「あしたから」変量そのものをいじっていけるということですね。「分類」とは目的が異なるのです。中には、クラスタリングの結果を主成分の（平面）散布図で示してしまうという意味不明な例示も散見されますが、…やっぱり意味不明だと思いました。「ＭＴ（マハラノビス・タグチ）システム」については[3283]を参照。
※どうにもならない感じのデータを、それでもああだこうだと探索的に分析しなければならない、かなりウンザリする状況で使用を迫られるのがクラスタリングであるとのあきらめでもございます。クラスター分析などというケッタイなものしか出番がないような混沌とした状況というのは、まあ、遠巻きに見ているだけで済めばそれに越したことはないとの…いえ、ま、そうともいっておられないのでクラスタリングを使いながらクラスター分析に取り組むわけですよ、ええ。
・（再掲）ターャジス「業務用 きくのIFCコーヒー」の風味傾向図です（※アイスコーヒーは飲料です。）
https://www.sujahta.co.jp/item/gyomu/img/aroma.gif
・「主成分分析」元デンソー氏の見解です（2016年9月11日）
http://techon.nikkeibp.co.jp/atcl/column/15/415548/091100016/?P=5&rt=nocnt
> 実は、かつてトヨタグループもそうでした。理論的な説明が中心の多変量解析の研修を行っていたところ、難しくて、技術者といえども実務で使いこなせなかった。研修の講座として学んでおしまいで、実践には至らない。それでは多変量解析を学ぶ意味はありません。
ほぉお！（略）いままさに「自由研究総合（自由形）」などと仮題してまで（メッソウですけど）取り組みたいのも、そういう感じのモチベーションなのですよ。わかりますわかります！
> こうして理論を学んだ上で手計算する方法をやめ、計算を自動化できるソフトウエアを使うことにしました。加えて、実践形式の研修を始めました。講義に加えて、職場から持ち寄った課題をテーマにグループワークを行う方法を取り入れたのです。すると、現場での多変量解析の活用率が飛躍的に伸びました。
スバラシイ。…実にスバラシイ。（※センエツながらココロの底からの感想でございます。）
> まず、Excelにデータを入力する。例えば、中古マンションの広さ、築年数、価格といったデータを入れる。次に、そのExcelデータをソフトウエアに貼り付ける（取り込む）。続いて、「多変量解析」ボタンを選択し、「重回帰分析」ボタンを選ぶ。すると、「回帰式」が出てくる。ここで「予測」ボタンを選択し、目を付けた中古マンションの広さと築年数のデータを入れると推定価格がはじき出される──。簡単でしょう？
いや、まあ、やっぱり、その、ハレでも（ざーざー）アメでも（ごろごろ）アラシでも（ぴよぴよぴよ）うぃーあーざあーるういずえくせらー…ズ（ぱらぼーら）「R with Excel」みたいなの、するんですね。わかりますわかります。
・ミラノにあるという「R」のユーザー会いわく「XLConnect」付近
http://www.milanor.net/blog/steps-connect-r-excel-xlconnect/
> XLConnect offers many features to realize a good connection between R and Excel.
> An Excel data grid becomes an R data.frame!
> An Excel named region is reported in R and used to place R objects in the right position!
ここまで密につなげるのはまた別の話で、仕事の道具として効率を追求する場合の話ですね。
・「主成分分析」日経リサーチの見解です
https://www.nikkei-r.co.jp/glossary/id=1632
> 日本経済新聞に掲載されている企業評価ランキングでは、調査データをもとに主成分分析を適用した結果が使われている。1997年に始まった環境経営度調査の企業ランキングでは主成分分析が利用された。また品質経営度調査でも、主成分分析によるスコアで企業ランキングが発表されている。
> このランキングはイメージ25項目を総合的に合成した得点に基づくもので、人々の心の中に蓄積されているイメージの多さ・豊かさを示していると解釈できる。
> 絶対的な基準はない。寄与率80%以上という基準には一般的な根拠はない。
> 結果として解釈が難しいときもある。その意味では、因子分析のほうが解釈しやすいので、マーケティング調査では主成分分析よりも因子分析が利用されることが多い。
> 仮に、25変数の本質的な次元数が5であるとすれば、第6固有値以降は平行になる。（略）実際のデータでは、正確に次元が定まってはいないが、ゆるやかに平行に近くなるところがあれば、その直前までを採用すべき成分の個数とする。これがスクリー基準である。
> 相関のないデータは主成分分析を適用できない。計算はできるが分析する意味はない。主成分分析は相関のあるデータを無相関の合成変数に変換する手法なので、すでに分析は終わっていることになる。
なお、「階層的クラスタリング」「非階層的クラスタリング」とも、回帰式も検定もない（外側で工夫する必要がある）ので「解析」とは呼ばれません。しかし、回帰式も検定もあるという意味での「多変量解析」だけが「多変量」の分析の方法であるというわけではないというところは、おさえておかなければと思わされます。
○さらに「k平均法（k-means clustering）」をくわしくカワサキ（談）
ここでは、（多変量の）クラスタリングそのものを理解していきたいので、「k平均法」を詳しく見ていきましょう。
仮に、平面上で辺の長さが2である正三角形の頂点に相当する3つの点があれば距離の総和は6で、距離の二乗の総和は12です。これを2つのクラスターに分けたとき、ある頂点から接しない辺に向かっておろした垂線の長さ（√3≒1.732）が、2つのクラスターの重心間の距離で、クラスターが2つの場合は、これがすなわち総和であり、二乗の総和は3（＝√3の二乗ですからね）となります。この場合、「3／12＝25％」となります。
なんだかそういうような感じの数字が出ていて、上掲の例では「88.5％」になったということです。クラスター間が『よく』離れていれば、この分数の「分子」が大きくなり、しかし、要素の総数が多ければ「分母」がとてつもなく大きくなっていくという数字ではあります。分数を計算してしまって「％」で表してからの数字だけでは一概には何とも言えず、やはり分数そのままの形式で眺めて検討する必要のある指標だと思えてきます。
・啓林館「発展的な考え方を育てる算数指導 〜少人数指導における発展コースの学習を通して〜」
http://www.shinko-keirin.co.jp/keirinkan/sansu/jissen/0412/4nen/
「垂線」は中学校2年への配当ですが、「二等辺三角形を2つ」「高さ」といえば小学校の4年の内容です。なんとか説明できる範囲ではないでしょうか。本当でしょうか。究極的には、平面なら実際に定規で測ればいいんですよ。…うーん。糸に印をつけながら「長さの総和」（の量感）を知覚させますか？ …うーん。「すべてのペア」を辞書式に書き下した表をつくって、順番に距離を定規で測って、表を埋めていきますか？ …なるほど、このほうが確かだなぁ。
・かみつたセンセイ
http://www.kamishima.net/jp/clustering/
> Guha 98
> クラスタの対象数に差がある場合には
数の問題ではなく、あくまで距離の問題だと思えてくるのですが、気のせいでしょうか。
・Wikipedia
https://en.wikipedia.org/wiki/K-means_clustering
> Discussion
> The result of k-means can also be seen as the Voronoi cells of the cluster means.
平面を分割していく「ボロノイ図」として見ようというのは、あくまでそういうデータであるときに限り有効との理解ではございます。k平均法は、あくまで飛び飛びに距離を見ながら操作していくだけのアルゴリズムなんです。結果的にボロノイ図みたいになるときもあるけれども、それはそういうデータだったからそうなるのであって、ボロノイ図を描こうというアルゴリズムでは、決してないのです。（…と理解しました、の意。）
・（あくまで参考）ウィキペディア「離散ボロノイ図」
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3
・再びWikipedia
> （略）so as to minimize the within-cluster sum of squares (WCSS) (i.e. variance).
> Because the total variance is constant, this is also equivalent to minimizing the squared deviations between points in different clusters (between-cluster sum of squares, BCSS).
> Since the arithmetic mean is a least-squares estimator, this also minimizes the within-cluster sum of squares (WCSS) objective.
※variance：分散。sum of squared deviations：偏差平方和。
「WCSS」「BCSS」それに（別のページですが）「TSS」という美しい表記が出てきます。「BCSS / TSS」というのは、偏差平方和どうしの割り算ですね。
・「マシンラーニングシリーズ：k-means」（2017年4月）
http://h22242.www2.hpe.com/products/software/hpsoftware/vertica/pdfs/Vertica%20Machine%20Learning_Series%20k-means_ja.pdf
> ここでは、UCIから公に入手可能な210行と8列の小さなデータセットを使用します。このデータセットには、3つの異なる種類の小麦（Kama, Rosa, Canadian）の幾何学的特性が含まれています。
> 今回のデータセットでは、3種類の小麦があるので、3つのクラスタが必要であると想定できます。
おおー（略）よさげなデータセットですのう。
> クラスタの二乗和内（WCSS）−この値は、クラスタの結合を測定します。この値が小さいほど、クラスタがよりコンパクトになります。各データポイントが1つの重心と一致するようにデータポイントの数と同数のクラスタがある場合、WCSSはゼロです。
> クラスタの二乗和の間（BCSS）−この値は、クラスタ間の分離を測定します。クラスタがひとつだけの場合、この値はゼロです。
> 総二乗和（TSS）−BCSSとすべてのWCSSの合計に等しい値です。
> BCSS/TSS比−クラスター内の結合度とクラスター分離度が高いほど、この値は1に近くなります。
おお、ちょうどよい「答えあわせ」っぽいですよ。えー、どれどれ？（略）「BCSS」「WCSS」「TSS」の説明だけして、クラスタリングの結果のよしあしの判断へのこれらの指標の使いかたは、述べられていないことがわかります。
・「ぐちゃっと経験的な値が書いてあるっぽいです？」付近
https://image.slidesharecdn.com/finalpresentationdiscussion-120506151937-phpapp02/95/gray-image-coloring-using-texture-similarity-measures-38-728.jpg
・なぜか出てくるNHK技研のイメージです
http://www.ht.sfc.keio.ac.jp/~masato/mt/images/NHK-DSC_0140.jpg
※「TSS means」で誤ってヒットしてます。…Googleさーん！ そっちは検索ノイズですよぅ。（棒読み）
クラスター数を指定されてから実行される「k平均法」のアルゴリズムとしての「ゴール（計算を終了する規準）」は「WCSSの最小化」であるわけですが、しかし、わたしたち、どのようにクラスター数を決めればよいのかというところで、この素朴な「k平均法」のアルゴリズムの外側に、なお課題があるわけです。
・統計学用語辞典「sum of squares」
http://www.weblio.jp/content/%E5%A4%89%E5%8B%95
http://www.westatic.com/img/dict/tkgyg/TokeigakuNote/Univariate/ss.png
> 観察値Xiから平均値Xbarを引いた偏差の2乗和 Σ(Xi-Xbar)2。
> （偏差）平方和とも呼ばれる。
すみません、「二乗」って何年生で出てくるんでしょうか。1桁なら九九でいいんでしょうか。（統計学や工学で）「二乗」するのは、『違いを際立たせる』（大げさに見せて、見間違えないようにする＝誤差に惑わされにくくする＝多少の誤差では順位が入れ替わらないようにする＝計算結果を安定させる＝必ず白黒つけて計算を終わらせる）というような（ややトートロジー的でもある）説明をしてもいいんでしょうか。
※高校の数学II・B「数列と対数」からの（工学的な数学もしくは物理学でいう）「遠近感」については[3400]を参照。
・（参考）啓林館「新学習指導要領における算数・数学内容系統一覧表」
https://www.shinko-keirin.co.jp/keirinkan/tea/pdf/sansu_sugaku_list.pdf
スーパーえむジンせんせいのページでは、「k平均法」については「正解データとのクロス集計表」を書いてからの『正解率』だけが言及されています。もっと詳細な検討は「モデルに基づいたクラスタリング（Model-Based Clustering）」で行なえといって、いきなり「ガウス混合分布モデルの情報量規準 BIC（Bayesian Information Criterion）」にまで飛ばされます。しかし、この「情報量規準」という、いつかどこかで赤池センセイもびっくりなソレっぽいのを、「k平均法」を使った場合にはまったく議論しなくてよいということでは、決してないとも思えてくるのです。
> オーソドックスな多変量データ解析の書物のほとんどは階層的クラスター分析を扱っているが、非階層的クラスター分析、モデルに基づいたクラスタリング法に関する内容を扱っている書物は比較的に少ない。クラスター分析の初心者向きには参考文献［7］がある。
・「クラスター分析の初心者向きには参考文献［7］がある。」（2004年）付近
http://www.shuwasystem.co.jp/products/7980html/0792.html
> アプリオリアルゴリズム
> サポートベクターマシーン
> マシーン
> マシーン
…うーん。ちょっと時代を感じます。「Apriori」については[3514]を参照。そして、この本をいきなり読むと、結局、何をしたらいいのかがわからないというところに戻ってきてしまいそうではあります。
・[3474]
> つごう、13,640円の「研きゅう費」を「獲とく」した我々はさっそく…えーと、どこへ飛ぶんでしたっけ。
> きっぷは目的地まで正しく買いましょう！
> ドラえもんネクタイや蛍光ペンの誘惑から逃れながら我々さっそうと目指すは一路…どこでしたっけ＆まだそこにいたんですかっ。（※演出です。）
・ウィキペディアのウ「様々な適用」付近
https://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%83%E3%82%AB%E3%83%A0%E3%81%AE%E5%89%83%E5%88%80#.E6.A7.98.E3.80.85.E3.81.AA.E9.81.A9.E7.94.A8
> ある測定データが与えられたとき、一般に、統計モデルを複雑にすればするほど、その測定データをうまく説明できる。しかし、そのようなモデルは、不必要に複雑なモデルであり、計算することが困難であるばかりでなく、過去のデータに過剰に適合してしまい、未来のデータを説明できなくなってしまう（過適合）。
『ほどよく複雑でなければクラスタリングをする意味がない（より簡潔に説明したいだけであれば主成分分析をしさえすれば済む）』というあたりのことをいうのはどれなのか、簡単にはわかりませんでした。（※恐縮です。）
○もっと！「k平均法（k-means clustering）」をはげしくカワサキっ
・再びかみつたセンセイ「［神嶌 03b］の10節」（2003年）
http://www.kamishima.net/archive/2002-s-jsai-clustering-2.pdf
> クラスタが超球形でない場合は，標準偏差で正規化したマハラノビス距離などのスケーリングの変換したり，そのような目的で開発された手法（［神嶌 03b］の10節）を利用すべきです．
> 任意形状のクラスタを抽出する近年の代表的な研究にEsterらのDBSCAN［Ester 96］がある．
> GuhaらのCURE［Guha 98］は，k-means法のようにセントロイド一つでクラスタを代表させる代りに，複数の代表点を用いる手法を提案している．
おおらかな気持ちでナイーブにも直感的には、データがスパースであるとき、いたってふつーのk-meansでも実質的に（ある種『残骸』みたいな感じで）そういうことになったりしないんでしょうか。…そういうことが確かめられるデータセットはこれやでー（どやぁ）的なのが、ポンとどこかにあったりしないでしょうか。…気になります！
> その他，グラフを用いたクラスタリングも任意の形状のクラスタが抽出できる．
明示的にグラフですよんと主張していなくても、実質的にグラフ的な扱いになっているということも、ありそうな気がしてきました。本当でしょうか。…かなり『データによる』のでなんともですよ、ええ。（※恐縮です。）
> その他，フラクタル次元を用いる手法［Barbará 00］などもある．
ぬおー（略）。
もう1つ気になるのは、「R」のkmeans関数で特に指定しなかったときにデフォルトで使われるとされる「Hartigan-Wong」アルゴリズムの詳細です。
・「Hartigan-Wong」付近のスライドです（アリガトウ！ …アリガトウっ！！）
https://image.slidesharecdn.com/kmeans-150630002125-lva1-app6891/95/kmeans-17-638.jpg
https://image.slidesharecdn.com/kmeans-150630002125-lva1-app6891/95/kmeans-18-638.jpg
きわめておおざっぱには、「途中で投げ出さないLloyd！」とでもいいましょうか、Lloydアルゴリズムを何通りも走らせてみるようなのを最初からやっているようなものといいましょうか、そんな感じに早合点してみました。（あくまで早合点です。）
・「Hartigan's Method: k-means Clustering without Voronoi」（2010年）
http://proceedings.mlr.press/v9/telgarsky10a/telgarsky10a.pdf
「without Voronoi」っ！ …うーん。
> Empirical tests verify not only good optimization performance relative to Lloyd's method, but also good running time.
> Note that the ratio is of corresponding attributes: thus min cost means the best optimization cost of Hartigan's method, divided by the best optimization cost of Lloyd's method.
> On average, Hartigan's method provides an improvement of roughly 5-10%.
> Hartigan, J. A. (1975).
> Hartigan, J. A. and M. A. Wong (1979).
うーん（略）。時間をかけて「Lloydアルゴリズムを何通りも走らせてみるようなの」よりは「速い」よ、ということでしょうか。本当でしょうか。
・SPSSのばやい付近
https://www.ibm.com/support/knowledgecenter/ja/SSLVMB_22.0.0/com.ibm.spss.statistics.help/spss/base/idh_quic.htm
https://www.ibm.com/support/knowledgecenter/ja/SSLVMB_22.0.0/com.ibm.spss.statistics.cs/spss/images/images_dlg/dlg_kmeans_options_telco_01.jpg
https://www.ibm.com/support/knowledgecenter/ja/SSLVMB_22.0.0/com.ibm.spss.statistics.cs/spss/images/images_m-r/out_kmeans_anova_telco_01.jpg
> 分散分析のF統計量を要求することもできます。この統計は便宜的なものですが（この手続きは異なるグループを形成しようとするため）、統計量の相対的なサイズにより、グループの分離に対する各変数の寄与率の情報が提供されます。
> The ANOVA table indicates which variables contribute the most to your cluster solution. Variables with large F values provide the greatest separation between clusters.
うーん。歴史の長いSPSSですから、黙ってアルゴリズムを変えたりしないはずで、何も説明がない限りはLloydそのものなのでしょうか。本当でしょうか。SPSSを使える環境にあるかたで検証されたかた、おられないでしょうか。（恐縮です。）
・「Rとグラフで実感する生命科学のための統計入門」羊土社（2017年3月10日）
https://www.yodosha.co.jp/yodobook/book/9784758120791/
> 無料ソフトRを使うことで手を動かしながら統計解析の基礎が身につく！
こういう盛りだくさんな教科書は挫折のもとですよ、ええ。それに、「R」の開発者へのビスケットと、こういう数学でよい成績が取れなかったひとへのたわしが不足していませんかねぇ。（棒読み）あまつさえ、こんなに盛りだくさんなのに、「k-meansしてからF検定する」というSPSSみたいな話には到達しないまま終わるんでしょうか。本当でしょうか。
・「日本IBM、ベイズ統計機能などを搭載した統計解析ソフトウェア「SPSS Statistics 25」」（2017年8月10日）
http://cloud.watch.impress.co.jp/docs/news/1075152.html
> IBM SPSS Statisticsは、初心者から分析の専門家までが利用可能な統計解析ツール。高度な多変量解析の手法を豊富に搭載しながらも、わかりやすい操作で、誰でも簡単にデータ分析を実行できる点が特徴という。もともとは、社会調査の統計解析ツールとして1968年にスタンフォード大学で誕生。
> “ベイズ推論”を、統計解析アルゴリズムの新機能として搭載
> 混合モデルにおける経験最良線形不偏予測量の利用や、時系列データの共変量設定を可能に
「報告編」（[3528]）に続きます。
| 