Academication-AI

AI活用・オープンイノベーションのためのメディアです。最先端のAIビジネス事例情報と研究情報をお届けします。

【研究者向け】Fast and Provably Good Seedings for k-Means — NIPS2016

【一言まとめ】重要な手法であるk-meansの初期値設定の改善手法を提案した。

【著者】Olivier Bachem, Mario Lucic, S. Hamed Hassani,Andreas Krause

【所属機関】ETH Zurich (チューリッヒ工科大学)

【URL】https://papers.nips.cc/paper/6478-fast-and-provably-good-seedings-for-k-means

【Abstract】
Seeding — the task of finding initial cluster centers — is critical in obtaining high-quality clusterings for k-Means. However, k-means++ seeding, the state of the art algorithm, does not scale well to massive datasets as it is inherently sequential and requires k full passes through the data. It was recently shown that Markov chain Monte Carlo sampling can be used to efficiently approximate the seeding step of k-means++. However, this result requires assumptions on the data generating distribution. We propose a simple yet fast seeding algorithm that produces *provably* good clusterings even *without assumptions* on the data. Our analysis shows that the algorithm allows for a favourable trade-off between solution quality and computational cost, speeding up k-means++ seeding by up to several orders of magnitude. We validate our theoretical results in extensive experiments on a variety of real-world data sets.

【Abstract翻訳】
Seeding — 最初のクラスタ中心を見つけるタスクは、k-Meansのための高品質なクラスタリングを得る上で非常に重要です。 しかし、k-means ++シード(最先端のアルゴリズム)は、本質的にシーケンシャルであり、データをk回フルパスする必要があるため、大量のデータセットには適していません。 最近、マルコフ連鎖モンテカルロサンプリングを用いて、k-means ++の播種ステップを効率的に近似することが示された。 しかし、この結果は、データ生成分布に関する仮定を必要とする。 私たちは、単純で高速なシードアルゴリズムを提案します。このアルゴリズムは、データを前提としない*良いクラスタリングを証明します*。 我々の分析によれば、このアルゴリズムは解の品質と計算コストとの間の有利なトレードオフを可能にし、k-means ++シードを最大数桁まで高速化します。 さまざまな現実世界のデータセットについて広範な実験を行い、理論結果を検証します。

 

【どんなもの?】
K-means 法の初期値設定方法の改善手法

【先行研究と比べてどこがすごい?】
既存手法の弱いところを補強している
→分布の仮定が無い.理論解析)

【技術や手法のキモはどこ?】
MCMCを使うが,最初のクラスタ中心に注目

【どうやって有効だと検証した?】
・連鎖長に対する反応
・距離計算回数

【議論はある?】
1回全データのスキャンが必要

【次に読むべき論文は?】
・ Approximate k-means++ in sublinear time — AAAI

【関連リンク】