K-means 法

ウィキペディア

k-means++法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/09 08:34 UTC 版)

k-means++法は、非階層型クラスタリング手法の1つで、k-means法の初期値の選択に改良を行なった方法である。 標準的なk-means法が頻繁にクラスタとすべきではないものにもクラスタ割り当てを行ってしまう問題や、 k-means法がNP困難な問題であることを解消するために、2007年にDavid ArthurとSergei Vassilvitskiiによって提案された。 2006年にRafail Ostrovskyらによって提案されたthree seeding methodと似ているが初期シードの分布が異なる。

背景

k-means法はクラスタ中心を見つけるアルゴリズムである。クラスタ中心とはクラス内分散を最小化する点であり、言い換えるとクラス内のそれぞれのデータ点との距離の二乗和を最小化する点である。任意の入力に対してk-meansの真の解を求める問題はNP困難な問題であるため、解の近似がよく行われる。その手法はLloydアルゴリズムまたはk-meansアルゴリズムと呼ばれ、多くの応用分野で用いられており、高速に近似解が得られる。

しかし、k-means法には2つの理論的な問題がある。

1. 1つ目は、最悪計算時間は入力サイズに対して超多項式（super-polynomial）であること。
2. もうひとつは、近似解は最適なクラスタリング結果と比べ関していくらでも悪くなることがあること。

このk-means++法は2つ目の問題の解消を目指した手法であり、標準的なk-means法の反復を行う前にクラスタ中心を初期化するプロセスを行う。k-means++法の初期化は、最適なk-means法の解に比べてO(log k) の近似比率で解を得ることが保証されている。

アルゴリズム

このk-means++法は、初期のk個のクラスタ中心はなるべく離れている方が良いという考えにもとづいている。まず始めにデータ点をランダムに選び1つ目のクラスタ中心とし、全てのデータ点とその最近傍のクラスタ中心の距離を求め、その距離の二乗に比例した確率でクラスタ中心として選ばれていないデータ点をクラスタ中心としてランダムに選ぶ。

アルゴリズムは以下の手順で行われる。

データ点からランダムに1つ選びそれをクラスタ中心とする。
while $k$個のクラスタ中心が選ばれるまで do
    それぞれのデータ点$x$に関して、その点の最近傍中心との距離$D(x)$を計算する。
    データ点$x$に関して重みつき確率分布 ${\frac {D(x)^{2}}{\sum D(x)^{2}}}$を用いて、データ点の中から新しいクラスタ中心をランダムに選ぶ。
選ばれたクラスタ中心を初期値として標準的なk-means法を行う。

この初期値決めの方法はk-means法を著しく改善する。 初期値決めに余計な時間がかかるが、k-means法は収束がとても早く計算時間はそれほどかからない。 著者らはこの手法を実データと人工データの両方で実験を行い、 だいたい収束スピードに関しては2倍、あるデータセットでは誤差が1000分の1となったことを報告している。 一連の実験では定番のk-means法に速度と誤差に関してつねに優っていた。

それに加え、このアルゴリズムの近似率が計算されている。k-means++法は 平均的に$O(\log k)$の近似比率で近似可能であることが保証されている。$k$はクラスタ数である。これに対し、標準的なk-means法では最適値に対して任意の精度で悪くなることがある。

ソフトウェア

• ELKI
• GNU R
• OpenCV
• Weka
• CMU's GraphLab

関連項目

• x-means法 - k=2で再帰的にk-meansを行う方法。終了条件はベイズ情報量規準(BSI: Bayesian information criterion)で決める。

k平均法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/28 17:12 UTC 版)

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|k-means clustering|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

k平均法の収束

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習（英語版） 半教師あり学習（英語版） 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

k平均法（kへいきんほう、英: k-means clustering）は、非階層型クラスタリングのアルゴリズム。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法（k-means）、c-平均法（c-means）とも呼ばれる。

何度か再発見されており、まず、Hugo Steinhusが1957年に発表し^[1]、Stuart Lloydが1957年に考案し、E.W.Forgyが1965年に発表し^[2]、James MacQueenが1967年に発表しk-meansと命名した^[3]。

数式で表現すると、下記最適化問題を解くアルゴリズム^[4]。本アルゴリズムでは最小値ではなく初期値依存の極小値に収束する。

${\displaystyle \operatorname {arg\,min} _{V_{1},\dotsc ,V_{k}}\sum _{i=1}^{n}\min _{j}\left\|x_{i}-V_{j}\right\|^{2}}$