Tools + Simulatorsnanase.cc / tools

クラスタリング

k-means

代表点ベース

階層

密度ベース

分布ベース

グラフベース

ニューラルネットワーク

グリッドベース

クラスタ数 k クラスタ数 k

バッチの割合 バッチの割合

反復回数 反復回数

ファジィ係数 ファジィ係数

k の上限 k の上限

カーネルの幅 カーネルの幅

CF の半径の上限 CF の半径の上限

代表点の数 代表点の数

収縮率 収縮率

半径 ε 半径 ε

最小点数 最小点数

切断の閾値 切断の閾値

最小クラスタサイズ 最小クラスタサイズ

バンド幅 バンド幅

バンド幅 バンド幅

接続距離の上限 接続距離の上限

カットオフ距離 カットオフ距離

ノイズの閾値 ノイズの閾値

成分数の上限 成分数の上限

混合比の事前分布 混合比の事前分布

反復回数の上限 反復回数の上限

近傍数 近傍数

近傍数 近傍数

近傍数 近傍数

選好度の倍率 選好度の倍率

反復回数の上限 反復回数の上限

インフレーション係数 インフレーション係数

解像度 解像度

格子の幅 格子の幅

エポック数 エポック数

ノードの数 ノードの数

ノード数の上限 ノード数の上限

セルの一辺 セルの一辺

密度の閾値 密度の閾値

点の数 点の数

点

外れ値 外れ値

%

正解との一致度
–
クラスタ数
–
ノイズ
–点
反復回数
–回
距離の計算
–回

動作原理と式

正解との一致度

2 点の組ごとに「同じクラスタか」を正解と比べる調整ランド指数です[1]。偶然の一致を引くので、完全に一致すれば 1、でたらめなら 0 付近になります。クラスタの番号の付け方にはよりません。

ARI=∑ij(nij2)−E12(∑i(ai2)+∑j(bj2))−E,E=∑i(ai2)∑j(bj2)(n2)

nij は正解 i で結果 j の点の数、ai と bj はその行と列の和です。

代表点ベース

k-means は点と重心の距離の 2 乗の和を減らします[2]。割り当てと重心の移動のどちらでも和は増えないので必ず止まりますが、最小とは限りません。

J=∑c=1k∑x∈Cc‖x−μc‖2

塊が丸くて大きさのそろったデータに向きます。三日月や同心円では、形によらず平面を直線で分けてしまいます。

階層

凝集型は、結合した後の距離を Lance-Williams の更新式で求めます[13]。結合法はクラスタどうしの距離の定義の違いです。

  • 最短距離法: 最も近い 2 点の距離。細長くつながった形を拾うが、外れ値の橋で 1 つにつながりやすい
  • 最長距離法: 最も遠い 2 点の距離。大きさのそろった丸いクラスタになりやすい
  • 群平均法: 全ての組の距離の平均
  • ウォード法: 結合で増える誤差平方和[12]

樹形図の高さは結合したときの距離です。ウォード法は誤差平方和の増加の平方根を高さにしています。

密度ベース

DBSCAN は、半径 ε の円の中に最小点数以上の点がある点をコア点とし、コア点の円でつながる点を 1 つのクラスタにします[16]。形によらず分けられますが、密度の違うクラスタを 1 つの半径で扱えません。OPTICS と HDBSCAN は半径をいくつも見るので、この弱点を減らせます。

Mean Shift はガウス関数で重み付けした平均へ点を動かす反復で、密度の勾配を登ります[19]。

x′=∑ixiexp(−‖x−xi‖2/2h2)∑iexp(−‖x−xi‖2/2h2)

分布ベース

混合ガウス分布は、点が k 個のガウス分布のどれかから生まれたと考えます。EM 法で所属確率と分布の更新を交互に行い、対数尤度を増やします[23]。楕円は 1σ と 2σ の等確率線です。

ric=πc𝒩(xi∣μc,Σc)∑qπq𝒩(xi∣μq,Σq)

変分ベイズは混合比に事前分布を置くので、要らない成分の重みが 0 へ近づき、クラスタ数が決まります[24]。

