クラスタリングの基礎を身につける練習です. はじめに実装したもの, 後半にクラスタリングについてのメモを少しだけ.
できたもの
こちらのページです.
Amazonの画像から自動的に色を抽出するようにしました. アニメキャラの色に基づいてパワーポイントやキーノートのテーマを作る時にだけ使えるかもしれません.
追記：クリップスタジオで読み込める形式のファイルを出力するようにしました
実装内容
仕組み
Amazonの画像からRGBデータを取得、12クラスにクラスタリング、クラスタリングのまとまりをデータ数とクラスタごとの平均色の類似度(つまり、クラスタのセントロイドの距離)に基づいて重み付け、最後に重みが大きい上位8クラスを選んで表示しています.
改善点
初音ミクのリボンの色など、小さいけれどもキャラを表している色を抽出するのに失敗してしまいます. そのため, 色の類似度を計算して類似度が離れているほど重要度を増やすような処理を加えて抽出します.
初音ミクの場合は「青色っぽい色ばかり抽出される」→「データ数は少ないけれど赤色もワンポイントになってそう」としています, 失敗していますが...。今後の課題. k-means minus minus を使って外れ値っぽいものをワンポイントの色として抽出してみた方がよかったかもしれません.
おまけ
文字と背景の組み合わせチェックも見れるようにしました. 需要なさそうですが, スライドなどを作る時に個人的に使いたいので作りました.
今後の課題
クラスタリング数を動的に変更する
有名な論文ですが
Pelleg, Dan, and Andrew W. Moore. "X-means: Extending K-means with Efficient Estimation of the Number of Clusters." ICML. Vol. 1. 2000.
にて提案された X-means 法にてクラスタ数を自動で決定するように変更したい. ベイズ情報量規準で分割を止める最適なクラスタ数を求める手法.
ワンポイントの色の抽出
今回は適当に (R, G, B) の値の絶対距離を用いて色の離れ具合を計算しているのでちゃんとした距離を定義して抽出をうまくいくようにしたい.
クラスタリングについてのメモ
クラスタリングするアルゴリズムの分類
クラスタリングと言っても問題設定なども含めて様々なバリエーションが思いつく.
階層的なクラスタリング手法
日本語記事がありませんが仕組みはHierarchical clustering - Wikipedia の通りです.
- 単連結法(Single-linkage clustering)
- 完全連結法(Complete-linkage clustering)
- UPGMA(群平均法)
- WPGMA
- Ward’s method
繰り返し割り当てを変えていく手法
一番よく知られる手法である k-means が代表的. 任意のデータ間の類似度計算ができないと動かないk-meansを改良したのがk-medoids.
- K-means
- 各クラスタの平均ベクトルとの距離の二乗を最小化
- K-medoids
- medoidとデータの距離の和を最小化
- K-means++(k-means plus plus)
- K-meansの初期値の決め方を改善, 初期のk個のクラスタ中心がなるべく離れるような選択を, データ間距離に基づいた確率分布に基づいて行う.
- K-means--(k-means minus minus)
- k このクラスタと L この外れ値クラスタを分ける最適化問題を定義して, 外れ値に大きく結果が左右される点を改善
- X-means
- ベイズ情報量規準に基づいてクラスタの分割停止タイミングを決定する
- G-means
- データがガウス分布に基づいて生成されると仮定して, 各クラスタがガウス分布に基づいて生成されるかをアンダーソン–ダーリング検定で確かめがらクラスタを作る?
- GX-means
- 上記二つの拡張
- S-means
- データが混合ガウス分布から生成されていると仮定しない. しかし初期値として定める閾値によって結果が大きく変化する.
その他
- PG-means
- MACEmeans
- NSS-AKmeans
データの分布密度からクラスタを決める手法
- DBCLASD
- Xu, Xiaowei, et al. "A distribution-based clustering algorithm for mining in large spatial databases." Data Engineering, 1998. Proceedings., 14th International Conference on. IEEE, 1998.
- DENCLUE
- カーネル密度推定を元にしたクラスタリング手法
モデルベースの手法
- 自己組織化マップ(SOM)
- データ間の関係性を維持しながら任意の次元に写像する様に学習するニューラルネットワーク. 初期値に結果が依存しやすい.
参考文献
[1] Chawla, Sanjay, and Aristides Gionis. "k-means–: A unified approach to clustering and outlier detection." Proceedings of the 2013 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2013.
Jain, Anil K. "Data clustering: 50 years beyond K-means." Pattern recognition letters 31.8 (2010): 651-666.
Murtagh, Fionn, and Pedro Contreras. "Algorithms for hierarchical clustering: an overview." Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 2.1 (2012): 86-97.
Hancer, Emrah, and Dervis Karaboga. "A comprehensive survey of traditional, merge-split and evolutionary approaches proposed for determination of cluster number." Swarm and Evolutionary Computation 32 (2017): 49-67.