グラフベース

スペクトラルは、近傍グラフの正規化した隣接行列の固有ベクトルを新しい座標にします[25][26]。つながりの弱い所で分けるので、三日月や同心円も分けられます。図の座標は第 2 と第 3 の固有ベクトルで、k-means は第 1 から第 k までを行ごとに正規化した座標で行います。

A=D−1/2WD−1/2

最小全域木の切断は最短距離法と同じ分け方になります。長い辺の切り方が同じだからです。

ニューラルネットワークとグリッドベース

自己組織化マップ・Neural Gas・Growing Neural Gas は、点を 1 つずつ見てノードを近づける学習です。CLIQUE は平面をセルに分け、点の多いセルをつなぎます。セルの大きさだけで決まるので速い代わりに、境界が階段状になります。

手法の一覧

n は点の数、k はクラスタ数、i は反復回数、b はバッチの点の数、M はノードの数です。計算量はこのツールの実装の距離の計算の目安で、速い実装の値ではありません。

手法分類計算量クラスタ数点の上限出典
k-means代表点ベース𝑛𝑘𝑖指定3,000[2][3][4]
ミニバッチ k-means代表点ベース𝑏𝑘𝑖指定3,000[5]
k-medoids代表点ベース𝑘(𝑛−𝑘)²𝑖指定1,000[6]
k-medians代表点ベース𝑛𝑘𝑖指定3,000[7]
Fuzzy c-means代表点ベース𝑛𝑘²𝑖指定3,000[8]
二分 k-means代表点ベース𝑛𝑘𝑖指定3,000[9]
X-means代表点ベース𝑛𝑘𝑖自動3,000[10]
カーネル k-means代表点ベース𝑛²𝑖指定1,000[11]
ウォード法階層𝑛³指定1,000[12][13]
最長距離法階層𝑛³指定1,000[13]
群平均法階層𝑛³指定1,000[13]
最短距離法階層𝑛³指定1,000[13]
DIANA階層𝑛²𝑘指定500[6]
BIRCH階層𝑛 log 𝑛指定3,000[14]
CURE階層𝑛² log 𝑛指定500[15]
DBSCAN密度ベース𝑛²自動3,000[16]
OPTICS密度ベース𝑛²自動3,000[17]
HDBSCAN密度ベース𝑛²自動3,000[18]
Mean Shift密度ベース𝑛²𝑖自動1,500[19]
Quick Shift密度ベース𝑛²自動3,000[20]
Density Peaks密度ベース𝑛²指定3,000[21]
DENCLUE密度ベース𝑛²𝑖自動1,500[22]
混合ガウス分布分布ベース𝑛𝑘𝑖指定3,000[23]
変分ベイズ混合ガウス分布分布ベース𝑛𝐾𝑖自動3,000[24]
スペクトラルグラフベース𝑛³指定800[25][26]
Affinity Propagationグラフベース𝑛²𝑖自動1,000[27]
最小全域木グラフベース𝑛²指定3,000[28]
ラベル伝播グラフベース𝑛²自動3,000[29]
Markov Clusteringグラフベース𝑛³𝑖自動1,000[30]
Louvainグラフベース𝑛 log 𝑛自動3,000[31]
自己組織化マップニューラルネットワーク𝑛𝑀·エポック指定3,000[32]
Neural Gasニューラルネットワーク𝑛𝑀 log 𝑀·エポック指定3,000[33]
Growing Neural Gasニューラルネットワーク𝑛𝑀自動3,000[34]
CLIQUEグリッドベース𝑛自動3,000[35]

出典

  1. 調整ランド指数L. Hubert, P. Arabie, “Comparing Partitions,” Journal of Classification, vol. 2, no. 1, pp. 193–218, 1985
  2. k-means の反復S. P. Lloyd, “Least Squares Quantization in PCM,” IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 129–137, 1982
  3. k-means の名前J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297, 1967
  4. k-means++D. Arthur, S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding,” Proc. SODA 2007, pp. 1027–1035
  5. ミニバッチ k-meansD. Sculley, “Web-Scale k-Means Clustering,” Proc. WWW 2010, pp. 1177–1178
  6. k-medoids（PAM）・DIANAL. Kaufman, P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, Wiley, 1990
  7. k-mediansP. S. Bradley, O. L. Mangasarian, W. N. Street, “Clustering via Concave Minimization,” NIPS 9, pp. 368–374, 1996
  8. Fuzzy c-meansJ. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, 1981
  9. 二分 k-meansM. Steinbach, G. Karypis, V. Kumar, “A Comparison of Document Clustering Techniques,” KDD Workshop on Text Mining, 2000
  10. X-meansD. Pelleg, A. Moore, “X-means: Extending K-means with Efficient Estimation of the Number of Clusters,” Proc. ICML 2000, pp. 727–734
  11. カーネル k-meansB. Schölkopf, A. Smola, K.-R. Müller, “Nonlinear Component Analysis as a Kernel Eigenvalue Problem,” Neural Computation, vol. 10, no. 5, pp. 1299–1319, 1998
  12. ウォード法J. H. Ward, “Hierarchical Grouping to Optimize an Objective Function,” JASA, vol. 58, no. 301, pp. 236–244, 1963
  13. 結合の距離の更新式G. N. Lance, W. T. Williams, “A General Theory of Classificatory Sorting Strategies: 1. Hierarchical Systems,” The Computer Journal, vol. 9, no. 4, pp. 373–380, 1967
  14. BIRCHT. Zhang, R. Ramakrishnan, M. Livny, “BIRCH: An Efficient Data Clustering Method for Very Large Databases,” Proc. SIGMOD 1996, pp. 103–114
  15. CURES. Guha, R. Rastogi, K. Shim, “CURE: An Efficient Clustering Algorithm for Large Databases,” Proc. SIGMOD 1998, pp. 73–84
  16. DBSCANM. Ester, H.-P. Kriegel, J. Sander, X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proc. KDD-96, pp. 226–231
  17. OPTICSM. Ankerst, M. M. Breunig, H.-P. Kriegel, J. Sander, “OPTICS: Ordering Points to Identify the Clustering Structure,” Proc. SIGMOD 1999, pp. 49–60
  18. HDBSCANR. J. G. B. Campello, D. Moulavi, J. Sander, “Density-Based Clustering Based on Hierarchical Density Estimates,” Proc. PAKDD 2013, LNCS 7819, pp. 160–172
  19. Mean ShiftD. Comaniciu, P. Meer, “Mean Shift: A Robust Approach Toward Feature Space Analysis,” IEEE TPAMI, vol. 24, no. 5, pp. 603–619, 2002
  20. Quick ShiftA. Vedaldi, S. Soatto, “Quick Shift and Kernel Methods for Mode Seeking,” Proc. ECCV 2008, LNCS 5305, pp. 705–718
  21. Density PeaksA. Rodriguez, A. Laio, “Clustering by Fast Search and Find of Density Peaks,” Science, vol. 344, no. 6191, pp. 1492–1496, 2014
  22. DENCLUEA. Hinneburg, D. A. Keim, “An Efficient Approach to Clustering in Large Multimedia Databases with Noise,” Proc. KDD-98, pp. 58–65
  23. 混合ガウス分布の EMA. P. Dempster, N. M. Laird, D. B. Rubin, “Maximum Likelihood from Incomplete Data via the EM Algorithm,” JRSS Series B, vol. 39, no. 1, pp. 1–22, 1977
  24. 変分ベイズ混合ガウス分布（10.2 節）C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006
  25. スペクトラルA. Y. Ng, M. I. Jordan, Y. Weiss, “On Spectral Clustering: Analysis and an Algorithm,” NIPS 14, pp. 849–856, 2001
  26. スペクトラルの解説U. von Luxburg, “A Tutorial on Spectral Clustering,” Statistics and Computing, vol. 17, no. 4, pp. 395–416, 2007
  27. Affinity PropagationB. J. Frey, D. Dueck, “Clustering by Passing Messages Between Data Points,” Science, vol. 315, no. 5814, pp. 972–976, 2007
  28. 最小全域木C. T. Zahn, “Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters,” IEEE Transactions on Computers, vol. C-20, no. 1, pp. 68–86, 1971
  29. ラベル伝播U. N. Raghavan, R. Albert, S. Kumara, “Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks,” Physical Review E, vol. 76, 036106, 2007
  30. Markov ClusteringS. van Dongen, Graph Clustering by Flow Simulation, PhD thesis, University of Utrecht, 2000
  31. LouvainV. D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, “Fast Unfolding of Communities in Large Networks,” Journal of Statistical Mechanics, P10008, 2008
  32. 自己組織化マップT. Kohonen, “Self-Organized Formation of Topologically Correct Feature Maps,” Biological Cybernetics, vol. 43, no. 1, pp. 59–69, 1982
  33. Neural GasT. Martinetz, K. Schulten, “A “Neural-Gas” Network Learns Topologies,” Artificial Neural Networks (ICANN-91), pp. 397–402, 1991
  34. Growing Neural GasB. Fritzke, “A Growing Neural Gas Network Learns Topologies,” NIPS 7, pp. 625–632, 1995
  35. CLIQUER. Agrawal, J. Gehrke, D. Gunopulos, P. Raghavan, “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications,” Proc. SIGMOD 1998, pp. 94–105

このツールで決めたこと

  • 座標は幅 1.6・高さ 1 の箱。点の数は 400 まで、描画は 3,000 まで
  • 手法の一覧の「点の上限」を超えると、その数の点をランダムに抽出して計算し、残りの点は最も近い抽出点のクラスタへ入れる
  • 描いた点は、比較では 1,000 点、一覧では 300 点を抽出して使う。パラメータは抽出した点の間隔から決める
  • 再生はコマを 420 まで、長さを 24 秒までに縮める
  • 外れ値は箱の中に一様に足す。一致度の計算から正解の外れ値は除き、ノイズの点は 1 点ずつ別のクラスタとして数える
  • クラスタの色は、大きいクラスタから順に正解と最も重なる色にする。9 個目以降は画面の線の色
  • 一覧は点の数 150、1 マスのコマは 48 まで。k-means は初期配置の運を除くため k-means++
  • k-means の既定の初期配置はランダム。k-means++ だとすぐ収束して動きが見えないため
  • 既定のパラメータはデータごとに手で選んだ値。半径は点の数の平方根に反比例、近傍数は比例させる
  • スペクトラルの近傍グラフは、全体の 1 割未満の破片を最も近い点へつなぐ。全ての点の組に 10⁻⁶ の重みを足す
  • k-medoids は PAM の BUILD と SWAP
  • BIRCH の CF 木は枝分かれと葉の項目数を 8 まで。最後の統合はウォード法。点の再割り当てはしない
  • CURE は標本化と分割をしない
  • X-means の BIC の分散は 1 次元あたりの値
  • OPTICS は生成距離を無限大とし、クラスタは論文の ExtractDBSCAN と同じく閾値で切り出す
  • HDBSCAN は凝縮した木を過剰質量で選ぶ。根のクラスタは選ばない
  • Mean Shift と DENCLUE は同じ山登りの式を使う。ウィンドウは半径の 3 倍で打ち切り、半径の半分より近い到達点を同じピークとする
  • DENCLUE のノイズの閾値は最も高い極大との比
  • 変分ベイズの事前分布の平均は全点の平均、自由度は 4
  • Affinity Propagation の選好度は類似度の中央値の倍率。減衰は 0.75 で、代表点が 15 回変わらなければ止める
  • 最小全域木は Zahn の不整合の判定を使わず、長い順に切る
  • Markov Clustering は 0.002 未満の遷移確率を捨てる
  • 自己組織化マップと Neural Gas は最後にノードをウォード法で k 個に統合する
  • CLIQUE は 2 次元だけを扱うので部分空間の探索はない
  • DOI のある出典は Crossref で書誌を確認した。本文は読み合わせていない。DOI のない出典は未確認

関連ツール

すべてのツール